FlyClient Guide Merkle mountain ranges, the chain-history commitment, and the FlyClient sampling protocol 3 Merkle mountain ranges 5 The FlyClient protocol

4 The FlyClient security model

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.

4.1 The variable-difficulty backbone model

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.

Definition 4.1 (Variable-difficulty backbone model).

Fix the security parameter $\lambda$ (Math Guide, §“The security parameter”) and a hash length $\kappa$ . The execution proceeds in rounds $r=1,2,\ldots$ . The proof-of-work function is a random oracle $H\colon\{0,1\}^{*}\to\{0,1\}^{\kappa}$ (Crypto Guide, §“The random oracle model”), its outputs read as integers in $[0,2^{\kappa})$ . In round $r$ there are $\nu_{r}$ honest and $t_{r}$ adversarial active players, and each active player makes $q$ sequential queries to $H$ per round. A block $B$ declares a target $T\in[1,2^{\kappa}]$ in its header, and $B$ carries a valid proof of work at $T$ if and only if $H(B)<T$ . A message broadcast in round $r$ is delivered to every player in round $r+1$ , in an order the adversary chooses. The honest participation sequence $(\nu_{r})_{r}$ is $(\gamma,s)$ -respecting: for every set $S$ of at most $s$ consecutive rounds,

\max_{r\in S}\nu_{r}\leq\gamma\min_{r\in S}\nu_{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 $s\geq 3$ it bounds participation over the whole execution.

The paper writes $\lambda$ for the oracle output length and $n_{r}$ for the honest player count; here the length is $\kappa$ , $\lambda$ being the security parameter, and the count is $\nu_{r}$ , $n$ being a leaf count (§1.2).

Definition 4.2 (Difficulty level and total work).

A single query to $H$ meets target $T$ with probability $T/2^{\kappa}$ . The difficulty level of $T$ is

D(T)=2^{\kappa}/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 $B_{1},\ldots,B_{m}$ with declared targets $T_{1},\ldots,T_{m}$ is

\omega=\sum_{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.

Definition 4.3 (Adversary).

Fix $\mu$ with $0<\mu<1$ . The adversary is a PPT algorithm (Math Guide, §“Algorithms, running time, and PPT”; Crypto Guide, §“Adversaries and the security parameter”) that controls the $t_{r}$ adversarial players of each round $r$ , with $t_{r}<\mu\nu_{r}$ , so that it makes at most $t_{r}q$ queries to $H$ in round $r$ . It is rushing: in each round it receives every honest message of the round before choosing its own, and it orders the delivery of all messages. Its goal is to make a light client accept a chain whose total work is at least that of the honest chain.

The prior knowledge of the verifier is fixed once, in Definition 4.16.

Assumption 4.4 (Persistence and liveness).

The backbone parameters $(\mu,\gamma,s,\tau,E,f)$ , with $\tau$ , $E$ and $f$ the constants of Definition 4.5, are such that there is a persistence depth $\ell$ with, except with probability negligible in $\lambda$ :

1.

(persistence) for all honest players $P_{1},P_{2}$ and rounds $r_{1}\leq r_{2}$ , the chain of $P_{1}$ at round $r_{1}$ with its last $\ell$ blocks removed is a prefix of the chain of $P_{2}$ at round $r_{2}$ ;
2.

(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 $\ell$ 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 $\ell$ is distinct from the catch parameter $k$ of §5.

4.2 Retargeting and the difficulty-raising attack

Definition 4.5 (Target recalculation with dampening).

Fix constants $E\geq 1$ (the retarget-epoch length, in blocks), $\tau>1$ (the dampening factor), an initial participation estimate $\nu_{0}>0$ and an initial target $T_{0}$ . Targets are constant within each retarget epoch of $E$ consecutive blocks. At the end of an epoch whose $E$ blocks were mined at target $T$ in $\Delta$ rounds, read from the rounds the blocks record, the participation estimate is

\hat{\nu}(T,\Delta)=\frac{2^{\kappa}E}{qT\Delta},

and the target of the next epoch is

\mathrm{Retarget}(T,\Delta)=\begin{cases}T/\tau&\text{if }(\nu_{0}/\hat{\nu}(T% ,\Delta))\,T_{0}<T/\tau,\\ \tau T&\text{if }(\nu_{0}/\hat{\nu}(T,\Delta))\,T_{0}>\tau T,\\ (\nu_{0}/\hat{\nu}(T,\Delta))\,T_{0}&\text{otherwise,}\end{cases}

that is, the value $(\nu_{0}/\hat{\nu})\,T_{0}$ clamped to $[T/\tau,\tau T]$ . Let $f=q\nu_{0}T_{0}/2^{\kappa}$ , the expected number of blocks per round of $\nu_{0}$ players at $T_{0}$ . A chain respects the rule when every epoch’s target is the image under $\mathrm{Retarget}$ of the previous epoch’s target and round span.

The unclamped value is the raw retarget

\frac{\nu_{0}}{\hat{\nu}(T,\Delta)}\,T_{0}=\frac{\nu_{0}T_{0}\,qT\Delta}{2^{% \kappa}E}=\frac{T\Delta 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 $\mathrm{Retarget}$ rather than the paper’s $D(n_{0},T_{0})$ , because $D$ is a difficulty level, and $\nu_{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.

Proposition 4.6 (Success of the difficulty-raising attack).

Model block discovery by exponential clocks (Consensus Guide, §“Memoryless clocks and the attribution sequence”): honest queries arrive at rate $\Lambda$ per unit time and adversarial queries at rate $\Lambda/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 $\Lambda^{\prime}$ at level $D$ form an exponential clock of rate $\Lambda^{\prime}/D$ . Fix a time $t_{0}>0$ and let $W=\Lambda t_{0}$ .

(i)

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$ .
(ii)

Suppose the adversary may mine one block at an arbitrary level, in violation of Definition 4.5, and sets its level to $D=W$ . Then it finds that block, whose work alone equals $W$ , before $t_{0}$ with probability

$1-e^{-1/3}\approx 0.2835,$

about $28.3$ per cent, a constant independent of $\lambda$ .

Proof.

(i) An honest query at target $T$ yields a block of work $D(T)$ with probability $T/2^{\kappa}=1/D(T)$ , hence has expected work $1$ whatever the target. By linearity of expectation the expected work found in $[0,t_{0}]$ equals the expected number of honest queries in $[0,t_{0}]$ , which is $\Lambda t_{0}=W$ (Math Guide, §“The clock toolkit: exponential clocks, Poisson counts, and the Chernoff method”, Theorem “Poisson arrival counts”). The honest chain carries at most the work found.

(ii) At level $D=W$ the adversary’s successes form an exponential clock of rate $(\Lambda/3)/W=1/(3t_{0})$ . Its first arrival exceeds $t_{0}$ with probability $e^{-t_{0}/(3t_{0})}=e^{-1/3}$ (Math Guide, same section, Lemma “Tail, mean, and memorylessness”), so it occurs before $t_{0}$ with probability $1-e^{-1/3}$ . □

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 $(1-1/W)^{W/3}\leq e^{-1/3}$ , since $1-x\leq e^{-x}$ , so it succeeds with probability at least $1-e^{-1/3}$ . Since $\log(1-x)\geq-x-x^{2}$ for $0\leq x\leq 1/2$ , $(1-1/W)^{W/3}\geq e^{-1/3-1/(3W)}\geq e^{-1/3}(1-1/(3W))$ , so for every such $W\geq 3$ the two probabilities differ by at most $e^{-1/3}/(3W)<1/W$ . The paper states “roughly 28%” without derivation (ePrint 2019/226, Section 3.1, p. 7); the comparison, as in the paper, is with the expected honest work.

Remark 4.7 (The clamp as a defence).

Definition 4.5 excludes the attack of Proposition 4.6: a target changes only at epoch ends and by at most the factor $\tau$ , 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 in motion”; it is not an instance of Definition 4.5.

4.3 The $(c,L)$ -adversary

Fix an honest player and let $C$ be its chain at round $r$ , the honest chain. A fork of a chain $C^{\prime}$ against $C$ has fork point $a$ , the last block common to $C$ and $C^{\prime}$ ; its blocks are those of $C^{\prime}$ 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.

Assumption 4.8 ( $(c,L)$ -adversary).

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 $0<c<1$ and $L\geq 1$ : for every PPT adversary respecting Definition 4.5 in the model of Definition 4.1, except with probability negligible in $\lambda$ , every fork it produces that has more than $L$ blocks after its fork point $a$ , and total work after $a$ at least the total work of $C$ after $a$ at the same round, has validly mined work less than $c$ times its total work after $a$ . Such a fork is therefore at least a $(1-c)$ fraction invalid by weight.

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 $\mu>0$ , since the adversary’s own fully valid private fork of more than $L$ blocks has valid fraction $1$ , and only forks that reach the honest weight can win under Definition 4.16.

Remark 4.9 (Two readings of $c$ ).

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 $\rho$ , adversarial to honest mining power, so that the adversary’s share of total power is $\rho/(1+\rho)$ : one third at $\rho=1/2$ , and $9/19\approx 0.4737$ , about $47.4$ per cent, at $\rho=0.9$ , where the paper prints $47.3$ per cent by truncation. The identification of $c$ with $\rho$ is not part of the assumption; it needs a bridge from mining power to fork weight, which Remark 4.13 classifies.

Remark 4.10 (Short forks and the checked suffix).

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 $L=\delta n$ ; under variable difficulty it states the checked suffix as a weight fraction $\delta$ (Section 6, p. 17), leaving its relation to the block count $L$ implicit. The size of the suffix under variable difficulty is fixed in §5.4 (Remark 5.24); no conclusion about it is drawn here.

Remark 4.11 (Lemma 1 of the paper).

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 $\mu$ times the honest adoption rate, then for $c>\mu$ ,

\mathrm{Pr}[X\geq cL]\leq e^{L(c-\mu)}(c/\mu)^{-cL}.

Corollary 1: for $L=\Theta(\lambda)$ and every $\mu$ there is $c<1$ for which the assumption holds at constant difficulty.

The printed bound is the Chernoff bound of a Poisson variable of mean $\mu L$ (Math Guide, §“The clock toolkit: 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 $1-\delta$ and $n$ , a footnote setting $\mu=1-\delta$ . Under independent exponential block clocks the count $X$ is negative binomial (same section, Theorem “Negative-binomial arrival count”), and the printed expression is not an upper bound for it in general: the Math Guide’s Example “The Poisson expression is not a bound for the arrival count”, in the same section, exhibits $\mu=1/2$ , $c=3/4$ , $L=200$ and $L=400$ with the exact tail above the printed expression. Lemma 1 and Corollary 1 are therefore unproved as printed; Proposition 4.12 replaces them in the clock model.

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 $\mu$ , the rates normalised to the honest adoption rate (Consensus Guide, §“Memoryless clocks and the attribution sequence”). For $M\geq 1$ let $X_{a,M}$ be the number of adversarial arrivals strictly before the $M$ -th honest arrival after $a$ . The count $X_{a,M}$ is nondecreasing in $M$ .

Proposition 4.12 (Constant-difficulty bound).

In the clock model, count as validly mined in a fork from $a$ only blocks the adversary finds after $a$ . Let $0<\mu<c<1$ and

\beta=\Bigl{(}\frac{1+c}{1+\mu}\Bigr{)}^{1+c}\Bigl{(}\frac{\mu}{c}\Bigr{)}^{c}% ,\qquad\theta=\Bigl{(}\frac{c(1+\mu)}{\mu(1+c)}\Bigr{)}^{c}.

Then:

(i)

for every fork point $a$ and $M\geq 1$ , $\mathrm{Pr}[X_{a,M}\geq cM]\leq\beta^{M}$ , and $\beta<1$ ;
(ii)

for any set $A$ of candidate fork points, the probability that for some $a\in A$ a fork from $a$ exists at some time with more than $L$ blocks, total work after $a$ at least that of the honest chain, and validly mined fraction at least $c$ , is at most

$|A|\,\frac{(1+\theta)\,\beta^{L+1}}{1-\beta}.$

For $|A|$ polynomial in $\lambda$ and $L=\Theta(\lambda)$ this is negligible in $\lambda$ , so Assumption 4.8 holds in the clock model, which recovers Corollary 1 there. The proposition says nothing about the variable-difficulty backbone.

Proof.

(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” (§“The clock toolkit: exponential clocks, Poisson counts, and the Chernoff method”), which also shows $\beta<1$ . That proof attains $\beta$ at $e^{t^{*}}=c(1+\mu)/(\mu(1+c))>1$ as $e^{-t^{*}c}\Phi_{1}(t^{*})=\beta$ , where $\Phi_{M}(t)=(1+\mu-\mu e^{t})^{-M}$ is the moment generating function of $X_{a,M}$ ; note that $\theta=e^{t^{*}c}$ .

(ii) Fix $a\in A$ . At constant difficulty the work of a block is constant, so work is block count. Consider a time at which the honest chain has $m$ blocks after $a$ , and a fork from $a$ at that time with $L^{\prime\prime}$ blocks, total work at least that of the honest chain and validly mined fraction at least $c$ . Then $L^{\prime\prime}\geq\max(m,L+1)$ . The validly mined blocks were found by the adversary after $a$ and before the $(m+1)$ -th honest arrival, so there are at most $X_{a,m+1}$ of them, and the fraction condition gives

X_{a,m+1}\geq cL^{\prime\prime}\geq c\max(m,L+1).

If $m\leq L$ , then $X_{a,L+1}\geq X_{a,m+1}\geq c(L+1)$ , an event of probability at most $\beta^{L+1}$ by (i). If $m=M-1$ with $M\geq L+2$ , the event is $X_{a,M}\geq cM-c$ ; the Chernoff method (Math Guide, same section, Theorem “The Chernoff method”) at $t^{*}$ bounds its probability by

e^{-t^{*}(cM-c)}\Phi_{M}(t^{*})=e^{t^{*}c}\,\bigl{(}e^{-t^{*}c}\Phi_{1}(t^{*})% \bigr{)}^{M}=\theta\beta^{M}.

The union bound (Math Guide, §“The union bound and a birthday calculation”) over these events gives, for the fork point $a$ ,

\beta^{L+1}+\theta\sum_{M\geq L+2}\beta^{M}\leq\beta^{L+1}+\frac{\theta\beta^{% L+2}}{1-\beta}\leq\frac{(1+\theta)\,\beta^{L+1}}{1-\beta},

and the union over $A$ contributes the factor $|A|$ . For negligibility, $\beta$ and $\theta$ are constants with $\beta<1$ , so for $L=\Theta(\lambda)$ the bound is a polynomial in $\lambda$ times a function exponentially small in $\lambda$ , which is negligible (Math Guide, §“Polynomial, exponential, and negligible functions”). □

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.

Remark 4.13 (Status of the $(c,L)$ assumption).

The paper conjectures that $(c,L)$ can be derived from the backbone parameters $(\mu,\gamma,s,\tau,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.

4.4 Security and succinctness of chain proofs

Definition 4.14 (SPV predicate).

Let $C=(B_{0},\ldots,B_{\eta})$ be a chain with genesis block $B_{0}$ and head $B_{\eta}$ . The SPV predicate of $C$ is $1$ if and only if every block $B_{\eta^{\prime}}$ carries a valid proof of work at the target that Definition 4.5 assigns to its position, and for $1\leq\eta^{\prime}\leq\eta$ the hash of $B_{\eta^{\prime}-1}$ is contained in the header of $B_{\eta^{\prime}}$ . The statement a prover proves at round $r$ is that it knows a chain ending in $B_{\eta}$ , with total work $\omega$ (Definition 4.2), whose SPV predicate is $1$ .

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 $\eta$ is a height and $\omega$ the total work, $n$ and $D$ being reserved.

Definition 4.15 (Equivalence up to the last blocks).

Two chains are equivalent up to the last $\ell$ blocks, with $\ell$ the persistence depth of Assumption 4.4, if removing the last $\ell$ 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 $\ell$ blocks.

The paper writes $k$ for this depth (Section 3.3, p. 9); here $\ell$ , $k$ being the catch parameter.

Definition 4.16 (Verifier setting).

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 $\mathcal{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).

Definition 4.17 (Security of a chain proof protocol).

A chain proof protocol is a pair $(\mathsf{P},\mathsf{V})$ of algorithms with oracle access to $H$ : the prover $\mathsf{P}$ maps a chain to a proof, and the verifier $\mathsf{V}$ maps a set of proofs to an output $(B,\omega)$ , a head and a total work, or to rejection. The security game, for an environment, a PPT adversary $\mathcal{A}$ as in Definition 4.3 and a round $r$ , is as follows.

1.

The backbone execution of Definition 4.1 runs to round $r$ , with $\mathcal{A}$ controlling the adversarial players.
2.

At the start of round $r$ the verifier receives a set $\mathcal{P}$ containing at least one proof that $\mathsf{P}$ computes on the chain of an honest full node; $\mathcal{A}$ chooses the other proofs.
3.
The adversary wins if either of the following clauses fails.
1. (a)
  
  At the end of round $r$ the verifier outputs the SPV predicate of greatest total work for some head $B$ : a pair $(B,\omega)$ such that the SPV predicate holds for a chain ending in $B$ of total work $\omega$ , and no proof in $\mathcal{P}$ of a chain whose SPV predicate holds carries more total work, up to Definition 4.15.
2. (b)
  
  Every honest full node at round $r$ holds a chain of which the chain committed by $B$ , with its last $\ell$ blocks removed, is a prefix.

The protocol is secure if for every environment, every PPT $\mathcal{A}$ and every round $r$ the probability that $\mathcal{A}$ wins is negligible in $\lambda$ .

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.

Definition 4.18 (Succinctness).

A chain proof protocol $(\mathsf{P},\mathsf{V})$ is succinct if for every PPT prover and every round $r$ , every proof produced at round $r$ has size $O(\mathrm{polylog}(N))$ bits, where $N$ is the number of blocks of the honest chain, $\mathrm{polylog}(N)=(\log N)^{O(1)}$ as fixed in §1.2, and the asymptotics are in $N$ with $\lambda$ , $c$ and $L$ fixed.

The definition is ePrint 2019/226, Definition 4 (p. 9), after Kiayias, Miller and Zindros, “Non-interactive proofs of proof-of-work”, Definition 4.

Definition 4.19 (Non-interactive proof of proof of work).

A non-interactive proof of proof of work is a chain proof protocol for the SPV predicate in which each prover sends a single message and no message passes from verifier to prover, and which is secure (Definition 4.17) and succinct (Definition 4.18).

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.