Subnet splitting

High level overview of subnet splitting steps

The Internet Computer Protocol (ICP) now supports a minimal viable product (MVP) version of subnet splitting. Subnet splitting is a process, where a subset of the canisters from the parent subnet A are split off onto a newly created child subnet B for load balancing purposes and the remaining canisters stay on the trimmed down subnet A’. The MVP process is orchestrated by a series of NNS proposals and, very roughly speaking, consists of the steps visualized on the right.

Background

To understand all the details of subnet splitting we need to take a closer look at some parts of the ICP.

Checkpoints and Manifests

Up to date nodes persist their state to disk every couple hundreds of rounds (usually 500). A state that is persisted to disk by the protocol is called a checkpoint. Each checkpoint is a directory with the following structure (note that not all of the files shown below are necessarily present in every checkpoint, e.g., writing empty files may be skipped).

├── canister_states
│   ├── <hex(canister_id)>
│   │  	├── canister.pbuf
│   │	├── queues.pbuf
│   │   ├── software.wasm
│   │   ├── stable_memory.bin
│   │	└── vmemory_0.bin
│   ...
├── ingress_history.pbuf
├── split_from.pbuf
├── subnet_queues.pbuf
└── system_metadata.pbuf

For example, the state of each canister is stored in a separate directory. In contrast, there’s a single file containing the current ingress history (request statuses) of all canisters.

For each checkpoint the protocol will also compute a so-called manifest. Such a manifest consists of the individual hashes of every file and file chunk (the actual contents of files are chunked so that the chunks can be individually transmitted) and a root hash computed from them. The root hash has the property that it is intractable to come up with two different states that hash to the same root hash and can hence be used to verify the integrity of a certain state relative to a root hash. A similar property holds for the file and chunk hashes in the manifest. However, they are redundant for guaranteeing the integrity of the entire state, as they are also covered by the root hash. The reason why they are included in the manifest nevertheless is to allow for efficiently computing state diffs by comparing file/chunk hashes.

CUPs

Every checkpoint will also be signed on behalf of the subnet by the protocol. This is done by creating and threshold signing a so-called catch up package (CUP). A CUP includes the root hash of the corresponding manifest as well as all the information that is required by a newly joining and/or behind node to resume execution from the respective checkpoint. The signature on the CUP together with the properties of the hash described above guarantees the authenticity of the state.

Remarks

Note that when we point to source code within this article we use links to a specific version of the code to make sure that these links don’t break if the code changes in the future. It is advisable to locate the code that is pointed to in the most recent version and/or the version that is used to verify the artifacts and look at it in this version to avoid missing changes that happened after the publication of this article.

Splitting Process

In more detail a subnet split proceeds as follows.

Create a new halted subnet via NNS proposal. This is the subnet to become subnet B. It should have the same size in terms of number of nodes as the subnet to be split (subnet A) to maintain the same trust assumptions. It is important that it is halted to ensure that it will remain in its genesis state. This is because we will propose to overwrite this subnet’s state later with the split off half of subnet A.
Add canisters to be split off to the migration list (NNS proposal). This is to make other subnets aware that canisters are going to be split off. This will help to react appropriately to messages that are, e.g., expected to come from subnet A according to the routing table but actually come from B or the other way round (note that not all subnets will observe a change of the routing table at the same time).
Halt subnet A at the next CUP/checkpoint (NNS proposal) and add keys that grant the entity executing the split read only access to the state (NNS proposal). Generally this proposal is the same as in the conventional subnet recovery case. The only difference is that it won’t instruct the subnet to halt immediately but at the next CUP. This will ensure that we obtain a state that is signed on behalf of the subnet so that the split can be verified by the community.
Update the routing table (NNS proposal). As soon as a subnet observes this change it will (among others) start routing messages to split off canisters to B. The reason for why this happens after halting subnet A is to ensure that A doesn’t route any new messages to B until it is unhalted again.
Obtain the state of subnet A together with the CUP at the height where it was halted (recall that a read only SSH key was added in step 3). Also obtain a certification of the public key of subnet A issued by the NNS (via a read_state call). Once obtained, split the state into two parts. The first part contains states of canisters that are not split off, as well as the entire subnet-level state of A, such as streams, subnet queues, etc.; this part will be used as the new genesis state of A (we’ll refer to the subnet A with this genesis state as A’). The second state part consists of an empty subnet state plus the canisters split off from A, and will become the new genesis state of subnet B. Both the genesis states of A’ and B will contain the full ingress history, to be pruned in the new subnets’ first execution round. Pruning it beforehand would change the checkpoint file contents and the hashes in the manifest needed for verification of the split would no longer match.
Verify whether each file ended up on the expected subnet and whether their hashes still match. The artifacts to perform the verification will be published during a split. A manifest only contains hashes but no file contents, i.e., any subnet or canister data. Comparing the hashes is sufficient because of the properties of the hash described above and the fact that split is done in a way that either (1) file contents are either not modified during splitting, or (2) the content of the files is fully determined by the split’s input parameters. If this step is successful, one knows which root hashes to expect in the recovery proposals for subnets A’ and B in the next steps.
Perform a subnet recovery for subnets A’ (resp. A) and B with the states obtained in the previous step (series of NNS proposals). The NNS voters should check that the root hashes of the states match the ones obtained in the verification step (details below) to be sure that the states were only split but not otherwise tampered with.
Once it is clear that there are no more messages in any stream to or from subnet A/A’ that may potentially be misrouted, remove the migration list entry (NNS proposal).

To gain confidence that the splitting process doesn’t violate the messaging guarantees that the IC provides to canisters, the above high-level design is accompanied by a formal model written in TLA+. An analysis of the model using the TLC tool found that the design preserves the messaging guarantees.

Verification of Artifacts in Subnet Splitting

As mentioned before, the process is orchestrated via NNS proposals and it will be end-to-end verifiable in the sense that the community will be able to verify whether the states recovered onto the new subnets are indeed the two halves of the initial state before voting on the respective proposals. A description on how to perform this verification is provided on the Verification of Artifacts in Subnet Splitting page.

Additional Useful Material

Template for announcing upcoming subnet splitting proposals