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,
Blocks are written B 0 (the genesis block), B 1 , B 2 , …, with B η the block at height η and hdr (B) the header of B .
Fix an aggregating range (Definition 3.19) under the
bagging Bag R (Definition 3.5) whose leaf map sends
a block B to a node tuple leaf (B) with hash field
The construction has the following invariant: the header of B η
commits, through one root, to exactly the blocks strictly before it, and a
head B η commits to
One sample at index
The inputs are a root tuple rt with leaf count n and an index
Leaf:
Prefix: for
Proof of work: hdr j carries a valid proof of work
at the target T it declares,
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.
Let rt be any root tuple, possibly chosen by the adversary, with
leaf count n , and let
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 rt commits;
every header-determined field of that leaf tuple is its value computed from that header;
for
The reduction B runs A and inspects two passing samples
(hdr, v, π) and (hdr ′, v ′, π ′) at position j .
(i) If
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
Let the head of C record the hash field of the root of a consistent
labelling over
the sequences (v 1 ′ . h, ..., v j − 1 ′ . h) and (v 1 . h, ..., v η . h) differ, possibly in length; and
no block header equals ser (l) ∥ ser (r) for
node tuples
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
By Proposition 5.3(iii) a passing sample makes the root
recorded in hdr (B) equal to the hash field of the root of the
consistent labelling of M j − 1 over
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.
Model H as a random oracle with κ -bit outputs (Crypto Guide, §“The random oracle model”), and let at most q H queries to H be made in the experiment, by 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
| Pr [A outputs a fork with a block mined by a reused query] ≤ q H 2 2 − κ + Adv H col (B) |
for an explicit reduction B . Consequently, except with that probability, only adversarial work done after the fork’s prefix is fixed counts against the honest chain.
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 Adv H col (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 } κ 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 − κ . The union bound over the at most q H queries (Math Guide, §“The union bound and a birthday calculation”) gives q H 2 2 − κ . □
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.
A sampling verifier sees few difficulty transitions, so the transitions it does not see must be constrained by committed aggregates.
The difficulty Merkle mountain range (difficulty MMR) is the instance of Definition 3.19 whose node v is the tuple
| v = (v . h, v . w, v . t, v . D start, v . D next, v . 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 . 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 . D next the level of the target that Definition 4.5 assigns to the block after B ;
The parent of l and r has hash field H (ser (l) ∥ ser (r)) , over both children’s complete tuples; its fields w , t and n are the sums of the children’s; it inherits D start from l and D next from r .
The fields h , w , D start and n of a leaf are determined by its header alone and are checked by item (a) of Construction 5.2; the fields t and D 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 (l c, r c) without fixing its input; hashing the children’s hash fields alone would leave their other fields unbound. The paper’s “timestamp” t is an elapsed time, and its “targets” w , D start and D next are difficulty levels. The paper’s checks name fields t start , t end and D end that its Definition 7 never declares; the declared aggregate 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.
Let a sample at leaf j pass Construction 5.2 against a root rt with leaf count n , the shape being fixed by n under Bag R . Except with probability Adv H col (B) for an explicit reduction B :
the leaf weight v j . w is the difficulty level D (T) of the target T at which the header’s proof of work is valid;
the interval
(1) Check (a) sets
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 l and r (one of them a carried sibling), the verifier checks:
for each of l and r , internal consistency:
a node v of altitude below log 2 E lies inside one retarget
epoch and has
a node v of altitude log 2 E is one retarget epoch, has
At the sampled leaf the checks (a) and (d) of
Construction 5.2 apply; their effect on w and
D start is Lemma 5.7.
Weight-position check: when a leaf is requested at a point x of
cumulative weight,
The construction is ePrint 2019/226, Section 6.1 (“Difficulty MMR Verification”); the paper states the weight-position check only informally (Section 2).
Let consecutive retarget epochs
| D start max (τ − e, τ y − z + e) ≤ D e ≤ D start min (τ e, τ y + z − e) ; |
for integer y with
an epoch at target T that lowers the difficulty maximally (new
target τ T ) lasts
(1) Since
In the setting of Proposition 5.9, let y be an integer
with
if
Bounds (2) and (3) are the geometric sums of the envelopes of
Proposition 5.9(2); at
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
In the model of Definition 4.1, for every adversary 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 A ′ that makes the
same number of oracle queries, respects the retarget rule, and with
probability at least
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 ′ be the highest node on a claimed path at which the node checks fail. Every path through x ′ , or carrying it as a sibling, rejects, so barring a collision every leaf of the subtree M ′ under the parent of x ′ is unsampleable without rejection. The adversary A ′ replaces the transitions inside M ′ by clamped ones consistent with the aggregates (w, t, D start, D next, n) of the root of M ′ , which is possible because that node passes the feasibility check and the leaves of M ′ , 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 ′ is meant.
(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 ′
changes every later root and hence every later header, so A ′ 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
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
At constant difficulty, over a claimed chain of n blocks and with u
samples per interval, the verifier draws, for every integer i with
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 .
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 λ .
Let the fork point be a and choose i with
The lemma is ePrint 2019/226, Lemma 2. A fork of at most min (L, u) blocks
lies in the checked suffix. When
The claimed chain is the interval [0, 1] in relative cumulative work: a
block whose cumulative-work interval is
Let φ be non-decreasing on an interval [a, b] with
With
Equal catch probability at every fork point, that is
| φ (a) = c φ (1 − c (1 − a)) . |
The function
The segment mass is
Fix
| g (ξ) = { 1 (ξ − 1) log δ 0 ≤ ξ ≤ 1 − δ, 0 otherwise, G (ξ) = log (1 − ξ) log δ (0 ≤ ξ ≤ 1 − δ) . |
Both factors of the denominator are negative, so
| G (1 − (1 − a) c) − G (a) = log c log δ, |
which is 1 / k at
Normalisation, G and the catch probability are direct integrations. For
the last clause,
Let the head’s root tuple rt carry committed work
rt . w , with leaf count n . The sampling map sends
a uniform
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 κ ; 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.
Let
if k is an integer, for every sampling density φ ,
the density g of Construction 5.18 attains
(1) Tiling. At the fork points
The theorem is ePrint 2019/226, Theorem 2, pp. 16–17. The paper prints
Let
| (1 − 1 / k) Q ≤ 2 − σ ⇔ Q ≥ σ log 2 (1 / (1 − 1 / k)) . |
At constant difficulty with the last
| lim n → ∞ Q σ log c (1 / 2) log n = 1 . |
Here σ is the statistical exponent, not the security parameter.
The miss bound is Definition 5.15 with
Theorem 5.21(2); the equivalence follows on taking logarithms.
Since
The proposition is ePrint 2019/226, Section 5.4 (“Optimizing the Proof Size”), p. 17.
At
Under variable difficulty the suffix checked in full is the weight fraction δ , 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 δ , 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).
At
| 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.
The parties are a verifier V in the setting of
Definition 4.16, which knows the genesis block B 0 ,
and provers
Each prover sends its head B η , whose header records
rt n . h over
If all heads are identical, V accepts that head.
Otherwise 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.
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.
The prover sends the checked suffix of Definition 5.19, and 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 D next of its predecessor’s leaf declares.
Any failure rejects that prover. Among the surviving claims 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.
Construction 5.26 is public-coin and one-round: the only
message of 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
O be a random oracle (Crypto Guide, §“The random oracle
model”); the uniforms are
Prover. It computes
Verifier. For each proof received it recomputes
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.
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
Assume Assumptions 5.28, 5.20,
5.11 and 4.8, let O be a random oracle,
let H be the random oracle of Definition 4.1, with κ -bit
outputs, and let
| R (1 − 1 / k) Q + q O q H 2 − κ + Adv H col (B) + negl (κ) |
for an explicit reduction B . Hence
| Q > σ + log 2 R log 2 (1 / (1 − 1 / k)) |
suffices for failure probability below 2 − σ plus negligible terms.
This Q is
Each head with a valid proof of work fixes, through rt n , the
claimed chain and its invalid set before its challenge
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.
At
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.
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”.
Assume:
H collision resistant and, as in Definition 4.1, a random oracle, and the sampling oracle O a random oracle;
a verifier that knows only the genesis block, and at least one honest prover (Definition 4.16);
no block header equals ser (l) ∥ ser (r) for
node tuples
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 − σ plus negligible terms when Q satisfies Proposition 5.29. Proofs have
| O (L δ + (σ + log R) k log n) |
headers and hashes, where L δ is the number of blocks of the checked
suffix. The construction is succinct (Definition 4.18)
whenever L δ , k and log R are O (polylog (n)) , in
particular at constant difficulty with constant L and
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 l 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
Each obligation is listed with the results that discharge it.
For the interactive protocol with Q from
Proposition 5.22, constant L and constant difficulty, a
proof has size
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
The corollary is ePrint 2019/226, Corollary 2 (Section 5.4), which states Θ ; the matching lower bound is not proved here.
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
Let a head B η with root tuple rt n be accepted. Membership of
the block at height
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.
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 l blocks below that chain’s head. Let the height of B ∗ be less than that of the newly accepted head minus l . 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.
By Theorem 5.32 both accepted chains are equivalent up to
their last l blocks to chains of honest full nodes. A head B η
commits to heights 0 to
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.
Assume the hypotheses of Theorem 5.32. Suppose a verifier
accepted a valid proof for a chain with head B η when the honest
chain had that head, and later, when the honest chain has head B η ′ ,
This is ePrint 2019/226, Theorem 3 (Section 8.2), with the paper’s proof idea. A fork after B η faces a fresh instance of the protocol with B η as genesis. A fork before B η fails the inclusion path, since the verifier’s B η is not in the adversary’s range, barring a collision (Proposition 5.36). □
The proposition concerns one commitment range from the genesis block.