BB Prover Error in 'MemBn254CrsFactory'

[MarkCampbell90]

Hello,
I was asked to also open an issue here because the following behavior might be prover related. (original issue on the noir github project)

Original

I tried to execute and prove following toy noir program and input using the bb-prover:

// main.nr
pub fn main(input : Field) -> pub Field {
    let mut output : Field = 0;
    output = input;
    let zero = 0;
    let b1 : [u8; 32] = zero.to_be_bytes();
    let b2 : [u8; 32] = input.to_be_bytes();
    let mut b3 : [u8; 32] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    for i in 0..32 {
        b3[i] = (b1[i] | b2[i]);
    }
    assert(!(0 == std::field::bytes32_to_field(b3)), "example assertion");
    output
}

// Prover.toml
input="1"

I used following commands and got following output:

$> nargo execute --force witness --expression-width 4
[Test] Circuit witness successfully solved
[Test] Circuit output: Field(1)
[Test] Witness saved to /app/noir-example/target/witness.gz

$> bb prove -b target/Test.json -w target/witness.gz -o proof
prover trying to get too many points in MemBn254CrsFactory! 205 vs 257

I used nargo version 0.34.0 and bb version 0.55.0

Addition Info

Following code is an even more minimal example with the same behavior:

fn main(input : Field) -> pub Field {
    let b2 : [u8; 32] = input.to_be_bytes();
    let b2_f = std::field::bytes32_to_field(b2); 
    assert(0 != b2_f, "example assertion");
    0
}

It was mentioned in this comment of the original issue.

[ludamad]

@lucasxia01 this looks related to AztecProtocol/barretenberg#1097

[lucasxia01]

Yea, it looks related. I can bump things up for now... maybe won't investigate until later when I optimize the SRS.

[lucasxia01]

Can you use an old version of bb in the meantime until this fix comes in?

[MarkCampbell90]

Thank you for looking into this!
I will try to work with an older version for now.

Just out of curiosity, could you explain what the bug is?

[lucasxia01]

Not sure what the bug is, but I'll update you once I look into it.

[lucasxia01]

It seems to be a mismatch of gate counting. We estimate fewer gates when we generate the SRS than we should be, so we don't store enough points for when we want to commitment to polynomials.

It's unclear to me how this problem is arising now. Have you tried older versions and gotten the same issue?

[MarkCampbell90]

For older versions of bb (I tried 0.52.0 and 0.49.0 using bbup), I get the error: Unknown variant index for enum.
So I believe I hit something else there. Maybe the olderbb versions are not compatible with nargo 0.34.0?

[MarkCampbell90]

I also found a "much" older version bb 0.41.0 and nargo 0.30.0. Here the program passed execution and proving, BUT i had to adapt it:

use dep::std;

pub fn main(input : Field) -> pub Field {
    let mut output : Field = 0;
    output = input;
    let zero = 0;
    let b1 : [u8] = zero.to_be_bytes(32);
    let b2 : [u8] = input.to_be_bytes(32);
    let mut b3 : [u8; 32] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    for i in 0..32 {
        b3[i] = (b1[i] | b2[i]);
    }
    assert(!(0 == std::field::bytes32_to_field(b3)), "example assertion");
    output
}

Maybe it has something to do with the change of to_be_bytes ?

[MarkCampbell90]

For the same adapted program, I get an error for versions bb 0.46.1 and nargo 0.32.0:

bb: /home/runner/work/aztec-packages/aztec-packages/barretenberg/cpp/src/barretenberg/plonk/work_queue/work_queue.cpp:210: void bb::plonk::work_queue::process_queue(): Assertion `(msm_size <= key->reference_string->get_monomial_size())' failed.
Aborted

I believe these are all the versions I could quickly find on my machine, hope it helps!

[MarkCampbell90]

I believe what ever was done in this noir commit fixes this issue (pin-pointed using git bisect ).

Oldest version that works:

> nargo --version
nargo version = 0.34.0
noirc version = 0.34.0+b280a79cf8a4fd2a97200e5436e0ec7cb7134711
(git version hash: b280a79cf8a4fd2a97200e5436e0ec7cb7134711, is dirty: false)

> bb --version
0.55.0

I also tested it with bb 0.56.0 (and newer noir versions) and I cannot reproduce the mentioned behavior.

@lucasxia01 do you want to keep the issue open or is it resolved from your side?

[lucasxia01]

Ah, I would doubt that actually fixed the underlying issue; I think it probably changed the gate counts so that it no longer ran into this edge case. However, I did push a commit last week that should have resolved any weird gate counting discrepancy issues, so I'm hopeful the issue is actually resolved. This fix would be in bb 0.58.0 I think.

I think we can close this issue though.

[MarkCampbell90]

I will check it against one of the previously failing noir commits.
The change you are referring to is this commit right?

[MarkCampbell90]

Ok it seems that #9046 has now actually fixed it :)
I compared against the predecessor commit before the error does no longer occur in noir, i.e. noir-lang/noir@79f8954 and the commit before the gate counting fix :

• 72e4867 with noir-lang/noir@79f8954 ==> failure
• 0bda0a4 with noir-lang/noir@79f8954 ==> success