FRI

[tiagofneto]

Good resources:

• https://blog.lambdaclass.com/how-to-code-fri-from-scratch/
• https://eprint.iacr.org/2022/1216.pdf
• ethSTARK 3.9

Reference: https://github.com/starkware-libs/cairo-lang/tree/9e6e0e96d208608d98635ccfad5b26285c4936e1/src/starkware/cairo/stark_verifier/core/fri

This issue will be further divided in more issues.

[Okm165]

Implementation Plan of Fast Reed Solomon Interactive Oracle Proof of Proximity

0: FRI Verify Config

• [x] fri_verify_config

1: FRI Commit Phase

• [x] fri_commit_phase 🔗
  • [x] fri_commit_rounds 🔗
  • [x] table_commit 🔗

2: FRI Query Phase

• [x] fri_query_phase 🔗
  • [x] gather_first_layer_queries 🔗
  • [x] get_fri_group 🔗
  • [x] fri_decommit_layers
    • [x] compute_next_layer 🔗
      • [x] compute_coset_elements 🔗
      • [x] fri_formula 🔗
        • [x] fri_formula2 🔗
        • [x] fri_formula4 🔗
        • [x] fri_formula8 🔗
        • [x] fri_formula16 🔗
    • [x] verify_last_layer 🔗
    • [x] table_decommit 🔗

[Okm165]

Developing tests for fri_commit_phase & fri_query_phase & fri_verify_config

[Okm165]

fri_commit&table_commit&vector_commit tests check for channel state at final stage