This section constructs the note commitment tree of a pool and its Merkle hash, defines the anchors, proves in Proposition 5.9 that a valid authentication path to an anchor exhibits a leaf of the anchored tree unless it yields a collision of the hash’s Sinsemilla instance or an input on which that instance returns , and proves in Lemma 5.16 that the authentication path of a leaf is a function of public data.
Requirement R2 of “Requirements on a shielded payment” (§1.4) asks the consumer of a note of non-zero value to show that the note was previously committed, without identifying it. In the Orchard protocol the claim to be shown is that the extracted commitment of the note (Definition 4.4) is a leaf of the note commitment tree of the note’s pool, and the leaf is not to be disclosed. Membership of a private leaf under a public root is provable in zero knowledge, with the root public and the leaf, its position and its authentication path private (Crypto Guide, §“Privacy-preserving membership via zero-knowledge paths”, Theorem “Privacy-preserving membership”). We construct the tree, its roots, called anchors, and its authentication paths; the relation proved for each Action is the Action statement, defined in “The Action statement” (§9.2).
Let
(protocol specification, §“Constants”). Each pool of the Orchard
protocol has its own note commitment tree, an append-only Merkle tree
(Crypto Guide, §“Binary Merkle trees” and §“Append-only and
incrementally updatable trees”) of fixed depth
Appending. Each Action of the pool in a transaction publishes the extracted commitment of its created note (§4.4). When the transaction enters the chain, each such is appended to the pool’s tree: it occupies the leaf for the least unused index , and is the note position of that commitment. Every pool’s tree has no appended leaf before the first block of the chain.
Leaves. After appends, the leaf is the value
appended at position for
Internal nodes. For
with the Merkle hash constructed below; the root is .
(Protocol specification, §“Note Commitment Trees”, §“Merkle Path Validity”, §“Note Commitments” and §“Transactions and Treestates”.)
Let
is
where
with the extracted Sinsemilla hash of §2.4 and field elements encoded through their integer representatives. The protocol specification names the map and the width (§“ Hash Function” and §“Constants”).
The prefix
Because ends in , each layer’s output has the type of its inputs, and one hash composes from the leaves to the root. Proofs of the Action statement, defined in “The Action statement” (§9.2), are Halo 2 proofs with the Vesta curve (protocol specification, §“Zero-Knowledge Proving System”), whose scalar field is (Math Guide, §“Base fields, scalar fields, and the Pasta cycle”). A node that is one element of is one value of that proof’s arithmetic, whereas a point-valued node would carry two coordinates and a curve-equation condition at each of the layers.
A node serves only as a digest, never to recover a point, and
The prefix
No point of the Pallas group satisfies
By definition
The protocol specification, §“Note Commitment Trees”, and ZIP 258,
“Changes to the Protocol Specification”, state the capacity rule: a block
must not add Ironwood-pool note commitments that would make the
Ironwood-pool note commitment tree exceed its capacity of
A pool’s treestate comprises its note commitment tree and its nullifier set, constructed in “Nullifier sets” (§6.2). Treestates are chained: the input treestate of the first block is empty; the input treestate of the first transaction of a block is the final treestate of the preceding block, and that of each later transaction the output treestate of the preceding transaction; the final treestate of a block is the output treestate of its last transaction (protocol specification, §“Transactions and Treestates”). The anchor of a block in a pool is the root of the pool’s tree in the block’s final treestate, an element of ; every block has exactly one anchor per pool. A bundle carries one anchor field, in the Ironwood pool and in the Orchard pool, shared by all its Actions; an Action carries no anchor of its own (“Action descriptions and bundles”, §11.1; protocol specification, §“Action Transfers and their Descriptions”).
The protocol specification, §“Action Transfers and their Descriptions”, and ZIP 258, “Changes to the Protocol Specification”, state the anchor rule: whenever a transaction has Ironwood-pool Actions, its field must refer to some earlier block’s final Ironwood-pool treestate, that is, equal the Ironwood-pool anchor of a block that precedes the transaction’s block in the chain. The field is bound likewise to the Orchard pool. The rule sets no bound on how far back that block lies.
Let be the anchor of a block in a pool, the number of
leaves appended to the pool’s tree through that block, and
| (2) |
The triple is a valid path
to if
From a valid path to with
In particular, if
The argument is the Crypto Guide’s Theorem “Soundness of Merkle membership proofs” (§“Soundness: forging a path implies a collision”), with layer-dependent compressions.
(i) Let
(ii) The extraction of (i) is deterministic and defined for every list of
leaves, so it applies to leaves that an adversary chose. An adversary that
outputs a valid path with
(iii) If
Appending leaves changes the final treestates of later blocks and of no earlier one. Once a block is in the chain, its anchor therefore roots one fixed tree: a valid path to it stays valid after later appends, the anchor stays admissible under the anchor rule while remains in the chain, and Proposition 5.9 applies to it at any later time. A valid path to the anchor of for an extracted note commitment shows that the commitment was appended in or earlier, which is what R2 requires. Excluding a second consumption of a note is not the task of the tree, which is append-only (protocol specification, §“Note Commitment Trees”), but that of the nullifier, constructed in “Nullifiers” (§6).
By the anchor rule, is the anchor of a block that
precedes . Proposition 5.9(iii), applied to , gives
For a consumed note of non-zero value, the relation that each Action proves, stated in “The Action statement” (§9.2), supplies such a path, up to two relaxations treated there. Corollary 12.8, in “Double-spend resistance” (§12.2), concludes that such a note is consumed only in a block after the one that created it, so that its consumption does not chain within a block.
A reorganisation is the replacement of the chain’s most recent blocks by a competing branch.
With the height of a block as in §1.1, the tip is
the last block of the chain. A reorganisation that removes the block whose
final treestate a bundle’s anchor refers to leaves the transaction in
violation of the anchor rule on the new chain, unless a block of the new
chain that precedes the transaction’s block has the same anchor;
to be included in the new chain, the transaction must then be rebuilt
against an anchor of that chain. The block blocks below a tip of height
, the block at height
The block target spacing, the intended mean interval between consecutive blocks, is seconds (ZIP 218, “Block target spacing”).
ZIP 315 recommends that a transaction built when the tip is at height
use as its anchor the final treestate of the block at height
The anchor is published with the bundle. Call the set
Let the pool’s tree hold leaves, namely the tree that the anchor
of a block roots, for a block at or after the one that
appended the note’s commitment, so that the note position satisfies
the sibling of the level- route node in the tree of size , with
The genuine path of an appended leaf is accepted: the fold on
reproduces the route
nodes,
Let the tree hold leaves, let
For each level the entry of the authentication path of is as follows.
If
If
Hence the authentication path is a deterministic function of and of the first leaves, which are the values published by the pool’s Actions in the chain through the anchoring block. A holder of the note who has these leaves computes the path without communicating , and verification needs, besides the path, only the public anchor.
By the recurrence of the tree, the node is a function of the leaves
at positions
The anchor is public. The position, the consumed note’s and its authentication path are not fields of the bundle, and the holder of the note computes the path locally (Lemma 5.16): obtaining the path of a particular position from another party would disclose to that party. The candidate set for the consumed note is the candidate set of the anchor (§5.2), the positions of the appended leaves of the anchored tree. Leaves that an observer knows by other means to be commitments of dummy created notes (§4.4) or of notes already consumed, and other data of the transaction, reduce the effective set, so alone does not measure it. What an Action reveals is stated in Theorem 12.13 (“Privacy”, §12.4).