This section fixes the model in which the FlyClient theorem is stated: the variable-difficulty backbone with its unit of work, the adversary and persistence; the retarget rule, the attack it excludes and the limit of that exclusion for a sampling verifier; the (c, L) assumption; and the definitions of security and succinctness for chain proofs.
The model of this section is the one ePrint 2019/226 adopts in Section 3.1 and Section 3.2, after Garay, Kiayias and Leonardos (the variable-difficulty backbone, CRYPTO 2017), and it is stated as the paper adopts it. Whether a Zcash chain satisfies its hypotheses is classified in §7, not here.
Fix the security parameter λ (Math Guide, §“The security
parameter”) and a hash length κ . The execution proceeds in rounds
| max r ∈ S ν r ≤ γ min r ∈ S ν r . |
Each block also records the round in which it was mined, which Definition 4.5 reads.
The paper’s paraphrase in Section 3.1 omits “consecutive”; read literally,
for
The paper writes λ for the oracle output length and n r for the honest player count; here the length is κ , λ being the security parameter, and the count is ν r , n being a leaf count (§1.2).
A single query to H meets target T with probability T / 2 κ . The difficulty level of T is
| D (T) = 2 κ / T, |
the expected number of queries per block valid at T . A harder target is a
smaller T and a larger D (T) : the level is a work-like quantity inversely
proportional to the target and is never the target itself. The total
work of a finite sequence of blocks
| ω = ∑ i = 1 m D (T i), |
the paper’s cumulative difficulty. A chain is heavier than another when its total work is larger.
The paper also calls a level a “target” in its Definition 7; in this volume D denotes only a level and T only a target. The Zcash analogue, the work of a block computed from its compact target, is defined in the Consensus Guide, §“Work, and the best chain”, from protocol specification, §“Definition of Work”. It is a different normalisation of the same ordering and is not used by the model.
Fix μ with
The prior knowledge of the verifier is fixed once, in Definition 4.16.
The backbone parameters (μ, γ, s, τ, E, f) , with τ , E and f the constants of Definition 4.5, are such that there is a persistence depth l with, except with probability negligible in λ :
(persistence) for all honest players
(liveness) a transaction given to every honest player for a number of consecutive rounds fixed by the parameters lies in that stable prefix of every honest chain.
ePrint 2019/226, Section 3.1 (p. 7), adopts this as a parameter choice, citing Theorems 26 and 27 of its reference [22], Garay, Kiayias and Leonardos, “The Bitcoin backbone protocol: analysis and applications” (EUROCRYPT 2015), a fixed-difficulty analysis; it names no theorem of its reference [23] (CRYPTO 2017), the source of the variable-difficulty model. No cited theorem establishes the assumption in the model of Definition 4.1.
The tips of honest chains need not coincide: persistence gives agreement only on all but the last l blocks. The paper’s sentence that persistence and liveness give “a single chain adopted by all honest full nodes” overstates this; the assumption states the corrected form. The persistence depth l is distinct from the catch parameter k of §5.
Fix constants
| ν ^ (T, Δ) = 2 κ E q T Δ, |
and the target of the next epoch is
| Retarget (T, Δ) = { T / τ if (ν 0 / ν ^ (T, Δ)) T 0 < T / τ, τ T if (ν 0 / ν ^ (T, Δ)) T 0 > τ T, (ν 0 / ν ^ (T, Δ)) T 0 otherwise, |
that is, the value (ν 0 / ν ^) T 0 clamped to
[T / τ, τ T] . Let
The unclamped value is the raw retarget
| ν 0 ν ^ (T, Δ) T 0 = ν 0 T 0 q T Δ 2 κ E = T Δ f E, |
which restores f blocks per round at the estimated participation. The current target T is an input of the rule; the paper’s list of constants omits it. The definition is ePrint 2019/226, Definition 1 (Section 3.1, p. 7), after Garay, Kiayias and Leonardos, Definition 2. The function is written Retarget rather than the paper’s D (n 0, T 0) , because D is a difficulty level, and ν 0 and T 0 are the initial constants of the cited definition, not the previous-epoch quantities of the gloss in the paper’s Definition 1. The retarget epoch is distinct from the upgrade epoch of §6.
Under variable difficulty the total work of a chain, not its length, decides between chains. An adversary may therefore mine fewer blocks at higher levels and use the larger variance of a sum of few heavy terms to exceed a more powerful honest chain: the difficulty-raising attack of Bahack (arXiv:1312.7013), recalled in ePrint 2019/226, Section 3.1.
Model block discovery by exponential clocks (Consensus Guide,
§“Memoryless clocks and the attribution sequence”): honest queries arrive
at rate Λ per unit time and adversarial queries at rate
Λ / 3 , one third of the honest power; each query succeeds
independently with probability 1 / D at level D , so that the successes of
a party querying at rate Λ ′ at level D form an exponential clock of
rate Λ ′ / D . Fix a time
The expected total work of the blocks the honest players find in [0, t 0] is W , whatever their targets, so the expected total work of the honest chain at t 0 is at most W .
Suppose the adversary may mine one block at an arbitrary level, in
violation of Definition 4.5, and sets its level to
| 1 − e − 1 / 3 ≈ 0.2835, |
about 28.3 per cent, a constant independent of λ .
(i) An honest query at target T yields a block of work D (T) with
probability
(ii) At level
In the discrete query model the same statement holds as an inequality: if
W / 3 is an integer, the adversary’s W / 3 queries at level W all fail
with probability
Definition 4.5 excludes the attack of Proposition 4.6: a target changes only at epoch ends and by at most the factor τ , so no block may declare an arbitrary level. The paper, citing Garay, Kiayias and Leonardos, states that this rule suffices against difficulty-raising attacks for full nodes, which see every transition and reject a chain that violates it (ePrint 2019/226, Section 3.1, p. 7); that sufficiency is the cited authors’ result and is not proved here. A verifier that samples few blocks sees few transitions. The clamp constrains the transitions it does not see only through data that the chain commits to, which §5.3 constructs; no conclusion about that construction is drawn here. The Zcash retarget rule is a different function, a per-block rule over an averaging window, defined in protocol specification, §“Difficulty adjustment”, and described in the Consensus Guide, §“Difficulty adjustment”; it is not an instance of Definition 4.5.
Fix an honest player and let C be its chain at round r , the honest chain. A fork of a chain C ′ against C has fork point a , the last block common to C and C ′ ; its blocks are those of C ′ after a . A block of the fork is validly mined if it carries a valid proof of work at its declared target (Definition 4.1), and invalid otherwise; its validly mined work is the total work of its validly mined blocks.
The printed form (ePrint 2019/226, Assumption 2, Section 3.2, p. 8) reads: “There exists no adversary in the variable-difficulty model that respects the target recalculation function from Definition 1 and can, with non-negligible probability, produce a fork that contains more than L blocks such that a c fraction of the difficulty weight in these blocks is honest.”
The operative form, for
The operative form departs from the printed one in three stated respects.
The word “honest” in the printed form means validly mined. The length
condition is “more than L blocks”, the printed assumption’s own wording,
where the paper’s preceding sentence (Section 3.2, p. 8) says “of length
L or longer”; the
choice is consistent with checking the last L blocks in full
(Remark 4.10). The operative form quantifies only over
forks whose work after the fork point reaches that of the honest chain,
following the same sentence (“a c fraction of the honest forks
weight”): the unrestricted reading fails for every
In Assumption 4.8 the parameter c bounds the validly mined
fraction of a competitive long fork’s weight. The paper’s evaluation
(ePrint 2019/226, Section 7.1, p. 20, and Section 7.2) reads it instead as a
power ratio ρ , adversarial to honest mining power, so that the
adversary’s share of total power is
Assumption 4.8 constrains only forks of more than L blocks, by
design: over a short window the variance of mining lets even an adversary
with small power produce a heavier short fork with non-negligible
probability (ePrint 2019/226, Section 3.2, p. 8). A verifier relying on the
assumption must therefore check in full a suffix of the claimed chain
containing at least its last L blocks. At constant difficulty the paper
takes
The paper’s only derivation of Assumption 4.8 from mining power is
its Lemma 1 with Corollary 1 (ePrint 2019/226, pp. 8–9), stated here to
register their defect. Lemma 1 as printed: in the constant-difficulty
backbone, if X is the number of blocks any adversary mines while the
honest chain adopts L blocks, and the adversary’s block rate is at most
μ times the honest adoption rate, then for
| Pr [X ≥ c L] ≤ e L (c − μ) (c / μ) − c L . |
Corollary 1: for
The printed bound is the Chernoff bound of a Poisson variable of mean
μ L (Math Guide, §“Exponential clocks, Poisson counts, and the Chernoff method”, Corollary “Chernoff bound for a
Poisson variable”). The proof asserts without proof that such a variable
models X , and it switches to the undefined symbols
The clock model identifies, at constant difficulty, honest adoption and
adversarial block discovery after a fork point a with independent
exponential clocks started at a , of rates 1 and μ , the rates
normalised to the honest adoption rate (Consensus Guide,
§“Memoryless clocks and the attribution sequence”). For
In the clock model, count as validly mined in a fork from a only blocks
the adversary finds after a . Let
| β = (1 + c 1 + μ) 1 + c (μ c) c, θ = (c (1 + μ) μ (1 + c)) c . |
Then:
for every fork point a and
for any set A of candidate fork points, the probability that for
some
| | A | (1 + θ) β L + 1 1 − β . |
For | A | polynomial in λ and
(i) By memorylessness the clocks restart at a , and the bound is the
Math Guide’s Theorem “Chernoff bound for the arrival count”, with
the law of Theorem “Negative-binomial arrival count” (§“Exponential clocks, Poisson counts, and the Chernoff method”),
which also shows
(ii) Fix
| X a, m + 1 ≥ c L ′′ ≥ c max (m, L + 1) . |
If
| e − t ∗ (c M − c) Φ M (t ∗) = e t ∗ c (e − t ∗ c Φ 1 (t ∗)) M = θ β M . |
The union bound (Math Guide, §“The union bound and a birthday calculation”) over these events gives, for the fork point a ,
| β L + 1 + θ ∑ M ≥ L + 2 β M ≤ β L + 1 + θ β L + 2 1 − β ≤ (1 + θ) β L + 1 1 − β, |
and the union over A contributes the factor | A | . For negligibility,
β and θ are constants with
The source omits step (ii). The identification of the fork experiment with the clock model is the paper’s (proof of Corollary 1) and is not derived from Definition 4.1; the counting hypothesis on validly mined blocks is returned to in §5.2.
The paper conjectures that (c, L) can be derived from the backbone parameters (μ, γ, s, τ, E, f) and leaves the derivation out of scope (“not trivial and out of the scope of this paper”, ePrint 2019/226, Section 3.2, p. 8). No such derivation exists: in the classes of Definition 1.3 it is an open problem. Proposition 4.12 covers only the constant-difficulty clock model and does not connect the variable-difficulty backbone to Assumption 4.8. Every result of this volume that uses the assumption is conditional on it.
Let
The definition is ePrint 2019/226, Definition 2 (Section 3.3, p. 9). The paper writes B n and D for the head and the cumulative difficulty; here η is a height and ω the total work, n and D being reserved.
Two chains are equivalent up to the last l blocks, with l the persistence depth of Assumption 4.4, if removing the last l blocks of each leaves one a prefix of the other. The verifier treats valid proofs of equivalent chains as proofs of one chain and takes the one of greatest total work as its representative; no predicate is evaluated on the last l blocks.
The paper writes k for this depth (Section 3.3, p. 9); here l , k being the catch parameter.
The verifier is a light client (Definition 2.1) whose only prior knowledge of the chain is the genesis block B 0 , and which has oracle access to H to check proofs of work. It receives a set P of proofs from several provers, at least one of which is honest, and accepts the SPV predicate of the proof whose head carries the greatest total work, up to Definition 4.15.
The honest-prover hypothesis places eclipse attacks, in which every prover is adversarial, outside the model (ePrint 2019/226, Section 3.3, p. 9).
A chain proof protocol is a pair (P, V) of algorithms with oracle access to H : the prover P maps a chain to a proof, and the verifier V maps a set of proofs to an output (B, ω) , a head and a total work, or to rejection. The security game, for an environment, a PPT adversary A as in Definition 4.3 and a round r , is as follows.
The backbone execution of Definition 4.1 runs to round r , with A controlling the adversarial players.
At the start of round r the verifier receives a set P containing at least one proof that P computes on the chain of an honest full node; A chooses the other proofs.
The adversary wins if either of the following clauses fails.
At the end of round r the verifier outputs the SPV predicate of greatest total work for some head B : a pair (B, ω) such that the SPV predicate holds for a chain ending in B of total work ω , and no proof in P of a chain whose SPV predicate holds carries more total work, up to Definition 4.15.
Every honest full node at round r holds a chain of which the chain committed by B , with its last l blocks removed, is a prefix.
The protocol is secure if for every environment, every PPT A and every round r the probability that A wins is negligible in λ .
The definition states both clauses of ePrint 2019/226, Definition 3 (Section 3.3, p. 9). The game idiom is that of the Crypto Guide, §“Security as a game”; the multi-prover game is defined here.
A chain proof protocol (P, V) is succinct if for
every PPT prover and every round r , every proof produced at round r has
size O (polylog (N)) bits, where N is the number of blocks of the
honest chain,
The definition is ePrint 2019/226, Definition 4 (p. 9), after Kiayias, Miller and Zindros, “Non-interactive proofs of proof-of-work”, Definition 4.
The term names this class of protocols. Kiayias, Miller and Zindros use the same name for their superblock construction, a different member of the class.