Difference between revisions of "IC consensus layer"
VictorShoup (talk | contribs) |
VictorShoup (talk | contribs) |
||
Line 87: | Line 87: | ||
the network delay. | the network delay. | ||
+ | ==Public keys== | ||
To implement the protocol, each replica is associated with a | To implement the protocol, each replica is associated with a | ||
Line 93: | Line 94: | ||
The association of replicas to public keys is maintained by the | The association of replicas to public keys is maintained by the | ||
[[IC network nervous system (NNS)|network nervous system (NNS) of the Internet Computer]]. | [[IC network nervous system (NNS)|network nervous system (NNS) of the Internet Computer]]. | ||
− | These BLS signatures will be used to authenticate messages | + | These BLS signatures will be used to authenticate messages |
sent by replicas. | sent by replicas. | ||
− | The protocol also uses the <b>signature aggregation</b> feature of BLS signatures, | + | 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 | which allows many signatures on the same message to be aggregated into | ||
a compact multi-signature. | a compact multi-signature. | ||
− | |||
==Random Beacon== | ==Random Beacon== | ||
Line 222: | Line 223: | ||
finalization invariant, the <b>safety property</b> is | finalization invariant, the <b>safety property</b> is | ||
guaranteed to hold for these (explicitly and implicitly) finalized blocks. | guaranteed to hold for these (explicitly and implicitly) finalized blocks. | ||
+ | |||
+ | |||
+ | |||
+ | ==Delay functions== | ||
+ | |||
+ | The protocol makes use of two <b>delay functions</b>, | ||
+ | <math>\Delta_\textrm{p}</math> and <math>\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>\Delta_\textrm{p}(r) \le \Delta_\textrm{n}(r)</math> | ||
+ | for all <math>r = 0, \ldots, n-1</math>. | ||
+ | The recommended definition of these functions is | ||
+ | <math>\Delta_\textrm{p}(r) = 2 \delta r</math> | ||
+ | and | ||
+ | <math>\Delta_\textrm{n}(r) = 2 \delta r + \epsilon</math>, | ||
+ | where <math>\delta</math> is an upper bound on the time to deliver | ||
+ | messages from one honest replica to another, | ||
+ | and <math>\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>\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 <b>liveness invariant</b>. | ||
+ | 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>P</math> will record the time at which it | ||
+ | enters a given round <math>h</math>, | ||
+ | which happens when it has obtained (1) some notarization for a | ||
+ | block of height <math>h-1</math>, and (2) the random beacon for | ||
+ | round <math>h</math>. | ||
+ | Since the random beacon for round <math>h</math> has been determined, | ||
+ | <math>P</math> can determine its own rank <math>r_P</math>, as well as the | ||
+ | rank <math>r_Q</math> of each other replica <math>Q</math> | ||
+ | for round <math>h</math>. | ||
+ | |||
+ | ===Block making=== | ||
+ | |||
+ | Replica <math>P</math> will only propose its own block <math>B_P</math> | ||
+ | provided (1) at least <math>\Delta_\textrm{p}(r_P)</math> time | ||
+ | units have passed since the beginning of the round, | ||
+ | and (2) there is no <i>better</i> block available to <math>P</math>. | ||
+ | A block is deemed to be <i>better</i> than <math>B_P</math> | ||
+ | if it was proposed by a replica of rank less than <math>r_P</math> | ||
+ | that has not been <i>disqualified</i>. | ||
+ | We will discuss <i>disqualification</i> below. | ||
+ | |||
+ | Note that since <math>P</math> is guaranteed to have a notarized block | ||
+ | of height <math>h-1</math> | ||
+ | when it enters round <math>h</math>, it can make its proposed | ||
+ | block a child of this notarized block (or any other | ||
+ | notarized block of height <math>h-1</math> that it may have). | ||
+ | |||
+ | ===Notarization=== | ||
+ | |||
+ | Replica <math>P</math> will support the notarization | ||
+ | of a valid block <math>B_Q</math> proposed by a | ||
+ | non-disqualified replica <math>Q</math> of rank | ||
+ | <math>r_Q</math> | ||
+ | provided | ||
+ | (1) at least <math>\Delta_\textrm{n}(r_Q)</math> time | ||
+ | units have passed since the beginning of the round, | ||
+ | and (2) there is no better block available to <math>P</math>. | ||
+ | |||
+ | ===Disqualify or relay=== | ||
+ | |||
+ | |||
+ | Suppose <math>P</math> sees | ||
+ | of a valid block <math>B_Q</math> proposed by a | ||
+ | non-disqualified replica <math>Q</math> of rank | ||
+ | <math>r_Q < r_P</math> | ||
+ | such that | ||
+ | (1) at least <math>\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>P</math>. | ||
+ | At this point in time, <math>P</math> will either | ||
+ | <b>disqualify</b> the replica <math>Q</math> (for the current round) | ||
+ | or | ||
+ | <b>relay</b> the block <math>B_Q</math>. | ||
+ | |||
+ | Party <math>P</math> will <b>disqualify</b> <math>Q</math> if it | ||
+ | has <i>evidence of inconsistent behavior</i> by <math>Q</math> in this round. | ||
+ | Such evidence consists of either (1) two different block proposals | ||
+ | by <math>Q</math> in this round, or (2) a <i>proof of inconsistent behavior</i> | ||
+ | obtained from another replica. | ||
+ | Such a proof of inconsistent behavior is simply a message consisting | ||
+ | of two distinct block proposals from <math>Q</math>. | ||
+ | In either case, <math>P</math> will mark <math>Q</math> as <i>disqualified</i> | ||
+ | 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>P</math> does not disqualify <math>Q</math>, and has not already | ||
+ | relayed the block <math>B_Q</math>, it will <b>relay</b> <math>B_Q</math>, which | ||
+ | means it will broadcast <math>B_Q</math> to all replicas and mark | ||
+ | <math>B_Q</math> as <i>relayed</i>. |
Revision as of 21:13, 8 November 2021
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
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 periodically timely .
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
When the network is timely,
the message complexity in a given round of the IC consensus protocol is
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
Block making
Each replica may at different points in time play the role of a block maker.
As a block maker in round
- the payload,
- the hash of
, - the rank of the block maker,
- the height
of the block.
After forming the block
- the block
, - the block maker's identity, and
- the block maker's signature on
.
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,
- the hash of
, - the height
of , - the identity of the supporting replica, and
- the notarizing replica's signature on a message comprising the hash of
and the height .
Any set of
- the hash of
, - the height
of , - the set of identities of the
supporting replicas, - an aggregation of the
signatures on the message comprising the hash of and the height .
Each replica will finish round
Finalization
There may be more than one
notarized block at a given height
For a block to become finalized,
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
. - If a block
is finalized, then its finalization must have been supported by a set of at least honest replicas (by the security property for aggregate signatures). - If another block
were notarized, then its notarization must have been supported by a set of at least honest replicas (again, by the security property for aggregate signatures). - The sets
and are disjoint (by the finalization logic). - Therefore,
, which implies , a contradiction.
One consequence of the finalization invariant is the following.
Suppose one replica sees a finalized block
Delay functions
The protocol makes use of two delay functions,
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
Block making
Replica
Note that since
Notarization
Replica
Disqualify or relay
Suppose
Party
If