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

Apply parallel sum gadget optimization to Prio3Histogram #274

Closed
divergentdave opened this issue Aug 1, 2023 · 0 comments
Closed

Apply parallel sum gadget optimization to Prio3Histogram #274

divergentdave opened this issue Aug 1, 2023 · 0 comments
Assignees

Comments

@divergentdave
Copy link
Collaborator

The range check portion of the Prio3Histogram circuit could be rewritten to use the parallel sum gadget. This would result in more wire polynomials, each of smaller degree, smaller proofs ($O(\sqrt{n})$ instead of $O(n)$), faster proving, and larger preparation message shares ($O(\sqrt{n})$ instead of $O(1)$). See #124 (comment).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants