Difference between revisions of "IC consensus layer"

From Internet Computer Wiki
Jump to: navigation, search
m
Line 18: Line 18:
 
==Assumptions==
 
==Assumptions==
  
As discussed [[The Internet Computer for Computer Scientists|in the introduction]], we assume
+
As discussed [[The Internet Computer for Computer Scientists|in the introduction]], assume
 
* a subnet of <math>n</math> replicas, and
 
* a subnet of <math>n</math> replicas, and
 
* at most <math>f < n/3</math> of the replicas are faulty.
 
* at most <math>f < n/3</math> of the replicas are faulty.
Line 24: Line 24:
  
  
We assume that communication is <b>asynchronous</b>, with no <i>a priori</i>
+
Assume communication is <b>asynchronous</b>, with no <i>a priori</i>
 
bound on the delay of messages sent between replicas.
 
bound on the delay of messages sent between replicas.
 
In fact, the scheduling of message delivery may be completely under adversarial control.
 
In fact, the scheduling of message delivery may be completely under adversarial control.
 
The IC consensus protocol guarantees safety under this very weak communication assumption.
 
The IC consensus protocol guarantees safety under this very weak communication assumption.
However, to guarantee liveness, we need to assume a form of <b>partial synchrony</b>,
+
However, to guarantee liveness, a form of <b>partial synchrony</b> is needed,
 
which (roughly stated) says that the network will be periodically synchronous
 
which (roughly stated) says that the network will be periodically synchronous
 
for short intervals of time.
 
for short intervals of time.
In such intervals of synchrony, all undelivered    
+
In such intervals of synchrony, all undelivered messages will be delivered in less than time <math>\delta</math>,
messages will be delivered in less than time <math>\delta</math>,
 
 
for some fixed bound <math>\delta</math>.
 
for some fixed bound <math>\delta</math>.
The bound <math>\delta</math> does not have to be known in advance  
+
The bound <math>\delta</math> does not have to be known in advance (the protocol is initialized with a reasonable bound, but will dynamically adapt and increase this bound if it is too small).
(the protocol is initialized with a reasonable bound, but will dynamically  
+
Regardless of whether an asynchronous
adapt and increase this bound if it is too small).
+
or a partially synchronous network is assumed,
Regardless of whether we are assuming an asynchronous
+
it is assumed that every message sent from one honest
or a partially synchronous network,
 
we assume that every message sent from one honest
 
 
party to another will <i>eventually</i> be delivered.
 
party to another will <i>eventually</i> be delivered.
  
Line 214: Line 211:
 
continues to grow (and this holds only assuming asynchronous eventual delivery,
 
continues to grow (and this holds only assuming asynchronous eventual delivery,
 
and not partial synchrony).
 
and not partial synchrony).
We prove the growth invariant
+
The proof of growth invariant can be found [[#Proof of growth invariant|below]].
[[#Proof of growth invariant|below]].
 
  
  
Line 223: Line 219:
 
There may be more than one  
 
There may be more than one  
 
notarized block at a given height <math>h</math>.
 
notarized block at a given height <math>h</math>.
However, if a block is <b>finalized</b>, then we can be sure that there
+
However, if a block is <b>finalized</b>, then it is sure that there
 
is no other notarized block at height <math>h</math>.  
 
is no other notarized block at height <math>h</math>.  
 
Let us call this the <b>safety invariant</b>.
 
Let us call this the <b>safety invariant</b>.
Line 249: Line 245:
 
to all other replicas.
 
to all other replicas.
  
We prove the safety invariant
+
The proof of safety invariant can be found [[#Proof of safety invariant|below]].
[[#Proof of safety invariant|below]].
 
 
One consequence of the safety invariant is the following.
 
One consequence of the safety invariant is the following.
 
Suppose two blocks <math>B</math> and <math>B'</math> are finalized,
 
Suppose two blocks <math>B</math> and <math>B'</math> are finalized,
Line 295: Line 290:
 
by the leader in that round will be finalized.
 
by the leader in that round will be finalized.
 
Let us call this the <b>liveness invariant</b>.
 
Let us call this the <b>liveness invariant</b>.
We prove this
+
The proof of liveness invariant can be found [[#Proof of liveness invariant|below]].
[[#Proof of liveness invariant|below]].
 
  
 
==An example==
 
==An example==
Line 311: Line 305:
 
As one can see, there can be more than one notarized block
 
As one can see, there can be more than one notarized block
 
in the tree at a given height.
 
in the tree at a given height.
For example, at height 31, we see there are two notarized blocks,
+
For example, at height 31, note there are two notarized blocks,
 
proposed by block makers of rank 1 and 2.
 
proposed by block makers of rank 1 and 2.
 
The same thing happens at height 34.
 
The same thing happens at height 34.
We can also see that the block at height 36 is also explicitly
+
Note that the block at height 36 is also explicitly
 
finalized, as indicated by the diamond-F symbol.
 
finalized, as indicated by the diamond-F symbol.
 
This means that <math>n-f</math> distinct replicas supported this block's finalization,
 
This means that <math>n-f</math> distinct replicas supported this block's finalization,
Line 328: Line 322:
 
==Putting it all together==
 
==Putting it all together==
  
We now describe in more detail how the protocol works;
+
This section describes in more detail how the protocol works;
specifically, we describe more precisely when a replica will
+
specifically, this section describes more precisely when a replica will
 
propose a block and when a replica will support the notarization of a block.  
 
propose a block and when a replica will support the notarization of a block.  
 
A given replica <math>P</math> will record the time at which it  
 
A given replica <math>P</math> will record the time at which it  
Line 418: Line 412:
 
===Proof of liveness invariant===
 
===Proof of liveness invariant===
  
We say that the network is  
+
It is said that the network is <b><math>\delta</math>-synchronous at time <math>t</math></b> if  
<b><math>\delta</math>-synchronous at time <math>t</math></b> if  
 
 
if all messages that have been sent by honest replicas at or before time <math>t</math> arrive at their destinations before time <math>t+\delta</math>.
 
if all messages that have been sent by honest replicas at or before time <math>t</math> arrive at their destinations before time <math>t+\delta</math>.
  
Line 425: Line 418:
 
Suppose that <math>\Delta_\mathrm{n}(1) \ge \Delta_\mathrm{m}(0) + 2\delta</math>.
 
Suppose that <math>\Delta_\mathrm{n}(1) \ge \Delta_\mathrm{m}(0) + 2\delta</math>.
 
Also  
 
Also  
suppose that in a given round <math>h</math>, we have
+
suppose that in a given round <math>h</math>,  
 
* the leader <math>P</math> in round <math>h</math> is honest,
 
* the leader <math>P</math> in round <math>h</math> is honest,
 
* the first honest replica <math>Q</math> to enter round <math>h</math> does so at time <math>t</math>, and
 
* the first honest replica <math>Q</math> to enter round <math>h</math> does so at time <math>t</math>, and
Line 440: Line 433:
 
===Growth latency===
 
===Growth latency===
  
Under a partial synchrony assumption, we can also formulate and prove
+
Under a partial synchrony assumption, a quantitative version of the growth invariant can also be formulated and proven.
a quantitative version of the growth invariant.
 
 
For simplicity, assume that the delay functions are defined
 
For simplicity, assume that the delay functions are defined
 
as recommended above: <math>\Delta_\textrm{m}(r) = 2 \delta r</math>
 
as recommended above: <math>\Delta_\textrm{m}(r) = 2 \delta r</math>
Line 464: Line 456:
  
 
Also, while replicas do not explicitly adjust the delay function  
 
Also, while replicas do not explicitly adjust the delay function  
<math>\Delta_\textrm{p}</math>, we can mathematically model local clock drift  
+
<math>\Delta_\textrm{p}</math>, local clock drift can be mathematically modeled by locally adjusting both delay functions.
by locally adjusting both delay functions.
 
  
 
Thus, there are many delay fucntions,
 
Thus, there are many delay fucntions,
Line 483: Line 474:
  
 
Another property that is important in consensus protocols is <b>fairness</b>.
 
Another property that is important in consensus protocols is <b>fairness</b>.
Rather than give a general definition, we simply observe that  
+
Rather than give a general definition, observe that  
 
the liveness invariant also implies a useful fairness property.
 
the liveness invariant also implies a useful fairness property.
 
Recall that the liveness invariant basically says that in any round
 
Recall that the liveness invariant basically says that in any round

Revision as of 12:54, 27 February 2023

The job of the consensus layer of the IC is to order transaction requests so that all replicas in a subnet will process such requests in the same order. There are many protocols in the literature for this problem. The IC uses a new consensus protocol, which is described here at a high level. For more details, see the paper https://eprint.iacr.org/2021/632 (in particular, Protocol ICC1 in that paper).

Any secure consensus protocol should guarantee two properties, which (roughly stated) are:

  • safety: all replicas in fact agree on the same ordering of transaction requests, and
  • liveness: all replicas should make steady progress.

The paper https://eprint.iacr.org/2021/632 proves that the IC consensus protocol satisfies both of these properties.

The IC consensus protocol is designed to be

  • simple,
  • robust (performance degrades gracefully when some replicas are crashed or malicious), and
  • optimistically responsive (when certain optimistic conditions are met, the protocol may proceed at the pace of the actual network delay, rather than some worst-case upper bound on the network delay).

Assumptions

As discussed in the introduction, assume

  • a subnet of [math]\displaystyle{ n }[/math] replicas, and
  • at most [math]\displaystyle{ f \lt n/3 }[/math] of the replicas are faulty.

Faulty replicas may exhibit arbitrary, malicious (i.e., Byzantine) behavior.


Assume communication is asynchronous, with no a priori bound on the delay of messages sent between replicas. In fact, the scheduling of message delivery may be completely under adversarial control. The IC consensus protocol guarantees safety under this very weak communication assumption. However, to guarantee liveness, a form of partial synchrony is needed, which (roughly stated) says that the network will be periodically synchronous for short intervals of time. In such intervals of synchrony, all undelivered messages will be delivered in less than time [math]\displaystyle{ \delta }[/math], for some fixed bound [math]\displaystyle{ \delta }[/math]. The bound [math]\displaystyle{ \delta }[/math] does not have to be known in advance (the protocol is initialized with a reasonable bound, but will dynamically adapt and increase this bound if it is too small). Regardless of whether an asynchronous or a partially synchronous network is assumed, it is assumed that every message sent from one honest party to another will eventually be delivered.

Protocol overview

Like a number of consensus protocols, the IC consensus protocol is based on a blockchain. As the protocol progresses, a tree of blocks is grown, starting from a special genesis block that is the root of the tree. Each non-genesis block in the tree contains (among other things) a payload, consisting of a sequence of transaction requests, and a hash of the block's parent in the tree. The honest replicas have a consistent view of this tree: while each replica may have a different, partial view of this tree, all the replicas have a view of the same tree. In addition, as the protocol progresses, there is always a path of finalized blocks in this tree. Again, the honest replicas have a consistent view of this path: while each replica may have a different, partial view of this path, all the parties have a view of the same path. The transaction requests in the payloads of the blocks along this path are the ordered transaction requests will be processed by the execution layer of the Internet Computer.

The protocol proceeds in rounds. In round [math]\displaystyle{ h }[/math] of the protocol, one or more blocks of height [math]\displaystyle{ h }[/math] are added to the tree. That is, the blocks added in round [math]\displaystyle{ h }[/math] are always at a distance of exactly [math]\displaystyle{ h }[/math] from the root. In each round, a pseudo-random process is used to assign each replica a unique rank, which is an integer in the range [math]\displaystyle{ 0,\ldots,n-1 }[/math]. This pseudo-random process is implemented using a random beacon (see below). The party of lowest rank is the leader of that round. When the leader is honest and the network is synchronous, the leader will propose a block, which will be added to the tree; moreover, this will be the only block added to the tree in this round and it will extend the finalized path. If the leader is not honest or the network is not synchronous, some other parties of higher rank may also propose blocks, and also have their blocks added to the tree. In any case, the logic of the protocol gives highest priority to the leader's proposed block and some block or blocks will be added to this tree in this round. Even if the protocol proceeds for a few rounds without extending the finalized path, the height of the tree will continue to grow with each round, so that when the finalized path is extended in round [math]\displaystyle{ h }[/math], the finalized path will be of length [math]\displaystyle{ h }[/math]. A consequence of this, even if the latency occasionally occasionally increases because of faulty replicas or unexpectedly high network latency, the throughput of the protocol remains essentially constant.


Public keys

To implement the protocol, each replica is associated with a public key for the BLS signature scheme, and each replica also holds the corresponding secret signing key. The association of replicas to public keys is maintained by the Network Nervous System (NNS) of the Internet Computer. These BLS signatures will be used to authenticate messages sent by replicas.

The protocol also uses the signature aggregation feature of BLS signatures, which allows many signatures on the same message to be aggregated into a compact multi-signature. The protocol will use these multi-signatures for notarizations and finalizations, which are aggregations of [math]\displaystyle{ n-f }[/math] signatures on messages of a certain form.

Random Beacon

In addition to BLS signatures and multi-signatures as discussed above, the protocol makes use of a BLS threshold signature scheme to implement the above-mentioned random beacon. The random beacon for height [math]\displaystyle{ h }[/math] is a [math]\displaystyle{ (f+1) }[/math]-threshold signature on a message unique to height [math]\displaystyle{ h }[/math]. In each round of the protocol, each replica broadcasts its share of the beacon for the next round, so that when the next round begins, all replicas should have enough shares to reconstruct the beacon for that round. As discussed above, the random beacon at height [math]\displaystyle{ h }[/math] is used to assign a pseudo-random rank to each replica that will be used in round [math]\displaystyle{ h }[/math] of the protocol. Because of the security properties of the threshold signature, an adversary will not be able to predict the ranking of the replicas more than one round in advance, and these rankings will effectively be as good as random. To set up such a threshold signature scheme, the Internet Computer runs a distributed key generation (DKG) protocol. There are many DKG protocols in the literature. The Internet Computer implements a new non-interactive DKG (NiDKG) protocol.


Block making

Each replica may at different points in time play the role of a block maker. As a block maker in round [math]\displaystyle{ h }[/math], the replica proposes a block [math]\displaystyle{ B }[/math] of height [math]\displaystyle{ h }[/math] that is to be a child of some block [math]\displaystyle{ B' }[/math] of height [math]\displaystyle{ h-1 }[/math] in the tree of blocks. To do this, the block maker first gathers together a payload consisting of all transaction requests it knows about (but not including those already included in payloads in blocks in the path through the tree ending at [math]\displaystyle{ B' }[/math]). The block [math]\displaystyle{ B }[/math] consists of

  • the payload,
  • the hash of [math]\displaystyle{ B' }[/math],
  • the rank of the block maker,
  • the height [math]\displaystyle{ h }[/math] of the block.

After forming the block [math]\displaystyle{ B }[/math], the block maker forms a block proposal, consisting of

  • the block [math]\displaystyle{ B }[/math],
  • the block maker's identity, and
  • the block maker's signature on [math]\displaystyle{ B }[/math].

A block maker will broadcast its block proposal to all other replicas.

Notarization

A block is effectively added to the tree of blocks when it becomes notarized. For a block to become notarized, [math]\displaystyle{ n-f }[/math] distinct replicas must support its notarization.

Given a proposed block [math]\displaystyle{ B }[/math] at height [math]\displaystyle{ h }[/math], a replica will determine if the proposal is valid, which means that [math]\displaystyle{ B }[/math] has the syntactic form described above. In particular, [math]\displaystyle{ B }[/math] should contain the hash of a block [math]\displaystyle{ B' }[/math] of height [math]\displaystyle{ h' }[/math] that is already in the tree of blocks (i.e., already notarized). In addition, the payload of [math]\displaystyle{ B }[/math] must satisfy certain conditions (in particulat, all of the transaction requests in the payload must satisfy various constraints, but these constraints are unrelated to consensus). Also, the rank of the block maker (as recorded in the block [math]\displaystyle{ B }[/math]) must match the rank assigned in round [math]\displaystyle{ h }[/math] by the random beacon to the replica that proposed the block (as recorded in the block proposal) .

If the block is valid and certain other constraints hold, the replica will support the notarization of the block by broadcasting a notarization share for [math]\displaystyle{ B }[/math], consisting of

  • the hash of [math]\displaystyle{ B }[/math],
  • the height [math]\displaystyle{ h }[/math] of [math]\displaystyle{ B }[/math],
  • the identity of the supporting replica, and
  • the supporting replica's signature on a message comprising the hash of [math]\displaystyle{ B }[/math] and the height [math]\displaystyle{ h }[/math].

Any set of [math]\displaystyle{ n-f }[/math] notarization shares on [math]\displaystyle{ B }[/math] may be aggregated together to form a notarization for [math]\displaystyle{ B }[/math], consisting of

  • the hash of [math]\displaystyle{ B }[/math],
  • the height [math]\displaystyle{ h }[/math] of [math]\displaystyle{ B }[/math],
  • the set of identities of the [math]\displaystyle{ n-f }[/math] supporting replicas,
  • an aggregation of the [math]\displaystyle{ n-f }[/math] signatures on the message comprising the hash of [math]\displaystyle{ B }[/math] and the height [math]\displaystyle{ h }[/math].

As soon as a replica obtains a notarized block of height [math]\displaystyle{ h }[/math], it will finish round [math]\displaystyle{ h }[/math], and will subsequently not support the notarization of any other blocks at height [math]\displaystyle{ h }[/math]. At this point in time, such a replica will also relay this notarization to all other replicas. Note that this replica may have obtained the notarization either by (1) receiving it from another replica, or (2) aggregating [math]\displaystyle{ n-f }[/math] notarization shares that it has received.


The growth invariant states that each honest replica will eventually complete each round and start the next, so that the tree of notarized blocks continues to grow (and this holds only assuming asynchronous eventual delivery, and not partial synchrony). The proof of growth invariant can be found below.


Finalization

There may be more than one notarized block at a given height [math]\displaystyle{ h }[/math]. However, if a block is finalized, then it is sure that there is no other notarized block at height [math]\displaystyle{ h }[/math]. Let us call this the safety invariant.

For a block to become finalized, [math]\displaystyle{ n-f }[/math] distinct replicas must support its finalization. Recall that round [math]\displaystyle{ h }[/math] ends for a replica when it obtains a notarized block [math]\displaystyle{ B }[/math] of height [math]\displaystyle{ h }[/math]. At that point in time, such a replica will check if it supported the notarization of any block at height [math]\displaystyle{ h }[/math] other than block [math]\displaystyle{ B }[/math] (it may or may not have supported the notarization of [math]\displaystyle{ B }[/math] itself). If not, the replica will support the finalization of [math]\displaystyle{ B }[/math] by broadcasting a finalization share for [math]\displaystyle{ B }[/math]. A finalization share has exactly the same format as a notarization share (but is tagged in such a way notarization shares and finalization shares cannot be confused with one another). Any set of [math]\displaystyle{ n-f }[/math] finalization shares on [math]\displaystyle{ B }[/math] may be aggregated together to form a finalization for [math]\displaystyle{ B }[/math], which has exactly the same format as a notarization (but again, is appropriately tagged). Any replica that obtains a finalized block will broadcast the finalization to all other replicas.

The proof of safety invariant can be found below. One consequence of the safety invariant is the following. Suppose two blocks [math]\displaystyle{ B }[/math] and [math]\displaystyle{ B' }[/math] are finalized, where [math]\displaystyle{ B }[/math] has height [math]\displaystyle{ h }[/math], [math]\displaystyle{ B' }[/math] has height [math]\displaystyle{ h'\le h }[/math]. Then the safety invariant implies that the path in the tree of notarized blocks ending at [math]\displaystyle{ B' }[/math] is a prefix of the path ending at [math]\displaystyle{ B }[/math] (if not, then there would be two notarized blocks at height [math]\displaystyle{ h' }[/math], contradicting the finalization invariant). Thus, whenever a replica sees a finalized block [math]\displaystyle{ B }[/math], it may view all ancestors of [math]\displaystyle{ B }[/math] as being implicitly finalized, and because of the safety invariant, the safety property is guaranteed to hold for these (explicitly and implicitly) finalized blocks.


Delay functions

The protocol makes use of two delay functions, [math]\displaystyle{ \Delta_\textrm{m} }[/math] and [math]\displaystyle{ \Delta_\textrm{n} }[/math], which control the timing of block making and notarization activity. Both of these functions map the rank [math]\displaystyle{ r }[/math] of the proposing replica no a nonnegative delay amount, and it is assumed that each function is monotonely increasing in [math]\displaystyle{ r }[/math], and that [math]\displaystyle{ \Delta_\textrm{m}(r) \le \Delta_\textrm{n}(r) }[/math] for all [math]\displaystyle{ r = 0, \ldots, n-1 }[/math]. The recommended definition of these functions is [math]\displaystyle{ \Delta_\textrm{m}(r) = 2 \delta r }[/math] and [math]\displaystyle{ \Delta_\textrm{n}(r) = 2 \delta r + \epsilon }[/math], where [math]\displaystyle{ \delta }[/math] is an upper bound on the time to deliver messages from one honest replica to another, and [math]\displaystyle{ \epsilon \ge 0 }[/math] is a "governor" to keep the protocol from running too fast. With these definitions, liveness will be ensured in those rounds in which (1) the leader is honest, and (2) messages really are delivered between honest parties within time [math]\displaystyle{ \delta }[/math]. Indeed, if (1) and (2) both hold in a given round, then the block proposed by the leader in that round will be finalized. Let us call this the liveness invariant. The proof of liveness invariant can be found below.

An example

Consensus-example.png

The figure above illustrates a block tree. Each block is labeled with its height (30, 31, 32, ...) and the rank of its block maker. The figure also shows that each block in the tree is notarized, as indicated by the diamond-N symbol. This means that for each notarized block in the tree, at least [math]\displaystyle{ n-f }[/math] distinct replicas supported its notarization. As one can see, there can be more than one notarized block in the tree at a given height. For example, at height 31, note there are two notarized blocks, proposed by block makers of rank 1 and 2. The same thing happens at height 34. Note that the block at height 36 is also explicitly finalized, as indicated by the diamond-F symbol. This means that [math]\displaystyle{ n-f }[/math] distinct replicas supported this block's finalization, which means that these replicas (or at least, the honest replicas among these) did not support the notarization of any other block. All of the ancestors of this block, which are shaded gray, are considered implicitly finalized.



Putting it all together

This section describes in more detail how the protocol works; specifically, this section describes more precisely when a replica will propose a block and when a replica will support the notarization of a block. A given replica [math]\displaystyle{ P }[/math] will record the time at which it enters a given round [math]\displaystyle{ h }[/math], which happens when it has obtained (1) some notarization for a block of height [math]\displaystyle{ h-1 }[/math], and (2) the random beacon for round [math]\displaystyle{ h }[/math]. Since the random beacon for round [math]\displaystyle{ h }[/math] has been determined, [math]\displaystyle{ P }[/math] can determine its own rank [math]\displaystyle{ r_P }[/math], as well as the rank [math]\displaystyle{ r_Q }[/math] of each other replica [math]\displaystyle{ Q }[/math] for round [math]\displaystyle{ h }[/math].

Random beacon details

As soon as a replica enters round [math]\displaystyle{ h }[/math], it will generate and broadcast its share of the random beacon at round [math]\displaystyle{ h+1 }[/math].

Block making details

Replica [math]\displaystyle{ P }[/math] will only propose its own block [math]\displaystyle{ B_P }[/math] provided (1) at least [math]\displaystyle{ \Delta_\textrm{m}(r_P) }[/math] time units have passed since the beginning of the round, and (2) there is no valid lower ranked block currently seen by [math]\displaystyle{ P }[/math].

Note that since [math]\displaystyle{ P }[/math] is guaranteed to have a notarized block of height [math]\displaystyle{ h-1 }[/math] when it enters round [math]\displaystyle{ h }[/math], it can make its proposed block a child of this notarized block (or any other notarized block of height [math]\displaystyle{ h-1 }[/math] that it may have). Also note that when [math]\displaystyle{ P }[/math] broadcasts its proposal for [math]\displaystyle{ B_P }[/math], it must also ensure that it also has relayed the notarization of [math]\displaystyle{ B_P }[/math]'s parent to all replicas.

Suppose a replica [math]\displaystyle{ Q }[/math] sees a valid block proposal from a replica [math]\displaystyle{ P }[/math] of rank [math]\displaystyle{ r_P \lt r_Q }[/math] such that (1) at least [math]\displaystyle{ \Delta_\textrm{m}(r_P) }[/math] time units have passed since the beginning of the round, and (2) there is no block of rank less than [math]\displaystyle{ r_P }[/math] currently seen by [math]\displaystyle{ Q }[/math]. Then at this point in time, if it has not already done so, [math]\displaystyle{ Q }[/math] will relay this block proposal (along with the notarization of the proposed block's parent) to all other replicas.

Notarization details

Replica [math]\displaystyle{ P }[/math] will support the notarization of a valid block [math]\displaystyle{ B_Q }[/math] proposed by a replica [math]\displaystyle{ Q }[/math] of rank [math]\displaystyle{ r_Q }[/math] provided (1) at least [math]\displaystyle{ \Delta_\textrm{n}(r_Q) }[/math] time units have passed since the beginning of the round, and (2) there is no block of rank less than [math]\displaystyle{ r_Q }[/math] currently seen by [math]\displaystyle{ P }[/math].

Proof of growth invariant

The growth invariant states that each honest replica will eventually complete each round and start the next. Assume that all honest replicas have started round [math]\displaystyle{ h }[/math]. Let [math]\displaystyle{ r^* }[/math] be the rank of the lowest ranked honest replica [math]\displaystyle{ P^* }[/math] in round [math]\displaystyle{ h }[/math]. Eventually, [math]\displaystyle{ P^* }[/math] will either (1) propose its own block, or (2) relay a valid block proposed by a lower ranked replica. In either case, some block must eventually be supported by all honest replicas, which means that some block will become notarized and all honest replicas will finish round [math]\displaystyle{ h }[/math]. All honest replicas will also receive the shares needed to construct the random beacon for round [math]\displaystyle{ h+1 }[/math], and so will start round [math]\displaystyle{ h+1 }[/math].


Proof of safety invariant

The safety invariant states that if a block is finalized in a given round, then no other block may be notarized in that round. Here is a proof of the safety invariant:

  1. Suppose that the number of corrupt parties is exactly [math]\displaystyle{ f^* \le f \lt n/3 }[/math].
  2. If a block [math]\displaystyle{ B }[/math] is finalized, then its finalization must have been supported by a set [math]\displaystyle{ S }[/math] of at least [math]\displaystyle{ n-f-f^* }[/math] honest replicas (by the security property for aggregate signatures).
  3. Suppose (by way of contradction) that another block [math]\displaystyle{ B' \ne B }[/math] were notarized. Then its notarization must have been supported by a set [math]\displaystyle{ S' }[/math] of at least [math]\displaystyle{ n-f-f^* }[/math] honest replicas (again, by the security property for aggregate signatures).
  4. The sets [math]\displaystyle{ S }[/math] and [math]\displaystyle{ S' }[/math] are disjoint (by the finalization logic).
  5. Therefore, [math]\displaystyle{ n-f^* \ge |S \cup S'| = |S| + |S'| \ge 2 (n-f-f^*) }[/math], which implies [math]\displaystyle{ n \le 3f }[/math], a contradiction.

Proof of liveness invariant

It is said that the network is [math]\displaystyle{ \delta }[/math]-synchronous at time [math]\displaystyle{ t }[/math] if if all messages that have been sent by honest replicas at or before time [math]\displaystyle{ t }[/math] arrive at their destinations before time [math]\displaystyle{ t+\delta }[/math].

The liveness invariant may be stated as follows. Suppose that [math]\displaystyle{ \Delta_\mathrm{n}(1) \ge \Delta_\mathrm{m}(0) + 2\delta }[/math]. Also suppose that in a given round [math]\displaystyle{ h }[/math],

  • the leader [math]\displaystyle{ P }[/math] in round [math]\displaystyle{ h }[/math] is honest,
  • the first honest replica [math]\displaystyle{ Q }[/math] to enter round [math]\displaystyle{ h }[/math] does so at time [math]\displaystyle{ t }[/math], and
  • the network is [math]\displaystyle{ \delta }[/math]-synchronous at times [math]\displaystyle{ t }[/math] and [math]\displaystyle{ t+\delta+\Delta_\mathrm{m}(0) }[/math].

Then the block proposed by [math]\displaystyle{ P }[/math] in round [math]\displaystyle{ h }[/math] will be finalized.

Here is a proof of the liveness invariant:

  1. Under partial synchrony at time [math]\displaystyle{ t }[/math], all honest replicas will enter round [math]\displaystyle{ h }[/math] before time [math]\displaystyle{ t+\delta }[/math] (the notarization that ended round [math]\displaystyle{ h-1 }[/math] for [math]\displaystyle{ Q }[/math], as well as the necessary round [math]\displaystyle{ h }[/math] random beacon shares, will arrive at all honest replicas before this time).
  2. The leader [math]\displaystyle{ P }[/math] in round [math]\displaystyle{ h }[/math] will propose a block [math]\displaystyle{ B }[/math] before time [math]\displaystyle{ t+\delta+\Delta_\mathrm{m}(0) }[/math], and again by partial synchrony, this block proposal will be delivered to all other replicas before time [math]\displaystyle{ t+2\delta+\Delta_\mathrm{m}(0) }[/math].
  3. Since [math]\displaystyle{ \Delta_\mathrm{n}(1) \ge \Delta_\mathrm{m}(0) + 2\delta }[/math], the protocol logic guarantees that each honest replica supports the notarization of block [math]\displaystyle{ B }[/math] and no other block, and thus [math]\displaystyle{ B }[/math] will become notarized and finalized.

Other issues

Growth latency

Under a partial synchrony assumption, a quantitative version of the growth invariant can also be formulated and proven. For simplicity, assume that the delay functions are defined as recommended above: [math]\displaystyle{ \Delta_\textrm{m}(r) = 2 \delta r }[/math] and [math]\displaystyle{ \Delta_\textrm{n}(r) = 2 \delta r + \epsilon }[/math], and further assume that [math]\displaystyle{ \epsilon \le \delta }[/math]. Suppose that at time [math]\displaystyle{ t }[/math], the highest numbered round entered by any honest replica is [math]\displaystyle{ h }[/math]. Let [math]\displaystyle{ r^* }[/math] be the rank of the lowest ranked honest replica [math]\displaystyle{ P^* }[/math] in round [math]\displaystyle{ h }[/math]. Finally, suppose that the network is [math]\displaystyle{ \delta }[/math]-synchronous at all times in the interval [math]\displaystyle{ [t,t+(3r^*+2)\delta] }[/math]. Then all honest replicas will start round [math]\displaystyle{ h+1 }[/math] before time [math]\displaystyle{ t+3(r^*+1)\delta }[/math].

Locally adjusted delay functions

When a replica does not see any finalized blocks for several rounds, it will start increasing its own delay function [math]\displaystyle{ \Delta_\textrm{n} }[/math] for notarization. Replicas need not agree on these locally adjusted notarization delay functions.

Also, while replicas do not explicitly adjust the delay function [math]\displaystyle{ \Delta_\textrm{p} }[/math], local clock drift can be mathematically modeled by locally adjusting both delay functions.

Thus, there are many delay fucntions, parameterized by replica and round. The critical condition [math]\displaystyle{ \Delta_\mathrm{n}(1) \ge \Delta_\mathrm{m}(0) + 2\delta }[/math] needed for liveness then becomes [math]\displaystyle{ \max \Delta_\mathrm{n}(1) \ge \min \Delta_\mathrm{m}(0) + 2\delta }[/math], where the [math]\displaystyle{ \max }[/math] and [math]\displaystyle{ \min }[/math] are taken over all the honest replicas in a given round. Thus, if finalization fails for enough rounds, all honest replicas will eventually increase their notarization delay until this holds and finalization will then resume. If some honest replicas increase their notarization latency function more than other replicas, there is no penalty in terms of liveness (but there may be in terms of growth latency).


Fairness

Another property that is important in consensus protocols is fairness. Rather than give a general definition, observe that the liveness invariant also implies a useful fairness property. Recall that the liveness invariant basically says that in any round where the leader is honest and the network is synchronous, then the block proposed by the leader will be finalized. In those rounds where this happens, the fact that the leader is honest ensures that it will include in the payload of its block all of the transaction requests it knows about (modulo limits on the payload size). So, very roughly speaking, any transaction request that is disseminated to enough replicas will be included in a finalized block in a reasonable amount of time with high probability.