triton-vm icon indicating copy to clipboard operation
triton-vm copied to clipboard

Replace `assert_vector` by pseudo instruction `eq_vector`

Open jan-ferdinand opened this issue 2 years ago • 2 comments

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.

jan-ferdinand avatar Sep 19 '22 08:09 jan-ferdinand

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.

jan-ferdinand avatar Oct 02 '22 21:10 jan-ferdinand

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.

jan-ferdinand avatar Oct 03 '22 09:10 jan-ferdinand