Skip to content
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

feat: complete folding prover and verifier for ultra instances #3419

Merged
merged 67 commits into from
Dec 8, 2023
Merged

feat: complete folding prover and verifier for ultra instances #3419

merged 67 commits into from
Dec 8, 2023

Conversation

maramihali
Copy link
Contributor

@maramihali maramihali commented Nov 24, 2023 •
edited by codygunton
Loading

Closes AztecProtocol/barretenberg#781
Closes AztecProtocol/barretenberg#689
Closes AztecProtocol/barretenberg#690
Closes AztecProtocol/barretenberg#802

This PR provides the first full version of folding prover and verifiers for Ultra instances and provides the first full folding test. The protogalaxy interfaces have been slightly reworked so the prover now returns a complete new relaxed Instance and a folding proof. While the verifier receives the folding proof and returns a boolean dependent on whether the pubic data from the relaxed instance, sent by the prover, is the same as the data computed by the folding verifier.

maramihali and others added 30 commits October 23, 2023 14:47
@maramihali
wip wip wip
6313f15
@maramihali
styuff
40cedd0
@maramihali
how do I do this?
c7cc936
@maramihali
pain
59c69f2
@maramihali
pain
aed27df
@maramihali
wip that works
265f248
@maramihali
Merge branch 'master' into mm/pg-plumbing
44da63f
@maramihali
cleanup
7ffc364
@maramihali
Merge branch 'master' into mm/combiner-quotient
62df97a
@maramihali
comment test
9d1b5c6
@maramihali
comment test
42ac7e2
@codygunton
Merge remote-tracking branch 'origin/master' into mm/combiner-quotient
75221fb
@codygunton
Add weirder test
bc63909
@codygunton
Use clearer type names
7d3e01b
@maramihali
wip
2287a76
@maramihali
pr review additions
86963a5
@maramihali
Merge branch 'master' into mm/combiner-quotient
a816c4b
@maramihali
fix formatting
91ca591
@maramihali
add missing issue
abb6ed2
@maramihali
Merge branch 'mm/combiner-quotient' into mm/pg-fold-alpha
81f7d89
@maramihali
wip that doesn't work
73068a6
@maramihali
wip
a86a9b4
@maramihali
subrelation number
a51d686
@maramihali
add stuff
df7a62c
@maramihali
confusion
1ff05b6
@maramihali
pain
1ed19f2
@maramihali
compiles
dea27c1
@maramihali
Merge branch 'master' into mm/pg-fold-alpha
05bf621
@maramihali
works
073db88
@maramihali
Merge branch 'master' into mm/pg-fold-alpha
e9079f3
@maramihali maramihali changed the title feat: full folding feat: complete folding prover and verifier for ultra instances Dec 4, 2023
@maramihali maramihali marked this pull request as ready for review December 4, 2023 16:47
@maramihali maramihali requested a review from codygunton December 4, 2023 16:54
codygunton
codygunton approved these changes Dec 6, 2023
View reviewed changes
Copy link
Contributor

@codygunton codygunton left a comment

Choose a reason for hiding this comment

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

Great stuff, very exciting progress. Lots of comments, nothing blocking, please respond and merge when ready.

barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_prover.hpp Outdated Show resolved Hide resolved
barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_prover.hpp Outdated Show resolved Hide resolved
barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_prover.hpp Outdated Show resolved Hide resolved
barretenberg/cpp/src/barretenberg/sumcheck/instance/verifier_instance.hpp Outdated Show resolved Hide resolved
barretenberg/cpp/src/barretenberg/sumcheck/instance/instances.hpp Outdated Show resolved Hide resolved
barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_prover.hpp Outdated Show resolved Hide resolved
barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_verifier.cpp Outdated Show resolved Hide resolved
barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_verifier.cpp Outdated Show resolved Hide resolved
barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_verifier.cpp Outdated Show resolved Hide resolved
barretenberg/cpp/src/barretenberg/protogalaxy/protogalaxy_verifier.cpp Show resolved Hide resolved
@codygunton
Copy link
Contributor

I should add that I didn't do a super deep check for correctness of the protocol, for lack of time, and because these are initial classes. If there are issues with the decider we we can do that sooner, otherwise the deep scrutiny comes in 2024.

@maramihali maramihali enabled auto-merge (squash) December 7, 2023 17:31
@maramihali maramihali merged commit bb86ce9 into master Dec 8, 2023
74 of 76 checks passed
@maramihali maramihali deleted the mm/pg-poc branch December 8, 2023 09:34
@AztecBot AztecBot mentioned this pull request Dec 8, 2023
Merged
critesjosh pushed a commit that referenced this pull request Dec 13, 2023
@AztecBot
chore(master): Release 0.16.8 (#3609)
10376ef 
🤖 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).
AztecBot added a commit to AztecProtocol/barretenberg that referenced this pull request Dec 14, 2023
@AztecBot
chore(master): Release 0.16.8 (#3609)
f92fd99 
🤖 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).
michaelelliot pushed a commit to Swoir/noir_rs that referenced this pull request Feb 28, 2024
@maramihali
feat: complete folding prover and verifier for ultra instances (Aztec…
4ab3ee7 
…Protocol#3419)

Closes AztecProtocol/barretenberg#781 
Closes AztecProtocol/barretenberg#689 
Closes AztecProtocol/barretenberg#690
Closes AztecProtocol/barretenberg#802

This PR provides the first full version of folding prover and verifiers
for Ultra instances and provides the first full folding test. The
protogalaxy interfaces have been slightly reworked so the prover now
returns a complete new relaxed `Instance` and a folding proof. While the
verifier receives the folding proof and returns a boolean dependent on
whether the pubic data from the relaxed instance, sent by the prover, is
the same as the data computed by the folding verifier.
michaelelliot pushed a commit to Swoir/noir_rs that referenced this pull request Feb 28, 2024
@AztecBot
chore(master): Release 0.16.8 (AztecProtocol#3609)
e5a1657 
🤖 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).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@codygunton codygunton codygunton approved these changes

Assignees

@maramihali maramihali

Labels
crypto cryptography
Projects
A3
Archived in project
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Folding public inputs Fold witness commitments ProtoGalaxyVerifier ProtoGalaxy Prover
3 participants
@maramihali @AztecBot @codygunton