Update Honk transcript to be able to produce more than 2 challenges per round #583
Assignees
Labels
bug
Something isn't working
Comments
4 tasks
4 tasks
lucasxia01
added a commit
to AztecProtocol/aztec-packages
that referenced
this issue
Oct 5, 2023
This PR updates challenge generation to not be powers of each other, fixing AztecProtocol/barretenberg#583. Before, we generated multiple challenges by generating one by hashing the round data and the previous challenge, and then taking powers of this challenge as the other challenges. Now, we generate challenges by taking a hash each time of the previous challenge (and the round data, which is only nonempty in the first iteration of get_next_challenge_buffer() in a round). Using powers of one challenge does not lead to soundness bugs in how we currently use challenges, but theoretically, we would want challenges to be "independent" of each other. Challenges are 128 bits. I truncate every 256-bit hash to 128 bits for 2 reasons. First, it is easier on the verifier to multiply with 128 challenges as opposed to 256 bits. Second, the 256-bit challenges were not actually uniformly distributed in a nice way because the challenges get modded by the 254-bit scalar field modulus. In this approach, the challenges should be distributed more uniformly (over 128-bit numbers). Optimization(AztecProtocol/barretenberg#741) - I could split every hash into 2 challenges, so I use all 256 bits of a hash (when we need it), instead of throwing away 128 bits every time. # Checklist: Remove the checklist to signal you've completed it. Enable auto-merge if the PR is ready to merge. - [x] If the pull request requires a cryptography review (e.g. cryptographic algorithm implementations) I have added the 'crypto' tag. - [x] I have reviewed my diff in github, line by line and removed unexpected formatting changes, testing logs, or commented-out code. - [x] Every change is related to the PR description. - [x] I have [linked](https://docs.github.com/en/issues/tracking-your-work-with-issues/linking-a-pull-request-to-an-issue) this pull request to relevant issues (if any exist).
AztecBot
pushed a commit
that referenced
this issue
Oct 6, 2023
This PR updates challenge generation to not be powers of each other, fixing #583. Before, we generated multiple challenges by generating one by hashing the round data and the previous challenge, and then taking powers of this challenge as the other challenges. Now, we generate challenges by taking a hash each time of the previous challenge (and the round data, which is only nonempty in the first iteration of get_next_challenge_buffer() in a round). Using powers of one challenge does not lead to soundness bugs in how we currently use challenges, but theoretically, we would want challenges to be "independent" of each other. Challenges are 128 bits. I truncate every 256-bit hash to 128 bits for 2 reasons. First, it is easier on the verifier to multiply with 128 challenges as opposed to 256 bits. Second, the 256-bit challenges were not actually uniformly distributed in a nice way because the challenges get modded by the 254-bit scalar field modulus. In this approach, the challenges should be distributed more uniformly (over 128-bit numbers). Optimization(#741) - I could split every hash into 2 challenges, so I use all 256 bits of a hash (when we need it), instead of throwing away 128 bits every time. # Checklist: Remove the checklist to signal you've completed it. Enable auto-merge if the PR is ready to merge. - [x] If the pull request requires a cryptography review (e.g. cryptographic algorithm implementations) I have added the 'crypto' tag. - [x] I have reviewed my diff in github, line by line and removed unexpected formatting changes, testing logs, or commented-out code. - [x] Every change is related to the PR description. - [x] I have [linked](https://docs.github.com/en/issues/tracking-your-work-with-issues/linking-a-pull-request-to-an-issue) this pull request to relevant issues (if any exist).
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Current transcript method takes a variadic input parameter to describe the number of hashes required per round.
However... the implementation will compute a 32 byte challenge and split this challenge among the required number of hashes, producing (32 / number-of-challenges) byte challenges.
If the byte length of the challenge is less than 16 an assert is triggered.
A cleaner and less brittle implementation would define the number of bytes required for each challenge as part of the Transcript class. Iterative hashing would be used to generate the required challenge bytes for an arbitrary number of hashes.
See the Plonk Transcript class for a reference implementation.
The text was updated successfully, but these errors were encountered: