Chain Key Cryptography: The Scientific Breakthrough Behind the Internet Computer
Chain Key cryptography is a set of cryptographic protocols that orchestrate the nodes that make up the Internet Computer.
By Jan Camenisch, VP of Research & Crypto | DFINITY
The Internet Computer is the world’s first web-speed, internet-scale public blockchain, which enables smart contracts to securely serve interactive web content directly into the browsers of end users. It enables developers, organizations, and entrepreneurs to build and deploy secure and autonomous software programs directly on the public internet. Years of dedicated research and development at the DFINITY Foundation have made this ambitious vision possible, combining novel cryptography and computer science to create a blockchain that provides unbounded storage and computation on-chain.
A skilled team of many of the world’s top cryptographers, researchers, and engineers have spearheaded this effort to enable decentralization and solve hard technical challenges. Working together, we have brought advanced concepts into the real world and implemented cutting-edge technologies that will have a tremendous impact on the entire world of computing.
The Internet Computer will eventually run millions of nodes at scale. Chain Key cryptography is one of the fundamental breakthroughs enabling this. It consists of a set of cryptographic protocols that orchestrate the nodes that make up the Internet Computer. The most visible innovation of Chain Key cryptography is that the Internet Computer has a single public key. This is a huge advantage as it allows any device, including smart watches and mobile phones, to verify the authenticity of artifacts from the Internet Computer. In contrast, this is not possible on traditional blockchains such as Ethereum, where the verification of just a small artifact requires an abundance of data.
The single public key is just the tip of the iceberg: Chain Key cryptography is the engine that drives the Internet Computer and makes its operation possible. It allows for
- Adding new nodes to form new subnets to scale the network infinitely;
- Replacing faulty or crashed nodes with new ones without ever stopping;
- Reviving subnets even if too many nodes within have failed; and
- Upgrading the Internet Computer Protocol seamlessly, allowing the network to fix bugs and add new features.
The Internet Computer
To put Chain Key cryptography into perspective, let us first have a closer look at the Internet Computer. It is composed of numerous nodes located all over the world that run the Internet Computer Protocol (ICP). The protocol connects all of these nodes and orchestrates the execution of canister smart contracts on these nodes. Software canisters are bundles containing both code and state that are deployed by developers onto the Internet Computer. An application can consist of a single canister or, since canisters are limited in size, of many canisters that interact with each other. Canisters can implement just about anything, such as web pages, enterprise systems, DeFi use cases, and even open internet services.
When a user interacts with an app that is deployed on the Internet Computer, a message is sent via the ICP to the canister. Next, the Internet Computer executes the canister on the input of that message and eventually computes an output message that the user can query back. By executing the message, the state of the canister is updated as prescribed by its code.
To achieve robustness and correctness of results computed by the Internet Computer, each canister is run on multiple nodes rather than just a single one. This is because a single node represents a single point of failure; a node could crash because of a hardware failure, be cut off from the internet, or, worse, intentionally report incorrect results. So the Internet Computer Protocol ensures that a canister is run on multiple nodes and that these nodes agree on which messages to process in what order, as well as on the value of the result of each computation. This ensures the correctness of results, that the network is robust against all kinds of failures, and that canisters can run forever.
Chain Key Cryptography
To ensure users of the Internet Computer of the correctness of results transmitted to them, it is further necessary that they can verify that messages they received indeed originate from the Internet Computer and not from elsewhere. As no single node is trusted, messages need to be jointly signed by all the nodes hosting the canister that the user queries for a result. That’s where Chain Key cryptography comes in: All nodes receive secret key shares that enable them to jointly sign a message with the requested result. The thus created signature can be verified using the Internet Computer’s public key only. The beauty here is that even though the Internet Computer is powered by millions of nodes and thousands of subnets at scale, all the network needs is a single public key to validate any of the results from the subnets.
For the Internet Computer to scale, not all nodes can run all canisters. Therefore, the nodes are partitioned into so-called subnets and the different canisters are distributed over these subnets. More precisely, when uploading a canister into the Internet computer, it gets assigned a subnet onto which it is installed and then is run only on the nodes that participate in that subnet. To authenticate messages, each subnet has its own public key. All the nodes of the subnet have a share of the secret key corresponding to their subnet’s public key. Using a so-called threshold signature scheme, if a sufficient number of nodes (more than the required threshold) agree, they can use their respective key share to jointly sign a message. The signature on the message can then be verified by a user w.r.t. the subnet public key. All subnet public keys will in turn be signed w.r.t. the single public key of the Internet Computer (we will describe below how this is done).
In summary, Chain Key cryptography makes it possible that knowledge of a single 48-byte public key — the public key of the Internet Computer — is sufficient for the validation of responses and the computation of the Internet Computer. In stark contrast, to validate an outcome of a smart contract on Ethereum, an open Ethereum client needs to download 400 gigabytes. Even worse, the required download size only grows linearly with time: The required size has doubled within a single year, it was only around 200 gigabytes a year ago.
Scaling out infinitely
At scale, when the Internet Computer has thousands of subnets, this means it will also have thousands of individual public keys corresponding to each subnet. These public keys and the corresponding secret key shares need to be generated, managed and maintained in a secure fashion in an environment where nodes are added and new subnets are formed to increase capacity, nodes fail for various reasons and are replaced, and attackers that block communication, try to manipulate it or to compromise nodes and cause them to deviate from the protocol in arbitrary ways.
For the nodes to jointly generate a signature on a message, a standard threshold signing algorithm is sufficient. For the generation and maintenance of all the keys, the DFINITY team has invented new cryptography that we are going to explain at a high level now. There are two main procedures that we have built: (1) The formation of new subnets and the generation of the key materials for them is done by the Internet Computer’s Network Nervous System (NNS) which is implemented by canisters that run on the initial subnet that is created at genesis; and (2) Once the nodes that are to form a new subnet have received their key materials from the NNS and started to operate a new subnet, the subnet will manage and maintain its keys itself as per the Internet Computer Protocol.
These two procedures are built from a number of cryptographic primitives including threshold signatures, public key encryption, and non-interactive zero-knowledge proofs. Let us first explain how the Internet Computer generates the keys for a new subnet. More precisely, how the NNS subnet generates the public key a new subnet and the corresponding key shares for the nodes designated to run the new subnet. The normal key generation algorithm for a threshold signature scheme assumes a single trusted dealer. However, this assumption is not warranted for the Internet Computer as it needs to tolerate malicious nodes. The solution that ICP implements is to 1) use multiple dealers, 2) have them prove that they encrypted the correct shares for the designated nodes, and 3) to combine the keys they generate into a single public key and corresponding secret key shares.
Chain Key cryptography will generate secure key materials as long as a single dealer is honest, a criterion which is satisfied if more than one-third of the nodes of the NNS subnet will act as dealers. They each generate a public key, encrypt secret key shares under the encryption keys that the new nodes have made available when registering with the Internet Computer, and then add our tailor-designed noninteractive zero-knowledge proofs that they have done all of this correctly. The NNS subnet as a whole verifies these proofs and, if they are correct, makes the information provided by all of the dealers available to the nodes of the new subnet. These new nodes decrypt their respective key shares and combine the shares from the different dealers into a single share. (This is possible because of a mathematical property called homomorphism that exists in the key space.) Once the nodes have done that, they are ready to operate the new subnet.
While operating a subnet, its nodes need to maintain the secret key shares. This is necessary because nodes might fail and need to be replaced or because nodes might become compromised by an attacker and consequently leak the respective secret key share. In both cases the secret key share must be replaced. To this end, the remaining nodes can reshare their secret key shares. Thus each node will receive sharings of an original secret key share from many other nodes. Due to the mathematical properties of secret sharing, these “shares of a share” can be recombined into an ordinary share of the secret key. The new shares generated like this will amount to a fresh sharing of the secret key. Therefore, similarly to key generation, each node will share its original secret key share obtaining shares of the secret key share, encrypt these shares for the (possibly different) set of nodes designated to run the subnet and add a noninteractive zero-knowledge proof that is done correctly. The new set of nodes will thus receive a number of such sharings and, if the proofs verify, decrypt the share and combine them into a single key share. After this process, the new set of nodes delete the old shares, if they had some, and then can continue to operate the subnet. This resharing process ensures that 1) fresh nodes get the necessary secret key shares and 2) shares that fall into the hands of an attacker become obsolete and thus worthless.
Subnet operation requires keys and canister state
As just explained, Chain Key cryptography allows the NNS subnet to scale out infinitely. It decides which node will be assigned to which subnet, and generates and certifies the public keys of all the subnets together with the initial secret key shares. So indeed, all the user needs is the public key of the NNS subnet to validate the certificate on the response that it gets from the subnet.
Let us discuss further aspects of Chain Key cryptography that are very important for the network to evolve. First, notice that apart from the secret key shares, a new node joining a running subnet also requires the current state of all canisters assigned to that subnet. This is necessary for the node to be able to process messages to canisters and update their states and fully participate in the subnet. A joining node can request the state from its peer nodes who are already operating the subnet (via a state-sync protocol). However, as nodes could be faulty, the joining node must be able to verify the authenticity and correctness of state received from peer nodes. To this end, the other nodes threshold sign (the root hash of) the states of all canisters.
Unfortunately, noninteractive key resharing and state certification are expensive operations, and therefore cannot be done for every block but only in regular intervals — say, every 200 blocks. Therefore, a subnet regularly produces a so-called catch-up package that bundles all the information a node requires to participate in the subnet. In addition to allowing new nodes to join a subnet, catch-up packages, as their name suggests, also enable existing nodes to resume operation in cases such as when they were cut off from the network.
The power of catch-up packages
Catch-up packages end up enabling many more things because they essentially provide a well-defined state in the execution of a subnet. Therefore, whenever a subnet has generated a catch-up package, all previous state can be deleted, which makes the Internet Computer much more storage efficient than typical blockchains where all state is maintained forever.
As a second feature, catch-up packages allow the Internet Computer to revive a subnet even if the majority of the nodes have crashed. As long as a single node survives, the catch-up package can be recovered, a new set of keys generated, and then a fresh subnet can continue to run the canisters from the state in the catch-up package.
Thirdly, catch-up packages allow the Internet Computer to load balance. Assuming the canisters installed on a subnet become very popular and require more resources that a single subnet can provide, the Internet Computer can instruct the nodes to split the subnet into two subnets, each of them continuing from the same catch-up package but each keeping only a half the canisters.
Lastly, catch-up packages also allow for upgrading the Internet Computer Protocol itself. The idea here is to instruct the nodes of a subnet to run a different version of the protocol after the next catch-up package has been produced. This makes it possible to fix bugs in the protocol, add new features, and so on. It is probably the most crucial feature for the Internet Computer to run forever.
_____
Stay tuned for more releases detailing the technologies behind the Internet Computer.
