Skip to content

Conversation

@ivokub
Copy link
Collaborator

@ivokub ivokub commented Jul 3, 2023

Description

This PR implements improved non-native modular multiplication as described in https://hackmd.io/3cpvkONzQl-TF5Oj8VXEHQ.

Type of change

  • New feature (non-breaking change which adds functionality)
  • This change requires a documentation update

How has this been tested?

The existing test suite passes.

How has this been benchmarked?

One of the biggest circuits we have - BW6-761 PLONK verifier in BN254 PLONK reduced from 180M constraints to 80M.

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 ivokub marked this pull request as ready for review December 1, 2023 01:28
@ivokub ivokub self-assigned this Dec 1, 2023
@ivokub ivokub added type: perf dep: linea Issues affecting Linea downstream priority: P1-high Issue priority: high labels Dec 1, 2023
@ivokub ivokub requested a review from gbotrel December 1, 2023 01:37
Copy link
Collaborator

@gbotrel gbotrel left a comment

Choose a reason for hiding this comment

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

couldn't find pointer issues, but my instinct tells me it's a bit risky ^^
also, did write some fuzz tests and ran for sometime, nothing found, but since we have a hint that does all the work, it just says the hint seems to be correct, not that everything is sound and one can't find a bad :)

lgtm 👍

@ivokub
Copy link
Collaborator Author

ivokub commented Dec 4, 2023

couldn't find pointer issues, but my instinct tells me it's a bit risky ^^ also, did write some fuzz tests and ran for sometime, nothing found, but since we have a hint that does all the work, it just says the hint seems to be correct, not that everything is sound and one can't find a bad :)

lgtm 👍

Yes, it is not perfect, but imo works well enough. I have some ideas on how to make it more robust. Namely we can keep some DB of "element pointer -> hash of limbs" and if we see during some non-native operation that there is a conflict then we can panic.

The problem with using values was that then I cannot re-use the element-as-polynomial evaluation value when same element is used in multiple muls. And this really impacted some non-native code. I could possibly try having some additional DB "hash of limbs -> stored evaluation", but dunno if this would be any better than the current approach + integrity check in prev paragraph.

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

Labels

dep: linea Issues affecting Linea downstream priority: P1-high Issue priority: high type: perf

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants