TritonVM / triton-vm / 26026689705

98%

Build Type

push

github

Committed by jan-ferdinand

Commit Message

fix!: Randomize quotient table

This change improves the plausibility with which Triton VM is
Zero-Knowledge: where before, we did not know of a proof-of-ZK, this
new construction has an explicit proof-of-ZK.

As a consequence, Triton VM loses perfect completeness: with negligible
probability, the verifier can sample randomness that would cause the
prover to violate ZK, in which case it aborts.

This endeavor also clarified and documented the following:
1. all Merkle trees for or downstream from the combination codeword leak
   no trace information already;
2. for the Merkle trees over the low-degree-extended, randomized trace
   and randomized quotient tables, one extra coefficient of margin on
   the number of trace randomizers h suffices.

BREAKING CHANGE: The type `QuotientSegments` becomes type
`RandQuotientSegments` to reflect the fact that quotient segments are
always randomized when communicated between prover and verifier.

Coverage Stats

218 of 228 new or added lines in 2 files covered. (95.61%)

24 existing lines in 3 files now uncovered.

15690 of 15971 relevant lines covered (98.24%)

9479788.86 hits per line