refactor: Compress quotient table

TritonVM / triton-vm

Triton is a virtual machine that comes with Algebraic Execution Tables (AET) and Arithmetic Intermediate Representations (AIR) for use in combination with a STARK proof system.

https://triton-vm.org

Apache License 2.0

241 stars 36 forks source link

refactor: Compress quotient table #262

Closed aszepieniec closed 6 months ago

aszepieniec commented 6 months ago

Refactor how the quotient combination codeword is computed. Now it is done without ever constructing the entire quotient table, meaning that a lot less memory is used. Additionally, the part of the sum across constraint values of the same category now preceeds the multiplication by the zerofier-inverse, leading to less multiplications and better proving time.

aszepieniec commented 6 months ago

Benchmarking against master using prove_halt on my laptop gives:

computing the quotient codeword goes from 12.35 ms to 8.91 ms (39% improvement)
overall proving time goes from 71.34 ms to 66.14 ms (7.8% improvement)
ram usage* goes from 76944 kB to 40472 kB (47% reduction)

*ram usage measured using /bin/usr/time -v <cmd> and looking at "Maximum resident set size".