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 by a path from
which the root over the prefix of length
Throughout,
Let
if
if
Every internal node with children of values and has value , the image of the -bit concatenation of its children’s values. The leaves are ordered from left to right and leaf holds . The root 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 is a subtree with leaves, all at depth below its
root; its root node 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 values is a perfect subtree of altitude .
Every left child in is perfect: the left child of a node over
Descend the right spine of 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 .
The range has depth exactly , which is
for
(1) By induction on . For
(2) Every node over
(3) Let a right-spine node have leaves. If is a power of two, the
node is perfect by (1) and the descent stops. Otherwise
(4) By induction on . For
For
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
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 , largest first,
covering consecutive runs of leaves from the left: they are
Let
Consequently the depth of is ; the depth of
is
The leaf lies at depth below the root of ; it remains to find the
depth of that root in the bag. Under the -th bagging node
lies at depth
Maxima. Under ,
A cycle of is a value and a nonempty sequence of evaluations of that, starting from inputs that include , recomputes .
Let
the roots and are distinct hash
expressions over the same peaks, and from values of the peaks for which
for every leaf , the sequence of sides of the siblings on leaf ’s path above its peak differs between and ;
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 ; the leaf depths differ as in Lemma 3.7, so the bound on the path length of ePrint 2019/226 does not hold for .
Definition 3.1 splits
(1) The root inputs are
and . If the root
values agree and these -bit strings differ, they are a collision.
Otherwise
(2) Above the path has under the single sibling
and under 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.
Every node of a range carries its leaf count . Procedure
takes the root of a range over leaves and a
value
if is a power of two ( is perfect;
otherwise, with children and , replace by
, set the value of to
with the new , set its leaf count to
The construction is ePrint 2019/226, Algorithm 5. The order 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 , following ePrint 2019/226, Theorem 6. If
Procedure creates or rehashes only
right-spine nodes of 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 (Lemma 3.2(4)), evaluates 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 , on
rejects unless
sets
accepts if and only if
By construction accepts with the
inclusion path of leaf against . Under
every path has at most siblings
(Lemma 3.7); ePrint 2019/226, Definition 10, counts at most
For
For , by induction on , following ePrint 2019/226,
Theorem 7, with siblings bottom-up. If
If
If
If
For , 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 the left siblings, from the top down, are the
peaks of . The bottom-up fold (set to the
lowest left sibling, then
Under , for
A leaf
Leaf 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 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 differs from at some
When is the hash of block , binding the blocks themselves requires in addition collision resistance of that hash.
(1) The honest pair is accepted. By
Theorem 3.17 the pairs and 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 from tuples to bit strings that is injective and prefix-free, no value of being a proper prefix of another, so that determines the pair ;
a leaf map from a leaf’s data to its tuple;
for each field one rule: inherit from the left child, inherit from the right child, or sum, in or in ;
the parent map , whose hash field is , over the children’s full serialisations, and whose other fields follow the rules.
A labelling of the shape with leaf tuples at the leaves is
consistent when every internal node is of its
children; its root is the root’s tuple. Inclusion paths and
are those of Definition 3.13 with tuples in
place of values and in place of
A serialisation of fixed width is prefix-free. Injectivity alone does not
suffice: with
Let be injective and prefix-free,
From two consistent labellings of with equal root tuples that differ at some node, a collision of 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 , a collision of 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 . By
Lemma 3.15 the left siblings are, under , the peak
tuples of the consistent labelling over the first
Let be injective and prefix-free, let be a summed field, the -field of the tuple of leaf , and the sum of the -fields of the left siblings on an accepted path of leaf .
Binding, for any root tuple chosen by the adversary: barring a
collision, and are functions of the root, , and . 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.