TLDR; This is a proposal for allowing each Action to have a variable-size merkle tree encoding the Action’s tags. This is important for both computational costs and interoperability.
This is a joint proposal with @Michael and @xuyang
Overview of the Current Design
Currently, the Risc0 RM uses a design that encodes the created and consumed tags to be fed as a RL instance input as a tree of a fixed size. This tree is computed by adding the tags in the order as provided by the compliance units.
To put it more concretely in RM-specific terms, we currently start the RM with a parameter ACTION_TREE_DEPTH. When the verifier constructs the instance for the RL in an action, it goes through the tags as ordered by the compliance unit order, adds them up as leaves to a merkle tree of depth ACTION_TREE_DEPTH. Instead of a list of created and consumed tags we have described in the spec currently, the instance now contains the root of the computed tree.
The relevant code can be seen here for Solidity implementation and here for Rust implementation.
Product Requirements
To see how this current state of things is not ideal, let us look at a resource logic that we might be interested in implementing.
In the resource logic, you may be interested to check that the info that is supplied by the prover in the witness actually matches what the verifier puts into the instance. A good example of when this is needed is for burning/minting, you might want to make sure that the action is balanced on its own and that the creation/consumption is (non)ephemeral when needed.
For an even more specific example of a logic that might be interested in that, check the EVM Interop thread where each proposed design required to make sure that there is a specific number of specific resources being created in the same action.
With this said, I consider the need to support this sort of checking of witness/plaintexts-instance/tags to be a product requirement.
How Might This Check Look Like Using Action Tree
Now, how can we check this exact correspondance of witness plaintexts and the root which represents the tags?
One of the evident solutions is to provide merkle paths for each leaf of the tree that the root has, including the empty ones.
This is the solution that seemingly is the canonical one at this point
How This Can Impact Interop
Suppose you launch one RM of Action tree depth 4. Now we start a new one with Action tree depth 3.
This would mean that the circuit (as it is not currently parametrized by the depth of the tree) for a Resource having the check we described above will be different for these two RMs.
What we would be interested in is both of them being capable of using the same circuit here.
Proposal
Parameterize the RL circuits by the depth of the action tree by
- removing the
ACTION_TREE_DEPTHconstant - computing the (non-fixed size) tree going through the action[1] during verification
- putting the depth of that tree into the instance
- RL now using the instance depth info can now know how to verify the paths appropriately.
This allows us to not worry about which depth does a particular resource machine have and even saves gas, without limiting the ammount of resources that can go into a single action.
Concerns
@xuyang is actively looking into whether that can be done on the ZKVM side
NB
If this is possible, then we possibly can make the commitment accumulator variable size! That can drastically cut the cost of execution on the PA for initial users and get rid of the worries regarding merkle tree filling up!
In particular, we start of with a miniscule commitment tree and only make it larger when needed, keeping the depth to a minimum required to contain all the resources.
For the compliance proof to know what depth the path corresponds to, we store not just the historical roots but a map roots => depth showcasing what was the depth of the tree at the time of commitment creation
So that the depth of the tree is the minimal
depthsuch thatnResource <= 2^depthwherenResourceis the number of resources in the given action ↩︎