Proposal for Variable-Size Action Tree Depth

RM
1

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

  1. removing the ACTION_TREE_DEPTH constant
  2. computing the (non-fixed size) tree going through the action[1] during verification
  3. putting the depth of that tree into the instance
  4. 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

  1. So that the depth of the tree is the minimal depth such that nResource <= 2^depth where nResource is the number of resources in the given action ↩︎

5 Likes
Resource machine optimization explorations
2

Thanks for sharing,

So that the depth of the tree is the minimal depth such that nResource <= 2^depth where nResource is the number of resources in the given action

Merkle trees are great for checking membership of a single or few leaves. In this case, we want to bundle all resources together.

I wonder if using a chained hash instead of checking membership for all is possible in the current RM. Seems that would simplify and speed up the design. For example, for 3 resources in an action, root=Hash(R3,Hash(R2,Hash(R1))), or even root = Hash(R1,R2,R3)

2 Likes
3

Sounds interesting! But we need then to decide what we are most interested in: proving that witness and instance data correspond in terms of tags-plaintexts or proving inclusion?

Ping @xuyang, @Michael for visibility

1 Like
4

It changes the semantic from caring about individual leaves (resources) to enforcedly considering all leaves’ existence in resource logic.

With a Merkle tree, we don’t need to worry about the order or position of leaves—only about proving their inclusion in the tree. However, when using a chained or simple hash of all leaves, the order matters. This creates a problem: when designing the logic circuit, we can’t predict the order of a resource in a new action, and different resources may conflict when combined. For example, the resource A takes the R1 position in logic circuit while resource B could also take the R1. A possible approach is to add an argument for each leave to describe its variable position and sort them, though this would complicate the process. Do you have a better way to support variable ordering in a chained hash?

2 Likes
5

If resources in a given action share the same execution context, then this should be always the case. However, the specs leave room to interpretation when it says “when proving, resource logics take as input resources created and consumed in that action”; the input resources could be taken to be a strict subset of the resources in the action.

In a way, the Merkle tree approach is more aligned with actions being “the union of the execution contexts” of the participating resources[1].

I’m sure I’m missing something that is clear to you. In my incomplete view, the ordering is how they are listed in the action. This is also how currently the leaves of the tree are ordered. Define the chain as the ordered sequence of the resource digests appearing in the action. If there are 4 resources, the chain has 4 digests. For a given logic, you pass the chain as witness[2], and for each witness resource you also pass the position it occupies in the chain, so its digest can be checked against. Similarly as now it is passed the Merkle path (which is position-aware) for each witness resource.

Regarding efficiency. The logic will output the hash of the chain, instead of checking all Merkle paths as done now. If there are 2^d resources, checking all Merkle paths needs d2^d hashes, and a chained-hash needs 2^d -1 hashes. Asymptotically speaking there is no significant improvement. But concretely speaking, if e.g. d=4 as in the code now, then we go from 64 hashes to 15 hashes. Also there is the question of padding. For example for 9 resources, we go from 36 = 4 * 9 hashes to 8. (Here, of course, the improvement is for the case when all logics in an action have the same execution environment.)

  1. Which kind of devoids the meaning of action: transactions are also the union of execution contexts. But this is a different debate. ↩︎

  2. For the case a subset of the resources is passed to the logic, one still passes the full chain with the digests of the non-used resources. This kind of happens now, as the Merkle path accounts for the digests of the non-used resources. The difference is that the full chain is of fixed size – what approach is better depends on how many witness resources are passed to the logic. ↩︎

6

This is correct. However, you’re assuming we must check all paths for each logic. The logic shares the same action context, but it doesn’t need to use or read all of it. In practice, most resource logics only care about the self resource and a few related ones. Since a resource logic is written before constructing an action, we can’t predict how resources will be combined in an action. Therefore, we usually only constrain the resources involved in each logic. Loading all resources and performing a “for-all check” only happens when needed. Thus, checking Merkle paths requires n * d hashes, where n is the number of participating resources. If d is small (few resources in an action), both approaches are similar. If d is large and n is small, the Merkle path approach is much more efficient. As you noted, chained hashing is better when checking all leaves.

In earlier versions, we did load all resources in each logic. The number is fixed due to technical limitations. If we want to return to a “load-all” approach, maybe we can consider storing all leaves(nfs and cms) in instance, as done in the Taiga protocol and transparent RM, eliminating the need for hashes in logic? That would be simpler and more efficient.

2 Likes
7

I think we probably can remove the depth from the instance by always using the minimal depth, as we already know the actual number in each action. Then we don’t need to modify the current instance structure. Are there any cases to intentionally use a larger depth? @ArtemG @Michael

1 Like
8

Are there any cases to intentionally use a larger depth?

I don’t think so. The point of the Action tree is to just effectively gather the tags of an action in a compact format. So I see no reason why we would be interested in larger-than-minimal trees

9

I think we probably can remove the depth from the instance by always using the minimal depth

But for compliance unit we would need the depth still, am I correct? As we cannot figure out the depth of a tree neither from the compliance data nor from the root.

10

I tested the circuits and confirmed that variable-size inputs and outputs are supported without changing the elf and id(proving key and verifying key). @ArtemG @Michael @kike @vveiln

3 Likes