Basic smt ops
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 key-value pair
A read therefore means locating the leaf
Hence, in addition to
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 zero-node, then the verifier needs only prove the existence of the zero-node, 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,
Case 1: When the key leads to a zero-node¶
The verifier receives the key
Since the least-significant key-bit of the given key,
The task here is to verify that the node is indeed a zero-node.
So the verifier computes the root as follows,
Note that he concatenates
He then checks if
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
The verifier is given; the key
When navigating the tree from
-
The key-bit
leads to the branch . -
Then, from
, the key-bit leads to the leaf , 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
is different from the Remaining Key supplied by the prover.
In proving that
-
Checks the root.
-
Computes the hash of the hashed-value,
. -
Uses the first sibling to compute,
. -
Then, uses the second sibling to compute the root,
. -
Completes the root-check by testing equality,
.
-
-
Checks the keys.
The verifier takes the two Remaining Keys
and , and the key-bits and ;-
Concatenates them as,
and . -
Checks
and . -
Finally shows the inequality,
.
-
This proves that the key
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
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
The verifier is provided with the following data;
- The
. - The least-significant key-bit
. - The second least-significant key-bit
. - The third least-significant key-bit
. - The old hashed value
. - The old root
. - The siblings
, and .
Consider the SMT given in the below figure.
The required step 2 of the update operation involves:
-
Computing the hash of the new value
as; . -
Forming the new leaf by again hashing the hashed value
as; . -
Using the first sibling
to compute, . -
Again, using the second sibling
to compute, . -
Then, uses the third sibling
to compute the root, .
Note that the key-bits are not changed. Therefore, replacing the following old values in the SMT,
The create operation¶
The create operation adds a new leaf
When navigating from the root, the new key
If new key navigates to a zero node¶
That is, the first
The first step is to double-check that indeed the node is a zero node. That is, the verifier performs a Merkle proof starting with either
Once it is established that the new key
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
as, . - Then forming the new leaf,
. - Recomputing all the nodes along the path climbing from the leaf
to the root, including computing the new root.
Example: A create operation at a zero node¶
Note
Inserting a new key-value pair at a Zero Node does not change the topology of the tree.
Suppose a new leaf with the key-value pair
As illustrated in the below figure, the two least-significant key-bits
(a) The lsb,
(b) Whilst the second lsb,
At this stage the verifier checks if this is indeed a zero node;
- First it computes
. - Then it computes
. - And, checks if
equals .
Once the zero-value is checked, the verifier now creates a non-zero leaf with the key-value pair
- It computes the hash of
as, . - It then forms the leaf
. - Also computes
. - And computes
.
An update of these values; the branch
If new key navigates to a non-zero leaf¶
That is, the first
Checking leaf inclusion¶
The first step is to double-check that indeed the value
That is, the verifier performs a Merkle proof starting with either
Once it is established that the value
Extending the SMT¶
Since it is not permissible for two distinct non-zero leaves,
As discussed earlier in this document, when building binary SMTs, the aim is to find a tree-address for the new leaf
So then, for as long as the next corresponding key-bits between
Here’s the general procedure;
- Start with the next least-significant key-bits,
and , and check if or not. - If they are not the same (i.e., if
), then one new extension branch with and as its child-nodes, suffices. - But, if
, then another extension branch needs to be formed. And, the first extension branch is made a parent-node to both and a NULL node “ ”. The key-bit determines whether the NULL node “ ” is on the left or the right. - One then continues with the next least-significant key-bits,
and , and checks if or not. - If
, then the second extension branch , with and as its child-nodes, completes the create operation. - However, if
, then a third extension branch is formed. And, as before, the second extension branch is made a parent-node to both and a NULL node “ ”. And similarly, the key-bit determines whether the NULL node “ ” is on the left or the right. - This procedure (of extending the tree) continues until,
for some . In which case, the -th extension branch , with the and as its child-nodes, 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 key-value pair
Consider the SMT shown in the below figure.
In this example, navigation using the least-significant key-bits,
-
Value-inclusion check.
A value-inclusion check of
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
passes the check, the create operation continues by inserting the new leaf. -
New leaf insertion.
In this example, the new leaf
cannot be inserted at the key-address 01 where is positioned. A branch extension must therefore be done at the address 01 with the leaves and as child-nodes.Since the third least-significant key-bits of
and are not the same, and , the addresses 110 and 010 of the leaves and , 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
. 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,
. - The new leaf,
. - Then,
. - Again,
. - And finally computes,
.
This illustrates how the create operation is performed at a non-zero leaf, when only one branch extension is required.
- The hashed value,
Example: A create operation with multiple branch extensions¶
This example provides an illustration of the create operation at a non-zero leaf, where more than one branch extensions are required.
Suppose a leaf must be created to store a new key-value pair
Consider the SMT shown in the below figure.
Navigating the tree by using the least-significant key-bits,
-
Value-inclusion check.
Before creating the new leaf, it is important to first check if
is indeed included in the root, . Since this amounts to performing a read operation, which has been illustrated in previous examples, we omit here how this is done.Once
passes the value-inclusion check, the create operation proceeds with inserting the new leaf. -
New leaf insertion.
Note that the first and second least-significant key-bits for both
and are the same. That is, and .As a result, the new leaf
cannot be inserted at the key-address 01, where is positioned. An extension branch is formed at the tree-address 01.But, can the leaves
and be child-nodes to ?Since the third least-significant key-bits of
and are the same; that is, ; leaves and cannot be child-nodes to .Another extension branch
is formed at the tree-address 011.Again, since the fourth least-significant key-bits of
and are the same; ; the leaves and cannot be child-nodes to .A third extension branch
is needed at the tree-address 0110.In this case, the fifth least-significant key-bits of
and are different, i.e., and .The leaves
and are now made child-nodes of the extension branch . See the above figure.Once unique addresses for the key-value pairs
and are reached, and the leaf is inserted, all the nodes along the navigation path from the new leaf to the root are updated as follows. -
An update of SMT values.
The verifier computes,
- The hash of the new value,
. - The new leaf,
. - Then,
. - Followed by
. - And,
. - Again,
. - Finally computes,
.
This completes the create operation at an existing leaf where several branch extensions are needed. Note that the create operation at a non-leaf node clearly changes the topology of the tree.
- The hash of the new value,
The delete operation¶
The delete operation refers to a removal of a certain key-value 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 non-zero 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 non-zero sibling-node.
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 sibling-node.
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 least-significant key-bits) matches the key at the leaf (reconstructed from the Remaining Key found at the leaf and the given key-bits).
-
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 zero-node, an update to a zero is performed and the parent-node is turned into a NULL node with no child-nodes.
Delete leaves with non-zero siblings¶
Consider a delete of a key-value pair
Suppose the data provided includes; the Remaining Key
With reference to the figure below, navigation leads to the leaf
Next, perform a Merkle proof to check if the hashed value
- Compute
. - Then
. - And,
. - Check if
equals .
Simultaneously, check if
Since the sibling
- The leaf
is set to “ ”, a zero node. - The parent-node is now,
. - And, the new root,
.
Notice how the SMT maintains its original shape.
Delete leaves with zero siblings¶
Consider deleting a key-value pair
Suppose the data provided includes; the Remaining Key
With reference to the figure below, navigation leads to the leaf
The read step in this case is similar to what is seen in the above case.
The update step depends on the sibling of
That is, the update step of this delete operation concludes as follows;
- The original branch
is now “ ”, a zero node. - The parent-node is now,
. - And, the new root,
.
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 zero-knowledge 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.