We are adding Halo2 functionality to Noir. Originally, we explored the laborious task of synthesizing the Halo2 matrix representation from each ACIR opcode (like VampIR[1]). However, “UltraPlonK” is “PLONKish” arithmetisation, which prompts the idea that we could simply use Barretenberg to build the polynomials that encode the circuit. Then, we can use the Halo2 API to construct the vanishing argument, multipoint opening argument, and inner product argument prescribed to make a Halo2 proof.
Assuming proper ZK adjustments, this could be a strong tailwind for the integration of Halo2 into Noir since we would rely on existing “Black Box Function” [3] OpCodes rather than connecting existing Halo2 gadgets and building others. This further begs the question as to whether we even need to build a “backend” for Noir. Instead, it appears that we could potentially work entirely within the Barretenberg library by adding IPA commitments.
Questions:
How does Barretenberg handle blinding of Lookup and Permutation arguments?
Do we need to make serious changes to fulfill compatibility with Halo2’s Zero Knowledge adjustment?
Instead of building a new backend for Noir, should we extend the Barretenberg library to use IPA if desired?
Should we still bind to the Halo2 sdk for the remaining Halo2 proof system steps so that we do not write a lot of code that would need analysis/ auditing? Does this require a backend, or can we comfortably add FFI C++ → Rust bindings to the Barretenberg library?
Are there any other concerns/ issues we are overlooking?
Bonus questions on KZG:
It appears that Barretenberg already makes KZG commitments [4] in proofs to some degree. How different is this from the PSE fork of Halo2 which swaps IPA for KZG?
Additional Links
replace “(dot)” with “.” (only 2 allowed in post for new user)
[1]: github(dot)com/anoma/vamp-ir/blob/main/src/halo2/synth.rs
[2]: zcash(dot)github(dot)io/halo2/design/proving-system/permutation.html#zero-knowledge-adjustment
[3]: github(dot)com/noir-lang/acvm/blob/master/acvm/src/pwg/blackbox.rs
[4]: github(dot)com/AztecProtocol/barretenberg/blob/97ccf76c42db581a8b8f8bfbcffe8ca015a3dd22/cpp/src/barretenberg/honk/pcs/kzg/kzg.hpp#L4
Hi. I will not be able to answer Halo 2-related questions, as I have no experience with it, but I can answer some of your questions
Permutation and plookup arguments in barretenberg for ultraplonk use the following mechanism for HVZK. The vanishing polynomial we use is not X’n-1, it has several roots cut out at the end. This allows us to substitute several final elements in each of those polynomials with random ones.
In its current state barretenberg is not ideal for picking out primitives and combining them to construct a new proving system. We are actively trying to change that by creating more independent mechanisms especially in the context of Honk and UltraHonk, but it might require significant effort to change the logic for Plonk/UltraPlonk.
Sharing some (lightly edited, for readability) notes from people commenting internally:
IPA performs quite badly in Ethereum smart contracts especially since proof size is not constant but logarithmic, so the bigger the circuit size the more calldata you need to process — perhaps this is okay for other use cases.
I think halo2 is sufficiently different to Barretenberg that trying to use the frontend from Barretenberg to plug into halo2 sounds like a theoretically easy undertaking but engineering wise it might be a massive pain.
(I have not looked at halo2 in a few months, so perhaps it’s changed a lot since then — for blinding, a separate random polynomial is used last time I checked)
If the goal is to avoid needing to re-implement the acir opcodes like sha256, then I think that’s probably not the best reason to do it this way since I imagine that those popular opcodes will eventually be implemented in halo2 and we have fallback functions that we plan to implement in ACIR.
We do already have a fallback for sha256 so the halo2 backend could just say it is not supported, but we don’t have a fallback for Blake or Pedersen, for example.
So the general recommendation is not to pursue this hybrid shortcut- got it! Will likely scrap the idea.
There isn’t an explicit gadget for pedersen in halo2_gadgets but we did copy an implementation from the zcash/orchard circuit for Pedersen in BattleZips-Halo2. I have not seen anything for Blake yet, however. From the phrasing, I assume it is a requirement to provide opcodes for the black box functions without fallbacks?
Also @Rumata888, I want to quickly explore the difference in how blinding works
Halo2 has u = 2^k - t - 1 rows for lookups/ permutations, using the last t rows for blinding in these polynomials. Then, as you said, a vanishing polynomial t(X)=(X^n−1) is constructed. Pretty sure u + t = n.
Is it correct to assert that Barretenberg essentially moves the t blinding elements from the lookup/ permutation polynomials to the vanishing polynomial?
