---
bibliography:
- 'references.bib'
---

[0.490]{}

[0.490]{}

Introduction
============

Bitcoin surprised scholars in distributed systems, as well as in security [@bonneau2015SoKResearch]. Authors have called the new composition of known concepts a “sweet spot” [@tschorsch2016BitcoinTechnical] in the design space for protocols, and praised the complex way the components are put together as a “true leap of insight” [@narayanan2017BitcoinAcademic] of Nakamoto [@nakamoto2008BitcoinPeertopeer]. Likely the most intriguing part is the way Bitcoin uses proof-of-work puzzles to secure a distributed log. The role of proof-of-work in Nakamoto consensus can be contemplated in several ways. First and most intuitively, the computational puzzles can be interpreted as a rate limit on new identities, which discourage Sybil attacks [@douceur2002SybilAttack] in a lottery for blocks and new coins. Second, proof-of-work can be conceived as a game-proof variant of a probabilistic back-off mechanism, as used in media access control in computer networks. It reduces the risk of collisions when many nodes concurrently seek write access to a shared medium, the ledger. Proof-of-work has been formalized in cryptographic security models of Nakamoto consensus [@garay2015BitcoinBackbone; @pass2017AnalysisBlockchain]. However, we are not aware of work pointing out the fundamental conflict between inclusiveness and security inherent to the way proof-of-work is used in the known distributed log protocols. This conflict precludes reliable and fast commits. Arguably, it is the reason why practical protocols trade finality for eventual consistency. But the lack of finality limits the applicability for high-value transactions [@bonneau2016WhyBuy; @gervais2016SecurityPerformance], a potential show-stopper discussed even beyond the technical community [@budish2018EconomicLimits; @auer2019DoomsdayEconomics].

We tackle this conflict directly, leading to a theory of proof-of-work quorums, which enables new ways of using proof-of-work in permissionless distributed log protocols. We propose one such protocol, , demonstrating that finality with reliable and short time to commit is possible. Specifically, we do not rely on sidechains, a tool used in the literature to stack Byzantine on top of Nakamoto consensus [@kogias2016EnhancingBitcoin; @pass2017HybridConsensus; @pass2018ThunderellaBlockchains]. Sidechains can add finality and increase throughput at the price of increased complexity, overhead, and tricky issues in the synchronization between layers [@kogias2016EnhancingBitcoin; @eyal2016BitcoinNGScalable].

The proposed protocol is inspired by two recent breakthroughs: Bobtail [@bissias2020BobtailImproved] and HotStuff [@yin2019HotStuffBFT]. The former optimizes stochastic properties of the block delay in Nakamoto consensus. The latter adapts principles of Byzantine fault tolerance to blockchains in a clever way. It has received attention after Facebook’s announcement to use it in LibraBFT [@calibra2019librabft].

We make the following contributions:

1.  We draw attention to a fundamental conflict between inclusiveness and security in and propose a principled resolution (Section \[sec:intuition\]).

2.  We develop a theory of proof-of-work quorums where quorums are formed over votes generated by stochastic processes. We show that sufficiently large quorums are practically unique (Section \[sec:pow\_quorum\]).

3.  We propose , a protocol that finds consensus over a distributed log without requiring pre-defined identities. scales at least as well as practical blockchain protocols and much better than Byzantine fault tolerance protocols. It relies on proof-of-work, but, unlike deployed systems using the longest chain rule, our construction supports a three-phase commit logic. State updates (transactions) are final after a predictable amount of time, and the probability of inconsistency is bounded according to our theory (Section \[sec:protocol\]).

4.  We simulate executions of as well as of variants with adversarial modifications. The results show that the protocol can tolerate network latency, churn, and targeted attacks on consistency and liveness at small overhead compared to the best deployed systems (Section \[sec:evaluation\]).

Section \[sec:discussion\] compares to related works and discusses its limitations. Section \[sec:conclusion\] concludes. For replicability and future research, we make the protocol implementation and the simulation code available online.

Intuition {#sec:intuition}
=========

The key conflict between inclusiveness and security faced by cryptocurrencies is as follows: *minorities should be encouraged to participate (inclusiveness), but they should not be able to make decisions alone (security).* achieves inclusiveness by sacrificing security for an uncertain period of time (eventual consistency). This becomes problematic when irreversible real-world actions are taken based on unsettled transactions in the distributed log (double spending). A short and reliable time to commit would mitigate this risk.

Recall that prioritizes inclusiveness by using a puzzle as gatekeeper to participation. The protocol specifies a repeated race for the first puzzle solution. Each winner proposes a state update and receives some reward. Most cryptocurrencies use puzzles—moderately hard functions—for which iterative trial and error is the best known solving algorithm. Such puzzles imply exponentially distributed solving time. Figure \[fig:min\_maj\_exp\] shows the probability distributions for the solving times of a $2/3$ majority of solving power compared to a $1/3$ minority. The expected time of the end of the race is marked with $\hat{t}_1$ (in Bitcoin $\hat{t}_1 \approx 10$ minutes). Consequently, the area under each curve represents the odds of winning the race. Observe that the minority has a fair chance. This makes the protocol inclusive, but also implies that minorities have a significant chance of directly writing state updates. For improved security, we would prefer a distribution such that the minority’s area under the curve is small (ideally negligible), as displayed in Figure \[fig:min\_maj\_gamma\].

Since the puzzle of behaves like in Figure \[fig:min\_maj\_exp\], a single state update is not reliable. As a result, users are recommended to wait for multiple consecutive blocks before acting upon a payment. The time needed for sequentially solving $k$ exponential puzzles is gamma distributed with shape parameter $k$. In fact, Figure \[fig:min\_maj\_gamma\] shows the gamma distribution for $k = 6$. Note the significant gap between minority and majority: it is unlikely that a minority can generate a sequence of $6$ state updates before the majority does so. In this sense, multiple puzzle solutions qualify a majority, while a single one does not.

In , security comes at the price of waiting for multiple solutions. Bitcoin’s convention of $k=6$ implies an expected waiting time of $\hat{t}_2 \approx 60$ minutes, which is arguably too slow for many applications. Besides, does not give a rationale on how to choose $k$.

A key idea for resolving this conflict is to break the one-to-one relationship between puzzle solutions and blocks. Instead of requiring a single $10$ minute puzzle per block, asks for $k$ easier puzzles each expected to take $10/k$ minutes. In other words, achieves security by appending puzzle solutions *in parallel* rather than sequentially, as illustrated in Figure \[fig:seq\_vs\_par\]. Since the puzzles are independent, we end up with the same block rate but $k$ times the number of solutions. The expected computational effort stays the same, but we accumulate a qualifying number of solutions for *every* block. This means we get the shape of Figure \[fig:min\_maj\_gamma\] much faster: $\hat{t}_2 \approx
\hat{t}_1$.

For a principled construction of , we reduce the payload “authenticated” [@back2014EnablingBlockchain] by proof-of-work to a minimum:

1.  a reference to a recent point in time ( a hash link to the last seen block)

2.  a reference to an identity (public key or commitment)

A triple of a puzzle solution and these two references forms a verifiable ephemeral identity. The puzzle solution binds resources in order to prevent Sybil attacks, the reference in time ensures freshness, and the identifier enables authorized actions, such as claiming a reward.

The main difference between proof-of-work systems and the well-studied class of Byzantine fault tolerant (BFT) systems [@lamport1982ByzantineGenerals; @dwork1988ConsensusPresence; @castro2002PracticalByzantine] is that the former do not rely on external identification of the participating nodes. Inspired by the early work of @aspnes2005Exposingcomputationallychallenged, uses proof-of-work to bootstrap ephemeral identities and plugs them into HotStuff [@yin2019HotStuffBFT], a state of the art blockchain-based BFT system. In HotStuff, each block carries a certificate about a qualified majority of nodes (quorum) confirming the last seen block. HotStuff’s proof of finality is based on the qualifying properties of each quorum. This motivates us to explore whether and to what extent a set of proof-of-work solutions can qualify a majority. In Section \[sec:pow\_quorum\], we will show that qualifying majorities are possible within a single block. This allows us to transfer HotStuff’s finality to the permissionless setting.

The recurse to HotStuff enables us to fix the number of blocks to wait before accepting a state update as final at the necessary number of phases to commit, thereby resolving a drawback of . As illustrated in Figure \[fig:pipeline\], HotStuff uses a three-phase commit, which can be pipelined for subsequent state updates on a blockchain. In a nutshell, the first phase locks a single proposal, the second phase confirms majority uptake of this lock, and the third phase ensures that the knowledge of this knowledge is propagated. We refer to [@yin2019HotStuffBFT] for the rationales and failure modes. In this sense, parallelizes not only puzzle solutions but also the phases of the commit logic.

(0,0) node \[draw\] (a1) ; (1,0) node \[draw\] (a2) ; (2,0) node \[draw\] (a3) ;

(1,-1) node \[draw\] (b1) ; (2,-1) node \[draw\] (b2) ; (3,-1) node \[draw\] (b3) ;

(2,-2) node \[draw\] (c1) ; (3,-2) node \[draw\] (c2) ; (4,-2) node \[draw\] (c3) ;

in [a,b,c]{} [ (2.west)–(1.east); (3.west)–(2.east); (1.west)–++(-4mm,0); ]{}

(-2, 0) node [Phase 1]{}; (-2,-1) node [Phase 2]{}; (-2,-2) node [Phase 3]{};

(2,.38) – (2,-2.2); (2,.35) – (2,-2.15); at (1.975,-0.7) [commit]{};

Another advantage of the gamma distribution per block is a reduction in the variance of block delays compared to the exponential distribution implied by the puzzle. While the commit pipeline gives us finality after three blocks, the reduced variance translates this into a reliable time to commit. The theory in the following section shows formally how all this is related to the quorum size, ’s new security parameter.

Proof-of-Work Quorums {#sec:pow_quorum}
=====================

Quorums are central to the design and analysis of BFT protocols. The typical Byzantine setting assumes a set of $n =
3f + 1$ identified nodes, of which at most $f$ deviate from the protocol. A set of $2f + 1$ votes for the same value is called a quorum. If correct nodes vote at most once, quorums imply a majority decision and thus are unique. The uniqueness may be violated in two situations.

1.  More than $n$ nodes vote. \[bft-network\]

2.  More than $f$ nodes vote more than once. \[bft-adversary\]

Practical systems avoid \[bft-network\] using preset identities for all nodes and rule out \[bft-adversary\] by assumption.

Proof-of-work enables systems where agents can join and leave at any time without obtaining permission from an identity provider or gatekeeper [@nakamoto2008BitcoinPeertopeer]. This difference is often implied in the terms “permissioned” and “permissionless”. In the permissionless case one must distinguish between *agents* and *nodes*. Agents are entities participating in a distributed system. An agent can operate any number of nodes. Colluding parties are interpreted as a single agent. We introduce the notion *proof-of-work quorum* for a set of votes where each vote requires a solution to a proof-of-work puzzle. Since the puzzle solving time is probabilistic, the uniqueness of quorums cannot be absolute. In contrast to the Byzantine setting, we have to consider three failure modes:

1.  The total compute power of the network is higher than assumed. \[pow-network\]

2.  The adversary controls more than the assumed fraction of compute power. \[pow-adversary\]

3.  A random bad realization happens. \[pow-probability\]

The failure modes \[pow-network\] and \[pow-adversary\] correspond to the Byzantine failure modes \[bft-network\] and \[bft-adversary\]. Our goal is to understand the new failure mode \[pow-probability\] and how it affects the potential ambiguity (violation of uniqueness) of quorums.

\[def:process\] A proof-of-work process is a stochastic count process where each event assigns one *ability to vote* (ATV) to one agent. Each ATV can be used by the agent it is assigned to, to vote once for one value.

We adopt the notion of a quorum from the BFT literature [@malkhi1998ByzantineQuorum; @yin2019HotStuffBFT] except that we will apply it to votes from ATVs rather than identified nodes.

\[def:quorum\] A set of $\qsize$ votes for the same value $x$ is called a $\qsize$-quorum for $x$.

Observing a $\qsize$-quorum implies that at least $\qsize$ ATVs have been used, hence the proof-of-work process must have assigned at least $\qsize$ ATVs. This connects to time.

\[def:oqt\] The time at which the proof-of-work process assigns the $\qsize$-th ATV is called optimistic $\qsize$-quorum time. For a proof-of-work process $P$ and quorum size $\qsize$ it is formally defined by the random variable $$T_{P,\qsize} := \inf\{t \in \realsgez \mid P(t) \geq \qsize\} \,.$$

$T_{P,\qsize}$ is the earliest point in time at which a $\qsize$-quorum is feasible. A $\qsize$-quorum is only possible at exactly $T_{P,\qsize}$, if all assigned ATVs are used to vote for the same value.

A quorum for $x$ is ambiguous if there is another quorum for $y \neq x$. Since each ATV can be used for at most one value, ambiguous $\qsize$-quorums are only possible when the proof-of-work process has assigned at least $2\qsize$ ATVs.

\[def:poa\] For a proof-of-work process $P$ and quorum size  we define the *probability of ambiguity* (POA) as $${\ensuremath{\operatorname{poa}}}_{P, \qsize}(t) := \prob{P(t) \geq 2 \qsize} \,.$$

For puzzles where the best known solving algorithm is independent trial and error, the stochastic process is instantiated by the Poisson process $P_\lambda$. This is because if each puzzle solution generates one ATV, the time between consecutive ATVs is exponentially distributed with rate $\lambda$.

\[lem:poa\_poisson\] The POA for the Poisson process $P_\lambda$ is given by $${\ensuremath{\operatorname{poa}}}_{P_\lambda, \qsize}(t) =
    1 - e^{-\lambda t} \sum_{i=0}^{2\qsize -1}{\frac{(\lambda t)^i}{i!}} \,.$$

See Appendix \[apx:proofs\].

\[lem:qt\_possion\] The optimistic -quorum time for the Poisson process is Erlang distributed with shape parameter  and rate parameter $\lambda$, in short $$T_{P_\lambda,\qsize} \drawn \distErlang(\qsize, \lambda) \,.$$

See Appendix \[apx:proofs\].

\[cor:tEv\] The expected optimistic $\qsize$-quorum time for the Poisson process is $${\ensuremath{\bar{t}_{\lambda, \qsize}}}:= \ev{T_{P_\lambda,\qsize}} = \qsize / \lambda\,.$$

The statement follows from Lemma \[lem:qt\_possion\] and the definition of the Erlang distribution [@stewart2009ProbabilityMarkov p. 146].

Figure \[fig:opt\_qtime\] illustrates the distribution of the optimistic $\qsize$-quorum time for $\qsize \in \{1,2,16\}$ based on the Poisson process. In order to compare quorum sizes greater than one to an ideal Bitcoin ($\qsize=1$, ${\ensuremath{\bar{t}_{\lambda, \qsize}}}{}=10$ minutes), we choose $\lambda = \qsize / 10$.

Figure \[fig:poa\_over\_time\] shows the POA for different quorum sizes as a function of time. Again, we adjust the rate such that the expected optimistic -quorum time is 10 minutes. Observe that the POA increases over time as the number of ATVs grows. More importantly, the POA at the expected optimistic quorum time decreases in the quorum size .

In order to isolate the effect of , we evaluate the POA at fixed time [$\bar{t}_{\lambda, \qsize}$]{}, which lends itself to a closed form.

\[cor:poa\_at\_ev\] For the Poisson process, the POA at expected optimistic -quorum time is given by $${\ensuremath{\operatorname{poa}}}_{P_\lambda, \qsize}({\ensuremath{\bar{t}_{\lambda, \qsize}}}) =
    1 - e^{-\qsize} \sum_{i=0}^{2\qsize -1}{\frac{\qsize^i}{i!}} \,.$$

By inserting Corollary \[cor:tEv\] into Lemma \[lem:poa\_poisson\].

Observe that the POA at expected optimistic quorum time is independent of $\lambda$. This is useful as $\lambda$ may measure the total compute capacity in proof-of-work networks, which is not necessarily known to each agent.

Since ambiguity causes failure, and the probability of ambiguity vanishes as $\qsize$ grows, $\qsize$ becomes a security parameter. In order to relate it to other security parameters, such as the key size, we adopt the common definition of negligibility from cryptography ( asymptotic decline faster than any polynomial) and state the following theorem.

\[thm:negligible\] For the Poisson process, the probability of ambiguity at the expected quorum time is negligible in the quorum size $\qsize$.

See Appendix \[apx:proofs\].

For Bitcoin parameters ($\qsize=1, \lambda=0.1$), the POA at [$\bar{t}_{\lambda, \qsize}$]{} is $p
= 0.2642$. This part of the theory can be validated on historical data. We estimate the expected block delay by averaging the differences between consecutive block time stamps over 2017–2018.[^1] The estimated average block delay is $\hat{t}=9.52$ minutes. The ratio of cases with more than two blocks arriving within $\hat{t}$ is $\hat{p} = 0.2606$. This estimate should be slightly below $p$ because our historic data does not contain orphaned blocks. Since $p \approx \hat{p}$, we conclude that the theory applies to Bitcoin.

The implication of this theory for protocol design is that larger quorums reduce the probability of ambiguity. The (close to) exponential decay makes it conceivable to choose parameters such that quorums are practically unique. This allows us to use a notion of quorum uniqueness with ephemeral identities generated by proof-of-work.

 {#sec:protocol}

Now we specify , a distributed log protocol secured by a proof-of-work process (Def. \[def:process\]) and $\qsize$-quorums (Def. \[def:quorum\]).

We present using pseudocode and a mixture of event-driven and imperative programming. A less ambiguous implementation in OCaml is provided online.

Prerequisites {#ssec:proto_prerequisites}
-------------

We assume interfaces to the network and application layers (Fig. \[fig:appstack\]), and the availability of cryptographic primitives.

### Broadcast Network {#sssec:method_net}

The proposed protocol requires a (potentially unreliable) network broadcast. We abstract from the exact implementation and assume that scheduling an event results in the message $m$ being sent to (most of) the other nodes. On the receiving side, the implementation delivers message $m'$ by scheduling .

### Application {#sssec:method_app}

implements a distributed log which may serve as a base for different applications [@lamport1978TimeClocks; @schneider1990ImplementingFaulttolerant; @abraham2017BlockchainConsensus]. For example, a simple cryptocurrency could append lists of transactions which jointly form a ledger. More advanced applications could add scalability layers that only record key decisions in the distributed log while handling other state updates separately [@eyal2016BitcoinNGScalable; @kogias2016EnhancingBitcoin; @pass2018ThunderellaBlockchains].

We abstract from the application logic using three procedures can call. takes an application state and a state update as arguments and returns true if the state update is valid. takes an application state and a state update and returns an updated state. takes an application state and returns a valid state update. We are agnostic about direct access of the application to the broadcast network. For example, cryptocurrencies share transactions provisionally before they are logged in blocks.

### Cryptography {#ssec:method_dsa}

\[ssec:method\_hash\] uses cryptographic hash functions for the hash-linked list and the proof-of-work process. We separate these two concerns and use two different hash functions, [$\mathcal{H}_{\text{list}}$]{} and [$\mathcal{H}_{\text{pow}}$]{}. While it is sufficient that [$\mathcal{H}_{\text{list}}$]{} is cryptographically secure, requires the same stronger assumptions for [$\mathcal{H}_{\text{pow}}$]{} as Bitcoin [@abraham2017BlockchainConsensus]. Since this difference is not central, the reader can safely assume ${\ensuremath{\mathcal{H}_{\text{list}}}}{} = {\ensuremath{\mathcal{H}_{\text{pow}}}}{} = \operatorname{SHA3}$.

also requires a digital signature scheme [@katz2014IntroductionModern Def. 12.1, p. 442]. We assume a secure implementation is given by the three procedures , , and . Every node holds an asymmetric key pair (me, secret).

Protocol
--------

### Local Block Store {#sssec:proto_global}

nodes maintain a local tree of hash-linked blocks and a reference to the preferred chain (head). They store blocks together with the associated application state, the block height, and a set of corresponding votes (see Listing \[lst:store\]). The block storage is indexed by [$\mathcal{H}_{\text{list}}$]{}.

h $\gets {\ensuremath{\mathcal{H}_{\text{list}}}}(\text{B})$ parent $\gets$ blocks\[B.parent\] blocks\[h\].parent $\gets$ parent blocks\[h\].state $\gets$ blocks\[h\].height $\gets$ parent.height + 1 blocks\[h\].votes $\gets \emptyset$ blocks\[h\].block $\gets$ B

### Votes {#sssec:proto_vote}

As mentioned in Section \[sec:intuition\], a vote in is a triple [$({\ensuremath{{\ensuremath{r}},{\ensuremath{p}},{\ensuremath{s}}}})$]{}, where [$r$]{} is a reference to a previous block, [$p$]{} is the public key of the voter, and [$s$]{} is a puzzle solution. A vote [$({\ensuremath{{\ensuremath{r}},{\ensuremath{p}},{\ensuremath{s}}}})$]{} is valid if ${\ensuremath{\mathcal{H}_{\text{pow}}}}{\ensuremath{({\ensuremath{{\ensuremath{r}},{\ensuremath{p}},{\ensuremath{s}}}})}}\leq \vthres$, where denotes the proof-of-work threshold and represents ’s difficulty parameter. nodes maintain a set of valid votes for each block. The procedure (Listing \[lst:collect\]) adds a valid vote [$({\ensuremath{{\ensuremath{r}},{\ensuremath{p}},{\ensuremath{s}}}})$]{} to the block referenced by [$r$]{} and, if necessary, updates the preferred chain (see Sect. \[sssec:proto\_preference\] below).

blocks\[[$r$]{}\].votes $\gets$ blocks\[[$r$]{}\].votes $\cup \{\text{({\ensuremath{p}}{}, {\ensuremath{s}}{})}\}$

### Quorums {#sssec:proto_quorum}

As defined in Section \[sec:pow\_quorum\], a -quorum is a set of  votes for the same reference. We represent such quorums as lists. Since the reference is the same for all votes, we omit it from the list. A list $L = \{({\ensuremath{p}}_i, {\ensuremath{s}}_i)\}$ represents a valid -quorum for ${\ensuremath{r}}$, if the following conditions hold:

1.  \[qcond\_size\]$|L| = \qsize$

2.  \[qcond\_threshold\] $\forall\, 1 \leq i \leq \qsize \colon {{\ensuremath{\mathcal{H}_{\text{pow}}}}({\ensuremath{r}}, {\ensuremath{p}}_i, {\ensuremath{s}}_i)} \leq \vthres$

3.  \[qcond\_order\] $\forall\, 1 \leq i < \qsize \colon {\ensuremath{\mathcal{H}_{\text{pow}}}}({\ensuremath{r}}, {\ensuremath{p}}_i, {\ensuremath{s}}_i) \leq {\ensuremath{\mathcal{H}_{\text{pow}}}}({\ensuremath{r}}, {\ensuremath{p}}_{i+1}, {\ensuremath{s}}_{i+1})$

The first condition enforces the quorum size. The second condition ensures that all votes are valid. The third condition imposes a canonical order which we use for leader election. We intentionally allow single nodes providing multiple votes. Sibyl attacks are mitigated by the scarcity of votes.

### Leader Election {#sssec:proto_leader}

A quorum can only be formed at optimistic quorum time (Def. \[def:oqt\]) if all nodes vote for the same block. We facilitate coordination by electing a leader who is responsible for proposing a new block. This election is based on the proof-of-work quorum: the leader is identified by the smallest vote. According to Section \[sssec:proto\_quorum\] Condition \[qcond\_order\], this vote is also the first element of the quorum. Leaders authenticate their proposals for the next block using and their private key. Everyone verifies proposals with the first public key in the quorum.

### Blockchain {#sssec:proto_block}

The global data structure of the protocol is a hash-linked list of blocks. Each block consists of a hash reference to its predecessor (parent), a proof-of-work quorum for this predecessor, a payload, and a proof of leadership (signature). The references to parent blocks are established by the collision-resistant hash function [$\mathcal{H}_{\text{list}}$]{}. The payload is a state update to the application implemented on top of the distributed log (see Sect. \[sssec:method\_app\]).

With quorums, leader election, and state updates defined, we are in the position to present ’s block validity rule in Listing \[lst:valid\_block\]. The loop iterates over the quorum, counts the votes, verifies them, and checks their canonical order. The boolean conjunction in line \[l:threecond\] verifies the remaining condition of the quorum, leadership, and the validity of the proposed state update.

$(c,h)  \gets (0,0)$ $h' \gets {\ensuremath{\mathcal{H}_{\text{pow}}}}(\text{B.parent}, {\ensuremath{p}}, {\ensuremath{s}})$ \[l:predecessor\] false false $(c,h)  \gets (c + 1, h')$ \[l:threecond\] $c = \qsize$ $\wedge$ $\wedge$

A key difference to is that the proof-of-work solutions in the quorum are bound to the previous block and not to the state update of the proposed block (see line \[l:predecessor\]). This implements the separation of puzzle solutions from block proposals and enables parallel puzzle solving (see Sect. \[sec:intuition\]).

### Proposing {#sssec:proto_propose}

Nodes assume leadership whenever possible. If so, the procedure (Listing \[lst:propose\]) obtains a state update from the application, integrates it into a new valid block, and shares it with the other nodes.

B.parent $\gets r$ B.quorum $\gets Q$ B.payload $\gets$ B.signature $\gets$ \[l:sendblock\] true  false

### Commit {#sssec:proto_commit}

Proposals become final after the three-phase commit. Each subsequent block carries a quorum that completes one phase, like in HotStuff (see Sect. \[sec:intuition\]). Consequently, the most recent application state can be retrieved from the local block store as shown in Listing \[lst:read\_state\].

blocks\[head\].parent.parent.parent.state

### Conflict Resolution {#sssec:proto_progress}

The commit becomes effective after three blocks, but we have to consider conflicting block proposals at the uncommitted frontier. For example, when more than $\qsize$ votes exist, the leader election is not unique. Moreover, a malicious leader can send different proposals without solving additional proof-of-work puzzles. Nodes resolve such conflicts based on the progress towards the *next* quorum.

### Block Preference {#sssec:proto_preference}

When learning of a new block or vote, nodes update their preferred chain according to a modified version of Nakamoto’s longest chain rule. adapts it to include information on quorum progress (Sect. \[sssec:proto\_progress\]) and reject changes to already committed state (Sect. \[sssec:proto\_commit\]). Procedure (Listing \[lst:update\_head\]) takes a candidate block reference and updates the preferred chain if necessary.

H $\gets$ blocks\[head\] R $\gets$ blocks\[[$r$]{}\] $d \gets \text{R.height} - \text{H.height}$ $($R, $d) \gets ($R.parent, $d - 1)$ head $\gets {\ensuremath{r}}$ \[l:detectfork\]

### Main Program

Listing \[lst:hotpow\] shows the set of event handlers that tie everything together and define a node. The execution is initiated by scheduling the event. The listing shows how nodes assume leadership upon completing a suitable quorum with an ATV of their own (line \[l:leadershipa\]), or votes received from others, either directly (line \[l:leadershipb\]) or as part of a block proposal (line \[l:leadershipc\]). In the last case, if more than $\qsize$ votes exist, it can happen that a node replaces the leader. It proposes a block of its own by reusing votes contained in the received proposal. This is possible because votes in reference the previous block and not the current proposal. The possibility of reusing votes reduces wasted work compared to orphans in , a problem that has been studied separately [@sompolinsky2015SecureHighRate]. It also provides robustness against leader failure (see Sect. \[sssec:leader-failure\]).

Line \[l:onatv\] handles ATVs. If the node cannot lead a quorum, it broadcasts the vote. The last missing part is how ATVs can be scheduled, which we discuss next.

me, secret $\gets$ head $\gets$ genesis blocks\[genesis\].state $\gets$ [$S_0$]{} blocks\[genesis\].height $\gets$ 0

\[l:onatv\] \[l:leadershipa\] \[l:sendvote\]

\[l:leadershipb\]

\[l:leadershipc\]

### Work {#sssec:proto_work}

Agents can participate in the quorum finding process by computing ATVs on their nodes. For completeness, Listing \[lst:work\] shows the trial-and-error algorithm which schedules solutions suitable for votes ($\leq\vthres$). Alternatively, agents can search ATVs with the help of other machines, possibly in parallel and using specialized hardware. Figure \[fig:appstack\] reflects this by splitting the lower layer in network and work.

draw random number $n$

Figure \[fig:timeline\] in the appendix visualizes an execution of by correct nodes and compares it to .

Incentives {#ssec:incentives}
----------

It is possible to motivate participation in by rewarding puzzle solutions. This requires some kind of virtual asset that (at least partly) fulfills the functions of money [@hicks1967CriticalEssays p. 1] and can be transferred to a vote’s public key. Claiming the reward for $({\ensuremath{r}},
{\ensuremath{p}}, {\ensuremath{s}})$ depends on the corresponding secret key. could adopt Bobtails’s constant reward per vote [@bissias2020BobtailImproved]. Rewarding votes instead of blocks would ensure inclusiveness without compromising security (see Sect. \[sec:intuition\]). Votes occur $\qsize$ times more frequently than blocks. ’s mining income would thus be less volatile than in . This reduces the pressure to form mining pools. However, it is not trivial to establish if constant rewards are incentive compatible because the utility of the reward *outside* the system may affect the willingness to participate *in* the system and thereby make $\lambda$ endogenous [@dimitri2017BitcoinMining; @prat2018EquilibriumModel]. This implies that rewards must be treated jointly with the assumptions preventing the failure modes \[pow-network\] and \[pow-adversary\]. We are unaware of protocol analyses that solve this problem convincingly.

On a more general note, designing protocols like economic mechanisms by incentivizing desired behavior sounds attractive because there is some hope that the assumption of honest nodes can be replaced by a somewhat weaker assumption of rational agents [@garay2013RationalProtocol; @groce2012ByzantineAgreement]. In this spirit, @badertscher2018WhyDoes present positive results for Bitcoin in a discrete round execution model and under assumption of a constant exchange rate. However, many roadblocks remain. Agents’ actions are not fully observable ( information withholding) and preference orders are not fully knowable, hence rationality is not precisely defined. Side-payments (bribes), which cannot be ruled out, pose an insurmountable challenge for mechanism design [@bonneau2016WhyBuy; @judmayer2017MergedMining; @budish2018EconomicLimits]. For distributed logs, which work inherently sequential, this approach may even be thwarted by negative results on the existence of unique equilibria in repeated games [@friedman1971NoncooperativeEquilibrium]. For these reasons, we skip the mechanism design aspects and limit our contribution to transferring Byzantine consensus to proof-of-work scenarios. In other words, supports incentives for inclusiveness, but its security intentionally does not rely on incentives.

Evaluation {#sec:evaluation}
==========

We implement in OCaml and evaluate it in a network of  nodes using a discrete event simulation. We average over  independent executions of the first  blocks. All results are reproducible with the code provided online.

The simulation maintains state for all simulated nodes separately. Events are stored in a priority queue, with keys representing points in time. Events are scheduled by inserting them into the queue. There are three types of simulation events: , and . The simulation’s main loop takes the first event from the queue and handles it by interacting with the nodes in the following way (also see Fig. \[fig:simulator\]).

#### Proof-of-Work

When taking an event from the queue, the simulation randomly and independently assigns an ATV to a node. The simulation executes the assignment by invoking the event handler on the receiving node. Then, it schedules the next ATV with a random, exponentially distributed time delta. This simulates a proof-of-work process according to Def. \[def:process\]. The simulation does not perform actual work by setting the vote threshold to the maximum; meaning puzzles are trivial to solve.

#### Broadcast

Nodes invoke the broadcast logic by scheduling local events. The simulation translates them to global events. For each broadcast event, the simulation schedules events for each node except the sender. During this step, the simulation injects latency and simulates churn and leader failure. Delivery events are handled by invoking the handler on the receiving node.

Robustness {#ssec:robustness}
----------

We evaluate the robustness in terms of latency, churn, and leader failure. In all simulation runs we check for inconsistent committed state, which did not occur.

### Latency {#sssec:latency}

We model the effect of latency by injecting a random time delay between broadcast send and message delivery. We draw delays from an exponential distribution with fixed expectation, independently for each node and delivery. Latency causes temporal state inconsistencies. In these periods, nodes spend their ATVs on extending superseded blocks, or even produce temporal forks. We observe that largely independent of the quorum size $\qsize$, expected latencies below 1% of the expected block time (Bitcoin: 6 seconds) have marginal impact, while latencies in the order of 10% of the expected block time (Bitcoin: 60 seconds) delay the commit by about 20%. Figure \[fig:latency\] visualizes these results.

Empirical measurements [@decker2013InformationPropagation; @croman2016ScalingDecentralized; @gervais2016SecurityPerformance] suggest that the propagation time of Bitcoin blocks ($\approx 500$ KB) is about 9 seconds on the Internet. If we take this as an upper bound, we can argue that tolerates practical latencies. Moreover, most of ’s messages are votes. They are multiple orders of magnitude smaller ($72$ B; see Sect. \[ssec:overhead\]), fit into a single packet, and are much easier to verify than Bitcoin blocks. Results of a simulation with different latencies for blocks ($10$s) and votes ($100$ms) suggest that can run at Internet scale with lower expected block time than 10 minutes.

### Churn

We simulate churn by muting a fraction (churn ratio) of random nodes for 10 times the expected block time. Muted nodes can receive ATVs but do not send or receive messages. Accordingly, the ATVs assigned to muted nodes represent lost work. We expect that the time to commit is inversely proportional to the churn ratio: if 50% of the nodes are muted, the time to commit is twice as long, independent of the quorum size. Figure \[fig:churn\] supports this claim.

### Leader Failure {#sssec:leader-failure}

Leaders may fail to propose blocks. We model such failures by dropping block proposals randomly with constant probability (leader failure rate).

In , lost proposals imply a full block worth of wasted work. can reuse votes for different proposals. Honest nodes reveal at most one new vote with their proposal. Accordingly, a lost proposal wastes at most the work of one vote. Therefore, with increasing quorum size the robustness to leader failure should improve. The results in Figure \[fig:failure\_real\] (with realistic 10s/100ms latency) and Figure \[fig:failure\] (without latency to isolate effects) support this claim. For perspective, the right end of the graph simulates a situation where an attacker can monitor all nodes’ network traffic and disconnect nodes at discretion with 50% success probability. Still, for large quorum sizes the time to commit is not longer than under the extreme latencies discussed in Section \[sssec:latency\].

The robustness against churn and leader failure emerges from ’s novel approach to form short-lived committees from ephemeral identities. This maintains liveness even under the threat of powerful network-level attacks. We move on to the discussion of attacks on the protocol layer.

Security {#ssec:security}
--------

The security evaluation draws on the framework by @zhang2019LayCommon. It distinguishes the security aspects proof-of-work blockchains should fulfill: chain quality, incentive compatibility, subversion gain, and censorship susceptibility.

The authors suggest Markov Decision Processes (MDP) as method and apply it to several variants of . However, state explosion prevented them from modeling Bobtail,[^2] because it ranks proof-of-work solutions by magnitude. Since adopts this ranking for the leader election (Sect. \[sssec:proto\_leader\]), it does not seem readily amenable to MDPs, either. We thus resort to informal reasoning and simulation. Following the convention in the literature, we assume two agents. Let $\lambda$ be the total compute power. The attacker has $\alpha\cdot\lambda$ compute power, the honest agent controls the rest. The honest agent operates correct nodes, while the attacker operates a single node that may deviate from the protocol specification.

### Subversion Gain

The canonical example for subversion gain in cryptocurrencies is double spending: the attacker wants at least one of the honest nodes (the merchant) to act on inconsistent state. supports commits, hence we neither need to consider the possibility of history rewriting nor the double spending of *un*committed transactions.[^3] suffers from these problems [@karame2012DoublespendingFast; @heilman2015EclipseAttacks; @gervais2016SecurityPerformance; @budish2018EconomicLimits; @apostolaki2017HijackingBitcoin]. The only remaining strategy is splitting the network so that the recipients of at least two different double-spend transactions commit to different states. This loss of consistency would materialize in permanent forks that require out-of-band resolutions (triggered by an else-branch after code line \[l:detectfork\]).

In order to understand how ensures consistency, it is instructive to recall the block preference rule in Sect. \[sssec:proto\_preference\]. Assume counterfactually that nodes never update their value according to received votes. Then, an attacker who becomes the leader could send different proposals to each node. This would fragment the honest nodes’ compute power and give the attacker time to form six quorums, three per conflicting state. The probability of the attacker becoming leader is at least $\alpha$ in each round. This would be a catastrophic attack.

The actual block preference rule selects the value with the highest progress among all known proposals. Therefore, as soon as the first vote is received from an honest node, all honest nodes converge to a single value. As a result, the attacker would have to form six complete quorums in the time the honest nodes get assigned a single ATV and broadcast the corresponding vote. Since $\frac{6 \qsize}{\alpha} \gg \frac1{1-\alpha}$, such an attack becomes infeasible for large quorum sizes and $\alpha<1/2$.

### Censoring {#sssec:censoring}

In the censoring scenario, the attacker wants to control the values on which consensus is achieved for some time. This means he has to be elected as leader in multiple ($m$) consecutive blocks.

We start with the probability of an attacker becoming the leader in a single round. Without deviating from the protocol, he leads with probability $\alpha$. This means he could successfully censor for $m$ consecutive blocks with probability $\alpha^m$.

However, naively following the protocol is not the best censoring strategy. Taking inspiration from the work on selfish mining [@eyal2014MajorityNot; @sapirshtein2016OptimalSelfish; @kiayias2016BlockchainMining], we argue that an attacker can do better by withholding information. A selfish miner in withholds complete blocks, such that other miners work on an irrelevant part of the chain. has a more granular type of information: an attacker might withhold his votes. A censoring attacker would release his votes only when the release implies leadership. In practice, this means that a censoring attacker does not share votes, he only proposes blocks. Using this strategy, the attacker can delay the next quorum until the honest nodes can form one without the attacker’s votes. This time window increases the attacker’s odds of becoming the leader.

We implement this *censor* strategy and instantiate it in a special attacker node of the simulation environment (see Fig. \[fig:simulator\]). We bias the assignment of ATVs towards this node such that it posesses computational power $\alpha$. We routinely check for forks, but do not find any. We count how many of the committed blocks are proposed by the attacker in order to estimate the probability of leadership per round. Figure \[fig:leadership\] shows this estimate as a function of the quorum size for different attacker strengths $\alpha$. Using the described withholding strategy, an $\alpha=1/3$ attacker contributes roughly 42% ($\alpha=1/2$: 64%) of the blocks. For comparison, the upper bound for block withholding strategies for the same attacker on is 50% ($\alpha=1/2$: 100%) [@sapirshtein2016OptimalSelfish].

We additionally validate the results on the censor strategy using an independent Monte Carlo (MC) simulation. (See Appendix \[apx:mcmc\] for details.) As depicted in Figure \[fig:leadership\], the MC analysis confirms the network simulation.

### Chain Quality and Incentive Compatibility

The prevalent strategy for increasing the own share of blocks and rewards is selfish mining [@eyal2014MajorityNot; @sapirshtein2016OptimalSelfish; @negy2020SelfishMining]. This attack is inherently connected with incentives. Its basic idea is to withhold and strategically release blocks in order to create an information asymmetry that allows to reap a disproportional amount of rewards for the invested share of work. This idea is not directly transferrable from to for three reasons. First, the finality after three blocks substantially limits the horizon of the selfish miner. Second, block proposals are less valuable. They are not significant sources of reward. Third, block proposals are less critical. In fact, block withholding reduces to the situation of leader failure. Since votes can be reused, honest nodes can replace missing proposals very fast (see Section \[sssec:leader-failure\]). This makes proposals less rare events than in , limiting the strategic advantage of withholding them.

However, as we have argued in Section \[sssec:censoring\], it is a valid strategy to *withhold votes*. Therefore, we analyze the effect of vote withholding on the distribution of rewards, assuming a constant reward per committed vote, like in Bobtail [@bissias2020BobtailImproved]. The naive strategy yields a share of $\alpha$ of the votes. The attacker’s goal is to maximize the number of votes he contributes to each quorum. Since only the leader can decide which votes are included in a proposed quorum, the first step of optimal vote withholding is to increase the odds of becoming the leader. This, in turn, can be achieved by withholding votes! The circularity indicates that the attack can be approximated with the censoring strategy discussed in Section \[sssec:censoring\]. Figure \[fig:votes\] shows simulation results on how the strategy, $\alpha$, and the quorum size affect the share of attacker votes committed to the chain. Interestingly, the censor receives fewer rewards than honest nodes and naive attackers, indicating a dilemma between paying for becoming the leader and capitalizing the power of leadership. The tradeoff is visible by comparing Figures \[fig:leadership\] and \[fig:votes\]. A similar tradeoff appears for the so-called “proof withholding” strategy in Bobtail [@bissias2020BobtailImproved], which resembles the censoring strategy in .

Again, we compare the protocol implementation in the network simulation with the idealized MC model described in Appendix \[apx:mcmc\].

Overhead {#ssec:overhead}
--------

requires one message broadcast per block, namely the block itself, independent of the number of participating nodes. adds $\qsize$ message broadcasts per block—one for each vote. Votes are much smaller than blocks. Under the conservative assumptions of 256 bits for block reference and public key, and 64 bits for the puzzle solution, a vote is 72B.[^4] The number of messages is constant in the number of nodes, like in Bitcoin. However, block headers grow. must store the complete quorum with $\qsize$ puzzle solutions. This overhead matters because the header is replicated in all nodes that want to verify the blockchain in the future.

Assuming the same vote size and the most robust case analyzed ($\qsize=256$), the storage overhead is about 10kB per block. This is less than 1% of Bitcoin’s average block size in 2019. With this choice of $\qsize$, falsely accepting a quorum as unique is much less likely than guessing a 128-bit key in one attempt. Table \[tab:overhead\] (in the appendix) shows the storage overhead per block and the associated probability of ambiguity at expected optimistic quorum time (Corollary \[cor:poa\_at\_ev\]) for different choices of $\qsize$. We argue that the benefits of the protocol outweigh its storage costs and leave the exploration of compression techniques to future work.

Discussion {#sec:discussion}
==========

Relation to Other Distributed Logs {#ssec:related}
----------------------------------

[max width=]{}

[lcccccccc]{} & & & & & & & &\
$\#$ nodes & 10 & $10^2$ & $10^3$ & $10^3$ & $10^3$ & $10^3$ & $10^3$ & $10^3$\
committee & & & & [()]{}& [()]{}& & &\
permissioned\
- network & &\
- committee & & &\
\
- BTP & & & & & & &\
- BTI & & & & & & & &\
sidechain & & & & & & & &\
finality & & & & & & & &\
\

New distributed log protocols are proposed almost every month. We do not claim to know all of them and we do not attempt to provide a complete map of the design space, since other researchers have specialized on this task [@bano2019SoKConsensus; @cachin2017BlockchainConsensus]. Instead, we compare to some of its closest relatives along selected dimensions (see Table \[tab:design-space\]).

### Number of Nodes {#sssec:table_size}

Early BFT protocols were designed for a small number of nodes. PBFT [@castro2002PracticalByzantine], for example, is proven secure under the Byzantine assumptions \[bft-network\] and \[bft-adversary\]. It requires multiple rounds of voting to reach consensus on a single value. The communication complexity of $O(n^2)$ renders it impractical for more than a dozen nodes $n$.

HotStuff [@yin2019HotStuffBFT] ensures safety under the same assumptions, but increases the rate of confirmed values to one per round of voting. Its key idea is to pipeline the commit phases of iterative consensus (recall Fig. \[fig:pipeline\]). Moreover, it reduces communication complexity to $O(n)$ by routing all communication through a leader. These two changes make HotStuff practical for larger networks. However, all correct nodes actively participate (send messages) for each block.

### Committee {#sssec:table_committee}

Protocols designed for even larger scale reduce communication complexity further by electing committees. Only committee members participate actively. All other nodes wait until they become part of a committee.

In , write-access to the ledger is controlled by a proof-of-work puzzle. In each round, one node – the finder of the block – broadcasts a message. Consequently, successful miners can be interpreted as single-node committees. In Bobtail [@bissias2020BobtailImproved] and , multiple proof-of-work puzzles are solved per block. Consequently the committee size is greater than one. The committee approach is also followed by proof-of-stake protocols. Here, committee membership is tied to the possession of transferable digital assets (stake).

### Permissioned {#sssec:table_permissioned}

As stated earlier (Sect. \[sec:pow\_quorum\]), assumption \[bft-network\] can only be satisfied by restricting access to the network based on identities assigned by an external identity provider or gatekeeper. Consequently, protocols relying on this assumption are permissioned on the network layer. Proof-of-stake internalizes the gatekeeping functionality by restricting access to the committee based on the distribution of stake. While participating as a node is possible without permission, access to the committee is still permissioned.

In proof-of-work systems any agent can join and leave the network and has a (fair) chance of becoming committee member without obtaining permission from a gatekeeper.[^5]

### Resource Binding {#sssec:table_binding}

Proof-of-work can be seen as a commitment of resources to a value. Typically, these values are chosen locally on each node. Freshness is guaranteed by including a reference to recent puzzle solutions in the value. We distinguish between resources bound to a proposal (BTP) for an upcoming state update and resources bound to an identifier (BTI) used for entering the committee.

Bound to proposal (BTP)\

(0,0) – (5.6,0); (5.6,0) – (8.4,0); (8.4,0) – (11,0) node \[below left\] [time]{}; [ (7, -3pt) node \[below, align=center\] [resource binding]{}; ]{} [ (10, 3pt) node \[above, align=center\] [publish]{} – (10, -3pt); ]{} [ (5.5, 3pt) node \[above, align=center\] [define\
proposal]{} – (5.5, -3pt); ]{} [ (8.5, 3pt) node \[above, align=center\] [find\
solution]{} – (8.5, -3pt); ]{}

Bound to identifier (BTI)\

(0,0) – (1.1,0); (1.1,0) – (3.9,0); (3.9,0) – (11,0) node \[below left\] [time]{}; [ (2.5, -3pt) node \[below, align=center\] [resource binding]{}; ]{} [ (10, 3pt) node \[above, align=center\] [publish]{} – (10, -3pt); ]{} [ (1, 3pt) node \[above, align=center\] [define\
identifier]{} – (1, -3pt); ]{} [ (4, 3pt) node \[above, align=center\] [find\
solution]{} – (4, -3pt); ]{} [ (5.5, 3pt) node \[above, align=center\] [define\
proposal]{} – (5.5, -3pt); ]{}

(0,0) – (1.5,0) node \[right\] [competition]{};

uses BTP. Nodes form a proposal for the next block locally and then start to solve a proof-of-work for this proposal. If they are successful in finding a puzzle solution, they share their proposal. This process is depicted in the upper half of Figure \[fig:btp\_vs\_bti\].

Bitcoin-NG [@eyal2016BitcoinNGScalable] innovated by translating the concept of leader election from the BFT literature ( [@dwork1988ConsensusPresence; @garciamolina1982ElectionsDistributed; @ongaro2014SearchUnderstandable]) to . The miner of a block (elected leader) becomes responsible for appending multiple consecutive (micro) blocks until the next leader emerges with the next mined block. In our framework, Bitcoin-NG adds throughput by switching from BTP to BTI in . A more elaborate BTI protocol is Byzcoin [@kogias2016EnhancingBitcoin]. It forms a committee over the last $\qsize$ successful miners. This rolling committee is then responsible for appending micro blocks. Byzcoin uses PBFT to reach final consensus within each committee, thereby shifting control over the micro blocks from a single node (Bitcoin-NG) to multiple nodes.

is a BTI protocol: nodes bind resources to identifiers by mining votes. If they happen to lead when the quorum is complete, they sign a block proposal with their secret key. The lower half of Figure \[fig:btp\_vs\_bti\] shows this order of events. Bobtail extends by binding a preliminary transaction list into the proof-of-work solution of each vote.[^6] This BTP aspect of Bobtail adds significant complexity to the voting logic in order to prevent the reuse of votes for different competing proposals. As described in Section \[sec:evaluation\], makes the reuse of votes a key feature.

### Sidechain {#sssec:table_sidechain}

The sequences of micro blocks in Bitcoin-NG, Byzcoin, and also Thunderella [@pass2018ThunderellaBlockchains] are often referred to as sidechains. Sidechains can serve several purposes, such as increasing throughput (Bitcoin-NG) or adding finality (Byzcoin). However, since different mechanisms are used to advance different chains, synchronization is a major problem. Bitcoin-NG tackles it with incentives, Thunderella focuses on an optimistic case, and Byzcoin leaves open which chain has priority. Sidechains often involve high protocol complexity because different consensus mechanisms are stacked onto each other: the protocols require a distributed log in order to provide a distributed log (with different properties). By contrast, provides an improved distributed log directly from a broadcast network and proof-of-work.

### Finality {#sssec:table_finality}

The lack of finality in exposes it to many attacks [@bonneau2016WhyBuy; @gervais2016SecurityPerformance; @budish2018EconomicLimits; @auer2019DoomsdayEconomics]. So far, according to conventional wisdom, eventual consistency has been accepted as the price of a truly permissionless system. Byzcoin challenged this view with a stacked solution involving sidechains. achieves the same at lower protocol complexity using proof-of-work quorums. Their stochastic uniqueness allows us to transfer the commit process from the permissioned world to the permissionless.

Other Related Protocols
-----------------------

Not included in Table \[tab:design-space\] are protocol proposals that replace the linear data structure of the distributed log with more general directed acyclic graphs (DAGs) [@sompolinsky2015SecureHighRate; @sompolinsky2016SPECTREFast]. This promises higher scalability and faster first confirmation in latent networks at the cost of additional complexity on the application layer, which cannot rely on the total order and uniqueness of state updates anymore. Also Fruitchain [@pass2017FruitChainsFair] can be interpreted as a DAG: it recognizes solutions to hard and easy puzzles but hides the DAG’s complexity from the application layer by not allowing ‘fruits’ to carry state updates.

An even more radical approach is to drop the distributed log completely and implement a digital asset directly on a secure (source-ordered) broadcast without consensus [@guerraoui2019ConsensusNumber]. However, this approach restricts the versatility of the application layer. For example, arbitrary smart contract logic is not supported.

Limitations and Future Work {#ssec:limits}
---------------------------

We have presented a protocol that achieves finality in a permissionless setting under axiomatic exclusion of the failure modes \[pow-network\] and \[pow-adversary\], and the acceptance of a negligible failure probability. The assumption on \[pow-network\] and \[pow-adversary\] are also made for security proofs of  [@garay2015BitcoinBackbone; @pass2017AnalysisBlockchain]. Nevertheless, it is worth discussing their suitability.

Excluding \[pow-network\] corresponds to assuming a fixed, network-wide compute power $\lambda$. But agents can add and remove nodes at their willing. Even if the number of nodes is fixed, the computational power of each node is not. We observe in practice that a control loop, known as difficulty adjustment (DA), can compensate changes of $\lambda$ up to a certain degree. But ample literature shows that the deployed DA algorithms are not optimal [@kraft2016DifficultyControl; @meshkov2017ShortPaper; @fullmer2018AnalysisDifficulty; @hovland2017NonlinearFeedback], especially in case of sudden changes of $\lambda$. We argue that proof-of-work quorums can support more precise difficulty adjustment algorithms. A higher quorum size implies more votes and hence more data points to inform the algorithm about changes of $\lambda$.

The same effect can be exploited for detecting network-level attacks, such as eclipse and splits, more accurately. (Appendix \[apx:detect\] provides additional details.) This is relevant in the context of the CAP theorem [@gilbert2002BrewerConjecture], which tells us that every distributed system has to sacrifice one out of consistency, availability and partition tolerance. , as presented, favors availability over consistency. It does not implement a mechanism for detecting network splits, even though it is possible at high confidence for big quorum sizes. The trade-off could be changed in favor of consistency. If a split is detected, the protocol withholds commits (and may notify the application layer in order to trigger out-of-band resolutions).

The second failure mode, \[pow-adversary\], can be catastrophic and is hard to rule out. We are not aware of any argument that bounds $\alpha$ to a constant below 50% for any proof-of-work system. In fact, &gt;50% attacks have been mounted against smaller instances of in practice [@cryptoslate2019percent51attacks].

Our network simulation in Section \[sec:evaluation\] models exponentially distributed message propagation times. This distribution puts the system under pressure, but it is not very realistic. Future work might put the simulation on a more structured network topology. However, since the literature reports a significant discrepancy between observed topologies and what cryptocurrencies are designed for [@delgadosegura2019TxProbeDiscovering; @mariem2020Allthat], it is not obvious what an appropriate topology would look like.

Similarly, we leave unexplored how to disseminate ’s smaller vote messages efficiently. Votes easily fit into single Internet packets and their verification requires only one hash evaluation. It might be possible to improve vote propagation times using UDP-based structured broadcast [@rohrer2019KadcastStructured] instead of the gossip broadcast used in many cryptocurrencies.

Finally, we refrain from designing an incentive mechanism for for the reasons stated in Section \[ssec:incentives\]. A principled approach would be to explore reward-optimizing strategies (combined withholding of votes and blocks) automatically using Markov Decision Processes [@sapirshtein2016OptimalSelfish; @zhang2019LayCommon] or even more sophisticated Reinforcement Learning techniques [@hou2019SquirRLAutomating].

Conclusion {#sec:conclusion}
==========

We understand as a positive example to support our claim that it is possible to build permissionless distributed logs *with* finality *directly* from proof-of-work. The claim is tentatively supported (with analysis and simulations) until is broken. We invite the community to prove our claim wrong, and provide running code online to facilitate this task. It is not safe to use this code in systems dealing with real values.

Regardless of whether our claim is true or false, the identified conflict between inclusiveness and security is instructive, and the associated theory of quorums on stochastic processes may find applications elsewhere. Since it comprises as a special case, it also contributes to a better understanding of the role of proof-of-work in known systems that “work in practice, but \[so far\] not in theory” [@bonneau2015SoKResearch].

If our claim holds, we have found a way to build permissionless distributed logs from proof-of-work that can serve many applications better than existing systems. However, proof-of-work is a very wasteful way of establishing consensus. It should be avoided whenever possible. Only if there is no alternative to proof-of-work, should be considered as a replacement for .

Proofs, Figures, and Visualizations
===================================

![image](figures/timeline.pdf){width="\linewidth"}

![image](figures/timeline.pdf){width="\linewidth"}

![image](figures/timeline.pdf)

\[apx:proofs\]

#### Lemma \[lem:poa\_poisson\]

The POA for the Poisson process $P_\lambda$ is given by $${\ensuremath{\operatorname{poa}}}_{P_\lambda, \qsize}(t) =
  1 - e^{-\lambda t} \sum_{i=0}^{2\qsize -1}{\frac{(\lambda t)^i}{i!}} \,.$$

$P_\lambda$ has the following properties [@stewart2009ProbabilityMarkov p. 389]:

1.  $\prob{P_\lambda(0) = 0 } = 1$,

2.  $P_\lambda(t) - P_\lambda(s) \drawn \distPoisson(\lambda
          \cdot(t-s))$ for all $s < t$, and

3.  for $n \in \nats$ and $0 < t_1 < \dots < t_n$, the family of random variables $$\{P_\lambda(t_i) - P_\lambda(t_{i-1})\mid 2 \leq i \leq
          n\}$$ is stochastically independent.

According to Definition \[def:poa\], $$\begin{aligned}
    {\ensuremath{\operatorname{poa}}}_{P_\lambda, \qsize}(t)
    = & \prob{P_\lambda(t) \geq 2 \qsize} \\
    = & 1 - \prob{P_\lambda(t) \leq 2 \qsize - 1} \,.
  \end{aligned}$$

By setting $s=0$ in property 2 of the Poisson process and using property 1, we conclude that $P_\lambda(t) \drawn \distPoisson(\lambda t)$. By evaluating the cumulative distribution function of the Poisson distribution $$\begin{aligned}
    F_{\distPoisson}(n; \lambda') =
    e^{-\lambda'} \sum_{i=0}^{\lfloor n \rfloor}{\frac{\lambda'^i}{i!}}
  \end{aligned}$$ for $n = 2\qsize - 1$ and $\lambda' = \lambda t$, we obtain the stated result.

#### Lemma \[lem:qt\_possion\]

The optimistic $\qsize$-quorum time for the Poisson process is Erlang distributed with shape parameter $\qsize$ and rate parameter $\lambda$, in short $$T_{P_\lambda,\qsize} \drawn \distErlang(\qsize, \lambda) \,.$$

The time between two consecutive count events of $P_\lambda$ is exponentially distributed with rate parameter $\lambda$. The times between any two consecutive count events are stochastically independent. The sum of $\qsize$ independent and identically distributed exponential random variables is Erlang distributed [@stewart2009ProbabilityMarkov p. 146] with shape parameter $\qsize$ and rate parameter $\lambda$.

#### Theorem \[thm:negligible\]

For the Poisson process, the probability of ambiguity at the expected quorum time is negligible in the quorum size $\qsize$.

Let $$\begin{aligned}
    f(k) :=
    {\ensuremath{\operatorname{poa}}}_{P_\lambda, \qsize}({\ensuremath{\bar{t}_{\lambda, \qsize}}}) =
    1 - e^{-\qsize} \sum_{i=0}^{2\qsize -1}{\frac{\qsize^i}{i!}} \,.
  \end{aligned}$$ Our first observation is that $f(k)$ can be expressed in terms of the regularized incomplete Gamma function $P(\alpha, k)$. According to , $$\begin{aligned}
    f(k) = P(2k,k) \,.
  \end{aligned}$$ Following the definition of the regularized incomplete Gamma function (see ), we obtain $$\begin{aligned}
    f(k) = \frac{\gamma(2k,k)}{(2k-1)!} \,, \label{eq:gamma_frac}
  \end{aligned}$$ with the incomplete Gamma function (see ) $$\begin{aligned}
    \gamma(\alpha,k) = \int_{0}^{k}{t^{\alpha -1}e^{-t} dt}\,.
  \end{aligned}$$ We will prove the theorem by providing an (asymptotic) upper bound for $f(k)$ that decreases exponentially in $k$. Stirling’s Approximation [@robbins1955RemarkStirling] provides a useful lower bound for the factorial in the denominator of Equation \[eq:gamma\_frac\]: $$\begin{aligned}
    n! \geq \sqrt{2\pi}\,n^{n+\frac{1}{2}}\,e^{-n} \label{eq:stirling_lower}
  \end{aligned}$$ We proceed with an upper bound for the enumerator as follows. Let $g(t) =
  t^{2k-1}e^{-t}$ be the function to integrate for $\alpha = 2k$. Like for integrals in general, $$\begin{aligned}
    \gamma(2k,k) = \int_{0}^{k}{g(t)\,dt} \leq k \cdot \max_{t \in [0,k]}{g(t)} \,.
  \end{aligned}$$ The derivative of $g$ is $g'(t)=e^{-t}(2k-t-1) t^{2k-2}$. For $t \in [0,k]$ the derivative $g'$ is greater than zero. Hence the function $g$ is monotonically increasing, the maximum is reached at the end of the interval, and $$\begin{aligned}
    \gamma(2k,k) \leq k^{2k}e^{-k} \,. \label{eq:enum}
  \end{aligned}$$ Applying Approximations \[eq:stirling\_lower\] and \[eq:enum\] to Equation \[eq:gamma\_frac\], yields $$\begin{aligned}
    f(k) &\leq \frac{k^{2k}e^{-k}}{\sqrt{2\pi}\,(2k-1)^{2k-\frac{1}{2}}\,e^{-2k+1}} \\
         &= {\left(\frac{k\sqrt{e}}{2k-1}\right)}^{2k} \sqrt{\frac{2k-1}{2\pi e^2}}
  \end{aligned}$$ Observe that $$\begin{aligned}
    \limsup_{k\to\infty} \frac{\left(\frac{k\sqrt{e}}{2k-1}\right)^{2k}}{\left(\frac{\sqrt{e}}{2}\right)^{2k}}
    = \limsup_{k\to\infty} \left(\frac{2k}{2k-1}\right)^{2k} = e < \infty\,.
  \end{aligned}$$ Thus, $$\begin{aligned}
    f(k) = O\left(\frac{e^k}{4^k}\sqrt{k}\right).
  \end{aligned}$$ Since $\sqrt{k} < 1.25^k$ for $k>1$, we can conclude $$\begin{aligned}
    f(k) &= O\left(\frac{e^k}{4^k} 1.25^k\right) \\
         &= O\left(0.85^k\right)\,.
  \end{aligned}$$

  ------------- -------------------------- --------------
   quorum size   probability of ambiguity   block header
                 at expected quorum time      (bytes)
        1                $0.2642$                72
        2                $0.1429$               112
       16                $0.0003$               672
       64          $1.2\times 10^{-12}$         2.6k
       256          $4\times 10^{-45}$          10k
  ------------- -------------------------- --------------

  : Storage overhead of consensus.[]{data-label="tab:overhead"}

Monte Carlo Simulation {#apx:mcmc}
======================

=\[\] =\[-&gt;, draw, rounded corners=1em\] =\[anchor=south, font=, xshift=-0.5em\] =\[anchor=north, font=, xshift=-0.5em\] (top) at (0,1) [$a,d,\top$]{}; (ta) at (1,0) [$a+1,d,\top$]{}; (tb) at (1,1) [$a,d+1,\bot$]{}; (tc) at (1,2) [$a,d+1,\top$]{}; (top) |- (ta); (top) – (tb); (top) |- (tc); at (0.5, 0) [$\alpha$]{}; at (0.5, 1) [$(1 - \alpha)/(a + d + 1)$]{}; at (0.5, 2) [$(1 - \alpha)\cdot(a+d)/(a + d + 1)$]{}; at (0.5, 0) [attacker extends lead]{}; at (0.5, 1) [defender obtains lead]{}; at (0.5, 2) [following defender catches up]{};

=\[\] =\[-&gt;, draw, rounded corners=1em\] =\[anchor=south, font=, xshift=-0.5em\] =\[anchor=north, font=, xshift=-0.5em\] (top) at (0,1) [$a,d,\bot$]{}; (ta) at (1,0) [$a,d+1,\bot$]{}; (tb) at (1,1) [$a+1,d,\top$]{}; (tc) at (1,2) [$a+1,d,\bot$]{}; (top) |- (ta); (top) – (tb); (top) |- (tc); at (0.5, 0) [$1 - \alpha$]{}; at (0.5, 1) [$\alpha/(a + d + 1)$]{}; at (0.5, 2) [$\alpha\cdot(a+d)/(a + d + 1)$]{}; at (0.5, 0) [defender extends lead]{}; at (0.5, 1) [attacker obtains lead]{}; at (0.5, 2) [following attacker catches up]{};

We cross-check the implementation of the censor strategy and its behavior in the network simulation (see Sect. \[sssec:censoring\]) using an independent Monte Carlo simulation. We model the formation of individual quorums using an (Absorbing) Markov Chain, but omit higher-level concepts such as blocks and their chaining. The censor strategy is to generally withhold votes until either the attacker can form a quorum as leader, or the defender forms a quorum without any of the attacker’s (withheld) votes. In a protocol execution, the first case ([<span style="font-variant:small-caps;">success</span>]{}) applies when the attacker proposes a block which the honest nodes accept. The second case ([<span style="font-variant:small-caps;">fail</span>]{}) applies when the honest nodes propose a block.

#### State representation and initialization

We model the current state as a triple $(a, d, l)$, where $a \in \nats$ denotes the number of (withheld) attacker votes, $d \in \nats$ (for defender) denotes the number of votes of the honest nodes, and $l \in \bools$ is true if the attacker holds the currently smallest vote. The initial state is $(1, 0, \top)$ with probability $\alpha$ and $(0, 1, \bot)$ otherwise.

#### State transition

Figure \[fig:mcmc\] shows an annotated state transition diagram. If $l = \top$, the next state is $$\begin{aligned}
  &(a + 1, d, l) &&  {\text{ with probability }}\alpha ,\\
  &(a, d + 1, \bot) && {\text{ with probability }}\frac{1 - \alpha}{a + d + 1} \text{, and}\\
  &(a, d + 1, l) && \text{ otherwise.}\end{aligned}$$ If $l = \bot$, the next state is $$\begin{aligned}
  &(a, d + 1, l) && {\text{ with probability }}1 - \alpha ,\\
  &(a + 1, d, \top) && {\text{ with probability }}\frac{\alpha}{a + d + 1} \text{, and}\\
  &(a + 1, d, l) && \text{ otherwise.}\end{aligned}$$

#### Termination

If $l \wedge a + d \geq \qsize$, the simulation terminates in [<span style="font-variant:small-caps;">success</span>]{}. If $\neg l \wedge d \geq \qsize$, it terminates in [<span style="font-variant:small-caps;">fail</span>]{}. The simulation continues until one of these conditions is true.

#### Simulation

We run the model 1000000 times for each combinations of $\alpha \in \left\{\frac{1}{50}, \frac{1}{10}, \frac{1}{5}, \frac{1}{3},
\frac{1}{2}\right\}$ and $\qsize \in \left\{1,2,4,\dots,256\right\}$. Figure \[fig:leadership\] shows the fraction of cases where the simulation terminates in [<span style="font-variant:small-caps;">success</span>]{}. Figure \[fig:votes\] shows the average number of attacker votes for the runs that end in [<span style="font-variant:small-caps;">success</span>]{}.

Detecting Attacks {#apx:detect}
=================

Each vote is linked to one ATV. By assumption (Sect. \[sec:pow\_quorum\]), the time between two consecutive ATVs is exponentially distributed with rate $\lambda$. In an honest network, a node regularly receives votes (and own ATVs). A node can test the hypothesis of being eclipsed based on the arrival of votes. Table \[tab:detect\] shows after how much time (relative to the block time) of not receiving a single vote a node can rule out a natural course of events with confidence $p = 0.001$.

Observe that larger quorums sizes increase the detectability of eclipse attacks. For quorum sizes greater than 8, eclipse attacks can be detected with confidence within a single expected block time. For plain ($\qsize=1$), an equally powerful test requires an observation window of almost 7 times the expected block time.

[^1]: We choose this time range because the block time stamps were less accurate in the more distant past as the data field was used for other purposes.

[^2]: @zhang2019LayCommon were aware of Bobtail and chose not to model it. This is confirmed in private communication with the authors of Bobtail [@bissias2020BobtailImproved].

[^3]: Sound applications on a system with finality wait until the commit. can be parametrized to acceptable commit times for economic exchanges between humans. (High-frequency trading needs other architectures.)

[^4]: Bitcoin shortens public keys to 160 bits and uses solutions of 32 bits. Its blocks are in the order of 1MB.

[^5]: We ignore the role of the supply chain for puzzle solving equipment.

[^6]: Since Bobtail inspired , a better frame is to see as simplification of Bobtail rather than Bobtail as an extension to .
