This section constructs the commitment on which the FlyClient protocol and the
chain-history commitment of ZIP 221 rest: a binary hash tree over a sequence
of values whose shape is fixed by the length of the sequence, extended by one
value at logarithmic cost, and opened at one position j by a path from
which the root over the prefix of length
Throughout,
Let
if
if
Every internal node with children of values v l and v r has value H (v l ∥ v r) , the image of the 2 κ -bit concatenation of its children’s values. The leaves are ordered from left to right and leaf j holds x j . The root rt n is the value of the root node; range abbreviates Merkle mountain range.
The depth of a node is the number of edges from the root to it, and
the depth of a tree the maximal depth of a leaf. A perfect subtree of
altitude a is a subtree with 2 a leaves, all at depth a below its
root; its root node v has altitude
ZIP 221, “Terminology”, calls a Merkle mountain range a binary hash tree
that admits appends of new leaves without changing the value of existing
nodes; Theorem 3.11 and Proposition 3.12 below
establish it for Definition 3.1 for the peaks and every node
beneath them. An append rehashes only the right-spine nodes above the first
perfect one, the counterparts of the bagging nodes of ZIP 221,
“Background”.
Definition 3.1 is ePrint
2019/226, Definition 11, with the base case
Let
A range over 2 a values is a perfect subtree of altitude a .
Every left child in M n is perfect: the left child of a node over
Descend the right spine of M n from the root, stopping at the first node whose leaf count is a power of two. The left children of the nodes passed, followed by the node where the descent stops, are perfect subtrees of pairwise distinct power-of-two sizes, decreasing from the root downwards, covering consecutive runs of leaves from left to right; their sizes are the terms of the binary expansion of n .
The range M n has depth exactly ⌈ log 2 n ⌉ , which is 0
for
(1) By induction on a . For
(2) Every node over
(3) Let a right-spine node have m leaves. If m is a power of two, the
node is perfect by (1) and the descent stops. Otherwise
(4) By induction on n . For
For
| rt 7 = H (P 1 ∥ H (H (x 5 ∥ x 6) ∥ x 7)) . |
For
Let
The peaks are the mountains of ZIP 221, “Background”, whose leftmost peak is the highest. The same section numbers nodes in the order of their creation; that numbering enters no committed value and no check, and the root is a function of the leaf sequence and the bagging order of Definition 3.5 alone. No node numbering is used in this volume.
Let
| Bag R (P 1, ..., P d) | = H (P 1 ∥ H (P 2 ∥ ⋯ H (P d − 1 ∥ P d) ⋯)), | ||
| Bag L (P 1, ..., P d) | = H (⋯ H (H (P 1 ∥ P 2) ∥ P 3) ⋯ ∥ P d) ; |
a single peak is its own bag under either fold. The left fold is the order
of ZIP 221, “Background”, which repeatedly joins the two leftmost peaks. For
For every
By Lemma 3.2(3) the nodes named are perfect subtrees
whose sizes are the terms of the binary expansion of n , largest first,
covering consecutive runs of leaves from the left: they are
Let
| depth R (n, j) = { a i + i i < d, a d + d − 1 i = d, depth L (n, j) = { a 1 + d − 1 i = 1, a i + d − i + 1 i ≥ 2 . |
Consequently the depth of M n R is ⌈ log 2 n ⌉ ; the depth of
M n L is
The leaf lies at depth a i below the root of P i ; it remains to find the
depth of that root in the bag. Under Bag R the t -th bagging node
lies at depth
Maxima. Under R ,
A cycle of H is a value v and a nonempty sequence of evaluations of H that, starting from inputs that include v , recomputes v .
Let
the roots rt n R and rt n L are distinct hash
expressions over the same peaks, and from values of the peaks for which
for every leaf j , the sequence of sides of the siblings on leaf j ’s path above its peak differs between M n R and M n L ;
the peaks and the perfect subtrees beneath them coincide, and so do the asymptotic costs of append, of storage of the peaks and of a path, each logarithmic in n ; the leaf depths differ as in Lemma 3.7, so the bound ⌈ log 2 n ⌉ on the path length of ePrint 2019/226 does not hold for M n L .
Definition 3.1 splits
(1) The root inputs are P 1 ∥ Bag R (P 2, ..., P d)
and Bag L (P 1, ..., P d − 1) ∥ P d . If the root
values agree and these 2 κ -bit strings differ, they are a collision.
Otherwise
(2) Above P 1 the path has under R the single sibling
Bag R (P 2, ..., P d) and under L the
(3) Both trees are built on the peaks of Definition 3.4, which
depend on the leaf sequence alone; there are
Collision resistance alone does not exclude a cycle, so part (1) does not assert that the two roots differ numerically. No later statement of this volume uses such an inequality; the later sections use the shapes and path lengths of part (2) and Lemma 3.7.
The eleven-leaf tree of ZIP 221, “Background”, has
| rt 11 L = H (H (P 1 ∥ P 2) ∥ P 3), rt 11 R = H (P 1 ∥ H (P 2 ∥ P 3)) . |
A leaf of P 1 , P 2 , P 3 has path length 4 , 3 , 2 under Bag R and 5 , 3 , 1 under Bag L . Figure 2 shows both trees.
Every node v of a range carries its leaf count m . Procedure
Append (v, x) takes the root v of a range over m leaves and a
value
if m is a power of two ( v is perfect;
otherwise, with children v l and v r , replace v r by
Append (v r, x) , set the value of v to
H (v l ∥ v r) with the new v r , set its leaf count to
The construction is ePrint 2019/226, Algorithm 5. The order H (v ∥ x) in step 1 is that of the algorithm and of Definition 3.1; the base case of the paper’s proof of its Theorem 6 writes the reverse order.
For every leaf count
By induction on n , following ePrint 2019/226, Theorem 6. If
Procedure Append (M n, x n + 1) creates or rehashes only
right-spine nodes of M n and one new node, with at most
The recursion descends the right spine until the first node whose leaf count is a power of two, at depth at most ⌈ log 2 n ⌉ (Lemma 3.2(4)), evaluates H once to create the new node, and once more at each spine node above it. Left children and the node where the descent stops are never modified. □
Figure 1 shows the case
Let
The verifier Verify b (rt, n, j, x, π) , on
rejects unless
sets
accepts if and only if
By construction Verify b accepts (x j, π) with π the
inclusion path of leaf j against rt n b . Under Bag R
every path has at most ⌈ log 2 n ⌉ siblings
(Lemma 3.7); ePrint 2019/226, Definition 10, counts at most
For
For rt j , by induction on n , following ePrint 2019/226,
Theorem 7, with siblings bottom-up. If
If
If
If
For rt j − 1 , the bottom-up fold of Lemma 3.15, whose proof does not use this theorem. The paper’s proof lists the path top-down with the path nodes included, while its Algorithm 3 outputs the siblings bottom-up; the bottom-up format of Definition 3.13 is the one fixed here. □
Let
Under Bag R the left siblings, from the top down, are the
peaks of (x 1, ..., x j − 1) . The bottom-up fold (set r to the
lowest left sibling, then
Under Bag L , for
A leaf
Leaf j lies at offset
Correctness of the construction is Lemma 3.15. The construction corrects the printed pseudocode of ePrint 2019/226, Algorithm 6, which uses an undefined index, ends in a vestigial boolean comparison, and has a call signature that does not match its call in Algorithm 2, and it fixes the siblings bottom-up.
Let
Both chains
The theorem extends the Crypto Guide’s Theorem “Merkle trees are succinct position-binding vector commitments” (§“Vector commitments”) from perfect trees to the shapes fixed by n and the bagging order. It is stated for a root chosen by the adversary, not for a fixed honest root as in the Crypto Guide’s Remark “Scope: a fixed honest root”: in FlyClient the root of the head comes from the prover.
Let
If
If (x 1 ′, ..., x m ′) differs from (x 1, ..., x m) at some
When x i is the hash of block i , binding the blocks themselves requires in addition collision resistance of that hash.
(1) The honest pair (x j, π ∗) is accepted. By
Theorem 3.17 the pairs (x, π) and (x j, π ∗) are
equal barring a collision, so
Part (1) is ePrint 2019/226, Corollary 3, and part (2) its Corollary 4, stated for both bagging orders and with the collision named.
A verifier that samples leaves by cumulative weight needs each path to bind the sampled leaf’s weight interval, and a verifier that constrains unsampled leaves needs aggregates over their runs; both follow from metadata propagated up the tree (ePrint 2019/226, Section 2 and Section 6).
An aggregating range extends Definition 3.1, after ZIP 221, “Specification”, which propagates metadata “by either summing the metadata of both children, or inheriting the metadata of a specific child”. It is given by:
a set of node tuples
a serialisation ser from tuples to bit strings that is injective and prefix-free, no value of ser being a proper prefix of another, so that ser (l) ∥ ser (r) determines the pair (l, r) ;
a leaf map from a leaf’s data to its tuple;
for each field f i one rule: inherit from the left child, inherit from the right child, or sum, in Z or in Z / 2 256 Z ;
the parent map par (l, r) , whose hash field is H (ser (l) ∥ ser (r)) , over the children’s full serialisations, and whose other fields follow the rules.
A labelling of the shape M n b with leaf tuples at the leaves is
consistent when every internal node is par of its
children; its root is the root’s tuple. Inclusion paths and
Verify b are those of Definition 3.13 with tuples in
place of values and par in place of
A serialisation of fixed width is prefix-free. Injectivity alone does not
suffice: with
Let ser be injective and prefix-free,
From two consistent labellings of M n b with equal root tuples that differ at some node, a collision of H is computed; barring a collision, equal roots imply agreement on every field of every node.
From any root tuple, chosen by the adversary, and two distinct accepted paths (leaf tuple and sibling tuples) at one position j , a collision of H is computed: an accepted path binds the full tuple of every node it recomputes and of every sibling it carries.
For
Unique decoding: if
(1) Take a node at which the labellings differ and whose parent they agree on; one exists because they agree at the root. The parent tuples are equal, so their hash fields are, while the child pairs differ; by unique decoding the two hash inputs differ: a collision.
(2) As in the proof of Theorem 3.17, with tuples: at the highest step whose inputs differ, the outputs are equal tuples, hence have equal hash fields, and the inputs are distinct pairs, hence by unique decoding distinct strings: a collision.
(3) In a consistent labelling the tuple of every subtree, a bagging node
included, is determined by its leaf tuples through par . By
Lemma 3.15 the left siblings are, under R , the peak
tuples of the consistent labelling over the first
Let ser be injective and prefix-free, let w be a summed field, w j the w -field of the tuple of leaf j , and W the sum of the w -fields of the left siblings on an accepted path of leaf j .
Binding, for any root tuple chosen by the adversary: barring a
collision, W and w j are functions of the root, b , n and j . One
accepted path therefore binds the interval
Meaning, for the path of a consistent labelling:
Part (2) is not claimed for a root chosen by the adversary, whose siblings off the path are never recomputed from their children.