Building Tachyon's Proof Tree with Shared Evidence

A shielded spend must prove that its note was created and has not already been spent, without revealing the note itself.

In Ironwood, a spend proves membership in the note-commitment tree and publishes the note's permanent nullifier. The commitment tree can be updated with compact working state, but the nullifier set keeps growing. Validators must retain all nullifiers ever published on-chain in all history, so they can recognize and reject a second spend of the same note.

Tachyon shrinks the nullifier set validators must maintain, by introducing epochs. Note nullifiers change per epoch, and validators are only responsible for small rolling window of recent history.

Beyond the rolling window, wallets simply prove none of their note's earlier nullifiers appeared on-chain in past epochs. To make this possible, Tachyon separates the work of proving the long arc of history (pool state) from the work of proving the small details of history (note state). Shared historic evidence can be built once per epoch, and reused by many wallets to prove the fate of an individual note in that epoch.

Epoch Nullifiers and Delegated Checks

Each note fixes a secret master key , derived from the wallet's nullifier key and the note's randomness. The wallet derives a pseudorandom nullifier for each epoch :

An oblivious syncing service (OSS) receives selected historical epoch/nullifier pairs and proves their absence from the corresponding epochs. These values are visible to the service, but are essentially arbitrary. The service never learns anything about the note.

The privacy boundary depends on sharing only historical values that the eventual spend will not publish. Revealing these historic nullifiers does not reveal the master key or make other epochs' nullifiers predictable. A wallet may also perform the checks itself.

This delegation model was introduced by oblivious synchronization and developed in A Note on Notes.

Accumulators and Anchors

Let be the Pasta field used by the accumulator. Tachyon represents a multiset of field elements by its root polynomial:

Against an authenticated commitment , a zero opening proves membership and a nonzero opening proves non-membership:

Multiplication combines multisets, preserving their multiplicities:

Exact division removes a contained multiset with its multiplicities. Proof steps can use these relations to combine or split authenticated collections without checking every element inside the circuit.

Because the accumulator supports both kinds of opening, note commitments and nullifiers can share one authenticated structure. Tachyon publishes both as tachygrams, 32-byte field elements without explicit commitment/nullifier role labels. A wallet proves that its note was created by opening the accumulator at the note commitment, and checks for earlier spends by opening it at the corresponding nullifiers.

A stamp commits to the tachygrams of one or more transactions and proves that they match the covered actions. Absorbing each published stamp commitment into a hash chain advances the anchor:

Epoch boundaries use a separate hash domain, including when an epoch contains no stamps. The anchor commits to the sequence of stamp commitments and epoch transitions. Proofs of these transitions ultimately connect to an anchor accepted by consensus, which establishes that the covered history occurred.

The proof tree connects claims using proof-carrying data (PCD): each proof step consumes earlier certified claims, checks a transition, and produces the next certified claim.

A spendable is wallet-held proof state certifying a note's creation and the absence of its required nullifiers through a particular anchor. It records the note commitment, its current epoch and nullifier, and the anchor. The wallet can resume from this authenticated position when it next synchronizes, proving absence over the intervening history before advancing the state. The intermediate proof stays in the wallet; it does not publicly associate the note commitment with a nullifier.

An aggregator can separately reuse proofs of anchor ancestry to align independently produced stamps at a common anchor before combining them. Those anchor segments establish alignment; the epoch evidence below supports queries against the tachygrams themselves.

Reusing Epoch Evidence

Shared evidence is constructed from published history without a note or candidate nullifier as input. An evidence builder authenticates the data against which queries will be made. An OSS uses that evidence to prove absence at a candidate value, and the wallet binds the returned result to its private nullifier derivation.

The builder's work can be reused across many queries, although each opening still depends on the value being tested. One operator can both build evidence and run a syncing service, and different builders can produce valid evidence for the same epoch.

The simplest service checks an epoch's nullifier against every stamp, then combines adjacent results into one proof. Each query repeats work over the same public history at a different evaluation point.

A summary reduces that work by combining a bounded run of consecutive stamps from one epoch into a single accumulator and recording its anchor span. Its degree is the number of tachygrams it contains. A small epoch can fit in one summary; larger epochs require more.

Combining the entire epoch into one polynomial would reduce the query to one opening, but an epoch with tachygrams gives a degree- polynomial. The linear-time opening method still does work proportional to the epoch's size. Dividing the data into smaller polynomials makes an individual opening cheaper, provided we can prove that the selected polynomial contains every occurrence of the value being tested.

Routing into Bounded Buckets

Tachyon uses quadratic-residue (QR) routing to construct those polynomials. Fix a public quadratic non-residue in . For a nonzero value , either or has a square-root witness.

A routing offset assigns to the residue side when is a square or zero, and to the non-residue side otherwise. The builder privately samples a base and uses consecutive offsets:

A value's QR profile is the sequence of its classification bits under that base. A bucket is certified for a prefix of this profile.

The builder keeps private while routing stamps or summaries during the active epoch, so publishers do not have its filter sequence to target a bucket. After the epoch closes, it reveals the base and publishes the sealed buckets. Different builders can use different bases.

Constructing and Certifying Buckets

For a bucket with certified prefix and authenticated history span , every tachygram in whose profile begins with must occur in the bucket. A nonzero opening at a matching value then proves its absence throughout the span, without opening the other buckets.

At each descent, the circuit checks that the selected child and its sibling multiply back to the parent. This prevents adding invented roots. It also proves that the sibling contains only the opposite class, preventing any matching occurrence from being routed away from the selected child.

Writing for the sibling polynomial, that class certificate uses the identity

Here is for a residue sibling and for a non-residue sibling, interpolates square-root witnesses, and is the quotient. At each root of , the identity forces the corresponding square-root relation. The split also opens its non-residue side nonzero at , since the square-root relation alone admits zero.

The selected child may retain off-profile values. These extras cannot hide a matching occurrence; they can only make a non-membership opening stricter.

The builder seeds the construction from stamps or summaries, then splits and descends as capacity requires. It merges adjacent spans only when their epoch, routing base and prefix agree and the product fits. Sealing connects the span's start to the epoch's opening boundary.

Let be the supported bucket degree. With approximately balanced routing, a depth near

brings the average population near . This is an expectation about balance, not a maximum-occupancy guarantee. Accepted buckets must satisfy the configured degree bound. A poor routing choice can make suitable buckets expensive or unavailable; it cannot justify an invalid absence proof. The implementation's 32 positions bound the available routing depth, not the cryptographic security level.

Querying the Buckets

A bucket's completeness initially applies to its own span. For whole-epoch absence, the span must start at the opening boundary and connect through the closing epoch transition to consensus-accepted history. A transition computed from an intermediate anchor does not establish epoch closure. This connection comes from the composed proof lineage and the eventual consensus check.

A bucket tree packages certified buckets in a Merkle tree whose root is covered by one proof. Its leaves bind each bucket's depth, profile and contents commitment; the tree carries their common epoch, span and routing base. The server still needs the bucket polynomials and authentication paths. Omitting a profile can prevent an answer, but cannot make an incorrect answer valid.

The OSS selects a bucket whose certified profile prefix matches the candidate and authenticates it against the tree root. The current query circuit checks the candidate's classifications at all 32 positions, compares the prefix selected by the bucket's depth, and opens the bucket polynomial at the candidate. Given the required epoch coverage, a nonzero opening proves absence for that epoch. The query uses one bounded polynomial opening and fixed-width routing checks, in addition to authenticating the bucket.

Creation membership needs less: a zero opening at the note commitment proves it is a root of an authenticated bucket. No profile check is needed, because every bucket root is a genuine tachygram from its span. Non-membership needs the additional completeness guarantee that the matching profile supplies.

The proof-tree implementation notes describe the individual steps.

Binding the Result to the Note

The service proves absence for the values it receives. The wallet must establish that those values are its note's nullifiers at the corresponding epochs.

Fix a public non-cube and encode each epoch/value pair as

Distinct permitted epoch/value pairs give distinct irreducible factors, even up to multiplication by a nonzero constant. The bounded domain of epoch indices is necessary for this claim.¹

The wallet proves the private derivation of its nullifiers over a range and commits to their product of factors. The service commits to the values carried by its certified segment over a range , including its boundary epochs:

The wallet provides a quotient for the polynomial identity

All three commitments, including the quotient's, are fixed before deriving the challenge . The proof checks authenticated evaluations:

The degree bounds and commitment system make this a sound randomized test of the identity. Unique factorization then establishes that each pair in the service's product occurs in the wallet's genuine derivation.

The factorization binds each value to its epoch, but multiplication does not encode the order of the checks. The segment proofs establish coverage and continuity separately. To join two spans, the proof checks that their meeting anchor, epoch and nullifier agree, then removes the duplicated boundary-epoch factor from the combined product.

Advancing the Spendable

The wallet consumes the bound segment and checks that its note commitment, starting epoch, nullifier and anchor agree with the spendable. It then advances to the segment's ending epoch, nullifier and anchor while keeping the note commitment fixed.

To initialize a spendable from closed-epoch evidence, the wallet combines creation membership with a bound absence segment covering the same span. Direct stamp or summary segments handle an active epoch, or any span without usable closed-epoch evidence. The wallet can continue from this authenticated state when it next synchronizes.

Spending adds the usual value and spending-authority checks and publishes the nullifiers for the spending anchor's epoch and the next epoch. The second value accommodates an epoch transition before inclusion. Validators check the proof, confirm the anchor belongs to accepted history, and check the published values against their retained recent window. These live checks cover the interval between the wallet's authenticated anchor and transaction inclusion.