As part of our effort to improve the efficiency of the circuit, a new design of the MerkleSumTreeChip
that makes use of fewer advice columns is proposed here.
Let's consider the situation in which we have N_ASSETS=2
. The circuit as designed now would take MST_WIDTH
advice columns, where pub const MST_WIDTH: usize = 3 * (1 + N_ASSETS)
so, in this case, it would be 9.
The current layout would look like this:
a |
b |
c |
d |
e |
f |
g |
h |
i |
bal_0_left |
bal_1_left |
bal_0_right |
bal_1_right |
- |
- |
hash_left |
hash_right |
- |
At the row = 0, bool selector
would be applied to check that swap_bit
is either 0 or 1.
At the row = 0, swap selector
would be applied to check that according to the swap_bit
selector, the values are swapped correctly in the next row.
For example, considering the case in which the swap_bit
is 0, this would mean that no swap needs to be performed as follow in row=1
a |
b |
c |
d |
e |
f |
g |
h |
i |
bal_0_left |
bal_1_left |
bal_0_right |
bal_1_right |
sum_0 |
sum_1 |
hash_left |
hash_right |
swap_bit |
At the row = 1 sum_selector
would be applied to check that sum_i = bal_i_left + bal_i_right
.
Furthermore, after row=1 is computed, other 2 operations are performed on the assigned cells of row 1:
- poseidon_chip is used to hash
H(hash_left, bal_0_left, bal_1_left, hash_right bal_0_right, bal_1_right, hash_leaf)
- overflow check is performed on
bal_0_left, bal_1_left, bal_0_right, bal_1_right
.
This structure grows in size linearly according to N_ASSETS
, in particular the relation between the number of assets and the number of advice columns is defined by MST_WIDTH
. 3 assets would mean 12 columns.
Therefore we can try to redisign it as follow, considering N_ASSETS = 2
and again considering swap_bit = 0
a |
b |
c |
hash_left |
hash_right |
swap_bit |
hash_left |
hash_right |
|
bal_0_left |
bal_0_right |
swap_bit |
bal_0_left |
bal_0_right |
sum_0 |
bal_1_left |
bal_1_right |
swap_bit |
bal_1_left |
bal_1_right |
sum_1 |
At row 0, 2 and 4 bool_constraint
and swap_selectors
need to be toogled.
At row 1 and 3 sum_selector
needs to be toogled
After row 5 is computed, the same poseidon
and overflow
check can be performed following the same structure as before.
An additional check that need to be performed here is that the swap_bit
remains consistent for an hasher round!
Note that this structure grows vertically according to N_ASSETS
, since every new asset will contribute with a two more rows, while it doesn't add any advice column! Which is exactly what we are looking for.
As a result of this implementation:
MST_WIDTH
will be removed as generics to the circuit
bool
and swap
selectors can be merged into a single selector as these are always toggled at the same time