IC consensus layer

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/1330 (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/1330 proves that the IC consensus protocol satisfies both of these properties

The IC consensus protocol is design to be

extremely simple, and
robust (performance degrades gracefully when some replicas are malicious).

As discussed in the introduction, we 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. To simplify the presentation, we assume here that [math]\displaystyle{ n=3f+1 }[/math].

We assume that 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, we need to assume a form of partial synchrony, which (roughly stated) says that the network will be periodically timely . Somewhat more precisely, there exists a bound [math]\displaystyle{ \Delta }[/math] such that periodically all undelivered messages will be delivered within time [math]\displaystyle{ \Delta }[/math]. The bound [math]\displaystyle{ \Delta }[/math] does not have to be known in advance (the protocol is initialized with a bound, but will dynamically adapt and increase this bound if it is too small). Regardless of whether we are assuming an asynchronous or a partially synchronous network, we assume that every message sent from one honest party to another will eventually be delivered.

Like a number of consensus protocols, the IC consensus protocol is based in 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,h-1 }[/math]. This is 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 timely, 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 timely, 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.

When the network is timely, the message complexity in a given round of the IC consensus protocol is [math]\displaystyle{ O(n^2) }[/math] with overwhelming probability. The protocol also enjoys the property known as optimistic responsiveness, which means that so long as the leader is honest, the protocol will proceed at the pace of the actual network delay, rather than some upper bound on the network delay.

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.

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 to be child of a 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 only added to the tree of blocks when it becomes notarized. For a block to become notarized, [math]\displaystyle{ 2f+1 }[/math] distinct replicas must support its notarization. Given a proposed [math]\displaystyle{ B }[/math] at height [math]\displaystyle{ h }[/math], a replica will verify a number of conditions, and if these tests pass, 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 notarizing 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{ 2f+1 }[/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{ 2f+1 }[/math] supporting replicas,
an aggregation of the [math]\displaystyle{ 2f+1 }[/math] signatures on the message comprising the hash of [math]\displaystyle{ B }[/math] and the height [math]\displaystyle{ h }[/math].

Each replica will finish round [math]\displaystyle{ h }[/math] as soon as it obtains a notarized block of height [math]\displaystyle{ h }[/math], and will not subsequently notarize any other blocks at height [math]\displaystyle{ h }[/math].

Finalization

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

For a block to become finalized, [math]\displaystyle{ 2f+1 }[/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]. 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{ 2f+1 }[/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.

One can easily see that the logic for finalizing blocks implies that the finalization invariant must hold. Here is a proof:

Suppose that the number of corrupt parties is exactly [math]\displaystyle{ f^* \le f \lt n/3 }[/math].
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).
If 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).
The sets [math]\displaystyle{ S }[/math] and [math]\displaystyle{ S' }[/math] are disjoint (by the finalization logic).
Therefore, [math]\displaystyle{ n-f^* \ge |S| + |S'| \ge 2 (n-f-f^*) }[/math], which implies [math]\displaystyle{ n \le 3f }[/math], a contradiction.

One consequence of the finalization invariant is the following. Suppose one replica sees a finalized block [math]\displaystyle{ B }[/math] at height [math]\displaystyle{ h }[/math] and that another replica sees a finalized block [math]\displaystyle{ B' }[/math] at height [math]\displaystyle{ h' \le h }[/math]. Then the finalization 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 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 finalization 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{p} }[/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 of the proposing replica no a nonnegative delay amount, and it is assumed that [math]\displaystyle{ \Delta_\textrm{p}(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{p}(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 }[/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. Note that even if (1) or (2) do not hold in a given round, the protocol is still guaranteed to make progress in the sense that at least one notarized block will be added to the tree in that round. Also note that the safety property of the protocol is always guaranteed.

Putting it all together

We now describe in more detail how the protocol works; specifically, we describe 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].

Block making

Replica [math]\displaystyle{ P }[/math] will only propose its own block [math]\displaystyle{ B_P }[/math] provided (1) at least [math]\displaystyle{ \Delta_\textrm{p}(r_P) }[/math] time units have passed since the beginning of the round, and (2) there is no better block available to [math]\displaystyle{ P }[/math]. A block is deemed to be better than [math]\displaystyle{ B_P }[/math] if it was proposed by a replica of rank less than [math]\displaystyle{ r_P }[/math] that has not been disqualified (see below).

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).

Notarization

Replica [math]\displaystyle{ P }[/math] will support the notarization of a valid block [math]\displaystyle{ B_Q }[/math] proposed by a non-disqualified 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, (2) there is no better block available to [math]\displaystyle{ P }[/math], and (3) there is no evidence of inconsistent behavior by [math]\displaystyle{ Q }[/math] in this round (see below).

Disqualify or relay

Suppose [math]\displaystyle{ P }[/math] sees of a valid block [math]\displaystyle{ B_Q }[/math] proposed by a non-disqualified replica [math]\displaystyle{ Q }[/math] of rank [math]\displaystyle{ r_Q \lt r_P }[/math] such that (1) at least [math]\displaystyle{ \Delta_\textrm{p}(r_Q) }[/math] time units have passed since the beginning of the round, and (2) there is no better block available to [math]\displaystyle{ P }[/math]. At this point in time, [math]\displaystyle{ P }[/math] will either disqualify the replica [math]\displaystyle{ Q }[/math] (for the current round) or relay the block [math]\displaystyle{ B_Q }[/math].

Party [math]\displaystyle{ P }[/math] will disqualify [math]\displaystyle{ Q }[/math] if there is evidence of inconsistent behavior by [math]\displaystyle{ Q }[/math] in this round. Such evidence consists of either (1) two different block proposals by [math]\displaystyle{ Q }[/math] in this round, or (2) a proof of inconsistent behavior obtained from another replica. Such a proof of inconsistent behavior is simply a message consisting of two distinct block proposals from [math]\displaystyle{ Q }[/math]. In either case, [math]\displaystyle{ P }[/math] will mark [math]\displaystyle{ Q }[/math] as disqualified for the current round, and broadcast to all replicas a proof of inconsistent behavior. Note that since block proposals are signed, it is infeasible to construct a proof of inconsistent behavior against an honest replica.

If [math]\displaystyle{ P }[/math] does not disqualify [math]\displaystyle{ Q }[/math], and has not already relayed the block [math]\displaystyle{ B_Q }[/math], it will relay [math]\displaystyle{ B_Q }[/math], which means it will broadcast [math]\displaystyle{ B_Q }[/math] to all replicas and mark [math]\displaystyle{ B_Q }[/math] as relayed.