Operations on SMTs
The previous sections have focused on the design of binary SMTs. The problems that cropped up with our initial design have assisted in refining and defining a secure design. While describing the design of binary SMTs, we have extensively utilised the read or get operation.
Now that the basic design is established, the other operations can be delineated. The operations that the storage state machine performs, as per instructions of the main state machine executor, are called storage actions. As mentioned above, the storage state machine verifies whether the operations; create, read, update and delete (CRUD); executed by the main state machine were correctly computed.
The read operation¶
First, we illustrate the read operation, which is in fact a get.
The prover can commit to a keyvalue pair \((K_{\mathbf{x}}, \text{HV}_{\mathbf{x}})\) where \(\text{HV}_{\mathbf{x}}\) is the hash of the value \(V_{\mathbf{x}}\). That is, he claims that he created a leaf \(\mathbf{L}_{\mathbf{x}}\) which contains the value \(V_{\mathbf{x}}\) and it can be located using the key \(K_{\mathbf{x}}\).
A read therefore means locating the leaf \(\mathbf{L}_{\mathbf{x}}\) and verifying that it contains the value \(V_{\mathbf{x}}\) by using a Merkle proof.
Hence, in addition to \((K_{\mathbf{x}}, \text{HV}_{\mathbf{x}})\), prover has to provide the rest of the information needed for completing the Merkle proof. That is, the root, the keybits \(\text{kb}_\mathbf{j}\) for locating the leaf \(\mathbf{L}_{\mathbf{x}}\), the Remaining Key \(\text{RK}_\mathbf{x}\) and all the necessary siblings.
What if the key is not set?¶
The next example demonstrates the read operation when a key is not set in the tree. That is, it illustrates how to check whether a value is not on a given SMT.
There are two cases that can occur. The given key may lead either to a zero node or to an existing leaf.
If the given key leads to a zeronode, then the verifier needs only prove the existence of the zeronode, and this would sufficiently prove that the key is not set.
But if the given key leads to an existing leaf, the verifier has to prove the leaf exists in the SMT and show that the given key is not the same as the actual key associated with the value at the leaf.
When The key is not set¶
Suppose the verifier needs to prove that the keys, \(K_{\mathbf{x}} = 11010101\) and \(K_{\mathbf{z}} = 10101010\) are not set in the SMT depicted in the figure below.
Case 1: When the key leads to a zeronode¶
The verifier receives the key \(K_{\mathbf{x}}\), the remaining key \(\text{RK}_\mathbf{x} = 1101010\), the leastsignificant keybit \(\text{kb}_0 = 1\), and the sibling \(\mathbf{{S}_{1}} = \mathbf{{B}_{\mathbf{ab}}}\).
Since the leastsignificant keybit of the given key, \(\text{kb}_0 = 1\), navigation from the root leads to the rightside, to the zeronode. See the node circled in a green colour, in the above figure.
The task here is to verify that the node is indeed a zeronode.
So the verifier computes the root as follows, \(\mathbf{{\tilde{root}}_{ab0}} = \mathbf{H_{noleaf}} (\mathbf{{S}_{1}} \ \mathbf{0} ) = \mathbf{H}( \mathbf{{B}_{\mathbf{ab}}} \ \mathbf{0} )\).
Note that he concatenates \(\mathbf{{S}_{1}}\) and \(\mathbf{0}\) in the given ordering, because \(\text{kb}_0 = 1\).
He then checks if \(\mathbf{{\tilde{root}}_{ab0}} = \mathbf{{root}_{ab0}}\). If this is true, then he concludes that the given key is not set.
Case 2: When the key leads to an existing leaf¶
Consider again the SMT depicted in the above figure, and suppose that the prover claims that the key \(K_{\mathbf{z}} = 10101010\) is set.
The verifier is given; the key \(K_{\mathbf{z}} = 10101010\), the Remaining Key \(\text{RK}_{\mathbf{z}} = 101010\), the leastsignificant keybit \(\text{kb}_0 = 0\), the second leastsignificant keybit \(\text{kb}_{\mathbf{1}} = 1\), and the siblings \(\mathbf{{S}_{1}} = \mathbf{L}_{a}\) and \(\mathbf{{S}_{2}} = \mathbf{0}\).
When navigating the tree from \(\mathbf{{root}_{ab0}}\), using the keybits \(\text{kb}_{\mathbf{0}} = 0\) and \(\text{kb}_{\mathbf{1}} = 1\), and with reference to the above figure,

The keybit \(\text{kb}_{\mathbf{0}} = 0\) leads to the branch \(\mathbf{{B}_{\mathbf{ab}}}\).

Then, from \(\mathbf{{B}_{\mathbf{ab}}}\), the keybit \(\text{kb}_{\mathbf{1}} = 1\) leads to the leaf \(\mathbf{L}_\mathbf{b}\), which is the leaf circled in brown in the above figure.
Since the key navigates to a leaf, the verifier’s task is to prove two things simultaneously;
 The leaf is in the SMT described in the above figure, and
 The Remaining Key at the leaf \(\mathbf{L}_\mathbf{b}\) is different from the Remaining Key supplied by the prover.
In proving that \(\mathbf{L}_{\mathbf{b}}\) is indeed in the tree, the verifier carries out the following tasks simultaneously;

Checks the root.

Computes the hash of the hashedvalue, \(\mathbf{ \tilde{L} }_{\mathbf{b}} = \mathbf{H_{leaf}} ( \text{RK}_{\mathbf{b}} \ \text{HV}_{\mathbf{b}} )\).

Uses the first sibling to compute, \(\mathbf{{\tilde{B}}_{\mathbf{ab}}} = \mathbf{H_{noleaf}} \big( \mathbf{L}_{\mathbf{a}} \ \mathbf{ \tilde{L}}_{\mathbf{b}} \big)\).

Then, uses the second sibling to compute the root, \(\mathbf{\tilde{root}}_{ab0} = \mathbf{H_{noleaf}} \big( \mathbf{{\tilde{B}}_{\mathbf{ab}}} \ \mathbf{0} \big)\).

Completes the rootcheck by testing equality, \(\mathbf{\tilde{root}}_{ab0} = \mathbf{{root}}_{ab0}\).


Checks the keys.
The verifier takes the two Remaining Keys \(\text{RK}_{\mathbf{x}}\) and \(\text{RK}_{\mathbf{b}}\), and the keybits \(\text{kb}_0\) and \(\text{kb}_{\mathbf{1}}\);

Concatenates them as, \(\tilde{K}_{\mathbf{x}} = \text{RK}_{\mathbf{x}} \ \text{kb}_0 \ \text{kb}_{\mathbf{1}}\) and \(\tilde{K}_{\mathbf{b}} = \text{RK}_{\mathbf{b}} \ \text{kb}_0 \ \text{kb}_{\mathbf{1}}\).

Checks \(\tilde{K}_{\mathbf{x}} = K_{\mathbf{x}}\) and \(\tilde{K}_{\mathbf{b}} = K_{\mathbf{b}}\).

Finally shows the inequality, \(\tilde{K}_{\mathbf{x}} \neq K_{\mathbf{b}}\).

This proves that the key \(K_{\mathbf{x}}\) is not set.
Info
The last check, where the verifier checks inequality of keys, turns out to be very expensive to implement. A much more smarter method is used in the storage state machine.
The update operation¶
The update operation does not change the topology of the tree. When carrying out the update, it is therefore important to retain all labels of nodes.
The update process entails the following;
First, the verifier needs to be provided with the following data, i.e., the remaining key \(\text{RK}\), the leastsignificant keybits, the new value, the old value, the old root and the siblings.
Step 1. Checking a read of the current value with the old root. That is, checking that the leaf exists in the tree, and it was included in calculating the old root.
Step 2. Recomputing (updating) all nodes along the path, from the leaf to the root, as well as computing the new root with the newly updated nodes.
The verifier can continue with step 2 only if all the checks in step 1 pass verification.
For the update operation, step 1 is exactly the same as the read operation. We therefore focus on illustrating step 2.
Example: An update operation¶
Suppose the set key is \(K_{\mathbf{c}} = 10110100\) corresponding to the old value \(V_{\mathbf{c}}\), and the new value is \(V_\mathbf{new}\).
The verifier is provided with the following data;
 The \(\text{RK}_{\mathbf{c}} = 10110\).
 The leastsignificant keybit \(\text{kb}_0 = 0\).
 The second leastsignificant keybit \(\text{kb}_1 = 0\).
 The third leastsignificant keybit \(\text{kb}_2 = 1\).
 The old hashed value \(\text{HV}_{\mathbf{c}}\).
 The old root \(\mathbf{{root}_{ab..f }}\).
 The siblings \(\mathbf{{S}_{1}} = \mathbf{{S}_{\mathbf{ab}}}\), \(\mathbf{{S}_{2}} = \mathbf{{L}_{d}}\) and \(\mathbf{{S}_{3}} = \mathbf{{S}_{\mathbf{ef}}}\).
Consider the SMT given in the below figure.
The required step 2 of the update operation involves:

Computing the hash of the new value \(V_\mathbf{new}\) as; \(\text{HV}_{\mathbf{new}} = \mathbf{H_{noleaf}}(V_\mathbf{new})\).

Forming the new leaf by again hashing the hashed value \(\text{HV}_{\mathbf{new}}\) as; \(\mathbf{ \tilde{L} }_{\mathbf{new}} = \mathbf{H_{leaf}}( \text{RK}_{\mathbf{new}} \ \text{HV}_{\mathbf{new}} )\).

Using the first sibling \(\mathbf{{S}_{1}} = \mathbf{{S}_{\mathbf{ab}}}\) to compute, \(\mathbf{{\bar{B}}_{abc}} = \mathbf{H_{noleaf}} \big( \mathbf{{S}_{\mathbf{ab}}} \ \mathbf{ \tilde{L}}_{\mathbf{new}} \big)\).

Again, using the second sibling \(\mathbf{{S}_{2}} = \mathbf{{L}_{d}}\) to compute, \(\mathbf{{\bar{B}}_{\mathbf{abcd}}} = \mathbf{H_{noleaf}} \big( \mathbf{{\bar{B}}_{abc}} \ \mathbf{{L}_{d}} \big)\).

Then, uses the third sibling \(\mathbf{{S}_{3}} = \mathbf{{S}_{\mathbf{ef}}}\) to compute the root, \(\mathbf{{{root}}_{\mathbf{new}}} = \mathbf{H_{noleaf}} \big( \mathbf{{\bar{B}}_{\mathbf{abcd}}} \ \mathbf{{S}_{\mathbf{ef}}}\big)\).
Note that the keybits are not changed. Therefore, replacing the following old values in the SMT, \(\text{HV}_\mathbf{c}, \mathbf{{B}_{abc}}, \mathbf{{B}_{abcb}}, \mathbf{{root}_{ab..f } }\), with the new ones, \(\text{HV}_\mathbf{new}, \mathbf{{\bar{B}}_{abc}}, \mathbf{{\bar{B}}_{abcb}}, \mathbf{{root}_{new } }\), respectively, completes the update operation.
The create operation¶
The create operation adds a new leaf \(\mathbf{L_{\mathbf{new}}}\) to the SMT in order to insert and store a new keyvalue pair \(( \mathbf{{K_{new}}} , \mathbf{V_{\mathbf{new}}} )\) at \(\mathbf{L_{\mathbf{new}}}\), where the key \(\mathbf{K_{new}}\) was never used in the SMT and thus is uniquely associated with the leaf \(\mathbf{L_{new}}\).
When navigating from the root, the new key \(\mathbf{K_{new}}\) can lead to either a zero node or an existing leaf. This results in two scenarios as discussed below.
If new key navigates to a zero node¶
That is, the first \(l\) leastsignificant bits of the key \(\mathbf{K_{new}}\) leads to a zero node, where \(l\) is the levels to root of the zero node.
The first step is to doublecheck that indeed the node is a zero node. That is, the verifier performs a Merkle proof starting with either \(\mathbf{H_{noleaf}} ( \mathbf{S_1} \ \mathbf{0} )\) or \(\mathbf{H_{noleaf}} ( \mathbf{0} \ \mathbf{S_1} )\), depending on whether the sibling of the zeronode is on the right (the edge corresponding to a keybit \(1\)) or on the left (the edge corresponding to a keybit \(0\)), respectively.
Once it is established that the new key \(\mathbf{K_{new}}\) has led to a zero node, the verifier simply changes the zero node to the leaf \(\mathbf{L_{new}}\) that stores the value \(\mathbf{V_{new}}\).
The create operation, in this case, therefore boils down to an update operation on the zero node. It amounts to;
 Computing the hash of the new value \(V_\mathbf{new}\) as, \(\text{HV}_{\mathbf{new}} = \mathbf{H_{noleaf}}(V_\mathbf{new})\).
 Then forming the new leaf, \(\mathbf{L_{new}} = \mathbf{H_{leaf}}( \text{RK}_{\mathbf{new}} \ \text{HV}_{\mathbf{new}})\).
 Recomputing all the nodes along the path climbing from the leaf \(\mathbf{L_{new}}\) to the root, including computing the new root.
Example: A create operation at a zero node¶
Note
Inserting a new keyvalue pair at a Zero Node does not change the topology of the tree.
Suppose a new leaf with the keyvalue pair \(\big(K_{\mathbf{new}}, \text{V}_{\mathbf{new}}\big)\), where \(K_{\mathbf{new}} = 11010110\), needs to be created.
As illustrated in the below figure, the two leastsignificant keybits \(\text{kb}_0 = 0\) and \(\text{kb}_1 = 1\), lead to a zero node. That is, navigating from the root;
(a) The lsb, \(\text{kb}_{0} = 0\) leads to the node \(\mathbf{{B}_{ab0}}\).
(b) Whilst the second lsb, \(\text{kb}_{1} = 1\) leads to a zero node.
At this stage the verifier checks if this is indeed a zero node;
 First it computes \(\mathbf{{\tilde{B}}_{ab0}} = \mathbf{H_{noleaf}} \big( \mathbf{{S}_{\mathbf{ab}}} \ \mathbf{0} \big)\).
 Then it computes \(\mathbf{{\tilde{root}}_{ab0c}} = \mathbf{H_{noleaf}} \big( \mathbf{{\tilde{B}}_{ab0}} \ \mathbf{L_{c}} \big)\).
 And, checks if \(\mathbf{{\tilde{root}}_{ab0c}}\) equals \(\mathbf{{root}_{ab0c}}\).
Once the zerovalue is checked, the verifier now creates a nonzero leaf with the keyvalue pair \(\big( \mathbf{K_{new}} , \text{HV}_{\mathbf{new}}\big)\).
 It computes the hash of \(\text{V}_{\mathbf{new}}\) as, \(\text{HV}_{\mathbf{new}} = \mathbf{H_{noleaf}}(V_\mathbf{new})\).
 It then forms the leaf \(\mathbf{L_{new}} = \mathbf{H_{leaf}}( \text{RK}_{\mathbf{new}} \ \text{HV}_{\mathbf{new}})\).
 Also computes \(\mathbf{B_{new}} = \mathbf{H_{noleaf}} ( \mathbf{{S}_{\mathbf{ab}}} \ \mathbf{L_{new}})\).
 And computes \(\mathbf{{root}_{new}} = \mathbf{H_{noleaf}} ( \mathbf{B_{new}} \ \mathbf{L_{c}} )\).
An update of these values; the branch \(\mathbf{B_{ab0}}\) to \(\mathbf{B_{new}}\) and the old root \(\mathbf{{root}_{ab0c}}\) to \(\mathbf{{root}_{new}}\); completes the create operation.
If new key navigates to a nonzero leaf¶
That is, the first \(\mathbf{l}\) leastsignificant bits of the key \(\mathbf{K_{new}}\) leads to a nonzero leaf \(\mathbf{L_z}\), where \(\mathbf{l}\) is \(\mathbf{L_z}\)’s number of levels to root. This means, the keys \(\mathbf{K_{new}}\) and \(\mathbf{K_{z}}\) share a common string of leastsignificant keybits, which is \(\mathbf{l}\) bits long.
Checking leaf inclusion¶
The first step is to doublecheck that indeed the value \(V_\mathbf{z}\) stored at the leaf \(\mathbf{L_z}\) is indeed included in the root.
That is, the verifier performs a Merkle proof starting with either \(\mathbf{H_{noleaf}} ( \mathbf{S_1} \ \mathbf{L_z} )\) or \(\mathbf{H_{noleaf}} ( \mathbf{L_z} \ \mathbf{S_1} )\), for some sibling \(\mathbf{S_1}\). The ordering of the hash arguments depends on whether the sibling of the leaf \(\mathbf{L_z}\) is on the left (the edge corresponding to a keybit \(0\)) or on the right (the edge corresponding to a keybit \(1\)), respectively. The check of valueinclusion gets completed by climbing the tree as usual.
Once it is established that the value \(V_\mathbf{z}\) stored at the leaf \(\mathbf{L_z}\) is included in the root, the new leaf \(\mathbf{L_{new}}\) storing the keyvalue pair can now be created.
Extending the SMT¶
Since it is not permissible for two distinct nonzero leaves, \(\mathbf{L_{new}}\) and \(\mathbf{L_z}\), to share a treeaddress, a create operation at \(\mathbf{L_z}\) results in extending the tree; by adding a new branch \(\mathbf{B_{ext1}}\) at the treeaddress where \(\mathbf{L_z}\) has been positioned.
As discussed earlier in this document, when building binary SMTs, the aim is to find a treeaddress for the new leaf \(\mathbf{L_{new}}\) which differs from the treeaddress of any existing leaf \(\mathbf{L_z}\).
So then, for as long as the next corresponding keybits between \(\mathbf{K_{new}}\) and \(\mathbf{K_{z}}\) coincide, a new extension branch needs to be formed.
Here’s the general procedure;
 Start with the next leastsignificant keybits, \(\text{kb}_\mathbf{(l+1)new}\) and \(\text{kb}_\mathbf{(l+1)z}\), and check if \(\text{kb}_\mathbf{(l+1)new} = \text{kb}_\mathbf{(l+1)z}\) or not.
 If they are not the same (i.e., if \(\text{kb}_\mathbf{(l+1)new} \neq \text{kb}_\mathbf{(l+1)z}\)), then one new extension branch \(\mathbf{B_{ext1}}\) with \(\mathbf{L_{new}}\) and \(\mathbf{L_{z}}\) as its childnodes, suffices.
 But, if \(\text{kb}_\mathbf{(l+1)new} = \text{kb}_\mathbf{(l+1)z}\), then another extension branch \(\mathbf{B_{ext2}}\) needs to be formed. And, the first extension branch \(\mathbf{B_{ext1}}\) is made a parentnode to both \(\mathbf{B_{ext2}}\) and a NULL node “\(\mathbf{0}\)”. The keybit \(\text{kb}_\mathbf{(l+1)new}\) determines whether the NULL node “\(\mathbf{0}\)” is on the left or the right.
 One then continues with the next leastsignificant keybits, \(\text{kb}_\mathbf{(l+2)new}\) and \(\text{kb}_\mathbf{(l+2)z}\), and checks if \(\text{kb}_\mathbf{(l+2)new} = \text{kb}_\mathbf{(l+2)z}\) or not.
 If \(\text{kb}_\mathbf{(l+2)new} \neq \text{kb}_\mathbf{(l+2)z}\) , then the second extension branch \(\mathbf{B_{ext2}}\), with \(\mathbf{L_{new}}\) and \(\mathbf{L_{z}}\) as its childnodes, completes the create operation.
 However, if \(\text{kb}_\mathbf{(l+2)new} = \text{kb}_\mathbf{(l+2)z}\), then a third extension branch \(\mathbf{B_{ext3}}\) is formed. And, as before, the second extension branch \(\mathbf{B_{ext2}}\) is made a parentnode to both \(\mathbf{B_{ext3}}\) and a NULL node “\(\mathbf{0}\)”. And similarly, the keybit \(\text{kb}_\mathbf{(l+2)new}\) determines whether the NULL node “\(\mathbf{0}\)” is on the left or the right.
 This procedure (of extending the tree) continues until, \(\text{kb}_\mathbf{(l+j)new} \neq \text{kb}_\mathbf{(l+j)z}\) for some \(j > 2\). In which case, the \(\mathbf{(l + j)}\)th extension branch \(\mathbf{B_{ext(l + j)}}\), with the \(\mathbf{L_{new}}\) and \(\mathbf{L_{z}}\) as its childnodes, completes the create operation.
An update of values¶
The create operation is actually only complete once all the values on the navigation path from the new root to the new leaf are updated.
Example: A create operation with single branch extension¶
Suppose a leaf needs to be created to store a new keyvalue pair \(\big({K_{\mathbf{new}}\ } , V_\mathbf{{new}}\big)\), where \(K_{\mathbf{new}} = 11010110\).
Consider the SMT shown in the below figure.
In this example, navigation using the leastsignificant keybits, \(\text{kb}_\mathbf{0} = 0\) and \(\text{kb}_\mathbf{1} = 1\), leads to an existing leaf \(\mathbf{L_{\mathbf{c}}}\). And the keyvalue pair \((V_\mathbf{\mathbf{c}}, \text{HV}_\mathbf{\mathbf{c}})\) stored at \(\mathbf{L_{\mathbf{c}}}\) has the key \(K_{\mathbf{c}} = 11010010\).

Valueinclusion check.
A valueinclusion check of \(V_\mathbf{\mathbf{c}}\) is performed before creating any new leaf. Since this amounts to a read operation, which has been illustrated in previous examples, we omit how this is done here.
Once \(V_\mathbf{\mathbf{c}}\) passes the check, the create operation continues by inserting the new leaf.

New leaf insertion.
In this example, the new leaf \(\mathbf{L_{new}}\) cannot be inserted at the keyaddress 01 where \(\mathbf{L_{\mathbf{c}}}\) is positioned. A branch extension \(\mathbf{{B}_{ext}}\) must therefore be done at the address 01 with the leaves \(\mathbf{L_{new}}\) and \(\mathbf{L_{c}}\) as childnodes.
Since the third leastsignificant keybits of \(K_{\mathbf{new}}\) and \(K_{\mathbf{c}}\) are not the same, \(\text{kb}_\mathbf{2new} = 1\) and \(\text{kb}_\mathbf{2c} = 0\), the addresses 110 and 010 of the leaves \(\mathbf{L_{new}}\) and \(\mathbf{L_{c}}\), respectively, are distinct.
Therefore, no further extension is necessary. And the create operation is complete by updating all the values on the navigation path.
The next process, after forming the branch extension, is to update all the nodes along the path from the root to the new leaf \(\mathbf{L_{new}}\). The verifier follows the steps of the update operation to accomplish this.

An update of SMT values.
The verifier computes the following,
 The hashed value, \(\text{HV}_{\mathbf{new}} = \mathbf{H_{noleaf}}(V_\mathbf{new})\).
 The new leaf, \(\mathbf{L_{new}} = \mathbf{H_{leaf}} ( \text{RK}_{\mathbf{new}} \ \text{HV}_{\mathbf{new}})\).
 Then, \(\mathbf{B_{ext}} = \mathbf{H_{noleaf}} ( \mathbf{L_{c}} \ \mathbf{L_{new}})\).
 Again, \(\mathbf{B_{new}} = \mathbf{H_{noleaf}}( \mathbf{S_{ab}} \ \mathbf{B_{ext}} )\).
 And finally computes, \(\mathbf{{root}_{new}} = \mathbf{H_{noleaf}}( \mathbf{B_{new}} \ \mathbf{L_{d}} )\).
This illustrates how the create operation is performed at a nonzero leaf, when only one branch extension is required.
Example: A create operation with multiple branch extensions¶
This example provides an illustration of the create operation at a nonzero leaf, where more than one branch extensions are required.
Suppose a leaf must be created to store a new keyvalue pair \(\big(K_{\mathbf{new}}, V_\mathbf{new}\big)\), where \(K_{\mathbf{new}} = 11010110\).
Consider the SMT shown in the below figure.
Navigating the tree by using the leastsignificant keybits, \(\text{kb}_\mathbf{0} = 0\) and \(\text{kb}_\mathbf{1} = 1\), leads to an existing leaf \(\mathbf{L_{\mathbf{c}}}\). In this example, suppose the keyvalue pair \((K_{\mathbf{c}}, \text{HV}_\mathbf{\mathbf{c}})\) stored at \(\mathbf{L_{\mathbf{c}}}\) has the key \(K_{\mathbf{c}} = 11100110\).

Valueinclusion check.
Before creating the new leaf, it is important to first check if \(V_\mathbf{\mathbf{c}}\) is indeed included in the root, \(\mathbf{root}_\mathbf{abcd}\). Since this amounts to performing a read operation, which has been illustrated in previous examples, we omit here how this is done.
Once \(V_\mathbf{\mathbf{c}}\) passes the valueinclusion check, the create operation proceeds with inserting the new leaf.

New leaf insertion.
Note that the first and second leastsignificant keybits for both \(K_\mathbf{new}\) and \(K_\mathbf{c}\) are the same. That is, \(\text{kb}_\mathbf{0new} = 0 = \text{kb}_\mathbf{0c}\) and \(\text{kb}_\mathbf{1new} = 1 = \text{kb}_\mathbf{1c}\).
As a result, the new leaf \(\mathbf{L_{new}}\) cannot be inserted at the keyaddress 01, where \(\mathbf{L_{\mathbf{c}}}\) is positioned. An extension branch \(\mathbf{{B}_{ext1}}\) is formed at the treeaddress 01.
But, can the leaves \(\mathbf{L_{new}}\) and \(\mathbf{L_{c}}\) be childnodes to \(\mathbf{{B}_{ext1}}\)?
Since the third leastsignificant keybits of \(K_\mathbf{new}\) and \(K_\mathbf{c}\) are the same; that is, \(\text{kb}_\mathbf{2new} = 1 = \text{kb}_\mathbf{2c}\); leaves \(\mathbf{L_{new}}\) and \(\mathbf{L_{c}}\) cannot be childnodes to \(\mathbf{{B}_{ext1}}\).
Another extension branch \(\mathbf{{B}_{ext2}}\) is formed at the treeaddress 011.
Again, since the fourth leastsignificant keybits of \(K_\mathbf{new}\) and \(K_\mathbf{c}\) are the same; \(\text{kb}_\mathbf{3new} = 0 = \text{kb}_\mathbf{3c}\); the leaves \(\mathbf{L_{new}}\) and \(\mathbf{L_{c}}\) cannot be childnodes to \(\mathbf{{B}_{ext2}}\).
A third extension branch \(\mathbf{{B}_{ext3}}\) is needed at the treeaddress 0110.
In this case, the fifth leastsignificant keybits of \(K_\mathbf{new}\) and \(K_\mathbf{c}\) are different, i.e., \(\text{kb}_\mathbf{4new} = 1\) and \(\text{kb}_\mathbf{4c} = 0\).
The leaves \(\mathbf{L_{new}}\) and \(\mathbf{L_{c}}\) are now made childnodes of the extension branch \(\mathbf{{B}_{ext3}}\). See the above figure.
Once unique addresses for the keyvalue pairs \(\big( K_{\mathbf{c}} , V_\mathbf{c} \big)\) and \(\big( K_\mathbf{{new}} , V_{\mathbf{new}}\big)\) are reached, and the leaf \(\mathbf{L_{new}}\) is inserted, all the nodes along the navigation path from the new leaf \(\mathbf{L_{new}}\) to the root are updated as follows.

An update of SMT values.
The verifier computes,
 The hash of the new value, \(\text{HV}_\mathbf{new} = \mathbf{H_{noleaf}}(V_\mathbf{new})\).
 The new leaf, \(\mathbf{L_{new}} = \mathbf{H_{leaf}} ( \text{RK}_{\mathbf{new}} \ \text{HV}_{\mathbf{new}})\).
 Then, \(\mathbf{B_{ext3}} = \mathbf{H_{noleaf}}( \mathbf{L_{c}} \ \mathbf{L_{new}})\).
 Followed by \(\mathbf{B_{ext2}} = \mathbf{H_{noleaf}}( \mathbf{B_{ext3}} \ \mathbf{0} )\).
 And, \(\mathbf{B_{ext1}} = \mathbf{H_{noleaf}}( \mathbf{0} \ \mathbf{B_{ext2}} )\).
 Again, \(\mathbf{B_{new}} = \mathbf{H_{noleaf}}( \mathbf{S_{ab}} \ \mathbf{B_{ext2}} )\).
 Finally computes, \(\mathbf{{root}_{new}} = \mathbf{H_{noleaf}}( \mathbf{B_{new}} \ \mathbf{L_{d}} )\).
This completes the create operation at an existing leaf where several branch extensions are needed. Note that the create operation at a nonleaf node clearly changes the topology of the tree.
The delete operation¶
The delete operation refers to a removal of a certain keyvalue pair from a binary SMT. It is in fact the reverse of the create operation.
There are two types of scenarios that can occur when executing a delete operation.
There is a scenario where a delete operation is equivalent to an update operation of a nonzero leaf to a NULL leaf. In this case the topology of the SMT does not change. This occurs when the leaf being deleted has a nonzero siblingnode.
On the other hand, a delete operation can be tantamount to the reverse of a create operation where extension branches are removed from the tree. The topology of the SMT can drastically change. This scenario occurs when the leaf being removed has a zero siblingnode.
A delete operation involves two main steps;

A read of the value to be deleted is executed. That is,
 Navigating to the value.
 Checking if the value is included in the root.
 Checking if the given key (reconstructed from the given Remaining Key and the leastsignificant keybits) matches the key at the leaf (reconstructed from the Remaining Key found at the leaf and the given keybits).

This step depends on whether the sibling of the leaf to be deleted is zero or not;
 If the sibling is not a zero node, an update to a zero is performed.
 If the sibling is a zeronode, an update to a zero is performed and the parentnode is turned into a NULL node with no childnodes.
Delete leaves with nonzero siblings¶
Consider a delete of a keyvalue pair \(\big(K_{\mathbf{b}} , V_\mathbf{b} \big)\) where its leaf \(\mathbf{L_b}\) has a nonzero node sibling.
Suppose the data provided includes; the Remaining Key \(\tilde{\text{RK}}_{\mathbf{b}}\), the leastsignificant keybits \(\text{kb}_0 = 0\) and \(\text{kb}_1 = 1\), the root \(\mathbf{{root}_{abc}}\), and the sibling \(\mathbf{L_a}\) which is not a zero node and the leaf \(\mathbf{L_c}\).
With reference to the figure below, navigation leads to the leaf \(\mathbf{L_b}\).
Next, perform a Merkle proof to check if the hashed value \(\text{HV}_\mathbf{b}\) at \(\mathbf{L_b}\) is included in the given root;
 Compute \(\tilde{\mathbf{L}}_\mathbf{b} = \mathbf{H_{leaf}} ( \text{RK}_{\mathbf{b}} \ \text{HV}_\mathbf{b} )\).
 Then \(\tilde{\mathbf{B}}_\mathbf{ab} = \mathbf{H_{noleaf}} ( \mathbf{L_a} \ \tilde{\mathbf{L}}_\mathbf{b})\).
 And, \(\tilde{\mathbf{root}}_\mathbf{abc} = \mathbf{H_{noleaf}} ( \tilde{\mathbf{B}}_\mathbf{ab} \ \mathbf{L_c} )\).
 Check if \(\tilde{\mathbf{root}}_\mathbf{abc}\) equals \(\mathbf{{root}_{abc}}\).
Simultaneously, check if \(\tilde{K}_{\mathbf{b}}\) equals \(\text{K}_{\mathbf{b}}\), where \(\tilde{K}_{\mathbf{b}} = \tilde{\text{RK}}_{\mathbf{b}} \ \text{kb}_1 \ \text{kb}_0\) and \(\text{K}_{\mathbf{b}} = \text{RK}_{\mathbf{b}} \ \text{kb}_1 \ \text{kb}_0\) are keys reconstructed while climbing the tree.
Since the sibling \(\mathbf{L_a}\) is not a zero node, the hashed value \(\text{HV}_\mathbf{b}\) found at the leaf \(\mathbf{L_b}\) is _update_d to a zero. And the values along the navigation path are also _update_d accordingly. That is,
 The leaf \(\mathbf{L_b}\) is set to “\(\mathbf{0}\)”, a zero node.
 The parentnode is now, \(\mathbf{B_{a0}} = \mathbf{H_{noleaf}} ( \mathbf{L_a} \ \mathbf{0} )\).
 And, the new root, \(\mathbf{{root}_{abc}} = \mathbf{H_{noleaf}}(\mathbf{B_{a0}} \ \mathbf{L_a})\).
Notice how the SMT maintains its original shape.
Delete leaves with zero siblings¶
Consider deleting a keyvalue pair \(\big(K_{\mathbf{c}} , V_\mathbf{c} \big)\) where its leaf \(\mathbf{L_c}\) has a zeronode sibling.
Suppose the data provided includes; the Remaining Key \(\tilde{\text{RK}}_{\mathbf{c}}\), the leastsignificant keybits \(\text{kb}_0 = 0\), \(\text{kb}_1 = 1\) and \(\text{kb}_2 = 1\), the root \(\mathbf{{root}_{a0cd}}\), and the sibling “\(\mathbf{0}\)” which is a zero node, and the leaves \(\mathbf{L_a}\) and \(\mathbf{L_d}\).
With reference to the figure below, navigation leads to the leaf \(\mathbf{L_c}\).
The read step in this case is similar to what is seen in the above case.
The update step depends on the sibling of \(\mathbf{L_c}\). Since the sibling is \(\mathbf{0}\), an update of \(\mathbf{L_c}\) to zero results in the branch \(\mathbf{B_{0c}}\) having two zero nodes as childnodes. Since \(\mathbf{H_{noleaf}} ( \mathbf{0} \ \mathbf{0}) = 0\), it is therefore expedient to turn the branch \(\mathbf{B_{0c}}\) into a zero node with no childnodes.
That is, the update step of this delete operation concludes as follows;
 The original branch \(\mathbf{B_{0c}}\) is now “\(\mathbf{0}\)”, a zero node.
 The parentnode is now, \(\mathbf{B_{a0}} = \mathbf{H_{noleaf}} ( \mathbf{L_a} \ \mathbf{0} )\).
 And, the new root, \(\mathbf{{root}_{a0d}} = \mathbf{H_{noleaf}}(\mathbf{B_{a0}} \ \mathbf{L_d})\).
Notice that in this example, the delete operation alters the topology of the SMT.
Conclusion¶
The operations discussed in this document are in fact the very actions the main state machine instructs the storage state machine to perform.
The prover and the verifier, as used in the above explanations, can loosely be interpreted as the executor of the storage state machine and the storage SM’s PIL code, respectively. The zeroknowledge Assembly (zkASM) of the storage state machine plays the facilitator’s role.
The zkASM is the interpreter between the storage state machine and the main state machine, also between the storage state machine and the Poseidon state machine. The two hash functions used in building the storage binary SMTs, are special versions of the Poseidon family of hash functions.