Oblivious Sync

Chapter 19 showed that a spend must prove one nullifier absent from each closed epoch since the note's creation, and chapter 20 built the chain of anchors that those proofs refer to. This chapter opens the black box they left behind. It covers how an untrusted service can prove absence over a whole epoch without knowing which note the values belong to, how the wallet later ties that work to its note, and what the service learns along the way.

Two problems run through the chapter. Sections 2 to 7 show how the wallet can tie values that a stranger tested to its own nullifiers at the right epochs. Sections 8 to 13 deal with size, since an epoch's polynomial is far too large to open directly. Section 14 then takes stock of what the service sees.

1. The work a spend needs

Take the running note of chapter 19, created in epoch 3 and spent with target epoch 7. Here is what its spend requires, with the same stand-in nullifiers:

Each row that says "tested" needs someone to read a whole epoch's tachygrams, which is exactly the work that wallets were supposed to stop doing. Handing that work to a service is safe only if the values it receives are useless later. Evolving nullifiers provide this, because the pair published at the spend is unrelated to the values tested for earlier epochs, assuming Poseidon behaves as a pseudorandom function. Chapter 19 explained why the wallet sends explicit values and no key.

We call this party the sync service, or the service. The book also says "delegate" and "oblivious syncing service (OSS)" for the same role.

2. Two branches that share no secrets

The service knows nothing about the note, so it cannot prove anything about the note. All it can prove is a statement about arbitrary field elements: "these values, at these epochs, do not appear in the pool." The code's name for such a proof is ArbitraryUnspent, and its doc comment says that the tested values remain arbitrary until the wallet attributes them to a derivation.

The wallet holds the other half. As chapter 19 showed, it proves that a range of nullifiers really derives from the master key of a note with commitment $\mathsf{cm}$, which gives a NoteNullifiers proof. Neither proof says anything about the other, so a final wallet step has to connect them. The proof tree page calls that step UnspentBind, and it is the only place where the two meet:

Both branches build their commitments step by step, because neither fits in one proof step. So the binding has to compare two values that were accumulated separately, by different parties, over different ranges. The wallet's range also needs to be at least as wide as the service's, since it covers epochs the service never saw. What we need is a commitment that grows one epoch at a time and that supports a proof that one committed collection sits inside another. The deep dive calls this a "ranged nullifier commitment," and it rules out the vector commitment schemes it surveyed because they rely on RSA or bilinear groups.

3. Testing containment with polynomials

Chapter 20 already has a tool for containment, since a polynomial divides another exactly when its roots form a sub-multiset, and a late random challenge checks the division. So the first thing to try is to give the service's values as roots. The service commits to $\Delta (X)={\prod }_i(X-{\delta }_i)$, the wallet commits to $N(X)={\prod }_j(X-{\mathsf{nf}}_j)$, and the wallet shows $N=C\cdot \Delta$ for a witnessed quotient $C$.

Our small examples use ${\mathbb{F}}_{43}$, so we reduce the nullifiers above modulo 43. That gives ${\mathsf{nf}}_3=29$, ${\mathsf{nf}}_4=9$, ${\mathsf{nf}}_5=12$, and ${\mathsf{nf}}_6=41$.

This proves that the tested values are the note's, but it says nothing about which value was tested against which epoch. A later proof looks for each nullifier only in the epoch with the same number, as chapter 19 stressed, so that loss is fatal.

Suppose an earlier spend of this note had target 3 and was accepted during epoch 4, so epoch 4 contains ${\mathsf{nf}}_3=29$ and ${\mathsf{nf}}_4=9$. Say epoch 4 publishes {29, 9, 17} and epoch 5 publishes {33, 6, 38}. A second spend must fail, and the honest test does fail, since $f_4(9)=0$. The cheater swaps the two values and tests 12 against epoch 4 and 9 against epoch 5. Both tests pass, with $f_4(12)=40$ and $f_5(9)=24$. The tested multiset is still {9, 12}, and its polynomial $(X-9)(X-12)=X^2+22X+22$ did not change, so it divides the wallet's polynomial just as the honest one does.

So each entry of the collection must carry its epoch as well as its value.

4. Putting the epoch into the factor

We want a polynomial factor that encodes the pair $(i,m)$, with the epoch $i$ and the value $m$, such that a product of factors determines which pairs went in. Polynomials over a field factor uniquely into irreducible pieces, up to multiplying the pieces by constants, so two goals follow. Each pair's factor should be irreducible, and the leftover constants should give a cheater no freedom.

The natural first attempt is the linear factor $(i+1)X+m$. The shift by one keeps the coefficient of $X$ nonzero at epoch 0. A linear polynomial is always irreducible, so the first goal holds, and the second one fails.

For epochs 4 and 5 the linear factors are $5X+9$ and $6X+12$, and their product is $30X^2+28X+22$. Move the unit $r=6/5=27$ from one factor to the other:

$$(5X+9)(6X+12)=(27(5X+9))(27^{-1}(6X+12))=(6X+28)(5X+10).$$

The right side reads as value 10 at epoch 4 and value 28 at epoch 5. Neither is the genuine nullifier, and the product is the same polynomial, so it passes every challenge.

To remove this freedom, Tachyon cubes the linear term and subtracts a constant:

$$F_{i,m}(X)=(m+(i+1)X{)}^3-c,a=i+1.$$

The constant $c$ does two jobs, and we can derive both.

The constant removes the scaling freedom. Suppose a second pair gives the same factor up to a constant $u$, so $(m^{\prime }+a^{\prime }X{)}^3-c=u((m+aX{)}^3-c)$. Write $Y=m+aX$, and express the other linear term through it as $m^{\prime }+a^{\prime }X=rY+s$, with $r=a^{\prime }/a$ and $s=m^{\prime }-rm$. Expanding the left side gives

$$r^3{Y}^3+3r^{2}s{Y}^2+3r{s}^{2}Y+s^3-c=u{Y}^3-uc.$$

Compare coefficients one power of $Y$ at a time. The $Y^2$ term gives $3r^{2}s=0$, and $r\ne 0$, so $s=0$. The constant term then reads $-c=-uc$, which forces $u=1$ whenever $c\ne 0$. The $Y^3$ term becomes $r^3=1$. So the two factors can agree only when $u=1$ and $(a^{\prime },m^{\prime })=(ra,rm)$ for a cube root of unity $r$. Without the $-c$, the constant term would say nothing, and any $u$ would do, which is the same trick as in the linear case. Section 5 deals with the cube roots of unity that remain.

A non-cube makes each factor irreducible. A cubic over a field can only split by having a root, and $F_{i,m}$ has a root $x$ exactly when $(m+ax{)}^3=c$, which requires $c$ to be a cube. So if $c$ is not a cube, $F_{i,m}$ has no root in the field and is irreducible. Non-cubes exist only when 3 divides $p-1$, because otherwise cubing permutes the nonzero elements. Pasta satisfies this, and the code fixes $c=2$, which it calls the smallest cubic non-residue.

In ${\mathbb{F}}_{43}$ the nonzero cubes are 1, 2, 4, 8, 11, 16, 21, 22, 27, 32, 35, 39, 41, 42, which is 14 of the 42 nonzero elements. The value 2 is one of them, since $20^3=2$ here, so the toy field cannot use the code's constant. Its smallest non-cube is $c=3$, and we use that. The real field does have $2$ as a non-cube, which we checked by computing $2^{(p-1)/3}\ne 1$ for the Pallas base field.

With $i=4$, $m=9$, and $c=3$ we have $a=i+1=5$, and expanding the cube gives

$$\begin{array}{rl}{F}_{4,9}(X)& =(9+5X{)}^3-3\\ & =5^3{X}^3+3\cdot 5^2\cdot 9X^2+3\cdot 5\cdot 9^{2}X+9^3-3\\ & =39X^3+30X^2+11X+38.\end{array}$$

Those four coefficients appear in the same order in the code. With irreducible factors and no spare constants, a product determines its multiset of pairs, which the code calls an indexed multiset.

We can test this on the toy field. Epochs 3 to 6 and all 43 values give 172 pairs, and they produce 172 different factors. Multiplying any two of them, repeats allowed, gives 14,878 products, and no two of those products are equal. So rescaling cannot produce a second set of pairs here.

The non-cube requirement has a concrete purpose, because a factor that splits can divide a product without being one of its members.

Here is the failure on the toy field, for the four pairs above and every candidate $(i,m)$ with $i$ from 0 to 29. With $c=2$, which is a cube, $N(X)$ has the 11 distinct roots 5, 11, 12, 18, 28, 30, 32, 33, 39, 40, 42, and 11 false pairs have all of their three roots among them. The pair $(0,35)$ is one, whose roots are 28, 40, 42, and its factor divides $N$ although it is no member of $N$. With $c=3$, $N(X)$ has no roots in the field at all, and no false pair divides it except for the scaled copies of Section 5, which are the same polynomial.

The sources do not discuss why they chose a cube over a square of the linear term, so we leave that question open.

5. When two pairs share a factor

The derivation leaves one escape. If $\omega$ is a cube root of unity other than 1, then $(i,m)$ and the pair with $a^{\prime }=\omega a$ and $m^{\prime }=\omega m$ have the same factor, because $(\omega Y{)}^3=Y^3$.

In ${\mathbb{F}}_{43}$ the cube roots of unity are 1, 6, and 36. Since $6\cdot 1=6$, the epoch numbers $a=1$ and $a=6$ are one scaling apart, and the factors for $(0,9)$ and $(5,11)$ are the same polynomial, namely $X^3+27X^2+28X+38$.

A collision like this would matter if a valid epoch number $a^{\prime }$ happened to equal $\omega a$. The code states a bound that prevents it, namely keeping $a$ below $\lfloor \sqrt{p/3}\rfloor$. The reason takes three lines. Suppose $a^{\prime }=\omega a$ with both numbers between 1 and that bound. A nontrivial $\omega$ satisfies ${\omega }^2+\omega +1=0$. Multiplying by $a^2$ gives

$$a^{\prime 2}+a^{\prime }a+a^2=a^2({\omega }^2+\omega +1)\equiv 0(\mathrm{mod}p).$$

As an ordinary integer, the left side is positive, and it is less than $3\cdot p/3=p$ because each of its three terms is below $p/3$. A positive integer below $p$ cannot be a multiple of $p$, so no such pair exists.

On the toy field the bound is $\lfloor \sqrt{43/3}\rfloor =3$, which is small, and the collision above has $1+6+6^2=43$, exactly the field size. For the Pallas base field the bound is about $2^{126}$, while the code has only $2^{20}$ epochs. Our window of epochs 3 to 6 lies above the toy bound, so we checked it directly, and Section 4 found no collision among those epochs.

The deep dive makes the same point more loosely, and adds that a real circuit does not range-check $i$ directly. It relies on the increments as ranges are built and on an out-of-range epoch leading to invalid anchors.

6. A full run on the toy curve

We can now run the whole binding. A wallet derives the range of epochs 3 to 6. Say it delegates epochs 4 and 5 to a service, keeping epoch 3 because that is the creation epoch, and epoch 6 because it has not reached the service yet. Real windows are larger, and Section 7 uses the true size. Over a delegated range, the delegation section defines

$$\Delta (X)=\prod _{i\in \text{delegated}}{F}_{i,{\delta }_i}(X),N(X)=\prod _{j\in \text{derived}}{F}_{j,{\mathsf{nf}}_j}(X),C(X)=\prod _{j\notin \text{delegated}}{F}_{j,{\mathsf{nf}}_j}(X),$$

and the claim is $N(X)=C(X)\cdot \Delta (X)$. The honest service tests the values it was given, so ${\delta }_i={\mathsf{nf}}_i$:

A header has room only for short values, so each party's header holds a commitment. UnspentBind first checks that its witnessed $\Delta$ and $N$ match the commitments on the two input headers.

Each polynomial commits on the toy curve as in chapter 6, with the extra generators of chapter 20 and more of the same kind, since $N$ needs 13: $\mathsf{Com}(\Delta )=(4,25)$, $\mathsf{Com}(C)=(28,10)$, and $\mathsf{Com}(N)=(22,24)$. A stand-in hash of those three points gives the challenge $z=6$.

The step then checks the product at the challenge. The shared helper enforce_poly_product absorbs all three commitments into the challenge, compares the evaluations, and records one opening claim per polynomial, which it leaves for the proof system to verify.

At $z=6$ the service's side evaluates factor by factor as $\Delta (6)=F_{4,9}(6)\cdot F_{5,12}(6)=19\cdot 36=39$. The wallet also has $C(6)=18$ and $N(6)=14$, and the identity holds, since $39\cdot 18=14$ in ${\mathbb{F}}_{43}$.

The output is a NoteUnspent header. It keeps the segment's anchors and epochs, and it carries the wallet's $\mathsf{cm}$, so the anonymous claim now belongs to one note.

A dishonest service gains nothing, because its proof is about whatever it tested, and the wallet's check leaves a diverging proof useless. It can refuse to serve, and it cannot fool the wallet. A cheating wallet is the more serious case, and the argument there runs through the order of events, as in chapter 3. The commitments are fixed before $z$ exists, so a false claim is a fixed nonzero polynomial $N-{\Delta }^{\prime }C$, and the challenge has to land on one of its roots. Here is every kind of attempt, with the honest $C$ committed:

The difference $N-{\Delta }^{\prime }C$ has degree at most 12, so no attempt can pass more than 12 challenges, and the worst one here passes 3. A wrong value passes so few because $N-{\Delta }^{\prime }C$ factors as $C$ and $F_{4,9}$, which have no roots in the field, times a difference of two cubes, which has degree 2. The proportion looks large only because the field has 43 elements.

The third row of that table needs one more fact. The wallet's $N$ has each epoch once, because NullifierFuse requires contiguous ranges, which keeps it squarefree. A repeated factor in $\Delta$ therefore cannot divide it.

7. The real window size

The code's derivation unit is wider than our toy range. NF_DERIVATION_WIDTH is 16, so NullifierDerive produces a group-aligned window of 16 epochs from 4 sponges, and NullifierFuse joins adjacent windows by multiplying their polynomials. Our note needs epoch 3 covered, so its first window starts at epoch 0. The factors for epochs 0 to 2, and for epochs the window runs ahead of the evidence, go into the complement, which stays with the wallet.

The stand-in range of chapter 19 is the prime 65,537, and it cannot host this encoding. Since $65,536$ is not divisible by 3, cubing permutes that field and every element is a cube. So this section works modulo the next prime with the right shape, 65,539, which is 1 modulo 3 and whose smallest non-cube is $c=2$. The nullifier values carry over unchanged.

The identity holds: $27584\cdot 52043\equiv 53395(\mathrm{mod}65,539)$. If the service instead tests 63094 at epoch 5, one more than the genuine 63093, then trying all 65,539 challenges finds 2 that pass, against the degree bound of 48. The window is well inside the injectivity bound here, which is $\lfloor \sqrt{65,539/3}\rfloor =147$.

Notice what UnspentBind does not compare. The proof tree page says it compares no bounds between the segment and the derivation. It does not need to, because each factor carries its own epoch. An epoch outside the derivation has no factor to divide out, so coverage follows from the identity.

8. Why one opening per epoch needs buckets

With the binding in place, we turn to what the service proves. A nullifier is absent from an epoch exactly when the epoch polynomial $e(X)$ is nonzero there. Anyone can show that $e$ is the product of the stamp polynomials absorbed into the anchor chain, and the work is paid once and reused for every query. The obstacle is the degree of $e$, because opening a commitment with Ragu's linear-time verifier costs time in proportion to it.

Take 100 two-input, two-output transactions per second as a hypothetical load, with 8 tachygrams each. An epoch of the code's 4,096 blocks lasts 307,200 seconds at 75 seconds per block, so it holds 245,760,000 tachygrams, and $e(X)$ has that degree.

The deep dive estimates more than 16 minutes of verification at its own higher figure, and so it drops this approach.

The deep dive's figure of more than 480,000,000 tachygrams uses a two-week epoch, and it matches 483,840,000, which is 4 tachygrams per transaction. Two per action would give 967,680,000. Its later scale estimate does use 8 per transaction. Neither figure uses the code's epoch length.

The fix is to split the epoch into buckets small enough to open, so that a query touches one. This only works if a value can find its own bucket without any list of the epoch's contents, and if nobody can leave a tachygram out of the bucket where it belongs. So the partition has to be a public rule computed from the value alone, and it has to be cheap to prove that a whole bucket obeys the rule. A rule based on hashing each member would cost one hash per member inside a proof, by our count, since the deep dive says only that its own choice is cheap to prove. Tachyon instead classifies values by quadratic residuosity, because a polynomial identity can attest many members at once, as Section 10 shows.

In ${\mathbb{F}}_{43}$ the nonzero squares are 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 41, which is half of the 42 nonzero elements. The smallest non-residue is $n=2$, and multiplying by it swaps the two halves. For example, $9$ is a square, and $2\cdot 9=18$ is not. The value $3$ is not a square, and $2\cdot 3=6$ is. So every nonzero $s$ has a root $y$ with either $y^2=s$ or $y^2=2s$, and never both. The code uses $n=5$, which is the smallest non-residue of the real field.

We write $n$ for this non-residue, since the sources use $c$ here as well as for the cube constant, which would be confusing.

9. Classifying a value

One split of the field gives two classes, and we need many. A discriminant $R$ is an offset that gives a different split, because $x$ is classified by whether $x+R$ is a square. The rule sets the bit $b=1$ when $x+R$ is a square or zero, which we call the residue side, and $b=0$ otherwise. A run of discriminants then gives each value a string of bits, its QR profile. Tachyon uses consecutive offsets, $R_j=R_0+j$, from a first discriminant $R_0$ that a builder picks.

Here is chapter 20's epoch 0, with its stamps A, B, and C. The small-field search for a readable example chose the $R_0$ below.

The "Root" column gives $y$ with $y^2=\kappa (x+R_0)$, where $\kappa =1$ on the residue side and $\kappa =n$ on the other. It is what a prover supplies to show a value's side, and the next section needs it.

One value needs special handling, which is the one where the shifted value is zero.

The exceptional value at our discriminant is $x=-R_0=17$. Its shifted value is 0, so $y=0$ satisfies $y^2=1\cdot 0$ and also $y^2=2\cdot 0$, which means a root alone would let it sit on either side.

The rule files this value on the residue side, so a step that claims the non-residue side must also check that the shifted value is nonzero. Without that check, a cheater could move $-R$ to whichever side suited it.

10. Proving a split

A builder holds a set of tachygrams with a committed polynomial, and it wants to split them into a non-residue side and a residue side. The product $q_0(X)q_1(X)=f(X)$ shows that the two sides partition the set, and that check works as in Section 6. What remains is to show that each member sits on the side it claims, without one check per member.

Suppose every root $x_i$ of a polynomial $s(X)$ has a root $y_i$ with $y_i^2=\kappa (x_i+R)$. Interpolate a polynomial $u(X)$ through the points $(x_i,y_i)$. Then $u(X{)}^2-\kappa (X+R)$ vanishes at every $x_i$, because at $x_i$ it equals $y_i^2-\kappa (x_i+R)=0$. Consensus forbids repeats within two epochs, so $s$ is squarefree. A polynomial that vanishes at every root of a squarefree $s$ is divisible by $s$, so a quotient $h$ exists with

$$u(X{)}^2-\kappa (X+R)=s(X)h(X).$$

The reverse also holds, and that is what gives the identity force. If this identity holds for some $u$ and $h$, then evaluating at any root $x$ of $s$ gives $u(x{)}^2=\kappa (x+R)$, so $u(x)$ is a root of the kind that only $x$'s true side allows. One identity, checked at one random point, therefore covers all the members at once.

The code splits this into two steps. QrIntakeSplit checks the product, and it opens the non-residue side at $-R$ to show that it is nonzero there, which handles the exceptional value. QrSideDescend then extracts one side as a child, and it runs the identity above on the other side, the sibling. The reasoning is that the sibling's attestation is what protects the child. If every root of the sibling truly belongs to the sibling's class, then every member of the child's class must be in the child.

Take stamp A as an intake, with members 22, 24, 40. At $R_0=26$ its non-residue side is $s(X)=X^2+40X+12$, with roots 22, 24, and its residue side is $X+3$. To descend into the residue side, the prover attests the sibling $s$ at $\kappa =n=2$. The roots from the table give $u(22)=15$, $u(24)=10$, so $u(X)=19X+27$. Then

$$\begin{array}{rl}u(X{)}^2-2(X+26)& =17X^2+35X+32\\ & =(X^2+40X+12)\cdot (17),\end{array}$$

so $h(X)=17$, a constant here because $s$ has degree 2. The commitments are $\mathsf{Com}(s)=(25,2)$, $\mathsf{Com}(u)=(26,23)$, and $\mathsf{Com}(h)=(20,6)$. A stand-in hash of those and $R_0$ gives $z=10$, where both sides equal 18.

Now we can see why cheating fails. An absence proof goes wrong only if a published value is missing from the bucket that its own profile selects.

Suppose a cheater wants 40 missing from the residue child, because later it will claim that 40 is absent. It moves 40 into the sibling, so the sibling polynomial gains the root 40. The identity then needs $u(40{)}^2=2(40+26)=3$, and 3 is not a square, so no $u$ exists. Trying all 43 values for $u(40)$ and taking the quotient by long division, 0 of them divide exactly, and the best attempt passes 2 of the 43 challenges.

The crate's tests reject a child short of a member in this way. The attack the other way is harmless. If the cheater left a stray non-residue member in the residue child, then the sibling's identity would still hold, and the child would have one root too many. A stray can only make a later nonzero opening harder to pass.

The challenge in QrSideDescend also absorbs $R$, through the point $[R]G_0$. $R$ is chosen by the prover, and it is not one of the committed polynomials, so without this a prover could solve the identity for $R$ after seeing $z$. Chapter 3 showed the same failure in general.

11. Routing an epoch into buckets

Splitting one big polynomial in one step is impossible, since no step can hold it, so the partition has to grow out of small pieces. Each stamp or short run of stamps starts as a root intake, a bounded set of tachygrams at depth zero with a range of anchors. A round of routing splits each intake and merges neighbours, and two intakes may merge only if they have the same profile, their anchor ranges meet, and the union fits the capacity. The merge is a polynomial product, as in chapter 20.

Here is the network for our epoch.

With a capacity of 4 per intake the network ends with 3 buckets: 1 holding 40, 23, 41, 21, 00 holding 24, 19, 01 holding 22, 20, 13. Multiplying the three bucket polynomials gives back the epoch polynomial $e_0(X)$ of chapter 20, and no bucket has degree above 4, where $e_0$ has degree 9.

The buckets have different depths. Profile 1 was complete after one round, because one intake covering all three stamps held all of it. Profile 0 still had two intakes after round 1, so only that branch went through another round. The deep dive calls this a jagged frontier, and the crate has a test with ragged depths. The final profiles form a prefix partition, so every value matches exactly one of them.

Each final bucket also has to cover the whole epoch, or a tachygram of that profile could be missing. QrBucketSeal certifies this by computing the boundary digest into the next epoch, which chapter 20 explained. A bucket sealed before the final anchor lands on a value outside the accepted chain. The step checks that the intake begins on a boundary digest, from an anchor_final_prev that it takes as a free witness, and consensus closes that gap later, as chapter 20 explained.

For our epoch, the step takes $anchor\_final\_prev=0$ for epoch zero and checks the start against $H_{\mathsf{ep}}(0,0)=29$. The last intake ended on the final anchor 26, so the step computes $H_{\mathsf{ep}}(26,1)=40$. The bucket covers the half-open range from 29 to 40, using the stand-in values of chapter 20.

An epoch with no stamps seals an empty bucket whose polynomial is 1, so it costs no more than any other.

The depth stays modest at real scale.

The deep dive sizes this for 50,000 such transactions per second over two weeks, which is 483,840,000,000 tachygrams. At 8,000 tachygrams per bucket that is 60,480,000 buckets, and ${\log }_2$ of that is 25.8, so the honest depth stays below 26, inside the 32 positions the header allows.

The 8,000 comes from the deep dive, and we found no such constant in the crate, where capacity is a parameter of the test fixtures.

The choice of $R_0$ does not affect soundness, because a proof certifies the buckets under whichever $R_0$ the builder used. It affects only balance, and the deep dive worries that a user who knew it could grind tachygrams into one bucket.

Across all 43 choices of $R_0$, the fullest of the four depth-2 classes holds on average 3.7 of our 9 tachygrams. With $R_0=26$ known in advance, a user could publish 9 of the 11 field elements with profile 11 and fill that class alone.

So each builder samples $R_0$ privately and keeps it unpublished until the epoch closes. A biased network hurts only its builder, and a wallet may use any valid network.

12. Testing a value against its bucket

The last step of the service's work is QrUnspentInit, which takes a sealed bucket and a value and proves the value absent. First it opens the bucket's polynomial at the value and requires a nonzero result.

Test the value 4, which chapter 20 found absent from this epoch. Its shifted values are $4+26=30$ and $4+27=31$, and these give it the sides 0, 1. So its bucket is 01, whose polynomial is $q(X)=X^3+31X^2+40X+42$, and $q(4)=31$ is nonzero. One opening of a polynomial of degree 3 has replaced an opening of degree 9.

It must also show that this bucket is the right one, because any other bucket would open nonzero too.

Now test 41, which stamp B published. Its sides lead to bucket 1, where $q(41)=0$, so the nonzero check fails and no proof exists. This is why the step must force the profile to match. Opened against the other buckets, 41 gives 30 in 00 and 35 in 01, both nonzero, so without the profile check a cheater could prove absence of a value that was published.

To force the match, the step witnesses the value's side and root at every one of 32 positions. With $s_j=x+R_0+j$, it checks

$$r_j^2=(n-(n-1)b_j)s_j,b_j=0⟹s_j\ne 0.$$

The factor in the first equation equals $1$ when $b_j=1$ and $n$ when $b_j=0$, so this is the root check of Section 9. Since $n$ is a non-residue, only the value's true side has a root. The step runs all 32 positions because a circuit's shape cannot depend on secret values, and buckets differ in depth.

The bucket's depth $d$ selects how many sides to compare, through a mask $m_j$ of 32 bits. The proof tree page gives the checks:

$$\sum _j{m}_j=d,2\sum _{j}j{m}_j=d(d-1),a_{j+1}=a_j+m_j(a_j+b_j),a_{32}=\mathsf{bits}.$$

The first two force the mask to be the first $d$ positions, since among bit vectors with $d$ ones only the leading positions reach the smallest possible index sum, which is $0+1+\cdots +(d-1)$. Where a mask bit is set, the third line becomes $a_{j+1}=2a_j+b_j$, which appends one bit, so $a$ builds the integer $\mathsf{bits}$ out of the value's own sides.

For depth 2 there are 496 ways to set two mask bits among 32 positions. The index sum must equal $d(d-1)/2=1$, and only the prefix $\{0,1\}$ does. For the value 4, the first four sides are 0, 1, 0, 0, and the fold under the mask runs through $a=0,1,1,1$. It ends at 1, the integer that encodes 01. The sides past the depth are computed and ignored.

The output is a one-epoch segment. It tests a value against a bucket, so its elapsed polynomial holds the single factor $F_{\text{epoch},x}$, which is what Section 6 multiplied up. The step must also tie that factor to the value $x$ it opened, and the check has a trap.

Take the one-factor sequence for value 12 at epoch 5, and let the challenge be $z=6$. If $z$ did not depend on the value, a cheater could set $m^{\prime }=\omega (m+6z)-6z=37$, using $\omega =6$. The inner terms differ by the factor $\omega$, so their cubes agree, and $F_{5,37}(6)=F_{5,12}(6)=36$. A sequence naming 12 would then pass for a test of 37, so the proof could test one value and record another.

So the challenge absorbs the point $[x]G_0$ as well as the sequence commitment, and $z$ then depends on the value. The crate has a test for exactly this twin.

13. Composing segments and keeping evidence

A segment for one epoch has to grow to cover many. UnspentLift appends the next epoch's bucket in one step, and UnspentFuse joins two segments on a shared boundary. Both check that the anchors and epochs meet, and that the new elapsed is the product of the old polynomials. Each producer adds exactly one factor per epoch and labels it with its own epoch, so a segment over $[e_1,e_2)$ holds one factor for each epoch in that range. This is the property that lets UnspentBind skip comparing bounds. Here is a segment over chapter 20's epochs 0 and 1, and epoch 1 published nothing. Its bucket is empty, so any value passes the opening.

The segment stops at the entry anchor of the first epoch it does not cover, so the following epoch's nullifier is someone else's to test. When the lineage lifts over the segment, it comes to rest on that anchor. In the running note's case this leaves epoch 7, which consensus scans directly, and that is the handover promised in chapter 19. The creation epoch works like any other, except that QrSpendableInit also opens that epoch's bucket at $\mathsf{cm}$ and requires zero. That check needs no profile, since a root of any bucket is a tachygram the epoch published. The deep dive has the wallet handle the creation epoch directly, which fits the rule that the service never sees $\mathsf{cm}$.

The routing network produces one proof per final bucket, and a builder would rather not store them all. So it folds them into a tree, a Poseidon Merkle tree whose node has four children. Two proofs at a time go in through EvidenceTreeLeafPair, and a builder short of four leaves repeats one. Each leaf digests the bucket's header, namely its epoch, both anchors, $R_0$, depth, bits, and commitment. With our three buckets, the last repeats:

The node over these four slots hashes to the root 33444, and this one value stands for all the buckets. To serve a query for bucket 01, a builder reveals the four children, the verifier rehashes them to 33444, and it then checks the bucket's fields against slot 2's digest.

A query walks down with EvidenceTreeDescend, and EvidenceTreeOpen replays the bucket as an ordinary QrBucket, which the steps above accept unchanged.

A quaternary tree with depth 13 has $4^{13}=2^{26}$ leaves, which is the deep dive's intended maximum, so an opening costs at most 13 node hashes and one leaf digest.

The leaf must bind the profile, for the reason in Section 12.

Suppose the leaf did not bind the profile, and a builder wanted to prove the published value 41 absent. It could offer the contents of bucket 00 under the label 1. The profile check would pass, because the label is 41's true profile, and the opening would give 30, which is nonzero. With the profile in the leaf, that combination digests to 63923, which matches none of the slots, so the path check rejects it.

A tree claims nothing about which buckets it holds. A builder that omits a bucket can fail to answer a query, and it cannot answer wrongly, since each bucket carries its own whole-epoch claim. All of this evidence is built from public data, so anyone can check or replace a builder, and the table of roles marks these steps as possible for a wallet.

14. What the service learns

"Oblivious" refers to what the service does not know. The table separates what comes from the proof steps from what depends on policy.

The service can compare its list with everything published, so the wallet must never delegate a value that it will later publish.

Alice's spend sits in the bundle of chapter 19, which publishes 13229, 24937, 30698, 31831, 40944, 46656, 55113, 55356, 61177. A service holding the list 2976, 63093, 59553 for epochs 4 to 6 compares that list with the bundle and finds no match. If Alice had also delegated epoch 7, the service would hold 55113 and would see it published, which would tie her request to this bundle.

So a wallet that spends with target $e$ has to keep ${\mathsf{nf}}_e$ and ${\mathsf{nf}}_{e+1}$ out of every request, as chapter 1 noted, which means a wallet that delegates ahead of time must spend with a target above everything it has delegated.

Beyond that, the sources point to measures and do not settle them. A range starts near a note's creation, so a request can suggest the note's age, and a stream of requests can reveal when a wallet stops asking. The deep dive suggests standard ranges, decoys, and local continuation to give different requests the same shape, and different ranges to different services, so that none of them sees the whole sequence. None of this is specified.

The table covers what the service's inputs reveal. What a proof itself reveals is a separate question, because chapter 2 records that Ragu's book and code do not yet establish zero knowledge.

15. Why cheating fails

Each row assumes that proofs cannot be forged, which rests on the proof system of the earlier chapters. As the status note at the top of this chapter said, the steps do not yet run as real circuits, so this describes the design.

16. Where this chapter leaves us

This chapter took the following steps:

1. A spend needs one absence proof per closed epoch, and the wallet can hand the reading to a service by sending explicit values.
2. The service proves a statement about arbitrary values, and the wallet proves its derivation. UnspentBind joins the two branches through a divisibility check.
3. Plain roots lose the epoch and linear factors can be rescaled, so each pair $(i,m)$ becomes the irreducible cubic $(m+(i+1)X{)}^3-c$ with $c$ a non-cube, which makes a product determine its pairs.
4. The check $N=C\cdot \Delta$ runs at a challenge fixed after all three commitments, and $C$ holds the factors that the service never tested.
5. An epoch's polynomial is too large to open, so builders route its tachygrams into buckets by a profile of quadratic-residue bits that any value can compute for itself.
6. A polynomial identity attests all of one side's members at once, and each descent attests the sibling, so a child cannot lack a member of its own class.
7. Sealing makes each bucket cover the whole epoch, and an opening at a value with a matching profile proves absence for that epoch. Segments then compose across epochs, and an evidence tree lets a builder retain one proof.
8. The service sees values, epochs, and timing. It learns no field of the note as long as those values are never published, although a range and its timing can still hint at the note's age, and the policies that would hide such patterns are unspecified at this commit.

All of this describes one commit of a proposal that has not activated, whose service ZIP is empty, and whose steps still run against a mock of Ragu. We have now seen most of the proof steps one at a time, with several chapters in between. The next chapter puts them in lifecycle order as PCD steps, from deriving nullifiers through bootstrapping, maintaining, and spending, and says who runs each.