💻 computer science

Split Tallies: A Discrete Certificate Calculus for Auditing Dynamic Ordered Sets in Constant Memory

This paper introduces "Split Tallies," a constant-memory auditing scheme that verifies dynamic ordered sets maintained by an untrusted party by tracking maximal gaps through a discrete certificate calculus, achieving high-probability security against computationally unbounded adversaries while proving that such efficiency is impossible without hidden randomness or timestamps.

Original authors: Faruk Alpay, Levent Sarioglu

Published 2026-06-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Faruk Alpay, Levent Sarioglu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, but potentially dishonest, librarian (the Maintainer) who manages a library of books arranged in perfect order. You (the User) ask questions like "Is book X here?" or "What's the book right before Y?" The librarian answers instantly. However, you don't trust the librarian's internal memory, and you can't check their shelves every time you ask a question because that would be too slow.

You need a way to verify later that every answer the librarian gave was actually correct, without needing to remember the entire library yourself.

This paper introduces a system called Split Tallies to solve this problem. It uses a clever mix of ancient accounting history and modern math to create a "certificate" that proves the librarian is telling the truth, using almost no memory on your end.

Here is how it works, broken down into simple concepts:

1. The Ancient Metaphor: The Split Stick

The idea is inspired by 600-year-old English "tally sticks."

The Story: If a merchant lent money to a farmer, they would cut notches into a wooden stick to represent the amount. Then, they would split the stick lengthwise. The merchant kept one half (the Stock), and the farmer kept the other (the Foil).
The Magic: When it was time to pay back, they would put the two halves together. Only the real stick would fit perfectly because the grain of the wood and the notches would align. A fake stick would never match.
In This Paper:
- The Librarian holds the "Foil" (their internal memory of the library).
- The Auditor (you) holds the "Stock" (a tiny, secret list of 5 numbers).
- The Public Tally is a list of "notches" the librarian must write down after every single action.
- The Audit is the moment you check if the librarian's story matches your secret list.

2. The Core Trick: Tracking "Gaps" Instead of Books

Most people think about a library as a list of books. This paper says: "No, think about the empty spaces between the books."

Imagine the library shelf has a start (0) and an end (U).
If the shelf is empty, there is one giant gap from start to finish.
If you add a book, you split that big gap into two smaller gaps.
If you remove a book, you merge two gaps back into one.

The paper proves that if you know exactly how the gaps are connected, you know exactly where every book is. The librarian doesn't just say "Book X is here"; they must point to the specific gap that proves it.

3. The Rules of the Game (The "Indenture")

To prevent the librarian from lying, the system forces them to follow strict rules, like a game of musical chairs with strict timing:

The Public Clock: Every time a new gap is created (a book is added), it gets a unique, sequential ID number (like a timestamp).
The Citation Rule: When the librarian answers a question, they must cite the ID number of the gap they are using.
- Crucial Rule: You can only cite a gap ID that was created before this moment. You cannot cite a "future" ID.
The Secret Math: The Auditor (you) holds a secret number. Every time a gap is born or used, the Auditor multiplies their secret numbers by a math formula involving that gap's ID.
- If the librarian is honest, the math works out perfectly at the end.
- If the librarian lies (e.g., says a book is there when it's not), they have to fake a gap ID. Because they don't know your secret number, the math will almost certainly fail at the end.

4. Why It's So Efficient

The paper claims this system is incredibly lightweight:

For You (The Auditor): You only need to remember 5 numbers and a "flag" (a yes/no switch). You don't need to store the library, the books, or the history. You just watch the stream of notches.
For the Librarian: They need a tiny bit of extra space (one extra number per book) to store the gap IDs.
The Cost: If the librarian tries to cheat, the chance of them getting away with it is astronomically low (less than 1 in a trillion for a million operations).

5. The "Impossible" Parts

The authors also proved that you cannot make this system simpler without breaking it:

No Randomness? If you don't use a secret random number, a clever liar can always fool you.
No Secrecy? If the librarian knows your secret number, they can fake the math.
No Time Limits? If the librarian is allowed to cite "future" IDs (time travel), they can create a perfect fake library that looks real. The "clock" rule is essential to stop this.

6. The "Rebalancing" Bonus

Libraries sometimes need to reorganize shelves (splitting a full shelf into two, or merging two empty ones). The paper shows that even these messy reorganization steps can be audited. They proved that no matter how many times the librarian reorganizes, the total number of "moves" is predictable. The auditor can simply count the librarian's "receipts" for these moves to ensure they aren't doing extra work to hide a lie.

Summary

This paper builds a mathematical lie detector for dynamic lists.

The Librarian does the work.
The Auditor does almost nothing (just 5 numbers).
The Tally is a public record of "notches."
The Result: You can verify with near-100% certainty that every answer given was correct, even if the librarian is a super-computer trying to trick you, and even if you have almost no memory to store the data.

It's like checking a bank account balance by looking at a single receipt that proves the math adds up, rather than counting every single coin in the vault.

Technical Summary: Split Tallies: A Discrete Certificate Calculus for Auditing Dynamic Ordered Sets in Constant Memory

Problem Statement

The paper addresses the verification of dynamic ordered sets maintained by an adversarial party (the "maintainer") and queried by a consumer. In many modern computing scenarios, data structures reside in untrusted environments (e.g., remote services, opaque hardware accelerators, or procured libraries). The consumer issues operations (insertions, deletions, membership tests, predecessor/successor queries, and extremum queries) and receives answers immediately, acting on them without delay.

The core challenge is to provide a certificate of correctness for the entire history of operations without requiring the consumer (the "auditor") to store the data structure itself or re-execute the operations. The auditor must be passive, storing only a constant amount of state (specifically, five machine words and a flag), while the maintainer appends a short "notch" (record) to a public, append-only sequence called a tally for every operation. The goal is to detect, with high probability, if the maintainer has ever provided an incorrect answer, even if the maintainer possesses unbounded computational power and adapts its strategy based on the visible history.

Methodology

The proposed solution, termed Split Tallies, draws inspiration from historical wooden tally sticks, where a debt was recorded by notching a stick, which was then split lengthwise. The creditor kept the "stock" and the debtor the "foil"; at settlement, the halves were meshed to verify authenticity. In this digital context:

The Tally: A public stream of notches appended by the maintainer.
The Stock: The auditor's private state (five words and a flag).
The Foil: The internal bookkeeping of the maintainer's structure.
The Audit: The process of "meshing" the stock against the foil (disclosed at the end of a session).

The Gap Calculus

The technical core of the paper is a discrete calculus of gaps. Instead of auditing the set $S$ directly, the system audits the family of maximal vacant intervals (gaps) that partition the ordered universe.

Representation: A set $S$ over a universe $\{1, \dots, U\}$ is uniquely represented by an interlocking chain of gaps $\langle a, b \rangle$ connecting sentinels $0$ and $U+1$ .
Normal Form: The paper proves that this gap family corresponds to the unique unit path from $0$ to $U+1$ in an interval acyclic graph.
Rewrites: Operations are modeled as local rewrites of this path:
- Insertion: Splits one gap $\langle a, b \rangle$ into two $\langle a, x \rangle, \langle x, b \rangle$ .
- Deletion: Merges two adjacent gaps $\langle a, x \rangle, \langle x, b \rangle$ into one $\langle a, b \rangle$ .
- Queries: Are answered by exhibiting a specific gap (e.g., the gap containing $x$ for membership, or the gap starting at $x$ for predecessor).

The Indenture Discipline

To audit these rewrites without storing the state, the auditor employs a fingerprinting mechanism based on polynomial identity testing over a finite field $\mathbb{F}_p$ :

Codes and Timestamps: Every gap birth is assigned a unique code (timestamp) via a public counter $\kappa$ .
Citations: Every operation must cite the codes of the gaps it consumes (rewrites).
Accumulators: The auditor maintains two accumulators, $A$ $A$ (for births) and $R$ $R$ (for consumptions). For a gap with code $c$ $c$ and endpoints $a, b$ $a, b$ , the value $\nu(a, b, c)$ $ν (a, b, c)$ is mapped into the field.
- On birth: $A \leftarrow A \cdot (z - \nu(a, b, c))$
- On consumption: $R \leftarrow R \cdot (z - \nu(a, b, c))$
- Here, $z$ is a secret field element chosen by the auditor before the session.
Verification: At the audit, the maintainer discloses the current set of gaps with their codes. The auditor checks if the disclosed gaps mesh (form a valid chain) and verifies if $A = R$ .

Key Mechanisms

Temporal Rule: A cited code must be strictly less than the counter value at the start of the event. This prevents the maintainer from "borrowing" future codes to forge a balanced ledger.
Forcing: Due to the uniqueness of the gap path, the correct answer to any query is a forced function of the cited gap. If the maintainer cites a gap that does not exist or is not live, the answer will be inconsistent with the gap's properties, or the ledger will become unbalanced.

Key Contributions and Results

1. The Audit Theorem (Soundness and Completeness)

The paper establishes that the scheme is perfectly complete (honest maintainers are always accepted) and $\epsilon$ -sound.

Soundness Error: If a maintainer provides even a single incorrect answer among $T$ operations, the probability of acceptance is at most $(4T + 1)/p$ .
Parameters: With a 61-bit prime $p$ (e.g., $2^{61}-1$ ), the error probability is below $2^{-38}$ for sessions up to one million operations.
Assumptions: No computational hardness assumptions are required; the security is information-theoretic against an unbounded adversary.

2. Impossibility and Necessity Results

The paper proves that the specific design choices are indispensable:

Deterministic Floor: Any deterministic auditor with end-of-session soundness must store at least $2n - \log_2(2n+1)$ bits of state for a set of size $n$ . This proves that randomness is a requirement, not a convenience.
Secret Randomness: If the auditor's random coins are visible to the maintainer, the soundness error becomes 1 (the maintainer can always forge a transcript). Secrecy of the evaluation point $z$ is necessary.
Temporal Rule Necessity: Without the rule preventing the citation of future codes, an explicit three-operation forgery exists that achieves exact balance and is accepted with probability 1.

3. Maintainer Implementation

The paper provides a concrete implementation using a leaf-oriented (2, 4)-tree:

Complexity: Operations run in $O(\log n)$ worst-case time.
Overhead: The structure requires only one extra word per element (to store the gap code).
Audited Rebalancing: The paper introduces an attestation envelope proving that the number of structural events (splits, fusions, shares) over $m$ updates is at most $2m$ . This bound is certified by the auditor counting one-word attestations appended by the maintainer, turning amortized analysis into a publicly verifiable claim.

4. Checkpoints and Epochs

The protocol supports arbitrary checkpoints. Audits can be performed at any time, and accepted epochs can be chained with additive error bounds. This allows the latency of detection to be tuned (e.g., auditing after every operation for high security, or less frequently for efficiency).

Significance and Scope

The paper claims to provide a closed account of constant-memory auditing for dynamic ordered sets. Its significance lies in:

Shifting the Paradigm: Moving from "testing in isolation" to "certification traveling with execution."
Information-Theoretic Guarantees: Achieving verification without cryptographic assumptions (like Merkle trees or digital signatures), relying instead on algebraic properties of polynomials and the combinatorial structure of ordered sets.
Tight Lower Bounds: Demonstrating that the proposed constant-memory solution is near-optimal by proving that any deterministic solution requires linear space and that randomness must be hidden.
Explicit Constants: All parameters (prime sizes, word counts, error bounds) are explicit and calibrated for practical use (e.g., fitting within 64-bit words).

The scope is strictly limited to the seven-operation interface (insert, delete, member, pred, succ, min, max). The paper explicitly notes that the gap calculus certifies arrangement (adjacency, bracketing, extremality) but does not extend to aggregate properties like rank, which are not local to a single gap. The detection is retrospective; the paper acknowledges that online detection (rejecting an answer immediately) in this information-theoretic setting is a recognized frontier linked to the existence of one-way functions, and thus the proposed solution is optimal within its defined retrospective model.