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

5 The FlyClient protocol

This section constructs the protocol of ePrint 2019/226 in the model of §4, each object before its first use: the header chain commitment and the check applied to one sampled block, two lemmas on forks, the difficulty Merkle mountain range with its node checks, the sampling distribution, the interactive and the non-interactive protocol, the security theorem with its hypotheses and status, and verification after acceptance. Throughout, $H\colon\{0,1\}^{*}\to\{0,1\}^{\kappa}$ is the hash function of §3, which is also the proof-of-work oracle of Definition 4.1; $\log$ is the natural logarithm and $\mathrm{Adv}^{\mathrm{col}}_{H}(\mathcal{B})$ the collision advantage of an algorithm $\mathcal{B}$ (Crypto Guide, Definition “Collision resistance”, §“Security notions: preimage, second-preimage, and collision resistance”), the security parameter left implicit.

5.1 Header chain commitments and per-sample checks

Blocks are written $B_{0}$ (the genesis block), $B_{1}$ , $B_{2}$ , …, with $B_{\eta}$ the block at height $\eta$ and $\mathrm{hdr}(B)$ the header of $B$ .

Construction 5.1 (Header chain commitment).

Fix an aggregating range (Definition 3.19) under the bagging $\mathrm{Bag}_{R}$ (Definition 3.5) whose leaf map sends a block $B$ to a node tuple $\mathrm{leaf}(B)$ with hash field $\mathrm{leaf}(B).\mathsf{h}=H(\mathrm{hdr}(B))$ . Leaf $j$ of every range is $\mathrm{leaf}(B_{j-1})$ , so leaf $j$ is the block at height $j-1$ . For every height $\eta\geq 1$ let $M_{\eta}$ be the range over the $\eta$ leaves $\mathrm{leaf}(B_{0}),\dots,\mathrm{leaf}(B_{\eta-1})$ and $\mathsf{rt}_{\eta}$ its root tuple. The producer of $B_{\eta}$ obtains $M_{\eta}$ from $M_{\eta-1}$ by Construction 3.10 applied to $\mathrm{leaf}(B_{\eta-1})$ , with the parent map $\mathrm{par}$ in place of $H(\cdot\,\|\,\cdot)$ ( $M_{1}$ is the single leaf $\mathrm{leaf}(B_{0})$ ), and records the hash field $\mathsf{rt}_{\eta}.\mathsf{h}$ in the header of $B_{\eta}$ . The genesis header records no root. A full node accepts $B_{\eta}$ only if its header records $\mathsf{rt}_{\eta}.\mathsf{h}$ .

The construction has the following invariant: the header of $B_{\eta}$ commits, through one root, to exactly the blocks strictly before it, and a head $B_{\eta}$ commits to $n=\eta$ leaves, $n$ denoting this leaf count below. The root’s fields other than its hash field are not recorded; a verifier recomputes the root tuple from its two children, which the hash field binds (Lemma 3.20). The range of ePrint 2019/226, Section 2, is the instance whose tuples carry the hash field alone; the paper’s difficulty Merkle mountain range is the instance of Definition 5.6. The one further header field is the paper’s only consensus change (Section 4.2). The paper indexes the committing block and its range inconsistently; the invariant fixes one indexing, and the paper’s is not carried. In the classes of Definition 1.3, this commitment from the genesis block is the paper’s design and no Zcash rule specifies it; the specified commitment is the epoch-scoped instance of “The chain-history commitment” (§6), from which nothing is concluded here.

One sample at index $j\in\{1,\dots,n\}$ against a head $B_{\eta}$ must establish three facts: that the sampled block is leaf $j$ under the head’s root, that the leaf’s tuple is the one its header determines, and that the root in the sampled header commits to exactly the first $j-1$ of the same leaves.

Construction 5.2 (Per-sample check).

The inputs are a root tuple $\mathsf{rt}$ with leaf count $n$ and an index $1\leq j\leq n$ . The prover sends the header $\mathrm{hdr}_{j}$ of the block at height $j-1$ , the tuple $v_{j}$ of leaf $j$ , and its inclusion path $\pi$ in $M_{n}$ (Definition 3.13) with every sibling as a full tuple. The verifier performs the following checks.

(a)

Leaf: $v_{j}.\mathsf{h}=H(\mathrm{hdr}_{j})$ , and every other field of $v_{j}$ that the leaf map determines from the header alone equals its value computed from $\mathrm{hdr}_{j}$ .
(b)

Inclusion: $\mathrm{Verify}_{R}(\mathsf{rt},n,j,v_{j},\pi)$ of Definition 3.13, in the tuple form of Definition 3.19, accepts; the side of each sibling and the path length $\mathrm{depth}_{R}(n,j)$ are fixed by $(j,n)$ .
(c)

Prefix: for $j\geq 2$ , the hash field of $\mathrm{PrefixRoot}_{R}(n,j,\pi)$ (Construction 3.16), run with $\mathrm{par}$ in place of $H(\cdot\,\|\,\cdot)$ , equals the root recorded in $\mathrm{hdr}_{j}$ ; for $j=1$ , $\mathrm{hdr}_{1}$ equals the genesis header, which the verifier knows.
(d)

Proof of work: $\mathrm{hdr}_{j}$ carries a valid proof of work at the target $T$ it declares, $H(\mathrm{hdr}_{j})<T$ (Definition 4.1).

Any failure rejects.

ePrint 2019/226, Algorithm 2, lists checks (b) and (c); checks (a) and (d) come from its Definition 5 and Section 6.1. Check (b) uses the length rule of Definition 3.13, not that of the paper’s Algorithm 4.

Proposition 5.3 (Soundness of the per-sample check).

Let $\mathsf{rt}$ be any root tuple, possibly chosen by the adversary, with leaf count $n$ , and let $1\leq j\leq n$ . There is an explicit reduction $\mathcal{B}$ such that, for every adversary $\mathcal{A}$ that outputs samples at position $j$ against $(\mathsf{rt},n)$ , the probability that every sample passes Construction 5.2 while one of the following fails is at most $\mathrm{Adv}^{\mathrm{col}}_{H}(\mathcal{B})$ :

(i)

any two passing samples at position $j$ carry the same leaf tuple and the same header, so the header is bound to position $j$ of the sequence that $\mathsf{rt}$ commits;
(ii)

every header-determined field of that leaf tuple is its value computed from that header;
(iii)

for $j\geq 2$ , the root recorded in that header is the hash field of a prefix-root tuple that is the same for every passing sample at $j$ , hence a function of $(\mathsf{rt},n,j)$ ; if $\mathsf{rt}$ is the root of a consistent labelling over $v_{1},\dots,v_{n}$ , it is the root of the consistent labelling over $v_{1},\dots,v_{j-1}$ .

Proof.

The reduction $\mathcal{B}$ runs $\mathcal{A}$ and inspects two passing samples $(\mathrm{hdr},v,\pi)$ and $(\mathrm{hdr}^{\prime},v^{\prime},\pi^{\prime})$ at position $j$ . (i) If $(v,\pi)\neq(v^{\prime},\pi^{\prime})$ , Lemma 3.20(2), the tuple form of Theorem 3.17 under the prefix-free serialisation of Definition 3.19, yields a collision at the highest step whose inputs differ. If $v=v^{\prime}$ but $\mathrm{hdr}\neq\mathrm{hdr}^{\prime}$ , check (a) gives $H(\mathrm{hdr})=v.\mathsf{h}=H(\mathrm{hdr}^{\prime})$ , a collision. (ii) is check (a). (iii) Barring the collisions of (i), $\pi=\pi^{\prime}$ , so the fold of check (c) over the left siblings of $\pi$ is the same tuple for every passing sample, and check (c) equates its hash field with the recorded root. For a consistent labelling, Lemma 3.15 with Lemma 3.20(3) identifies the fold with the root over $v_{1},\dots,v_{j-1}$ , as Theorem 3.14 does for plain values. □

5.2 Forks against a committed chain

A claimed chain $C$ forks from the honest chain at its fork point, the last common block (§4.3). Its head records the root of a range over the leaf tuples $v^{\prime}_{1},\dots,v^{\prime}_{n}$ of its blocks, and $C$ places a block $B$ at leaf position $j$ when $v^{\prime}_{j}.\mathsf{h}=H(\mathrm{hdr}(B))$ .

Lemma 5.4 (Honest blocks after the fork point).

Let the head of $C$ record the hash field of the root of a consistent labelling over $v^{\prime}_{1},\dots,v^{\prime}_{n}$ . Let $B$ be a block of the honest chain at height $\eta$ above the fork point, whose header records the hash field of the honest root over the honest leaf tuples $v_{1},\dots,v_{\eta}$ , and let $C$ place $B$ at leaf position $j\geq 2$ . Suppose that

1.

the sequences $(v^{\prime}_{1}.\mathsf{h},\dots,v^{\prime}_{j-1}.\mathsf{h})$ and $(v_{1}.\mathsf{h},\dots,v_{\eta}.\mathsf{h})$ differ, possibly in length; and
2.

no block header equals $\mathrm{ser}(\ell)\,\|\,\mathrm{ser}(r)$ for node tuples $\ell,r$ (leaf–internal separation).

Then from a sample of $B$ that passes Construction 5.2 against the head of $C$ an explicit reduction computes a collision of $H$ , or finds a leaf position $i<j$ of $C$ whose tuple $v^{\prime}_{i}$ has hash field $H(\mathrm{ser}(\ell)\,\|\,\mathrm{ser}(r))$ for node tuples $\ell,r$ . A sample at $i$ passes check (a) only on a header hashing to that value, which by hypothesis 2 is a collision. Consequently, barring a collision, either a sample on $B$ rejects or leaf $i$ does, and that block or leaf belongs, in the analysis of §5.4, to the invalid set of the fork.

Proof.

By Proposition 5.3(iii) a passing sample makes the root recorded in $\mathrm{hdr}(B)$ equal to the hash field of the root of the consistent labelling of $M_{j-1}$ over $v^{\prime}_{1},\dots,v^{\prime}_{j-1}$ . That value is also the hash field of the honest root of $M_{\eta}$ . Descend both labellings from their roots, keeping a pair of nodes with equal hash fields whose leaf subsequences differ in their hash fields. At a pair of internal nodes, equal hash fields $H(\mathrm{ser}(\ell)\,\|\,\mathrm{ser}(r))=H(\mathrm{ser}(\ell^{\prime})\,\|\,% \mathrm{ser}(r^{\prime}))$ with $(\ell,r)\neq(\ell^{\prime},r^{\prime})$ are a collision by unique decoding (proof of Lemma 3.20); otherwise the children agree as tuples, the leaf subsequences of the left children or of the right children differ, and the descent continues there. Two leaves with equal hash fields do not have different hash-field sequences, so the descent ends at a leaf opposite an internal node. If the leaf is honest, its hash field is $H(\mathrm{hdr})$ for the header $\mathrm{hdr}$ of an honest block, and $H(\mathrm{hdr})=H(\mathrm{ser}(\ell)\,\|\,\mathrm{ser}(r))$ with distinct inputs by hypothesis 2 is a collision. If the leaf is a leaf $v^{\prime}_{i}$ of $C$ , $i\leq j-1$ , opposite an honest internal node with children $\ell,r$ , then $v^{\prime}_{i}.\mathsf{h}=H(\mathrm{ser}(\ell)\,\|\,\mathrm{ser}(r))$ , which is the second outcome. The descent takes at most $\max(\lceil\log_{2}(j-1)\rceil,\lceil\log_{2}\eta\rceil)$ steps. □

The lemma is ePrint 2019/226, Section 5.1 with Corollary 4 (here Corollary 3.18), extended to a block placed at a height other than its own, where the two roots have different leaf counts and hypothesis 2 is needed. It concerns honest blocks placed after the fork point and states nothing about blocks the adversary mines; those are the subject of the next lemma.

Lemma 5.5 (No reuse of work across the fork point).

Model $H$ as a random oracle with $\kappa$ -bit outputs (Crypto Guide, §“The random oracle model”), and let at most $q_{H}$ queries to $H$ be made in the experiment, by $\mathcal{A}$ , by the verification of its output, and by the computation of the prefix root at every position of the output fork after its fork point. Call a query $H(x)$ reused if $x$ is the header of a block $B$ of the output fork after its fork point, $x$ records the hash field of the prefix root of the fork at $B$ ’s position, and the query precedes the first query whose answer is that recorded value. Then

\mathrm{Pr}\bigl{[}\mathcal{A}\text{ outputs a fork with a block mined by a % reused query}\bigr{]}\leq q_{H}^{2}\,2^{-\kappa}+\mathrm{Adv}^{\mathrm{col}}_{% H}(\mathcal{B})

for an explicit reduction $\mathcal{B}$ . Consequently, except with that probability, only adversarial work done after the fork’s prefix is fixed counts against the honest chain.

Proof.

By Construction 5.1 the root recorded in a header after the fork point is the hash field of a tuple over the fork’s prefix; by Proposition 5.3(iii) that tuple is a function of the fork’s root, position and leaf count, barring a collision, which accounts for the term $\mathrm{Adv}^{\mathrm{col}}_{H}(\mathcal{B})$ . Its hash field is the answer of a query, made at the latest during that computation. A reused query fixes a recorded value $r$ before any query has answer $r$ . The first query with answer $r$ has an input not queried before, since a repeated input returns an earlier answer; its answer is uniform on $\{0,1\}^{\kappa}$ and independent of all earlier queries, so it equals one of the at most $q_{H}$ values recorded in earlier query inputs with probability at most $q_{H}\,2^{-\kappa}$ . The union bound over the at most $q_{H}$ queries (Math Guide, §“The union bound and a birthday calculation”) gives $q_{H}^{2}\,2^{-\kappa}$ . □

The paper asserts the statement in one sentence (ePrint 2019/226, Section 3.2); the proof above is this volume’s. The bound is in the number of oracle queries, not in the mining rate.

5.3 The difficulty Merkle mountain range

A sampling verifier sees few difficulty transitions, so the transitions it does not see must be constrained by committed aggregates.

Definition 5.6 (Difficulty Merkle mountain range).

The difficulty Merkle mountain range (difficulty MMR) is the instance of Definition 3.19 whose node $v$ is the tuple

v=(v.\mathsf{h},\,v.\mathsf{w},\,v.\mathsf{t},\,v.\mathsf{D}_{\mathsf{start}},% \,v.\mathsf{D}_{\mathsf{next}},\,v.\mathsf{n}),

with a serialisation that concatenates injective fixed-width encodings of the six fields, hence prefix-free. For a block $B$ whose header declares target $T$ , the leaf map sets

•

$v.\mathsf{h}=H(\mathrm{hdr}(B))$ ;
•

$v.\mathsf{w}=v.\mathsf{D}_{\mathsf{start}}=D(T)$ , the difficulty level of $T$ (Definition 4.2);
•

$v.\mathsf{t}$ the number of rounds between the round recorded by the predecessor of $B$ and the round recorded by $B$ ( $0$ for the genesis block);
•

$v.\mathsf{D}_{\mathsf{next}}$ the level of the target that Definition 4.5 assigns to the block after $B$ ;
•

$v.\mathsf{n}=1$ .

The parent of $\ell$ and $r$ has hash field $H(\mathrm{ser}(\ell)\,\|\,\mathrm{ser}(r))$ , over both children’s complete tuples; its fields $\mathsf{w}$ , $\mathsf{t}$ and $\mathsf{n}$ are the sums of the children’s; it inherits $\mathsf{D}_{\mathsf{start}}$ from $\ell$ and $\mathsf{D}_{\mathsf{next}}$ from $r$ .

The fields $\mathsf{h}$ , $\mathsf{w}$ , $\mathsf{D}_{\mathsf{start}}$ and $\mathsf{n}$ of a leaf are determined by its header alone and are checked by item (a) of Construction 5.2; the fields $\mathsf{t}$ and $\mathsf{D}_{\mathsf{next}}$ depend on neighbouring blocks and are constrained only by Construction 5.8. The definition makes three precisions against ePrint 2019/226, Definition 7. The paper writes $H(lc,rc)$ without fixing its input; hashing the children’s hash fields alone would leave their other fields unbound. The paper’s “timestamp” $\mathsf{t}$ is an elapsed time, and its “targets” $\mathsf{w}$ , $\mathsf{D}_{\mathsf{start}}$ and $\mathsf{D}_{\mathsf{next}}$ are difficulty levels. The paper’s checks name fields $t_{\mathrm{start}}$ , $t_{\mathrm{end}}$ and $D_{\mathrm{end}}$ that its Definition 7 never declares; the declared aggregate $\mathsf{t}$ suffices for every timing check below, so the field set is the declared one. The paper’s data field is omitted, since no check uses it. No encoding of the fields is fixed by the paper.

Lemma 5.7 (Weight binding for the difficulty MMR).

Let a sample at leaf $j$ pass Construction 5.2 against a root $\mathsf{rt}$ with leaf count $n$ , the shape being fixed by $n$ under $\mathrm{Bag}_{R}$ . Except with probability $\mathrm{Adv}^{\mathrm{col}}_{H}(\mathcal{B})$ for an explicit reduction $\mathcal{B}$ :

1.

the leaf weight $v_{j}.\mathsf{w}$ is the difficulty level $D(T)$ of the target $T$ at which the header’s proof of work is valid;
2.

the interval $[W,W+v_{j}.\mathsf{w})$ , with $W$ the sum of the fields $\mathsf{w}$ of the left siblings on the path, is a function of $(\mathsf{rt},n,j)$ .

Proof.

(1) Check (a) sets $v_{j}.\mathsf{w}=D(T)$ for the declared target $T$ , check (d) validates the proof of work at that $T$ , and Proposition 5.3(i) and (ii) bind the header and its fields to position $j$ . (2) Lemma 3.21(1). Whether $W$ equals the true prefix weight is part (2) of that lemma, which holds for a consistent labelling only and is not claimed here. □

Construction 5.8 (Node checks).

Assume, with ePrint 2019/226, Section 6.1, that the retarget-epoch length $E$ of Definition 4.5 and the leaf count $n$ are powers of two, so that the retarget epochs are the perfect subtrees of altitude $\log_{2}E$ . For every parent $p$ on a sample’s path, with children $\ell$ and $r$ (one of them a carried sibling), the verifier checks:

1.

$p=\mathrm{par}(\ell,r)$ under Definition 5.6;
2.

$\ell.\mathsf{D}_{\mathsf{next}}=r.\mathsf{D}_{\mathsf{start}}$ ;
3.
for each of $\ell$ and $r$ , internal consistency:
1. (a)
  
  a node $v$ of altitude below $\log_{2}E$ lies inside one retarget epoch and has $v.\mathsf{w}=v.\mathsf{n}\cdot v.\mathsf{D}_{\mathsf{start}}$ , and $v.\mathsf{D}_{\mathsf{next}}=v.\mathsf{D}_{\mathsf{start}}$ unless $v$ contains the last block of its epoch;
2. (b)
  
  a node $v$ of altitude $\log_{2}E$ is one retarget epoch, has $v.\mathsf{w}=E\cdot v.\mathsf{D}_{\mathsf{start}}$ , and $v.\mathsf{D}_{\mathsf{next}}=D\bigl{(}\mathrm{Retarget}(2^{\kappa}/v.\mathsf{D% }_{\mathsf{start}},v.\mathsf{t})\bigr{)}$ , the level that Definition 4.5 assigns after an epoch of $v.\mathsf{t}$ rounds at level $v.\mathsf{D}_{\mathsf{start}}$ ;
3. (c)
  
  a node $v$ above altitude $\log_{2}E$ is feasible: its $(v.\mathsf{t},v.\mathsf{w},v.\mathsf{D}_{\mathsf{start}},v.\mathsf{D}_{\mathsf% {next}},v.\mathsf{n})$ is attained by some sequence of clamped retargets (Propositions 5.9 and 5.10).

At the sampled leaf the checks (a) and (d) of Construction 5.2 apply; their effect on $\mathsf{w}$ and $\mathsf{D}_{\mathsf{start}}$ is Lemma 5.7. Weight-position check: when a leaf is requested at a point $x$ of cumulative weight, $0\leq x<\mathsf{rt}.\mathsf{w}$ , the returned leaf $j$ satisfies $W\leq x<W+v_{j}.\mathsf{w}$ , with $W$ the sum of the fields $\mathsf{w}$ of the left siblings on its path; this interval is bound to $(\mathsf{rt},n,j)$ by Lemma 3.21(1). Any failure rejects.

The construction is ePrint 2019/226, Section 6.1 (“Difficulty MMR Verification”); the paper states the weight-position check only informally (Section 2).

Proposition 5.9 (Feasibility envelope).

Let consecutive retarget epochs $0,\dots,z-1$ have levels $D_{0}=\mathsf{D}_{\mathsf{start}},D_{1},\dots,D_{z-1}$ , and let $D_{z}=\mathsf{D}_{\mathsf{next}}=\tau^{y}\,\mathsf{D}_{\mathsf{start}}$ , where every retarget obeys the clamp of Definition 4.5, so that $D_{e+1}/D_{e}\in[1/\tau,\tau]$ . Then:

1.

$|y|\leq z$ and, for every $e$ ,

$\mathsf{D}_{\mathsf{start}}\max(\tau^{-e},\tau^{y-z+e})\leq D_{e}\leq\mathsf{D% }_{\mathsf{start}}\min(\tau^{e},\tau^{y+z-e});$
2.

for integer $y$ with $z-y$ even both envelopes are attained by clamped sequences, so the total weight $E\sum_{e<z}D_{e}$ is maximal when the difficulty is raised by $\tau$ per epoch and then lowered by $\tau$ per epoch to $\mathsf{D}_{\mathsf{next}}$ , and minimal when it is lowered first and then raised;
3.

an epoch at target $T$ that lowers the difficulty maximally (new target $\tau T$ ) lasts $\Delta\geq\tau E/f$ rounds, and one that raises it maximally (new target $T/\tau$ ) lasts $\Delta\leq E/(f\tau)$ rounds.

Proof.

(1) Since $|\log_{\tau}D_{e+1}-\log_{\tau}D_{e}|\leq 1$ , induction on $e$ from epoch $0$ gives $|\log_{\tau}(D_{e}/\mathsf{D}_{\mathsf{start}})|\leq e$ , and from epoch $z$ gives $|\log_{\tau}(D_{e}/\mathsf{D}_{\mathsf{start}})-y|\leq z-e$ ; at $e=0$ the second bound is $|y|\leq z$ . (2) For $z-y$ even the pointwise upper envelope has exponent steps $+1$ up to $e=(y+z)/2$ and $-1$ after, and the lower envelope steps $-1$ up to $e=(z-y)/2$ and $+1$ after; both are clamped, and the weight is increasing in each $D_{e}$ . (3) The raw retarget is $T\Delta f/E$ (§4.2); the clamp is reached from above when $T\Delta f/E\geq\tau T$ and from below when $T\Delta f/E\leq T/\tau$ . A script checks the sums against brute force over exponent sequences, and the two thresholds. □

Proposition 5.10 (Feasibility bounds).

In the setting of Proposition 5.9, let $y$ be an integer with $y\geq 0$ and $z-y$ even. If a node spanning the $z$ epochs is attained by a clamped sequence, then

1.

$y\leq z$ (Proposition 5.9(1));
2.

$\displaystyle\mathsf{w}\leq E\,\mathsf{D}_{\mathsf{start}}\,\frac{(\tau+1)\,% \tau^{(y+z)/2}-\tau^{1+y}-1}{\tau-1}$ ;
3.

$\displaystyle\mathsf{w}\geq E\,\mathsf{D}_{\mathsf{start}}\,\frac{\tau^{y}+% \tau-(\tau+1)\,\tau^{-(z-y)/2}}{\tau-1}$ ;
4.

if $y=z$ , then $\mathsf{t}\leq zE/(f\tau)$ .

Proof.

Bounds (2) and (3) are the geometric sums of the envelopes of Proposition 5.9(2); at $y=z$ both reduce to $(\tau^{z}-1)/(\tau-1)$ . For (4), $y=z$ forces a maximal raise in each of the $z$ epochs, each of at most $E/(f\tau)$ rounds by Proposition 5.9(3). A script confirms that the closed forms equal the brute-force extremes in all $123$ cases with $\tau\in\{2,4,3/2\}$ , $1\leq z\leq 11$ , $0\leq y\leq z$ and $z-y$ even; at $\tau=4$ , $y=0$ , $z=2$ they give $5$ and $5/4$ per unit of $E$ . □

The paper states these checks with $k$ and $n$ in place of $y$ and $z$ , which here are the catch parameter and the leaf count (ePrint 2019/226, Section 6.1, pp. 18–19). Three departures are made. The printed lower bound has exponent $(y+z)/2$ in place of $-(z-y)/2$ and is then negative, $-5$ against the corrected $5/4$ at $\tau=4$ , $y=0$ , $z=2$ . The printed bounds count one level per epoch, whereas the leaf rule $\mathsf{w}=\mathsf{D}_{\mathsf{start}}$ sums per block, so both scale by $E$ . The printed upper summation overcounts by $\tau^{z}$ at $y=z$ , where its closed form is right. The paper further requires that $\mathsf{t}$ cover the epochs in which the difficulty is lowered, without a formula, and calls the cases of non-integer and negative $y$ “similar” without stating them. The conditions above are necessary, not sufficient: the general feasibility predicate that item 3(c) of Construction 5.8 requires is not given by the paper.

Assumption 5.11 (Transition rewriting).

In the model of Definition 4.1, for every adversary $\mathcal{A}$ that with non-negligible probability $p$ outputs a chain $C$ accepted by the node checks on every sample, some of whose difficulty transitions violate Definition 4.5, there is an adversary $\mathcal{A}^{\prime}$ that makes the same number of oracle queries, respects the retarget rule, and with probability at least $p-\mathsf{negl}(\kappa)$ outputs a chain $C^{\prime}$ whose validly mined blocks occupy the same positions as those of $C$ .

The assumption is the statement of ePrint 2019/226, Lemma 4, taken as a hypothesis because its proof is a sketch. It handles subtrees whose aggregates are inconsistent with their children, which Lemma 3.21(2) does not cover. The paper’s proof strategy is as follows. Let $x^{\prime}$ be the highest node on a claimed path at which the node checks fail. Every path through $x^{\prime}$ , or carrying it as a sibling, rejects, so barring a collision every leaf of the subtree $M^{\prime}$ under the parent of $x^{\prime}$ is unsampleable without rejection. The adversary $\mathcal{A}^{\prime}$ replaces the transitions inside $M^{\prime}$ by clamped ones consistent with the aggregates $(\mathsf{w},\mathsf{t},\mathsf{D}_{\mathsf{start}},\mathsf{D}_{\mathsf{next}},% \mathsf{n})$ of the root of $M^{\prime}$ , which is possible because that node passes the feasibility check and the leaves of $M^{\prime}$ , being invalid, need no proof of work; this is repeated until no invalid transition remains. The paper writes “consistency with $x_{0}$ ” where the parent of $x^{\prime}$ is meant.

Remark 5.12 (Gaps in the rewriting argument).

(1) The feasibility step presumes a complete feasibility predicate, which the paper gives only in the simplified setting of Proposition 5.10. (2) Rewriting the leaves of $M^{\prime}$ changes every later root and hence every later header, so $\mathcal{A}^{\prime}$ must fix the rewrite before it mines the later valid blocks, and must mine them anew; the paper asserts without a simulation argument that this succeeds with probability at least $p-\mathsf{negl}(\kappa)$ . (3) “The same valid blocks” holds for positions, not for header contents. Assumption 5.11 is therefore the paper’s claim, not a result of this volume.

5.4 The sampling distribution

Uniform sampling fails on forks near the tip: almost every uniform sample lands before a late fork point, where the two chains agree. If the fork point were known, each sample after it would be invalid with probability at least $1-c$ under Assumption 4.8.

Construction 5.13 (Dyadic-suffix sampling).

At constant difficulty, over a claimed chain of $n$ blocks and with $u$ samples per interval, the verifier draws, for every integer $i$ with $0\leq i<\log_{2}n$ , $u$ samples uniformly and independently from the last $n/2^{i}$ blocks, and checks every one of the last $\min(L,u)$ blocks.

The samples do not depend on the prover’s answers, so the protocol is one-shot and public-coin (Crypto Guide, §“Interactive protocols, proofs, and arguments”). The construction is ePrint 2019/226, Section 5.3, with $u$ in place of the paper’s $k$ .

Lemma 5.14 (Dyadic miss probability).

Under Assumption 4.8, at constant difficulty, for every fork point $a$ and every fork from $a$ of more than $L$ blocks whose total work after $a$ is at least that of the honest chain, the probability that the $u\log_{2}n$ samples of Construction 5.13 include no invalid block of the fork is at most $((1+c)/2)^{u}$ , except with probability negligible in $\lambda$ .

Proof.

Let the fork point be $a$ and choose $i$ with $(2^{i}-1)n/2^{i}\leq a<(2^{i+1}-1)n/2^{i+1}$ . The interval of the last $n^{\prime}=n/2^{i}$ blocks then contains $a$ in its first half, so the fork length $l=n-a$ satisfies $l>n^{\prime}/2$ , and by Assumption 4.8, at constant difficulty, the interval holds at least $(1-c)l>(1-c)n^{\prime}/2$ invalid blocks. Each of its $u$ independent uniform samples misses them with probability at most $1-(1-c)/2=(1+c)/2$ , and the samples of the other intervals are discarded. A script checks the bound for $c\in\{0.25,0.5,0.9\}$ , $u\in\{1,5,20\}$ and intervals of $8$ , $64$ and $1{,}024$ blocks. □

The lemma is ePrint 2019/226, Lemma 2. A fork of at most $\min(L,u)$ blocks lies in the checked suffix. When $u<L$ , a fork of $l$ blocks with $u<l\leq L$ is covered by neither clause, since Assumption 4.8 does not constrain it; the construction is sound for $u\geq L$ , or with the last $L$ blocks checked in full.

Definition 5.15 (Continuum model and catch probability).

The claimed chain is the interval $[0,1]$ in relative cumulative work: a block whose cumulative-work interval is $[W,W+w)$ within total committed work $\omega$ occupies $[W/\omega,(W+w)/\omega)$ ; genesis is at $0$ and the head at $1$ . A fork point is a point $a\in[0,1)$ . By Assumption 4.8 in its operative form, the adversary designates an invalid set $S\subseteq[a,1]$ of Lebesgue measure at least $(1-c)(1-a)$ ; every such $S$ is admissible. A sampling density is a probability density $\varphi$ on $[0,1]$ (Math Guide, §“Beyond finite spaces: countable additivity, limits, and densities”). When a suffix $[1-\delta,1]$ is checked in full, a set $S$ that meets it in positive measure is caught with probability $1$ , and any other $S$ is caught by one draw with probability $\int_{S}\varphi$ . The single-draw catch probability at $a$ is the infimum $p_{\varphi}(a)$ of these probabilities over admissible $S$ . For $Q$ independent draws (Math Guide, §“Conditional probability and independence”) against a set $S$ fixed before the draws, all miss with probability $(1-\int_{S}\varphi)^{Q}\leq(1-p_{\varphi}(a))^{Q}$ . The design problem is to choose $\varphi$ to maximise $\min_{a}p_{\varphi}(a)$ .

Lemma 5.16 (Best response).

Let $\varphi$ be non-decreasing on an interval $[a,b]$ with $b\leq 1$ , and let $0\leq m\leq b-a$ . Among measurable $S\subseteq[a,b]$ of measure $m$ , the integral $\int_{S}\varphi$ is minimal for $S=[a,a+m]$ . Hence against a density non-decreasing on $[a,1-\delta]$ , with $[1-\delta,1]$ checked in full, an adversary forking at $a\leq 1-\delta/c$ places its valid weight last, and its invalid set is $[a,1-(1-a)c]$ .

Proof.

With $I=[a,a+m]$ , $\int_{S}\varphi-\int_{I}\varphi=\int_{S\setminus I}\varphi-\int_{I\setminus S}\varphi$ ; the two sets have equal measure, $S\setminus I$ lies right of $a+m$ and $I\setminus S$ left of it, and $\varphi$ is non-decreasing, so the difference is non-negative. A set meeting the suffix in positive measure is caught with certainty, so the adversary’s best set lies in $[a,1-\delta]$ and has the least admissible measure $(1-c)(1-a)$ ; it ends at $a+(1-c)(1-a)=1-(1-a)c\leq 1-\delta$ . □

Construction 5.17 (Indifference density).

Equal catch probability at every fork point, that is $\Phi(1-c(1-a))-\Phi(a)$ constant in $a$ for an antiderivative $\Phi$ of $\varphi$ , gives on differentiation

\varphi(a)=c\,\varphi\bigl{(}1-c(1-a)\bigr{)}.

The function $\varphi(\xi)=K/(1-\xi)$ solves it. With $K=(1-c)/c$ every invalid segment $[a,1-c(1-a)]$ has mass $(c-1)\log(c)/c$ , which is $\log 2\approx 0.693147$ at $c=1/2$ . The equation fixes $\varphi$ only up to a factor periodic in $\log(1-\xi)$ with period $\log(1/c)$ . The function is not integrable on $[0,1]$ , its mass on $[0,1-\epsilon]$ being $K\log(1/\epsilon)$ , so it is not a density there.

The segment mass is $K\bigl{(}\log(1-a)-\log(c(1-a))\bigr{)}=-K\log c$ ; a script checks it for $c\in\{0.3,0.5,0.9\}$ and $a\in\{0,0.2,0.7\}$ , and the divergence. The construction is ePrint 2019/226, Section 5.4, p. 16.

Construction 5.18 (FlyClient sampling density).

Fix $0<c<1$ and $\delta\in(0,c]$ ; the suffix $[1-\delta,1]$ is checked in full. The FlyClient sampling density is

g(\xi)=\begin{cases}\dfrac{1}{(\xi-1)\log\delta}&0\leq\xi\leq 1-\delta,\\[6.0% pt] 0&\text{otherwise},\end{cases}\qquad G(\xi)=\frac{\log(1-\xi)}{\log\delta}% \quad(0\leq\xi\leq 1-\delta).

Both factors of the denominator are negative, so $g>0$ on its support, and $g$ is increasing there; $G$ is its distribution function, with $G(1-\delta)=1$ . For $a\leq(c-\delta)/c$ the invalid segment $[a,1-(1-a)c]$ lies in $[0,1-\delta]$ and has catch probability

G\bigl{(}1-(1-a)c\bigr{)}-G(a)=\frac{\log c}{\log\delta},

which is $1/k$ at $\delta=c^{k}$ . For $a>(c-\delta)/c$ every admissible invalid set meets the checked suffix in positive measure, and the fork is caught with probability $1$ .

Normalisation, $G$ and the catch probability are direct integrations. For the last clause, $[a,1-\delta]$ has measure $1-\delta-a<(1-c)(1-a)$ exactly when $a>1-\delta/c=(c-\delta)/c$ . A script checks normalisation, $G$ and the catch probability $1/k$ for $c\in\{0.25,0.3,0.5,0.75,0.9\}$ and $2\leq k\leq 9$ . The density is ePrint 2019/226, Section 5.4, p. 16; Figure 3 shows it.

Refer to caption — Figure 3: The FlyClient sampling density $g$ of Construction 5.18 for $c=1/2$ and $k=4$ , so $\delta=1/16$ and $g(\xi)=1/((1-\xi)\log 16)$ on $[0,15/16]$ . The amber strip is the suffix $[15/16,1]$ , checked in full, on which $g$ vanishes. The four shaded segments $[1-c^{i},1-c^{i+1}]$ , $i=0,\dots,3$ , are the invalid sets of an adversary forking at $1-c^{i}$ with its valid weight last; each has mass $1/4$ under $g$ , and together they tile the support, which is the proof of Theorem 5.21(1).

Definition 5.19 (Sampling map).

Let the head’s root tuple $\mathsf{rt}$ carry committed work $\mathsf{rt}.\mathsf{w}$ , with leaf count $n$ . The sampling map sends a uniform $U\in[0,1]$ to the point $\xi=1-\delta^{U}$ , the inverse of $G$ at $U$ , so that $\xi$ has density $g$ ; it sends $\xi$ to the point $x=\xi\cdot\mathsf{rt}.\mathsf{w}$ of cumulative work, and $x$ to the leaf $j$ whose interval $[W,W+v_{j}.\mathsf{w})$ contains $x$ . That interval is bound to $(\mathsf{rt},n,j)$ by Lemma 3.21(1) and is checked by the weight-position check of Construction 5.8. The checked suffix is the set of blocks whose interval meets $[(1-\delta)\,\mathsf{rt}.\mathsf{w},\mathsf{rt}.\mathsf{w})$ , together with the last $L$ blocks and the head.

Assumption 5.20 (Discretisation).

For every chain $C$ output by an adversary respecting Definition 4.5, and for the fork point $a$ of $C$ against the honest chain, if $C$ has more than $L$ blocks after $a$ and total work after $a$ at least that of the honest chain, then one draw of Definition 5.19 returns an invalid block, or a block on which the per-sample check fails, with probability at least $p_{g}(a)$ of Definition 5.15 minus a function negligible in $\kappa$ ; the $Q$ draws are independent.

The paper asserts that the continuum analysis “still produces a good distribution for the discrete case” (ePrint 2019/226, Section 5.4) and gives no proof; the hypothesis is named here.

Theorem 5.21 (Optimal sampling distribution).

Let $0<c<1$ , let $k\geq 1$ be real and $\delta=c^{k}$ . Suppose that the suffix $[1-\delta,1]$ is checked in full and that the adversary’s valid weight after any fork point $a$ is at most a $c$ fraction. Then:

1.

if $k$ is an integer, for every sampling density $\varphi$ , $\min_{a}p_{\varphi}(a)\leq 1/k$ ;
2.

the density $g$ of Construction 5.18 attains $\min_{a}p_{g}(a)=1/k$ , against every placement of the invalid weight.

Proof.

(1) Tiling. At the fork points $a_{i}=1-c^{i}$ , $i=0,\dots,k-1$ , the placement with valid weight last is available to the adversary against every $\varphi$ , and leaves the invalid segment $[1-c^{i},1-c^{i+1}]$ , of measure $c^{i}(1-c)=(1-c)(1-a_{i})$ , inside $[0,1-\delta]$ . These $k$ segments tile $[0,1-c^{k}]=[0,1-\delta]$ , so $1\geq\sum_{i}\int_{[1-c^{i},1-c^{i+1}]}\varphi\geq k\min_{i}p_{\varphi}(a_{i})$ . No monotonicity of $\varphi$ is used. (2) The density $g$ is increasing on $[0,1-\delta]$ , so for $a\leq(c-\delta)/c$ Lemma 5.16 makes $[a,1-(1-a)c]$ the adversary’s best set, whose catch probability is $1/k$ by Construction 5.18; later fork points meet the suffix and are caught with probability $1$ . A script checks the $k$ tiling masses. □

The theorem is ePrint 2019/226, Theorem 2, pp. 16–17. The paper prints $c\in(0,1]$ , where $\log\delta=0$ at $c=1$ and $g$ is undefined; the domain here is $0<c<1$ . The paper’s proof sums over $k+1$ segments, $i=0,\dots,k$ , the last of which lies in the checked suffix; the range is $i=0,\dots,k-1$ . The paper’s Lemma 3, a monotonicity lemma, is not needed.

Proposition 5.22 (Sample count).

Let $k>1$ . Then $Q$ independent draws from $g$ all miss an optimally placed invalid set with probability at most $(1-1/k)^{Q}$ , and

(1-1/k)^{Q}\leq 2^{-\sigma}\iff Q\geq\frac{\sigma}{\log_{2}\bigl{(}1/(1-1/k)% \bigr{)}}.

At constant difficulty with the last $L=c^{k}n$ blocks checked, $k=\log_{1/c}(n/L)$ and the least such $Q$ is $\Theta(\sigma k)$ , which is $O(\sigma\log_{1/c}n)$ ; for constant $L$ it satisfies

\lim_{n\to\infty}\frac{Q}{\sigma\log_{c}(1/2)\,\log n}=1.

Here $\sigma$ is the statistical exponent, not the security parameter.

Proof.

The miss bound is Definition 5.15 with Theorem 5.21(2); the equivalence follows on taking logarithms. Since $\log_{2}(1/(1-1/k))=1/(k\log 2)+O(1/k^{2})$ , the least $Q$ satisfies $Q\sim\sigma k\log 2=\sigma\log_{c}(1/2)\log(n/L)$ , and $\log(n/L)/\log n\to 1$ for constant $L$ . A script cross-checks the least $Q$ against exact rational arithmetic for $2\leq k\leq 9$ at $\sigma=50$ . □

The proposition is ePrint 2019/226, Section 5.4 (“Optimizing the Proof Size”), p. 17.

Remark 5.23 (Domain of the catch parameter).

At $k=1$ , $\delta=c$ : one draw suffices in the continuum model, and $\log_{2}(1/(1-1/k))$ is undefined, so Proposition 5.22 is stated for $k>1$ . For $k<1$ , $\delta>c$ and the checked suffix catches every adversary; the paper assumes $k\geq 1$ without loss of generality. For non-integer $k>1$ , Construction 5.18 still gives catch probability $\log c/\log\delta=1/k$ and hence the sample bound. The tiling of part (1) of Theorem 5.21 needs integral $k$ .

Remark 5.24 (Length of the checked suffix).

Under variable difficulty the suffix checked in full is the weight fraction $\delta$ , and a sound instantiation makes it contain at least the last $L$ blocks, as Definition 5.19 does (Remark 4.10). The length $L$ is bounded below by the $L$ of the $(c,L)$ assumption in force and trades against $Q$ : a larger $L$ means a larger $\delta$ , a smaller $k$ and fewer samples. The asymptotic size bound holds for constant $L$ ; within it, $L$ may be chosen numerically. Which $(c,L)$ holds for Zcash is classified in “The deployment boundary” (§7).

Example 5.25 (Sample counts).

At $c=1/2$ and $\sigma=50$ , with $k=\log_{2}(n/L)$ , the least $Q$ with $(1-1/k)^{Q}\leq 2^{-50}$ is as follows.

$n$	$L$	$k$	bound	$Q$
$2^{20}$	$100$	$13.36$	$445.3$	$446$
$2^{22}$	$100$	$15.36$	$514.7$	$515$
$2^{22}$	$1{,}000$	$12.03$	$399.5$	$400$
$2^{24}$	$100$	$17.36$	$584.0$	$585$
$2^{26}$	$100$	$19.36$	$653.4$	$654$

Every $k$ here is non-integer, so Remark 5.23 applies: the counts are sufficient, and their optimality is not claimed.

5.5 The interactive protocol

Construction 5.26 (Interactive FlyClient).

The parties are a verifier $\mathcal{V}$ in the setting of Definition 4.16, which knows the genesis block $B_{0}$ , and provers $\mathcal{P}_{1},\dots,\mathcal{P}_{m}$ , at least one of them honest. The parameters are $c$ , $L$ , a real $k>1$ , $\delta=c^{k}$ and $Q$ . The ranges are difficulty MMRs (Definition 5.6) committed by Construction 5.1.

1.

Each prover sends its head $B_{\eta}$ , whose header records $\mathsf{rt}_{n}.\mathsf{h}$ over $B_{0},\dots,B_{\eta-1}$ , together with the two children of the root tuple (for $n=1$ , the single leaf tuple). The verifier recomputes the root tuple $\mathsf{rt}$ with $\mathrm{par}$ , rejects unless $\mathsf{rt}.\mathsf{h}$ equals the recorded value, and reads $n=\mathsf{rt}.\mathsf{n}$ and the claimed total work $\omega=\mathsf{rt}.\mathsf{w}+D(T_{\mathrm{head}})$ , where $T_{\mathrm{head}}$ is the target the head declares.
2.

If all heads are identical, $\mathcal{V}$ accepts that head.
3.

Otherwise $\mathcal{V}$ orders the claims by claimed total work, heaviest first, and for each prover draws $Q$ independent uniforms, maps each to a point of cumulative work by Definition 5.19, and requests the leaf at each point.
4.

For each requested point the prover returns the header, the leaf tuple and its inclusion path with full node tuples. The sample must pass Construction 5.2, whose checks (a) and (d) require a proof of work valid at a target that the difficulty-MMR fields declare, and Construction 5.8 on every node of its path, including the weight-position check that the drawn point lies in the returned leaf’s interval.
5.

The prover sends the checked suffix of Definition 5.19, and $\mathcal{V}$ checks it in full: every block passes the per-sample and node checks, and consecutive blocks, the head included, satisfy the linkage and target conditions of Definition 4.14, the target of each block being the one that the field $\mathsf{D}_{\mathsf{next}}$ of its predecessor’s leaf declares.
6.

Any failure rejects that prover. Among the surviving claims $\mathcal{V}$ accepts the heaviest, outputting its head and claimed total work; claims equivalent under Definition 4.15 count as one claim.

The construction is ePrint 2019/226, Algorithms 1 and 2 with Definition 5 and Sections 5.3, 5.4 and 6.1. Step 5 belongs to the protocol by Sections 5.3 and 5.4 of the paper, although its Algorithm 1 omits it. For claims of different weight the paper delegates the comparison to the generic verifier of Kiayias, Miller and Zindros (“Non-interactive proofs of proof-of-work”), which checks the longest claim first; under variable difficulty the order is by claimed total work, as in step 3.

5.6 The non-interactive protocol

Construction 5.27 (Non-interactive FlyClient).

Construction 5.26 is public-coin and one-round: the only message of $\mathcal{V}$ is its sampling coins, which do not depend on the provers’ answers. The non-interactive protocol applies the Fiat–Shamir transform (Crypto Guide, §“The Fiat–Shamir transform: from interactive to non-interactive”), the challenge hashing the instance. Let $\mathcal{O}$ be a random oracle (Crypto Guide, §“The random oracle model”); the uniforms are $U_{i}=\mathcal{O}(H(\mathrm{hdr}(B_{\eta})),i)$ , $i=1,\dots,Q$ , read as points of $[0,1)$ , seeded by the proof-of-work output of the head. Through $\mathsf{rt}_{n}$ the head commits to the whole claimed chain.

1.

Prover. It computes $U_{1},\dots,U_{Q}$ from its head and the sampled leaves by Definition 5.19, and sends one message: the head with the root’s children, for each $i$ the sampled header, leaf tuple and inclusion path with full node tuples, and the checked suffix.
2.

Verifier. For each proof received it recomputes $U_{1},\dots,U_{Q}$ from the head and runs steps 1 and 4 to 6 of Construction 5.26 on the points they determine.

The paper suggests a standard hash (ePrint 2019/226, Section 6.2) and fixes no domain separation, no map from hash outputs to points and no proof encoding. In the classes of Definition 1.3 the construction is designed but unspecified for Zcash.

Assumption 5.28 (Head-recomputation budget).

During one execution the adversary produces at most $R$ heads that carry a valid proof of work.

Assumption 4.8 bounds the validly mined weight of a fork, not the number of head recomputations, and does not imply Assumption 5.28. The paper’s budget $R=cn$ (“our security assumption gives a concrete bound on the number of PoW puzzles the adversary can solve, which is $c n$ ”, ePrint 2019/226, Section 6.2) is asserted, not derived.

Proposition 5.29 (Grinding bound).

Assume Assumptions 5.28, 5.20, 5.11 and 4.8, let $\mathcal{O}$ be a random oracle, let $H$ be the random oracle of Definition 4.1, with $\kappa$ -bit outputs, and let $k>1$ . Let at most $q_{\mathcal{O}}$ queries to $\mathcal{O}$ and $q_{H}$ queries to $H$ be made. The probability that an adversary makes Construction 5.27 accept a claimed chain whose fork is not caught is at most

R\,(1-1/k)^{Q}+q_{\mathcal{O}}\,q_{H}\,2^{-\kappa}+\mathrm{Adv}^{\mathrm{col}}% _{H}(\mathcal{B})+\mathsf{negl}(\kappa)

for an explicit reduction $\mathcal{B}$ . Hence

Q>\frac{\sigma+\log_{2}R}{\log_{2}\bigl{(}1/(1-1/k)\bigr{)}}

suffices for failure probability below $2^{-\sigma}$ plus negligible terms. This $Q$ is $\Theta((\sigma+\log R)\,k)$ and, at constant difficulty with constant $L$ , $\Theta((\sigma+\log R)\log_{1/c}n)$ ; it exceeds the interactive count of Proposition 5.22 by the $\log_{2}R$ bits of grinding.

Proof.

Each head with a valid proof of work fixes, through $\mathsf{rt}_{n}$ , the claimed chain and its invalid set before its challenge $\mathcal{O}(H(\mathrm{hdr}(B_{\eta})),\cdot)$ is known, barring a collision of $H$ (Proposition 5.3). The challenge of a header cannot be computed before $H(\mathrm{hdr})$ is queried, and that same query decides validity. Since $\mathcal{O}$ is independent of $H$ , the challenges of the at most $R$ valid heads are uniform and independent of which heads are valid, except when $\mathcal{O}$ was queried at a value before it arose as an $H$ -output, which has probability at most $q_{\mathcal{O}}\,q_{H}\,2^{-\kappa}$ . So by Assumption 5.20 and Theorem 5.21 the $Q$ samples of each valid head all miss with probability at most $(1-1/k)^{Q}$ plus a negligible term. A head without a valid proof of work fails step 5 of Construction 5.26. By Assumption 5.28 at most $R$ heads qualify, and the union bound (Math Guide, §“The union bound and a birthday calculation”) gives the bound. The threshold follows on taking logarithms, and its order as in the proof of Proposition 5.22. □

The bound is proved here because the Crypto Guide proves Fiat–Shamir security only for Sigma protocols (§“The Fiat–Shamir transform: from interactive to non-interactive”); the argument above uses only that the challenge is a random-oracle image of the proof-of-work output of a header committing to the whole instance. Seeded by the header itself, the challenge could be evaluated before the proof of work is attempted, and an adversary could mine only heads whose samples miss.

Example 5.30 (Grinding cost).

At $c=1/2$ , $\sigma=50$ , $L=100$ and $n=2^{22}$ , $k=\log_{2}(n/L)\approx 15.36$ . Proposition 5.22 gives $Q\geq 514.7$ , so $515$ samples. With the paper’s $R=cn=2^{21}$ the budget adds $21$ bits, and Proposition 5.29 gives $Q>730.8$ , so $731$ samples. At the other $(n,L)$ of Example 5.25, namely $(2^{20},100)$ , $(2^{22},1{,}000)$ , $(2^{24},100)$ and $(2^{26},100)$ , the non-interactive counts are $615$ , $568$ , $853$ and $981$ .

Proposition 5.31 (Transferability).

A proof of Construction 5.27 is publicly verifiable: its verification uses only the proof, the genesis block and the public oracles, so any party can relay it unchanged, and it convinces every verifier that the original convinces. For a given head the sampled points are deterministic; under a canonical proof encoding there is therefore one proof per head, which one party can compute for every verifier.

Proof.

The verifier’s decision is a deterministic function of the proof and public data, and the points are a function of the head. □

The paper’s statement that “there only exists a single valid non-interactive proof” (ePrint 2019/226, Section 8.1) holds only under a canonical encoding, which no ZIP specifies. ZIP 221, “Security and Privacy Considerations” records that, because FlyClient proofs are non-interactive and publicly verifiable, “they could be shared among many light clients after the initial server interaction”.

5.7 The security theorem

Theorem 5.32 (FlyClient security and succinctness).

Assume:

1.

$0<c<1$ , a real $k>1$ and $\delta=c^{k}$ ;
2.

the variable-difficulty backbone model (Definition 4.1), in which every adversary is a $(c,L)$ -adversary (Assumption 4.8);
3.

$H$ collision resistant and, as in Definition 4.1, a random oracle, and the sampling oracle $\mathcal{O}$ a random oracle;
4.

Assumptions 5.28, 5.20, 5.11 and 4.4;
5.

a verifier that knows only the genesis block, and at least one honest prover (Definition 4.16);
6.

no block header equals $\mathrm{ser}(\ell)\,\|\,\mathrm{ser}(r)$ for node tuples $\ell,r$ (leaf–internal separation, hypothesis 2 of Lemma 5.4).

Then an adversary wins the game of Definition 4.17 against Construction 5.27 with probability at most $R\,(1-1/k)^{Q}$ plus negligible terms, which is at most $2^{-\sigma}$ plus negligible terms when $Q$ satisfies Proposition 5.29. Proofs have

O\bigl{(}L_{\delta}+(\sigma+\log R)\,k\log n\bigr{)}

headers and hashes, where $L_{\delta}$ is the number of blocks of the checked suffix. The construction is succinct (Definition 4.18) whenever $L_{\delta}$ , $k$ and $\log R$ are $O(\mathrm{polylog}(n))$ , in particular at constant difficulty with constant $L$ and $\delta=L/n$ , where $L_{\delta}=L$ and $k=\log_{1/c}(n/L)$ ; there, with the paper’s $R=cn$ , the size is $O(L+(\sigma+\log n)\log_{1/c}(n)\log n)$ .

Proof structure.

The proof composes the obligations O1 to O6 of Remark 5.33, following the five steps of ePrint 2019/226, Section 6.3. (0) The honest prover’s proof passes every check: its labelling is consistent, its transitions are clamped, and Lemma 3.21(2) makes each weight interval its true prefix weight. (1) Assumption 5.11 replaces an adversary with invalid transitions by one that respects the retarget rule, to which Assumption 4.8 applies (O3). (2) O1 pins every sampled answer to one committed chain; O2 makes every block after the fork point adversarial, or places a leaf of the fork in its invalid set, and makes its validly mined weight post-fork; O3 binds each sampled leaf’s weight interval to the root, while the agreement of that interval with the chain’s true prefix weight rests on the node checks and Assumption 5.11. (3) O4: a fork heavier than the honest chain and longer than $L$ blocks is caught by one draw with probability at least $1/k$ , and a fork within the checked suffix with certainty. (4) O5: the Fiat–Shamir step with the grinding bound. (5) O6: the size count. Agreement of honest full nodes on the prefix up to the last $\ell$ blocks, the second clause of Definition 4.17, is Assumption 4.4. □

The theorem is ePrint 2019/226, Theorem 1 (p. 10, restated p. 20); ZIP 221, “Security and Privacy Considerations” restates its honest-connection and genesis hypotheses. The paper states the size as $O(L+\lambda\log_{1/c}(n)\log n)$ . That equals the constant-difficulty bound above with $R=cn$ only when $\log n=O(\lambda)$ , for instance for $n$ polynomial in $\lambda$ ; under the convention that $n$ grows with $\sigma$ fixed, the theorem states the $\log R$ form and no stronger bound.

Remark 5.33 (Proof obligations).

Each obligation is listed with the results that discharge it.

O1

Binding: Theorem 3.17, Corollary 3.18, Lemma 3.20 and Proposition 5.3.
O2

Fork structure: Lemmas 5.4 and 5.5.
O3

Weight binding and transitions: Lemma 5.7, Construction 5.8 and, for subtrees whose aggregates are inconsistent, Assumption 5.11.
O4

Catch probability and sample count: Theorem 5.21, Definition 5.19, Assumption 5.20 and Proposition 5.22.
O5

Grinding: Proposition 5.29, which fixes the non-interactive $Q$ .
O6

Size: Corollary 5.34.

Corollary 5.34 (Proof size).

For the interactive protocol with $Q$ from Proposition 5.22, constant $L$ and constant difficulty, a proof has size $O(\sigma\log n\log_{1/c}n+L)$ : $Q=\Theta(\sigma\log_{1/c}n)$ samples, each a header and a path of at most $\lceil\log_{2}n\rceil$ nodes under $\mathrm{Bag}_{R}$ (Lemma 3.7), and the $L$ suffix blocks. For the non-interactive protocol, with $Q$ from Proposition 5.29, $\sigma$ is replaced by $\sigma+\log_{2}R$ .

Proof.

Multiply $Q$ by the cost of one sample. The suffix blocks form a contiguous run of leaves ending at leaf $n$ , so the union of their paths has $O(L+\log n)$ nodes and is sent once. □

The corollary is ePrint 2019/226, Corollary 2 (Section 5.4), which states $\Theta$ ; the matching lower bound is not proved here.

Remark 5.35 (Status of the security theorem).

Theorem 5.32 is the paper’s conditional claim, not an independently completed proof. Deriving the $(c,L)$ assumption from the backbone parameters is open (Remark 4.13); the paper’s Lemma 1 is invalid as printed (Remark 4.11); its Lemma 4 is a sketch with recorded gaps and enters as Assumption 5.11; the step from the continuum to blocks is Assumption 5.20; and the budget $R=cn$ is asserted. Proved in this volume are binding (O1), fork structure (O2) under leaf–internal separation, the binding of sampled weight intervals to the root, optimality, the sample count and the grinding bound.

5.8 Verification after acceptance

Proposition 5.36 (Inclusion after acceptance).

Let a head $B_{\eta}$ with root tuple $\mathsf{rt}_{n}$ be accepted. Membership of the block at height $j-1$ in the accepted chain is established by one inclusion path of leaf $j$ against $\mathsf{rt}_{n}$ , and membership of a transaction in that block by one further Merkle path against the transaction root its header carries; no intermediate header is needed. Both are binding barring a collision.

Proof.

For the block, Proposition 5.3(i); for the transaction path, Crypto Guide, §“Soundness: forging a path implies a collision”. □

The proposition is ePrint 2019/226, Sections 1 and 4.2.

Proposition 5.37 (Verification against a fresh head).

A client may run the protocol against the freshest heads and store one recent block $B^{*}$ of its previously accepted chain lying more than $2\ell$ blocks below that chain’s head. Let the height of $B^{*}$ be less than that of the newly accepted head minus $\ell$ . Under the hypotheses of Theorem 5.32, except with its soundness error, the accepted head’s committed range contains $B^{*}$ at its height, which the client checks by one inclusion path (Proposition 5.36); a head is rejected if a sample exposes an invalid block.

Proof.

By Theorem 5.32 both accepted chains are equivalent up to their last $\ell$ blocks to chains of honest full nodes. A head $B_{\eta}$ commits to heights $0$ to $\eta-1$ , so clause (b) of Definition 4.17 at the earlier round places $B^{*}$ in every honest chain of that round with its last $\ell$ blocks removed, and Assumption 4.4 places it in every later honest chain. The height of $B^{*}$ is below that of the new head minus $\ell$ , so $B^{*}$ lies in the part of the new committed chain that clause (b) makes a prefix of an honest chain. □

The paper states without qualification that the range of a fresh head “cannot contain invalid blocks and it must contain all stable blocks” (ePrint 2019/226, Section 4.2, “Unstable Blocks”); that sentence is not carried.

Proposition 5.38 (Subchain proofs, the paper’s claim).

Assume the hypotheses of Theorem 5.32. Suppose a verifier accepted a valid proof for a chain with head $B_{\eta}$ when the honest chain had that head, and later, when the honest chain has head $B_{\eta^{\prime}}$ , $\eta^{\prime}>\eta$ , receives a subproof for the blocks from $B_{\eta}$ to $B_{\eta^{\prime}}$ , sampled as an instance of the protocol with $B_{\eta}$ in place of genesis, together with one inclusion path showing that $B_{\eta}$ lies in the range committed by $B_{\eta^{\prime}}$ . Then, except with the soundness error of Theorem 5.32 for the instance from $B_{\eta}$ , it accepts no chain that a verifier given a full proof for height $\eta^{\prime}$ would reject. The instance from $B_{\eta}$ , which samples only leaves after $B_{\eta}$ of a range committed from $B_{0}$ , is the paper’s design (ePrint 2019/226, Section 8.2) and is not constructed here.

Proof idea.

This is ePrint 2019/226, Theorem 3 (Section 8.2), with the paper’s proof idea. A fork after $B_{\eta}$ faces a fresh instance of the protocol with $B_{\eta}$ as genesis. A fork before $B_{\eta}$ fails the inclusion path, since the verifier’s $B_{\eta}$ is not in the adversary’s range, barring a collision (Proposition 5.36). □

The proposition concerns one commitment range from the genesis block.