DFINITY Technology Overview Series

Consensus System
Rev.1
Timo Hanke, Mahnush Movahedi and Dominic Williams
ABSTRACT Dfinity will be introduced in a series of technology overviews,
The Dfinity blockchain computer provides a secure, performant each highlighting an independent innovation in Dfinity such as
and flexible consensus mechanism. While first defined for a permis- the consensus backbone, smart contract language, virtual machine,
sioned participation model, the consensus mechanism itself can be concurrent contract execution model, daemon contracts, peer-to-
paired with any method of Sybil resistance (e.g. proof-of-work or peer networks and secure broadcast, governance mechanism and
proof-of-stake) to create an open participation model. Dfinity’s scaling techniques. The present document will focus on the con-
greatest strength is unfolded in the most challenging proof-of-stake sensus backbone and cryptographic randomness.
case. Dfinity has an unbiasable, verifiable random function (VRF)
At its core, Dfinity contains a decentralized randomness beacon built-in at the core of its protocol. The VRF not only drives the
which acts as a verifiable random function (VRF) that produces a consensus, it will also be the foundation for scaling techniques such
stream of outputs over time. The novel technique behind the beacon as sharding, validation towers, etc. Moreover, the VRF produced
relies on the existence of a unique-deterministic, non-interactive, by the consensus layer is available to the application layer, i.e., to
DKG-friendly threshold signatures scheme. The only known ex- the smart contracts and virtual machine. In this way, the consensus
amples of such a scheme are pairing-based and derived from BLS backbone is intertwined with many of the other topics.
[3, 10].
The Dfinity blockchain is layered on top of the Dfinity beacon 2 INTRODUCTION
and uses the beacon as its source of randomness for leader selec- Dfinity’s consensus mechanism has four layers as depicted in
tion and leader ranking. A "weight" is attributed to a chain based Fig. 1. The first layer provides registered and Sybil-resistant client
on the ranks of the leaders who propose the blocks in the chain, identities. On the second layer is a decentralized random beacon.
and that weight is used to select between competing chains. The On the third layer is a blockchain that is driven by the random bea-
Dfinity blockchain is further hardened by a notarization process con through a probabilistic mechanism for leader ranking. On the
which dramatically improves the time to finality and eliminates the fourth layer is a decentralized notary that provides timestamping
nothing-at-stake and selfish mining attacks. and publication guarantees, and is ultimately responsible for near-
Dfinity’s consensus algorithm is made to scale through contin- instant finality. Dfinity’s consensus layers and other key aspects
uous quorum selections driven by the random beacon. In practice, of the consensus mechanism can be summarized in the following
Dfinity achieves block times of a few seconds and transaction fi- main categories.
nality after only two confirmations. The system gracefully handles
temporary losses of network synchrony including network splits,
while it is provably secure under synchrony.

Notary Layer
Consensus Protocol Layers

Observe

External Actors
Observers
1 PROLOGUE
Blockchain Layer Transaction
DFINITY is a decentralized network design whose protocols gen- Users
erate a reliable "virtual blockchain computer" running on top of a
peer-to-peer network upon which software can be installed and Random Beacon Layer

can operate in the tamperproof mode of smart contracts. The goal

is for the virtual computer to finalize computations quickly (using
Identity Layer Register
short block times and by requiring only a small number of blocks as
New Clients
"confirmations"), to provide predictable performance (by keeping
the time between confirmations approximately constant), and for
computational and storage capacity to scale up without bounds as
Figure 1: Dfinity’s consensus mechanism layers. 1. Identity layer:
demand for its services increases (using novel validation mecha-
provides a registry of all clients. 2. Random Beacon layer: provides
nisms and sharding systems discussed in our other papers). The the source of randomness (VRF) for all higher layers including ap-
protocols must be secure against an adversary controlling less than plications (smart contracts). 3. Blockchain layer: builds a blockchain
a certain critical proportion of its nodes, must generate crypto- from validated transactions via the Probabilistic Slot Protocol driven
graphic randomness (which is required by advanced decentralized by the random beacon. 4. Notarization layer: provides fast finality
applications) and must maintain a decentralized nature as it grows guarantees to clients and external observers.
in size to millions of nodes.
1
Technology Overviews, Jan. 23, 2018, DFINITY Stiftung Timo Hanke, Mahnush Movahedi and Dominic Williams

1st layer: Identities and Registry. The active participants in the the block candidates that are presented to a client for notarization,
Dfinity network are called clients. All clients in Dfinity are reg- the client only notarizes the highest-ranked one with respect to a
istered, i.e., have permanent, pseudonymous identities. The regis- publicly verifiable ranking algorithm driven by the random beacon.
tration of clients has advantages over the typical proof-of-work It is important to emphasize that notarization is not consensus
blockchains where it is impossible to link different blocks to the because it is possible, due to adverse timing, for more than one
same miner. For example, if registration requires a security deposit, block to get notarized at a given height. This is explicitly tolerated
a misbehaving client would lose its entire deposit, whereas a miner and an important difference to other proof-of-stake proposals that
in a typical proof-of-work blockchain would only forego the block apply full Byzantine agreement at every block. Dfinity achieves
reward during the time of misbehavior. As a result, the penalty for its high speed and short block times exactly because notarization is
misbehavior can be magnitudes larger for registered identities than not full consensus. However, notarization can be seen as optimistic
it can be for unregistered identities. This is particularly important consensus because it will frequently be the case that only one
as blockchains can track unbounded external value that exceeds block gets notarized. Whether this is the case can be detected after
the value of the native token itself. Moreover, Dfinity supports one subsequent block plus a relay time (cf. Theorem 9.3). Hence,
open membership by providing a protocol to register new clients whenever the broadcast network functions normally a transaction
via a stake deposit with a lock-up period. This is the responsibility is final in the Dfinity consensus after two notarized confirmations
of the first layer. plus a network traversal time.
We like to emphasize that a notarization in Dfinity is not pri-
2nd layer: Random Beacon. The random beacon in the second
marily a validity guarantee but rather a timestamp plus a proof
layer is an unbiasable, verifiable random function (VRF) that is
of publication. The notarization step makes it impossible for the
produced jointly by registered clients. Each random output of the
adversary to build and sustain a chain of linked, notarized blocks
VRF is unpredictable by anyone until just before it becomes avail-
in secret. For this reason, Dfinity does not suffer from the selfish
able to everyone. This is a key technology of the Dfinity system
mining attack [4] or the nothing-at-stake problem.
which relies on a threshold signature scheme with the properties of
uniqueness and non-interactivity. The BLS signature scheme is the Threshold Relay and Network Scalability. Dfinity’s consensus
only practical1 scheme that can provide these features, and Dfinity is designed to operate on a network of millions of clients. To en-
has a particularly optimized implementation of BLS built in [2, 11]. able scalability to this extent, the random beacon and notarization
Using a threshold mechanism for randomness creation solves the protocols are designed such that they can be safely and efficiently
fundamental "last actor" problem. Any decentralized protocol for delegated to a committee. A committee is a randomly sampled sub-
creating public randomness without a threshold mechanism suffers set of all registered clients that deploys a threshold mechanism (for
from the problem that the last actor in that protocol knows the next safety) that is moreover non-interactive (for efficiency).
random value and can decide to abort the protocol. In Dfinity, the active committee changes regularly. After having
temporarily executed the protocol on behalf of all clients, the com-
3rd layer: Blockchain and fork resolution. The third layer deploys
mittee relays the execution to another pre-configured committee.
the "probabilistic slot protocol" (PSP). This protocol ranks the clients
We call this technique "Threshold Relay" in Dfinity.
for each height of the chain, in an order that is derived determin-
istically from the unbiased output of the random beacon for that Consistency vs availability. It is worth noting that network splits
height. A weight is then assigned to block proposals based on the are implicitly detectable by Dfinity and are handled conservatively.
proposer’s rank such that blocks from clients at the top of the list This is a consequence of the random sampling of committees. If
receive a higher weight. Forks are resolved by giving favor to the the network splits in two halves of more or less the same size,
"heaviest" chain in terms of accumulated block weight – quite sim- this will automatically cause the random beacon to pause within
ilar to how traditional proof-of-work consensus is based on the a few blocks so that none of the sides can continue. The random
highest accumulated amount of work. The first advantage of the beacon will automatically resume once the network reconnects. If
PSP protocol is that the ranking is available instantaneously, which the network splits in a way that one component is significantly
allows for a predictable, constant block time. The second advantage larger than half of the network, the protocol may continue in that
is that there is always a single highest-ranked client which allows one large component but will pause in all other components.
for a homogenous network bandwidth utilization. Instead, a race Network splits can not only occur when the communication
between clients would favor a usage in bursts. is interrupted. Another important and even more realistic case is
when there are multiple implementations of the Dfinity client and
4th layer: Notarization and near-instant finality. Finality of a given they disagree due to the exposures of a bug. Dfinity handles this
transaction means a system-wide consensus that a given transaction case gracefully. If there are two clients in evenly widespread use
has been irreversibly executed. While most distributed systems and they start to disagree, then both clients will pause. If there are
require rapid transaction finality, existing blockchain techniques are many evenly spread clients and one starts to disagree from all the
unable to provide it. Dfinity deploys the novel technique of block others, then the network will likely continue and only the isolated
notarization in its fourth layer to speed up finality. A notarization client will pause. This is exactly the desired behavior in the given
is a threshold signature under a block created jointly by registered scenarios. Other blockchains do not handle this case well and the
clients. Only notarized blocks can be included in a chain. Of all occurrence of such an event poses a real threat to them. The reason
1 RSA-based alternatives exist but suffer from an impracticality of setting up the thresh- is that these chains put too much emphasis on availability rather
old keys without a trusted dealer. than consistency.
2
DFINITY Consensus Technology Overviews, Jan. 23, 2018, DFINITY Stiftung

Paper organization. § 3 presents a high-level view of the protocol.

§ 4 specifies our system, communication and threat models and Notary
introduces relevant notations. § 5-7 describe the probabilistic slot 3. Notarized 3. Notarized
protocol and random beacon protocol in detail. § 8.1 introduces the Block Block
Threshold Relay technique which allows the protocols to be safely
executed by pre-configured committees rather than by all replicas.
§ 8.2 describes the open participation model which allows members 1. Random 2. Block
to join and leave the protocol over time. Finally, § 9 provides the value proposals
security and correctness proofs for the Dfinity protocol. Random Block
Beacon 1. Random Makers
3 A HIGH-LEVEL VIEW OF THE CONSENSUS value
PROTOCOL
Figure 2: High-level overview on the system components. 1. The ran-
Roles. The Dfinity peer-to-peer network consists of clients con- dom beacon in round r produces random output ξ r . 2. The block
nected by a broadcast network over which they can send messages maker(s) selected deterministically by ξ r propose block(s) for round
to everyone. Clients fulfill three active functions: (a) participate r . 3. The decentralized notary notarizes the block(s) of the preferred
in the decentralized random beacon, (b) participate in the decen- block maker(s). 4. The random beacon advances to round r + 1 upon
tralized notary, (c) propose blocks. Clients also observe blocks and seeing a notarized block from round r .
build their own view of the finalized chain.
behaves like a trusted third party. We emphasize that the commit-
Committees and Threshold Relay. To improve scalability, the ran- tee does not need to run a Byzantine agreement protocol for every
dom beacon and notary are run by a committee. In a small scale output that the beacon produces. Instead, agreement on each of the
network the committee can be the set of all clients. In a large scale beacon’s output is automatic because of the uniqueness property of
network, the committee is smaller than the set of all clients and our threshold signature scheme. This explains how the random bea-
changes from round to round (i.e., from block to block). The random con can run at such high speed, and thereby the Dfinity blockchain
beacon output in one round chooses the committee for the next can achieve such a low block time.
round according to the threshold relay technique described in § 8.1.
Decentralized Notary. As was the case for the random beacon, the
The committee size is configured based on a failure probability
notary is completely decentralized and operated by all clients in the
calculation (see § 4.2.4).
committee together and its behavior as a whole can be equated to a
Block ranking. If we abstract away the decentralized aspect of the trusted third party. However, unlike the random beacon, the notary
random beacon and notary then the consensus protocol is depicted seeks to agree on live input – a block – rather than on a pseudo-
in Fig. 2. The protocol proceeds in rounds such that there is a random number. There is no "magic" cryptography available for
one-to-one correspondence between the round number and the this, so a full Byzantine agreement protocol would be the only
position (called height) in the chain. At the beginning of round r , option. But instead of doing that, the Dfinity notary merely runs
the randomness beacon produces a fresh, verifiable random value an optimistic protocol which achieves consensus "under normal
and broadcasts it to the network (Fig. 2, step 1). The random beacon operation" though may sometimes notarize more than one block
output for round r , denoted by ξ r , determines a priority ranking of per round. If this happens, Dfinity’s chain ranking algorithm will
all registered clients. Any client can propose a block but a higher resolve the fork and finality can be achieved in a subsequent normal
priority level of the client means a higher chance that the block round. The optimistic protocol is non-interactive and fast, hence
will get notarized and that block makers in the subsequent round the notary can run at the same speed as the random beacon.
will build on top of it.
4 MODELS AND PRELIMINARIES
Notarization. Once a client sees a valid ξ r , it pools transactions 4.1 System Model
collected from users into a block candidate and sends it to the
notary (Fig. 2, step 2). The notary waits for a specific constant time 4.1.1 Replicas. From now on we speak of clients as replicas and
(BlockTime) to receive the proposed blocks. Then, the notary runs label them 1, 2, . . . ∈ N. Let U be the finite set of labels of all replicas,
the ranking mechanism based on the random beacon, chooses the called the universe. Each replica i ∈ U has a public/private key pair
highest-ranked block, and signs and broadcasts it (Fig. 2, step 3). As (pki , ski ). We assume the set {pki | i ∈ U } is known and agreed
soon as clients receive a notarized block, they use it to extend their upon2 by all i ∈ U .
copies of the blockchain thereby ending round r in their respective 4.1.2 Authentication. Each protocol message is signed by the
views. Finally, the random beacon broadcasts ξ r +1 which marks the replica that issues the message. The replicas only accept and act
beginning of a new round. upon a message if the message is signed by one of the ski , i ∈ U .

Decentralized Random Beacon. The random beacon protocol is 4.1.3 Groups. At any given time, some or all i ∈ U are arranged
completely decentralized and operated by all clients in the com- into one or more subsets G 1 , G 2 , . . . ⊆ U called groups, of which
mittee together. Nevertheless from the outside (i.e., looking only at 2 In practice, the agreement is achieved by registering all replicas on the blockchain
the outputs produced and the timing of the outputs), the beacon with their public key.
3
Technology Overviews, Jan. 23, 2018, DFINITY Stiftung Timo Hanke, Mahnush Movahedi and Dominic Williams

a single one, the committee, is active to drive progress and ensure Given an acceptable failure probability ρ, we can solve (4.3) for
consensus. We assume all groups G j have the same size n. The the minimal group size n = n(β, ρ, |U |) such that
number n is a system parameter called the group size.
Prob[G honest] > 1 − ρ
4.1.4 Synchrony. For the practical use of Dfinity we assume
a semi-synchronous network by which we mean that the network for each random sample G ⊆ U with |G | = n. The result for the
traversal time can be modeled by a random variable Y whose prob- example value |U | = 104 and different values for ρ and β are shown
ability distribution is known. The Dfinity protocol then chooses in Figure 3 below.
two system-wide timeout constants BlockTime and T based on the
distribution of Y and the security parameter of the system. In the n(β, ρ, 104 )
− log2 ρ
formal security analysis in § 9 we give proofs for the synchronous β =3 β =4 β =5
case in which an upper bound ∆ for Y is known. 40 405 169 111
The two constants are responsible for liveness (BlockTime) and 64 651 277 181
safety (T ) of the system, respectively. Timeout clocks are triggered 80 811 349 227
based on local events, i.e. received messages. The protocol does not 128 1255 555 365
depend on a global time nor does it assume synchronized clocks
between the replicas. Figure 3: Minimal group size for |U | = 104 . Example values for the
The system evolves in rounds. Replicas advance to the next round minimal group size n(β, ρ, 104 ) for adversarial strength 1/β and fail-
based on events. The rounds are not expected to be in sync across ure probability ρ.
different replicas.
As the population size increases to infinity the hypergeometric
4.2 Threat Model
distribution converges to the binomial distribution. Thus, as |U |
4.2.1 Byzantine replicas. A replica that faithfully follows the increases to infinity we get
protocol is called honest and all other replicas are called Byzantine.
A Byzantine i ∈ U may behave arbitrarily, e.g., it may refuse to Proposition 4.2. Let CDFbinom (x, n, p) denote the cumulative
participate in the protocol or it may collude with others to perform distribution function of the binomial probability distribution where p
a coordinated attack the system. is the success probability per draw, n is the sample size and x is the
maximum number of successes allowed per sample. Then
4.2.2 Adversarial strength. For any G ⊆ U let f (G) denote the
number of Byzantine replicas in G. Prob[G honest] ≥ CDFbinom (⌈n/2⌉ − 1, n, 1/β). (4.4)
Assumption 1. There is β > 2 such that Given ρ, we can solve (4.4) for n and get the minimal group size
|U | > β f (U ). (4.1) n(β, ρ) such that n(β, ρ) ≥ n(β, ρ, |U |) for all values of |U |.
The result for different values for ρ and β are shown in Figure 4
The value 1/β is called the adversarial strength. In practice, As- below. As one can see, within the range of interest for ρ, the group
sumption 1 is achieved through economic incentives in conjunction size is approximately linear in − log2 ρ. The resulting group sizes
with a form of Sybil resistance.3 are practical for the protocols described in this paper.5
4.2.3 Honest groups. Let n be the group size. Then a group G is
called honest if n(β, ρ)
− log2 ρ
n > 2f (G). (4.2) β =3 β =4 β =5
The protocols described in § 5-7 rely on 40 423 173 111
64 701 287 185
Assumption 2. Each group G used in the system is honest. 80 887 363 235
4.2.4 Random samples. Given Assumption 1, the universe U it- 128 1447 593 383
self is honest. Each group G ⊆ U used in the system is a random sam-
ple of size n drawn from U . Given n, the probability Prob[G honest] Figure 4: Minimal group size for arbitrarily large U . Example values
can be calculated as follows: for the minimal group size n(β, ρ) for adversarial strength 1/β and
failure probability ρ.
Proposition 4.1. Let CDFhg (x, n, M, N ) denote the cumulative
distribution function of the hypergeometric probability distribution
where N is the population size, M is the number of successes4 in the 4.2.5 Adaptive adversary. We assume that the adversary is mildly
population, n is the sample size and x is the maximum number of adaptive. This means the adversary may adaptively corrupt groups
successes allowed per sample. Then but this corruption takes longer than the activity period of the
Prob[G honest] = CDFhg (⌈n/2⌉ − 1, n, ⌊|U |/β⌋, |U |). (4.3) group.
3 Sybil resistance is achieved for example by requiring a stake deposit for each replica.
Then Assumption 1 translates to the assumption that at least a 1/β fraction of stake 5The main protocols described in this paper are so-called "non-interactive". Group sizes
deposits were made by honest participants. of 1,000 have been tested in implementations and were proven to be unproblematic.
4 In our application M is the number of Byzantine replicas in U . Dfinity plans to launch its network with group sizes in the order of 400.
4
DFINITY Consensus Technology Overviews, Jan. 23, 2018, DFINITY Stiftung

4.3 Cryptographic Primitives The chain C(S) is defined because every C(B), B ∈ S, contains
4.3.1 Hash function. We assume we have a collision-resistant the genesis block. For any sets of blocks S,T with S ⊆ T we have
hash function H with digests of bit-length l where l matches the C(T ) ≤ C(S). Suppose prv S := {prv B | B ∈ S \ {B 0 }} , ∅. Then
security parameter κ.
C(prv S) ≤ C(S). (4.5)
4.3.2 Pseudo-random numbers. We also assume we have a cryp-
tographically secure pseudo-random number generator PRG which 5 PROBABILISTIC SLOT PROTOCOL AND
turns a seed ξ into a sequence of values PRG(ξ , i) for i = 0, 1, . . .. NOTARIZATION
4.3.3 Pseudo-random permutations. The sequence PRG(ξ , i) can As was explained in § 3, each protocol round runs through the
be used as input to the Fisher-Yates shuffle [9, Algorithm 3.4.2P] to steps of producing a random beacon output (1), producing block
produce a random permutation of U . The result is an bijective map proposals (2), and producing block notarizations (3). Since more
{1, . . . , |U |} → U which we denote by PermU (ξ ). than one block can get notarized, these steps alone do not provide
consensus. This is where the probabilistic slot protocol (PSP) steps
4.3.4 Diffie-Hellman. We assume that the adversary is bounded in.
computationally and that the computational Diffie-Hellman prob- Based on block weight, the PSP allows replicas to decide which
lem is hard for the elliptic curves with pairings in [2]. chain to build on when they propose a new block. Over time, this
leads to probabilistic consensus on a chain prefix, where the prob-
4.4 Dfinity’s Block Chain ability of finality increases the more "weight" is added to a chain.
We now define formally the concept of a blockchain in Dfinity. This is analogous to proof-of-work chains, where the probability
of finality increases the more "work" is added to a chain. However,
4.4.1 Blocks. Dfinity does not stop here and does not rely on this probabilis-
tic type of finality decisions. PSP is only used to guide the block
Definition 4.3. A block is either a special genesis block or a tuple
proposers. For finality, Dfinity applies a faster method utilizing a
(p, r , z, d, o) where p ∈ {0, 1}l is the hash reference to the previous
notarization protocol.
block, r ∈ N is the round number, z ∈ {0, 1}∗ is the notarization of
For this section, we assume the random beacon (which we in-
the previous block, d ∈ {0, 1}∗ is the data payload ("transactions"
troduce later in § 7) is working without failure and provides all
and "state"), o ∈ U is the creator (or "owner"). A notarization is a
replicas with a new, unbiased random value ξ r at the start of each
signature on the previous block created by a "notary". For a block
round r . Figure 5 shows how the protocol alternates between ex-
B = (p, r , z, d, o) we define
tending the blockchain and extending the random beacon chain and
prv B := p, nt B := z, rd B := r, dat B := d, own B := o. demonstrates how the random beacon, block proposer and notary
advance in lockstep.
We emphasize that a block contains the notarization z of the For the exposition of the present section, however, the decen-
previous block in the chain that it references. tralized nature and precise inner workings of the random beacon
4.4.2 Chains. are irrelevant. Hence we simply regard the sequence ξ r as given
without making further assumptions about it.
Definition 4.4. By a chain C we mean a finite sequence of blocks Regarding the threat model, we assume (4.2) for all groups, as
(B 0 , B 1 , . . . , Br ) with rd Bi = i for all i, prv Bi = H (Bi−1 ) for all stated in Assumption 2. However, for the description and under-
i > 0, and nt Bi a valid signature of Bi−1 for all i > 0. The first standing of the notarization protocol it is sufficient to assume that
block B 0 is a genesis block. The last block Br is called the head of there is only a single group consisting of the universe of replicas U
C. We define and that
len C := r + 1, gen C := B 0 , head C := Br . |U | > 2f (U ). (5.1)

Since blocks in a chain are linked through cryptographic hashes, For simplicity of exposition we do adopt this view. It may then be
a chain is an authenticated data structure. A chain is completely apparent that the protocol described in this section can be delegated
determined by its head by virtue of to any honest committee or sequence of honest committees.

Proposition 4.5. It is computationally infeasible to produce two 5.1 Block Rank and Chain Weight
chains C , C ′ with head C = head C ′ .
Based on ξ r , the protocol assigns a rank to each i ∈ U and the rank
Definition 4.6. We write C(B) for the uniquely defined chain C of the proposer defines the weight of a block as follows.
with head C = B. Given two chains C, C ′ we write C ≤ C ′ if C is a
Definition 5.1 (Replica Ranking). The ranking permutation for
prefix of C ′ .
round r is defined as πr := PermU (ξ r ). The rank of i ∈ U in round
Assume from now on that all chains have the same genesis block r is defined as πr (i).
B0 .
Definition 5.2 (Block Ranking). The rank of a block B is defined
Definition 4.7. For any non-empty set S of blocks we denote by as rk B := πr (own B) where r = rd B. We say B has higher priority
C(S) the largest common prefix of all chains C(B) with B ∈ S. level than B ′ if rk B < rk B ′ .
5
Technology Overviews, Jan. 23, 2018, DFINITY Stiftung Timo Hanke, Mahnush Movahedi and Dominic Williams

σr | |ξ r ,i 1
ξ r −1 ξr ξ r −1 ξr ξ r −1 ξr σr | |ξ r ,i 2 ξ r −1 ξr ξ r +1
...
σr | |ξ r ,i t
σ Br ,i 1
Br −1 Br σ Br ,i 2 Br −1 Br Br −1 Br Br −1 Br
...
zr −1 σ Br ,i t zr −1 zr zr −1 zr zr −1 zr

1. In round r , a block B r is being pro- 2. B r has received signature 3. Members of the random beacon com- 4. The next random beacon output ξ r +1
posed by a block maker that is prior- from a majority of replicas and mittee, which is selected by ξ r , sign the is formed as a unique threshold signa-
itized by ξ r . B r references the previ- is now notarized by virtue of the previous randomness ξ r right after en- ture. The cycle continues with step 1
ous block B r −1 . Members of the no- aggregated signature z r . Every tering round r + 1. for round r + 1.
tary committee, which is selected by ξ r , replica enters round r + 1 upon
sign off B r . seeing z r .

Figure 5: Alternation between the random beacon chain and the notarized blockchain.

r −3 r −2 r −1 r 5.3 Block Notarization

w(0) = 1 wt C 1 = 3.25 The goal of notarization is to enforce that chains are only being
built from blocks that were published during their respective round,
not later. In other words, notarization prevents that an adversary
w(1) = 12 wt C 2 = 3
can build a private conflicting chain and reveal it later. Blocks that
are revealed too late cannot get notarized anymore, so that the
w(2) = 14 timely publication of block proposals is enforced. A notarization is
therefore regarded as a timestamp as well as a proof of publication.
The protocol guarantees to notarize at least one of multiple
w(2) = 18 proposed chain heads for the current round. It attempts to notarize
exactly one chain head for each round but does not guarantee that.
Figure 6: Block proposals. The weight of each block is Therefore, notarization does not imply consensus nor does it require
1, 1/2, 1/4, 1/8, . . ., based on the rank of its proposer. Each chain consensus.
accumulates the weights of its blocks (here shown only for blocks When participating in the notarization protocol the replicas are
starting at round r − 3). A replica with this view will resolve between only concerned about extending at least one valid chain, not about
the two forks that are still active at round r and will choose to build
which chain wins (which is the subject of the finalization in § 6).
on the heavier one: C 1 .
Definition 5.5. A notarization of block B is an aggregated signa-
ture by a majority subset of U on the message B. We call a block
If an adversary equivocates then there will be multiple blocks signed if it has received at least one signature and notarized if it has
for the same round with the same rank. received a notarization. A notarized block is a block concatenated
We assume the protocol has defined a monotonically decreasing with a notarization of itself.
function w. In particular, for Dfinity we instantiate w as w(x) = As described in Alg. 1 below, each replica in each round r collects
2−x . all valid block proposals from all replicas (including from itself) for
Definition 5.3 (Block Weight). The weight of a block B is defined a fixed time frame, the so-called BlockTime. A proposed block B is
as wt B := w(rk B). considered valid for round r if rd B = r and there is a valid block
B ′ such that
Definition 5.4 (Chain Weight). The weight of a chain C = (B 0 , . . . , Br ) (1) prv B = H (B ′ ) and rd B ′ = rd B − 1,
Ír
is defined as wt C := h=0 wt Bh . We call C heavier than another (2) nt B is a notarization of B ′ ,
chain C ′ if wt C > wt C ′ . (3) dat B is valid.7
After BlockTime, the replica signs all highest priority blocks for
5.2 Block Proposals
the current round that it has received and broadcasts a signature
At each round each replica can propose a block. To do so, in round message for this block to the entire network.
r + 1, the replica selects the heaviest valid6 chain C with len C = r More than one block can have the highest priority but only if
in its view (cf. Fig. 6). The replica then considers all new trans- the block maker has equivocated. In this case all equivocated block
actions that it has received from users. The new proposed block proposals will get signed. This is not an issue because each honest
Br references head C and is composed of the selected transactions. block makers in the next round will only build on one of the blocks.
The replica broadcasts Br in order to request notarization from the 7 Having a validity criteria for dat B is optional and not required for the consensus
notary committee. protocol. Depending on the application of the blockchain, for example, dat B can be
configured to be valid only if dat B represents valid transactions and a valid state
6 Validity of blocks is explained after Def. 5.5. A chain is valid if and only if all its transition from dat B ′ . From the perspective of the consensus protocol dat B is arbitrary
blocks are valid. data.
6
DFINITY Consensus Technology Overviews, Jan. 23, 2018, DFINITY Stiftung

The replica continues to sign all highest priority block proposals Definition 5.7. An artifact of round r was timely published (within
as it receives more block proposals after BlockTime. When a nota- d rounds) if it was broadcasted while at least one honest replica
rization for the current round has been observed then the replica was in round ≤ r (resp. in round ≤ r + d).
advances to the next round.
As a rule, honest replicas re-broadcast every block that they sign.
Hence,
Algorithm 1 – Block Notarization
Only timely published blocks can be honestly signed. (5.2)
Goal: Notarize at least one block for the current round.
Given a signed block, it is not possible to tell whether the block
1: Initialize chain with the genesis block was timely published or not because it is not possible to tell if the
2: r ←1 ▷ initialize round number signature was honest or not. This is different for notarized blocks
3: while true do as we will explain next.
4: Wait(BlockTime)
5: while no notarization for round r received do 5.4.4 Notarization withholding. By (5.1), any majority subset of
6: B ← set of all valid round-r block proposals so far replicas contains at least one honest replica. Thus, we have:
7: for All B ∈ B with minimal rk B do (5.3)
Only honestly signed blocks can get notarized.
8: if B not already signed then
9: σ ← Sign(B) We emphasize that an adversary can withhold its own signatures
10: Broadcast(σ ) under an honestly signed block which can lead to a situation where
11: end if an honestly signed block does not appear to be notarized to the pub-
12: end for lic. However, the adversary can use its own signatures to produce
13: end while and reveal a notarization at any later point in time.
14: r ←r +1 5.4.5 Enforcing publication. By (5.3) and (5.2),
15: end while
Only timely published block proposals can get (5.4)
notarized.
However, despite (5.4), notarizations can be withheld. To show
5.4 Properties of notarization that withholding notarizations is harmless we introduce another
5.4.1 Liveness. From the description above it should be clear theoretical concept:
that Algorithm 1 cannot deadlock – even in the presence of an
Definition 5.8. A notarization z is referenced if there is a notarized
adversary. The fact that each replica continues to sign the highest
block B with nt B = z.
priority block proposal until a notarization for the current round is
observed is sufficient to ensure that at least one block gets notarized Note that publishing a block, B, implicitly publishes the nota-
in the current round. Eventually this will happen because (5.1) holds rization of the previous block, nt B, because nt B is contained in B.
and the ranking establishes a well-ordering on the set of block Hence, (5.4) implies
proposals. After observing the first notarization for the current
Only notarizations that are timely published within 1
round it is safe to stop signing because the observed notarization is (5.5)
round can get referenced.
being re-broadcasted and will eventually reach all honest replicas.
Thus, all honest replicas will advance to the next round. Obviously, in a surviving chain all notarizations are referenced.
The above argument relies on propagation assumptions for block Thus, the publication of both block proposals and notarizations
proposals and notarizations. We will analyze these in detail, includ- is enforced. An adversary cannot build a private chain because a
ing the relay policies involved, and provide a formal proof for chain can only survive if:
liveness in § 9. • All its blocks were timely published.
• All its notarizations were timely published within 1 round.
5.4.2 Honestly signed blocks.
5.4.6 Consensus. We stated above that a chain can only survive
Definition 5.6. A block is called honestly signed if it has received if all its notarizations were timely published within 1 round. This
at least one signature from an honest replica. means a replica looking at the notarizations of round r can restrict
Note that an honest replica i only issues a signature on a block itself to a certain time window. All notarizations for round r re-
B if B was the highest priority proposal visible to i at some point ceived after that window are necessarily irrelevant for the surviving
in the round after BlockTime expired. The concept of honestly chains. This fact is the key to the finalization algorithm in § 6 below.
signed blocks is a theoretical one, used to argue about the security See Figure 7 for an example.
properties of the notarization protocol. It is not possible to tell if There are multiple ways that this fact can lead to a consensus
a given signature was issued by an honest or Byzantine replica. point. Note that it is not necessary for consensus that a single block
Hence it is not observable whether a signed block is an honestly gets notarized in a round, nor that a single notarization can get
signed block or not. referenced. It is sufficient for a consensus point that all notarizations
that were received within the time window (indirectly) reference
5.4.3 Timely publication. the same block one (or more) rounds back.
7
Technology Overviews, Jan. 23, 2018, DFINITY Stiftung Timo Hanke, Mahnush Movahedi and Dominic Williams

5.4.7 Normal operation. Algorithm 2 – Finalization

Definition 5.9. A round has normal operation if only one block Goal: Build the finalized chain from observing notarized
for that round gets notarized. blocks.
Main:
Algorithm 1 strives to achieve normal operation by enforcing the
1: Ni ← ∅ for all i ▷ Empty buckets for notarized blocks
BlockTime waiting period, and by giving preference to the highest
2: N0 ← {B 0 } ▷ Consider genesis block "notarized"
priority block proposal.
3: C ← (B 0 ) ▷ Finalized chain
If the highest priority block maker is honest and BlockTime is
4: r ← 1 ▷ Current round
large enough then the highest priority block proposal will arrive at
5: while true do
all honest replicas before BlockTime expires. This means that only
6: while Nr = ∅ do
one block can get notarized in this round. Hence, assuming that
7: B ← incoming notarized block
BlockTime is chosen correctly, Algorithm 1 will achieve normal
8: Store B in Nrd B
operation in every round in which the highest priority block maker
9: end while
is honest.
10: Schedule the call Finalize(r − 1) at time T from now
We will analyze in detail what it means that BlockTime is "large
11: r ←r +1
enough" (see § 9), taking into account the inner workings of the
12: end while
broadcast network such as the relay policy. We will show that if
the network traversal time is bounded by ∆ then Alg. 1 is correct if Finalize(h):
BlockTime ≥ 3∆ (Cor. 9.16, Prop. 9.24, Prop. 9.27). 1: if h > 0 then
Note that every round with normal operation creates consensus 2: C ← C(Nh )
on the unique block notarized in that round. However, normal 3: end if
operation is a theoretical concept that cannot be observed due to
the possibility of notarization withholding. Luckily, as we saw in r −3 r −2 r −1 r
§ 5.4.6, normal operation is not necessary for consensus.

AL

AL
0
N

N
FI

FI
6 FINALIZATION
Replicas use the finalization procedure described in Alg. 2 to identify
points of consensus. For this process, it suffices to observe only
D

D
1
EA

EA
the notarized blocks, i.e. block proposals and individual signatures
D

D
under block proposals can be ignored. The finalization protocol
is passive and independent from the notarization protocol. Since
D

it can be carried out by anyone (outside of the replicas) who has 2

EA
D

access to the notarized blocks, we speak of observers in this section

rather than of replicas.
Figure 7: Finalizing blocks. The diagram shows a view of notarized
6.1 Description blocks at time T after first seeing a notarized block for round r (i.e. at
Algorithm 2 makes the assumption that the observer receives all time T after ending round r and beginning round r + 1). According
round-(r − 1) notarizations that can get referenced before time to the correctness assumption, (6.1), no additional blocks that receive
T after having received the first notarization for round r . This an inbound arrow can appear for the empty positions on the left of
the vertical dashed line. Therefore, we mark positions (r − 2, 2) and
assumption is equivalent to the correctness of Alg. 2 and is proved
(r −1, 0) with a cross. The Finalize(r −1) procedure outputs the longest
for all replicas in Theorem 9.18. common prefix, marked "FINAL", of all chains defined by blocks from
The general idea of Alg. 2 is as follows: We continuously collect round r − 1 as their chain tips. As a consequence the blocks marked
all notarized blocks and bucket them according to their round "DEAD" are now excluded from ever becoming final.
number. Let Nr be the bucket for all notarized blocks for round r .
Multiple buckets can be filled concurrently. For example, a second
block may go into Nr even when Nr +1 is already non-empty. How- 6.2 Properties of Finalization
ever, a block cannot be validated without knowing its predecessor. We emphasize that there are some notable differences between the
Therefore, we assume that for every pair of blocks that reference use of BlockTime and T : BlockTime is agreed upon and part of the
each other, the predecessor is processed first. As a consequence Nr protocol specification, whereas each observer can specify its own
must receive its first element before Nr +1 does. T . The notarization protocol requires only BlockTime, not T . The
By our initial assumption, for each round r , there is a time when finalization protocol requires only T , not BlockTime.
we can rule out the receipt of any further notarized blocks for Nr The following assumption about Alg. 2 is called the correctness
that can get referenced. At that time we "finalize" round r because assumption:
we know that Nr already contains all chain tips that can possi- At the time when Finalize(h) is being executed, Nh
bly survive beyond round r . Therefore, we can output the longest contains all round-h blocks that can get referenced.
(6.1)
common prefix C(Nr ) as being final.
8
DFINITY Consensus Technology Overviews, Jan. 23, 2018, DFINITY Stiftung

Proposition 6.1. Suppose (6.1) holds. Then the chain C in Alg. 2 that if we set n = 2t − 1 then both conditions are equivalent to
is append-only. f ≤ t − 1.
The threshold signature scheme used in the DRB protocol is
The assertion justifies to call the chain C in Alg. 2 finalized. set up using a distributed key generation mechanism (see 7.1.4)
which does not rely on trusted parties. We start by providing the
Proof. Let Ch , Ch+1 be the chains returned by Finalize(h) and
background information on threshold cryptography that we use.
Finalize(h + 1), respectively, in an execution of Alg. 2. Let Nht
denote the set Nh at time t. Obviously, Nht can grow with increasing
7.1 Background on Threshold Cryptography
t. Let t 0 , t 1 be the times when Finalize(h), Finalize(h+1) are called,
respectively. By (6.1), none of the blocks added to Nh after t 0 can get
referenced. In other words, we have prv(Nh+1 ) ⊆ Nht0 regardless 7.1.1 Threshold Signatures. In a (t, n)-threshold signature scheme,
of the time at which Nh+1 is considered. Thus, n parties jointly set up a public key (the group public key) and each
(4.5) party retains an individual secret (the secret key share). After this
Ch = C(Nht0 ) ≤ C(prv(Nh+1
t1 t1
)) ≤ C(Nh+1 ) = Ch+1 . setup, t out of the n parties are required and sufficient for creating
□ a signature (the group signature) that validates against the group
public key.
We will show that if the network traversal time is bounded by ∆
7.1.2 Non-interactiveness. A threshold signature scheme is called
then (6.1) holds if T ≥ 2∆ (Thm. 9.18, Prop. 9.25). Notably, this result
non-interactive if the process of creating the group signature in-
does not make any assumptions about BlockTime, i.e. the result
volves only a single round of one-way communication for each of
holds even if the notaries choose an incorrect value for BlockTime.
the t participating parties. Typically in a non-interactive scheme,
There is alternative version of Alg. 2 which does not require the
each participating party creates a signature share using its indi-
parameter T . In line 10, instead of calling Finalize(r − 1) at time T
vidual secret and sends this signature share to a third party. Once
from now, the alternative calls Finalize(r − 2) immediately. This
the third party has received t valid shares it can recover the group
can also guarantee (6.1) according to Cor. 9.19 but it requires an
signature without any further interaction. For example, ECDSA can
assumption about the value of BlockTime used by the notaries.
be turned into a threshold signature scheme ([6]) but it does not
have the property of non-interactivity.
7 DECENTRALIZED RANDOMNESS BEACON
The decentralized random beacon protocol (DRB) allows replicas to 7.1.3 Uniqueness. A signature scheme is called unique if for
agree on a verifiable random function (VRF) and to jointly produce every message and every public key there is only one signature
one new output of the VRF in every round. By a VRF we mean a that validates successfully. This property applies to single signa-
commitment to a deterministic, pseudo-random sequence (ξ r )r ≥0 ture schemes and threshold signature schemes alike. But in the
for which each output ξ r is unpredictable given the knowledge setting of a threshold scheme it has the additional requirement
of all prior outputs ξ 0 , . . . , ξ r −1 and for which each output ξ r is that the signature must not depend on the subset of t parties that
verifiable for correctness by anyone against the commitment. In participated in creating the signature. In other words, in a unique
particular, the VRF outputs are unbiasable due to their deterministic threshold signature scheme, regardless of who signs, the resulting
pseudo-random nature. In our decentralized protocol, the output ξ r group signature will always be the same.
shall not be predictable by the adversary before at least one honest "Unique" is a property that is strictly stronger than "determinis-
replica has advanced to round r . tic". A signature scheme is called deterministic if the signing function
Regarding the threat model, we assume (4.2) for all groups, as does not use randomness. Note that "unique" is a property of the
stated in Assumption 2. For simplicity of exposition we describe verification function whereas "deterministic" is a property of the
the random beacon protocol for a single group G with |G | = n and signing function. Unique implies deterministic but not conversely.
n > 2f (G). The protocol can then be adapted to be executed by For example, DSA and ECDSA can be made deterministic by re-
changing groups as described in § 8.1 below. defining the signing function in a way that it derives its so-called
Our DRB protocol uses unique t-of-n threshold signatures (see "random k-value" deterministically via a cryptographic hash func-
§ 7.1) created by the group G as the source of randomness. The tion from the message plus the secret key instead of choosing it
adversary cannot predict the outcome of such a signature if f ≤ t −1 randomly. However, this technique cannot be used to make DSA
and cannot prevent its creation if f ≤ n − t. If the adversary could or ECDSA unique because one cannot expose the k-value to the
abort the protocol by preventing a signature from being created, verification function.
then any restart or fallback mechanism would inevitably introduce
7.1.4 Distributed Key Generation (DKG). For a given (t, n)-thres-
bias into the output sequence.8 We treat the two failures (predicting
hold signature scheme, a DKG protocol allows a set of n parties
and aborting) equally. Therefore we require t ∈ [f + 1, n − f ]. Note
to collectively generate the keys required for the scheme (i.e. the
8Several existing proposals in the literature are susceptible to bias due to a single party
group public key and the individual secret key shares) without the
aborting the protocol. For example Algorand [8, § 5.2] describes a fallback mechanism help of a trusted party.
which inevitably introduces bias. RANDAO [1] relies on game-theoretic incentives to Note that a DKG protocol is more than a secret sharing protocol.
keep malicious actors from aborting the protocol. In practice, however, the gain for a
malicious actor from biasing the randomness is unbounded whereas the penalty for In a secret sharing protocol the secret shares can be used to recover
aborting is bounded. the group secret, but this can be done only once. After everyone
9
Technology Overviews, Jan. 23, 2018, DFINITY Stiftung Timo Hanke, Mahnush Movahedi and Dominic Williams

has learned the group secret the shares are not reusable. In a DKG are produced. The DKG is slow and requires agreement whereas
the shares can be used repeatedly for an unlimited number of group the repeated signing is non-interactive and fast.
signatures without ever recovering the group secret key explicitly.
7.3.1 Setup. When setting up a threshold signature scheme, we
DKG protocols are relatively straight-forward for discrete-log
do not want to rely on any trusted third party. Therefore, the group
based cryptosystems and typically utilize multiple instances of a
G runs a DKG for BLS to set up the group public key and the secret
verifiable secret sharing protocol (VSS). Dfinity uses the "Joint-
key shares during the initialization of the blockchain system. The
Feldman DKG"9 as described in [7].
threshold t is a parameter of the setup.
Once the DKG has finished successfully, it outputs a public ver-
7.2 The BLS signature scheme
ification vector VG ∈ Gt2 , and leaves each replica i ∈ G with its
The only known signature schemes that have a unique, non-interactive secret key share skG,i . The verification vector VG gets committed
threshold version and allow for a practical, efficient DKG are the to and recorded in the blockchain, for example in the genesis block.
pairing-based schemes derived from BLS [3]. BLS was introduced Let VG = (v 0 , . . . , vt −1 ). The group public key is pkG = v 0 ∈ G2 .
by Boneh, Lynn, and Shacham in 2003 and related work can be The secret key skG corresponding to pkG is not known explicitly
found in [10]. We shall use the original BLS scheme throughout. to anyone in G but can be used implicitly through skG,i . The ver-
7.2.1 BLS functions. Assuming we have generated a secret/public ification vector VG can be used to recover the public key share
key pair (sk, pk), BLS provides the following functions: pkG,i ∈ G2 corresponding to skG,i via “polynomial” substitution
(1) Sign(m, sk): Signs message m using secret key sk and re- t −1
vki ∈ G2 .
k
Ö
turns signature σ . pkG,i =
(2) Verify(m, pk, σ ): Verifies the signature σ for message m k =0
against the public key pk and returns true or false. Hence, all signature shares produced by i can be publicly verified
Under the hood, BLS uses a non-degenerate, bilinear pairing against the information VG and i. The group public key pkG can
be used to verify the output of Recover.
e : G1 × G2 → GT
7.3.2 Signing process. Recall that a replica enters round r upon
between cyclic subgroups G1 , G2 of suitable elliptic curves points
seeing the first notarization for round r − 1. At the beginning of its
with values in a group of units GT . We shall write all groups multi-
round r , replica i ∈ G computes the signature share
plicatively in this paper. For each group, we fix an arbitrary gener-
ator: д1 ∈ G1 , д2 ∈ G2 , дT ∈ GT . We also assume a hash function σr,i = Sign(r ∥ ξ r −1 , skG,i ),
H 1 : {0, 1}∗ → G1 with values in G1 . where ξ r −1 is the random value of round r − 1. To bootstrap, ξ 0 has
The secret keys are scalars, the public keys are elements of G2 been set to a nothing-up-my-sleeve number, e.g. the hash of the
and the signatures are elements of G1 . The function Sign(m, sk) string “Dfinity”. Replica i then broadcasts (i, σr,i ).
computes H 1 (m)sk and Verify(m, pk, σ ) tests whether e(σ , д2 ) = Any replica who receives this data can validate (i, σr,i ) against
e(H 1 (m), pk). the public information VG as described in 7.3.1 above. If valid
7.2.2 Threshold BLS. We refer to the threshold version of BLS as then the replica stores and re-broadcasts (i, σr,i ). As soon as a
TBLS. The same functions Sign and Verify that are defined for BLS replica has received at least t different valid signature shares, it
also apply to the key/signature shares and group keys/signatures runs Recover(i 1 , . . . , i t , σr,i 1 , . . . , σr,i t ) to compute the group sig-
in TBLS. We assume all participating parties in the (t, n)-DKG are nature σG,r . Finally, the random output ξ r for round r is computed
numbered 1, . . . , n. After having run the DKG as in 7.1.4, the (t, n)- as the hash of σG,r .
TBLS provides additionally the function: We emphasize that the signing process is non-interactive. Any
third party can do the recovery after a one-way communication of
(1) Recover(i 1 , . . . , i t , σi 1 , . . . , σi t ): Recover the group signa- sufficiently many shares.
ture σ from the signature shares σi j , j = 1, . . . , t, where
σi j is provided by the party i j ∈ {1, . . . , n}. 8 SCALABILITY
Because of the uniqueness property, the output of Recover does
not depend on which t shares from the group are used as inputs.
8.1 Threshold Relay
Recover computes a "Lagrange interpolation" for points in G1 . The For reasons of scalability the notarization and random beacon pro-
indices i 1 , . . . , i t must be pairwise different for the Recover function tocols from § 5 and § 7 are executed by groups of size n rather than
to succeed. by all replicas in U . Otherwise the message complexity would be
unbounded as the total number of replicas grows.
7.3 Randomness Generation The groups, also called committees here, are random samples of
The randomness generation consists of a) a one-time setup in which size n from the whole population U . The group size n is a system
a DKG is run and b) a repeated signing process in which the outputs parameter that is chosen according to the failure probability anal-
ysis of § 4.2.4. A large enough group size ensures that – up to an
9 It is known from [6] that the adversary can bias the distribution of public keys acceptable failure probability – every group used in the system is
generated by the Joint-Feldman DKG. However, the bias generally does not weaken honest (Assumption 2).
the hardness of the DLP for the produced public key ([6, § 5]). Therefore, with the
simplicity of our protocol in mind, we use the original, unmodified Joint-Feldman DKG The mechanism by which Dfinity randomly samples replicas
even though variations are available that avoid the bias. into groups, sets the groups up for threshold operation, chooses
10
DFINITY Consensus Technology Overviews, Jan. 23, 2018, DFINITY Stiftung

the current committee, and relays from one committee to the next Let r be the first round of epoch e. For each j ≤ m max the j-
is called threshold relay. th candidate group is defined as G = Group(ξ r , j). The members
of G run a DKG to establish a group public key pkG . If the DKG
8.1.1 Group Derivation. Let n be the group size. The groups are
succeeds then the members create a registration transaction for
derived from a random seed ξ where the j-th derived group is
G which contains the tuple x = (e, j, pkG ). After x is signed by a
Group(ξ , j) := PermU (PRG(ξ , j))({1, . . . , n}). (8.1) super-majority of G, any member can submit x for inclusion in
At the start of the system, we choose a number m and a seed ξ the blockchain. The validity of the signature under x is publicly
and form groups verifiable against the information already on the blockchain, i.e.,
the pool U of active replicas and the random beacon output ξ r that
G j := Group(ξ , j), j = 1, . . . , m. (8.2)
defined the group. A registration transaction x is only valid if it is
Each G j runs the DKG described in Section 7.3 to create group keys included in a block that lies within the epoch e.
pkG j which are then stored in the genesis block. If the DKG fails or x fails to get a super-majority signature from
G or x is not included in the blockchain within epoch e then G
8.1.2 Committee Selection. The sequence (ξ i ) is bootstrapped
cannot register. An adversary can cause the registration to fail. For
by defining an initial value for ξ 0 . Then, in round r , we choose
example, if the super-majority is defined as a 2/3-majority then an
G (r ) := G j , j := ξ r mod m (8.3) adversary controlling ≥ 1/3 of G can deny the signature under x.
as the committee for round r . The same committee can be used However, due to variance, this will happen only to some of the
for the notarization and the random beacon protocols of the same group candidates. For example, an adversary controlling < 1/3 of U
round. will control < 1/3 in at least half of all groups.
In the random beacon protocol, the members of G (r ) jointly pro- Groups are de-registered automatically when they expire after a
duce the output ξ r , which is then used to select the next committee fixed number of epochs defined by a system parameter.
G (r +1) . Since activity is relayed from one group to the next, we call 8.2.4 Delayed Activity. If the registration of a new identity
the mechanism "threshold relay". (replica or group) is included in the chain in epoch e, then the
newly registered entity becomes active in epoch e + 2. Thus, there
8.2 Open Participation is always a gap of at least l rounds between the registration of a
It is impractical to assume that the set of all replicas is known from new entity and the first activity of that new entity. This sequence
the start of the protocol, especially in Dfinity’s public chain. This of events is shown in Fig. 8.
section describes how the protocol adopts an open participation The gap is required to ensure that all registrations of new entities
model in which new replicas can join and existing replicas can leave are finalized before they can be allowed to have any influence on the
the system. random beacon. The minimum value of l can be derived from the
growth property of the finalized chain that is proved in Prop. 9.24
8.2.1 Epochs. We divide the rounds into non-overlapping epochs
below.
of length l where l is a system parameter and is fixed. The block
Dfinity uses a value for l that is far greater than the minimum
produced in the first round of each epoch is a registry block (also
required, because we want to limit the rate at which key frames
called key frame) and contains a summary of all new registrations
are produced, in order to reduce load on so-called observing "light
and de-registrations of replicas that happened during the previous
clients".
epoch that just ended. Note that the summary is a deterministic
result of all the blocks in the preceding epoch so that the block
maker of the key frame has no opportunity to censor registrations. 9 SECURITY ANALYSIS
The first round of the very first epoch is DFINITY’s genesis block In this section, we show that the Dfinity protocol provides us with
which is also a key frame. a robust and fast distributed public ledger abstraction. Any ledger
must satisfy the following two fundamental properties which we
8.2.2 Registration of Replicas. A replica can request to join the will derive from lower-level properties in § 9.4.
network (i.e. register) or leave the network (i.e. de-register) by sub-
mitting a special transaction for that purpose. The transaction is Definition 9.1 (Ledger properties).
submitted to the existing replicas for inclusion in the chain just a) Persistence. Once a transaction is included into the finalized
like any other user transaction. A registration transaction contains chain of one honest replica, it will then be included in every
the public key of the new replica plus an endorsement proving that honest replica’s finalized chain.
it was allowed to form. Depending on the underlying Sybil resis- b) Liveness. All transactions originating from honest parties will
tance method, the endorsement is, e.g., the proof of a locked-up eventually be included in the finalized chain.
stake deposit, the solution to a proof-of-work puzzle tower, or the
certification by a central, trusted authority. What distinguishes Dfinity from other ledgers is the property
of near-instant finality. This property is formalized by the following
8.2.3 Registration of Groups. The random beacon output of the two definitions and theorem.
first round in an epoch e defines the composition of all the groups
that are allowed to newly enter the system during this epoch. A Definition 9.2 (Number of Confirmations). We say a transaction
system parameter, m max , governs how many different groups can has n confirmations if it is contained in a notarized block Br and
form during an epoch. there is a chain of notarized blocks of the form (. . . , Br , . . . , Br +n−1 ).
11
Technology Overviews, Jan. 23, 2018, DFINITY Stiftung Timo Hanke, Mahnush Movahedi and Dominic Williams

Key Frame Key Frame Key Frame Key Frame

Block Block Block Block
e −3 e −2 e −1 e
Chain Head

Join tx Join tx Activation

Group Client Group
0x2b197453 0x6e22e1ba 0x2b197453
Client
0x6e22e1ba

Figure 8: Epochs and Registration. The chain is divided into epochs defined by the round numbers of the blocks. A client joins by submitting a special transaction
into a block which also locks up a stake deposit. A group joins by successfully executing a DKG (distributed key generation) and submitting the result as a join
transaction into the blockchain. Clients and groups become actively involved in the protocol only after a gap of at least 1 epoch between their join transaction
and their first activity.

Note that the definition refers to any notarized blocks known to replicas cannot observe whether an artifact has saturated the net-
the replica, not necessarily finalized blocks. work or not. Saturating the network does not constitute a reliable
broadcast.
Theorem 9.3 (Main Theorem). Under normal operation in round
Artifacts can be received out of order, e.g. a signature or a nota-
r , every transaction included in a block for round r is final after two
rization for a block can be received before the block. If an artifact
confirmations plus the maximum network roundtrip time 2∆.
x is received before an artifact that is referenced by x then x can
From the perspective of an arbitrary observer, the Main Theorem not be validated. For this reason, all honest replicas first queue any
means the following. Suppose an observer sees a transaction x that incoming artifact x until all artifacts referenced by x have also been
has received two confirmations, i.e. a notarized block Br for round r received. Only then is x processed. In particular, an honest replica
containing x and another notarized block Br +1 with prv Br +1 = Br . i relays an artifact x only if it possesses all artifacts referenced by
If round r experienced normal operation then, at time 2∆ after x. Hence, a peer j of i who receives x from i can then request any
the observer received the notarization for Br +1 , the finalization artifact that is referenced by x that j does not already possess. This
algorithm (Alg. 2) is guaranteed to append Br to the observer’s final is an artifact synchronization process which happens transparently
chain. We assume here that T in Alg. 2 is set to 2∆. The proof of in the background and is completed before j processes x. Therefore,
the Main Theorem will occupy § 9.3 below. throughout the paper, we take for granted that if an artifact x is
We will provide proofs for the synchronous model where an received then all artifacts referenced by x have also been received.
upper bound for the network traversal time ∆ is known. We assume Signatures under block proposals are collected in a background
that processing times for messages are included in the network process and, once a majority is available for a given block proposal,
traversal time. are aggregated into a notarization which is then treated in the
same way as if it was received from outside. Block proposals and
9.1 Broadcast and Processing notarizations are collected in the background and made available
The security analysis must take into account the behavior of the to Alg. 1 and 2.
broadcast network, which implements a gossip protocol. In par- Our relay policy and network assumptions (see § 9.2.1 below)
ticular, the relay policy that is applied to gossiping is going to be guarantee the following property:
essential for the provability of our results.
Replicas continuously receive new protocol artifacts, e.g. block Any artifact that falls under b) and is processed by an
(9.1)
proposals, signatures under block proposals, notarizations, nota- honest replica will eventually saturate the network.
rized blocks or random beacon outputs. As soon as an artifact is Property (9.1) does not hold for artifacts relayed under policy a)
determined to be valid it is immediately relayed ("gossiped") to the because a replica in the middle of the broadcast path may have
replica’s peers if it falls under the relay policy defined below. advanced to the next round in which case the artifact will be con-
Definition 9.4 (Relay Policy). All honest replicas relay the follow- sidered old and will be dropped.
ing artifacts Suppose an honest replica i has processed a block proposal B and
considered it valid. Then i must possess prv B and a notarization
a) for the current round: valid block proposals and valid signatures
of prv B. We emphasize that the honest replica i re-broadcasts the
under block proposals,
notarized block prv B in this case. By (9.1), this behavior guarantees:
b) for any round: notarizations and notarized blocks.
We say an artifact has saturated the network if it has been received If a block B is honestly signed then the notarized block
(9.2)
by all honest replicas. prv B eventually saturates the network.
We emphasize that saturating the network is a global condition Property (9.2) does not hold for B itself or for individual signatures
that is only of theoretical value in our security arguments. The under B, for these artifacts do not fall into category b) of Def. 9.4.
12
DFINITY Consensus Technology Overviews, Jan. 23, 2018, DFINITY Stiftung

9.2 Timing and Progress 9.2.2 Maximal Progress.

This section makes statements about the relative timing of events Lemma 9.9 (Notarization, "Fast" Bound). For all rounds r we
that happen at different replicas. We do not assume normal opera- have:
tion in any round and therefore have to consider the possibility of
multiple notarizations zr , zr′ , . . . being created and broadcasted for τ (r ) + BlockTime ≤ τ ∗ (r + 1). (9.5)
¯ ¯
the same round r .
Proof. Honest replicas participate in a notarization zr for round
9.2.1 Preliminaries. We assume that a message broadcasted by r only after they have been in round r for at least BlockTime
an honest replica at time t reaches every honest replica before t + ∆ (cf. Alg. 1). The inequality (9.5) means that at least one honest
(i.e. at a time < t + ∆). Since processing times are not in the scope of replica is required before anyone can see a notarization zr for
our analysis, we assume all processing times to be zero. This applies round r . □
to the creation as well as to the validation of all messages including
block proposals, signatures, notarizations, random beacon shares, Proposition 9.10 (Maximal Progress). Suppose BlockTime ≥
and random beacon outputs. As a consequence, for example, when ∆. Then the round number of any honest replica increases at most
a replica i receives a random beacon output ξ r at time t then it every BlockTime − ∆. Moreover, at any point in time, the difference
broadcasts its block proposal for round r at the same time t. Or, between the round numbers of two honest replicas can be at most 1.
when a random beacon member i receives a notarization zr for
round r at time t then i broadcasts its random beacon share for Proof. From (9.3) and (9.5) together we get:
round r + 1 immediately at the same time t. τ̄ (r ) + (BlockTime − ∆) ≤ τ ∗ (r + 1).
¯
Definition 9.5. Let τi (A) denote the time at which replica i sees This implies both statements. □
event A where A is one of the following: a random beacon output ξ r ,
a block proposal Br , or a notarization zr . We set τi (r ) := τi (zr −1 ) Corollary 9.11 (Safe Broadcast). Suppose BlockTime ≥ ∆.
where zr −1 is the first notarization for round r − 1 that i receives. For all rounds r and any round-r event A under Def. 9.4a) we have:
Thus, τi (r ) is the time when replica i enters round r . To study τ (A) ≤ τ (r ) + (BlockTime − ∆) =⇒ τ̄ (A) ≤ τ (r ) + BlockTime.
when the first honest or last honest replica sees an event, we define: ¯ ¯ ¯
(9.6)
Definition 9.6. The interpretation is that if a round-r event is broadcasted by
τ (A) := min τi (A), τ̄ (A) := max τi (A). τ (r )+(BlockTime−∆) then it is guaranteed to saturate the network,
¯ i honest i honest ¯
and this happens by τ (r ) + BlockTime.
For example, τ (r ) is the time when the first honest replica enters ¯
¯
round r and τ̄ (r ) is the time when the last honest replica enters Proof. From τ (A) ≤ τ (r ) + (BlockTime − ∆) we conclude
round r . Finally, it is also of interest when an event can first be seen ¯ ¯
(9.5)
or constructed by the adversary. Therefore, we define: τ (A) + ∆ ≤ τ (r ) + BlockTime ≤ τ (r + 1).
¯ ¯ ¯
Definition 9.7. Thus, by (9.4),
τ ∗ (A) := min τi (A).
¯ i τ̄ (A) ≤ τ (A) + ∆ ≤ τ (r ) + BlockTime.
¯ ¯
For example, τ (ξ r ) is the earliest time that the adversary can
∗
¯ □
construct the random beacon output ξ r .
We will prove in Cor. 9.16 below that the protocol makes contin- 9.2.3 Normal Operation.
uous progress, i.e. that all values τi (r ) are finite. As the reader may
verify, the statements made in this section up until Cor. 9.16 also Lemma 9.12 (Beacon, "Slow" Bound). For all rounds r we have:
hold (trivially) in the case that any of the values τi (A) are infinite. τ̄ (ξ r ) ≤ τ (r ) + 2∆ (9.7)
¯
Lemma 9.8. For all rounds r we have:
Proof. Each honest random beacon member i broadcasts its
τ̄ (r ) ≤ τ (r ) + ∆ (9.3) random beacon share for ξ r at τi (r ) (cf. § 7.3.2). Thus, any other
¯
and, for any round-r event A under Def. 9.4a), honest replica will receive all honest random beacon shares for ξ r
τ (A) + ∆ ≤ τ (r + 1) =⇒ τ̄ (A) ≤ τ (A) + ∆ (9.4) by τ̄ (r ) + ∆ and thus will recover ξ r by that time, i.e.
¯ ¯ ¯
Proof. Let i be an honest replica and let zr −1 be a notarization τ̄ (ξ r ) ≤ τ̄ (r ) + ∆.
for round r − 1 such that τi (zr −1 ) = τ (r ). By Def. 9.4b), zr −1 is The assertion follows after applying (9.3). □
¯
relayed across the network and reaches any other honest replica j
by τi (r ) + ∆. This proves (9.3). We now assume BlockTime ≥ 3∆ for the rest of the subsection.
Now let A be any event that falls under the relay policy in The timing of events with BlockTime = 3∆ is illustrated in Fig. 9.
Def. 9.4a) for round r . If τ (A) + ∆ ≤ τ (r + 1) then the same ar-
¯ ¯ Lemma 9.13 (Block, "Slow" Bound). Suppose BlockTime ≥ 3∆.
gument applies. Indeed, the assumption means that all replicas
For each round r and each honest block proposal Br we have:
along the broadcast path will still be in round r , thus will relay A
according to Def. 9.4a). This proves (9.4). □ τ̄ (Br ) ≤ τ (r ) + BlockTime. (9.8)
¯
13
Technology Overviews, Jan. 23, 2018, DFINITY Stiftung Timo Hanke, Mahnush Movahedi and Dominic Williams

i starts the waiting i is ready to Proof. Set x 0 := τ (r ) + BlockTime. Let Br be the unique pro-
¯
period of Alg. 1 sign posal made by i for round r . By Lemma 9.13, all honest notary
BlockTime = 3∆
Replica i members receive Br by time x 0 .
zr
−1 ξr For each time x ≥ x 0 , we consider the set S x of valid block
zr
−1 proposals for round r that have been received by at least one honest
Random Beacon

r
B
ξr replica. More formally, S x consists of those valid round-r proposals
z r−
ξr B that satisfy τ (B) ≤ x. For example, Br ∈ S x 0 . We then define
1
Block Makers ¯
Br
f (x) := min{rk B | B ∈ S x }.
Replica j For example, f (x 0 ) ≤ d because Br has rank d.
τ (r ) = τi (r ) ∆ ∆ ∆
For x ≥ x 0 , the function f has values in the non-negative integers
¯
and is monotonically decreasing. Since f (x 0 ) ≤ d, it follows that
Figure 9: Events Timings. Let replica i be the first honest replica to there is a time x 0 ≤ x 1 ≤ x 0 + d∆ such that f (x 1 ) = f (x 1 + ∆).
enter round r , at time τi (r ) = τ (r ), upon receipt (or construction) of (Otherwise, if f (x + ∆) ≤ f (x) − 1 for all x 0 ≤ x ≤ x 0 + d∆ then
¯
a notarization z r −1 for round r − 1. Let j be any other honest replica f (x 0 + (d + 1)∆) < 0, a contradiction.)
for illustration. Replica i broadcasts z r −1 to everyone where it arrives We claim τ (r + 1) ≤ x 1 + 2∆. This proves (9.9) since
before τ (r ) + ∆. Thus, all honest replicas start their round r before ¯
¯
τ (r ) + ∆. Immediately after starting round r , all honest random bea- x 1 + 2∆ ≤ x 0 + (d + 2)∆
¯
con members create and broadcast their random beacon share to ev- = τ (r ) + BlockTime + (d + 2)∆.
eryone where it arrives before τ (r ) + 2∆. Immediately after receiving ¯
¯
ξ r , each honest block maker broadcasts its block proposals B r to ev- If a notarization for a block different from B arrives at any replica
eryone where it arrives before τ (r ) + 3∆. Replica i finishes its waiting before x 1 + 2∆ then the claim is already proven. We assume w.l.o.g.
¯
period at τi (r )+BlockTime = τ (r )+3∆ and proceeds to sign the highest that this is not the case. Note that under this assumption, (9.4)
¯
priority proposal B r in its view. Replica j finishes its waiting period applies to the events B and any signature under B.
later, at τ j (r ) + BlockTime, and does the same. Let B ∈ S x 1 with rk B = f (x 1 ). Since B ∈ S x 1 we have τ (B) ≤ x 1 .
¯
Hence, by (9.4),
τ̄ (B) ≤ x 1 + ∆.
Proof. Since Br is proposed by an honest replica i, it is broad- The facts τ̄ (B) ≤ x 1 + ∆ and rk B = f (x 1 + ∆) together mean that
casted immediately when i receives ξ r . (Note that we generally B has minimal rank in every honest replica’s view at time x 1 + ∆.
ignore processing times throughout the section, including the block Also, x 1 + ∆ ≥ τ (r ) + BlockTime + ∆ ≥ τ̄ (r ) + BlockTime, i.e. x 1 + ∆
creation time.) This means τ (Br ) ≤ τ̄ (ξ r ), hence ¯
is past the BlockTime waiting period for every honest replica. Thus,
¯
(9.7) all honest replicas have broadcasted a signature for B by x 1 + ∆.
τ (Br ) ≤ τ̄ (ξ r ) ≤ τ (r ) + 2∆ ≤ τ (r ) + (BlockTime − ∆). By (9.4), all honest replicas receive f + 1 signatures by x 1 + 2∆, i.e.
¯ ¯ ¯
τ̄ (r + 1) ≤ x 1 + 2∆. □
The assertion follows from Cor. 9.11 for A = Br . □
We remark without proof: In the case d = 0 the bound can be
Proposition 9.14 (Normal Operation). Suppose BlockTime ≥ improved to τ (r + 1) ≤ τ (r ) + BlockTime + ∆. The resulting bounds
¯ ¯
3∆. If the highest priority replica in round r is honest, then round r are then strict for all d.
has normal operation. As a corollary, by induction, we conclude that the protocol makes
continuous progress:
Proof. Let i be the highest priority replica of round r and sup-
Corollary 9.16. Suppose BlockTime ≥ 3∆. For all rounds r and
pose i is honest. Then i proposes exactly one block Br for round r .
all honest replicas i, τi (r ) is finite.
Lemma 9.13 implies that for each honest notary member j we have
τ j (Br ) ≤ τ j (r ) + BlockTime. By Alg. 1, replica j waits BlockTime
9.3 Near-Instant Finality
after entering round r and then signs Br and only Br because Br ’s
proposer i has the highest possible priority. Finality is provided by Alg. 1. This section first proves the correct-
Since notarization requires the participation of at least one hon- ness of this algorithm and then shows as the main theorem that
est replica, and all honest replicas sign only Br , Br is the only block finality is achieved quickly under normal operation.
that can possibly get notarized. In other words, round r can only be Recall:
ended by a notarization of Br , which guarantees that the signatures • According to the relay policy the notarization will reach
under Br saturate the network and Br indeed gets notarized. □ all other honest replicas.
• As was stated in (9.2), if a block is honestly signed then the
9.2.4 Minimal Progress. notarized previous block will saturate the network.
• if a block is honestly signed then nt B is re-broadcasted
Proposition 9.15 (Minimal Progress). Suppose BlockTime ≥ under the policy Def. 9.4b).
3∆. Suppose that in a given round r the replica i with πr (i) = d is
honest. Then Lemma 9.17. Suppose zr −1 is a referenced notarization for round
r − 1. Then,
τ (r + 1) ≤ τ (r ) + BlockTime + (d + 2)∆. (9.9) τ̄ (zr −1 ) ≤ τ̄ (r + 1) + ∆. (9.10)
¯ ¯
14
DFINITY Consensus Technology Overviews, Jan. 23, 2018, DFINITY Stiftung

Proof. Let Br be a notarized block with nt Br = zr −1 . Since Br c) Quality with parameter l and µ. Out of any l consecutive blocks
received an honest signature, we have τ (Br ) ≤ τ̄ (r + 1). Since Br from the finalized chain of an honest replica, at least µl blocks
¯
contains zr −1 , we have τ (zr −1 ) ≤ τ (Br ). This implies τ̄ (zr −1 ) ≤ were proposed by an honest replica.
¯ ¯
τ (zr −1 ) + ∆ ≤ τ̄ (r + 1) + ∆. □
¯ Proposition 9.22. Persistence follows from the properties of chain
Theorem 9.18 (Correctness of Finalization). Suppose T ≥ consistency and chain growth.
2∆. For every honest replica, before the replica executes Finalize(h) Proof. Suppose a transaction is included in the finalized chain
in Algorithm 2 it has received all notarizations for round h that can of one honest replica i, say in the block at round r . Given any other
get referenced. honest replica j, by the growth property, j’s finalized chain will
The assertion is precisely the correctness assumption (6.1). eventually reach length r as well. At that point, the consistency
property guarantees that j’s block at round r is identical to the one
Proof. Suppose zr −1 is a referenced notarization for round r −1. in i’s finalized chain. □
From (9.10) and (9.3), we get
Proposition 9.23. Liveness follows from the properties of chain
τ̄ (zr −1 ) ≤ τ (r + 1) + 2∆. (9.11) quality and chain growth.
¯
In particular, for any honest replica i, Proof. A transaction originating from an honest replica is picked
τi (zr −1 ) ≤ τi (r + 1) + 2∆. (9.12) up by all other honest parties and included in their block propos-
als.10 The growth property guarantees that the finalized chain will
This shows that any notarization for round r −1 that arrives at i after
eventually grow arbitrarily long. The chain quality property applies
τi (r +1)+2∆ cannot get referenced. Since Alg. 2 calls Finalize(r −1)
and guarantees that there will eventually be a block in the finalized
at time τi (r + 1) + T and T ≥ 2∆, this proves the claim. □
chain that was proposed by an honest replica. □
Corollary 9.19. Suppose BlockTime ≥ 2∆. Suppose zr −1 is a 9.4.1 Chain Growth.
referenced notarization for round r − 1. Then,
Proposition 9.24 (Chain Growth). Suppose BlockTime ≥ 3∆.
τ̄ (zr −1 ) ≤ τ (r + 2). (9.13) Accepting a failure probability of ρ, the Chain Growth property holds
¯
Proof. By (9.5), τ (r + 1) + BlockTime ≤ τ (r + 2). Hence, by with parameter k = ⌈− logβ ρ⌉.
¯ ¯
(9.11), τ̄ (zr −1 ) ≤ τ (r + 1) + 2∆ ≤ τ (r + 2). □ Proof. We first look at the property assuming normal operation
¯ ¯
in round r . In this case, the chain will be finalized up to and including
Provided that BlockTime ≥ 2∆, (9.13) provides an alternative
round r at the end of round r + 1 plus 2∆ according to Alg. 2. In
criteria for when to execute Finalize(r − 1) in Alg. 2 that does not
terms of round numbers, based on Proposition 9.10, each round
require T . Instead of waiting for T into round r + 1, the finalization
including round r + 2 takes at least BlockTime − ∆ > 2∆, thus at
procedure can simply wait for round r + 1 to end in the observer’s
the end of round r + 2, we can finalize round r so that the finalized
view.
chain will have length r + 1. This means the property holds with
Theorem 9.20 (Main Theorem). Under normal operation in k = 1.
round r , every transaction included in a block for round r is final Whenever the highest priority block maker for r is honest then
for an observer after two confirmations plus the maximum network round r has normal operation (Prop. 9.14). Thus, in general, normal
roundtrip time 2∆. operation happens with probability at least 1 − 1/β. Then, with
probability at least 1 − (1/β)k the property holds with parameter k.
Proof of Theorem 9.3. Suppose round r has normal operation, Thus, if we equate this probability with the minimal desired success
i.e. only one block Br gets notarized for round r . We assume the probability of 1 − ρ and solve for k we get k = ⌈− logβ ρ⌉. □
observer has chosen T = 2∆. At time T after seeing a notarization
for round r + 1, the observer will finalize round r . Since Nr (the 9.4.2 Chain Consistency.
bucket of all received notarized blocks for round r ) contains only
Proposition 9.25 (Chain Consistency). Suppose T ≥ 2∆. Sup-
Br , Br is appended to the final chain at this time. □
pose two honest replicas i, i ′ output the finalized chains C, C ′ upon
executing Finalize(h), Finalize(h ′ ), respectively. Then C ≤ C ′ or
9.4 Chain Properties C ′ ≤ C.
Recall that each replica at the end of each round has its own view
of an append-only finalized chain (cf. Alg. 2). We consider the Proof. Assume w.l.o.g h ′ ≤ h. Let Nh , Nh′ be the sets of Al-
following properties regarding state and content of the finalized gorithm 2 at the time when Finalize(h) is being executed by i, i ′ ,
chain C. respectively. Since h ′ ≤ h, by Prop. 6.1, C ′ ≤ C(Nh′ ). Let X be the
set of all round-h notarizations that can get referenced. Note that X
Definition 9.21 (Chain properties). is globally defined after all honest replicas have ended their round
a) Growth with parameter k. Each honest replica’s finalized chain h + 1 (though X is not known to anyone). By Thm. 9.18 (correctness
at the end of their round r has length ≥ r − k. 10 There may be reasons why a transaction can not be included in a block proposal
b) Consistency. If C, C ′ are the finalized chains of two honest parties, even if the proposer is honest. Those reasons, such as limited block space, are not part
taken at any point in time, then C is a prefix of C ′ or vice versa. of our definition of "liveness" and are not considered here.
15
Technology Overviews, Jan. 23, 2018, DFINITY Stiftung Timo Hanke, Mahnush Movahedi and Dominic Williams

of finalization), we have X ⊆ Nh , Nh′ . The set X is furthermore [7] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Advances in Cryptology —
non-empty because Finalize(h) is only called once some round-h EUROCRYPT ’99: International Conference on the Theory and Application of Cryp-
tographic Techniques Prague, Czech Republic, May 2–6, 1999 Proceedings, chapter
notarizations are actually referenced. Hence, C = C(Nh ) ≤ C(X ) Secure Distributed Key Generation for Discrete-Log Based Cryptosystems, pages
and C ′ ≤ C(Nh′ ) ≤ C(X ). The fact that C, C ′ are prefixes of a 295–310. Springer Berlin Heidelberg, Berlin, Heidelberg, 1999.
[8] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich. Algorand: Scaling
common chain proves the claim. □ Byzantine Agreements for Cryptocurrencies.
[9] D. E. Knuth. The art of computer programming. volume 1: Fundamental algo-
9.4.3 Chain Quality. Whether the highest priority replica in rithms. volume 2: Seminumerical algorithms. Bull. Amer. Math. Soc, 1997.
round r is adversarial can be modelled as a Bernoulli trial X r with [10] B. Libert, M. Joye, and M. Yung. Born and raised distributively: Fully distributed
success probability f (U )/|U |. Since the adversary cannot bias the non-interactive adaptively-secure threshold signatures with short shares. Theo-
retical Computer Science, 645:1–24, 2016.
random beacon, the trials X r for different r are independent. There- [11] S. Mitsunari. Barreto-Naehrig curve implementation and BLS. https://github.
fore, an execution of the protocol comes with a Bernoulli process com/dfinity/bn, 2017.
X 1 , X 2 , . . . that models the success of the adversary in gaining pref-
erence on the proposed block.
Following Garay et.al. [5], we define an execution of the protocol
as typical if the Bernoulli process does not deviate too much from its
expectation. For any set of rounds S we define the random variable
X (S) := i ∈S X i .
Í

Definition 9.26. An execution is (ϵ, η)-typical if, for any set S of

consecutive rounds with |S | ≥ η,
X (S) − E(X (S))
<ϵ
E(X (S))
The idea is that a) we can guarantee chain quality in all typical
executions, and b) any execution is typical with all but negligible
probability. In practice, "negligible probability" is defined by the
security parameter κ and the parameters ϵ, η are a function of κ.
Proposition 9.27 (Chain Quality). Suppose BlockTime ≥ 3∆.
In a (ϵ, η)-typical execution the Chain Quality property holds for
µ = (1 − 1/β)(1 − ϵ) and l = η.
Proof. Whenever X r = 0 there will be only one notarization
for r (Prop. 9.14). This notarization will be for the honest proposer’s
block, so the honest proposal is guaranteed to be in the finalized
chain. Therefore the chain quality is at least (1 − 1/β)(1 − ϵ) for a
(ϵ, η)-typical execution if l ≥ η. □

ACKNOWLEDGMENTS
We would like to thank Robert Lauko, Marko Vukolic, Arthur Ger-
vais, Bryan Ford, Ewa Syta, Philipp Jovanovic, Eleftherios Kokoris,
Cristina Basescu and Nicolas Gailly for helpful comments and dis-
cussions.

REFERENCES
[1] RANDAO: A DAO working as RNG of Ethereum. https://github.com/randao/
randao, 2017.
[2] J.-L. Beuchat, J. E. González-Díaz, S. Mitsunari, E. Okamoto, F. Rodríguez-
Henríquez, and T. Teruya. High-Speed Software Implementation of the Optimal
Ate Pairing over Barreto-Naehrig Curves. Pairing, 6487:21–39, 2010.
[3] D. Boneh, B. Lynn, and H. Shacham. Short Signatures from the Weil Pairing. In
Proceedings of the 7th International Conference on the Theory and Application of
Cryptology and Information Security: Advances in Cryptology, ASIACRYPT ’01,
pages 514–532, London, UK, UK, 2001. Springer-Verlag.
[4] I. Eyal and E. G. Sirer. Majority is not enough: Bitcoin mining is vulnerable.
In International conference on financial cryptography and data security, pages
436–454. Springer, 2014.
[5] J. Garay, A. Kiayias, and N. Leonardos. The Bitcoin Backbone Protocol with
Chains of Variable Difficulty. In Annual International Cryptology Conference,
pages 291–323. Springer, 2017.
[6] R. Gennaro, S. Goldfeder, and A. Narayanan. Threshold-optimal DSA/ECDSA
signatures and an application to Bitcoin wallet security. In International Con-
ference on Applied Cryptography and Network Security, pages 156–174. Springer,
2016.
16