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.

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

Optimization: Require all wraparound checks to pass #60

Open
cjpatton opened this issue Feb 20, 2024 · 0 comments
Open

Optimization: Require all wraparound checks to pass #60

cjpatton opened this issue Feb 20, 2024 · 0 comments

Comments

@cjpatton
Copy link
Collaborator

The FLP circuit runs a number of independent wraparound checks (NUM_WR_CHECKS); the input is deemed valid if a fraction of the checks succeed (NUM_WR_SUCCESSES / NUM_WR_CHECKS).

We are in the midst of choosing parameters for PINE (#39). One potential outcome of this search: there may be no benefit to allowing wraparound checks to fail, either in terms of performance or ZK/soundness error. On the other hand, if we require all checks to succeed, then we can simplify the circuit a bit.

To allow a fraction of checks to fail, the prover sends the verifiers shares of a bit (denoted g here and in the paper) indicating whether the test succeeded. The circuit proves that:

  1. either the prover asserted success (i.e., that g=1) and the check succeeded or the prover asserted failure (g=0).
  2. The number of successes asserted by the prover is exactly NUM_WR_SUCCESSES / NUM_WR_CHECKS.

If instead we require all tests to succeed, then the verifiers simply need to check that every check was successful. In particular, there is no need for the prover to assert success. Not only is the resulting circuit simpler, it leads to some modest performance improvements:

  1. Shorter input (no need to send g for each wraparound check)
  2. Shorter proof (less calls to the FLP gadget)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant