AztecProtocol
Blake3 Noir program bb verification failure
An internal issue for this corresponding aztec-packages issue detailing a UH verification failure for a noir program involving blake3 hashing. Tom indicated that UP also fails for the same program which potentially indicates a circuit issue rather than something in the proving system. Evidently not a specific Blake3 issue. Tom says: "I think it's relatively unlikely to cause issues for outside parties as blake3 isn't one of our more popular hash functions and it's not always failing (tests are passing on other programs which contain blake3)."
Hi, Florin from TACEO here. I was just implementing the Blake3 Blackbox function in coNoir and thought maybe the following insights could be helpful regarding this issue. I think it is somehow related to input size, since this Noir circuit is fine for inputs x of length <=1024, but for bigger ones it returns "Builder failure when we have real witnesses!" while proving, probably during these asserts (https://github.com/AztecProtocol/barretenberg/blob/39cf3b2090a8307e198e02e4f9e73927fe92b08b/cpp/src/barretenberg/dsl/acir_format/blake3_constraint.cpp#L37), where the variables are then not equal in assert_equal (i.e. https://github.com/AztecProtocol/barretenberg/blob/39cf3b2090a8307e198e02e4f9e73927fe92b08b/cpp/src/barretenberg/stdlib_circuit_builders/circuit_builder_base_impl.hpp#L205 is false).
I was running all this with this basic circuit:
fn main(x: [u8; 4]) -> pub [u8; 32] { std::hash::blake3(x) }
Hi, 1024 seems very specific for Blake3 since Blake3 internally handles inputs from 1024 onwards differently. It "hashes" each chunk of at most 1024 bytes separately and combines them by computing a Merkle tree. Maybe this behaviour is missing in the circuits? See, e.g., a (unconstrained) Blake3 in Noir here https://github.com/TaceoLabs/noir-chacha/blob/blake/blake3/src/blake3.nr
After a lot of searching I found this issue: Can confirm: I also have a circuit where I hash slightly over 1024 bytes with blake3 and get an unverifiable proof.
We can confirm that there is indeed an issue with Blake3s for inputs larger than 1024 bytes.
The logic of Blake3 is quite different when the input is larger than 1024 bytes.
For the sake of simplicity, the standard library in Barretenberg only implements the simpler logic for inputs
with less than 1024 bytes.
We have blocked the usage of Blake3s with inputs larger than 1024 bytes in both Noir stdlib and Barretenberg.
