triton-vm
triton-vm copied to clipboard
Replace `assert_vector` by pseudo instruction `eq_vector`
Suggested by @aszepieniec.
By returning the result of the quintuple equality test instead of crashing the VM on inequality, a programmer can test whether a hash digest equals the Merkle root of any Merkle tree, for example the ones making up a Merkle Mountain Range. Other use cases might exist.
If desired, a crash can still be induced by calling already existing instruction assert
on the result of eq_vector
.
One way of arithmetizing instruction-to-be eq_vector
is
$$ \begin{align} (st0' - 1) &· (1 - (st0 - st5)·hv0)\\ &· (1 - (st1 - st6)·hv1)\\ &· (1 - (st2 - st7)·hv2)\\ &· (1 - (st3 - st8)·hv3)\\ &· (1 - (st4 - st9)·hv4) \end{align} $$
$$ \begin{align}
&(st0 - st5)·hv0·st0' \\
&(st1 - st6)·hv1·st0' \\
&(st2 - st7)·hv2·st0' \\
&(st3 - st8)·hv3·st0' \\
&(st4 - st9)·hv4·st0' \\
&\ \
&(1 - (st0 - st5)·hv0)·hv0 \\
&(1 - (st0 - st5)·hv0)·(st0 - st5) \\
&(1 - (st1 - st6)·hv1)·hv1 \\
&(1 - (st1 - st6)·hv1)·(st1 - st6) \\
&(1 - (st2 - st7)·hv2)·hv2 \\
&(1 - (st2 - st7)·hv2)·(st2 - st7) \\
&(1 - (st3 - st8)·hv3)·hv3 \\
&(1 - (st3 - st8)·hv3)·(st3 - st8) \\
&(1 - (st4 - st9)·hv4)·hv4 \\
&(1 - (st4 - st9)·hv4)·(st4 - st9) \\
\end{align} $$
This gives rise to a total of 16 polynomials – 15 of degree 3 and one of degree 11.
In contrast, current instruction assert_vector
requires 6 polynomials, all of which have degree 1.
eq_vector
as a pseudo instruction:
dup 0
dup 5
eq
dup 2
dup 7
eq
mul
dup 3
dup 8
eq
mul
dup 4
dup 9
eq
mul
dup 5
dup 10
eq
mul
Using 19 instructions as opposed to making the AIR more complex seems like the better option.
Relates to #6.