Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Barycentric Low-degree Verification for FRI #156

Closed
aszepieniec opened this issue Dec 13, 2022 · 1 comment · Fixed by #266
Closed

Barycentric Low-degree Verification for FRI #156

aszepieniec opened this issue Dec 13, 2022 · 1 comment · Fixed by #266
Labels
🤖 code Changes the implementation ✨ enhancement Improvement or new feature 🟡 prio: medium Not super urgent ⏩ speedup Makes stuff go faster.

Comments

@aszepieniec
Copy link
Collaborator

The last codeword sent in FRI has to be of low degree. What's the best way to prove this? The Miden team proposes this:

  • send both the codeword [q_i | 0 <= i < m] and the polynomial P(X) that corresponds to it (but don't send the coefficients known to be zero)
  • pick a random τ
  • evaluate P(X) in τ using straightforward Horner evaluation
  • evaluate the interpolant through [q_i | 0 <= i < m] in τ using the Barycentric Lagrange formula. This step requires $O(m^2)$ precomputation work and $O(m)$ online work.
  • Equate the two evaluations.

The soundness error is bounded by m / |F|, where |F| is the size of the field from which τ is drawn.
@aszepieniec aszepieniec added ✨ enhancement Improvement or new feature 🟡 prio: medium Not super urgent 🤖 code Changes the implementation ⏩ speedup Makes stuff go faster. labels Dec 13, 2022
@jan-ferdinand
Copy link
Member

See #5 for the different (possibly prohibitively expensive) answer to the same question.

aszepieniec added a commit that referenced this issue Apr 22, 2024
@aszepieniec
perf!: Include last FRI polynomial into proof
b05d5cb 
BREAKING CHANGE

Now the prover sends the last polynomial in addition to the last
codeword in FRI. The verifier verifies that the polynomial is of
low degree directly (without iNTTs!) and checks that it matches
with the codeword using the barycentric evaluation function and
randomness sampled from the proof stream's sponge state.

No performance change was observed on my laptop using benchmark
`prove_verify_halt` (11ms in both cases) but the main selling
point comes from the smaller anticipated clock cycle count in the
recursive verifier.

Closes #156.
jan-ferdinand pushed a commit that referenced this issue Apr 23, 2024
@aszepieniec @jan-ferdinand
perf!: Include last FRI polynomial into proof
79de920 
No performance change was observed on my laptop using benchmark
`prove_verify_halt` (11ms in both cases) but the main selling
point comes from the smaller anticipated clock cycle count in the
recursive verifier.

BREAKING CHANGE: Now the prover sends the last polynomial in addition to
the last codeword in FRI. The verifier verifies that the polynomial is
of low degree directly (without iNTTs!) and checks that it matches with
the codeword using the barycentric evaluation function and randomness
sampled from the proof stream's sponge state.

Closes #156
@jan-ferdinand jan-ferdinand linked a pull request Apr 23, 2024 that will close this issue
Barycentric Evaluation #266
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
🤖 code Changes the implementation ✨ enhancement Improvement or new feature 🟡 prio: medium Not super urgent ⏩ speedup Makes stuff go faster.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Barycentric Evaluation TritonVM/triton-vm
2 participants
@aszepieniec @jan-ferdinand