Implement Gruen factoring out of eq term.

Open
#487 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
35/100
Issue type
Feature
Clarity
Mostly clear
Activity status
Quiet
Domain
cryptography

Research direction

Start at provekit/prover/src/whir_r1cs.rs lines 763-772 and trace the existing eq(X, r) term through the prover and verifier. Understand how factoring it out changes the zero-check quadratic and evaluation points, then verify that the implementation reduces those points to {0, ∞} without breaking the protocol.

Written by the indexing model from the issue text.

Description

https://github.com/worldfnd/provekit/blob/4b61b5d68e633a044eb41de4a6934d52ffdcbedc/provekit/prover/src/whir_r1cs.rs#L763-L772

We can make the zero-check quadratic by factoring out the eq(X, r) term. The verifier can compute this factor and add it back in.

This way we can reduce the evaluation points to {0, ∞}.

Dominant language
Noir
Stars
138
Forks
47
Avg merge
1d 34m
Merged PRs (30d)
6

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from worldfnd/provekit

All issues in worldfnd/provekit

Similar issues

More Cryptography issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.