succinctlabs / gnark-plonky2-verifier

MIT License
85 stars 25 forks source link

feat: Reduce # of plonk constraints in the goldilocks range checker #31

Closed kevjue closed 1 year ago

kevjue commented 1 year ago

Use Miden's approach for range checking that an element is within goldilocks.

For the check that an element is not larger than 1111111111111111111111111111111100000000000000000000000000000000, our current range checker is adding up all the most sig 32 bits and least sig 32 bits to verify most sig 32 bits != 2**32-1 or lst sig 32 bits == 0.

Miden is verifying that differently, which will remove all the adds. We should do the same verification check that miden does.

puma314 commented 1 year ago

Completed. Reduces the constraint count to ~20 million PLONK and ~6 million in Groth16.