Split Tallies: A Discrete Certificate Calculus for Auditing Dynamic Ordered Sets in Constant Memory
Catching sneaky changes to ordered lists using almost no memory
Researchers developed a method for spotting when someone secretly alters a growing or shrinking ordered list of data—detecting wrong answers with near-certainty despite the auditor only remembering five numbers. The approach works by tracking invisible gaps between items and checking if the record of when gaps appeared matches when they disappeared.
Databases and financial ledgers often rely on untrusted third parties to maintain sorted data correctly. This method lets an auditor verify that data hasn't been corrupted or manipulated without storing a copy of the entire dataset—critical for systems where storage is expensive or memory is constrained, like blockchain systems or distributed databases.