In #185, I added minimal install targets for barretenberg; however, it should also be consumable via find_package or FetchContent_MakeAvailable in other CMake builds.

We an mimic https://github.com/google/benchmark to do this well.

• add methods for serialization/deserialization of univariate to transcript and corresponding tests
• integrate existing transcript into Sumcheck

Getting rid of it, and all of the extra structure that supports it, is a nice goal, but a useful step would at least be to remove whatever is necessary for Honk to not have any notion of unrolled.

The manifests are currently a primary source of loose coupling in Barretenberg. Resolving this issue would give a more flexible transcript (e.g., simplifying the tests that now require a manifest (sometimes a partial one)) and would follow the paradigm of having "a single source of information". Namely, the prover's algorithm and the verifier's algorithm will be specified in code, and a manifest recording their interactions will be documented in a test. In-order execution of the algorithms will be enforced via the properties of the hash function that is used to generate the challenges; out-of-order execution will lead to differing challenges.

These comments have been left in Barretenberg:

/* IMPROVEMENT(Cody): This could or should be improved in various ways. In no particular order:
   1) Edge cases are not considered. One non-use case situation (I forget which) leads to a segfault.
   2) This could all be constexpr.
   3) Precomputing for all possible size pairs is probably feasible and might be a better solution than instantiating
   many instances separately. Then perhaps we could infer input type to `extend`.
   4) There should be more thorough testing of this class in isolation. */

This goes in the nice-to-have bin for now.

As noted in WebAssembly/wasi-sdk#125, the <filesystem> library cannot be used in wasm/wasi. This project seems stuck on wasi-sdk 12 because it contained a bug that didn't disable loading that filesystem header, but if that code path is every taken, it'd crash.

@adr1anh noted this in an internal issue, and had fixes to use mkdir instead; this seemed to have been blocked as "not portable".

We should either #ifndef around all code using <filesystem> or switch to mkdir. It seems this can be made portable by using _mkdir on Windows.

The following lines only contain a description of "Non native field arithmetic gate 2".

What is this doing for us? I find it hard to navigate, wonder what others think.

Maybe also move some shared stuff into bonk namespace. Maybe also give some better names to things (e.g., waffle::StandardComposer can become plonk::StandardComposer and honk::StandardHonkComposer can become honk::StandardComposer).

From #31 (review): methods should be added that batch prove and batch verify multiple polynomial commitments.

Since the git commit hook to format code runs on and commits all files that are changed, if you try to use git add -p to stage chunks of a file, the entire file gets committed.

This is really bad for workflows that make a bunch of changes and then chop them up into digestible commits.

In #185, I added minimal install targets for barretenberg; however, we should also provide a file that pkg-config can use to find out any flags, etc that are required when linking against the library (such as omp).

Fake SRS in existing Plonk tests?

Split tests into more CCI jobs?

Assess whether we really need all of the biggroup tests?

The sumcheck argument requires that the sum to be checked has summands weighted by powers of a random element $\zeta$ so that, when the sum is shown to be zero, one can conclude with high probability that each of the summands is zero. This is not implemented in the sumcheck work, at present.

After #23 is merged, this will handle the work of replacing mocked calls to the multivariate PCS by real calls.

The proving key for the Plonk based proving systems contains the witnesses which breaks the idea that a pkey should be "shareable" between provers. This work makes that possible (as is already the case for Honk).

It would be nice if we could initialise commitment key with file/memory reference strings. Also, if we had the option of initialising pippenger runtime separately, when we know the size of the circuit.

From: #31 (review): the Fiat-Shamir heuristic must be used to generate the round challenges as part of the ipa_prove and ipa_verify algorithms. The InnerProductArgument class should have a Hash template parameter that defines which hash algorithm is used.

Clean up TODOs in Honk:

• remove outdated TODOs
• address very simple TODOs
• make issues for everything else

This could be split into three tasks:

1. Reinstate tests that that were replaced by tests of Honk during the building of the PoC. This was done for expediency.
2. Assess test coverage.
3. Finally complete the overhaul of the standard library tests, most likely along the lines of #24. This would include using typed tests.

Another goal that is worth achieving is to avoid having any skipped tests. Currently we skip some tests (e.g., in biggroup) that are not intended to run, but it might be better to simply not build these tests and use "skipping" as a temporary measure only.

Hi,

Barretenberg doesn't seem to work for me at the moment on a mac m1.

I don't know much about c++ but this is possibly an issue related to tbb in the ultra composer file. As I'm running into this error

 Could not find a package configuration file provided by "TBB" with any of
  the following names:
 
    TBBConfig.cmake
    tbb-config.cmake

after running

./bootstrap.sh

After running,

brew install tbb

the error turned into this

fatal error: 'tbb/atomic.h' file not found
#include <tbb/atomic.h>

Investigate possibility of modifying our product equality check arguments (copy constraints and plookup) to use logarithmic derivatives as in Cached Quotients paper. This would allow us to remove commitments to the quotient polynomials.

Clean out outdated/unnecessary memory management stuff from the Polynomial class.

From #31 (review): "The SRS object contains a single pippenger_runtime_state object that is used to perform all pippenger computations (constructing pippenger_runtime_state is expensive)."

The objective of this issue is to reduce the cost of using pippenger by using only a single pippenger_runtime_state.

This project currently only builds to a "binary dir" (as cmake calls them) but it should also have install targets so you can do cmake --install . --prefix "/usr/local"

A formal collision resistance proof for the ultraplonk pedersen hash (based on the merkle damagard construction) is pending. Opening this issue so that we don't forget this.

Code:

The join_split circuit now skips signature verification for merge join_splits since It checks that the spender and total amounts are going to remain the same and that only note aggregation is happening.

However, using the account_required flag an exploiter that has control over an account key but no spending keys could still drain the notes that have account_required to true:

• Decode the notes using the account key
• Do regular merge join_splits with them, with a fake signature (since it's going to be skipped) to the same owner BUT creating the output notes as account_required = false
• Now the attacker can spend the notes with the account key since the output notes are account_required false

We need to investigate and check if the PR fixing this issue was merged into master.

Motivation

We currently store too many preprocessed polynomials in the proving key, like ID_1, ID_2, ID_3, and L_FIRST and L_LAST.
All of these can be efficiently evaluatable by the verifier, so they do not need to be committed. Moreover, it may be more efficient to derive their "edge extension" directly by exploiting their structure.

In the recursive verification circuit, we aggregate the proof verification by computing $P_0, P_1$. To compute $P_0$, we perform the BN254 MSM operation on a vector of group elements and scalars inside the circuit using the function bn254_endo_batch_mul_with_generator .

Similarly, the MSM to compute $P_1$ uses the function wnaf_batch_mul.

But the problem is: if any of the elements in the rhs_elements contain $(0,0)$ as its $x,y$-coordinate (btw $(0,0)$ isn't point on the curve) then the composer should catch that and throw an error. Ideally, there should be an assertion failure in the division function msub_div in the bigfield module. This doesn't happen when using Standard or Turbo composers. It fails at the correct assertion when using Ultraplonk though.

I wrote a quick test to confirm this is a problem with the MSM operation in the circuit. This only tests wnaf_batch_mul function.

Questions:

1. Is this the expected behaviour or are we missing some checks?
2. Is this a problem because we don't allow overflows while constructing fq_ct points?

The sum check code should panic if the Input univariates in the sumcheck relations are not linear polynomials.

Update Honk so that all commitments are computed via the work queue.

We should extend our field fuzzer to a dynamic array fuzzer. The dynamic array implementation is complicated and must be audited thoroughly before being used in production.

Assuming we adopt the form where 'polynomials' have 0 in the first and last index, we only need one grand product relation of the form [(Z_{shift,i} + L_{n-1,i}) * G_i] - [(Z_i + L_{0,i}) * F_i].

• Update the current grand product computation relation
• Remove the no longer needed grand product initialization relation

Consolidate the two existing std::maps that hold commitments in the verification key into a single map called commitments.

This lets the proving key be something shareable between provers (the correct abstraction). This is a step toward getting rid of the polynomial manifest in Honk.

SYSTEM_COMPOSER is an Aztec Connect-specific concept. Unless someone has a good reason to keep it, it should go away and tests such as those of stdlib Schnorr should be rewritten and tested with Honk.

Include public inputs via permutation argument in Honk.

Currently gemini breaks for a polynomial, where the second half of coefficients is zero.

From #31 (review): the function commit, ipa_prove and ipa_verify should take in an SRS object instead of a vector of generators (and have this SRS class load the required points from disk like our KZG SRS)

From @kevaundray in #171

We could use the assert_equal which this method calls, this helper function just makes it explicit that we are not actually asserting anything and instead doing a copy/replace

It's confusing that assert_equal is just a copy (and only works in one direction). Ideally this function would be renamed for clarity.

This SYSTEM_COMPOSER variable was introduced by @suyash67 to ease the process of changing the underlying proof system of the Aztec Connect rollup (pre-root verifier circuit). It seems to me this feature is now just noise, so I propose to remove it from Barretenberg. It's possible that we should reinstate it in some other form in Aztec 3, though there we will be blending various proof systems and curves, so something more robust will be needed. Thoughts @suyash67 @iAmMichaelConnor?

https://github.com/AztecProtocol/aztec2-internal/pull/1615

• Assess it.
• Improve it (e.g., some stdlib tests are only being run for StandardHonkComposer now).

Add basic benchmarking suite for Honk (using google benchmark).