fix: challenge generation update #2628

lucasxia01 · 2023-10-02T19:22:31Z

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).

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.

If the pull request requires a cryptography review (e.g. cryptographic algorithm implementations) I have added the 'crypto' tag.
I have reviewed my diff in github, line by line and removed unexpected formatting changes, testing logs, or commented-out code.
Every change is related to the PR description.
I have linked this pull request to relevant issues (if any exist).

barretenberg/cpp/src/barretenberg/honk/transcript/transcript.hpp

ledwards2225

Looks good. I left some minor comments (reflecting our discussion). In general I would request that you 1) review the analogous code for the Plonk transcript to understand how/if it differs and whether that's important, 2) ensure you have thorough comments indicating the new logic, and 3) add a test demonstrating the new capability (since we should now be able to generate an arbitrary number of challenges IIUC)

ledwards2225 · 2023-10-03T18:36:38Z

barretenberg/cpp/src/barretenberg/honk/transcript/transcript.hpp

-        if (round_number > 0) {
-            full_buffer.insert(full_buffer.end(), previous_challenge_buffer.begin(), previous_challenge_buffer.end());
-        }
+        full_buffer.insert(full_buffer.end(), previous_challenge_buffer.begin(), previous_challenge_buffer.end());


Should be able to condition on previous_challenge_buffer != empty_challenge_buffer to avoid appending zeros. But actually I'm confused as to why the ASSERT a few lines above does not trigger for the first round..

the assert doesn't trigger because current_round_data isn't empty the first time we call this function

barretenberg/cpp/src/barretenberg/honk/transcript/transcript.hpp

updated comments and minor refactoring

ledwards2225

Getting close! just a couple of questions/comments and minor formatting things

ledwards2225 · 2023-10-05T21:04:30Z

barretenberg/cpp/src/barretenberg/honk/transcript/transcript.hpp

+            // copy half of the hash to lower 128 bits of challenge
+            std::copy_n(next_challenge_buffer.begin(),
+                        HASH_OUTPUT_SIZE / 2,
+                        field_element_buffer.begin() + HASH_OUTPUT_SIZE / 2);


I'm not sure how this serialization works but I would've assumed the byte at index 0 would correspond to the lowest byte of the deserialized result. If thats the case then you'd be writing to the highest 16 bytes of the field element. I assume you checked this and I'm wrong?

yeah actually good point. I did check this, but I'm not sure why this happens. I believe the Adrian's old code actually made this mistake and put it in the upper 16 bytes.

Bizarre. Maybe there was good reason for doing this but its not intuitive. Worth a comment I would say

so it actually reads the buffer like an integer; not entirely sure if some of the bytes get reversed or anything like that, but the resulting challenge is indeed 128 bits.

barretenberg/cpp/src/barretenberg/honk/transcript/transcript.test.cpp

barretenberg/cpp/src/barretenberg/honk/transcript/transcript.hpp

ledwards2225 · 2023-10-05T21:12:52Z

barretenberg/cpp/src/barretenberg/honk/transcript/transcript.hpp

-
-        // concatenate the hash of the previous round (if not the first round) with the current round data.
+        // Empty buffer to compare against
+        std::array<uint8_t, HASH_OUTPUT_SIZE> empty_challenge_buffer{};


Is this only needed to check if there was a previous challenge or not? It seems clearer to just use Adrians original if (round_number > 0) check. Maybe I'm missing something? if (!no_previous_challenge) is kind of icky :)

can't use round_number because in the 0th round, we might want to call this function multiple times. I could change the bool to first_challenge instead to avoid double negative?

I see. Maybe just a first_challenge bool that's initialized to true then gets set to false. I just find it a bit hard to understand what the intent is as you have it

good idea, just did this instead

ledwards2225

LGTM

🤖 I have created a release *beep* *boop* --- <details><summary>aztec-packages: 0.8.8</summary> ## [0.8.8](aztec-packages-v0.8.7...aztec-packages-v0.8.8) (2023-10-09) ### Features * Actually compute selectors ([#2686](#2686)) ([dcb65e1](dcb65e1)) * Add otterscan to sandbox ([#2648](#2648)) ([6986649](6986649)) * **aztec.js:** Remove attach method ([#2715](#2715)) ([c03c654](c03c654)) * Create .gitattributes in aztec-nr ([#2661](#2661)) ([8084fc3](8084fc3)) * GCC 13 preset ([#2623](#2623)) ([4881414](4881414)) * Update noir to v0.16 ([#2718](#2718)) ([e8d0675](e8d0675)) ### Bug Fixes * Avoid ambiguity on blank and blank-react (prefix issue) ([#2729](#2729)) ([68cdb3f](68cdb3f)) * Block encoding ([#2719](#2719)) ([c4796ac](c4796ac)) * Canary tests to use a fork ([#2739](#2739)) ([4906142](4906142)) * Challenge generation update ([#2628](#2628)) ([68c1fab](68c1fab)) * Docs: Sandbox version numbers ([#2708](#2708)) ([34b0209](34b0209)) * Docs: Update Sandbox page to use #include_aztec_version ([#2703](#2703)) ([d5b78af](d5b78af)) * Remove npx from extract_tag_version ([#2697](#2697)) ([fe4484a](fe4484a)) * Version in sandbox deployment ([#2730](#2730)) ([b1d8efd](b1d8efd)) ### Miscellaneous * `foundation/src/serialization` tech debt ([#2722](#2722)) ([e92154b](e92154b)) * Add node10 entrypoint to Foundation ([#2706](#2706)) ([30c7935](30c7935)) * Add storage slot to docs ([#2601](#2601)) ([a7710f0](a7710f0)) * Add visibility modifiers ([#2728](#2728)) ([d9ae189](d9ae189)) * **benchmark:** Measure time to decrypt notes in pxe ([#2714](#2714)) ([33a230a](33a230a)) * Build boxes as part of workspace ([#2725](#2725)) ([d18349f](d18349f)) * Bump ACIR deserializer ([#2675](#2675)) ([502ee87](502ee87)) * **circuits:** Delete old code that set a different generator index per vector entry in pedersen commitment ([#2700](#2700)) ([4eabfd1](4eabfd1)) * **log:** Show log level in debug logs ([#2717](#2717)) ([2b87381](2b87381)) * Move { Fr } imports to foundation/fields ([#2712](#2712)) ([f6fc7f2](f6fc7f2)) * **uniswap_tests:** Test edge cases around uniswap flow ([#2620](#2620)) ([7a58fe9](7a58fe9)) * Use `serialize` functions in `getInitialWitness` ([#2713](#2713)) ([93cc668](93cc668)) </details> <details><summary>barretenberg.js: 0.8.8</summary> ## [0.8.8](barretenberg.js-v0.8.7...barretenberg.js-v0.8.8) (2023-10-09) ### Miscellaneous * **barretenberg.js:** Synchronize aztec-packages versions </details> <details><summary>barretenberg: 0.8.8</summary> ## [0.8.8](barretenberg-v0.8.7...barretenberg-v0.8.8) (2023-10-09) ### Features * GCC 13 preset ([#2623](#2623)) ([4881414](4881414)) ### Bug Fixes * Challenge generation update ([#2628](#2628)) ([68c1fab](68c1fab)) ### Miscellaneous * Bump ACIR deserializer ([#2675](#2675)) ([502ee87](502ee87)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).

🤖 I have created a release *beep* *boop* --- <details><summary>aztec-packages: 0.8.8</summary> ## [0.8.8](AztecProtocol/aztec-packages@aztec-packages-v0.8.7...aztec-packages-v0.8.8) (2023-10-09) ### Features * Actually compute selectors ([#2686](AztecProtocol/aztec-packages#2686)) ([dcb65e1](AztecProtocol/aztec-packages@dcb65e1)) * Add otterscan to sandbox ([#2648](AztecProtocol/aztec-packages#2648)) ([6986649](AztecProtocol/aztec-packages@6986649)) * **aztec.js:** Remove attach method ([#2715](AztecProtocol/aztec-packages#2715)) ([c03c654](AztecProtocol/aztec-packages@c03c654)) * Create .gitattributes in aztec-nr ([#2661](AztecProtocol/aztec-packages#2661)) ([8084fc3](AztecProtocol/aztec-packages@8084fc3)) * GCC 13 preset ([#2623](AztecProtocol/aztec-packages#2623)) ([4881414](AztecProtocol/aztec-packages@4881414)) * Update noir to v0.16 ([#2718](AztecProtocol/aztec-packages#2718)) ([e8d0675](AztecProtocol/aztec-packages@e8d0675)) ### Bug Fixes * Avoid ambiguity on blank and blank-react (prefix issue) ([#2729](AztecProtocol/aztec-packages#2729)) ([68cdb3f](AztecProtocol/aztec-packages@68cdb3f)) * Block encoding ([#2719](AztecProtocol/aztec-packages#2719)) ([c4796ac](AztecProtocol/aztec-packages@c4796ac)) * Canary tests to use a fork ([#2739](AztecProtocol/aztec-packages#2739)) ([4906142](AztecProtocol/aztec-packages@4906142)) * Challenge generation update ([#2628](AztecProtocol/aztec-packages#2628)) ([68c1fab](AztecProtocol/aztec-packages@68c1fab)) * Docs: Sandbox version numbers ([#2708](AztecProtocol/aztec-packages#2708)) ([34b0209](AztecProtocol/aztec-packages@34b0209)) * Docs: Update Sandbox page to use #include_aztec_version ([#2703](AztecProtocol/aztec-packages#2703)) ([d5b78af](AztecProtocol/aztec-packages@d5b78af)) * Remove npx from extract_tag_version ([#2697](AztecProtocol/aztec-packages#2697)) ([fe4484a](AztecProtocol/aztec-packages@fe4484a)) * Version in sandbox deployment ([#2730](AztecProtocol/aztec-packages#2730)) ([b1d8efd](AztecProtocol/aztec-packages@b1d8efd)) ### Miscellaneous * `foundation/src/serialization` tech debt ([#2722](AztecProtocol/aztec-packages#2722)) ([e92154b](AztecProtocol/aztec-packages@e92154b)) * Add node10 entrypoint to Foundation ([#2706](AztecProtocol/aztec-packages#2706)) ([30c7935](AztecProtocol/aztec-packages@30c7935)) * Add storage slot to docs ([#2601](AztecProtocol/aztec-packages#2601)) ([a7710f0](AztecProtocol/aztec-packages@a7710f0)) * Add visibility modifiers ([#2728](AztecProtocol/aztec-packages#2728)) ([d9ae189](AztecProtocol/aztec-packages@d9ae189)) * **benchmark:** Measure time to decrypt notes in pxe ([#2714](AztecProtocol/aztec-packages#2714)) ([33a230a](AztecProtocol/aztec-packages@33a230a)) * Build boxes as part of workspace ([#2725](AztecProtocol/aztec-packages#2725)) ([d18349f](AztecProtocol/aztec-packages@d18349f)) * Bump ACIR deserializer ([#2675](AztecProtocol/aztec-packages#2675)) ([502ee87](AztecProtocol/aztec-packages@502ee87)) * **circuits:** Delete old code that set a different generator index per vector entry in pedersen commitment ([#2700](AztecProtocol/aztec-packages#2700)) ([4eabfd1](AztecProtocol/aztec-packages@4eabfd1)) * **log:** Show log level in debug logs ([#2717](AztecProtocol/aztec-packages#2717)) ([2b87381](AztecProtocol/aztec-packages@2b87381)) * Move { Fr } imports to foundation/fields ([#2712](AztecProtocol/aztec-packages#2712)) ([f6fc7f2](AztecProtocol/aztec-packages@f6fc7f2)) * **uniswap_tests:** Test edge cases around uniswap flow ([#2620](AztecProtocol/aztec-packages#2620)) ([7a58fe9](AztecProtocol/aztec-packages@7a58fe9)) * Use `serialize` functions in `getInitialWitness` ([#2713](AztecProtocol/aztec-packages#2713)) ([93cc668](AztecProtocol/aztec-packages@93cc668)) </details> <details><summary>barretenberg.js: 0.8.8</summary> ## [0.8.8](AztecProtocol/aztec-packages@barretenberg.js-v0.8.7...barretenberg.js-v0.8.8) (2023-10-09) ### Miscellaneous * **barretenberg.js:** Synchronize aztec-packages versions </details> <details><summary>barretenberg: 0.8.8</summary> ## [0.8.8](AztecProtocol/aztec-packages@barretenberg-v0.8.7...barretenberg-v0.8.8) (2023-10-09) ### Features * GCC 13 preset ([#2623](AztecProtocol/aztec-packages#2623)) ([4881414](AztecProtocol/aztec-packages@4881414)) ### Bug Fixes * Challenge generation update ([#2628](AztecProtocol/aztec-packages#2628)) ([68c1fab](AztecProtocol/aztec-packages@68c1fab)) ### Miscellaneous * Bump ACIR deserializer ([#2675](AztecProtocol/aztec-packages#2675)) ([502ee87](AztecProtocol/aztec-packages@502ee87)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).

updated challenge generation to not be powers of each other

f071f1b

lucasxia01 self-assigned this Oct 2, 2023

lucasxia01 changed the title ~~challenge-generate-update~~ refactor: challenge-generate-update Oct 2, 2023

lucasxia01 changed the title ~~refactor: challenge-generate-update~~ refactor: Challenge generation update Oct 2, 2023

lucasxia01 changed the title ~~refactor: Challenge generation update~~ refactor: challenge generation update Oct 2, 2023

lucasxia01 linked an issue Oct 2, 2023 that may be closed by this pull request

Update Honk transcript to be able to produce more than 2 challenges per round AztecProtocol/barretenberg#583

Closed

lucasxia01 commented Oct 2, 2023

View reviewed changes

barretenberg/cpp/src/barretenberg/honk/transcript/transcript.hpp Outdated Show resolved Hide resolved

lucasxia01 requested a review from ledwards2225 October 3, 2023 17:37

ledwards2225 requested changes Oct 3, 2023

View reviewed changes

lucasxia01 added 3 commits October 4, 2023 16:42

fixes to address review:

0136da9

updated comments and minor refactoring

small comment updates

4dde4a3

Merge branch 'master' into lx/challenge-gen-update

ae8e413

lucasxia01 changed the title ~~refactor: challenge generation update~~ fix: challenge generation update Oct 4, 2023

lucasxia01 added 3 commits October 5, 2023 19:10

added challenge generation test

c1bd45d

make challenges 128 bits

6eaa1a3

minor update to test, challenge instantiation

2e55921

ledwards2225 requested changes Oct 5, 2023

View reviewed changes

lucasxia01 added 2 commits October 5, 2023 21:43

fixed formatting and removed infos

3455f3c

updated checking on first challenge, extra comment

1231039

ledwards2225 approved these changes Oct 5, 2023

View reviewed changes

lucasxia01 enabled auto-merge (squash) October 5, 2023 22:05

lucasxia01 merged commit 68c1fab into master Oct 5, 2023
3 checks passed

lucasxia01 deleted the lx/challenge-gen-update branch October 5, 2023 22:21

AztecBot mentioned this pull request Oct 5, 2023

chore(master): Release 0.8.8 #2699

Merged

codygunton mentioned this pull request Oct 11, 2023

Weird challenges from new variadic challenge generation code AztecProtocol/barretenberg#375

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

fix: challenge generation update #2628

fix: challenge generation update #2628

lucasxia01 commented Oct 2, 2023 •

edited

Loading

ledwards2225 left a comment

ledwards2225 Oct 3, 2023

lucasxia01 Oct 4, 2023

ledwards2225 left a comment

ledwards2225 Oct 5, 2023

lucasxia01 Oct 5, 2023

ledwards2225 Oct 5, 2023

lucasxia01 Oct 5, 2023

ledwards2225 Oct 5, 2023

lucasxia01 Oct 5, 2023

ledwards2225 Oct 5, 2023

lucasxia01 Oct 5, 2023

ledwards2225 left a comment

fix: challenge generation update #2628

fix: challenge generation update #2628

Conversation

lucasxia01 commented Oct 2, 2023 • edited Loading

Checklist:

ledwards2225 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ledwards2225 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ledwards2225 left a comment

Choose a reason for hiding this comment

lucasxia01 commented Oct 2, 2023 •

edited

Loading