Write recursive verifier

[jan-ferdinand]

Write the recursive verifier. The checklist below is probably incomplete and in some places too coarse-grained. It will be updated and broken up into additional issues as subtasks become clearer.

Triton Assembly Verifier

• decompress partial authentication paths (not TASM)
• sample {indices, weights, challenges}
  • Fiat-Shamir
• Merkle tree authentication path verification
• quotient building
  • evaluate AIR (see also: generate (optimal) TASM for constraint evaluation #135)
  • divide by zerofier
• non-linear combination
• {base, extension, combination} tree root comparison
• FRI verify
  • co-linear point compute
  • Checking low-degreeness of last FRI codeword in recursive verifier #5

sample weights

input: seed, num_weights

list_of_weights = []
for i in {0, …, num_weights-1}:
    digest = xlix(seed, i)
    weight = XFieldElement(digest)
    list_of_weights += [weight]
return list_of_weights

sample indices

See document on index sampling.

Revealed indices

For the recursive verifier, we need to do something different with revealed indices: We currently sort and deduplicate, which is going to be expensive/hard when coding this in TVM.

(Originally issue number 24 in the internal issue tracker.)

[jan-ferdinand]

Instead of translating our current rust verifier into Triton assembly in one straight go, it might be worth considering to do an intermediate step. For example:

• Write a standard library for Triton VM, exposing commonly used data structures and functionalities.
• Write a stand-alone, no_std Triton rust verifier.

[jan-ferdinand]

Tasm-lib now has a recursive verifier. One of the next steps is to bring it into Triton VM. In any case, this issue is superseded.