Skip to content

optimize paddingFixedWidth of sha3 using divmod hint #1450

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.

Sign up for GitHub

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

Jump to bottom
Merged
ivokub merged 13 commits into from
Jul 4, 2025
Merged

optimize paddingFixedWidth of sha3 using divmod hint #1450

ivokub merged 13 commits into from
Jul 4, 2025

Conversation

@ggq89
Copy link
Contributor

@ggq89 ggq89 commented Mar 24, 2025 •
edited
Loading

Description

In this PR, a divmod function is implemented with hint, and it is used to optimize the paddingFixedWidth of sha3 to reduce the number of selects in the process of padding data and calculating numberOfBlocks.

In the project we are currently working on, one of the data lengths to be keccak256 hashed ranges from 1130 to 1710. Using the new FixedLengthSum can reduce about 50,000 constraints, as shown below:

Old version paddingFixedWidth: hash=keccak256/bound=1130/maxLen=1710/nbConstraints=3871960
New version paddingFixedWidth: hash=keccak256/bound=1130/maxLen=1710/nbConstraints=3820827

Type of change

  • New feature (non-breaking change which adds functionality)

How has this been tested?

  • TestSHA2FixedLengthSum
  • TestSHA3FixedLengthSum

How has this been benchmarked?

  • Benchmark A, on Macbook pro M1, 32GB RAM
  • Benchmark B, on x86 Intel xxx, 16GB RAM

Checklist:

  • I have performed a self-review of my code
  • I have commented my code, particularly in hard-to-understand areas
  • I have made corresponding changes to the documentation
  • I have added tests that prove my fix is effective or that my feature works
  • I did not modify files generated from templates
  • golangci-lint does not output errors locally
  • New and existing unit tests pass locally with my changes
  • Any dependent changes have been merged and published in downstream modules

@ivokub
Copy link
Collaborator

ivokub commented Mar 24, 2025

Thanks for the PR. I'll review it soon.

@ivokub ivokub self-requested a review March 24, 2025 09:48
ggq89
ggq89 commented Mar 29, 2025
View reviewed changes
ggq89
ggq89 commented Mar 29, 2025
View reviewed changes
Copy link
Contributor Author

@ggq89 ggq89 left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The constraint comparator.AssertIsLessEq(length, maxLen) should be added to prevent the wrong value from being returned when length>maxLen.

cursor[bot]

This comment was marked as outdated.

Sign in to view

@ivokub
Copy link
Collaborator

ivokub commented Jul 4, 2025 •
edited
Loading

Thanks for the contribution @ggq89! Looks good to me. However, I currently removed the std/math/arith package as it only had a single method and implemented the divmod directly in the sha3 package. Lets see in the future if there is more use for such a package, but otherwise I'm afraid it could cause confusion as we still operative in native field arithmetic.

I also added the assertions you mentioned in the comments, even though I'm not sure if it could be exploitable without, imo as far as I figured, it looks like it would create a digest for which there really isn't a preimage, so I guess in most applications it would be safe. But maybe there are some use cases where it could lead to some unexpected output (i.e. hashing known message and the digest is incorrect, leading to double spend using nullifiers etc.).

Can you have a look at my changes and if it is OK? If so, then I'll go forward with merging the PR. Thanks again!

@ivokub ivokub self-requested a review July 4, 2025 12:23
@ggq89
Copy link
Contributor Author

ggq89 commented Jul 4, 2025

@ivokub It looks fine after you make some changes，and thank you for stepping in!

@ivokub ivokub merged commit 0c973fa into Consensys:master Jul 4, 2025
4 checks passed
@ivokub
Copy link
Collaborator

ivokub commented Jul 4, 2025

@ivokub It looks fine after you make some changes，and thank you for stepping in!

Thanks for confirming!

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

Reviewers

@cursor cursor[bot] cursor[bot] left review comments

@ivokub ivokub Awaiting requested review from ivokub

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@ggq89 @ivokub