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(ultrahonk): Added a simple filler table to minimize the amount of entries used to make UltraHonk polynomials non-zero #531

Merged
merged 7 commits into from
Jun 15, 2023
Merged

feat(ultrahonk): Added a simple filler table to minimize the amount of entries used to make UltraHonk polynomials non-zero #531

merged 7 commits into from
Jun 15, 2023

Conversation

Rumata888
Copy link
Contributor

@Rumata888 Rumata888 commented Jun 14, 2023 •
edited
Loading

Description

In the past we used UINT32 XOR and ADD lookup tables to ensure that UltraHonk! polynomials are not zero. This made the minimum size of the circuit 2^14. This PR adds a dummy table which can be used for the same purpose but only has 2 basic tables each consisting of just 4 entries. In addition I got rid of s_randomness in UltraHonkComposerHelper, which produced bugs, since we don't randomise the polynomials in the same way in Honk!

Checklist:

  • I have reviewed my diff in github, line by line.
  • Every change is related to the PR description.
  • I have linked this pull request to the issue(s) that it resolves.
  • There are no unexpected formatting changes, superfluous debug logs, or commented-out code.
  • There are no circuit changes, OR specifications in /markdown/specs have been updated.
  • There are no circuit changes, OR a cryptographer has been assigned for review.
  • I've updated any terraform that needs updating (e.g. environment variables) for deployment.
  • The branch has been rebased against the head of its merge target.
  • I'm happy for the PR to be merged at the reviewer's next convenience.
  • New functions, classes, etc. have been documented according to the doxygen comment format. Classes and structs must have @brief describing the intended functionality.
  • If existing code has been modified, such documentation has been added or updated.

@Rumata888 Rumata888 changed the title fix(ultrahonk): Added a simple filler table to minimize the amount of entries used to make UltraHonk polynomials non-zero feat(ultrahonk): Added a simple filler table to minimize the amount of entries used to make UltraHonk polynomials non-zero Jun 14, 2023
@Rumata888 Rumata888 requested a review from maramihali June 15, 2023 13:20
maramihali
maramihali reviewed Jun 15, 2023
View reviewed changes
cpp/src/barretenberg/honk/composer/composer_helper/ultra_honk_composer_helper.cpp
@@ -230,7 +220,7 @@ std::shared_ptr<typename Flavor::ProvingKey> UltraHonkComposerHelper_<Flavor>::c
polynomial poly_q_table_column_3(subgroup_size);
polynomial poly_q_table_column_4(subgroup_size);

size_t offset = subgroup_size - tables_size - s_randomness - 1;
size_t offset = subgroup_size - tables_size;
Copy link
Contributor

Choose a reason for hiding this comment

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

why was the -1 for previously?

Copy link
Contributor Author

Choose a reason for hiding this comment

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

We inserted a 1 at the end so that the polynomial would not be zero. Don't know why since we add randomness anyway

maramihali
maramihali reviewed Jun 15, 2023
View reviewed changes
cpp/src/barretenberg/proof_system/circuit_constructors/ultra_circuit_constructor.cpp
@@ -100,23 +100,17 @@ void UltraCircuitConstructor::add_gates_to_ensure_all_polys_are_non_zero()
// to get a non-zero value in table_4. I assume this index is arbitrary and could
// start from 1 instead of 0?
uint32_t left_value = 3;
uint32_t right_value = 5;
uint32_t right_value = 3;
Copy link
Contributor

@maramihali maramihali Jun 15, 2023 •
edited
Loading

Choose a reason for hiding this comment

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

can you explain what this value is because the change looks arbitrary - maybe add comment as well

Copy link
Contributor Author

Choose a reason for hiding this comment

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

The change is because the multitable only works on 2-bit values, so 5 is too big

maramihali
maramihali reviewed Jun 15, 2023
View reviewed changes
cpp/src/barretenberg/proof_system/plookup_tables/dummy.hpp Outdated
namespace dummy_tables {

/**
* @brief Lookup the value corresponding to a sepcific key
Copy link
Contributor

Choose a reason for hiding this comment

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

typo in specific

Copy link
Contributor Author

Choose a reason for hiding this comment

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

Thanks

cpp/src/barretenberg/proof_system/plookup_tables/dummy.hpp
inline BasicTable generate_honk_dummy_table(const BasicTableId id, const size_t table_index)
{

ASSERT(table_id == static_cast<uint64_t>(id));
Copy link
Contributor

Choose a reason for hiding this comment

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

why do this two have to be equal - i understand that id is static while table_id can change depending on function (?)

Copy link
Contributor Author

Choose a reason for hiding this comment

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

We are using the same function in 2 places by templating it, but the API already includes the id in arguments. This is just a simple bug check to ensure that we don't use the wrong instantiation

@Rumata888 Rumata888 marked this pull request as ready for review June 15, 2023 18:04
@Rumata888 Rumata888 merged commit b20b401 into master Jun 15, 2023
@Rumata888 Rumata888 deleted the is/simple_table branch June 15, 2023 18:05
@github-actions github-actions bot mentioned this pull request Jun 15, 2023
Merged
@codygunton codygunton linked an issue Jun 20, 2023 that may be closed by this pull request
Avoid zero-polynomials in Ultra Honk #423
Closed
@github-actions github-actions bot mentioned this pull request Jul 11, 2023
Merged
ludamad pushed a commit to AztecProtocol/aztec-packages that referenced this pull request Jul 22, 2023
@Rumata888
feat(ultrahonk): Added a simple filler table to minimize the amount o…
a751959 
…f entries used to make UltraHonk polynomials non-zero (AztecProtocol/barretenberg#531)

feat(ultrahonk): Added a simple filler table to minimize the amount of entries used to make UltraHonk polynomials non-zero
ludamad pushed a commit to AztecProtocol/aztec-packages that referenced this pull request Jul 24, 2023
@Rumata888
feat(ultrahonk): Added a simple filler table to minimize the amount o…
656a23c 
…f entries used to make UltraHonk polynomials non-zero (AztecProtocol/barretenberg#531)

feat(ultrahonk): Added a simple filler table to minimize the amount of entries used to make UltraHonk polynomials non-zero
This was referenced Jul 25, 2023
Closed
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@maramihali maramihali maramihali left review comments

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Avoid zero-polynomials in Ultra Honk
2 participants
@Rumata888 @maramihali