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.

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

chore: included subrelation witness degrees in the relations relevant to zk-sumcheck #7479

Merged
merged 3 commits into from
Jul 16, 2024

Conversation

iakovenkos
Copy link
Contributor

@iakovenkos iakovenkos commented Jul 15, 2024

The subrelation witness degrees are used in zk-sumcheck and affect the sizes of the univariates in the SumcheckTupleOfTuplesOfUnivariates as well as the sizes of the sumcheck round univariates.

In several relations, I used upper bounds on the witness degrees which are simply given by the corresponding subrelation's length - 1. Indicated explicitly that those are upper bounds. Computed the precise constants for the relations relevant to Mega.

The auxiliary and logderiv_lookup_relation contain a trick allowing to re-use the values accumulated by an accumulator of a different size using ShortView.

@iakovenkos iakovenkos requested a review from maramihali July 15, 2024 16:59
@@ -12,6 +12,12 @@ template <typename FF_> class UltraArithmeticRelationImpl {
5 // secondary arithmetic sub-relation
};

/**
* @brief Total degrees of sub-relations considered as polynomials in witnesses.
Copy link
Contributor

Choose a reason for hiding this comment

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

Suggested change
* @brief Total degrees of sub-relations considered as polynomials in witnesses.
* @brief Total degrees of subrelations considered as polynomials in witnesses.

Copy link
Contributor

Choose a reason for hiding this comment

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

Could you rephrase this comment so it's clear where it's being used? Also I think it's quite a confusing comment. Here and in the other places

* @brief Upper bound on total degrees of sub-relations considered as polynomials in witnesses.
*
*/
static constexpr std::array<size_t, NUM_BUS_COLUMNS * 2> SUBRELATION_WITNESS_DEGREES{
Copy link
Contributor

Choose a reason for hiding this comment

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

please explain here the -1 and in the other places, it really helps the reader in a few months

using View = typename Accumulator::View;
using ShortView = typename std::tuple_element_t<0, ContainerOverSubrelations>::View;
Copy link
Contributor

Choose a reason for hiding this comment

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

I think it would be nice to add the related comment from the PR description here

Copy link
Contributor

@maramihali maramihali left a comment

Choose a reason for hiding this comment

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

Overall looks good, thanks for the additional docs, just some nit picks and requests for clarifying comments.

@iakovenkos
Copy link
Contributor Author

Resolved all isssues: added clearer definitions for SUBRELATION_WITNESS_DEGREES and explained the upper bounds appearing in some of the relations (mostly ECCVM and Translator). Added comments for the ShortView trick in logderivative and auxiliary relations.

@iakovenkos iakovenkos enabled auto-merge (squash) July 16, 2024 09:44
@iakovenkos iakovenkos merged commit 457a115 into master Jul 16, 2024
35 checks passed
@iakovenkos iakovenkos deleted the zk-relation-length-adjustments branch July 16, 2024 10:05
rahul-kothari pushed a commit that referenced this pull request Jul 16, 2024
🤖 I have created a release *beep* *boop*
---


<details><summary>aztec-package: 0.46.7</summary>

##
[0.46.7](aztec-package-v0.46.6...aztec-package-v0.46.7)
(2024-07-16)


### Features

* Devnet updates
([#7421](#7421))
([103f099](103f099))


### Bug Fixes

* Cli l1-chain-id option
([#7490](#7490))
([307bc57](307bc57))


### Miscellaneous

* Turn on elaborator
([#7451](#7451))
([0599500](0599500))
</details>

<details><summary>barretenberg.js: 0.46.7</summary>

##
[0.46.7](barretenberg.js-v0.46.6...barretenberg.js-v0.46.7)
(2024-07-16)


### Miscellaneous

* **barretenberg.js:** Synchronize aztec-packages versions
</details>

<details><summary>aztec-packages: 0.46.7</summary>

##
[0.46.7](aztec-packages-v0.46.6...aztec-packages-v0.46.7)
(2024-07-16)


### Features

* Add unconstrained context to txe
([#7448](#7448))
([699fb79](699fb79))
* Add unconstrained getters to sharedmutable
([#7429](#7429))
([c0ff566](c0ff566))
* Devnet updates
([#7421](#7421))
([103f099](103f099))
* Point::fromXandSign(...)
([#7455](#7455))
([225c6f6](225c6f6))


### Bug Fixes

* **avm:** Update generated verifier
([#7492](#7492))
([f1216a7](f1216a7))
* Cli l1-chain-id option
([#7490](#7490))
([307bc57](307bc57))
* Don't pass secrets to earthly-ci 'publish docs' command
([#7481](#7481))
([a3f6feb](a3f6feb))
* Fix msg_sender direct call exploit
([#7404](#7404))
([1dcae45](1dcae45))
* Missing NoteSelector from JSON RPC proxies
([#7493](#7493))
([b209fad](b209fad))
* **pxe:** Best effort noir call stack generation
([#7336](#7336))
([0c7459b](0c7459b))
* Validate gas used
([#7459](#7459))
([6dc7598](6dc7598))


### Miscellaneous

* **avm:** More stats and codegen cleanup
([#7475](#7475))
([1a6c7f2](1a6c7f2))
* Checking compute_encrypted_note_log against TS impl
([#7491](#7491))
([1e8a597](1e8a597))
* Included subrelation witness degrees in the relations relevant to
zk-sumcheck
([#7479](#7479))
([457a115](457a115))
* Replace relative paths to noir-protocol-circuits
([71960d4](71960d4))
* Turn on elaborator
([#7451](#7451))
([0599500](0599500))
</details>

<details><summary>barretenberg: 0.46.7</summary>

##
[0.46.7](barretenberg-v0.46.6...barretenberg-v0.46.7)
(2024-07-16)


### Features

* Point::fromXandSign(...)
([#7455](#7455))
([225c6f6](225c6f6))


### Bug Fixes

* **avm:** Update generated verifier
([#7492](#7492))
([f1216a7](f1216a7))


### Miscellaneous

* **avm:** More stats and codegen cleanup
([#7475](#7475))
([1a6c7f2](1a6c7f2))
* Included subrelation witness degrees in the relations relevant to
zk-sumcheck
([#7479](#7479))
([457a115](457a115))
</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 Jul 17, 2024
🤖 I have created a release *beep* *boop*
---


<details><summary>aztec-package: 0.46.7</summary>

##
[0.46.7](AztecProtocol/aztec-packages@aztec-package-v0.46.6...aztec-package-v0.46.7)
(2024-07-16)


### Features

* Devnet updates
([#7421](AztecProtocol/aztec-packages#7421))
([103f099](AztecProtocol/aztec-packages@103f099))


### Bug Fixes

* Cli l1-chain-id option
([#7490](AztecProtocol/aztec-packages#7490))
([307bc57](AztecProtocol/aztec-packages@307bc57))


### Miscellaneous

* Turn on elaborator
([#7451](AztecProtocol/aztec-packages#7451))
([0599500](AztecProtocol/aztec-packages@0599500))
</details>

<details><summary>barretenberg.js: 0.46.7</summary>

##
[0.46.7](AztecProtocol/aztec-packages@barretenberg.js-v0.46.6...barretenberg.js-v0.46.7)
(2024-07-16)


### Miscellaneous

* **barretenberg.js:** Synchronize aztec-packages versions
</details>

<details><summary>aztec-packages: 0.46.7</summary>

##
[0.46.7](AztecProtocol/aztec-packages@aztec-packages-v0.46.6...aztec-packages-v0.46.7)
(2024-07-16)


### Features

* Add unconstrained context to txe
([#7448](AztecProtocol/aztec-packages#7448))
([699fb79](AztecProtocol/aztec-packages@699fb79))
* Add unconstrained getters to sharedmutable
([#7429](AztecProtocol/aztec-packages#7429))
([c0ff566](AztecProtocol/aztec-packages@c0ff566))
* Devnet updates
([#7421](AztecProtocol/aztec-packages#7421))
([103f099](AztecProtocol/aztec-packages@103f099))
* Point::fromXandSign(...)
([#7455](AztecProtocol/aztec-packages#7455))
([225c6f6](AztecProtocol/aztec-packages@225c6f6))


### Bug Fixes

* **avm:** Update generated verifier
([#7492](AztecProtocol/aztec-packages#7492))
([f1216a7](AztecProtocol/aztec-packages@f1216a7))
* Cli l1-chain-id option
([#7490](AztecProtocol/aztec-packages#7490))
([307bc57](AztecProtocol/aztec-packages@307bc57))
* Don't pass secrets to earthly-ci 'publish docs' command
([#7481](AztecProtocol/aztec-packages#7481))
([a3f6feb](AztecProtocol/aztec-packages@a3f6feb))
* Fix msg_sender direct call exploit
([#7404](AztecProtocol/aztec-packages#7404))
([1dcae45](AztecProtocol/aztec-packages@1dcae45))
* Missing NoteSelector from JSON RPC proxies
([#7493](AztecProtocol/aztec-packages#7493))
([b209fad](AztecProtocol/aztec-packages@b209fad))
* **pxe:** Best effort noir call stack generation
([#7336](AztecProtocol/aztec-packages#7336))
([0c7459b](AztecProtocol/aztec-packages@0c7459b))
* Validate gas used
([#7459](AztecProtocol/aztec-packages#7459))
([6dc7598](AztecProtocol/aztec-packages@6dc7598))


### Miscellaneous

* **avm:** More stats and codegen cleanup
([#7475](AztecProtocol/aztec-packages#7475))
([1a6c7f2](AztecProtocol/aztec-packages@1a6c7f2))
* Checking compute_encrypted_note_log against TS impl
([#7491](AztecProtocol/aztec-packages#7491))
([1e8a597](AztecProtocol/aztec-packages@1e8a597))
* Included subrelation witness degrees in the relations relevant to
zk-sumcheck
([#7479](AztecProtocol/aztec-packages#7479))
([457a115](AztecProtocol/aztec-packages@457a115))
* Replace relative paths to noir-protocol-circuits
([71960d4](AztecProtocol/aztec-packages@71960d4))
* Turn on elaborator
([#7451](AztecProtocol/aztec-packages#7451))
([0599500](AztecProtocol/aztec-packages@0599500))
</details>

<details><summary>barretenberg: 0.46.7</summary>

##
[0.46.7](AztecProtocol/aztec-packages@barretenberg-v0.46.6...barretenberg-v0.46.7)
(2024-07-16)


### Features

* Point::fromXandSign(...)
([#7455](AztecProtocol/aztec-packages#7455))
([225c6f6](AztecProtocol/aztec-packages@225c6f6))


### Bug Fixes

* **avm:** Update generated verifier
([#7492](AztecProtocol/aztec-packages#7492))
([f1216a7](AztecProtocol/aztec-packages@f1216a7))


### Miscellaneous

* **avm:** More stats and codegen cleanup
([#7475](AztecProtocol/aztec-packages#7475))
([1a6c7f2](AztecProtocol/aztec-packages@1a6c7f2))
* Included subrelation witness degrees in the relations relevant to
zk-sumcheck
([#7479](AztecProtocol/aztec-packages#7479))
([457a115](AztecProtocol/aztec-packages@457a115))
</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
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants