|
|
(52 intermediate revisions by 5 users not shown) |
Line 1: |
Line 1: |
− | The job consensus layer of the IC is to order transaction requests so that all replicas in a subnet will process
| + | Please see [https://internetcomputer.org/how-it-works/consensus/ How Consensus Layer works] |
− | 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:
| |
− | * <b>safety</b>: all replicas in fact agree on the same ordering of transaction requests, and
| |
− | * <b>liveness</b>: all replicas should make steady progress.
| |
− | | |
− | The IC consensus protocol is design to be
| |
− | * extremely simple, and
| |
− | * robust (performance degrades gracefully when some replicas are malicious).
| |
− | | |
− | As discussed [[The Internet Computer for Computer Scientists|in the introduction]], we assume
| |
− | * a subnet of <math>n</math> replicas, and
| |
− | * at most <math>f < n/3</math> of the replicas are faulty.
| |
− | Faulty replicas may exhibit arbitrary, malicious (i.e., Byzantine) behavior.
| |
− | | |
− | We assume that communication is <b>asynchronous</b>, with no <i>a priori</i>
| |
− | 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 <b>partial synchrony</b>,
| |
− | which (roughly stated) says that the network will be <b>timely</b> periodically.
| |
− | Somewhat more precisely, there exists a bound <math>\Delta</math> such that
| |
− | periodically all undelivered
| |
− | messages will be delivered within time <math>\Delta</math>.
| |
− | The bound <math>\Delta</math> does not have to be known in advance (the protocol can
| |
− | adapt itself to an unknown <math>\Delta</math> value).
| |
− | Regardless of whether we are assuming an asynchronous
| |
− | or partially synchronous network,
| |
− | we assume that every message sent from one honest
| |
− | party to another will <i>eventually</i> be delivered.
| |
− | | |
− | Like a number of consensus protocols,
| |
− | the IC consensus protocol is based in a [[wikipedia:blockchain|blockchain]].
| |
− | As the protocol progresses, a tree of blocks is grown,
| |
− | starting from a special <i>genesis block</i> that is the root of the tree.
| |
− | Each non-genesis block in the tree contains (among other things)
| |
− | a <i>payload</i>, 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 <i>same</i> tree.
| |
− | In addition, as the protocol progresses,
| |
− | there is always a path of <i>finalized</i> 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 <i>same</i> path.
| |
− | The transaction requests in the payloads of the blocks along this
| |
− | path are the ordered transaction requests will be processed by the [[IC execution layer|execution layer]]
| |
− | of the Internet Computer.
| |
− | | |
− | The protocol proceeds in <b>rounds</b>.
| |
− | In round <math>h</math> of the protocol,
| |
− | one or more blocks of <b>height</b> <math>h</math> are added to the tree.
| |
− | That is, the blocks added in round <math>h</math> are always at a distance
| |
− | of exactly <math>h</math> from the root.
| |
− | In each round, a [[random beacon]] is used to
| |
− | generate a random permutation of the <math>n</math> parties,
| |
− | so as to assign to each party a <b>rank</b>.
| |
− | The party of lowest rank is the <b>leader</b> 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.
| |
− | 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.
| |
− | | |
− | The message complexity per round of the IC consensus protocol is typically <math>O(n^2)</math>.
| |
− | The protocol also enjoys the property known as <b>optimistic responsiveness</b>,
| |
− | 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.
| |
− | | |
− | | |
− | To implement the protocol, each replica is associated with a
| |
− | public key for the [[wikipedia:BLS_digital_signature|BLS signature scheme]], and each replica also holds
| |
− | the corresponding secret signing key.
| |
− | The association of replicas to public keys is maintained by the
| |
− | [[IC network nervous system (NNS)|network nervous system (NNS) of the Internet Computer]].
| |
− | These BLS signatures will be used to authenticate messages, also called <b>artifacts</b>,
| |
− | sent by replicas.
| |
− | The protocol also uses the <b>signature aggregation</b> 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.
| |
− | | |
− | In addition to BLS signatures and multi-signatures as discussed above,
| |
− | the protocol makes use of a BLS [[wikipedia:Threshold_cryptosystem|threshold signature scheme]] to implement the
| |
− | above-mentioned [[random beacon]].
| |
− | To set up such a threshold signature scheme, the Internet Computer runs a
| |
− | [[wikipedia:Distributed_key_generation|distributed key generation (DKG)]] protocol.
| |
− | There are many DKG protocols in the literature.
| |
− | The Internet Computer implements a new [[non-interactive DKG (NiDKG) protocol]].
| |
− | | |
− | Initialization:
| |
− | * broadcast a share of the height 1 beacon
| |
− | * <math>D \gets \emptyset</math> — ''the set of disqualified parties''
| |
− | | |
− | | |
− | For each height <math>h=1, 2, 3, \ldots</math>
| |
− | * wait for <math>f+1</math> shares of the height-<math>h</math> random beacon
| |
− | * combine these shares to obtain the height-<math>h</math> random beacon
| |
− | ** ''this defines the rank of each replica''
| |