-
Notifications
You must be signed in to change notification settings - Fork 274
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
feat: Log-derivative based generic permutations for AVM #3428
feat: Log-derivative based generic permutations for AVM #3428
Conversation
Benchmark resultsMetrics with a significant change:
Detailed resultsAll benchmarks are run on txs on the This benchmark source data is available in JSON format on S3 here. Values are compared against data from master at commit L2 block published to L1Each column represents the number of txs on an L2 block published to L1.
L2 chain processingEach column represents the number of blocks on the L2 chain where each block has 16 txs.
Circuits statsStats on running time and I/O sizes collected for every circuit run across all benchmarks.
MiscellaneousTransaction sizes based on how many contracts are deployed in the tx.
|
5bdcfed
to
9f6bff7
Compare
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
a few minor formatting comments. Other than that looks good. Would be nice to have a fully generic way of defining column equivalences and lookups directly on columns in the Flavor class, but I'll leave it up to you on whether you want to implement!
namespace proof_system::honk { | ||
namespace flavor { | ||
|
||
class AVMTemplate { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
what is AVMTemplate? Some comments + description would be useful
constexpr size_t WRITE_TERMS = Relation::WRITE_TERMS; | ||
|
||
// For now we only do simple permutations over tuples with 1 read and 1 write term |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Could you make an issue to change this? I suspect we'll need to have more exotic lookups to fully support the AVM
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This is just for permutations
|
||
namespace proof_system { | ||
|
||
template <typename Flavor> class AVMTemplateCircuitBuilder { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
maybe put "Toy" in the name? Some top-level comments would be useful here as well
6098063
to
b00dc64
Compare
🤖 I have created a release *beep* *boop* --- <details><summary>aztec-packages: 0.16.8</summary> ## [0.16.8](aztec-packages-v0.16.7...aztec-packages-v0.16.8) (2023-12-13) ### Features * Block header block number oracle ([#3648](#3648)) ([ac1edc1](ac1edc1)) * Complete folding prover and verifier for ultra instances ([#3419](#3419)) ([bb86ce9](bb86ce9)) * Copy constructors for builders ([#3635](#3635)) ([b82b0c5](b82b0c5)) * Enabling nullifier tree snapshot ([#3670](#3670)) ([b47d49d](b47d49d)) * Libraryfying historic access ([#3658](#3658)) ([6877ca1](6877ca1)) * Log-derivative based generic permutations for AVM ([#3428](#3428)) ([379b5ad](379b5ad)) * Merge recursive verifier ([#3588](#3588)) ([cdd9259](cdd9259)) * New install script and container wrappers. ([#3617](#3617)) ([c7f1878](c7f1878)) * Persist pxe state ([#3628](#3628)) ([9ccbbd9](9ccbbd9)) * Update command handles Dockerized sandbox ([#3656](#3656)) ([7c85750](7c85750)) ### Bug Fixes * Aztec sandbox compose fixes ([#3634](#3634)) ([765a19c](765a19c)) * Broken uint256_t implicit copy ([#3625](#3625)) ([1a6b44d](1a6b44d)) * **ci:** Rebuild versioned cli / sandbox images ([#3613](#3613)) ([6a53fbc](6a53fbc)) * Make lsp work in docker, plus some other install tweaks. ([#3661](#3661)) ([53eb54f](53eb54f)) * **noir-compiler:** Compile time error if ctor is missing ([#3649](#3649)) ([12249bf](12249bf)) * Sandbox node mode api prefix ([#3662](#3662)) ([fd6eefe](fd6eefe)) * Top level init bb.js, but better scoped imports to not incur cost too early ([#3629](#3629)) ([cea862d](cea862d)) ### Miscellaneous * **ci:** Combine deploy / release jobs + canary update ([#3610](#3610)) ([0888c05](0888c05)), closes [#3579](#3579) * **docs:** Update implementation references in token contract tutorial ([#3626](#3626)) ([a2cee4f](a2cee4f)) * Nuke fib ([#3607](#3607)) ([48e2e3d](48e2e3d)) * Reduced spam logging in archiver ([#3671](#3671)) ([e749daa](e749daa)) * Run the protocol circuits noir tests in CI ([#3660](#3660)) ([383e123](383e123)), closes [#3205](#3205) ### Documentation * Updated yellow paper for fees ([#3659](#3659)) ([5513624](5513624)) * **yellowpaper:** Rewrite section on tagged memory, misc rewording/cleanup ([#3523](#3523)) ([fe849e3](fe849e3)) * **yellowpaper:** Update `cast` instruction description with truncation operation ([#3621](#3621)) ([2cede41](2cede41)) </details> <details><summary>barretenberg.js: 0.16.8</summary> ## [0.16.8](barretenberg.js-v0.16.7...barretenberg.js-v0.16.8) (2023-12-13) ### Bug Fixes * Aztec sandbox compose fixes ([#3634](#3634)) ([765a19c](765a19c)) * Top level init bb.js, but better scoped imports to not incur cost too early ([#3629](#3629)) ([cea862d](cea862d)) </details> <details><summary>barretenberg: 0.16.8</summary> ## [0.16.8](barretenberg-v0.16.7...barretenberg-v0.16.8) (2023-12-13) ### Features * Complete folding prover and verifier for ultra instances ([#3419](#3419)) ([bb86ce9](bb86ce9)) * Copy constructors for builders ([#3635](#3635)) ([b82b0c5](b82b0c5)) * Log-derivative based generic permutations for AVM ([#3428](#3428)) ([379b5ad](379b5ad)) * Merge recursive verifier ([#3588](#3588)) ([cdd9259](cdd9259)) ### Bug Fixes * Aztec sandbox compose fixes ([#3634](#3634)) ([765a19c](765a19c)) * Broken uint256_t implicit copy ([#3625](#3625)) ([1a6b44d](1a6b44d)) ### Miscellaneous * Nuke fib ([#3607](#3607)) ([48e2e3d](48e2e3d)) </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.16.8</summary> ## [0.16.8](AztecProtocol/aztec-packages@aztec-packages-v0.16.7...aztec-packages-v0.16.8) (2023-12-13) ### Features * Block header block number oracle ([#3648](AztecProtocol/aztec-packages#3648)) ([ac1edc1](AztecProtocol/aztec-packages@ac1edc1)) * Complete folding prover and verifier for ultra instances ([#3419](AztecProtocol/aztec-packages#3419)) ([bb86ce9](AztecProtocol/aztec-packages@bb86ce9)) * Copy constructors for builders ([#3635](AztecProtocol/aztec-packages#3635)) ([b82b0c5](AztecProtocol/aztec-packages@b82b0c5)) * Enabling nullifier tree snapshot ([#3670](AztecProtocol/aztec-packages#3670)) ([b47d49d](AztecProtocol/aztec-packages@b47d49d)) * Libraryfying historic access ([#3658](AztecProtocol/aztec-packages#3658)) ([6877ca1](AztecProtocol/aztec-packages@6877ca1)) * Log-derivative based generic permutations for AVM ([#3428](AztecProtocol/aztec-packages#3428)) ([379b5ad](AztecProtocol/aztec-packages@379b5ad)) * Merge recursive verifier ([#3588](AztecProtocol/aztec-packages#3588)) ([cdd9259](AztecProtocol/aztec-packages@cdd9259)) * New install script and container wrappers. ([#3617](AztecProtocol/aztec-packages#3617)) ([c7f1878](AztecProtocol/aztec-packages@c7f1878)) * Persist pxe state ([#3628](AztecProtocol/aztec-packages#3628)) ([9ccbbd9](AztecProtocol/aztec-packages@9ccbbd9)) * Update command handles Dockerized sandbox ([#3656](AztecProtocol/aztec-packages#3656)) ([7c85750](AztecProtocol/aztec-packages@7c85750)) ### Bug Fixes * Aztec sandbox compose fixes ([#3634](AztecProtocol/aztec-packages#3634)) ([765a19c](AztecProtocol/aztec-packages@765a19c)) * Broken uint256_t implicit copy ([#3625](AztecProtocol/aztec-packages#3625)) ([1a6b44d](AztecProtocol/aztec-packages@1a6b44d)) * **ci:** Rebuild versioned cli / sandbox images ([#3613](AztecProtocol/aztec-packages#3613)) ([6a53fbc](AztecProtocol/aztec-packages@6a53fbc)) * Make lsp work in docker, plus some other install tweaks. ([#3661](AztecProtocol/aztec-packages#3661)) ([53eb54f](AztecProtocol/aztec-packages@53eb54f)) * **noir-compiler:** Compile time error if ctor is missing ([#3649](AztecProtocol/aztec-packages#3649)) ([12249bf](AztecProtocol/aztec-packages@12249bf)) * Sandbox node mode api prefix ([#3662](AztecProtocol/aztec-packages#3662)) ([fd6eefe](AztecProtocol/aztec-packages@fd6eefe)) * Top level init bb.js, but better scoped imports to not incur cost too early ([#3629](AztecProtocol/aztec-packages#3629)) ([cea862d](AztecProtocol/aztec-packages@cea862d)) ### Miscellaneous * **ci:** Combine deploy / release jobs + canary update ([#3610](AztecProtocol/aztec-packages#3610)) ([0888c05](AztecProtocol/aztec-packages@0888c05)), closes [#3579](AztecProtocol/aztec-packages#3579) * **docs:** Update implementation references in token contract tutorial ([#3626](AztecProtocol/aztec-packages#3626)) ([a2cee4f](AztecProtocol/aztec-packages@a2cee4f)) * Nuke fib ([#3607](AztecProtocol/aztec-packages#3607)) ([48e2e3d](AztecProtocol/aztec-packages@48e2e3d)) * Reduced spam logging in archiver ([#3671](AztecProtocol/aztec-packages#3671)) ([e749daa](AztecProtocol/aztec-packages@e749daa)) * Run the protocol circuits noir tests in CI ([#3660](AztecProtocol/aztec-packages#3660)) ([383e123](AztecProtocol/aztec-packages@383e123)), closes [#3205](AztecProtocol/aztec-packages#3205) ### Documentation * Updated yellow paper for fees ([#3659](AztecProtocol/aztec-packages#3659)) ([5513624](AztecProtocol/aztec-packages@5513624)) * **yellowpaper:** Rewrite section on tagged memory, misc rewording/cleanup ([#3523](AztecProtocol/aztec-packages#3523)) ([fe849e3](AztecProtocol/aztec-packages@fe849e3)) * **yellowpaper:** Update `cast` instruction description with truncation operation ([#3621](AztecProtocol/aztec-packages#3621)) ([2cede41](AztecProtocol/aztec-packages@2cede41)) </details> <details><summary>barretenberg.js: 0.16.8</summary> ## [0.16.8](AztecProtocol/aztec-packages@barretenberg.js-v0.16.7...barretenberg.js-v0.16.8) (2023-12-13) ### Bug Fixes * Aztec sandbox compose fixes ([#3634](AztecProtocol/aztec-packages#3634)) ([765a19c](AztecProtocol/aztec-packages@765a19c)) * Top level init bb.js, but better scoped imports to not incur cost too early ([#3629](AztecProtocol/aztec-packages#3629)) ([cea862d](AztecProtocol/aztec-packages@cea862d)) </details> <details><summary>barretenberg: 0.16.8</summary> ## [0.16.8](AztecProtocol/aztec-packages@barretenberg-v0.16.7...barretenberg-v0.16.8) (2023-12-13) ### Features * Complete folding prover and verifier for ultra instances ([#3419](AztecProtocol/aztec-packages#3419)) ([bb86ce9](AztecProtocol/aztec-packages@bb86ce9)) * Copy constructors for builders ([#3635](AztecProtocol/aztec-packages#3635)) ([b82b0c5](AztecProtocol/aztec-packages@b82b0c5)) * Log-derivative based generic permutations for AVM ([#3428](AztecProtocol/aztec-packages#3428)) ([379b5ad](AztecProtocol/aztec-packages@379b5ad)) * Merge recursive verifier ([#3588](AztecProtocol/aztec-packages#3588)) ([cdd9259](AztecProtocol/aztec-packages@cdd9259)) ### Bug Fixes * Aztec sandbox compose fixes ([#3634](AztecProtocol/aztec-packages#3634)) ([765a19c](AztecProtocol/aztec-packages@765a19c)) * Broken uint256_t implicit copy ([#3625](AztecProtocol/aztec-packages#3625)) ([1a6b44d](AztecProtocol/aztec-packages@1a6b44d)) ### Miscellaneous * Nuke fib ([#3607](AztecProtocol/aztec-packages#3607)) ([48e2e3d](AztecProtocol/aztec-packages@48e2e3d)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).
…l#3428) Introduces a relation for constructing generic permutations that needs to be templated for PIL for AVM. Renames lookup_library to logderivative_library
🤖 I have created a release *beep* *boop* --- <details><summary>aztec-packages: 0.16.8</summary> ## [0.16.8](AztecProtocol/aztec-packages@aztec-packages-v0.16.7...aztec-packages-v0.16.8) (2023-12-13) ### Features * Block header block number oracle ([AztecProtocol#3648](AztecProtocol#3648)) ([ac1edc1](AztecProtocol@ac1edc1)) * Complete folding prover and verifier for ultra instances ([AztecProtocol#3419](AztecProtocol#3419)) ([bb86ce9](AztecProtocol@bb86ce9)) * Copy constructors for builders ([AztecProtocol#3635](AztecProtocol#3635)) ([b82b0c5](AztecProtocol@b82b0c5)) * Enabling nullifier tree snapshot ([AztecProtocol#3670](AztecProtocol#3670)) ([b47d49d](AztecProtocol@b47d49d)) * Libraryfying historic access ([AztecProtocol#3658](AztecProtocol#3658)) ([6877ca1](AztecProtocol@6877ca1)) * Log-derivative based generic permutations for AVM ([AztecProtocol#3428](AztecProtocol#3428)) ([379b5ad](AztecProtocol@379b5ad)) * Merge recursive verifier ([AztecProtocol#3588](AztecProtocol#3588)) ([cdd9259](AztecProtocol@cdd9259)) * New install script and container wrappers. ([AztecProtocol#3617](AztecProtocol#3617)) ([c7f1878](AztecProtocol@c7f1878)) * Persist pxe state ([AztecProtocol#3628](AztecProtocol#3628)) ([9ccbbd9](AztecProtocol@9ccbbd9)) * Update command handles Dockerized sandbox ([AztecProtocol#3656](AztecProtocol#3656)) ([7c85750](AztecProtocol@7c85750)) ### Bug Fixes * Aztec sandbox compose fixes ([AztecProtocol#3634](AztecProtocol#3634)) ([765a19c](AztecProtocol@765a19c)) * Broken uint256_t implicit copy ([AztecProtocol#3625](AztecProtocol#3625)) ([1a6b44d](AztecProtocol@1a6b44d)) * **ci:** Rebuild versioned cli / sandbox images ([AztecProtocol#3613](AztecProtocol#3613)) ([6a53fbc](AztecProtocol@6a53fbc)) * Make lsp work in docker, plus some other install tweaks. ([AztecProtocol#3661](AztecProtocol#3661)) ([53eb54f](AztecProtocol@53eb54f)) * **noir-compiler:** Compile time error if ctor is missing ([AztecProtocol#3649](AztecProtocol#3649)) ([12249bf](AztecProtocol@12249bf)) * Sandbox node mode api prefix ([AztecProtocol#3662](AztecProtocol#3662)) ([fd6eefe](AztecProtocol@fd6eefe)) * Top level init bb.js, but better scoped imports to not incur cost too early ([AztecProtocol#3629](AztecProtocol#3629)) ([cea862d](AztecProtocol@cea862d)) ### Miscellaneous * **ci:** Combine deploy / release jobs + canary update ([AztecProtocol#3610](AztecProtocol#3610)) ([0888c05](AztecProtocol@0888c05)), closes [AztecProtocol#3579](AztecProtocol#3579) * **docs:** Update implementation references in token contract tutorial ([AztecProtocol#3626](AztecProtocol#3626)) ([a2cee4f](AztecProtocol@a2cee4f)) * Nuke fib ([AztecProtocol#3607](AztecProtocol#3607)) ([48e2e3d](AztecProtocol@48e2e3d)) * Reduced spam logging in archiver ([AztecProtocol#3671](AztecProtocol#3671)) ([e749daa](AztecProtocol@e749daa)) * Run the protocol circuits noir tests in CI ([AztecProtocol#3660](AztecProtocol#3660)) ([383e123](AztecProtocol@383e123)), closes [AztecProtocol#3205](AztecProtocol#3205) ### Documentation * Updated yellow paper for fees ([AztecProtocol#3659](AztecProtocol#3659)) ([5513624](AztecProtocol@5513624)) * **yellowpaper:** Rewrite section on tagged memory, misc rewording/cleanup ([AztecProtocol#3523](AztecProtocol#3523)) ([fe849e3](AztecProtocol@fe849e3)) * **yellowpaper:** Update `cast` instruction description with truncation operation ([AztecProtocol#3621](AztecProtocol#3621)) ([2cede41](AztecProtocol@2cede41)) </details> <details><summary>barretenberg.js: 0.16.8</summary> ## [0.16.8](AztecProtocol/aztec-packages@barretenberg.js-v0.16.7...barretenberg.js-v0.16.8) (2023-12-13) ### Bug Fixes * Aztec sandbox compose fixes ([AztecProtocol#3634](AztecProtocol#3634)) ([765a19c](AztecProtocol@765a19c)) * Top level init bb.js, but better scoped imports to not incur cost too early ([AztecProtocol#3629](AztecProtocol#3629)) ([cea862d](AztecProtocol@cea862d)) </details> <details><summary>barretenberg: 0.16.8</summary> ## [0.16.8](AztecProtocol/aztec-packages@barretenberg-v0.16.7...barretenberg-v0.16.8) (2023-12-13) ### Features * Complete folding prover and verifier for ultra instances ([AztecProtocol#3419](AztecProtocol#3419)) ([bb86ce9](AztecProtocol@bb86ce9)) * Copy constructors for builders ([AztecProtocol#3635](AztecProtocol#3635)) ([b82b0c5](AztecProtocol@b82b0c5)) * Log-derivative based generic permutations for AVM ([AztecProtocol#3428](AztecProtocol#3428)) ([379b5ad](AztecProtocol@379b5ad)) * Merge recursive verifier ([AztecProtocol#3588](AztecProtocol#3588)) ([cdd9259](AztecProtocol@cdd9259)) ### Bug Fixes * Aztec sandbox compose fixes ([AztecProtocol#3634](AztecProtocol#3634)) ([765a19c](AztecProtocol@765a19c)) * Broken uint256_t implicit copy ([AztecProtocol#3625](AztecProtocol#3625)) ([1a6b44d](AztecProtocol@1a6b44d)) ### Miscellaneous * Nuke fib ([AztecProtocol#3607](AztecProtocol#3607)) ([48e2e3d](AztecProtocol@48e2e3d)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).
Introduces a relation for constructing generic permutations that needs to be templated for PIL for AVM.
Renames lookup_library to logderivative_library
Checklist:
Remove the checklist to signal you've completed it. Enable auto-merge if the PR is ready to merge.