IC consensus layer
The job consensus layer of the IC is to order transaction requests so that all replicas in a subnet will process transaction 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
replicas, and - at most
of the replicas are faulty.
Faulty replicas may exhibit arbitrary, malicious (i.e., Byzantine) behavior.
To simplify the presentation, we assume here that
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 timely periodically.
Somewhat more precisely, there exists a bound
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
The message complexity per round of the IC consensus protocol is typically
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, also called artifacts,
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.
FIXME: citation, discussion of rogue key attack mitigation.
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
XXX