View source for Replicated state structure

= This Page is Still Work in Progress =
Each node of the Internet Computer maintains a state. The state includes the data related to canisters, the messages processed by the node, responses generated after processing the messages, etc. A portion of the state is individual to each node (Eg: messages received in the peer-to-peer layer, cryptographic key material). A portion of the state is identical for all the honest nodes in the subnet. This portion of the state is called <b>replicated state</b> of the subnet. In this article, we describe the structure of the replicated state stored on the Internet Computer.

== Per-round Certified State == 
In each consensus round, one of the nodes in the subnet proposes a new block. The nodes in the subnet execute the consensus protocol to finalize one block per consensus round. Finalized blocks are passed onto the <i>message routing</i> layer. Message routing layer routes each message in the block into the appropriate input queue of the target canister. 

For each canister C running on a subnet, there are several input queues. There is one input queue specifically for ingress messages (sent by the external users) to C. For each other canister C′, with whom C communicates, there is one input queue. This input queue is used to store cross-subnet messages received from canister C'. In each round, the execution layer will consume some of the inputs in these queues, update the replicated state of the relevant canisters, and place outputs in <i>ingress history</i> and various output queues. Ingress history is used store the responses generated by the canister on processing ingress messages. For each canister C running on a subnet, there are several output queues. For each other canister C′, with whom C communicates, there is one output queue. This output queue is used to store cross-subnet messages to be sent from C to C'. 

After the round, each node in the subnet stores some relevant information related to the round execution in a tree structure as shown below. The execution layer is designed to execute all the canisters deterministically. Therefore, each node in the subnet should independently create at the same tree. Each node then create a Merkle tree by hashing  the below tree, sign the root hash using their <i>threshold signing key</i>, and broadcast their signature share to rest of the nodes in the subnet. On receiving the signature shares from peers, each node then combines the signature shares to create a <i>signature</i> of the root hash. We now consider the tree as certified by the nodes in the subnet. The below state tree along with its signature is called <i>Per-round certified state</i>. The process of certificate creation can be found in the [https://internetcomputer.org/docs/current/references/ic-interface-spec/#certificate interface spec]. 
[[File:Per-round certified state.png|900px|frameless|left]]
In the above per-round state tree, the internal nodes store a label and are represented by rectangles. The leaves contain data and are represented with rounded boxes. In the per-round state tree, we store the following information. 
* Time - Height of the blockchain for which the tree is generated.
* Metadata - Metadata of the subnet.
* Canister - For each canister running on the subnet, we store its certified state, module hash, controllers and metadata.
** Controllers - Each canister can have a (possibly empty) list of controllers. A controller of a canister has the ability to upgrade, stop or delete the canister. 
** Module hash - Each canister runs a Web Assembly (WASM) module. Module hash is the hash of the module. 
** Metadata - Metadata contains a bunch of key-value pairs. When a WASM module is installed into the canister, the blockchain nodes look into the "Custom Section" of the WASM module and place that data as metadata of the canister. The most common use cases of metadata are to store the candid interface of the canister and git repository link of the canister code. 
** Certified state - When a user sends a query call to the Internet Computer, the message is processed by only one (possibly malicious) blockchain node of the subnet. The response to query calls will not have a certificate and thereby cannot be trusted. To improve the trust in query call responses, Internet Computer has the notion of <i>certified variables</i>. In a nutshell, a canister can a-priori choose to create a certificate for some information and store it in the replicated state. When a user makes a query call later for the information, the canister can directly responds with the information along with its certificate from the replicated state. These certified variable are stored as <i>certified state</i> in the per-round state tree. Note that this <i>certified state</i> is not the entire state of the canister. A canister explicitly chooses a part of its state to be stored as certified state. More details can be found in the [https://internetcomputer.org/docs/current/references/ic-interface-spec/#system-api-certified-data interface spec].
* Subnet - We store some relevant information related to all the other subnets. Specifically, 
* Request data - The request data contains the ingress history generated by the execution layer during the round. For each ingress message processed by the execution layer, the request data stores status, reply, reject code, reject message and error code. More details can be found in the [https://internetcomputer.org/docs/current/references/ic-interface-spec/#state-tree-request-status interface spec].
* Streams - As we run the canisters during the round, a canister C may send a message to another canister C'. Canister C places all its outgoing inter-canister messages in its output queues. After the round, the message routing layer will take the messages in these output queues and place them into <i>subnet-to-subnet streams</i> to be processed by a crossnet transfer protocol, whose job it is to actually transport these messages to other subnets. For each other subnet, we store the cross-subnet messages to be sent to the subnet. 

== Total Replicated State ==

The implementation for the total replicated state can be found on [https://github.com/dfinity/ic/blob/master/rs/replicated_state/src/replicated_state.rs github].