VII FlyClient Guide: Merkle mountain ranges, the chain-history commitment, and the FlyClient sampling protocol 2 The verification problem 4 The FlyClient security model

3 Merkle mountain ranges

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 $j-1$ is recomputed, and, under the right fold, also the root over the prefix of length $j$ . The construction is parametrised by the order in which its perfect subtrees are joined: the right fold of ePrint 2019/226 and the left fold of ZIP 221, “Background”. The fixed-depth trees of the Crypto Guide, §“Binary Merkle trees” and §“Append-only and incrementally updatable trees”, are the special case of a sequence whose length is a power of two.

Throughout, $H\colon\{0,1\}^{*}\to\{0,1\}^{\kappa}$ is a hash function drawn from a family that is collision resistant in the sense of the Crypto Guide, Definition “Collision resistance” (§“Security notions: preimage, second-preimage, and collision resistance”); ePrint 2019/226, Definition 8, states the same assumption. A statement holds barring a collision when a deterministic procedure, given any input on which the statement fails, outputs two distinct strings with equal images under $H$ , using the number of evaluations of $H$ stated with it. Such a procedure is a tight reduction in the sense of the Crypto Guide, Definition “Reduction loss and tightness” (§“Reductions”), so a probabilistic polynomial-time adversary makes the statement fail with negligible probability.

3.1 The recursive definition

Definition 3.1 (Merkle mountain range).

Let $n\geq 1$ and $x_{1},\dots,x_{n}\in\{0,1\}^{\kappa}$ . The Merkle mountain range $M_{n}$ over $(x_{1},\dots,x_{n})$ is the rooted ordered binary tree, every internal node of which has exactly two children, a left and a right one, with a value in $\{0,1\}^{\kappa}$ at every node, defined by recursion on $n$ :

1.

if $n=1$ , $M_{1}$ is the single leaf with value $x_{1}$ ;
2.

if $n>1$ , let $i=\lfloor\log_{2}(n-1)\rfloor$ , so that $2^{i}<n\leq 2^{i+1}$ and $2^{i}$ is the largest power of two strictly below $n$ ; the root has as left child the range $M_{2^{i}}$ over $(x_{1},\dots,x_{2^{i}})$ and as right child the range $M_{n-2^{i}}$ over $(x_{2^{i}+1},\dots,x_{n})$ , where $1\leq n-2^{i}\leq 2^{i}$ .

Every internal node with children of values $v_{\ell}$ and $v_{r}$ has value $H(v_{\ell}\,\|\,v_{r})$ , the image of the $2\kappa$ -bit concatenation of its children’s values. The leaves are ordered from left to right and leaf $j$ holds $x_{j}$ . The root $\mathsf{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 $\mathrm{alt}(v)=a$ . The right spine is the sequence of nodes that starts at the root and continues from each internal node to its right child, ending at a leaf.

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 $n=1$ , implicit there, made explicit. Every node of $M_{n}$ is the root of a range over a run of consecutive values, by the recursion. Its depth is fixed in Lemma 3.2.

Lemma 3.2 (Left children are perfect).

Let $n\geq 1$ .

1.

A range over $2^{a}$ values is a perfect subtree of altitude $a$ .
2.

Every left child in $M_{n}$ is perfect: the left child of a node over $m\geq 2$ leaves is the perfect range over $2^{\lfloor\log_{2}(m-1)\rfloor}$ leaves.
3.

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$ .
4.

The range $M_{n}$ has depth exactly $\lceil\log_{2}n\rceil$ , which is $0$ for $n=1$ .

Proof.

(1) By induction on $a$ . For $a=0$ the range is a leaf. For $a\geq 1$ , $\lfloor\log_{2}(2^{a}-1)\rfloor=a-1$ , so the root has two children over $2^{a-1}$ values each, perfect of altitude $a-1$ by hypothesis; all leaves lie at depth $a$ .

(2) Every node over $m\geq 2$ leaves is a range $M_{m}$ , whose left child is a range over $2^{\lfloor\log_{2}(m-1)\rfloor}$ values, perfect by (1).

(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 $2^{\lfloor\log_{2}m\rfloor}<m$ , hence $m-1\geq 2^{\lfloor\log_{2}m\rfloor}$ and $\lfloor\log_{2}(m-1)\rfloor=\lfloor\log_{2}m\rfloor$ : the left child takes the highest term $2^{\lfloor\log_{2}m\rfloor}$ of the binary expansion of $m$ and the right child the remaining terms. By induction along the spine, the left children passed take the terms of the expansion of $n$ from the highest downwards, and the descent stops when one term is left. The runs are consecutive because each left child precedes its sibling’s leaves.

(4) By induction on $n$ . For $n=1$ the depth is $0$ . For $n>1$ let $i=\lfloor\log_{2}(n-1)\rfloor$ . The left child is perfect over $2^{i}$ leaves, of depth $i$ ; the right child has $n-2^{i}\leq 2^{i}$ leaves and depth $\lceil\log_{2}(n-2^{i})\rceil\leq i$ by hypothesis. The depth of $M_{n}$ is therefore $i+1$ , which equals $\lceil\log_{2}n\rceil$ since $2^{i}<n\leq 2^{i+1}$ . □

Example 3.3 (Six and seven leaves).

For $n=6$ , $i=\lfloor\log_{2}5\rfloor=2$ and $6=4+2$ . The left child is the perfect range $P_{1}$ over $x_{1},\dots,x_{4}$ ; the right child has two leaves, is perfect, and has value $P_{2}=H(x_{5}\,\|\,x_{6})$ ; hence $\mathsf{rt}_{6}=H(P_{1}\,\|\,P_{2})$ . For $n=7$ , $i=\lfloor\log_{2}6\rfloor=2$ and $7=4+3$ ; the three-leaf right child splits as $3=2+1$ , so $7=4+(2+1)$ and

\mathsf{rt}_{7}=H\bigl{(}P_{1}\,\|\,H(H(x_{5}\,\|\,x_{6})\,\|\,x_{7})\bigr{)}.

Refer to caption — Figure 1: The range $M_{6}$ over $x_{1},\dots,x_{6}$ in single-rooted form (solid): the root $\mathsf{rt}_{6}$ has left child $P_{1}$ , the perfect range over $x_{1},\dots,x_{4}$ , and right child $P_{2}=H(x_{5}\,\|\,x_{6})$ , the perfect range over $x_{5},x_{6}$ . The nodes $P_{1}$ and $P_{2}$ are the peaks of Definition 3.4; $P_{2}$ is the first perfect node on the right spine of $M_{6}$ , whose last node is the leaf $x_{6}$ . Dashed: appending $x_{7}$ creates only the nodes $H(P_{2}\,\|\,x_{7})$ and $\mathsf{rt}_{7}=H(P_{1}\,\|\,H(P_{2}\,\|\,x_{7}))$ ; the nodes $P_{1}$ , $P_{2}$ and every node beneath them are shared by $M_{6}$ and $M_{7}$ .

3.2 Peaks and bagging

For $n\geq 1$ , $\mathrm{popcount}(n)$ is the number of ones in the binary expansion of $n$ .

Definition 3.4 (Peaks).

Let $n\geq 1$ and write $n=2^{a_{1}}+\dots+2^{a_{d}}$ with $a_{1}>\dots>a_{d}\geq 0$ , so that $d=\mathrm{popcount}(n)$ , and let $s_{i}=\sum_{l<i}2^{a_{l}}$ for $1\leq i\leq d$ . The peaks of the sequence $(x_{1},\dots,x_{n})$ are $P_{1},\dots,P_{d}$ , where $P_{i}$ is the perfect range over $(x_{s_{i}+1},\dots,x_{s_{i}+2^{a_{i}}})$ , of altitude $\mathrm{alt}(P_{i})=a_{i}$ . There is one peak per set bit of $n$ , of altitude that bit’s index; the altitudes strictly decrease from the left, and the peaks cover consecutive runs of leaves. The symbol $P_{i}$ denotes both the subtree and its root value.

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.

Definition 3.5 (Bagging orders).

Let $P_{1},\dots,P_{d}$ be the peaks of $(x_{1},\dots,x_{n})$ . The right fold and the left fold of the peaks are

	$\displaystyle\mathrm{Bag}_{R}(P_{1},\dots,P_{d})$	$\displaystyle=H\bigl{(}P_{1}\,\\|\,H(P_{2}\,\\|\,\cdots H(P_{d-1}\,\\|\,P_{d})% \cdots)\bigr{)},$
	$\displaystyle\mathrm{Bag}_{L}(P_{1},\dots,P_{d})$	$\displaystyle=H\bigl{(}\cdots H(H(P_{1}\,\\|\,P_{2})\,\\|\,P_{3})\cdots\\|\,P_{d}% \bigr{)};$

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 $b\in\{R,L\}$ the tree $M^{b}_{n}$ consists of the $d$ perfect peak subtrees joined by the $d-1$ internal bagging nodes of $\mathrm{Bag}_{b}$ , and $\mathsf{rt}^{b}_{n}$ is its root value. Both are determined by $n$ , $b$ and the leaf sequence.

Proposition 3.6 (Peaks of the recursive form).

For every $n\geq 1$ the peaks of $(x_{1},\dots,x_{n})$ are exactly the left children of the right-spine nodes of $M_{n}$ , from the root down to the first perfect right-spine node, followed by that node. Hence $M_{n}=M^{R}_{n}$ and $\mathsf{rt}_{n}=\mathrm{Bag}_{R}(P_{1},\dots,P_{d})$ .

Proof.

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 $P_{1},\dots,P_{d}$ in order. Along the spine, the $t$ -th node passed has value $H(P_{t}\,\|\,v_{t+1})$ with $v_{t+1}$ the value of the next spine node, and the last spine node considered is $P_{d}$ ; unwinding gives the right fold. □

Lemma 3.7 (Path lengths under the two baggings).

Let $n\geq 1$ have peaks $P_{1},\dots,P_{d}$ of altitudes $a_{1}>\dots>a_{d}$ , let $b\in\{R,L\}$ , and let leaf $j$ lie in $P_{i}$ . The depth $\mathrm{depth}_{b}(n,j)$ of leaf $j$ in $M^{b}_{n}$ is

\mathrm{depth}_{R}(n,j)=\begin{cases}a_{i}+i&i<d,\\ a_{d}+d-1&i=d,\end{cases}\qquad\mathrm{depth}_{L}(n,j)=\begin{cases}a_{1}+d-1&% i=1,\\ a_{i}+d-i+1&i\geq 2.\end{cases}

Consequently the depth of $M^{R}_{n}$ is $\lceil\log_{2}n\rceil$ ; the depth of $M^{L}_{n}$ is $\lfloor\log_{2}n\rfloor+\mathrm{popcount}(n)-1\leq 2\lfloor\log_{2}n\rfloor$ , attained by the leaves of $P_{1}$ ; and the two depths differ exactly when $d\geq 3$ . For $n=7$ they are $3$ and $4$ ; for $n=127$ they are $7$ and $12$ . Leaf depths are functions of $(b,n,j)$ ; for $d\geq 2$ they are not all equal.

Proof.

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 $\mathrm{Bag}_{R}$ the $t$ -th bagging node lies at depth $t-1$ and has left child $P_{t}$ for $t\leq d-1$ , and the last bagging node has right child $P_{d}$ ; so $P_{i}$ lies at depth $i$ for $i<d$ and $P_{d}$ at depth $d-1$ . Under $\mathrm{Bag}_{L}$ the root has right child $P_{d}$ and left child $\mathrm{Bag}_{L}(P_{1},\dots,P_{d-1})$ , and inductively $P_{i}$ lies at depth $d-i+1$ for $i\geq 2$ while $P_{1}$ shares depth $d-1$ with $P_{2}$ ; for $d=1$ the single peak lies at depth $0$ .

Maxima. Under $R$ , $a_{i}\leq a_{1}-(i-1)$ gives $a_{i}+i\leq a_{1}+1$ and $a_{d}+d-1\leq a_{1}$ ; the maximum is $a_{1}+1$ for $d\geq 2$ and $a_{1}$ for $d=1$ , which is $\lceil\log_{2}n\rceil$ in both cases, as $n$ is a power of two exactly when $d=1$ . Under $L$ , for $i\geq 2$ , $a_{i}+d-i+1\leq a_{1}+d-2i+2\leq a_{1}+d-2$ , so the maximum is $a_{1}+d-1$ , attained by $P_{1}$ ; with $a_{1}=\lfloor\log_{2}n\rfloor$ and $d=\mathrm{popcount}(n)\leq\lfloor\log_{2}n\rfloor+1$ this is the stated value and bound. The maxima $a_{1}+1$ and $a_{1}+d-1$ coincide for $d=2$ , both equal $a_{1}$ for $d=1$ , and differ for $d\geq 3$ . For $d\geq 2$ a leaf of $P_{1}$ and a leaf of $P_{d}$ differ in depth under $R$ ( $a_{1}+1$ against at most $a_{1}$ ), and a leaf of $P_{1}$ and a leaf of $P_{2}$ under $L$ ( $a_{1}\neq a_{2}$ ). □

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$ .

Theorem 3.8 (Fold order).

Let $n\geq 1$ have $d$ peaks. The shapes $M^{R}_{n}$ and $M^{L}_{n}$ coincide if and only if $d\leq 2$ . For $d\geq 3$ :

1.

the roots $\mathsf{rt}^{R}_{n}$ and $\mathsf{rt}^{L}_{n}$ are distinct hash expressions over the same peaks, and from values of the peaks for which $\mathsf{rt}^{R}_{n}=\mathsf{rt}^{L}_{n}$ a collision or a cycle of $H$ is computed;
2.

for every leaf $j$ , the sequence of sides of the siblings on leaf $j$ ’s path above its peak differs between $M^{R}_{n}$ and $M^{L}_{n}$ ;
3.

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 $\lceil\log_{2}n\rceil$ on the path length of ePrint 2019/226 does not hold for $M^{L}_{n}$ .

Proof.

Definition 3.1 splits $n=2^{\lfloor\log_{2}(n-1)\rfloor}+(\text{rest})$ with the first peak on the left and recurses on the rest, which is the right fold (Proposition 3.6). For $d=1$ both folds are $P_{1}$ and for $d=2$ both are $H(P_{1}\,\|\,P_{2})$ . For $d\geq 3$ the root’s left child is $P_{1}$ under $R$ and a bagging node under $L$ , so the shapes differ.

(1) The root inputs are $P_{1}\,\|\,\mathrm{Bag}_{R}(P_{2},\dots,P_{d})$ and $\mathrm{Bag}_{L}(P_{1},\dots,P_{d-1})\,\|\,P_{d}$ . If the root values agree and these $2\kappa$ -bit strings differ, they are a collision. Otherwise $P_{1}=\mathrm{Bag}_{L}(P_{1},\dots,P_{d-1})$ and $P_{d}=\mathrm{Bag}_{R}(P_{2},\dots,P_{d})$ , each a value recomputed from itself by $d-2\geq 1$ evaluations of $H$ : a cycle.

(2) Above $P_{1}$ the path has under $R$ the single sibling $\mathrm{Bag}_{R}(P_{2},\dots,P_{d})$ and under $L$ the $d-1\geq 2$ siblings $P_{2},\dots,P_{d}$ . Above $P_{d}$ it has under $R$ the $d-1\geq 2$ siblings $P_{d-1},\dots,P_{1}$ and under $L$ the single sibling $\mathrm{Bag}_{L}(P_{1},\dots,P_{d-1})$ . Above $P_{i}$ with $2\leq i<d$ the first sibling is on the right under $R$ , namely $\mathrm{Bag}_{R}(P_{i+1},\dots,P_{d})$ , and on the left under $L$ , namely $\mathrm{Bag}_{L}(P_{1},\dots,P_{i-1})$ .

(3) Both trees are built on the peaks of Definition 3.4, which depend on the leaf sequence alone; there are $d\leq\lfloor\log_{2}n\rfloor+1$ of them. Appending $x_{n+1}$ joins the last peaks of equal altitude with $x_{n+1}$ , at most $\lfloor\log_{2}n\rfloor+1$ evaluations of $H$ , and re-bagging the at most $\lfloor\log_{2}(n+1)\rfloor+1$ new peaks costs one evaluation fewer than their number, under either fold. A path has at most $2\lfloor\log_{2}n\rfloor$ siblings under either fold by Lemma 3.7, whose depths are the stated ones. □

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.

Example 3.9 (Eleven leaves).

The eleven-leaf tree of ZIP 221, “Background”, has $11=8+2+1$ and peaks $P_{1}$ , $P_{2}$ , $P_{3}$ of altitudes $3$ , $1$ and $0$ , joined by two bagging nodes. The left fold that ZIP 221 commits and the right fold are

\mathsf{rt}^{L}_{11}=H\bigl{(}H(P_{1}\,\|\,P_{2})\,\|\,P_{3}\bigr{)},\qquad% \mathsf{rt}^{R}_{11}=H\bigl{(}P_{1}\,\|\,H(P_{2}\,\|\,P_{3})\bigr{)}.

A leaf of $P_{1}$ , $P_{2}$ , $P_{3}$ has path length $4$ , $3$ , $2$ under $\mathrm{Bag}_{R}$ and $5$ , $3$ , $1$ under $\mathrm{Bag}_{L}$ . Figure 2 shows both trees.

3.3 Appending a leaf

Construction 3.10 (Append).

Every node $v$ of a range carries its leaf count $m$ . Procedure $\mathrm{Append}(v,x)$ takes the root $v$ of a range over $m$ leaves and a value $x\in\{0,1\}^{\kappa}$ and returns the root of a range over $m+1$ leaves:

1.

if $m$ is a power of two ( $v$ is perfect; $m=1$ included), return a new node with left child $v$ , right child the leaf $x$ , value $H(v\,\|\,x)$ and leaf count $m+1$ ;
2.

otherwise, with children $v_{\ell}$ and $v_{r}$ , replace $v_{r}$ by $\mathrm{Append}(v_{r},x)$ , set the value of $v$ to $H(v_{\ell}\,\|\,v_{r})$ with the new $v_{r}$ , set its leaf count to $m+1$ , and return $v$ .

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.

Theorem 3.11 (Correctness of append).

For $n\geq 1$ , $\mathrm{Append}(M_{n},x_{n+1})$ is $M_{n+1}$ over $(x_{1},\dots,x_{n+1})$ : the leaves of $M_{n}$ followed by $x_{n+1}$ as the rightmost leaf.

Proof.

By induction on $n$ , following ePrint 2019/226, Theorem 6. If $n=2^{i}$ , Definition 3.1 for $n+1$ has $\lfloor\log_{2}n\rfloor=i$ and right part $1$ : left child $M_{n}$ , right child the leaf $x_{n+1}$ , which is step 1. Otherwise $n=2^{i}+m$ with $1\leq m<2^{i}$ , and $n+1=2^{i}+(m+1)$ with the same $i$ , since $m+1\leq 2^{i}$ . The left child $M_{2^{i}}$ is unchanged, and the right child is $\mathrm{Append}$ applied to the range $M_{m}$ over $(x_{2^{i}+1},\dots,x_{n})$ , which is $M_{m+1}$ over $(x_{2^{i}+1},\dots,x_{n+1})$ by hypothesis; step 2 rehashes the root. □

Proposition 3.12 (Cost of append).

Procedure $\mathrm{Append}(M_{n},x_{n+1})$ creates or rehashes only right-spine nodes of $M_{n}$ and one new node, with at most $\lceil\log_{2}n\rceil+1$ evaluations of $H$ . Every left child of $M_{n}$ , and the perfect right-spine node at which the recursion stops, is a subtree of $M_{n+1}$ with unchanged values.

Proof.

The recursion descends the right spine until the first node whose leaf count is a power of two, at depth at most $\lceil\log_{2}n\rceil$ (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 $n=6$ : two evaluations of $H$ create $H(P_{2}\,\|\,x_{7})$ and $\mathsf{rt}_{7}$ .

3.4 Inclusion paths and prefix roots

Definition 3.13 (Inclusion path).

Let $b\in\{R,L\}$ , $n\geq 1$ , $1\leq j\leq n$ , and $m=\mathrm{depth}_{b}(n,j)$ (Lemma 3.7). Let $u_{0},u_{1},\dots,u_{m}$ be the nodes from leaf $j$ to the root of $M^{b}_{n}$ . The inclusion path of leaf $j$ is $\pi=(\pi_{1},\dots,\pi_{m})$ , where $\pi_{t}$ is the value of the sibling of $u_{t-1}$ , listed bottom-up. The side $\sigma_{t}\in\{\text{left},\text{right}\}$ records whether that sibling is the left or the right child of $u_{t}$ . The sides and $m$ are functions of $(b,n,j)$ through the shape of $M^{b}_{n}$ .

The verifier $\mathrm{Verify}_{b}(\mathsf{rt},n,j,x,\pi)$ , on $\mathsf{rt},x\in\{0,1\}^{\kappa}$ and a sequence $\pi$ of $\kappa$ -bit values:

1.

rejects unless $|\pi|=\mathrm{depth}_{b}(n,j)$ ;
2.

sets $y_{0}=x$ and, for $t=1,\dots,m$ , $y_{t}=H(\pi_{t}\,\|\,y_{t-1})$ if $\sigma_{t}=\text{left}$ and $y_{t}=H(y_{t-1}\,\|\,\pi_{t})$ otherwise;
3.

accepts if and only if $y_{m}=\mathsf{rt}$ .

By construction $\mathrm{Verify}_{b}$ accepts $(x_{j},\pi)$ with $\pi$ the inclusion path of leaf $j$ against $\mathsf{rt}^{b}_{n}$ . Under $\mathrm{Bag}_{R}$ every path has at most $\lceil\log_{2}n\rceil$ siblings (Lemma 3.7); ePrint 2019/226, Definition 10, counts at most $\log_{2}n+1$ hashes, the leaf pair included. For $d\geq 2$ , path lengths differ between leaves (Lemma 3.7). The paper’s Algorithm 4 requires $|\pi|=\lceil\log_{2}(n-1)\rceil$ and so rejects valid paths: $1{,}225$ of the $8{,}384$ leaf paths of the ranges $M_{n}$ , $2\leq n\leq 129$ , among them both leaves of $M_{2}$ and leaf $5$ of $M_{6}$ . The verifier above fixes the length from $(b,n,j)$ instead. For $n$ a power of two, $M^{b}_{n}$ is a perfect tree, and the inclusion path and its verifier coincide with the Crypto Guide’s Definition “Authentication path” and Definition “Path verification” (§“Authentication paths and membership proofs”) at index $j-1$ , with the bits $b_{t}$ fixed by $j$ instead of carried in the path.

Theorem 3.14 (Prefix roots from one path).

For $1\leq j\leq n$ , from $x_{j}$ and the inclusion path of leaf $j$ in $M_{n}$ a verifier computes $\mathsf{rt}_{j}$ and, for $j\geq 2$ , $\mathsf{rt}_{j-1}$ , the roots of the ranges over $(x_{1},\dots,x_{j})$ and $(x_{1},\dots,x_{j-1})$ .

Proof.

For $\mathsf{rt}_{j}$ , by induction on $n$ , following ePrint 2019/226, Theorem 7, with siblings bottom-up. If $j=n$ , $\mathsf{rt}_{j}=\mathsf{rt}_{n}$ is the recomputed root $y_{m}$ . Otherwise $n>1$ ; let $2^{i}$ be the largest power of two strictly below $n$ , so that the root’s children are $M_{2^{i}}$ and a range over $n-2^{i}$ values.

1.

If $j=2^{i}$ , $\mathsf{rt}_{j}$ is the value of the root’s left child, which is $y_{m-1}$ .
2.

If $j<2^{i}$ , the path without its top sibling is the inclusion path of leaf $j$ in the left child $M_{2^{i}}$ , and the hypothesis applies.
3.

If $2^{i}<j<n$ , then $j-1\geq 2^{i}$ and $j<2^{i+1}$ , so $2^{i}$ is also the largest power of two strictly below $j$ . The top sibling is $P$ , the value of $M_{2^{i}}$ , and the path without it is the inclusion path of leaf $j-2^{i}$ in the right child; by hypothesis it yields the root $r^{\prime}$ over $(x_{2^{i}+1},\dots,x_{j})$ , and $\mathsf{rt}_{j}=H(P\,\|\,r^{\prime})$ by Definition 3.1.

For $\mathsf{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. □

Lemma 3.15 (Left siblings cover the prefix).

Let $b\in\{R,L\}$ , $1\leq j\leq n$ , and consider the inclusion path of leaf $j$ in $M^{b}_{n}$ . Its left siblings are subtrees whose leaf runs partition $\{1,\dots,j-1\}$ , higher siblings covering earlier leaves; its right siblings cover $\{j+1,\dots,n\}$ and enter none of the folds below. Let $j\geq 2$ and let leaf $j$ lie in peak $P_{i}$ .

1.

Under $\mathrm{Bag}_{R}$ the left siblings, from the top down, are the peaks of $(x_{1},\dots,x_{j-1})$ . The bottom-up fold (set $r$ to the lowest left sibling, then $r\leftarrow H(\pi\,\|\,r)$ for each further left sibling $\pi$ upwards) yields $\mathsf{rt}_{j-1}$ ; started instead from $r=x_{j}$ and applied to every left sibling, it yields $\mathsf{rt}_{j}$ .
2.

Under $\mathrm{Bag}_{L}$ , for $i\geq 2$ the topmost left sibling is $\mathrm{Bag}_{L}(P_{1},\dots,P_{i-1})$ and the others lie in $P_{i}$ , with sizes the terms of the binary expansion of $j-1-s_{i}$ ; for $i=1$ all left siblings lie in $P_{1}$ . The top-down fold (set $r$ to the topmost left sibling, then $r\leftarrow H(r\,\|\,\pi)$ for each further left sibling $\pi$ downwards) yields $\mathsf{rt}^{L}_{j-1}$ .

Proof.

A leaf $l<j$ leaves the path of leaf $j$ at their lowest common ancestor, in whose left child $l$ lies; that left child is a left sibling on the path. Distinct ancestors give disjoint runs, higher ancestors earlier runs. The same argument for $l>j$ gives the right siblings. Inside a perfect subtree the left siblings of the leaf at offset $o$ from its first leaf are perfect subtrees whose sizes are the terms of the binary expansion of $o$ , largest highest.

Leaf $j$ lies at offset $o=j-1-s_{i}$ in $P_{i}$ , and $j-1=s_{i}+o$ , so the peaks of $(x_{1},\dots,x_{j-1})$ are $P_{1},\dots,P_{i-1}$ followed by the left siblings inside $P_{i}$ , top-down. Under $R$ the siblings $P_{i-1},\dots,P_{1}$ lie above $P_{i}$ as left children of bagging nodes (proof of Lemma 3.7); the bottom-up fold is then the right fold of the peaks of $(x_{1},\dots,x_{j-1})$ , which is $\mathsf{rt}_{j-1}$ by Proposition 3.6. Started from $x_{j}$ , it is the right fold of those peaks followed by $x_{j}$ . The largest power of two strictly below $j$ is the highest term of $j-1$ , the size of the first of these peaks, and the recursion of Definition 3.1 on $j$ splits off the peaks of $j-1$ in turn and ends at the single leaf $x_{j}$ ; this fold is therefore $\mathsf{rt}_{j}$ . Under $L$ with $i\geq 2$ the root of $P_{i}$ is the right child of the bagging node $H(\mathrm{Bag}_{L}(P_{1},\dots,P_{i-1})\,\|\,P_{i})$ , and every higher node on the path is a left child; the top-down fold is the left fold of the peaks of $(x_{1},\dots,x_{j-1})$ . For $i=1$ the root of $P_{1}$ is a left child and every higher node on the path too. □

Construction 3.16 (Prefix root).

Procedure $\mathrm{PrefixRoot}_{b}(n,j,\pi)$ takes $b\in\{R,L\}$ , $2\leq j\leq n$ and a sequence $\pi$ of $\kappa$ -bit values with $|\pi|=\mathrm{depth}_{b}(n,j)$ , with sides $\sigma_{t}$ as in Definition 3.13. It selects the $\pi_{t}$ with $\sigma_{t}=\text{left}$ and outputs their bottom-up fold for $b=R$ and their top-down fold for $b=L$ (Lemma 3.15).

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.

Theorem 3.17 (Position binding).

Let $b\in\{R,L\}$ , $n\geq 1$ and $1\leq j\leq n$ . From any $\mathsf{rt}\in\{0,1\}^{\kappa}$ , chosen by the adversary, and two pairs $(x,\pi)\neq(x^{\prime},\pi^{\prime})$ both accepted by $\mathrm{Verify}_{b}(\mathsf{rt},n,j,\cdot,\cdot)$ , a collision of $H$ is computed with at most $2\,\mathrm{depth}_{b}(n,j)$ evaluations of $H$ . In particular $x\neq x^{\prime}$ yields a collision, and the siblings of an accepted path and every value it recomputes are functions of $(\mathsf{rt},b,n,j)$ , barring a collision.

Proof.

Both chains $y_{0},\dots,y_{m}$ and $y^{\prime}_{0},\dots,y^{\prime}_{m}$ of Definition 3.13 have the length $m=\mathrm{depth}_{b}(n,j)$ and the sides fixed by $(b,n,j)$ , and $y_{m}=y^{\prime}_{m}=\mathsf{rt}$ . Since $(x,\pi)\neq(x^{\prime},\pi^{\prime})$ , some step has differing inputs; let $t$ be the highest step with $(y_{t-1},\pi_{t})\neq(y^{\prime}_{t-1},\pi^{\prime}_{t})$ . Then $y_{t}=y^{\prime}_{t}$ : for $t=m$ both equal $\mathsf{rt}$ , and for $t<m$ the inputs of step $t+1$ agree. The two $2\kappa$ -bit inputs of step $t$ place their operands on the same sides and differ, and $H$ maps both to $y_{t}$ : a collision. For $n=1$ the path is empty and $\mathrm{Verify}_{b}$ accepts only $x=\mathsf{rt}$ , so no two distinct pairs are accepted. The extractor is deterministic and the reduction tight in the sense of the Crypto Guide, §“Reductions”; it is the first-level-of-agreement argument of the Crypto Guide, Proposition “Binding of the root” (§“Binary Merkle trees”) and §“Soundness: forging a path implies a collision”. □

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.

Corollary 3.18 (Prefix binding and root sensitivity).

Let $b\in\{R,L\}$ and $1\leq j\leq n$ .

1.

If $\mathsf{rt}=\mathsf{rt}^{b}_{n}$ over $(x_{1},\dots,x_{n})$ and $\mathrm{Verify}_{b}$ accepts $(x,\pi)$ at position $j$ , then $x=x_{j}$ and, for $j\geq 2$ , $\mathrm{PrefixRoot}_{b}(n,j,\pi)=\mathsf{rt}^{b}_{j-1}$ over $(x_{1},\dots,x_{j-1})$ , barring a collision: one accepted path binds $x_{1},\dots,x_{j}$ as a prefix of the committed sequence.
2.

If $(x^{\prime}_{1},\dots,x^{\prime}_{m})$ differs from $(x_{1},\dots,x_{m})$ at some $i\leq m$ , then $\mathsf{rt}^{b}_{m}(x^{\prime})\neq\mathsf{rt}^{b}_{m}(x)$ , barring a collision: changing $x_{i}$ changes every root $\mathsf{rt}^{b}_{m}$ with $m\geq i$ .

When $x_{i}$ is the hash of block $i$ , binding the blocks themselves requires in addition collision resistance of that hash.

Proof.

(1) The honest pair $(x_{j},\pi^{*})$ is accepted. By Theorem 3.17 the pairs $(x,\pi)$ and $(x_{j},\pi^{*})$ are equal barring a collision, so $x=x_{j}$ and the fold of Construction 3.16 on $\pi$ is the fold on $\pi^{*}$ , which is $\mathsf{rt}^{b}_{j-1}$ by Lemma 3.15. (2) The two trees have the same shape $M^{b}_{m}$ . The honest paths of leaf $i$ in both are accepted against the common root, with $x_{i}\neq x^{\prime}_{i}$ ; Theorem 3.17 yields a collision. □

Part (1) is ePrint 2019/226, Corollary 3, and part (2) its Corollary 4, stated for both bagging orders and with the collision named.

3.5 Aggregating ranges

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).

Definition 3.19 (Aggregating range).

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:

1.

a set of node tuples $v=(v.\mathsf{h},v.f_{1},\dots,v.f_{r})$ with $v.\mathsf{h}\in\{0,1\}^{\kappa}$ ;
2.

a serialisation $\mathrm{ser}$ from tuples to bit strings that is injective and prefix-free, no value of $\mathrm{ser}$ being a proper prefix of another, so that $\mathrm{ser}(\ell)\,\|\,\mathrm{ser}(r)$ determines the pair $(\ell,r)$ ;
3.

a leaf map from a leaf’s data to its tuple;
4.

for each field $f_{i}$ one rule: inherit from the left child, inherit from the right child, or sum, in $\mathbb{Z}$ or in $\mathbb{Z}/2^{256}\mathbb{Z}$ ;
5.

the parent map $\mathrm{par}(\ell,r)$ , whose hash field is $H(\mathrm{ser}(\ell)\,\|\,\mathrm{ser}(r))$ , over the children’s full serialisations, and whose other fields follow the rules.

A labelling of the shape $M^{b}_{n}$ with leaf tuples at the leaves is consistent when every internal node is $\mathrm{par}$ of its children; its root is the root’s tuple. Inclusion paths and $\mathrm{Verify}_{b}$ are those of Definition 3.13 with tuples in place of values and $\mathrm{par}$ in place of $H(\cdot\,\|\,\cdot)$ ; $\mathrm{Verify}_{b}$ accepts if and only if the recomputed root tuple equals the given one.

A serialisation of fixed width is prefix-free. Injectivity alone does not suffice: with $\mathrm{ser}(x)=0$ , $\mathrm{ser}(y)=01$ and $\mathrm{ser}(z)=10$ , the pairs $(x,z)$ and $(y,x)$ have the same concatenation $010$ .

Lemma 3.20 (Aggregate binding).

Let $\mathrm{ser}$ be injective and prefix-free, $b\in\{R,L\}$ and $n\geq 1$ .

1.

From two consistent labellings of $M^{b}_{n}$ 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.
2.

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.
3.

For $2\leq j\leq n$ and the inclusion path of leaf $j$ in a consistent labelling, the folds of Lemma 3.15 run with $\mathrm{par}$ in place of $H(\cdot\,\|\,\cdot)$ yield the root tuple of the consistent labelling of $M^{b}_{j-1}$ over the first $j-1$ leaf tuples.

Proof.

Unique decoding: if $\mathrm{ser}(\ell)\,\|\,\mathrm{ser}(r)=\mathrm{ser}(\ell^{\prime})\,\|\,% \mathrm{ser}(r^{\prime})$ , one of $\mathrm{ser}(\ell)$ , $\mathrm{ser}(\ell^{\prime})$ is a prefix of the other, hence they are equal, and $\ell=\ell^{\prime}$ by injectivity; then $\mathrm{ser}(r)=\mathrm{ser}(r^{\prime})$ and $r=r^{\prime}$ .

(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 $\mathrm{par}$ . By Lemma 3.15 the left siblings are, under $R$ , the peak tuples of the consistent labelling over the first $j-1$ leaves, and so are they under $L$ with $i\leq 2$ . Under $L$ with $i\geq 3$ , the topmost is the tuple of the bagging node $\mathrm{Bag}_{L}(P_{1},\dots,P_{i-1})$ of that labelling, and the others are its peak tuples inside $P_{i}$ . The folds of that lemma, run with $\mathrm{par}$ , therefore yield the root tuple of $M^{b}_{j-1}$ . The engine of (1) and (2) is the Crypto Guide, Proposition “Binding of the root” (§“Binary Merkle trees”). □

Lemma 3.21 (Cumulative-weight interval of a leaf).

Let $\mathrm{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$ .

1.

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 $[W,W+w_{j})$ of leaf $j$ .
2.

Meaning, for the path of a consistent labelling: $W=\sum_{i<j}w_{i}$ , under either bagging order. For a sum taken modulo $2^{256}$ , this holds as an identity of integers when the sum of $w$ over all $n$ leaves is below $2^{256}$ .

Part (2) is not claimed for a root chosen by the adversary, whose siblings off the path are never recomputed from their children.

Proof.

(1) Lemma 3.20(2). (2) In a consistent labelling the summed field of a node is the sum over its leaves, by induction on height; with the total below $2^{256}$ no reduction occurs. The left siblings partition $\{1,\dots,j-1\}$ by Lemma 3.15, a property of any binary tree. □

Two instances follow. The difficulty Merkle mountain range of ePrint 2019/226, whose nodes aggregate difficulty and time, is Definition 5.6 in §5.3. The node vector of ZIP 221, whose nodes aggregate work, heights and pool data, is Definition 6.3 in §6.3.