|
|
| (69 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 there exists a bound <math>\Delta</math>
| |
| − | such that from time to time,
| |
| − | 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 ``genesis block'' that is the root of the tree.
| |
| − | Each non-genesis block in the tree contains (among other things)
| |
| − | a {\em payload}, consisting of a sequence of commands,
| |
| − | and a hash of the block's parent in the tree.
| |
| − | The honest parties have a consistent view of this tree:
| |
| − | while each party may have a different, partial view
| |
| − | of this tree, all the parties have a view of the {\em same} tree.
| |
| − | In addition, as the protocol progresses,
| |
| − | there is always a path of {\em committed} blocks in this tree.
| |
| − | Again, the honest parties have a consistent view of this path:
| |
| − | while each party may have a different, partial view
| |
| − | of this path, all the parties have a view of the {\em same} path.
| |
| − | The commands in the payloads of the blocks along this
| |
| − | path are the commands that are output by each party.
| |