This is a note of Internet Computer whitepaper: The Internet Computer for Geeks, published on 04/19/2022 by the Dfinity team.
The Internet Computer (IC) is a platform for executing smart contracts that are general purpose, tamperproof computer programs whose execution is performed autonomously on a decentralized public network. In addition, smart contracts are composable and support tokenization. The IC is designed to address the current blockchain issues of high cost, low throughput, low latency, no scalablitlity, immutability.
The IC is a complete technology stack for building systems and services running entirely on the IC. It is an end-to-end solution that interacts directly with end users using the same HTTP protocol. It provides secure and reliable message delivery, transparent accountability, backup facilities, load balancing, and failover orchestration. The IC has the following special features:
- Supports intereoperability, shared functions, permanent APIs, and ownerless applications.
- Persists data automatically in memory.
- Simplifies the technology stack.
At a high level, the IC can be viewed as a network of interacting replicated state machines. A replicated state machine comprises a subnet of replicas that runs a consensus protocol to process the same inputs in the same order. It tolerates 1/3 Byzantine node faults. The subnet is globally distributed and uses a partial synchrony communication model to achieve good performance.
The IC’s permission model is a hybrid model called DAO-controlled network that works as follows: each subnet runs a permissioned consensus protocol, but a decentralized autonomous organization (DAO) determines which entities provide replicas, con gures the topology of the network, provides a public-key infrastructure, and controls which version of the protocol is deployed to the replicas. The IC’s DAO is called the network nervous system (NNS), and is based on a PoS. The NNS is itself a replicated state machine that runs on a particular subnet whose membership is determined via the same PoS-based governance system.
The NNS maintains a database called the registry, which keeps track of the topology of the IC. The registry binds public keys to replicas and subnets as a whole – so called chain-key cryptography has the following components:
- Threshold signatures: secret signing key is split into shares that are distributed among a subnet’s all replicas. An output of one subnet may be verfied by another subnet or external user. The IC uses an innovative distributed key generation (DKG) protocol that create a public key adn the corresponding secret signing key shares.
- Chain-evolution technology: a subnet operates in epochs of many rounds. Many maintenance activities are executed periodically with a cadence including garbage collection, fast forwarding, membership changes, pro-active resharing of secrets, protocol upgrades.
The basic computational unit is a canister that comprises of both a WebAsssembly (Wasm) program and its state. Motoko is a strongly typed, actor-based programming language designed to align with the operational semantics of the IC. It supports orthogonal persistence, asynchronous message passing, automatic memory management, generics, type inference, pattern matching, and both arbitrary and fixed-precision arithemtic. The IC also provides a messaging interfacer definition language and wire format called Candid, for typed, high-level, and cross-language interoperability. Rust is another supported language to develop a canister.
The IC has a utility token called ICP that is used for staking, gas, and rewards.
Boundary nodes provide the network edge services (entry point, DOS protection and seamless access from legacy clients) of the IC. All communications among clients, boundary nodes, and replicas is secured via TLS.
The NNS is an algorithmic governance system that controls the IC. It has a set of canisters on a special system subnet. Some NNS canisters are
- the reigstry canister: configuration of the IC
- the governance canister: decision making and voting
- the ledger canister: the users' ICP token accounts and transactions
In the future, any canister can be controlled by its own DAO, called the service nervous system (SNS).
The ICP consists of four layers: p2p, consensus, routing, and execution. The p2p layer transports protocol messages in a best effort broadcast channel between the replicas in a subnet. The protocol messages consist of consensus messages and input messages. The consensus layer (see Section 5) bundles inputs into payloads, which get placed into blocks, and as blocks are nalized, the corresponding payloads are delivered to the message routing layer, then processed by the execution environment, which updates the state of the canisters on the replicated state machine and generates outputs, and these outputs are processed by the message routing layer.
The consensus layer guarantees safety (same ordering) and liveness (progress). The consensus layer is a blockchain where a tree of blocks grows as the protocol progresses. Inputs are placed into block payloads. The root of the tree is a special genesis block. There is always a path of finalized blocks in this tree as the protocol progresses in rounds. While each replica may have a different, partial view of the tree/path, all the replicas have a view of the same tree and same path.
The message routing layer takes messages in a canister’s subnet-to-subnet output queues, place them into subnet-to-subnet streams and transport them using a crossneet transfer protocol. The replicated state comprises that state of the canisters and system state that include the above queues/streams and ingress history. In each round, the system state is certified as per-round certified state using a threshold signature. The certified state is authenticated with ordered messages. As an optimization, query calls is processed directly by a single replica without passing through consensus. However, certified variables are authenticated.
The execution layer processes one input at a time. Each subnet has access to a distributed pseudorandom generator (PRG). A Random Tape is a threshold signature consists of pseudorandom bits. It is genereated in each round.
3 Threshold Signatures
The threshold signature has the following security property: “Assume that at most
f replicas may be corrupted by an adversary. Then it is infeasible for the adversary to compute a valid signature on a message unless it obtains signature shares on that message from at least
t - f honest replicas.”
The distributed key generation (DKG) protocol is used to distribute the shares of the secret signing key to the replicas. It has two components: a publicly verifiable secret sharing (PVSS) scheme and a consensus protocol. It can also be used to create a fresh, random sharing of a previously shared secret.
4 Peer-to-peer Layer
The peer-to-peer layer is to transport protocol messages between the replicas in a subnet. The protocol messages consist of consensus messages (block proposals, notarizations etc) and ingress messages. The p2p layer has the following design goals:
- it works with bounded resources of memory, bandwidth and CPU.
- messages have different priorities.
- high throughput is more important than low latency.
- it prvents DOS/SPAM.
It uses advertise-request-deliver mechanism to improve throughput at the cost of higher latency. Small subnets use broadcasting. Large subnets use an overlay network, also called gossip network.
5 Consensus Layer
The IC assumes a form of partial synchrony: the network will be periodically synchronous for short intervals of time. In such intervals of synchrony, all messages will be delivered in a fixed bound time – the bound time is dynamically adaptive. It also assumes that every message will eventually be delivered.
The consensus protocol proceeds in rounds. Blocks added in round
h are always at a distance of exactly
h from the genesis block. In each round, a random beacon assigns each replica a unique rank, which is an integer in the range 0, …, n - 1 where
n is the number of replicas. The replica of the lowest rank is the leader of that round. The leader will propose a block if the leader is an honest one. If the leader is not honest or the network is not synchronous, other replicas of higher ranks may propose blocks. It is possible that the finalized path is not extended when the protocol continue to proceed for a few rounds. The protocol has a constant throughput at the cost of occasionally increased latency. It is robust to proceed in a timely fashion when a leadeer is corrupt.
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. The protocol will use these multi-signatures for notarizations and nalizations, which are aggregations of
n - f signatures on messages of a certain form.
The random beacon for height
h is a
(f + 1)-threshold signature on a message unique to height
h. 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. It is impossible to know it in advance.
5.2 Making a Block
A block maker propose a block that has the following fields:
- the payload
- the hash of the parent block
- the rank of the block maker
- the height of the block
The block proposal add the block maker’s identity and signature to the block and broadcast the proposal to other replicas.
5.3 Notarization and Finalization
For a block to become notarized,
n - f distinct replicas must support its notarization. The aggregation of the
n - f notarizations form a block notorization that is broadcasted to other replicas. There maybe more than one notarized block at a given height. If a block is finalized, there is only one notarized block at the given height – this is called safety invariant.
For a block to become nalized,
n - f distinct replicas must support its nalization. A replica broadcasts a finalization share for its supported notarization. Any set of
n - f nalization shares on B may be aggregated together to form a nalization for B, Any replica that obtains a finalized block will broadcast the nalization to all other replicas. Once a block is finalized, all its ancestors are finalized.
5.4 Consensus Process
A replica enters a round
h when it receives a block notarization of height
h - 1 and random beacon for round
h. It will realy the random beacon for round
h to all other replicas. It will generate and broadcast its share of the random beacon for round
h + 1.
A replica P will only propose its own block provided (1) at least a specified time units have passed since this round, and (2) there is no valid lower ranked block current seen by P. P then broadcast its block proposal. Another replica Q checks the same condition and replay this block proposal to all other replicas. Q also support the notarization of the block proposal if the two conditions are met.
The consensus process meets the growth invariant, safety invariant, and liveness invariant. If a subnet has a network delay of
d, then the growth delay latency has an upper bound of
3(r + 1)d, where
r is the lowest rank of honest replicas.
6 Message Routing Layer
The consensus layer is decoupled from the message routing and execution layers and is allowed to run a bit ahead. Upon receiving a payload from consensus, the inputs in that payload are placed into various input queues. For each canister C running on a subnet, there are several input queues: there is one queue speci cally for ingress messages to C, and each other canister C', with whom C communicates, gets its own queue. The execution layer will consume some of the inputs in these queues in each round, update the replicated state of the relevant canisters, and place outputs in various output queues. The message routing layer will take the messages in these output queues and place them into subnet-to-subnet streams to be processed by a crossnet transfer protocol, whose job it is to actually transport these messages to other subnets.
There is also an ingress history data structure. Once an ingress message has been processed by a canister, a response to that ingress message will be recorded in this data structure. At that point, the external user who provided the ingress message will be able to retrieve the corresponding response. Note that ingress history does not maintain the full history of all ingress messages. Intra-subnet messages are moved directly from output queues to corresponding input queues.
A replicated state consists of the state of the canisters, input queues, output queues, subnet-to-subnet streams, and the ingress history data. Both the message routing and execution layers are involved in updating and maintaining the replicated state of a subnet. It is essential that all of this state is updated in a completely deterministic fashion, so that all replicas maintain exactly the same state.
6.2 Per-round Certified State
In each round, the per-round certified state is generated and hashed as a Merkle tree and is signed by threshold signagure scheme. The per-round certified state consist of
- cross-subnet messages that were recently added to the subnet-to-subnet streams.
- other metadata, including the ingress history data structure.
- the Merkle-tree root hash of the per-round ceertified state from the previous round.
Note that the per-round certied state does not include the entire replicated state of a subnet, as this in general will be too big to be certified in every round. The per-round certied state is used in the following scenarios:
- Output (ingress message responses and cross-subnet messages) authentication.
- Preventing and detecting non-determinism.
- Coordination with consensus using consensus throttling and state-specific payload validation.
6.3 Query Calls vs Update Calls
A query call may be processed dirctly by a single replica without passing through consensus. The response to a query call is not recorded in the ingress history data structure. If authenticated responses are needed, certified variables can be used and will be part of the per-round certified state.
6.4 External User Authentication
An external user identifies himself to a canister using a user identifier (aka principal), which is a hash of a public signature-verification key. Each ingress message includes the user’s public key and message signature.
A user may associate several key pairs with a single user identif, using signatue delegation. Therefore a user may access the IC from several devices using the same user identity.
7 Execution Layer
A scheduler determines which inputs are executed in a given round, and in which order. The scheduling must be deterministic (only depend on the given data) and the amount of work, in terms of cycles, done in each round should be close to some pre-determined amount. If a canister overflows another canister, is should be throttled.
8 Chain-evolution Technology
Chain-evolution technology implements maintenance actitives that are executed in each epoch: garbage collection, fast forwarding, subnet membership changes, pro-active resharing of secrets, and protocol upgrades. Summary blocks and catch-up packages (CUPs) are two essential ingredients to chain-evolution technology.
8.1 Summary Blocks
A summary block contains data used to manage the shares of the two threshold signature schemes: a low-threshold
(f + 1)-out-of-n scheme and a ghigh-threshold
(n - f)-out-of-n scheme. The low-threshold scheme is used for the random beacon and the random tape. A new signing key is generated every epoch. The high-threshold scheme is used to certify the replicated state of the subnet and is reshared every epoch.
Subnets must agree on which registry version they use at various times for various purpose. The registry data
nextRegistryVersion for each epoch are stored in the summary block.
Summary block also includes data such as
collectDealingParams etc used by different committees such as threshold signing committee, consensus committee, receiving committee
A CUP is a special message that has mostly everything a replica needs to begin working in a given epoch. It has the following data fields:
- The root of a Merkle has tree for the entire replicated state.
- The summary block for the epoch.
- The random beacon for the first round of the epoch.
- A signature on the above fields under the
(n-f)-out-of-nthreshold signing key for the subnet.
8.3 Maintenance Tasks
- Garbage collection: every replica purges processed inputs and consensus-level protocol messages.
- Fast forwarding: fast forward to the most recent epoch.
- Subnet membership chagnes.
- Pro-active resharing of secrets.
- Protocol upgardes