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

bug: squaring in multicommit unsafe for some curves #1203

Closed
ivokub opened this issue Jul 16, 2024 · 0 comments · Fixed by #1212
Closed

bug: squaring in multicommit unsafe for some curves #1203

ivokub opened this issue Jul 16, 2024 · 0 comments · Fixed by #1212
Assignees
Labels
bug Something isn't working P1: High Issue priority: high

Comments

@ivokub
Copy link
Collaborator

ivokub commented Jul 16, 2024

Description

In the std/multicommit we allow to collect all variables we want to commit to and only use single api.Commit for making the verifier more efficient (every call to api.Commit creates a new pairing computation for Groth16 and adds scalar multiplication in PLONK). The approach for now for computing the per-instance commitment is to derive the individual commitments using squaring from the root commit. However, in some cases with small 2-adicity we may obtain 1 as a individual commitment (and which will stay 1), allowing a malicious prover to break the soundness of the circuit (as the challenge is known ahead of time).

Currently it doesn't have an impact as requires at least 192 commitments with curves we don't use, but it would be better to have a sound implementation.

Possible Fix

Use consecutive powers instead of squaring or use the same root commitment. I prefer using consecutive powers as when using same root commitment imo we need to be aware not to use in contexts where we expect the commitments to be different. Even better approach would imo to use hashing, but it may have negative impact on the constraint count when we use many commitments. But we could measure, maybe it isn't too bad.

@ivokub ivokub added bug Something isn't working P1: High Issue priority: high labels Jul 16, 2024
@ivokub ivokub self-assigned this Jul 16, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working P1: High Issue priority: high
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant