We now proof that if honest parties have some advantage over the dishonest parties in winning the lottery, then the UC Bitcoin protocol \(\textsf {Modular-Ledger-Protocol} _{T}\) realizes the ledger functionality. By the composition theorem, we can directly conclude that \(\textsf {Ledger-Protocol} _{q,\texttt {D},T}\) realizes the Bitcoin ledger functionality.
7.4.2 The Analysis
In the analysis of Bitcoin, conditions are needed that allow to reasonably lower and upper bound expected values of the above random variables (and their variances). As we will quickly recap below, it is shown in [
44] that if the involved query power exceeds any limits in the constant-difficulty case, then no security guarantees can be obtained. We start with the following definition.
Technically, these definitions imply lower and upper bounds on the expectations of the random variables \(\alpha ^{(r)}\) and \(\beta ^{(r)}\), respectively, which is what will be eventually needed.
The bounds in the theorem will depend on several worst-case quantities that we introduce below.
Following [
44], the theorem will take into account that the network delay
\(\Delta \) decreases the effectiveness of the actual honest mining power:
We are now ready to state and prove the main theorem which assures that we can realize the ledger for a given range of parameters.
12
Note that \(\beta _{min}\) is the most restrictive restriction (but not a lower-bound) on the adversary (similarly, \(\alpha _{max}\) is the best guaranteed lower-bound for honest-and-synchronous mining power). In general, the adversary (and hence the environment) is free to activate as many ITIs unless it would exceed \(\texttt {T} _{mp}\) if the environment is \(\texttt {T} _{mp}\)-bounded, and no more than what is allowed by \(\vec {\beta }\). This is a more general setting in the fixed-difficulty setting compared to previous works in the same setting. Furthermore, we show in the next subsection how to get a better bound for chain-quality.
Looking ahead, for example in [
44], the overall number of parties is fixed to be some number
n and there is an upper bound on the number of dishonest parties
\(\rho n\) (and de-synchronized parties are not allowed by definition). Assume for simplicity that
\(p_H= p_A= p\) for a very small value
\(p>0\). We then obtain
\(\alpha _{min} \approx (1-\rho ) \cdot n \cdot p\) and
\(\beta _{max} \approx \rho _H \cdot n \cdot p\). By
\(\texttt {T} _{mp}= n\cdot p\) and since the mining pattern as defined above is flat in flat models (cf. Sect.
8.1), the correspondence
\(\rho _a = \rho \) and
\(\rho _h = (1-\rho )\) follows.
Also, as pointed out by [
44], for too large values of
p in a range that would yield
\(\texttt {T} _{mp}= n\cdot p > \frac{1}{ \Delta }\) (where
\(\Delta \) is the network delay), there is an attack against the protocol, even if one assumes an honest majority. This indicates that the main condition of the theorem in Eq. (
1) is also necessary up to a constant factor, and recent works have revealed the exact threshold for security [
20,
27].
We now prove our main theorem.
Proof of Theorem 7.9
We start with an overview followed by a sequence of claims.
Overview. We prove the theorem using the formalism of [
4] to be able to model shared functionalities. In more detail, we specify the simulator
\(\mathcal {S}_{\text {ledg}} \) as pseudo-code in Appendix
C to prove that
. Recall from Sect.
2.1.4 that this means that in the real world, parties are running
, and in the ideal world the parties are running
, where the operator obliviously transforms the defined protocols into standard UC protocols without changing their behavior, and the indistinguishability notion is the standard UC-emulation notion.
Let us explain the general structure of the simulator and the proof: the simulator internally runs the round-based mining procedure of every honest party. Whenever a working mini-round is over, i.e., whenever the real world parties have issued their queries to \(\mathcal {F}_{\textsc {StX}} \), then the simulator will assemble the views of its simulated honest-and-synchronized miners and determine their common prefix of states, which is the longest state stored or received by each simulated party when chopping off T blocks. The adversary will then propose a new block candidate, i.e., a list of transactions, to the ledger to announce that the common prefix has increased (procedure ExtendLedgerState). The ledger will apply the \(\textsf {Blockify} \) on this list of transactions and add it to the state. Note that since \(\textsf {Blockify} \) does not depend on time, the current time of the ledger has no influence on this output. To reflect that not all parties have the same view on this common prefix, the simulator can adjust the state pointers accordingly (procedure AdjustView). The simulation inside the simulator is perfect and is simply the emulation of real-world processes. What restricts a perfect simulation is the requirement of a consistent prefix and the restrictions imposed by \(\textsf {ExtendPolicy} \). In order to show that these restrictions are not forbidding a proper simulation, we have to justify, why the choice of the parameters in the theorem are sufficient to guarantee that (except with negligible probability). To this end, we analyze the real-world execution to bound the corresponding bad events that prevent a perfect simulation.
We basically follow the proof ideas of Pass, Seeman, and shelat [
44] to bound the bad events and adapt their observations to our setting. The analysis is divided into several different claims about the real-world execution. They include properties such as a lower-bound on the chain growth, the chain quality, or an upper-bound on the chain growth. These claims prove that our simulator can simulate the real-world view perfectly, since the restrictions imposed by the ledger prohibit that only with negligible probability, where the distinguishing advantage is upper bounded by
\(R \cdot \text {negl}(T)\), where
R denotes the number of rounds the protocol is running and
\(\text {negl}(\cdot )\) denotes a negligible function in the parameter
T.
Recall that each round consists of two time-ticks. Hence, if a statement is expressed with respect to a certain number t of rounds, it can equivalently be expressed with respect to 2t clock-ticks. Recall that the ledger parameters have to be given with respect to the clock, since the clock is the formal reference point of time. However, for the analysis, it is easier to think in rounds. In the following sections, if we refer to an interval \(r,\dots ,r+t\), this refers to t full rounds, i.e., the time window when the clock first switched to the value \(\tau =2r\) up to any point where the clock value satisfies \(\tau \in \{2(r+t),2(r+t)+1\}\).
Chain dissemination. We first state an obvious useful fact about the protocol’s operation.
Probably the most useful corollary which is used in the sequel, is to apply the above lemma to the sub-class of honest-and-synchronized miners. Note that if \(P _j\) in the above lemma is honest-and-synchronized at round \(r+\Delta \) it must have been registered to the network not later than at round \(\max \{0, r-\Delta \}\) and hence the statement applies.
Analyzing chain growth. We now state the relation between time (measured in number of rounds) and guaranteed number of new state blocks.
Base Case(s): We give the base cases \(t=0\) and \(=1\) to already include the arguments for the general case below. We argue for any fixed \(\sigma _Z\) and show that the condition in the event cannot be violated. Since adversary \(\mathcal {A}_{} \) and \(\mathcal {A}_{} '\) behave identical up to and including round r, the length of the longest state known or received by any party is the same. The reason is that \(\mathcal {A}_{} '\) and \(\mathcal {A}_{} \) play exactly the same strategy when the randomness is fixed, since \(\mathcal {A}_{} '\) itself does not use additional random coins and thus case \(t=0\) follows. Furthermore, when the randomness \(\sigma '\) of \(\mathcal {F}_{\textsc {StX}} \) is fixed, a miner i in any round \(r'\) is successful, if and only if it is successful in round \(r'\) with adversary \(\mathcal {A}_{} '\). Thus, the condition for \(t=1\) would only be violated if player i receives a longer state in round \(r+1\). However, since \(\mathcal {A}_{} '\) maximally delays messages, if any state arrives in round \(r+1\) in the real execution with \(\mathcal {A}_{} '\), then it arrives no later than \(r+1\) in the real execution with \(\mathcal {A}_{} \). This concludes the base cases.
Induction Step: \(t \rightarrow t+1\): By the induction hypothesis, we have that the condition
holds with probability one. We argue that
holds as well (on the above arguments) with probability one. Assume this was not the case, then following the above reasoning, it can only be due to miner
i receiving a state in round
\(r+t+1\) that would increase the value of
but not the value of
(since the success of miner
i in round
\(r+t+1\) is fixed given
\(\sigma '\)). By the same reasoning as above, since
\(\mathcal {A}_{} '\) maximally delays delivery of new states, if any state arrives in round
r in the real execution with
\(\mathcal {A}_{} '\), then it arrives no later than
r in the real execution with
\(\mathcal {A}_{} \). This concludes the induction proof.
We note that the hybrid world, if we sample \(\sigma , \sigma '\) this yields the distribution \(T_{\textsc {exec}_{\pi ,\mathcal {A}',\mathcal {Z}}}(\kappa ,z)\) (for any fixed input z to the environment). Let us abbreviate this by \(T_{\textrm{real}, \mathcal {A}_{} '}\) to save on notation (and assuming the input z is hard-coded in the environment). Similarly, let us denote \(T_{\textrm{real}, \mathcal {A}_{}}\) the distribution in an execution with \(\mathcal {A}_{} \).
By taking the expectation over
\(\sigma ,\sigma '\) (and by the law of total probability), we immediately get from the above arguments that for any positive integer
c and any round
r:
where we also used that for
\(t=0\), the length distributions induced by
\(\mathcal {A}_{} \) and
\(\mathcal {A}_{} '\) are identical. Hence, chain growth can be analyzed w.r.t. adversary
\(\mathcal {A}_{} '\) to yield a useful statement for any adversary
\(\mathcal {A}_{} \).
Let us use the following terminology: We say a round
\(r'\) is
uniform if
holds (where
tr is a transcript), for all honest-and-synchronized miners
i and
j. Recall that adversary
\(\mathcal {A}_{} '\) does not broadcast adversarially generated states and any new state is delayed by exactly
\(\Delta \) rounds. The slowest progress of the overall maximal state length known to an honest-and-synchronized party occurs in case uniform rounds are the only successful rounds (if at all). Otherwise, the honest miner with the longest state could be successful and broadcast a longer state at round
\(r'\), which would be guaranteed to arrive to any other honest miner in
\(r + \Delta \). Furthermore, by a standard coupling argument, the probability of success of any honest-and-synchronized party in some round
\(r'\) is minimized by an environment
\(\mathcal {Z}\) that activates just enough parties to obey the mining pattern
\(\alpha _{r'}\). The coupling with any other environment can be obtained by letting the activation results be the same up to the point where enough parties have been activated to satisfy the mining pattern. Further activations honest-and-synchronized participants can only induce more successful state extension than what
\(\mathcal {Z}\) obtained.
We are thus left with analyzing growth w.r.t. a simple adversary and an environment \(\mathcal {Z}\) with a fixed activation pattern per round to match the mining pattern.
Obtaining a tail bound depending on number of blocks. Now, fix some round
r. If in round
\(s=r+t\), the length increase of the overall longest state of an honest-and-synchronized miner is less than
c blocks, then at most
\(c\cdot \Delta \) non-uniform rounds occurred. According to above, we can associate to each round
i a random variable
\(X_{i}\) which is 1 if at least one honest-and-synchronized miner successfully extended the state by a query to
\(\mathcal {F}_{\textsc {StX}} \). The
\(X_i\)’s are independent by construction and there must be at least
\(t-c\cdot \Delta \) uniform rounds. On the other hand, for any concrete sub-sequence of rounds
\(S \subset (r,\dots ,r+t)\) of size
\(t'\), the Chernoff-Hoeffding bound in Theorem
2.3 implies for our setting (of independent heterogeneous variables) that
$$\begin{aligned} \Pr \left[ \sum _{i \in S} X_i \le (1-\delta ) \cdot \overline{\alpha }_S \cdot t' \right] \le \exp (-\Omega (\overline{\alpha }_S \cdot t')), \end{aligned}$$
(2)
where
\(\overline{\alpha }_S:= \frac{1}{t'}\sum _{i \in S}\alpha _i\).
We conclude that if for the sub-sequence
S of rounds in the interval from
r to
s, the relations
\(c = {{\,\mathrm{\mathbb {E}}\,}}\left[ \sum _{i \in S} X_i\right] = \overline{\alpha }_S \cdot t'\) and
\(|S| =: t' = t- c\Delta \) hold, we can derive a tail-estimate depending on the number of blocks. We can define
$$\begin{aligned} c_S := \frac{\overline{\alpha }_S t}{1+\overline{\alpha }_S\Delta } \end{aligned}$$
and assign a corresponding growth coefficient
$$\begin{aligned} \gamma _S := \frac{\overline{\alpha }_S}{1+\overline{\alpha }_S\Delta }. \end{aligned}$$
and thus except with exponentially small probability in
\(t\gamma _S=c_S\), the length-increase is at least
\(c_S\) for this particular interval.
For the first part of the statement, observe that
\(\overline{\alpha }_S \ge \alpha _{min}\), for all subsets
S, and that the function
\(\frac{x}{1+kx}\), where
k is a positive integer and
\(x\in (0,1)\), is monotone in
x. We get the guaranteed minimal growth by
\(t\cdot \gamma _{min}\) in any interval of size
t rounds for an honest-and-synchronized party except with negligible probability in
\(t\cdot \gamma _{min}\) by taking the union bound overall all rounds
r. What remains to prove is that this bound applies also to the growth of the state if one compares any two honest-and-synchronized miners which we do below (still following the proof steps of [
44]).
For the second part of the statement, we generalize the above observation: if we have a guaranteed lower bound \(\tau \) on the average \(\overline{\alpha }_S\) (better than \(\alpha _{min}\) as used before) with respect to any subset of the required size within the given interval \(r,\dots ,r+t\) (note that indeed we only have a bound for the size of S in our experiments but no guarantee that a particularly “good” one is chosen), the second part of the statement follows.
Bound for any honest-and-synchronized party. By Lemma
7.10, we know that if an honest-and-synchronized miner knows some state, then within
\(\Delta \) rounds, every other honest miner will be aware of that state. A similar calculation shows that the lower bound on the time to have a state increase by
T blocks by all honest-and-synchronized parties follows the same law (and hence the perceived ledger speed is the same). By requiring
\(s=r+t-\Delta \) above, and thus considering
\(t':= t- \Delta - c\cdot \Delta = t-(c+1)\Delta \) does not change the asymptotic behavior since
\(\gamma _S t - 1< \gamma _S t - \gamma _S \Delta < \gamma _S t\) for all
t and
S since
\(\Delta \gamma _S < 1\). Hence, this additional additive term can be compensated by choosing a sufficiently small constant
\(\delta \) in Eq. (
2).
\(\square \)
Mining limits. We state some helpful facts about bounds on the mining behavior.
Block withholding. From chain growth and the theorem’s condition, we derive that if an honest-and-synchronized miner adopts a new state that contains a block the adversary obtained by \(\mathcal {F}_{\textsc {StX}} \) then either this block has been published by the adversary before, or it was mined quite recently by a corrupted party.
Chain-growth upper-bound. Our ledger also restricts the growth over time. This is based on the following observation.
Worst-case chain quality. We give a very coarse bound on the overall chain quality in any sequence of T blocks as follows:
Proof
Let us assume that at round r, the state adopted by miner \(P _i\) is \(\vec {\texttt {st}}_{r'} = \texttt {st} _0||\dots ||\texttt {st} _k\). We show that in any sub-sequence of T state blocks \(\texttt {st} _{j+1},\dots ,\texttt {st} _{j+T}\) in \(\vec {\texttt {st}}_{r}\), the fraction of adversarially mined blocks is bounded. Without loss of generality, one can assume that the state \(\vec {\texttt {st}}^{<j}:= \texttt {st} _0||\dots ||\texttt {st} _j\) as well as the state \(\vec {\texttt {st}}^{>j+T}:= \texttt {st} _0||\dots ||\texttt {st} _{j+T+1}\) are mined by honest-and-synchronized miners (or \(j+T\) equals the length of the state). Otherwise, one can enlarge T to meet this condition — this can only increase the fraction of adversarial blocks in the sequence of T blocks and since any state is finite and starts with the genesis block, the condition will be fulfilled for some T. We further assume that \(\vec {\texttt {st}}^{<j}\) is mined at round \(r'\), and that in round \(r'+t\), the state \(\vec {\texttt {st}}^{>j+T}\) appears for the first time as the state, or the prefix of a state, of at least one honest-and-synchronized miner. We conclude that if an adversary successfully extended the state during some round by a new state block \(\texttt {st} _{j+s}\) of the above sequence \(\texttt {st} _{j+1},\dots , \texttt {st} _{j+T}\), then this happens in a round between \(r'\) and \(r'+t\).
We now relate the number
t of rounds to the number
T of blocks. Since
t is assumed to be the minimal number of rounds until the first honest-and-synchronized miner adopted a state containing
\(\texttt {st} _{j+1}\), we can make use of the minimal chain-growth Lemma
7.11 to conclude that the probability that the condition
\(t > \frac{T}{(1-\delta ')\gamma _{min}}\) occurs in such an execution is at most
\(\text {negl}(T)\). We hence have
\(t \le \frac{T}{(1-\delta ')\gamma _{min}}\) with overwhelming probability in
T.
Similar to above, by Lemma
7.12 the time it takes to generate
T blocks is at least
\(t \ge \frac{T}{(1+\delta ) \texttt {T} _{mp}}\) except with probability
\(\text {negl}(T)\) and thus with overwhelming probability, in
\(t \le \frac{T}{(1+\delta )\texttt {T} _{mp}}\), no more than
T blocks are mined.
Furthermore, also by Lemma
7.12, we get a worst-case upper bound. Let
\(N_A^t\) denote the expected value in
t rounds, invoking Lemma
7.12 gives us that
\(N_A^t \le (1+\delta )\beta _{max}t\) except with probability
\(\text {negl}(\beta _{min} t)\) (where we again use the minimum to bound the average of any interval). Hence, since
\(\rho _a \cdot \texttt {T} _{mp}= \beta _{min}\) by definition it follows as in previous lemmata that the bound holds except with probability
\(\text {negl}(T)\).
Putting things together, we conclude that except with negligible probability in
T, the number of times the adversary was successful in extending the state by one block is upper bounded by the quantity
$$\begin{aligned} N_A^{\frac{T}{(1-\delta ')\gamma }} \le \frac{1+\delta }{1-\delta '} \cdot T \cdot \frac{\beta _{max}}{\gamma _{min}}. \end{aligned}$$
Hence, the fraction of adversarial blocks within
T consecutive blocks cannot be more than
\(f = \min \{1, (1+\delta '')\frac{\beta _{max}}{\gamma _{min}}\}\) for any
\(\delta ''\) and sufficiently small constants
\(\delta ,\delta ' >0\), except with negligible probability in the length
T of the sequence.
Since our arguments hold for any interval, the proof is concluded by taking the union bound over the number of such sequences (which is in the order of number of rounds). \(\square \)
Consistency (common prefix). We now state the lemma on the common-prefix property in our setting.
Proof
We again follow the basic line of reasoning in [
44] and adapt the appropriate arguments to our setting. First, since an inconsistency at round
r implies an inconsistency at round
\(r'>r\), if the claim is proven for the case
\(r \le r' \le r+1\), then by an inductive argument, the claim holds for any
\(r'\ge r\).
The protocol mandates that the honest-and-synchronized miners truncates the
T newest blocks from the current respective state. Thus, we need to argue that the block which is
\(T+1\) far away from the head will be part of any state output by any honest-and-synchronized miner. Suppose we are at round
\(r'\) in the protocol, then the time it takes to generate the last
T blocks is at least
\(t \ge \frac{T}{(1+\delta ) \texttt {T} _{mp}}\) except with negligible probability in
T as established in Lemma
7.12 and any
\(0< \delta < 1\).
Looking ahead, we will eventually conclude that with overwhelming probability within the interval of rounds \(s = r-t, \dots , r'\in \{r,r+1\}\) (where \(r\ge t\)), the honest-and-synchronized miners have an opportunity to agree on a common state and hence at round \(r'\), they will still agree on a large common prefix of the current state at round \(r'\).
In the interval of rounds, let this set be denoted as usual by
S, between round
s and round
\(r'=r\), the expected number of rounds, where at lest one honest-and-synchronized miner is successful, is at least
\(\overline{\alpha }_S t\). Thus, again by a standard Chernoff bound, the probability that the number of these successful rounds is smaller than
\(\bar{q}_{min}:= (1-\delta ')\cdot \overline{\alpha }_S t\) is no more than
\(\exp (-\Omega (t\overline{\alpha }_S))\) in the real-world UC random experiment. Again, a coupling argument as in Lemma
7.11 yields that this tail-bound (where the environment activates the least number of parties possible and hence the random variables that describe the success are independent) applies to any environment. Finally, the conditions of the theorem in particular assure that
\(\overline{\alpha }_S > \beta _{min}\) and hence this probability can be upper bounded by
\(\text {negl}(\beta _{min} t)\).
Unfortunately, the “race” between the good guys and the bad guys is not yet conclusively analyzed, since the mere superiority of honestly mined blocks does not imply that the honest parties will reach agreement. In particular, not all of the expected honestly mined blocks are equally useful to obtain a so-called convergence opportunity. In particular, we need to know how many of the honestly mined blocks happen in isolated, sufficiently silent intervals.
Formally, let us introduce the random variable \(R_i\) that measures the number of elapsed round between successful round \(i-1\) and successful round i in the real-world UC execution, where \(R_1\) measures the number of elapsed rounds to the first successful round. Based on \(R_i\), the random variable \(X_i\) is defined as follows: \(X_i = 1\) if and only if \(R_i > \Delta \) and exactly one honest-and-synchronized miner mines a new state (i.e., successfully appends a new block to the state) in the ith successful round.
Let \(E^i_1\) be the event that there is at least one successful round in the interval of \(\Delta \) rounds starting after successful round \(i-1\) (or at the onset of the experiment). Let \(E^i_2\) be the event that strictly more than one miner is successful in the following successful round i.
Overall, our goal is to suitably bound the number of blocks that prevent those events of “success & silence” (i.e., bound the probability of the event \(X_i=0\)) in an interval of t rounds. We call these the undesirable blocks. They have to be infrequent enough such that in combination with adversarially mined blocks, they do not prevent too many convergence opportunities. We hence need to suitably bound the occurrence of the above two bad events \(E^i_j\) in our experiment.
By a union bound, and invoking that \(\alpha _r \le \texttt {T} _{mp}\), we directly have that \(\Pr [X_i=0] = \Pr [E^i_1 \cup E^i_2] \le \Delta \texttt {T} _{mp}+ \texttt {T} _{mp}\), hence, on the positive side, \(\Pr [X_i=1] \ge 1-\texttt {T} _{mp}(\Delta +1)\).
Let
\(X:= \sum _{i=1}^{\bar{q}_{min}} X_i\), and let us define
\(\bar{q}_{min}':= (1-\delta '')\cdot (1-\texttt {T} _{mp}(\Delta +1)) \cdot \bar{q}_{min}\). Since by Eq. (
1) the term
\(1-2(\Delta +1)\texttt {T} _{mp}\) must be positive, we have that
\(\texttt {T} _{mp}(\Delta +1) \le \frac{1}{2}\) and, because
\(\mathcal {F}_{\textsc {StX}} \) treats each new state-submission independently of previous submission, we conclude that
\(\Pr [X_i=1 \,|\, X_1,\dots ,X_{i-1}] \ge \frac{1}{2}\). Since we do not argue here about any particular optimal strategy by an environment-adversary pair
\((\mathcal {Z},\mathcal {A}_{})\), we need to invoke Lemma
7.17 from which we get
$$\begin{aligned} \Pr [X \le \bar{q}_{min}'] \le \exp \left( -(\delta '')^2 \bar{q}_{min}/2\right) . \end{aligned}$$
(3)
To express this w.r.t.
\(\beta _{min}\), observe that not only
\(\alpha _r > \beta _r\) (and thus
\(\alpha _{min} > \beta _{min}\)) by Eq. (
1) but also there is an actual constant
\(0< \widehat{\delta } < 1\) such that
\(\texttt {T} _{mp}(\Delta + 1) < 1-\widehat{\delta }\). This is true since by the theorem condition we deduce that
$$\begin{aligned}&(1-2(\Delta +1)\texttt {T} _{mp}) \ge \lambda (\beta _{min}/\alpha _{min}) \\&\implies 1-\lambda (\beta _{min}/\alpha _{min}) \ge 2(\Delta +1)\texttt {T} _{mp}> (\Delta +1)\texttt {T} _{mp}. \end{aligned}$$
And since
\(\lambda > 1\), i.e., we get can bound the constant by
\(0<\widehat{\delta } < \lambda (\beta _{min}/\alpha _{min})\) and obtain
$$\begin{aligned} (1-\texttt {T} _{mp}(\Delta +1)) \cdot \bar{q}_{min}> \widehat{\delta }(1-\delta ')\cdot \overline{\alpha }_S t > \widehat{\delta }(1-\delta ')\cdot \overline{\beta _S} t. \end{aligned}$$
And hence conclude by Eq. (
3) that
\(\Pr [X \le \bar{q}_{min}'] \le \exp (-\Omega (\beta _{min} t))\). We thus have a (high-probability) lower bound on the number of silent patterns.
We are actually interested in the number of times that
\(X_i = X_{i+1} = 1\). This situation, as already introduced above, means that we have a situation, in which for
\(\Delta \) rounds, no miner is successful, then exactly one honest-and-synchronized miner is successful, and afterward, we again have
\(\Delta \) rounds of silence. This is denoted in [
44] as a
convergence opportunity. For example, a convergence opportunity has the desirable property, that
at the end of such an opportunity, if the adversary is unable to provide a longer state to the honest-and-synchronized miners during this period, all honest-and-synchronized miners will reach an agreement on the current longest state. Thus, in order to prevent this, an adversary needs to be successful in mining roughly at the rate of the number of convergence opportunities within
t rounds.
We have already seen that with overwhelming probability, there are at least
\(\bar{q}_{min}\) successful rounds, and among which
\((\bar{q}_{min}-\bar{q}_{min}')\) can disturb convergence opportunities. Since a single disturbing round can at most prevent two convergence opportunities (it violates the condition for a convergence opportunity with its neighbors in the sequence
\(X_1,\dots ,X_k\)), the number of effective convergence opportunities
C is lower bounded (except with negligible probability) by
$$\begin{aligned}&C \ge \bar{q}_{min} - 2(\bar{q}_{min}-\bar{q}_{min}') = 2 \bar{q}_{min}' - \bar{q}_{min} \\&\ge (1-\delta ')\overline{\alpha }_St[1-2\texttt {T} _{mp}(\Delta +1)-2\delta '']. \end{aligned}$$
For any constant
\(\epsilon \), by picking
\(\delta '\) and
\(\delta ''\) sufficiently small, this yields a bound (except with negligible probability as derived above) of
$$\begin{aligned} C > (1-\epsilon )(1-2\texttt {T} _{mp}(\Delta +1))\overline{\alpha }_S t. \end{aligned}$$
The final argument is a counting argument. Let us denote by
\(\mathcal {S}_{r'}\) the set of maximal states known to
\(\mathcal {F}_{\textsc {StX}} \) at round
\(r'\) (i.e., any path from the root to some a leaf) of length at least
\(\ell + C\), where
\(\ell \) is the length of the longest state known to at least one honest-and-synchronized miner at round
s. Note that
\(\mathcal {S}_{r'}^{\ell +C}\) is non-empty: since each convergence opportunity increases the length by at least one, and before each successful round, there is a period of
\(\Delta \) rounds where no honest miner mines a new state, there has to exist at least one state with length at least
\(\ell +C\) at round
\(r'\).
Assume that the number of successful state extensions made by the adversary (to \(\mathcal {F}_{\textsc {StX}} \)) between round s and \(r'\) is \(T_{\mathcal {A}_{}} < C\). Then, by the pigeonhole principle, for all \(\vec {\texttt {st}} \in \mathcal {S}_{r'}\), it holds that there is at least one block \(\texttt {st} _k\), such that functionality \(\mathcal {F}_{\textsc {StX}} \) is successfully queried by exactly one honest-and-synchronized miner \(P \) in round i to extend the state to length \(k+1\), but no query by the adversary to extend a state of length k to a state of length \(k+1\) has been successful up to and including round \(r'\). Even more, \(T_{\mathcal {A}_{}} < C\) implies that such an i has to exist that also constitutes a convergence opportunity.
After this convergence opportunity at round i, all honest-and-synchronized miners have a state whose first \(k+1\) blocks are \(\vec {\texttt {st}}_i = \texttt {st} _0\dots ,\texttt {st} _k\). Unless the adversary provides an alternative state with a prefix \(\vec {\texttt {st}}_i'\) of length \(k+1\), such that \(\texttt {st} _l' \ne \texttt {st} _l\) for at least one index \(0< l \le k\), no honest-and-synchronized miner will ever mine on a state whose first \(k+1\) blocks do not agree with \(\vec {\texttt {st}}_i\).
The existence of an alternative prefix \(\vec {\texttt {st}}_i'\) of length \(k+1\) for any such i and for all states \(\vec {\texttt {st}} \in \mathcal {S}_{r'}^{\ell +C}\) implies \(T_{\mathcal {A}_{}} \ge C\) and therefore contradicts the assumption that \(T_{\mathcal {A}_{}} < C\).
What is left to prove is that for any such interval of size
t (from round
s to round
\(r'\)), the probability that
\(T_{\mathcal {A}_{}} < C\) holds in any real-world execution except with negligible probability in
\(\beta _{min} t\). Analogously to Lemma
7.12, by the definition
\(\rho _a \cdot \texttt {T} _{mp}= \beta _{min}\) (and recalling that we established a lower bound on
t in the beginning) we get that this error probability is negligible in
T.
First, by Lemma
7.13, for any
\(\omega > 0\), the probability that any new state accepted by an honest-and-synchronized miner during the period of at most
\(t+1\) rounds (from
s to
\(r'\)) is actually a state extension that the adversary withheld since round
\(s-\omega (t+1)\) (or even before) is at most
\(\text {negl}(\beta _{min} t)\). By Lemma
7.12, the number of adversarial blocks (i.e., successful state extensions by
\(\mathcal {A}_{} \)) generated within this slightly larger interval
\(S'\) of size
\(|S'|=(1+\omega ) (t+1)\) rounds is (except with probability
\(\text {negl}(\beta _{min} t)\)) upper bounded by
\(T_{\mathcal {A}_{}} \le (1+\delta )(1+\omega ) (t+1)\overline{\beta }_{S'}\). Also by picking constant
\(\omega \) sufficiently small, we have that
\(|S| \ge (1-\alpha _{max}\Delta )|S'|\) and thus
\(\overline{\alpha }_S\) dominates
\(\overline{\beta }_{S'}\) by the theorem assumptions. We hence get
\(T_{\mathcal {A}_{}} \le \frac{(1+\delta )(1+\omega )}{\lambda } (t+1)\overline{\alpha }_S \cdot (1-2\texttt {T} _{mp}\cdot (\Delta +1))\) by Eq. (
1). By picking the constants
\(\delta \) and
\(\omega \), and
\(\epsilon \) sufficiently small relative to
\(\lambda \), we hence get
\(T_{\mathcal {A}_{}} < C\) except with probability
\(\text {negl}(\beta _{min} t)\). Since our arguments hold for any particular intervals
S, we again apply the union bound over the number of rounds and get the desired claim.
\(\square \)
We used the following useful lemma in the previous proof to bound the deviation with respect to an arbitrary environment (inducing a certain sequence of random variables):
Concluding observations. Finally, we conclude the proof by noting that after a delay of
\(\Delta \) rounds, all honestly multicast transactions are known to all honest-and-synchronized miners and would be included into the next honestly minded block if valid. In the simulation, the simulator also does it in the ideal world and hence will never propose blocks of honest parties that do not comply with the conditions of the defined
\(\textsf {ExtendPolicy} \) of
. Further, the synchronization of a party takes at most
\(\texttt {Delay} =4\Delta \) clock ticks: if
\(P _j\) joins the network, his knowledge of the longest chain and the set of valid transactions relative to that state, which is known to at least one honest and synchronized miner is only reliable after
\(2\Delta \) rounds (
\(4\Delta \) clock ticks) since it takes at most
\(\Delta \) rounds to multicast the initial message that the miner has joined the network, and additional
\(\Delta \) rounds until the replies are received. During this
\(2\Delta \) round the new miner will also have received all messages sent at or after he joined the network, and in particular all transactions that are more than
\(\Delta \) rounds (
\(2\Delta = \frac{\texttt {Delay}}{2}\)) old and potentially valid.
The pointers of honest-and-synchronized parties can also not be too distant, i.e., the slackness is upper bounded by \(\texttt {windowSize} \ge T\) as otherwise we would have a common-prefix violation in that execution (assume the prefix of the chain known to a honest-and-synchronized party was further away than T blocks from the prefix of the actual longest chain, this would yield a fork with substantial probability). The theorem follows. \(\square \)