# Securing Parallel-chain Protocols under Variable Mining Power

Xuechao Wang<EMAIL_ADDRESS>University of Illinois Urbana-Champaign ,
Viswa Virinchi Muppirala<EMAIL_ADDRESS>University of Washington at Seattle
,  Lei Yang<EMAIL_ADDRESS>MIT CSAIL ,  Sreeram Kannan<EMAIL_ADDRESS>University of Washington at Seattle and  Pramod Viswanath
<EMAIL_ADDRESS>University of Illinois Urbana-Champaign

###### Abstract.

Several emerging proof-of-work (PoW) blockchain protocols rely on a “parallel-
chain” architecture for scaling, where instead of a single chain, multiple
chains are run in parallel and aggregated. A key requirement of practical PoW
blockchains is to adapt to mining power variations over time (Bitcoin’s total
mining power has increased by a $10^{14}$ factor over the decade). In this
paper, we consider the design of provably secure parallel-chain protocols
which can adapt to such mining power variations.

The Bitcoin difficulty adjustment rule adjusts the difficulty target of block
mining periodically to get a constant mean inter-block time. While
superficially simple, the rule has proved itself to be sophisticated and
successfully secure, both in practice and in theory (backbone, ; full2020, ).
We show that natural adaptations of the Bitcoin adjustment rule to the
parallel-chain case open the door to subtle, but catastrophic safety and
liveness breaches. We uncover a meta-design principle that allow us to design
variable mining difficulty protocols for three popular PoW blockchain
proposals (Prism (bagaria2019prism, ), OHIE (yu2020ohie, ), Fruitchains
(pass2017fruitchains, )) inside a common rubric.

The principle has three components: (M1) a pivot chain, based on which blocks
in all chains choose difficulty, (M2) a monotonicity condition for referencing
pivot chain blocks and (M3) translating additional protocol aspects from using
levels (depth) to using “difficulty levels”. We show that protocols employing
a subset of these principles may have catastrophic failures. The security of
the designs is also proved using a common rubric – the key technical challenge
involves analyzing the interaction between the pivot chain and the other
chains, as well as bounding the sudden changes in difficulty target
experienced in non-pivot chains. We empirically investigate the responsivity
of the new mining difficulty rule via simulations based on historical Bitcoin
data, and find that the protocol very effectively controls the forking rate
across all the chains.

Correspondence can be sent to<EMAIL_ADDRESS>
##  1\. Introduction

Scaling problem. Built on the pioneering work of Nakamoto, Bitcoin
(nakamoto2008bitcoin, ) is a permissionless blockchain operating on proof-of-
work based on the Nakamoto protocol. The Nakamoto longest-chain protocol was
proven to be secure as long as the adversary controlled less than $50\%$ of
the mining power in the breakthrough work (backbone, ). Recent works
(eyal2016bitcoin, ; sompolinsky2015secure, ; li2018scaling, ) have tried to
improve the scalability of Bitcoin (croman2016scaling, ; bonneau2015sok, ), in
particular the throughput and latency, by redesigning the core consensus
protocol. A variety of approaches have been proposed, for example hybrid
consensus algorithms (schwartz2014ripple, ; gilad2017algorand, ;
mazieres2015stellar, ; pass2017hybrid, ) try to convert the permissionless
problem into a permissioned consensus problem by subselecting a set of miners
from a previous epoch. While such approaches achieve scalability, they are not
natively proof-of-work (PoW) and hence do not retain the dynamic availability,
unpredictability and security against adaptive adversaries that the Nakamoto
longest chain protocol enjoys.

Parallel-chain protocols. An emerging set of proof-of-work protocols maintain
the native PoW property of Bitcoin and achieve provable scaling by using many
parallel chains. The chains run in parallel and use an appropriate aggregation
rule to construct an ordered ledger of transactions out of the various
parallel chains. We will highlight three examples of parallel-chain protocols
(PCP): (1) Prism (bagaria2019prism, ), which achieves high-throughput and low-
latency using a proposer chain and many voter chains, (2) OHIE (yu2020ohie, ),
which achieves high-throughput using parallel chains and (3) FruitChains
(pass2017fruitchains, ), which achieves fairness using two distinct types of
blocks (blocks and fruits) mined in parallel. There are other approaches such
as ledger combiners (fitzi2020ledger, ), which achieve some of the same goals
using different architectures.

Common structure of PCP. In all of these parallel-chain protocols (PCP), there
are multiple types of blocks (for example, in OHIE, each type may correspond
to a different chain) and we determine the final type only after mining the
block - we will term this process as hash sortition. The idea of sortition was
first formalized in (backbone, ) called 2-for-1 PoW. All three PCPs adopt this
technique to achieve parallel mining. A miner creates a single commitment (for
example, a Merkle root) to the potential version of the different block types
and performs a mining operation. Depending on the region the hash falls, the
block is considered mined of a certain type. Different protocols utilize
different types of aggregation rules and semantics in order to consider the
final ledger out of these parallel chains.

Variable mining power problem. A key requirement of deployed PoW blockchains
is to adapt to the immense variation in mining power. For example, the mining
power of Bitcoin increased exponentially by an astonishing factor of $10^{14}$
during its decade of deployment. If Bitcoin had continued to use the same
difficulty for the hash puzzle, then the inter-block time would have fallen
from the original $10$ minutes to $6$ picoseconds. Such a drop would have
caused an intolerable forking rate and seriously undermined the security of
Bitcoin, lowering the tolerable adversarial mining power from nearly $50\%$ to
$10^{-11}$. However, this is prevented by adjusting the difficulty threshold
of Bitcoin using a difficulty adjustment algorithm.

Bitcoin difficulty adjustment algorithm. There are three core ideas to the
Bitcoin difficulty adjustment algorithm: (a) vary the difficulty target of
block mining based on the median inter-block time from the previous epoch (of
$2016$ blocks), (b) use the heaviest chain (calculated by the sum of the block
difficulties) instead of the longest chain to determine the ledger, and (c)
allow the difficulty to be adjusted only mildly every epoch (by an upper bound
of a factor of $4$). While this appears to be a simple and intuitive
algorithm, minor seemingly-innocuous variants turn out to be dangerously
insecure.

Difficulty adjustment terminology. Throughout the paper, we call the hash
puzzle threshold in PoW mining the target of a block. The block difficulty of
each block is measured in terms of how many times the block is harder to
obtain than using the initial target of the system that is embedded in the
genesis block. However, for simplicity, we will adapt the notation of block
difficulty to be the inverse of the target of the block. The chain difficulty
of a chain is the sum of block difficulties of all blocks that comprise the
chain, then each block in the chain covers an interval of chain difficulty.
The chain with the largest chain difficulty is said to be the heaviest chain.
We also refer the chain difficulty of a block as the chain difficulty of the
chain ending at this block. This notation is summarised in the following
table.

Target |  Threshold of the hash puzzle in PoW mining
---|---
Block difficulty |  Inverse of the target of a block
Chain difficulty |  Sum of block difficulties of all blocks in the chain

Difficulty adjustment requires nuanced design. Consider a simpler algorithm
using only (b), i.e., simply let the nodes choose their own difficulty and
then use (b) the heaviest chain rule. At a first glance, this rule appears
kosher - the heaviest chain rule seems to afford no advantage to any node to
manipulate their difficulty. However, this lack of advantage only holds in
expectation, and the variance created by extremely difficult adversarial
blocks can thwart a confirmation rule that confirms deeply-embedded blocks, no
matter how deep, with non-negligible probability proportional to the
attacker’s mining power (refer to Appendix A for a detailed discussion). Now
consider a more detailed rule involving only (a) and (b). It turns out that
there is a difficulty raising attack (refer to Appendix A for a detailed
discussion), where the adversary creates an epoch filled with timestamps
extremely close-together, so that the difficulty adjustment rule from (a) will
set the difficulty extremely high for the next epoch, at which point, the
adversary can utilize the high variance of the mining similar to the
aforementioned attack. This more complex attack is only thwarted using the
full protocol that employs (a), (b) and (c) together. The full proof of the
Nakamoto heaviest chain protocol was obtained in a breakthrough work
(garay2017bitcoin, ).

Difficulty adjustment in PCP. When there are multiple parallel-chains, one
natural idea is to apply Bitcoin’s difficulty adjustment algorithm to each of
the chains independently. However, this idea does not integrate well with hash
sortition since the range of a particular chain will depend on the state of
other chains. Instead, since the mining power variation is the same across all
chains, a natural approach is to use the same difficulty threshold across all
chains, which is then modulated based on past evidence. How should this common
difficulty threshold be chosen? One approach is to utilize inter-block arrival
times across all the chains to get better statistical averaging and respond
faster to mining power variation. However, it requires some sort of
synchronization across the chains and breaks the independence assumption.

General methodology. We propose a general methodology by which to adapt
parallel-chain architectures to the variable mining rate problem. Our general
methodology is comprised of three parts, as detailed below.

  * •

M1: Pivot-chain. Use a single chain as the pivot chain for difficulty
adjustment. Blocks mined in any other chain need to refer to a block in the
pivot chain and use the target inferred therefrom.

  * •

M2: Monotonicity. In a non-pivot chain, blocks can only refer to pivot-chain
blocks of non-decreasing chain difficulty.

  * •

M3: Translation. Wherever the protocol uses the concept of a block’s level, it
is updated to refer to the block’s chain difficulty instead.

Using M1 pivot-chain for difficulty adjustment ensures that we can continue to
use the hash-sortition method. The M2 monotonicity rule ensures that blocks in
non-pivot chain do not refer to stale/old pivot blocks with target which is
very different from expected in the present round. Finally, the M3 translation
rule ensures that other aspects of the protocol, such as the confirmation rule
are adapted correctly to deal with the variable difficulty regime correctly.
We show in Section 3 why each of the three aspects of our methodology is
critical in designing variable difficulty for Prism by showing attacks for
subsets of M1,M2, and M3.

On the positive side, we show a concrete adaptation of our general methodology
to various schemes, in particular to Prism in Section 3, to OHIE in Section 4
and to FruitChains  in Section 5.

Security proofs. The problem of analyzing the difficulty adjustment mechanism
in Bitcoin was first addressed in (garay2017bitcoin, ) in the lock-step
synchronous communication model. It introduces a setting where the number of
participating parties’ rate of change in a sequence of rounds is bounded but
follows a predetermined schedule. Later two concurrent works (full2020, ;
chan2020Varying, ) analyzed the problem in a bounded-delay network with an
adaptive (as opposed to predetermined) dynamic participation, with different
proof techniques. Following the two later papers, we adopts the more general
network and adversary models: we assume a $\Delta$-synchronous communication
model, where every message that is received by a honest node is received by
all other honest nodes within $\Delta$ rounds; we allow the adversary to
control the mining rate even based on the stochastic realization of the
blockchain, as long as the mining rate does not change too much in a certain
period of time. We assume that the adversarial nodes are Byzantine and they do
not act rationally. Under this general model, we establish that our proposed
modification to Prism, OHIE and FruitChains  satisfy the dual security
properties of safety and liveness. The proofs require a new understanding of
how difficulty evolution in a non-pivot chain progresses based on the
difficulty in the pivot chain - this statistical coupling presents a
significant barrier to surmount in our analysis, and differs from previous
work in this area. We show these results in Section 6.

Systems implementation. Our variable difficulty scheme does not add
significant computation and communication overhead on existing parallel-chain
protocols, making our protocol an easy upgrade. We conduct extensive
simulation studies to examine how our systems respond to varying mining power.
Results show that our scheme is able to closely match the system mining power
and the mining difficulty for each individual chain, thus keeping the chain
forking rate stable. We examine adversarial behavior and how it can influence
the difficulties of various chains, and confirm that our scheme is secure
against significant adversarial presence. The simulations are based on
historical Bitcoin mining power data and parameters collected from real-world
experiments of the Prism (prism-system, ) parallel-chain protocol, making the
insights meaningful for real-world systems.

Other related works. A recently proposed blockchain protocol Taiji
(li2020taiji, ) combines Prism with a BFT protocol to construct a dynamically
available PoW protocol which has almost deterministic confirmation with low
latency. Since Taiji inherits the parallel-chain structure from Prism, our
meta-principles will also apply. The vulnerability of selfish mining has
recently been discussed on several existing blockchain projects with variable
difficulty in (negy2020selfish, ). Our proposed variable difficulty
FruitChains  protocol guarantees fairness of mining, thus disincentivizes
selfish mining.

##  2\. Model

Synchronous network. We describe our protocols in the now-standard
$\Delta$-synchronous network model considered in (pass2017analysis, ;
full2020, ; badertscher2018ouroboros, ) for the analysis of proposed variable
difficulty protocols, where there is an upper bound $\Delta$ in the delay
(measured in number of rounds) that the adversary may inflict to the delivery
of any message. Observe that notion of “rounds” still exist in the model
(since we consider discretized time), but now these are not synchronization
rounds within which all messages are supposed to be delivered to honest
parties.

Similar to (full2020, ; pass2017analysis, ), the protocol execution proceeds
in “round” with inputs provided by an environment program denoted by
${\mathcal{Z}}(1^{\kappa})$ to parties that execute the protocol $\Pi$, where
$\kappa$ is a security parameter. The adversary ${\mathcal{A}}$ is adaptive,
and allowed to take control of parties on the fly, as well as “rushing”,
meaning that in any given round the adversary gets to observe honest parties’
actions before deciding how to react. The network is modeled as a diffusion
functionality similar to those in (full2020, ; pass2017analysis, ): it allows
order of messages to be controlled by ${\mathcal{A}}$, i.e., ${\mathcal{A}}$
can inject messages for selective delivery but cannot change the contents of
the honest parties’ messages nor prevent them from being delivered beyond
$\Delta$ rounds of delay — a functionality parameter.

Random oracle. We abstract the hash function as a random oracle functionality.
It accepts queries of the form $(\texttt{compute},x)$ and
$(\texttt{verify},x,y)$. For the first type of query, assuming $x$ was never
queried before, a value $y$ is sampled from $\\{0,1\\}^{\kappa}$ and it is
entered to a table $T_{H}$. If $x$ was queried before, the pair $(x,y)$ is
recovered from $T_{H}$. In both cases, the value $y$ is provided as an answer
to the query. For the second type of query, a lookup operation is performed on
the table. Honest parties are allowed to ask one query per round of the type
compute and unlimited queries of the type verify. The adversary
${\mathcal{A}}$ is given a bounded number of compute queries per round and
also unlimited number of verify queries. The bound for the adversary is
determined as follows. Whenever a corrupted party is activated the bound is
increased by 1; whenever a query is asked the bound is decreased by 1 (it does
not matter which specific corrupted party makes the query).

Adversarial control of variable mining power. We assume no rational node in
the adversarial model. The adversary can decide on the spot how many honest
parties are activated adaptively. In a round $r$, the number of honest parties
that are active in the protocol is denoted by $n_{r}$ and the number of
corrupted parties controlled by ${\mathcal{A}}$ in round $r$ is denoted by
$t_{r}$. Note that $n_{r}$ can only be determined by examining the view of all
honest parties and is not a quantity that is accessible to any of the honest
parties individually. We make the “honest majority” assumption, i.e.,
$t_{r}<(1-\delta)n_{r}$ for all $r$, where the positive constant $\delta<1$ is
the advantage of honest parties. Further, we will restrict the environment to
fluctuate the number of parties in a certain limited fashion. Suppose
${\mathcal{Z}},{\mathcal{A}}$ with fixed coins produces a sequence of parties
$n_{r}$, where $r$ ranges over all rounds of the entire execution, we define
the following notation.

###### Definition 2.1.

Let $r_{\rm max}\in\mathbb{N}$ is the total number of rounds in the execution.
For $\gamma\in\mathbb{R}^{+}$, we call $(n_{r}),r\in[0,r_{\rm max}]$, as
$(\gamma,s)$-respecting if for any set $S\subseteq[0,r_{\rm max}]$ of at most
$s$ consecutive rounds,

$\max_{r\in S}\ n_{r}\leq\gamma\min_{r\in S}\ n_{r}.$

We say that ${\mathcal{Z}}$ is $(\gamma,s)$-respecting if for all
${\mathcal{A}}$ and coins for ${\mathcal{Z}}$ and ${\mathcal{A}}$ the sequence
of honest parties $n_{r}$ is $(\gamma,s)$-respecting.

##  3\. Prism

###  3.1. Fixed Difficulty Algorithm

Each block in the longest chain of the Bitcoin protocol performs dual roles:
Proposing and Voting. A proposed block gets confirmed with high reliability
only after the block, and several more blocks extending it make it in the
longest chain. The latency of the protocol is the number of blocks for which
one needs to wait (this number depends on the reliability). To guarantee
security, the mining rate remains low (backbone, ), which leads to low
throughput and high latency. Prism (bagaria2019prism, ) is a Proof-of-Work
protocol that decouples block proposals and voting to scale throughput and
latency. We will briefly explain the Prism as it was originally described in
the fixed mining rate, i.e., fixed difficulty regime. As show in Figure 1,
Prism runs multiple $m+1$ separate parallel “blocktrees” where one of the
trees, called the proposer tree, consists of blocks from which the final
transaction ledger is constructed. We define a block’s level in the proposer
tree as the block’s depth from the genesis. The final transaction ledger will
comprise of one proposer block at each level chosen by the longest chain in
each of the $m$ voter blocktrees; they are referred to as voter chains. A
voter block in any voter blocktree can vote for one or more proposer blocks at
different levels by including a pointer to the corresponding proposer blocks
in its payload. A voter block can also consist of a null vote if the chain it
entered already voted on the latest level. At a given level of the proposer
tree, a voter chain can vote for exactly one proposer block. The net vote for
a proposer block can be counted by aggregating which of the $m$ voter chains
voted for that block. The block with the most votes at any particular level is
termed as the leader block for that level, and the ledger is constructed by
concatenating the leader blocks at various levels.

Mining and sortition. In order to ensure that the adversary cannot focus the
mining power onto a single chain, a “sortition” mechanism is used. A miner
creates a “super-block” containing information about its parent block in each
of the $m+1$ trees. Each tree has a target of $T$, and for $1\leq i\leq m$ if
a node creates a block of hash value in between $iT$ and $(i+1)T$, it will be
able to mine this block in the voter block-tree $i$. If it creates a block of
hash value less than $T$, it will be able to mine this block in the proposer
block-tree as show in Figure 1.

Figure 1. Fixed difficulty Prism. Snapshot of a miner’s view of Prism block-
trees. The confirmed blocks are darker in color and the votes are shown using
dotted arrows.

The structure of this voting scheme in Prism enables low confirmation latency.
The high-level idea is that votes accrue only sequentially in Bitcoin, whereas
in Prism, votes accrue parallelly. Thus for a given amount of security,
confirmation only needs to wait for a much shorter amount of time (since
voting blocks are created in parallel), thus reducing the amount of latency.

###  3.2. Natural Approaches Are Insecure

Different difficulty adjustment for different chains (no M1). To add support
for variable mining power to Prism, a natural first approach is to replace the
longest chain rule (backbone, ) by the heaviest chain rule (full2020, ) in all
the parallel chains, and adjust the mining difficulty in each chain
separately. However, miners in Prism use cryptographic sortition to mine
blocks on all chains at the same time, and having different thresholds for
different chains depending on the state will require complex coupling across
chains. Furthermore, since the mining power variation is the same across
different chains, it is efficient to have a single difficulty threshold across
the entire system.

As we explained in the introduction, our general methodology for converting a
fixed-difficulty protocol into a variable-difficulty protocol comprises of
three attributes M1: Pivot-chain, M2: Monotonicity and M3: Translation. We
will now explore the subtleties inherent in this process and show why a subset
of these attributes is insufficient for Prism.

M1 without M2 $\Rightarrow$ Safety failure. To make the cryptographic
sortition technique applicable, a straightforward approach is to use the
proposer chain as a pivot chain for difficulty adjustment (M1): the difficulty
of the proposer blocks is adjusted according to the Bitcoin rule (full2020, ),
and the difficulty of voter blocks tracks that of the proposer chain by
reference links. However, if we allow the miners to use the difficulty of any
proposer block for the voter blocks, then safety failures may occur on the
voter chains. We demonstrate an example safety failure here. Let the honest
parties maintain the difficulty $d_{0}$ throughout the execution, and the
adversary mines private proposer blocks with timestamps in rapid succession to
increase the difficulty to $d_{0}*k$, where $k$ is a desired security
parameter on the voter chains (i.e., we hope that a $k$-deep voter block will
be stable forever). Even if the adversary cannot keep up the chain difficulty
of its private proposer chain with the heaviest public chain, at the current
time on the voter chain, the adversary will refer to this very difficult block
on the proposer tree to create a very difficult block on the voter tree. If
the adversary is lucky and mines one voter block with difficulty $d_{0}*k$,
the probability of which is a constant rather than exponentially decaying in
$k$ (via the same anti-concentration argument in Appendix A), then it can
overtake the heaviest voter chain and reverse a $k$-deep voter block. This
attack is described in Figure 2. To address this issue, we require that on
each voter chain the referred proposer blocks should have non-decreasing chain
difficulty (M2), so that the adversary can no longer adopt an old mining
difficulty from the proposer chain. With M2, although the adversary may not
refer to the tip of the proposer chain, both our analysis in Section 6.4 and
the simulation in Section 7.3 show that the security of the voter chain can
still be guaranteed.

Figure 2. Attack on safety when we enforce M1 but not M2. At the current time,
the adversary will choose a very difficult proposer block in a less heavier
chain as its proposer-parent in the voter chain, hurting the ledger’s
security. The dotted arrows represent the relation between the voter blocks
and their proposer parents.

Voting rule: No M3 $\Rightarrow$ Liveness Failure. In fixed difficulty Prism,
a voter block votes on all levels in the proposer tree that are unvoted by the
voter block’s ancestors. In the variable difficulty algorithm, while the
notion of “level” on the proposer chain is well-defined an adversary can
always mine a very long but easy proposer chain. As a result, if we still
order proposer blocks by level, the leader sequence will be full of
adversarial blocks, which may cause liveness failure as described in Figure 3.
A natural generalization would be that voter blocks vote for each difficulty
value rather than level and the leader sequence is also decided for each
difficulty value (M3). See the complete algorithm in the next subsection.

Figure 3. Attack on liveness when M1, M2 are enforced but not M3. The
adversary lowers the block difficulty and advances in level on the proposer
tree. The voter blocks will not be able to vote for any honest blocks, hurting
the ledger’s liveness.

###  3.3. Variable Difficulty Algorithm

We now describe the full Prism protocol for the variable difficulty setting
constructed using our general methodology. We refer the reader to Appendix F
for a pseudocode of the algorithm. There are two types of blocks in Prism
blockchain: proposer blocks and voter blocks. Proposer blocks contain
transactions that are proposed to be included in the ledger, and constitutes
the skeleton of Prism blockchain. Voter blocks are mined on $m$ separate voter
blocktrees, each with its own genesis block. We say a voter block votes on a
proposer block $B$ if it includes a pointer to $B$ in its payload.

Block proposal rule. The proposer chain follows the heaviest chain rule, and
the difficulty adjustment uses the target calculation function defined in
(full2020, ) with parameter $\Phi$ and $\tau$, where $\Phi$ is the length of
an epoch in number of blocks and $\tau\geq 1$ is the dampening filter (line 14
in Algorithm 2). All $m$ voter chains also follow the heaviest chain rule, but
the difficulty adjustment on voter chains is more tricky and we will discuss
it soon when introducing sortition.

Whereas Bitcoin miners mine on a single blocktree, Prism miners simultaneously
mine one proposer block and $m$ voter blocks via cryptographic sortition. More
precisely, while mining, each miner selects $m+1$ parent blocks, which are the
tips of the heaviest chains on the proposer tree and the $m$ voter trees. We
call these tips proposer parent and voter parents separately. And the miner
maintains outstanding content for each of the $m+1$ possible mined blocks: For
the proposer block, the content is a list of transactions; For the voter block
on the $i$-th voter tree, the content is a list of hashes of proposer blocks
at each difficulty in the proposer blocktree that has not yet received a vote
in the heaviest chain of the $i$-th voter tree. More precisely, on the $i$-th
voter tree, if the last proposer block voted by the heaviest chain covers the
difficulty interval $(a_{0},b_{0}]$ and the proposer parent covers
$(a^{*},b^{*}]$, then a valid voter block on the $i$-th voter tree must
satisfy the following conditions (see Algorithm 4).

  * •

If $b^{*}=b_{0}$, then it should contain no vote.

  * •

If $b^{*}>b_{0}$, then it should vote for an arbitrary number of proposer
blocks $B_{1},B_{2},\cdots,B_{n}$, each covering $(a_{1},b_{1}],$
$(a_{2},b_{2}],$ $\cdots,$ $(a_{n},b_{n}]$, such that $a_{i}<b_{i-1}<b_{i}$
for all $1\leq i\leq n$ and $b_{n}=b^{*}$.

Figure 4. A miner’s view of Prism block-trees with variable chain difficulty.
The confirmed blocks are darker in color. Both the votes and proposer-parent
links are shown using the same dotted arrows.

Upon collecting this content, the miner tries to generate a block with target
according to the proposer parent via proof-of-work (M1). Once a valid nonce is
found, the output of the hash is deterministically mapped to either a voter
block in one of the $m$ trees or a proposer block (lines 19-25 in Algorithm
2).

While mining, nodes may receive blocks from the network, which are processed
in much the same way as Bitcoin. For a received voter block to be valid, the
chain difficulty of its proposer parent must be at least that of the proposer
parent of its voter parent (M2). Upon receiving a valid voter block, the miner
updates the heaviest chain if needed, and updates the vote counts accordingly.
Upon receiving a valid proposer block $B$ with chain difficulty higher than
the previous heaviest chain, the miner makes $B$ the new proposer parent, and
updates all $m$ voter trees to vote for chain difficulties until $B$.

Ledger formation rule. Note that all the voters on one voter chain may cover
overlapping intervals. So we first sanitize them into disjoint intervals: For
$n$ consecutive valid votes $(a_{1},b_{1}],$ $(a_{2},b_{2}],$ $\cdots,$
$(a_{n},b_{n}]$ on a voter chain, we sanitize them into new intervals
$(a_{1},b_{1}],(b_{1},b_{2}],\cdots,(b_{n-1},b_{n}]$. In this way, we make
sure that each real-valued difficulty $d$ is voted at most once by each voter
chain, hence $d$ can receive at most $m$ votes. Since voter blocks vote for
each difficulty value rather than level, the ledger is also generated based on
difficulty values (M3). Let $v_{i}(d)$ be the proposer block with interval
containing $d$ voted by the heaviest chain on the $i$-th voter tree. Let
$\ell(d)$ be the leader block of difficulty $d$, which is the plurality of the
set $\\{v_{i}(d)\\}_{i=1}^{m}$. For each proposer block $B_{p}$ in the
proposer tree, define $g(B_{p})$ as

(1) $g(B_{p})=\inf_{d\geq 0}\\{d:\ell(d)=B_{p}\\}.$

Note that if $\\{d:\ell(d)=B_{p}\\}$ is empty, then $g(B_{p})=\infty$.
Finally, by sorting all proposer blocks by $g(\cdot)$, we get the leader
sequence of the proposer blocks. A concrete example of this ledger formation
rule is shown in Figure 5.

Operationally, we only need to count votes for intervals in the atomic
partition of all intervals covered by the proposer blocks. After finding the
leader block for each atomic interval, we can get the leader sequence by
sanitizing the repeated proposer blocks.

Figure 5. An example of the ledger formation rule in Prism. For simplicity, we
only have one voter chain in the example. The number inside each proposer
block is the block difficulty. In this example, the heaviest proposer chain
has chain difficulty 5. We find the leader block $\ell(d)$ for each difficulty
level $d$ in $(0,5]$ according to the votes (as shown in the first table).
Then we find the grade $g(\cdot)$ of each proposer block by Equation (1) as
shown in the second table. Finally, the proposer blocks are ordered by their
grades.

Main result: persistence and liveness of Prism (Informal) We show that Prism
generates a transaction ledger that satisfies persistence and liveness in a
variable mining power setting in Theorem 6.17.

##  4\. OHIE

###  4.1. Fixed Difficulty Algorithm

OHIE (yu2020ohie, ) composes $m$ parallel instances of Bitcoin longest chains.
Each chain has a distinct genesis block, and the chains have ids from $0$ to
$m-1$. Similar to Prism, OHIE also uses cryptographic sortition to ensure that
miners extend the $m$ chains concurrently and they do not know which chain a
new block will extend until the PoW puzzle is solved.

Each individual chain in OHIE inherits the proven security properties of
longest chain protocol (backbone, ), and all blocks on the $m$ chains
confirmed by the longest chain confirmation rule (eg. the $k$-deep rule) are
called partially-confirmed. However, this does not yet provide a total
ordering of all the confirmed blocks across all the $m$ chains in OHIE. The
goal of OHIE is to generate a sequence of confirmed blocks (SCB) across all
$m$ parallel chains. Once a partially-confirmed block is added to SCB, it
becomes fully-confirmed.

In OHIE, each block has two additional fields used for ordering blocks across
chains, denoted as a tuple $({\tt rank},\,\,{\tt next\\_rank})$. In SCB, the
blocks are ordered by increasing ${\tt rank}$ values, with tie-breaking based
on the chain ids. For any new block $B$ that extends from its parent block
denoted as ${\tt parent}(B)$, we directly set $B$’s ${\tt rank}$ to be the
same as ${\tt parent}(B)$’s ${\tt next\\_rank}$. A genesis block always has
${\tt rank}$ of $0$ and ${\tt next\\_rank}$ of $1$. Properly setting the ${\tt
next\\_rank}$ of a new block $B$ is the key design in OHIE. Let $\mathcal{B}$
be the set of all tips of the $m$ longest chains before $B$ is added to its
chain, then the ${\tt next\\_rank}$ of $B$ is given by

${\tt next\\_rank}(B)=\max\\{{\tt
rank}(B)+1,\max_{B^{\prime}\in\mathcal{B}}\\{{\tt
next\\_rank}(B^{\prime})\\}\\}.$

If $B$ copies the ${\tt next\\_rank}$ of a block $B^{\prime}$ on a chain with
different id, then a reference link to $B^{\prime}$ (or the hash of
$B^{\prime}$) is added into $B$. In the example of Figure 6, when B11 is
mined, B04 has the highest ${\tt next\\_rank}$, so B11 copies the ${\tt
next\\_rank}$ of B04 and has a reference link to B04.

OHIE generates a SCB in the following way. Consider any given honest node at
any given time and its local view of all the $m$ chains. Let $y_{i}$ be the
${\tt next\\_rank}$ of the last partially-confirmed block on chain $i$ in this
view. Let ${\tt confirm\\_bar}\leftarrow\min_{i=1}^{k}y_{i}$. All partially-
confirmed blocks whose rank is smaller than ${\tt confirm\\_bar}$ are deemed
fully-confirmed and included in SCB. Finally, all the fully-confirmed blocks
will be ordered by increasing ${\tt rank}$ values, with tie-breaking favoring
smaller chain ids. As an example, in Figure 6, we have
$y_{0}=4,y_{1}=7,y_{2}=9$, hence ${\tt confirm\\_bar}$ is $4$. Therefore, the
$8$ partially-confirmed blocks whose ${\tt rank}$ is below $4$ become fully-
confirmed.

Figure 6. OHIE with fixed difficulty. Each block has a tuple $({\tt
rank},\,\,{\tt next\\_rank})$. In this figure, a block that is at least 2-deep
in its chain is partially-confirmed. The blocks arrive in this order: B00,
B10, B20, B01, B02, B03, B04, B11, B12, B13, B14, B21, B22, B23. Figure 7.
OHIE with variable difficulty. Each block has a tuple $({\tt rank},\,\,{\tt
next\\_rank})$. In this figure, a block that is at least 2-deep in its chain
is partially-confirmed. The width of a block represents its mining difficulty.
Different from the fixed difficulty algorithm, the mining difficulty is
adjusted every 3 blocks on chain 0; Each block $B$ on chain $i$ ($i>0$) has a
chain 0 parent (shown by the red reference link), which decides the mining
difficulty of $B$. The blocks arrive in this order: B00, B10, B20, B11, B01,
B02, B03, B04, B12, B13, B21, B05, B14, B22.

###  4.2. Variable Difficulty Algorithm

Following the same meta-principle of designing variable difficulty Prism, we
can also turn the fixed difficulty OHIE into a variable difficulty algorithm
by making the following changes.

  * •

Each individual chain follows the heaviest chain rule instead of the longest
chain rule.

  * •

The mining difficulty of chain 0 is adjusted the same way as the Bitcoin rule
(full2020, ).

  * •

Following our design principle M1, each block $B$ on chains $1,2,...,(m-1)$
will also have a chain 0 parent $\hat{B}$ (assigned before mining). The mining
difficulty of $B$ is the same as the difficulty used to mine a child block of
$\hat{B}$. To prevent the adversary from adopting an old mining difficulty
from chain 0, we require that on each chain the referred chain 0 parent should
have non-decreasing chain difficulty (M2). As an example in Figure 7, each
block on chain 1 and chain 2 refers to (shown in red dashed arrow) a chain 0
parent with non-decreasing chain difficulty, which decides the mining
difficulty of the block.

  * •

A straightforward adoption on how to decide the ${\tt next\\_rank}$ of a block
would follow from our design principle M3. Let $\mathcal{B}$ be the set of all
tips of the $m$ heaviest chains before $B$ is added to its chain, then the
${\tt next\\_rank}$ of $B$ is given by

${\tt next\\_rank}(B)=\max\\{{\tt rank}(B)+{\rm
diff}(B),\max_{B^{\prime}\in\mathcal{B}}\\{{\tt
next\\_rank}(B^{\prime})\\}\\}.$

If $B$ copies the ${\tt next\\_rank}$ of a block $B^{\prime}$ on a chain with
different id, then a reference link to $B^{\prime}$ (or the hash of
$B^{\prime}$) is added into $B$. Note that $B^{\prime}$ may be different from
$B$’s chain 0 parent, eg. B21 in Figure 7. We point out that this design is
not necessary for the security analysis, but it is a very natural choice.

Main result: persistence and liveness of OHIE (Informal) We show that OHIE
generates a transaction ledger that satisfies persistence and liveness in a
variable mining power setting in Theorem D.2.

##  5\. FruitChains

###  5.1. Fixed Difficulty Algorithm

The FruitChains  protocol was developed in order to solve the selfish mining
problem and develop incentives which are approximately a Nash equilibrium. A
key underlying step in FruitChains  is to ensure that a node that controls a
certain fraction of mining power receives reward nearly proportional to its
mining power, irrespective of adversarial action. FruitChains  runs an
instance of Nakamoto consensus but instead of directly putting the
transactions inside the blockchain, the transactions are put inside “fruits”
and fruits are included by blocks. Mining fruits also requires solving some
PoW puzzle. Similar to Prism and OHIE, the FruitChains  protocol also uses
cryptographic sortition to ensure that miners mine blocks and fruits
concurrently and they do not know the type of the blocks until the puzzle is
solved. Additionally, a fruit is required to “hang” from a block which is not
too far from the block which includes the fruit.

In FruitChains, each of the fruit will have two parent blocks, we call them
fruit parent and block parent: the fruit parent is a recently
stabilized/confirmed block that the fruit is hanging from; the block parent
should be the tip of the longest chain. A block will also have a fruit parent
because the fruit mining and block mining are piggybacked atop each other, but
a block actually does not care about this field. See Figure 8 for
illustration. We say that a fruit $B_{f}$ is recent w.r.t. a chain
${\mathcal{C}}$ if the fruit parent of $B_{f}$ is a block that is at most $R$
deep in ${\mathcal{C}}$, where $R$ is called the recency parameter. The
FruitChains  protocol requires that blocks only include recent fruits.
Intuitively, the reason why fruits need to be recent is to prevent the “fruit
withhold attack”: without it, an attacker could withhold fruits, and suddenly
release lots of them at the same time, thereby creating a very high fraction
of adversarial fruits in some segment of the chain.

Figure 8. The FruitChains  protocol.

We term a blockchain protocol as fair if players controlling a $\phi$ fraction
of the computational resources will reap a $\phi$ fraction of the rewards.
Intuitively, the reason why the FruitChains  protocol guarantees fairness is
that even if an adversary tries to “erase” some block mined by an honest
player (which contains some honest fruits), by the liveness of the longest
chain protocol, eventually an honest player will mine a new block including
those fruits and the block will be stable – in fact, by setting the recency
parameter $R$ reasonably large, we can make sure that any fruit mined by an
honest player will be included sufficiently deep in the chain. And further, if
rewards and transaction fees are evenly distributed among the fruits in the
long segment of the chain, then the FruitChains  protocol guarantees fairness.

###  5.2. Variable Difficulty Algorithm

Following our meta-principles, we can also turn the fixed difficulty
FruitChains  into a variable difficulty algorithm by making the following
changes.

  * •

The underlying blockchain protocol follows the heaviest chain rule instead of
the longest chain rule, i.e., the block parent of a block/fruit is the tip of
the heaviest chain.

  * •

The mining difficulty is adjusted the same way as the Bitcoin rule (full2020,
), and the block/fruit mining will use the same mining difficulty, or the
difficulties of fruit and block will remain the same ratio (M1).

  * •

A fruit $B_{f}$ is recent w.r.t. a chain ${\mathcal{C}}$ at round $r$ if the
fruit parent of $B_{f}$ is in ${\mathcal{C}}$ and has timestamp at least
$r-R$, where $R$ is called the recency parameter. And again, blocks only
include recent fruits, i.e., a block $B$ with timestamp $r$ is valid if for
all fruits $B_{f}\in B$, the fruit parent of $B_{f}$ has timestamp at least
$r-R$.

If rewards and transaction fees are designed to distribute proportional to the
fruit difficulty in a sufficiently long segment of the chain, then the
variable difficulty FruitChains  protocol guarantees fairness under a variable
mining power setting. This is where the meta-principle M3 kicks in. In the
fixed difficulty setting, the reward is distributed equally among all fruit
miners equally in a window of blocks. In the variable difficulty setting, the
reward is distributed proportional to the difficulty of the fruits. To model
this in our calculation of fairnesss, we say that the variable difficulty
protocol is fair if the fraction of difficulty of fruits of a given miner in a
window is approximately proportional to its mining power. Note that
monotonicity condition (M2) does not apply to variable difficulty FruitChains
as there is no chaining structure among the fruits. But the recency condition
on the fruits has the same effect and does prevent the adversary from adopting
an old mining difficulty for fruits.

Main result: persistence, liveness and fairness of FruitChains  (Informal) We
show that FruitChains  generates a transaction ledger that satisfies
persistence, liveness and fairness in a variable mining power setting in
Appendix E.

##  6\. Security Analysis

###  6.1. Desired Security Properties

###### Notation 6.1.

We denote by ${\mathcal{C}}^{\lceil\ell}$ the chain resulting from “pruning”
the blocks with timestamps within the last $\ell$ rounds. If
${\mathcal{C}}_{1}$ is a prefix of ${\mathcal{C}}_{2}$, we write
${\mathcal{C}}_{1}\prec{\mathcal{C}}_{2}$. The latest block in the chain
$\mathcal{C}$ is called the head of the chain and is denoted by
head$(\mathcal{C})$. We denote by ${\mathcal{C}}_{1}\cap{\mathcal{C}}_{2}$ the
common prefix of chains ${\mathcal{C}}_{1}$ and ${\mathcal{C}}_{2}$. We say
that a chain $C$ is held by or belongs to an honest party if it is one of the
heaviest chains in its view.

The following two properties called common prefix and chain quality, are
essential in proving the persistence and liveness of the transaction ledger.
The common prefix property states that any two honest parties’ chains at two
rounds have the earlier one subsumed in the later as long as the last a few
blocks are removed, while chain quality quantifies the contributions of the
honest parties to any sufficiently long segment of the chain.

###### Definition 6.2 (Common Prefix).

The common prefix property with parameter $\ell_{\rm cp}\in\mathbb{N}$ states
that for any two honest players holding chains ${\mathcal{C}}_{1}$,
${\mathcal{C}}_{2}$ at rounds $r_{1}$, $r_{2}$, with $r_{1}\leq r_{2}$, it
holds that ${\mathcal{C}}_{1}^{\lceil\ell_{\rm cp}}\prec{\mathcal{C}}_{2}$.

###### Definition 6.3 (Chain Quality).

The chain quality property is defined for two parameters $\ell_{\rm
cq}\in\mathbb{N}$ and $\mu\in\mathbb{R}$. Let $\mathcal{C}$ be a chain held by
any honest party at round $r$ and let $S_{0}\subseteq[0,r]$ be an interval
with at least $\ell_{\rm cq}$ consecutive rounds. Let ${\mathcal{C}}(S_{0})$
be the segment of ${\mathcal{C}}$ containing blocks with timestamps in $S_{0}$
and $d$ be the total difficulty of all blocks in ${\mathcal{C}}(S_{0})$. The
chain quality property states that the honest blocks in ${\mathcal{C}}(S_{0})$
have a total difficulty of at least $\mu d$.

In the context of Prism, let $\texttt{LedSeq}_{d}(r)$ be the leader sequence
up to difficulty level $d$ at round $r$. And the leader sequence at the end of
round $r_{\rm max}$, the end of the protocol execution, is the final leader
sequence, $\texttt{LedSeq}_{d}(r_{\rm max})$. Then similar to a single chain,
we can define the following properties on the leader sequence.

###### Definition 6.4 (Leader Sequence Common Prefix ).

The leader sequence common prefix property with parameter $\ell_{\rm
lscp}\in\mathbb{N}$ states that for a fixed difficulty level $d$, let $R_{d}$
be the first round in which a proposer block covering $d$ was received by all
honest players, then it holds that

(2) $\texttt{LedSeq}_{d}(r)=\texttt{LedSeq}_{d}(r_{\rm max})\quad\forall r\geq
R_{d}+\ell_{\rm lscp}.$

###### Definition 6.5 (Leader Sequence Quality).

The leader sequence property is defined for two parameters $\ell_{\rm
lsq}\in\mathbb{N}$ and $\mu\in\mathbb{R}$. Let $\mathcal{C}$ be a proposer
chain held by any honest party at round $r$ and let $D$ be the difficulty
range covered by all blocks in ${\mathcal{C}}$ with timestamps in the last
$\ell_{\rm lsq}$ rounds. The leader sequence quality property states that
leader blocks mined by honest players cover at least $\mu$ fraction of $D$.

Our goal is to generate a robust transaction ledger that satisfies persistence
and liveness as defined in (backbone, ; yu2020ohie, ).

###### Definition 6.6 (from (backbone, ; yu2020ohie, )).

A protocol $\Pi$ maintains a robust public transaction ledger if it organizes
the ledger as a blockchain of transactions and it satisfies the following two
properties:

  * •

(Persistence) Consider the confirmed ledger $L_{1}$ on any node $u_{1}$ at any
round $r_{1}$, and the confirmed ledger $L_{2}$ on any node $u_{2}$ at any
round $r_{2}$ (here $u_{1}$ ($r_{1}$) may or may not equal $u_{2}$ ($r_{2}$)).
If $r_{1}+\Delta<r_{2}$, then $L_{1}$ is a prefix of $L_{2}$.

  * •

(Liveness) Parameterized by $u\in\mathbb{R}$, if a transaction tx is received
by all honest nodes for more than $u$ rounds, then all honest nodes will
contain tx in the same place in the confirmed ledger.

###  6.2. Proof Sketch

Figure 9. Proof sketch for Prism. M1, M2 and M3 are crucial in proving these
properties for the leader sequence.

Since there is a pivot chain in all three protocols (by M1), the first step of
our analysis is to prove some desired properties (including chain growth,
common prefix, and chain quality) of the pivot chain. As the pivot chain just
follows the difficulty adjustment rule as in Bitcoin, we can directly borrow
results from a beautiful paper (full2020, ). The key step is to show that by
adopting the heaviest pivot chain, honest nodes are always mining with
“reasonable” block difficulties (this is formally defined as Good round/chain
in Section 6.3). We state all the useful lemmas and summarize the proof from
(full2020, ) in Appendix B.

The key technical challenge involves analyzing the properties of the non-pivot
chains. Unlike in a pivot chain where all blocks in an epoch will have the
same block difficulty, the block difficulties may experience sudden changes in
non-pivot chains. This presents a significant barrier to surmount in our
analysis, and differs from previous work in this area. Recall that M1 ensures
that an honest party chooses the target of the next block in a non-pivot chain
from the tip of the heaviest pivot chain in its view. Hence, the targets used
by an honest party for the non-pivot chains are also reasonable. Then how
about the non-pivot-chain blocks mined by the adversary? As discussed in
Section 3, allowing the miners to choose arbitrary mining difficulty in a non-
pivot chain is risky. So we use the monotonicity condition M2 to ensure that
non-pivot-chain blocks also have “reasonable” block difficulties even if the
adversary mines them.

Then we prove that any two heaviest non-pivot chains cannot diverge for too
long to prove the common prefix property. We do this by considering two non-
pivot chains $C_{1}$ and $C_{2}$ (in one of the non-pivot block tree) that
diverge for too long and consider the last common honest block $B$ of $C_{1}$
and $C_{2}$. M2 ensures that the blocks arriving after $B$ should refer to a
pivot-chain block with monotonically non-decreasing chain difficulty than the
one referred by $B$. We also argue that the chain difficulty intervals covered
by uniquely successful honest blocks (defined as honest blocks that are mined
more than $\Delta$ rounds apart) in chains $C_{1}$ and $C_{2}$ do not overlap
similar to the analysis for the common prefix in (full2020, ). To make $C_{1}$
and $C_{2}$ diverge, the adversary has to accumulate an enormous total
difficulty compared to uniquely successful honest blocks.

When the number of adversarial queries is high in the chains $C_{1}$ and
$C_{2}$ after the block $B$, we bound the difficulty accumulated by the
adversary via concentration. When it is low, the variance is high; we prove
this by dividing the problem into 5 cases. Since the adversary cannot
contribute an enormous total difficulty compared to uniquely successful honest
blocks in one of the heaviest chains, the chain quality property also holds.
The full proof can be found in Section 6.4.

The last step of our proof is using the desired proprieties on each individual
chain to show the security of the full parallel-chain protocol. Since each
parallel-chain protocol has its own way of forming the transaction ledger, the
proof also has to differ. By properly turning the concept of block level to
block’s chain difficulty (M3), we make sure that our proof works out for all
three protocols. We complete the proof of persistence and liveness for Prism
in Section 6.5 (and the flowchart of the proof sketch can be found in Figure
9), while the proof for OHIE can be found in Appendix D. In addition, we
define and prove block reward fairness of FruitChains  under a variable mining
setting in Appendix E.

###  6.3. Definitions

$m\in\mathbb{N}$ | number of voter/parallel chains in Prism/OHIE
---|---
$n_{r}$ | number of honest parties mining in round $r$
$t_{r}$ | number of corrupted parties mining in round $r$
$\delta$ | advantage of honest parties ($t_{r}<(1-\delta)n_{r}$ for all $r$)
$\Delta$ | network delay in rounds
$\kappa$ | security parameter; length of the hash function output
$\Phi\in\mathbb{N}$ | the length of an epoch in number of blocks
$\tau\geq 1$ | the dampening filter (Definition 6.7)
$(\gamma,s)$ | restrictions on the fluctuation of the number of
| parties across rounds (Definition 2.1)
$f$ | expected mining rate in number of blocks per round
$\varepsilon$ | quality of concentration of random variables
$\lambda$ | related to the properties of the protocol
$\ell$ | minimum number of rounds for concentration bounds
$r_{\rm max}$ | total number of rounds in the execution
Table 1. The parameters used in our analysis.

Let $T,\Lambda,\Phi$ and $n$ denote the target of a block, duration of an
epoch, epoch length and number of honest parties respectfully. Throughout the
analysis, the block difficulty of a block with target $T$ is set to be $1/T$.
The chain difficulty of a chain is equal to the sum of all block difficulties
that comprise the chain. The following is the target recalculation function
for the pivot chain which is the same function used in Bitcoin.

###### Definition 6.7 (from (backbone, )).

Consider a pivot chain of $v$ blocks with timestamps $(r_{1}\ldots r_{v})$.
For fixed constants $\kappa,\tau,\Phi,n_{0}$ the initial number of
participants, $T_{0}$ the initial target, the target calculation function
$\mathcal{T}:\mathbb{Z}^{*}\rightarrow\mathbb{R}$ is defined as

$\displaystyle\mathcal{T}(\emptyset)$ $\displaystyle=T_{0},$
$\displaystyle\mathcal{T}(r_{1}\ldots r_{v})$
$\displaystyle=\left\\{\begin{array}[]{ll}\frac{1}{\tau}T&\text{if
}\frac{n_{0}}{n(T,\Lambda)}T_{0}<\frac{1}{\tau}T\\\ \tau T&\text{if
}\frac{n_{0}}{n(T,\Lambda)}T_{0}>{\tau}T\\\
\frac{n_{0}}{n(T,\Lambda)}T_{0}&\text{ otherwise}\end{array}\right.$

where $n(T,\Lambda)=2^{\kappa}\Phi/T\Lambda$, with
$\Lambda=r_{\Phi^{\prime}}-r_{\Phi^{\prime}-\Phi}$, $T=\mathcal{T}(r_{1}\ldots
r_{\Phi^{\prime}-1})$, and $\Phi^{\prime}=\Phi\lfloor v/\Phi\rfloor$.

We now define a notion of “good” properties such as good round and good chain.
These properties will bound the targets used by the honest parties, which will
help us prove chain quality and common prefix.

###### Definition 6.8 (Good round, from (full2020, )).

Let $T^{min}_{r}$ and $T^{max}_{r}$ denote the minimum and the maximum targets
the $n_{r}$ honest parties are querying the oracle for in round $r$. Round r
is good if $f/2\gamma^{2}\leq pn_{r}T^{min}_{r}$ and
$pn_{r}T^{max}_{r}\leq(1+\delta)\gamma^{2}f$.

###### Definition 6.9 (Good chain, from (full2020, )).

Round $r$ is a target-recalculation point of a pivot chain $\mathcal{C}$, if
$\mathcal{C}$ has a block with timestamp $r$ and height a multiple of $\Phi$.
A target-recalculation point $r$ is good if the target $T$ of the next block
satisfies $f/2\gamma\leq pn_{r}T\leq(1+\delta)\gamma f$. A pivot chain
$\mathcal{C}$ is good if all its target-recalculation points are good.

We will use the superscript $P$ to denote the variables, blocks, chains and
sets corresponding to the pivot chain/tree and $i$ to denote the ones of the
$i^{th}$ non-pivot chain/tree.

At any round $r$ of an execution, the adversary may keep chains in private
that have the potential to be adopted by an honest party (because the private
chains are heavier than the heaviest chain adopted by the honest party). So,
we expand our chains of interest beyond the chains that belong to an honest
party. For every non-pivot tree and the pivot tree, we define a set of valid
chains $\mathcal{S}_{r}^{P}$ and $\mathcal{S}_{r}^{i}$ (full2020, ) that
include the chains that belong to or have the potential to be adopted by an
honest party.

We will be dealing with random variables to quantify the difficulty
accumulated by the honest parties and the adversary in our analysis. At round
$r$, define the real random variable $D^{P}_{r}$ equal to the sum of the
difficulties of all pivot-chain blocks computed by honest parties. Also,
define $Y^{P}_{r}$ to equal the maximum difficulty among all pivot-chain
blocks computed by honest parties, and $Q^{P}_{r}$ to equal $Y^{P}_{r}$ when
$D^{P}_{u}=0$ for all $r<u<r+\Delta$ and 0 otherwise. We call an honest block
uniquely successful if it is mined at round $r$ such that $Q_{r}>0$. Similarly
define $D^{i}_{r},Y^{i}_{r}$ and $Q^{i}_{r}$ for the $i$-th non-pivot chain
($1\leq i\leq m$ in Prism and $1\leq i\leq m-1$ in OHIE). For a set of rounds
$S$, we define $D^{P}(S)=\sum_{r\in S}D^{P}_{r},Q^{P}(S)=\sum_{r\in
S}Q^{P}_{r}$ and $D^{i}(S)=\sum_{r\in S}D^{i}_{r},Q^{i}(S)=\sum_{r\in
S}Q^{i}_{r}$ for all $i$.

Regarding the adversary, for a set of $J$ adversarial queries to the oracle,
let $T(J)$ be target associated with the first query in $J$. Define the real
random variable $A^{P}(J)$, as the sum of difficulties of all the adversarial
blocks created during queries in $J$ with difficulty less than $\tau/T(J)$.
For all $i$, define $A^{i}(J)$ as the sum of difficulties of all the
adversarial blocks created during queries in $J$ with difficulty less than
$b^{i}(J)=max_{j\in
J}sup\\{A^{i}_{j}-A^{i}_{j-1}|\mathcal{E}_{j-1}=E_{j-1}\\}$, a function
associated with the set of queries $J$ (defined according to Theorem 8.1 in
(dubhashi2009concentration, )). $A^{P}_{j}$ is the difficulty of the pivot-
chain block with difficulty at most $\tau/T(J)$ obtained at the $j^{th}$ query
of $J$. $A^{i}_{j}$ is the difficulty of the block obtained at $j^{th}$ query
of $J$ for non-pivot chain $i$.

Let $\mathcal{E}$ denote the entire execution and let $\mathcal{E}_{r}$ be the
execution just before round $r+1$. To obtain meaningful concentration of our
random variables, we should be considering a sufficiently long sequence of at
least

(3)
$\displaystyle\ell\triangleq\frac{4(1+3\varepsilon)}{\varepsilon^{2}f[1-(1+\delta)\gamma^{2}f]^{\Delta+1}}\max\\{\Delta,\tau\\}\gamma^{3}\lambda$

consecutive rounds.

We require $\Phi$ the duration of an epoch to be large enough in order to
obtain meaningful security bounds:

(4) $\displaystyle\Phi\geq 4(1+\delta)\gamma^{2}f(\ell+3\Delta)\varepsilon.$

In order for the proofs for the security analysis to work, the parameters of
the protocol should satisfy the following conditions:

(5) $\displaystyle[1-(1+\delta)\gamma^{2}f]^{\Delta}\geq
1-\varepsilon,~{}~{}8\varepsilon\leq\delta\leq 1.$

Note that Equations (4) and (5) can always be satisfied by setting $\Phi$ to
be large enough and $f$ to be small enough. Also note that (4) and (5) are not
tight bounds on the parameters and are just sufficient conditions for the
analysis to work.

We now define what a typical execution, which will help us bound the random
variables in our analysis.

###### Definition 6.10 (Typical Execution).

For any set $S$ of at least $\ell$ consecutive good rounds, any set of $J$
consecutive adversarial queries and
$\alpha(J)=2(\frac{1}{\varepsilon}+\frac{1}{3})\lambda/T(J)$, an execution $E$
is typical if

$\displaystyle(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}pn(S)<Q^{i/P}(S)\leq
D^{i/P}(S)<(1+\varepsilon)pn(S),$ $\displaystyle
A^{P}(J)<p|J|+\max\\{\varepsilon p|J|,\tau\alpha(J)\\},$ $\displaystyle
A^{i}(J)<p|J|+\max\\{\varepsilon
p|J|,b^{i}(J)\lambda(\frac{1}{\varepsilon}+\frac{1}{3})\\},$

where $b^{i}(J)=max_{j\in
J}sup\\{A^{i}_{j}-A^{i}_{j-1}|\mathcal{E}_{j-1}=E_{j-1}\\}$.

We now show that a typical execution is a high-probability event.

###### Theorem 6.11.

For an execution $\mathcal{E}$ of $r_{\rm max}$ rounds, in a
$(\gamma,s)$-respecting environment, the probability of the event
“$\mathcal{E}$ not typical” is bounded by $\mathcal{O}(r_{\rm
max}^{2})e^{-\lambda}$.

The proof for Theorem 6.11 can be found in Appendix C.1

###  6.4. Non-pivot chain properties

Pivot chain behaves similar to the Bitcoin chain and its properties can be
found in Appendix B

Next we prove some desired properties for the non-pivot chains.

###### Lemma 6.12 (Chain growth for non-pivot chain, from (full2020, )).

Suppose that at round $u$ of an execution $E$, an honest party broadcasts a
$i$-th non-pivot chain of difficulty $d$. Then, by round $v$, every honest
party receives a chain of difficulty at least $d+Q^{i}(S)$, where
$S=\\{r:u+\Delta\leq r\leq v-\Delta\\}$.

The proof of Lemma 6.12 is identical to Lemma B.3.

At round $r$, to mine on a non-pivot chain block, an honest party picks a
target from the tip of a pivot chain in $\mathcal{S}^{P}_{r}$ which has good
targets at round $r$ because of Lemma B.4. So, as a consequence of M1, all the
targets used by the honest parties on a non-pivot chain also satisfies
$f/2\gamma^{2}\leq pn_{r}T_{r}\leq f(1+\delta)\gamma^{2}$.

###### Lemma 6.13 (Common prefix for non-pivot chains).

For a typical execution in a $(\gamma,2(1+\delta)\gamma^{2}\Phi/f)$-respecting
environment, each non-pivot chain satisfies the common-prefix property with
parameter $\ell_{\rm cp}=\ell+2\Delta$.

The proof of Lemma 6.13 is in Appendix C

###### Lemma 6.14 (Chain quality for non-pivot chains).

For a typical execution in a $(\gamma,2(1+\delta)\gamma^{2}\Phi/f)$-respecting
environment, each non-pivot chain satisfies the chain-quality property with
parameter $\ell_{\rm cq}=\ell+2\Delta$ and $\mu=\delta-3\varepsilon$.

The proof of Lemma 6.14 is in Appendix C.3.

###  6.5. Persistence and Liveness of Prism

###### Lemma 6.15 (Leader sequence common prefix).

For a typical execution in a $(\gamma,2(1+\delta)\gamma^{2}\Phi/f)$-respecting
environment, the leader sequence satisfies the leader-sequence-common-prefix
property with parameter $\ell_{\rm lscp}=2\ell+4\Delta$.

###### Lemma 6.16 (Leader sequence quality).

For a typical execution in a $(\gamma,2(1+\delta)\gamma^{2}\Phi/f)$-respecting
environment, the leader sequence satisfies the leader-sequence-quality
property with parameter $\ell_{\rm lsq}=\ell+2\Delta$ and
$\mu=\delta-3\varepsilon$.

The proofs of Lemma 6.15 and Lemma 6.16 are in Appendix C.4.

###### Theorem 6.17 (Persistence and liveness of Prism).

For a typical execution in a $(\gamma,2(1+\delta)\gamma^{2}\Phi/f)$-respecting
environment, Prism satisfies persistence and liveness with parameter
$u=\frac{4(1+\varepsilon)\gamma^{2}(\ell+2\Delta)}{(\delta-3\varepsilon)(1-\varepsilon)^{2}}$.

###### Proof.

By our definition, the persistence of Prism is equivalent to the leader
sequence common prefix property proved in Lemma 6.15.

We next prove the liveness property. Suppose a transaction tx is received by
all honest nodes before or at round $r_{0}$. Let $r\geq r_{0}+u$ be current
time and we shall prove that tx is contained in the permanent leader sequence
of all honest nodes at round $r$. As shown in Figure 10, let
$S_{1}=\\{r_{0},\cdots,r\\}$, $S_{2}=\\{r-2\ell-4\Delta,\cdots,r\\}$, and $J$
be the adversarial queries in $S_{2}$. By Lemma 6.15, for a difficulty level
$d$, if $d$ is covered by an honest block mined in $S1\setminus S2$, then the
block covering $d$ will be permanent in the leader sequence at round $r$. We
know that the difficulty level grows at least
$Q^{P}(S_{1})\geq(1-\varepsilon)^{2}pn_{r}u/\gamma$ in $S_{1}$. By Lemma 6.16,
we have that among the chain growth in $S_{1}$, different difficulty levels
with size at least $(\delta-3\varepsilon)(1-\varepsilon)^{2}pn_{r}u/\gamma$ is
covered by honest leader blocks (which may not be permanent at round $r$). On
the other hand, the proposer blocks that are not permanent (mined in $S_{2}$)
cover different difficulty levels with size at most

Figure 10. The leader blocks at each difficulty level in the proposer tree.

$\displaystyle D^{P}(S_{2})+A^{P}(S_{2})$ $\displaystyle<2D^{P}(S_{2})\leq
2(1+\varepsilon)p\gamma n_{r}(2\ell+4\Delta)$
$\displaystyle=4(1+\varepsilon)p\gamma n_{r}(\ell+2\Delta).$

Hence at least one honest proposer block $B$ mined after $r_{0}$ is permanent
in the leader sequence at round $r$. Since either $B$ or some proposer block
referred by $B$ will contain $\sf tx$, in both case we can conclude the proof.

∎

##  7\. Evaluation

In our evaluation, we answer the following questions.

  * •

Is the proposed scheme effective in matching the mining difficulty and the
miner hash power?

  * •

Does the blockchain forking rate remain low under our scheme, even with
changing miner hash power?

  * •

Does our scheme ensure that non-pivot chains adopt the difficulty of pivot
chains, even with presence of the adversary?

  * •

Does our scheme cause major computation and communication overhead when
applied?

Figure 11. Forking rate of all parallel chains in two simulations, one using
our scheme and one using fixed difficulty.

Figure 12. Frequency histogram of the delay where non-pivot chains update
their difficulty to follow that of the pivot chain. Note the y-axis is log
scale.

Figure 13. Frequency of difficulty change on a non-pivot chain where 30% of
miner power is adversarial.

###  7.1. Experimental Setup

Simulator. To evaluate our scheme, we build a mining simulator for parallel-
chain protocols in Golang. The simulator uses a round-by-round model with an
adjustable round interval. In each round, blocks are mined on each of the
parallel chains, and the number of blocks mined is determined by drawing from
independent Poisson random variables with mean set to the product of the round
interval and the per-chain mining rate. Miners receive newly-mined blocks
after an adjustable network latency.

Simulated protocol. Our simulator does not consider the interpretation of the
chains, such as transaction confirmation, ledger formation, etc. We only
simulate the mining process. As a result, our evaluation is not tied to any
particular protocol. Meanwhile, it is meaningful broadly to all PoW parallel-
chain protocols, because they share this mining process.

There are 1 pivot chain and 1000 non-pivot chains. We simulate PoW mining on
each of the chains at the same mining rate $f$. Each pivot-chain block
contains its timestamp, difficulty, and parent. Each non-pivot-chain block
also contains all these fields, plus a reference to a pivot-chain block (M1).
We simulate two parties of miners: honest and adversary. Honest miners follow
the general methodology described in section 1 by always referring to the best
block in the pivot chain. They enforce the rules M1, M2 by rejecting any non-
compliant block . We design different adversarial miners to simulate attacks,
and we provide more details later in Section 7.3.

Parameters. The round interval and the network latency are set to 2 seconds
according to data collected in large-scale experiments of Prism (prism-system,
). The target mining rate $f$ is set to 0.1 block per second per chain
according to (prism-system, ). The epoch length $\Phi$ is set to 2016 blocks,
and the dampening filter $\tau$ is set to 4 according to Bitcoin . We replay
the historical Bitcoin mining power data (hashratedata, ) during the
simulation.

###  7.2. Adaptation to Changing Miner Power

The main purpose of our scheme is to ensure the mining difficulty adapts to
changing mining power. To show that, we simulate our scheme while varying the
mining power according to the historical Bitcoin miner hash rate trace from
Jan 2, 2019 to Feb 20, 2020. Figure 14 shows that even though the miner hash
power has tripled during the simulated period, the mining difficulty of every
chain keeps tracking the miner hash power very closely. Also, at any point in
time, the max and min difficulty of all chains are very close. This
demonstrates that the mining difficulty of all chains are always closely
coupled, and no single chain experiences unstable difficulty or vulnerability.

Figure 14. Miner hash power and mining difficulty of each chain when
simulating our scheme over the historical Bitcoin miner power trace.
Difficulty is plotted as a region to show the max and min difficulty across
all chains. Both metrics are normalized over their initial values.

As mentioned in Section 1, support for variable miner power is crucial to
keeping the blockchain secure. If the miner hash power increases while the
mining difficulty stays the same, the forking rate will increase due to
decreased block inter-arrival time. To show our scheme is effective in keeping
the blockchain secure, we compare the forking rate of two simulations: one
using our scheme and one using a fixed mining difficulty. We use the same
Bitcoin mining power data as in the previous experiment, and Figure 13 shows
the results. Here, we report the forking rate as the ratio of the number of
blocks not on the longest chain, to the number of blocks on the longest chain.
If a fixed difficulty is used, the forking rate quickly increases as the miner
power increases, to almost tripling towards the end of the simulation. In
comparison, our scheme keeps the forking rate low across all parallel chains
for the whole simulation. This is because the mining difficulty and the miner
hash power are closely matched under our scheme, so the block mining rate
stays at a safe level.

###  7.3. Difficulty Update on Non-pivot Chains

One major challenge in designing our scheme is to ensure non-pivot chains
adopt the pivot chain difficulty quickly after a new epoch begins, and we
achieve it with the M2 (Monotonicity, cf. Section 1). To show that adversarial
miners cannot delay this process, we simulate our scheme where 30% of miners
are adversarial. Adversarial miners do not voluntarily refer to the latest
block on the pivot chain after a new epoch begins, but rather try to stay in
the previous epoch (and mining difficulty) for as long as possible. We also
simulate an all-honest scenario for comparison. We measure how soon non-pivot
chains adopt new difficulty by tracking the delay from the last block of the
previous epoch on the pivot chain to the first block of the new epoch of the
non-pivot chain. Figure 13 shows the results. In either scenario, the
difficulty of non-pivot chains is updated within 1–5 block intervals (0–50
seconds in real time). Although adversarial presence does delay the update of
difficulty, the delay is not significant. This demonstrates that our mechanism
ensures in-time update of non-pivot-chain difficulty.

We demonstrate that M2 is essential to ensuring the mining difficulty does not
vary too frequently on non-pivot chains. We compare two simulations where 30%
of miner power is adversarial. In one case, we apply our full scheme. In the
other case, we disable M2 so that the adversary is free to choose whatever
block on the pivot chain to refer when mining non-pivot chain blocks.
Specifically, the adversary always tries to mine blocks with the lowest
difficulty possible by referring to the genesis pivot-chain block. We focus on
one non-pivot chain, and track the frequency of difficulty change. Difficulty
change is defined as a block on the longest chain having different difficulty
than its parent. Figure 13 shows the results. Under our scheme, non-pivot
chain difficulty does not change for most of the time, and only changes
swiftly at the beginning of new epochs, so the curve for our scheme stays
close to zero. On the contrary, if we disable M2, the difficulty oscillates
violently, as frequently as 0.2 times per second on average. This shows that
our design is essential to maintain stable mining difficulty of non-pivot
chains.

###  7.4. Analysis of Overhead

Finally, we analyze and show that our schemes will cause minimal overhead when
implemented on existing parallel-chain protocols.

Communication and storage. Every block on the non-pivot chains needs to refer
to a block on the pivot chain (M1), which takes the size of a hash (usually 32
bytes). This is a very small overhead compared to the size of the blockchain.
For example, in Prism, the size of a voter (non-pivot-chain) block is 534
bytes (prism-system, ). The pivot-chain reference constitutes to an increase
of 6% in communication and storage cost for voter blocks. Notice that voter
blocks themselves only make up for 0.21% of the size of the Prism blockchain
(prism-system, ), so the overhead of pivot-chain referencing is negligible,
regardless of the parameters.

Computation. Our scheme changes the mining and the transaction confirmation
process of parallel chain protocols. For mining, notice that the pivot chain
follows the same difficulty adjustment rule as Bitcoin, which is proven
practical by its real-world deployment. Mining on non-pivot chains uses the
same difficulty as the pivot chain, so there is no additional bookkeeping.

For transaction confirmation, we use Prism as a concrete example (note that no
computation overhead exists in transaction confirmation for OHIE and
FruitChains). Under static difficulty, Prism selects a leader for every level
of the proposer tree. With M3, we partition the proposer tree into real-valued
difficulty intervals such that no interval is partially occupied by any
proposer block. We need to select a leader for each of such intervals (section
3.3). To determine the overhead, we need to answer: how many more intervals
are there compared to levels?

We simulate the mining process of Prism with 1000 voter chains, epoch length
$\Phi=2016$ blocks, target mining rate $f=0.1$ block per second, and found the
number of intervals is only 0.12% more than the number of levels. That is, our
scheme incurs a confirmation overhead of 0.12%. This is expected, because only
forks that happen at the beginning of an epoch will lead to extra intervals,
and such a fork rarely exists with $\Phi=2016$ and $f=0.1$. Decreasing $\Phi$
may cause the overhead to increase because there are more epochs and it is
more likely to fork at the beginning of an epoch. Table 2 plots the
confirmation overhead for different $\Phi$; we see that even at $\Phi=10$, the
overhead is smaller than 1%.

Table 2. Confirmation overhead vs epoch length $\Phi$ $\Phi$ | 10 | 100 | 1000 | 2016
---|---|---|---|---
Overhead | 0.43% | 0.07% | 0.11% | 0.12%

##  8\. Discussion

We presented a general methodology by which any parallel chain protocol can be
converted from the fixed difficulty to the variable difficulty setting. We
also proved the safety, liveness, and performance of the proposed scheme using
novel proof method that analyzes the coupling between the pivot and non-pivot
chains. There are several open directions of research. 1) In our design
methodology, we proposed using a single chain as a pivot chain to set the
difficulty target for all blocks. However, if we can use the information (for
example, inter-block arrival times) from all the chains together to determine
the difficulty target, we can get much better statistical averaging. This can
lead to protocols which can adapt to much more aggressive mining power
variation than is possible with a single-chain protocol. Such a protocol needs
to be designed with care since it leads to strong coupling across all the
chains. In particular, every chain needs to know the state of all other chains
in order to check the correctness of the difficulty target. Since other chains
can have forking in the meanwhile, it may lead to unintended complex
interactions. 2) We analyzed various protocols under the variable difficulty
setting. One new protocol, called Ledger-combiners (fitzi2020ledger, ) uses
parallel-chains for robustly combining multiple ledgers as well as for
achieving low latency. Analyzing that protocol in the variable difficulty
setting is an interesting direction for future work.

##  9\. Acknowledgements

This research is supported in part by a gift from IOHK Inc., an Army Research
Office grant W911NF1810332 and by the National Science Foundation under grants
CCF 17-05007 and CCF 19-00636.

## References

  * [1] Blockchain charts - total hash rate.  https://www.blockchain.com/charts/hash-rate.
  * [2] Christian Badertscher, Peter Gaži, Aggelos Kiayias, Alexander Russell, and Vassilis Zikas.  Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availability.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 913–930, 2018.
  * [3] Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath.  Prism: Deconstructing the blockchain to approach physical limits.  In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 585–602, 2019.
  * [4] Lear Bahack.  Theoretical bitcoin attacks with less than half of the computational power (draft).  arXiv preprint arXiv:1312.7013, 2013.
  * [5] Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A Kroll, and Edward W Felten.  Sok: Research perspectives and challenges for bitcoin and cryptocurrencies.  In 2015 IEEE symposium on security and privacy, pages 104–121. IEEE, 2015.
  * [6] T-H. Hubert Chan, Naomi Ephraim, Antonio Marcedone, Andrew Morgan, Rafael Pass, and Elaine Shi.  Blockchain with varying number of players.  Cryptology ePrint Archive, Report 2020/677, 2020.  https://eprint.iacr.org/2020/677.
  * [7] Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin Gün Sirer, et al.  On scaling decentralized blockchains.  In International conference on financial cryptography and data security, pages 106–125. Springer, 2016.
  * [8] Devdatt P Dubhashi and Alessandro Panconesi.  Concentration of measure for the analysis of randomized algorithms.  Cambridge University Press, 2009.
  * [9] Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, and Robbert Van Renesse.  Bitcoin-ng: A scalable blockchain protocol.  In 13th $\\{$USENIX$\\}$ symposium on networked systems design and implementation ($\\{$NSDI$\\}$ 16), pages 45–59, 2016.
  * [10] Matthias Fitzi, Peter Gaži, Aggelos Kiayias, and Alexander Russell.  Ledger combiners for fast settlement.  In Theory of Cryptography Conference, pages 322–352. Springer, 2020\.
  * [11] Juan Garay, Aggelos Kiayias, and Nikos Leonardos.  The bitcoin backbone protocol: Analysis and applications.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 281–310. Springer, 2015.
  * [12] Juan Garay, Aggelos Kiayias, and Nikos Leonardos.  The bitcoin backbone protocol with chains of variable difficulty.  In Annual International Cryptology Conference, pages 291–323. Springer, 2017.
  * [13] Juan Garay, Aggelos Kiayias, and Nikos Leonardos.  Full analysis of nakamoto consensus in bounded-delay networks.  Cryptology ePrint Archive, Report 2020/277, 2020.  https://eprint.iacr.org/2020/277.
  * [14] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich.  Algorand: Scaling byzantine agreements for cryptocurrencies.  In Proceedings of the 26th Symposium on Operating Systems Principles, pages 51–68, 2017.
  * [15] Chenxing Li, Peilun Li, Dong Zhou, Wei Xu, Fan Long, and Andrew Yao.  Scaling nakamoto consensus to thousands of transactions per second.  arXiv preprint arXiv:1805.03870, 2018.
  * [16] Songze Li and David Tse.  Taiji: Longest chain availability with bft fast confirmation.  arXiv preprint arXiv:2011.11097, 2020.
  * [17] David Mazieres.  The stellar consensus protocol: A federated model for internet-level consensus.  Stellar Development Foundation, 2015.
  * [18] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system.  Technical report, 2008.
  * [19] Kevin Alarcón Negy, Peter R Rizun, and Emin Gün Sirer.  Selfish mining re-examined.  In International Conference on Financial Cryptography and Data Security, pages 61–78. Springer, 2020.
  * [20] Rafael Pass, Lior Seeman, and Abhi Shelat.  Analysis of the blockchain protocol in asynchronous networks.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 643–673. Springer, 2017.
  * [21] Rafael Pass and Elaine Shi.  Fruitchains: A fair blockchain.  In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 315–324, 2017.
  * [22] Rafael Pass and Elaine Shi.  Hybrid consensus: Efficient consensus in the permissionless model.  In 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [23] David Schwartz, Noah Youngs, Arthur Britto, et al.  The ripple protocol consensus algorithm.  Ripple Labs Inc White Paper, 2014.
  * [24] Yonatan Sompolinsky and Aviv Zohar.  Secure high-rate transaction processing in bitcoin.  In International Conference on Financial Cryptography and Data Security, pages 507–527. Springer, 2015.
  * [25] Lei Yang, Vivek Bagaria, Gerui Wang, Mohammad Alizadeh, David Tse, Giulia Fanti, and Pramod Viswanath.  Prism: Scaling bitcoin by 10,000 x.  arXiv preprint arXiv:1909.11261, 2019.
  * [26] Haifeng Yu, Ivica Nikolić, Ruomu Hou, and Prateek Saxena.  Ohie: Blockchain scaling made simple.  In 2020 IEEE Symposium on Security and Privacy (SP), pages 90–105. IEEE, 2020.

## Appendix

##  Appendix A The Difficulty Raising Attack

Bitcoin set its target recalculation using a “dampening filter”-like
adjustment (as defined in Definition 6.7). It turns out that this design is
surprisingly foresighted. If we make a relaxation of the adjustment mechanism
by removing the dampening filter, then it is subject to an attack called
difficulty raising attack firstly discovered in [4]. At a high level, in this
attack the adversary mines private blocks with timestamps in rapid succession,
and induce one block with arbitrarily high difficulty in the private chain;
via an anti-concentration argument, a sudden adversarial advance that can
break agreement amongst honest parties cannot be ruled out. In this appendix,
we describe this attack in detail and explain why having a “dampening filter”
in the target recalculation function could resolve it.

A simple attack. As a prelim, we first look at a simple attack if the protocol
lets miners to choose their own difficulty and use the heaviest chain rule. At
a first glance, this rule appears kosher - the heaviest chain rule seems to
afford no advantage to any miner to manipulate their difficulty. However, this
lack of advantage only holds in expectation, and the variance created by
extremely difficult adversarial blocks can thwart a confirmation rule that
confirms deeply-embedded blocks, no matter how deep, with non-negligible
probability. We give a simple calculation here. For simplicity, we using the
difficulty defined in the genesis block as the difficulty unit and the
expected inter-block time (10 minutes in Bitcoin) as the time unit. Let $n$ be
number of honest queries to the hash function per unit time and $t$ be the
number of adversarial queries per unit time. Then we know that to mine a block
with unit difficulty, each query solves the PoW puzzle with probability $1/n$.
We further assume that $n$ and $t$ don’t change over time and the network
delay among honest nodes is zero. Note that these assumptions only make the
adversary weaker. The goal of the adversary is to double-spend a coin by
mining a heavier chain than the public honest chain from the genesis.

Suppose honest miners are adopting the initial mining difficulty as defined in
the genesis block, hence on average it take $k$ units of time to mine a honest
chain with $k$ blocks. To mine a heavier chain, the adversary only needs to
mine one block which has difficulty $k$ (See Figure 15 for illustration),
within $k$ unit of time. The adversarial can make $tk$ queries in $k$ units of
time, and each query succeeds with probability $1/nk$. Hence the success
probability of this attack would be

$\mathbb{P}({\rm attack~{}succeeds})=1-(1-\frac{1}{nk})^{tk}\approx
1-e^{t/n},$

since $n$ and $t$ are large in PoW mining. Note that the success probability
is a constant independent of $k$, therefore any $k$-deep confirmation rule
will fail.

Figure 15. A simple attack if allowing miners to choose their own difficulty.
The adversary mines one block which is as difficult as $k$ honest blocks.

Difficulty raising attack. However, even if we adopts a epoch based difficulty
adjustment rule as in Bitcoin (but without the “dampening filter”), there is
still a difficulty raising attack. We using the difficulty of the first epoch
(defined in the genesis block) as the difficulty unit and the expected inter-
block time (10 minutes in Bitcoin) as the time unit. Let $\Phi$ be the length
of an epoch in number of blocks (2016 in Bitcoin). And we define $n$ and $t$
the same as above.

Note that the adversary can put any timestamp in its private blocks, so the
difficulty of the second epoch in its private chain can be arbitrary value as
long as the adversary completes the first epoch. Let $B$ with difficulty $X$
be the first block of the second epoch in the private chain (that is each
query solves the PoW puzzle with probability $1/nX$), then $B$ has chain
difficulty $\Phi+X$. See Figure 16 for illustration. To mine an honest chain
with chain difficulty $\Phi+X$, on average it takes $\Phi+X$ time. On the
other hand, it takes on average $n\Phi/t$ time for the adversary to complete
the first epoch in its private chain. Therefore, to succeed in this attack,
the adversary needs to mine the block $B$ within $\Phi+X-n\Phi/t$ time, which
happens with probability:

$\displaystyle{\mathbb{P}}{({\rm attack~{}succeeds})}$
$\displaystyle=1-(1-\frac{1}{nX})^{(\Phi+X-n\Phi/t)t}$
$\displaystyle=1-(1-\frac{1}{nX})^{Xt-(n-t)\Phi}$ $\displaystyle\approx
1-e^{t/n},$

if $X\gg\Phi\gg 1$. Note that the success probability is independent of the
length of the public longest chain, hence any $k$-deep confirmation rule will
fail.

Figure 16. The difficulty raising attack. The adversary raises the difficulty
to extremely high in the second epoch by faking timestamps.

However, Bitcoin is saved by the dampening filter in the target recalculation
function. As in Definition 6.7, the difficulty can be increased by a factor of
at most $\tau$ between two consecutive epochs ($\tau=4$ in Bitcoin). Then we
shall analyze the difficulty raising attack under the same assumptions made
above. Since the epoch size $\Phi\gg 1$, the time for the adversary to
complete one epoch or mine $\Phi$ blocks with the same difficulty will satisfy
the concentration bound of binomial random variables. Hence if the adversary
always rises the difficulty by $\tau$ in each epoch, then it takes on average
$\frac{n}{t}\sum_{i=0}^{\ell-1}\tau^{i}\Phi$ time for the adversary to
complete $\ell$ epochs in its private chain, and the public honest chain will
on average have difficulty $\frac{n}{t}\sum_{i=0}^{\ell-1}\tau^{i}\Phi$ during
this time. Since the private chain has chain difficulty
$\sum_{i=0}^{\ell-1}\tau^{i}\Phi$, the gap of chain difficulties between the
public honest chain and the private chain will be

$(\frac{n}{t}-1)\sum_{i=0}^{\ell-1}\tau^{i}\Phi=(\frac{n}{t}-1)\frac{\tau^{\ell}-1}{\tau-1}\Phi.$

Each block of the $(\ell+1)$-th epoch in the private chain will have
difficulty $\tau^{\ell}$, hence the adversary still needs to mine
approximately $\frac{n-t}{t(\tau-1)}\Phi$ blocks in order to catch up the
honest chain. As $\Phi\gg 1$, the time for the adversary to catch up is still
controlled by the concentration bound, and the success probability of this
attack will be at most $e^{-\theta(\Phi)}$. By setting $\Phi$ large enough,
the difficulty raising attack can be ruled out.

While this specific attack could in principle be thwarted, to have security
guarantee we still need to consider all possible attacks in the presence of a
full-blown adversary. A full and beautiful analysis of Bitcoin rule is
provided in [13] and we shall give a proof sketch in Appendix B.

##  Appendix B Bitcoin Backbone Properties Revisited

We will briefly revisit the analysis in [13] because the pivot chain is
identical to the Bitcoin chain.

We will additionally define a stale chain and accuracy related to timestamps
of the blocks.

###### Definition B.1 (from [13]).

A block created at round $u$ is accurate is it has a timestamp $v$ such that
$|u-v|\leq\ell+2\Delta$. A chain is accurate if all its blocks are accurate. A
chain is stale if for some $u\geq\ell+2\Delta$ it does not contain a honest
block with timestamp $v\geq u-\ell-2\Delta$.

Recall that we define $\mathcal{S}^{P}_{r}$ as the set of pivot chains that
belong to or have the potential to be adopted by an honest party at round $r$
in Section 6.3. Now we define a series of useful predicates with respect to
$\mathcal{S}^{P}_{r}$.

###### Definition B.2 (from [13]).

For a round $r$,
$GoodRounds(r):=$ “All rounds $u\leq r$ are good.”
$GoodChains(r):=$ “For all rounds $u\leq r$, every chain in
$\mathcal{S}^{P}_{u}$ is good.”
$NoStaleChains(r):=$ “For all rounds $u\leq r$, there is no stale chain in
$\mathcal{S}^{P}_{u}$.”
$Accurate(r):=$ “For all rounds $u\leq r$, all chains in $\mathcal{S}^{P}_{u}$
are accurate.”
$Duration(r):=$ “For all rounds $u\leq r$ and duration$\Lambda$ of an epoch of
any chain in $\mathcal{S}^{P}_{u}$,
$\frac{1}{2(1+\delta)\gamma^{2}}\frac{m}{f}\leq\Lambda\leq
2(1+\delta)\gamma^{2}\frac{m}{f}$.”

The following lemma provides a lower bound on the progress of the honest
parties, which holds irrespective of any adversary.

###### Lemma B.3 (Chain growth for pivot chain, from [13]).

Suppose that at round $u$ of an execution $E$, an honest party broadcasts a
pivot chain of difficulty $d$. Then, by round $v$, every honest party receives
a chain of difficulty at least $d+Q^{P}(S)$, where $S=\\{r:u+\Delta\leq r\leq
v-\Delta\\}$.

In order to prove properties like common prefix and chain quality for the
pivot chain, we need all rounds in a typical execution to be good.

###### Lemma B.4 (All rounds in a typical execution are good, Theorem 2 from
[13]).

Consider a typical execution in a
$(\gamma,2\gamma^{2}(1+\delta)\Phi/f)$-respecting environment. If the protocol
is initiated such that the first round it good, and all the conditions 3, 4
and 5 are satisfied, then all rounds are good.

###### Proof.

The elaborate proof can be found in [13] and we summarize it as follows.

We will use an induction argument. In a $(\gamma,s)$-respecting environment,
$s\geq 2(1+\delta)\gamma^{2}m/f$ covers at least the first epoch. It is easy
to see that if the initial target is good, the rounds in the first epoch are
good, and the first target recalculation point is good. We will prove that the
subsequent rounds and target recalculation points are good using an induction
argument shown in Figure 17. The predicates are defined as follows.

Figure 17. An induction argument to prove that all rounds in a typical
execution are good.

We prove $NoStaleChains(r)$ from $GoodRounds(r-1)$ using typicality bounds,
showing that the adversary cannot accumulate more difficulty than the lower
bound of the minimum chain growth, $Q^{P}$. Let $w$ be the timestamp of the
last honest block on the stale chain. Set $U=\\{u:w\leq u\leq r\\}$,
$S=\\{u:w+\Delta\leq u\leq r-\Delta\\}$ and $J$ be the adversarial queries in
$U$. We will first consider the case where the chain has more than one target
recalculation point. In this case we divide $J$ into sub-queries $J_{i}$ such
that each subset covers at least $m/2$ blocks and has exactly one target
recalculation point in it. In this case, we have
$A^{P}(J)=\sum_{i}A^{P}(J_{i})<\sum_{i}(1+\varepsilon)p|J_{i}|=(1+\varepsilon)p|J|$.
We arrive at a contradiction by showing $(1+\varepsilon)p|J|$ is lower than
$Q^{P}(S)$’s lower bound. In case of at most one target recalculation point,
if $A(J)<(1+\varepsilon)p|J|$ applies, the argument from the previous case
applies. If $A(J)<(1+1/\varepsilon)(1/3+1/\varepsilon)\lambda\tau/T(J)$, we
prove that the lower bound of $Q^{P}(S)$ considering only the first $l$ rounds
will cover $(1+1/\varepsilon)(1/3+1/\varepsilon)\lambda\tau/T(J)$.
$Accurate(r)$ follows from $NoStaleChains(r)$.

We then prove the bound on duration by contradiction, assuming that the
previous target recalculation point is good using property $GoodChains(r-1)$.
The lower bound is contradicted by showing that even if the adversary and
honest party join forces, they can’t produce $e$ blocks in less than
$\frac{1}{2(1+\delta)\gamma^{2}}\frac{m}{f}$. The upper bound is contradicted
by showing that the lower bound of $Q^{P}$ produces at least $e$ blocks in
$2(1+\delta)\gamma^{2}\frac{m}{f}$ rounds. To prove $GoodChains(r)$, we prove
that the next target-recalculation point is good. This is proved again, using
a contradiction for both the bounds of a good target recalculation point.
Finally, we use $Duration(r)$, $GoodChains(r)$ and the
$(\gamma,2(1+\delta)\gamma^{2}m/f)$-respecting environment assumption to prove
$GoodRounds(r)$. ∎

The following lemma from [13] is useful to prove common prefix and chain
quality of the pivot chain.

###### Lemma B.5 (Lemma 2(c) from [13]).

Consider a typical execution in a $(\gamma,s)$-respecting environment. Let
$S=\\{r:u\leq r\leq v\\}$ be a set of rounds with at least $\ell$ rounds and
$J$ be the set of adversary queries in $U=\\{r:u-\Delta\leq r\leq
v+\Delta\\}$. If $w$ is a good round such that $|w-r|\leq s$ for any $r\in S$,
then $A^{P}(J)<(1-\delta+3\varepsilon)Q^{P}(S)$

The following properties of the pivot chain are from [13].

###### Lemma B.6 (Common prefix for pivot chain).

For a typical execution in a $(\gamma,2(1+\delta)\gamma^{2}\Phi/f)$-respecting
environment, the pivot chain satisfies the common-prefix property with
parameter $\ell_{\rm cp}=\ell+2\Delta$.

###### Lemma B.7 (Chain quality for pivot chain).

For a typical execution in a $(\gamma,2(1+\delta)\gamma^{2}\Phi/f)$-respecting
environment, the pivot chain satisfies the chain-quality property with
parameter $\ell_{\rm cq}=\ell+2\Delta$ and $\mu=\delta-3\varepsilon$.

##  Appendix C Proof for Section 6

###  C.1. Proof for typical execution

The following concentration bound on a martingale is helpful to bound the
probability of a not typical execution.

###### Theorem C.1 (from [13]).

Let $(X_{1},X_{2},\ldots)$ be a martingale with respective the sequence
$(Y_{1},Y_{2},\ldots)$, if an event $G$ implies $X_{k}-X_{k-1}\leq b$ and
$V=\sum_{k}var[X_{k}-X_{k-1}|Y_{1},\ldots,Y_{k-1}]\leq v$, then for non-
negative $n$ and $t$

$\displaystyle P(X_{n}-X_{0}\geq t,G)\leq
e^{-\frac{t^{2}}{2v+\frac{2bt}{3}}}.$

And for the proof of Theorem 6.11

###### Proof.

The proof for $Q^{P}(S),D^{P}(S)$ and $A^{P}(J)$ can be found in [13] and the
same proof follows for $Q^{i}(S)$ and $D^{i}(S)$. We will prove it for
$A^{i}(J)$. For each $j\in J$, let $A_{j}$ be the difficulty of the block
obtained with the $j^{th}$ query as long as the target was at least
$1/b^{i}(J)$. Define

$\displaystyle X_{0}=0,$ $\displaystyle
X_{k}=\sum_{j\in[k]}A_{j}-\sum_{j\in[k]}\mathbb{E}[A_{j}|\mathcal{E}_{j-1}],k\in[|J|],$

which is a martingale with respect to the sequence $\mathcal{E}_{j-1},j\in J$.
For the above martingale, for all $k\in[|J|]$, we have $X_{k}-X_{k-1}\leq
b^{i}(J)$, using the definition of $b^{i}(J)$ and $var[X_{k}-X_{k-1}]\leq
pb^{i}(J)$ and $\mathbb{E}[A_{j}|\mathcal{E}_{j-1}]\leq p$. We will apply
Theorem C.1 with $t=\max\\{\varepsilon p|J|,\\\
b^{i}(J)\lambda(\frac{1}{\varepsilon}+\frac{1}{3})\\}\geq
b^{i}(J)\lambda(\frac{1}{\varepsilon}+\frac{1}{3})$ and $v=b^{i}(J)p|J|$ to
obtain

$\displaystyle Pr[\sum_{j\in J}A_{j}\geq p|J|+t]\leq
exp\\{-\frac{t}{2b^{i}(J)(\frac{1}{3}+\frac{1}{\varepsilon})}\\}\leq
e^{-\lambda}.$

∎

###### Lemma C.2 (Proposition 2 from [13]).

In a $(\gamma,s)$-respecting environment, let $U$ be a set of at most $s$
consecutive rounds and $S\subseteq U$ then, for any $n\in\\{n_{r}:r\in U\\}$
we have

$\displaystyle\frac{n}{\gamma}$ $\displaystyle\leq\frac{n(S)}{|S|}\leq\gamma
n,$ $\displaystyle n(U)$ $\displaystyle\leq(1+\frac{\gamma|U\setminus
S|}{|S|})n(S).$

###  C.2. Proof of Lemma 6.13

By the definition of typical execution, we have the following lemma that will
be useful in the proof.

###### Lemma C.3.

Under a typical execution, for the set of rounds $S$ with $|S|\geq\ell$, let
$Q^{P}(S)$ correspond to the pivot tree and $Q^{i}(S)$ correspond to any non-
pivot tree then,
$Q^{i}(S)>Q^{P}(S)(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}/(1+\varepsilon)$.

###### Proof.

This follows from the definition of typicality, we use the following
inequalities

$\displaystyle(1+\varepsilon)pn(S)$ $\displaystyle>Q^{P}(S),$ $\displaystyle
Q^{i}(S)$
$\displaystyle>(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}pn(S).$

∎

The following proposition will be useful in the proof of non-pivot chain’s
common prefix.

###### Proposition 1.

In a typical execution, we have the following bound

$\displaystyle A^{i}(J)<(1+\varepsilon)p|J|$

for
$p|J|\geq\frac{2b^{i}(J)\lambda}{\varepsilon}(\frac{1}{3}+\frac{1}{\varepsilon}).$

$\displaystyle
A^{i}(J)<(1+\varepsilon)\frac{2b^{i}(J)\lambda}{\varepsilon}(\frac{1}{3}+\frac{1}{\varepsilon})<\frac{(1-\varepsilon^{2})(\frac{\varepsilon}{3}+1)\varepsilon\Phi}{8\gamma^{5}(1+\delta)(1+3\varepsilon)}\frac{b^{i}(J)}{\tau}$

for
$p|J|<\frac{2b^{i}(J)\lambda}{\varepsilon}(\frac{1}{3}+\frac{1}{\varepsilon})$,
the second inequality follows from the bound on $\ell$.

For the proof of Lemma 6.13

###### Proof.

Consider the $i^{th}$ non-pivot chain, suppose common prefix fails for two
chains ${\mathcal{C}}_{1}$ and ${\mathcal{C}}_{2}$ held by honest players at
rounds $r_{1}\leq r_{2}$ respectively, that is, $\exists
B\in{\mathcal{C}}_{1}^{\lceil\ell+2\Delta}$, s.t. $B\notin{\mathcal{C}}_{2}$.
It is not hard to see that in such a case there was a round $r\leq r_{2}$ and
two honest held chains ${\mathcal{C}}$ and ${\mathcal{C}}^{\prime}$ in
$\mathcal{S}_{r}^{i}$, such that $B\in{\mathcal{C}}^{\lceil\ell+2\Delta}$ but
$B\notin{\mathcal{C}}^{\prime}$. Then we know $B$ is a descendant of
head$({\mathcal{C}}\cap{\mathcal{C}}^{\prime})$, and hence
head$({\mathcal{C}}\cap{\mathcal{C}}^{\prime})\in{\mathcal{C}}^{\lceil\ell+2\Delta}$.
Therefore, the timestamp of head$({\mathcal{C}}\cap{\mathcal{C}}^{\prime})$ is
less than $r-\ell-2\Delta$.

Let $v<r-\ell-2\Delta$ be the timestamp of
head$({\mathcal{C}}\cap{\mathcal{C}}^{\prime})$ and $w\leq v$ be the timestamp
of the last honest block $B^{i}_{h}$ on
$({\mathcal{C}}\cap{\mathcal{C}}^{\prime})$. Let $U^{i}=\\{u:w\leq u\leq
r\\},S^{i}=\\{u:w+\Delta\leq u\leq r-\Delta\\}$ and let $J^{i}$ be the
adversarial queries in rounds $U^{i}$. Let $\mathcal{S}^{P}_{r,w-\Delta}$ be
the collection of pivot chains heavier than at least one chain in
$\mathcal{S}_{w-\Delta}$. And for $j\in J^{i}$, let
$\mathcal{S}^{P}_{j,w-\Delta}$ be the collection of pivot chains heavier than
at least one chain in $\mathcal{S}_{w-\Delta}$. Due to condition M2, all the
difficulties of the blocks in $C$ or $C^{\prime}$ that come after $B_{0}^{i}$
are extending $\mathcal{S}_{r,w-\Delta}^{P}$. We have $b=b^{i}(J)=\max_{j\in
J^{i}}\sup\\{A^{i}_{j}-A^{i}_{j-1}|\mathcal{E}_{j-1}=E_{j-1}\\}=\max_{j\in
J^{i}}sup\\{A^{i}_{j}-A^{i}_{j-1}|\mathcal{E}_{j-1}=E_{j-1}\\}=\max_{j\in
J^{i}}\sup\\{{\rm
diff}(C^{P}B^{*})|C^{*}\in\mathcal{S}_{j,w-\Delta}\\}=\sup_{C^{P}\in\mathcal{S}_{r,w-\Delta}}\\{{\rm
diff}(C^{P}B^{*})\\}$. The last equality applies because, for $j\in J^{i}$,
$\mathcal{S}_{j,w-\Delta}\subseteq\mathcal{S}_{r,w-\Delta}$. Let
$C^{*}\in\mathcal{S}_{r,w-\Delta}$ be the chain for which ${\rm
diff}(C^{*}B^{*})=b$. In case such $C^{*}$ doesn’t exist, there exists a
sequence of chains $C^{*}_{n}$, such that ${\rm diff}(C^{*}_{n}B^{*})$
approaches $b$ in limit. Let the block $B^{P}_{h}$ be the last honest block on
$C^{*}$ with timestamp $x$.

We claim that if $r>\ell+2\Delta+w$, then
$A^{i}(J^{i})<(1+\delta+3\varepsilon)Q^{i}(S^{i})$. The proof is as follows.
When
$p|J^{i}|\geq\frac{2b\lambda}{\varepsilon}(\frac{1}{3}+\frac{1}{\varepsilon})$,
the concentration bound $A^{i}(J^{i})<(1+\varepsilon)p|J^{i}|$ applies. We
have $n(U^{i})\leq n(S^{i})(1+\gamma|U\setminus
S|/|S|)<(1+\varepsilon^{2}/2)n(S)$ and

$\displaystyle A^{i}(J^{i})$
$\displaystyle<(1+\varepsilon)(1-\delta)pn(U^{i})<(1+\varepsilon)(1+\varepsilon^{2}/2)(1-\delta)pn(S^{i})$
$\displaystyle<(1-\delta+\varepsilon)pn(S^{i})<(1-\delta+3\varepsilon)Q^{i}(S^{i})$

We will prove this when
$p|J^{i}|<\frac{2b\lambda}{\varepsilon}(\frac{1}{3}+\frac{1}{\varepsilon})$.

Case 1 |  $C^{*}$ has at most one target-recalculation point after $B_{h}^{P}$ and $w\leq x\leq r\Rightarrow f/2\gamma^{2}\tau<\frac{1}{b}n_{x}p$
---|---
Case 2 |  $C^{*}$ has at least two target-recalculation point after $B_{h}^{P}$ and $w\leq x\leq r$
Case 3 |  $x<w,|w-x|>\gamma^{2}(1+\delta)\Phi/f-\ell-2\Delta$
Case 4 |  $x<w,|w-x|<\gamma^{2}(1+\delta)\Phi/f-\ell-2\Delta$, and $C^{*}$ has at most one target-recalculation point after $B_{h}^{P}$
Case 5 |  $x<w,|w-x|<\gamma^{2}(1+\delta)\Phi/f-\ell-2\Delta$, and $C^{*}$ has at least two target-recalculation point after $B_{h}^{P}$

Figure 18. Common Prefix Proof (Left): $w<x$, (Right): $w>x$

Cases 1, 2 are shown in left and cases 3,4,5 in right of Figure 18.

Case 1: The last honest block $B^{P}_{h}$ in the chain $C^{*}$ has a timestamp
$x\geq w$. We will look at the case when $C^{*}$ has at most one target
recalculation point after $B^{P}_{h}$. In this case the difficulty $b$
satisfies $\frac{f}{2\gamma^{2}\tau}<\frac{1}{b}n_{x}p$ since the difficulty
can raise by at most a factor of $\tau$ and considering the first $\ell$
rounds in $S^{i}$, we have ${n(S^{i})}>\frac{n_{x}}{\gamma}\ell$. Using
typicality we have, $p|J|\leq(1-\delta+\varepsilon^{2}/2)pn(S)$ and

$\displaystyle\varepsilon(1-2\varepsilon)pn(S^{i})>\varepsilon(1-2\varepsilon)\frac{pn_{x}\ell
b}{\gamma b}>\frac{\varepsilon(1-2\varepsilon)f\ell b}{2\gamma^{3}\tau}\geq
2b\lambda(\frac{1}{\varepsilon}+\frac{1}{3}),$ $\displaystyle
A^{i}(J^{i})<p|J|+2b\lambda(\frac{1}{\varepsilon}+\frac{1}{3})\leq(1-\delta+\varepsilon)pn(S^{i})<(1-\delta+3\varepsilon)Q^{i}(S^{i})$

Case 2: The last honest block $B^{P}_{h}$ in the chain $C^{*}$ has a timestamp
$x\geq w$. We will look at the case when $C^{*}$ has more than one target
recalculation point after $B^{P}_{h}$. Let $U^{P}$ be the set of rounds
$\\{u:x\leq u\leq r\\}$, $S^{P}$ be the set of rounds $\\{u:x+\Delta\leq u\leq
r-\Delta\\}$ and $J^{P}$ be the queries made by the adversary for the proposer
chain in $U^{P}$. In this case difficulty accumulated by the adversary in
$J^{P}$ queries is at least $\frac{b}{\tau}\Phi$. Using typicality, we have
$p|J^{P}|>\frac{b\Phi}{\tau(1+\varepsilon)}$ and using honest party’s
advantage we have $n(S^{i})\geq
n(S^{P})>\frac{|J^{P}|}{(1-\delta)(1+\varepsilon^{2}/2)}$.

$\displaystyle(1-\delta+3\varepsilon)Q^{i}(S^{i})$
$\displaystyle>(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}\frac{(1-\delta+3\varepsilon)p|J^{P}|}{(1-\delta)(1+\varepsilon^{2}/2)}$
$\displaystyle>\frac{b\Phi}{\tau}\geq A^{i}(J^{i}).$

The last inequality implies from Proposition 1.

Case 3: Consider the case when $x<w$ and $|w-x|>s/2-\ell-2\Delta$. Let
$S^{\prime}:=\\{u:x+\Delta\leq u\leq w-\Delta\\}$, $U^{P}=\\{u:x\leq u\leq
r\\}$ and $J^{P}$ be the set of adversarial queries for the proposal tree in
the rounds $U^{P}$. The difficulty accumulated in the chain $C^{*}$ in $J^{P}$
queries is more than that of the chain growth in $S^{\prime}$.

$\displaystyle A^{P}(J^{P})\geq ChainGrowth^{P}(S^{\prime})\geq
Q^{P}(S^{\prime}).$

Since $s=\frac{2\gamma^{2}(1+\delta)\Phi}{f}$, we have
$|S^{\prime}|\geq(1+\delta)(1-\varepsilon)\gamma^{2}\Phi/f$. Considering the
first $s/2-\ell$ rounds in $U^{P}\setminus U^{i}$ , if $T_{x}$ is the target
used by the honest party in round $x$, then
$\frac{n(S^{\prime})}{|S^{\prime}|}\geq\frac{n_{x}}{\gamma}$ and
$T_{x}n_{x}p\geq\frac{f}{2\gamma^{2}}$. Using these, we have

$\displaystyle Q^{P}(S^{\prime})$
$\displaystyle>(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}pn(S^{\prime})$
$\displaystyle\geq(1+\delta)(1-\varepsilon)^{3}\frac{\gamma\Phi
pn_{x}T_{x}}{2fT_{x}}\geq(1+\delta)(1-\varepsilon)^{3}\frac{\Phi}{2\gamma
T_{x}}>\frac{\Phi}{2T_{x}\gamma}$

Note that starting with target $T_{x}$, if $C^{*}$ has at most one target
recalculation point after $B_{h}^{P}$, then the accumulated difficulty is at
least $\frac{\Phi}{2\gamma}\frac{b}{\tau}$, which is a smaller quantity than
$\frac{\Phi}{2T_{x}\gamma}$. If the chain has more than one target
recalculation point, then the accumulated difficulty is at least
$m\frac{b}{\tau}$ which is larger than $\frac{\Phi}{2\gamma}\frac{b}{\tau}$.
Hence, the accumulated difficulty will be at least
$\frac{\Phi}{2\gamma}\frac{b}{\tau}$ in any case.

$\displaystyle|J^{P}|p(1+\varepsilon)>A^{P}(J^{P})\geq Q^{P}(S^{\prime}),$
$\displaystyle A^{P}(J^{P})>\frac{\Phi}{2\gamma}\frac{b}{\tau}$

We have
$n(S^{i})+n(S^{\prime})>\frac{|J^{P}|}{(1-\delta)(1+\varepsilon^{2}/2)}$ and

$\displaystyle Q^{i}(S^{i})+Q^{i}(S^{\prime})$
$\displaystyle>(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}\frac{p|J^{P}|}{(1-\delta)(1+\varepsilon^{2}/2)},$
$\displaystyle Q^{i}(S^{\prime})$
$\displaystyle<Q^{P}(S^{\prime})\frac{(1+\varepsilon)}{(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}}$
$\displaystyle<\frac{(1+\varepsilon)^{2}}{(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}}p|J^{P}|$

Combining both we have,

$\displaystyle
Q^{i}(S^{i})>p|J^{P}|\frac{((1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta})^{2}-(1+\varepsilon)^{2}(1-\delta)(1+\varepsilon^{2}/2)}{(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}(1-\delta)(1+\varepsilon^{2}/2)},$

and then

$\displaystyle(1-\delta+3\varepsilon)Q^{i}(S^{i})$ $\displaystyle>$
$\displaystyle(1+3\frac{\varepsilon}{1-\delta})\frac{(\delta(1+\varepsilon^{2}/2)(1+\varepsilon)^{2}-6\varepsilon)}{(1-\varepsilon^{2})[1-(1+\delta)\gamma^{2}f]^{\Delta}(1+\varepsilon^{2}/2)}\frac{\Phi}{2\gamma}\frac{b}{\tau}$
$\displaystyle>$ $\displaystyle A^{i}(J^{i}),$

Where the last inequality follows from the condition $\delta>8\varepsilon$.

Case 4: Consider the case the last honest block in the chain containing $B$’s
proposer parent has a timestamp $x<w$ and $|w-x|<s/2-\ell-2\Delta$ and $C^{*}$
has at most one target recalculation point after $B^{P}_{h}$. Let
$S^{\prime}:=\\{u:x+\Delta\leq u\leq w-\Delta\\}$. The difficulty accumulated
$C^{*}$ in $J^{P}$ queries is more than that of the chain growth in
$S^{\prime}$. Considering just first $\ell$ rounds in $S^{i}$, we have
$n(S^{i})>\ell n_{x}/\gamma$ and $b$ satisfies
$\frac{f}{2\gamma^{2}\tau}<\frac{1}{b}n_{x}p$. Using these bounds and Lemma
B.3, we have

$\displaystyle\varepsilon(1-2\varepsilon)pn(S^{i})>\varepsilon(1-2\varepsilon)\frac{pn_{x}\ell
b}{\gamma b}>\frac{\varepsilon(1-2\varepsilon)f\ell b}{2\gamma^{3}\tau}\geq
2b\lambda(\frac{1}{\varepsilon}+\frac{1}{3}),$ $\displaystyle
A^{i}(J^{i})<p|J|+2b\lambda(\frac{1}{\varepsilon}+\frac{1}{3})\leq(1-\delta+\varepsilon)pn(S^{i})<(1-\delta+3\varepsilon)Q^{i}(S^{i})$

Case 5: Consider the case the last honest block in the chain containing $B$’s
proposer parent has a timestamp $x<w$ and $|w-x|<s/2-\ell-2\Delta$. Let
$S^{\prime}:=\\{u:x+\Delta\leq u\leq w-\Delta\\}$. The difficulty accumulated
by $C^{*}$ in $J^{P}$ queries is more than that of the chain growth in
$S^{\prime}$. We will consider the case $C^{*}$ has more than one target
recalculation point after $B^{P}_{h}$. The adversary accumulates more than
$\frac{b}{\tau}\Phi$ difficulty in $J^{P}$ queries and similar to Case 4, we
have

$\displaystyle|J^{P}|p(1+\varepsilon)>A^{P}(J^{P})\geq\Phi\frac{b}{\tau},$
$\displaystyle A^{P}(J^{P})\geq Q^{P}(S^{\prime}),$ $\displaystyle
n(S^{i})+n(S^{\prime})>\frac{|J^{P}|}{(1-\delta)(1+\varepsilon^{2}/2)},$

and

$\displaystyle Q^{i}(S^{i})+Q^{i}(S^{\prime})$
$\displaystyle>(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}\frac{p|J^{P}|}{(1-\delta)(1+\varepsilon^{2}/2)},$
$\displaystyle Q^{i}(S^{\prime})$
$\displaystyle<Q^{P}(S^{\prime})\frac{(1+\varepsilon)}{(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}}$
$\displaystyle<\frac{(1+\varepsilon)^{2}}{(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}}p|J^{P}|$

Combining both we have

$\displaystyle Q^{i}(S^{i})$
$\displaystyle>p|J^{P}|\frac{((1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta})^{2}-(1+\varepsilon)^{2}(1-\delta)(1+\varepsilon^{2}/2)}{(1-\varepsilon)[1-(1+\delta)\gamma^{2}f]^{\Delta}(1-\delta)(1+\varepsilon^{2}/2)},$

and then

$\displaystyle(1-\delta+3\varepsilon)Q^{i}(S^{i})$ $\displaystyle>$
$\displaystyle(1+3\frac{\varepsilon}{1-\delta})\frac{(\delta(1+\varepsilon^{2}/2)(1+\varepsilon)^{2}-6\varepsilon)\Phi
b}{(1-\varepsilon^{2})[1-(1+\delta)\gamma^{2}f]^{\Delta}(1+\varepsilon^{2}/2)\tau}$
$\displaystyle>$ $\displaystyle A^{i}(J^{i}),$

The last inequality follows from the condition $\delta>8\varepsilon$.

We also claim that, if $r-w>\ell+2\Delta$, then $2Q^{i}(S^{i})\leq
D^{i}(U^{i})+A^{i}(J^{i})$, which leads to a contradiction as
$D^{i}(U^{i})<(1+5\varepsilon)Q^{i}(S)$ and
$A^{i}(J^{i})<(1-\delta+3\varepsilon)Q^{i}(S^{i})$.

Towards proving the claim above, associate with each $r\in S$ such that
$Q^{i}_{r}>0$ an arbitrary honest block that is computed at round $r$ for
difficulty $Q^{i}_{r}$. Let $\mathcal{B}$ be the set of these blocks and note
that their difficulties sum to $Q^{i}(S)$. Then consider a block
$B\in\mathcal{B}$ extending a chain ${\mathcal{C}}^{*}$ and let $d={\rm
diff}({\mathcal{C}}^{*}B)$. If $d\leq{\rm
diff}({\mathcal{C}}\cap{\mathcal{C}}^{\prime})$ (note that $u<v$ in this case
and head$({\mathcal{C}}\cap{\mathcal{C}}^{\prime})$ is adversarial), let
$B_{0}$ be the block in ${\mathcal{C}}\cap{\mathcal{C}}^{\prime}$ containing
d. Such a block clearly exists and has a timestamp greater than $u$.
Furthermore, $B_{0}\notin\mathcal{B}$, since $B_{0}$ was an adversarial block.
If $d>{\rm diff}({\mathcal{C}}\cap{\mathcal{C}}^{\prime})$, note that there is
a unique $B\in\mathcal{B}$ such that $d\in B$. Since $B$ cannot simultaneously
be on chain ${\mathcal{C}}$ and ${\mathcal{C}}^{\prime}$, there is a
$B_{0}\notin\mathcal{B}$ either on ${\mathcal{C}}$ or on
${\mathcal{C}}^{\prime}$ that contains $d$. Hence there exists a set of blocks
$\mathcal{B}^{\prime}$ computed in $U$ such that
$\mathcal{B}\cap\mathcal{B}^{\prime}=$ and $\\{d\in
B:B\in\mathcal{B}\\}\subseteq\\{d\in B:B\in\mathcal{B}^{\prime}\\}$. Because
each block in $\mathcal{B}^{\prime}$ contributes either to $D^{i}(U)-Q^{i}(S)$
or to $A^{i}(J)$, we have $Q^{i}(S^{i})\leq
D^{i}(U^{i})-Q^{i}(S)+A^{i}(J^{i})$.

∎

###  C.3. Chain Quality of Non-pivot Chains

###### Proof of Lemma 6.14.

Without loss of generality, we focus on the first non-pivot chain. Let $B_{i}$
denote the $i$-th block of ${\mathcal{C}}$ and consider $K$ consecutive blocks
$B_{u},\cdots,B_{v}$ in ${\mathcal{C}}$ with timestamp in $S_{0}$. Define
$K_{0}$ as the least number of consecutive blocks
$B_{u^{\prime}},\cdots,B_{v^{\prime}}$ that include the $K$ given ones (i.e.,
$u^{\prime}\leq u$ and $v\leq v^{\prime}$) and have the properties (1) that
the block $B_{u^{\prime}}$ was mined by an honest party at some round $r_{1}$
or is the genesis block in case such block does not exist, and (2) that there
exists a round $r_{2}$ such that the chain ending at block $B_{v^{\prime}}$ is
adopted by some honest node at round $r_{2}$. Let $d^{\prime}$ be the total
difficulty of these $K^{\prime}$ blocks. Define $U=\\{r_{1},\cdots,r_{2}\\}$,
$S=\\{r_{1}+\Delta,\cdots,r_{2}-\Delta\\}$, and $J$ the adversarial queries in
$U$ associated with the $K^{\prime}$ blocks. Then we have
$|S|=|U|-2\Delta\geq|S_{0}|-2\Delta\geq\ell$. Then following the same argument
from Lemma 6.13, we have $A^{1}(J)<(1-\delta+3\varepsilon)Q^{1}(S)$. Let $x$
denote the total difficulty of all the blocks from honest parties that are
included in the $K$ blocks and—towards a contradiction—assume $x<\mu d\leq\mu
d^{\prime}$. In a typical execution, all the $K^{\prime}$ blocks have been
mined in $U$. But then we have the following contradiction

$A^{1}(J)\geq
d^{\prime}-x>(1-\mu)d^{\prime}\geq(1-\mu)Q^{1}(S)=(1-\delta+3\varepsilon)Q^{1}(S).$

Therefore, we can conclude the proof. ∎

###  C.4. Common Prefix and Chain Quality of the Leader Sequence

###### Proof of Lemma 6.15.

Let $r\geq R_{d}+2\ell+4\Delta$ be the current round. For $1\leq i\leq m$, let
${\mathcal{C}}_{i}$ be the heaviest voter chain $i$ in an honest node $u$’s
view at round $r$. By the common prefix property in Lemma 6.13, blocks in
${\mathcal{C}}_{i}^{\lceil\ell+2\Delta}$ remain unchanged until $r_{\rm max}$.
In addition, by the chain quality property in Lemma 6.14, we know that for
$1\leq i\leq m$, there exists at least one honest block $B_{i}$ on chain
${\mathcal{C}}_{i}$ whose timestamp is in the interval
$(r-2\ell-4\Delta,r-\ell-2\Delta)$,i.e., $B_{i}$ is on the chain
${\mathcal{C}}_{i}^{\lceil\ell+2\Delta}$. As $B_{i}$ is an honest block mined
after $R_{d}$, $B_{i}$ or an ancestor of $B_{i}$ must have voted for the
difficulty level $d$. Therefore the leader sequence remains unchanged up to
difficulty level $d$ until $r_{\rm max}$. ∎

###### Proof of Lemma 6.16.

Let $r$ be the current round, ${\mathcal{C}}$ be the proposer chain held by
honest player $P$, and $d=\rm{diff}({\mathcal{C}})$. Let interval
$D=(d^{\prime},d]$ be the difficulty range covered by all blocks in
${\mathcal{C}}$ with timestamp in last $\ell+2\Delta$ rounds. Define:

$\displaystyle d^{*}$ $\displaystyle:=\max\big{(}\tilde{d}\leq
d^{\prime}\;\;s.t\;\;\text{ the honest players mined}$ $\displaystyle\text{the
first proposer block covering~{}}\tilde{d}\big{)}$

Let $r^{*}$ be the round in which the first proposer block covering $d^{*}$
was mined. $r^{*}=0$ and $d^{*}=0$ if such proposer block does not exists.
Define $U=\\{r^{*},\cdots,r\\}$, $S=\\{r^{*}+\Delta,\cdots,r-\Delta\\}$, and
$J$ the adversarial queries in $U$. Then we have $|S|=|U|-2\Delta\geq\ell$.
From the definition of $d^{*}$ we have the following two observations:

  1. (1)

All difficulties in $(d^{*},d^{\prime}]$ are covered by at least one
adversarial proposer block.

  2. (2)

All the proposer blocks covering $(d^{*},d]$ are mined in the interval $U$
because there are no proposer blocks covering $d^{*}$ before round $r^{*}$ and
hence no player can mine a proposer block covering a difficulty level greater
than $d^{*}$ before round $r^{*}$.

Let $L_{h}$ be the size of difficulty range covered by honest leader blocks in
the range $(d^{\prime},d]$ and say

(6) $L_{h}<\mu(d-d^{\prime})\leq\mu(d-d^{*}).$

Let $L_{h}^{\prime}$ be the size of difficulty range covered by honest leader
blocks in the range $(d^{*},d^{\prime}]$. The adversarial leader blocks have
covered difficulty ranges with size $d-d^{*}-L_{h}-L_{h}^{\prime}$ in the
interval $U$. From our first observation, we know that adversarial proposer
blocks in the difficulty range $[d^{*},d^{\prime}]$ which are not leader
blocks cover difficulty ranges with size at least $L_{h}^{\prime}$, and from
our second observation, these proposer blocks are mined in the interval $U$.
Therefore, we have the following bound on $A^{P}(J)$

$\displaystyle A^{P}(J)$
$\displaystyle\geq(d-d^{*}-L_{h}-L_{h}^{\prime})+L_{h}^{\prime}$
$\displaystyle=d-d^{*}-L_{h}$ $\displaystyle\left(\text{From Equation
}\eqref{eqn:local_contradition_1}\right)$ $\displaystyle>d-d^{*}-\mu(d-d^{*})$
(7) $\displaystyle=(1-\mu)(d-d^{*}).$

From the chain growth, we know that $d-d^{*}\geq Q^{P}(S)$ and combining this
with Equation (7) gives us

(8) $A^{P}(J)>(1-\mu)Q^{P}(S)=(1-\delta+3\varepsilon)Q^{P}(S),$

which contradicts Lemma B.5. ∎

##  Appendix D Persistence and Liveness of OHIE

###### Lemma D.1 (Common prefix and chain quality for each individual chain).

For a typical execution in a $(\gamma,2(1+\delta)\gamma^{2}m/f)$-respecting
environment, each chain $i$ ($0\leq i\leq m-1$) satisfy the the common-prefix
property with parameter $\ell_{\rm cp}=\ell+2\Delta$ and chain-quality
property with parameter $\ell_{\rm cq}=\ell+2\Delta$ and
$\mu=\delta-3\varepsilon$.

###### Proof.

The proof directly follows Lemmas B.6,B.7, 6.13 and 6.14. ∎

We call all blocks on a chain except the blocks with timestamp in last
$\ell+2\Delta$ rounds as partially confirmed. Then by Lemma D.1, we know that
the ordering of these partially confirmed blocks on their chain will no longer
change in the future. Recall that OHIE generates a SCB in the following way.
Consider any given honest node at any given time and its local view of all the
$m$ chains. Let $y_{i}$ be the ${\tt next\\_rank}$ of the last partially-
confirmed block on chain $i$ in this view. Let ${\tt
confirm\\_bar}\leftarrow\min_{i=1}^{k}y_{i}$. Then all partially-confirmed
blocks whose rank is smaller than ${\tt confirm\\_bar}$ are deemed as fully-
confirmed, and included in SCB. Finally, all the fully-confirmed blocks will
be ordered by increasing ${\tt rank}$ values, with tie-breaking favoring
smaller chain ids. Next, we will prove that the SCB generated in this way
satisfies persistence and liveness properties.

###### Theorem D.2 (Persistence and Liveness of OHIE ).

For a typical execution in a $(\gamma,2(1+\delta)\gamma^{2}m/f)$-respecting
environment, OHIE satisfies persistence and liveness with parameter
$u=2\ell+4\Delta$.

###### Proof.

We first prove the persistence property. Let $L_{1}$ and $L_{2}$ be the SCB
held by two honest node $u_{1}$ and $u_{2}$ at round $r_{1}$ and $r_{2}$
respectively, with $r_{2}>r_{1}+\Delta$. Let $x_{1}$ and $x_{2}$ be the ${\tt
confirm\\_bar}$ of $L_{1}$ and $L_{2}$, respectively. Then we will prove that
$L_{1}$ is a prefix of $L_{2}$.

Let $F_{1}(i)$ be the sequence of partially-confirmed blocks on chain $i$ in
$u_{1}$’s view at round $r_{1}$. Let $G_{1}(i)$ be the prefix of $F_{1}(i)$
such that $G_{1}(i)$ contains all blocks in $F_{1}(i)$ whose ${\tt rank}$ is
smaller than $x_{1}$. Similarly define $F_{2}(i)$ and $G_{2}(i)$, where
$G_{2}(i)$ contains those blocks in $F_{2}(i)$ whose ${\tt rank}$ is smaller
than $x_{2}$. We first prove the following two claims:

  * •

For all $i$, $0\leq i\leq m-1$, $G_{1}(i)$ is a prefix of $G_{2}(i)$. By round
$r_{2}$, node $u_{2}$ must have seen all blocks seen by $u_{1}$ at round
$r_{1}$. By the common prefix property in Lemma D.1, all partially-confirmed
blocks on $u_{1}$ at round $r_{1}$ must also be partially-confirmed on $u_{2}$
at round $r_{2}$, i.e., $F_{1}(i)$ is a prefix of $F_{2}(i)$. Then we have
$x_{1}\leq x_{2}$ and also $G_{1}(i)$ should be a prefix of $G_{2}(i)$.

  * •

For all $i$, $0\leq i\leq m-1$, and all block $B\in G_{2}(i)\setminus
G_{1}(i)$, $B$’s ${\tt rank}$ must be no smaller than $x_{1}$. We prove this
claim via a contradiction and assume that $B$’s ${\tt rank}$ is smaller than
$x_{1}$. Together with the fact that $B$ is in $G_{2}(i)\setminus G_{1}(i)$,
we know that $B$ is in $F_{2}(i)$ but not in $F_{1}(i)$. Let $x_{0}$ be the
${\tt rank}$ of the last block $B_{0}$ in $F_{1}(i)$. Since $F_{1}(i)$ is a
prefix of $F_{2}(i)$, both $B_{0}$ and $B$ must be in $F_{2}(i)$, and $B$ must
be a descendent of $B_{0}$ in $F_{2}(i)$. Since the blocks in $F_{2}(i)$ must
have increasing ${\tt rank}$ values, we know that $B_{0}$’s ${\tt rank}$ must
be smaller than $B$’s, hence we have $x_{0}<x_{1}$. On the other hand, since
$B_{0}$’s ${\tt next\\_rank}$ must be greater than its ${\tt rank}$, by the
design of ${\tt confirm\\_bar}$, we know that $x_{1}<x_{0}$. This yields a
contradiction.

Now we can use the above two claims to prove that $L_{1}$ is a prefix of
$L_{2}$. Note that $L_{1}=\cup_{0\leq i\leq m-1}G_{1}(i)$ and
$L_{2}=\cup_{0\leq i\leq m-1}G_{2}(i)$. Since $G_{1}(i)$ is a prefix of
$G_{2}(i)$ for all $i$, we know that $L_{1}\subseteq L_{2}$. For all blocks in
$L_{1}$, the sequence $L_{1}$ orders them in exactly the same way as the
sequence $L_{2}$. For all block $B\in L_{2}\setminus L_{1}$, by the second
claim above, we know that $B$’s ${\tt rank}$ must be no smaller than $x_{1}$.
Hence in the sequence $L_{2}$, all blocks in $L_{2}\setminus L_{1}$ must be
ordered after all the blocks in $L_{2}\cap L_{1}$ (whose ${\tt rank}$ must be
smaller than $x_{1}$). This completes our proof that $L_{1}$ is a prefix of
$L_{2}$.

We next prove the liveness property. Suppose a transaction tx is received by
all honest nodes before or at round $r_{0}$. Let $L$ be the SCB of an honest
node $u$ at round $r\geq r_{0}+2\ell+4\Delta$ and $x$ be the ${\tt
confirm\\_bar}$ of $L$. For $0\leq i\leq m-1$, let $F(i)$ be the sequence of
partially-confirmed blocks on chain $i$ in $u$’s view at round $r$ and $G(i)$
be the prefix of $F(i)$ such that $G(i)$ contains all blocks in $F(i)$ whose
${\tt rank}$ is smaller than $x$. Without loss of generality, assume $x$ is
the ${\tt next\\_rank}$ of the last block in $F(0)$. Then we have
$G(0)=F(0)\subset L$. By the chain quality property in Lemma D.1, we know that
there exists at least one honest block $B$ on chain 0 whose timestamp is in
the interval $(r-2\ell-4\Delta,r-\ell-2\Delta)$. As $B$ is an honest block
mined after $r_{0}$, $B$ or an ancestor of $B$ must contain $\sf tx$.
Therefore $L$ contains $\sf tx$ since $B$ and all its ancestors are fully
confirmed. ∎

##  Appendix E Fairness of FruitChains

For our analysis to go through, we choose the following protocol parameters
for FruitChains:

(9)
$\ell\triangleq\frac{4(1+3\varepsilon)}{\varepsilon^{2}f[1-(1+\delta)\gamma^{2}f]^{\Delta+1}}\max\\{\Delta,\tau\\}\gamma^{4}\lambda,$
(10) $\Phi=4(1+\delta)\gamma^{2}f(\ell+3\Delta)/\varepsilon,$

and

(11) $s=2(1+\delta)\gamma^{2}\Phi/f.$

Note that in Equation (9), we define a larger $\ell$ than in Equation (3) for
Prism and OHIE. This is for the proof of fairness to work. Since Equation (10)
satisfies Equation (4) and $s$ is selected the same as in Prism and OHIE, all
the pivot-chain properties stated in Appendix B still hold for FruitChains.
Therefore, the persistence and liveness of variable difficulty FruitChains
simply follow the persistence and liveness of Bitcoin, as the protocols are
identical if we ignore the content of the blocks. In this section, we formally
prove the fairness property guaranteed by FruitChains. To ease the analysis,
we assume $t_{r}=(1-\delta)n_{r}$ for all rounds $r$, i.e., the number of
adversarial queries in the worst case. We first give a definition of fairness.

###### Definition E.1.

We say that ${\mathcal{H}}$ is a $\phi$-fraction honest subset if players in
${\mathcal{H}}$ (that may change over time) are honest and
$n^{{\mathcal{H}}}_{r}=\lceil\phi(n_{r}+t_{r})\rceil=\lceil\phi(2-\delta)n_{r}\rceil$
for round $r$, where $n^{{\mathcal{H}}}_{r}$ is number of players in
${\mathcal{H}}$ at round $r$.

###### Definition E.2 (Fairness).

We say the FruitChains  protocol has (approximate) $\sigma-$fairness if for
any $0<\phi<\frac{1}{2-\delta}$ and any $\phi-$fraction honest subset
${\mathcal{H}}$, there exists $W_{0}\in\mathbb{N}$ such that for any honest
player holding chain ${\mathcal{C}}$ at round $r$ and any interval
$S_{0}\in[0,r]$ with at least $W_{0}$ consecutive rounds, let
${\mathcal{C}}(S_{0})$ be the segment of ${\mathcal{C}}$ containing blocks
with timestamps in $S_{0}$ and $d$ be the total difficulty of all fruits
included in ${\mathcal{C}}(S_{0})$, then it holds that the fruits included in
${\mathcal{C}}(S_{0})$ mined by ${\mathcal{H}}$ have total difficult at least
$(1-\sigma)\phi d$.

By the common prefix property proved in Lemma B.6, for a chain ${\mathcal{C}}$
held by an honest node at round $r$, the prefix
${\mathcal{C}}^{\lceil\ell+2\Delta}$ are stabilized, so to mine a fruit/block
at round $r$ an honest miner will select the tip of
${\mathcal{C}}^{\lceil\ell+2\Delta}$ as the fruit parent by our proposed
variable difficulty FruitChains  algorithm. And we set the recency parameter
$R=3\ell+7\Delta$, i.e., a fruit $B_{f}$ is recent w.r.t. a chain
${\mathcal{C}}$ at round $r$ if the fruit parent of $B_{f}$ is in
${\mathcal{C}}$ and has timestamp at least $r-3\ell-7\Delta$. With this
selection of the recency parameter, we can prove the following key property of
the FruitChains  protocol: any fruit mined by an honest player will be
incorporated into the stabilized chain (and thus never lost). We refer to this
as the Fruit Freshness Lemma—fruits stay “fresh” sufficiently long to be
incorporated.

###### Lemma E.3 (Fruit Freshness).

For a typical execution in a $(\gamma,2(1+\delta)\gamma^{2}\Phi/f)$-respecting
environment, if $R=3\ell+7\Delta$, then an honest fruit mined at round $r$
will be included into the stabilized chain before round $r+r_{\rm wait}$,
where $r_{\rm wait}=2\ell+5\Delta$.

###### Proof.

Suppose an honest fruit $B_{f}$ is mined at round $r_{0}$ with block parent
being the tip of ${\mathcal{C}}_{0}$, then the fruit parent of $B_{f}$ is the
tip of ${\mathcal{C}}_{0}^{\lceil\ell+2\Delta}$. Further, by the NoStaleChains
property (defined in Appendix B), the fruit parent of $B_{f}$ has timestamp
$r_{1}\geq r_{0}-2\ell-4\Delta$. By round $r_{0}+\Delta$, all honest nodes
will receive $B_{f}$. Let $r_{2}=r_{0}+2\ell+5\Delta$ and ${\mathcal{C}}$ be
any chain held by honest nodes at round $r_{2}$, then by the chain quality
property in Lemma B.7, we know that there exists at least one honest block $B$
on ${\mathcal{C}}$ whose timestamp $r_{3}$ is in the interval
$(r_{2}-2\ell-4\Delta,r_{2}-\ell-2\Delta)$. We check that $B_{f}$ is still
recent at round $r_{3}$ as

$r_{3}-r_{1}<(r_{2}-\ell-2\Delta)-(r_{0}-2\ell-4\Delta)=3\ell+7\Delta=R.$

As $B$ is an honest block mined after $r_{0}+\Delta$, $B$ or an ancestor of
$B$ must include $B_{f}$. And since $B$ is stabilized in ${\mathcal{C}}$ at
round $r_{2}$, we have that $r_{\rm wait}=r_{2}-r_{0}=2\ell+5\Delta$ ∎

Define the random variable $D_{r}$ equal to the sum of the difficulties of all
fruits computed by honest parties at round $r$. And for fixed $\phi$ and
$\phi-$fraction honest subset ${\mathcal{H}}$, define the random variable
$D^{{\mathcal{H}}}_{r}$ equal to the sum of the difficulties of all fruits
computed by parties in ${\mathcal{H}}$ at round $r$. For a set of rounds $S$,
we define $D(S)=\sum_{r\in S}D_{r}$, $D^{{\mathcal{H}}}(S)=\sum_{r\in
S}D^{{\mathcal{H}}}_{r}$, and $n^{{\mathcal{H}}}(S)=\sum_{r\in
S}n^{{\mathcal{H}}}_{r}$. For a set of $J$ adversarial queries, define the
random variable $A(J)$, as the sum of difficulties of all the fruits created
during queries in $J$.

Next we define the following fruit-typical execution.

###### Definition E.4 (Fruit-typical Execution).

An execution $E$ is fruit-typical if the followings hold

(a) For any set $S$ of at least $\ell$ consecutive good rounds,

$\displaystyle D(S)<(1+\varepsilon)pn(S).$

(b) For any set $S$ of at least $\ell$ consecutive good rounds, let $J$ be the
set of adversarial queries in $S$, if we further know each query in $J$ made
at round $r$ with target $T$ satisfies $f/2\tau\gamma^{3}\leq
pn_{r}T\leq(1+\delta)\tau\gamma^{3}f$, then

$D(S)+A(J)<(1+\varepsilon)p(n(S)+|J|).$

(c) For any set $S$ of at least $\ell/\phi(2-\delta)$ consecutive good rounds,

$D^{{\mathcal{H}}}(S)>(1-\varepsilon)pn^{{\mathcal{H}}}(S).$

###### Theorem E.5.

For an execution $\mathcal{E}$ of $L$ rounds, in a $(\gamma,s)$-respecting
environment, the probability of the event “$\mathcal{E}$ not fruit-typical” is
bounded by $\mathcal{O}(L)e^{-\lambda}$.

###### Proof.

The proof for (a) is the same as in [13]. For (b), by the condition, for each
query in $S$ (made either by an honest node or the adversary) at round $r$
with target $T$, we have $f/2\tau\gamma^{3}\leq p(n_{r}+t_{r})T\leq
2(1+\delta)\tau\gamma^{3}f$. Therefore, the proof is similar to [13] (by
setting $\ell$ to be slightly larger as we did in Eqn.(9)).

For (c), let the execution be partitioned into parts such that each part has
at least $l/{\phi(2-\delta)}$ rounds and at most $s$ rounds. We will prove
that the statement fails with a probability less than $e^{-\lambda}$ for each
part. Let $J$ denote the queries made by $\mathcal{H}$ in rounds $S$. We have
$|J|=n^{\mathcal{H}}(S)=n(S)\phi(2-\delta)$. For $k\in[|J|]$, let $Z_{i}$ be
the difficulty of any block obtained from query $j\in J$. Then

$\displaystyle X_{0}=0$ $\displaystyle
X_{k}=\sum_{i\in[k]}Z_{i}-\sum_{i\in[k]}\mathbb{E}[Z_{i}|\mathcal{E}_{i-1}]$

is a martingale with respect to $\mathcal{E}_{0},\ldots,\mathcal{E}_{k}$. We
have

$\displaystyle X_{k}-X_{k-1}$
$\displaystyle=X_{k}-\mathbb{E}[X_{k}|\mathcal{E}_{k-1}]=Z_{k}-\mathbb{E}[Z_{k}|\mathcal{E}_{k-1}]$
$\displaystyle\leq\frac{1}{T_{k}^{min}}=\frac{pn_{k}}{pn_{k}T_{k}^{min}}\leq
2\gamma^{3}pn(S)/f|S|:=b.$

Similarly

$\displaystyle V$
$\displaystyle=\sum_{k}var[X_{k}-X_{k-1}|\mathcal{E}_{k-1}]\leq\sum_{k}\mathbb{E}[Z_{k}^{2}|\mathcal{E}_{k-1}]$
$\displaystyle=\sum_{k}pT_{k}\frac{1}{T_{k}^{2}}\leq
2\gamma^{3}p^{2}|J|n(S)/f|S|:=v.$