Trees with longer node sizes

[hackaugusto]

I'm creating this discussion as a continuation of #55, but focused on the trees and not the hashing function.

Current behavior

The current sparse tree implementation is tiered, each tier has depth 16 and the tree has a maximum depth of 64. It is a binary tree, meaning each internal node has 2 children. This means the tree has $2^{d-1}$ elements at depth $d$, updating an element requires $d-1$ hash calls, and the proof has the same size.

metric	value	For depth 16
node size	$2$ words (except root, and leaves)	$2$ words
#of-leaves	$2^{d-1}$	32768
#of-internal	$2^{d-1}-1$	32767
#of-nodes	$2^d-1$	65535
#of-permutations	$d-1$ (this assumes a 2-to-1 hash function)	16

Larger internal nodes

If instead of a binary tree, the internal nodes would be bigger and accept m children

metric	value	m=4 d=8	m=4 d=9	m=6 d=6	m=6 d=7
node size	$m$ words (except root, and leaves)	4 words	4 words	6 words	6 words
#of-leaves	$m^{d-1}$	16384	65536	7776	46656
#of-internal	$(1-m^{d-1})/(1-m)$	5461	21845	1555	9331
#of-nodes	$(1-m^d)/(1-m)$	21845	87381	9331	55987
#of-permutations	either $m*(d-1)$ or $(d-1)*(m/2)$	28 or 14	32 or 16	30 or 15	36 or 18
ratio-leaves	#of-leaves / #of-leaves-binary	0.5	2	0.23	1.42
ratio-storage	#of-nodes / #of-nodes-binary	0.33	1.33	0.14	0.85

$m*(d-1)$ can be done in parallel(ish) ref, $(d-1)*(m/2)$ is sequential but saves a few extra hash calls ref

The above numbers are just samples for values that are around the current 32768, if my rationale is correct it is possible to tune it.

[bobbinth]

Using higher arity would be pretty challenging from the VM/ZKP standpoint. Right now, we can do 2-to-1 hash in a single permutation of the hash function. This means we can describe 2-to-1 hashing relatively easily in the VM (this is done in the hash chiplet). With higher airty trees we'd need to do one of the following:

1. Increase the state size of the hash function.
2. Absorb each node in multiple permutations.

Both of these complicate things quite a bit, and I'm not sure we'll realize much benefit if we go that route.

But yes, outside the VM using higher arity trees would give a nice performance improvement.

[hackaugusto]

This was based on the idea 2. I haven't done any calculations for a different state size to keep things simple.

Using higher arity would be pretty challenging from the VM/ZKP standpoint [...] Both of these complicate things quite a bit

Can you elaborate a bit on what do you mean by complicate things? AFAIU this is what it is done by the instruction hperm, and it is used internally by adv_pipe, so it is built-in and we use this on some situations already.

and I'm not sure we'll realize much benefit if we go that route.

The trade off should be quantifiable, the table above has some examples, like the node with length 4 and depth 8 would use 2 fewer per permutations than the current approach, to have half of the number of items at 33% of the storage.

[bobbinth]

AFAIU this is what it is done by the instruction hperm

Using hperm instruction for Merkle path verification would be pretty inefficient (though, as you mention above, would be good to quantify this). The VM supports specialized instructions for verifying Merkle paths of arity 2 (this is handles by the hash chiplet internally). If we use a tree of different arity, we would need to do one of the following:

1. Redesign hasher chiplet to support trees of this arity more efficiently.
2. Use hperm instruction manually.

My intuition (again, would be good to verify this), is that using hperm instruction manually will be less efficient than using built-in instructions mtree_get and mtree_set. Moreover, mtree_get and mtree_set instructions are coupled with how the advice provider maintains structured Merkle tree data. For hperm we'll need to come with a different mechanism of keeping the advice provider in sync with what is happening on the VM.

[hackaugusto]

Ahhh, I didn't realize that mtree_get was more efficient to hperm, I will read over on that. Thank you!

[bobbinth]

Yes, mtree_get uses MPVERIFY VM operation which can verify a binary Merkle path of length $n$ in just a single VM cycle (though, we still need to use $8 \cdot n$ rows of the hasher chiplet.

Similarly, mtree_set uses MRUPDATE VM operation which can compute a new root of a Merkle tree of depth $n$ in a single VM cycle (though again, we still need to use $16 \cdot n$ rows in the hash chiplet).

With hperm and higher arity tree we may end up using fewer rows of the hash chiplet, but we'll probably use many more cycles on the stack.