[BUG] bb generates invalid zk proof for large circuits

[DimitrisPapac]

What are you trying to do?

I've been experimenting with circuits involving a large evaluation domain; in particular cases where LOG_N > 20. I crafted a Noir program for which bb generates an invalid proof for the evm target. Interestingly enough, for the same program, changing the target to evm-no-std will actually produce a valid proof. This seems to be a bug so thought it might be constructive to share this information here. Perhaps there is some overflow somewhere in bb that is linked to the zero-knowledge flavor? Please note that I am using bb v3.0.3 and nargo 1.0.0-beta.17. The contents of main.nr and Prover.toml can be found under "Code Reference" down below.

To reproduce the issue, please follow the steps below:

• Step 1: Paste the program into main.nr and run nargo check to generate the Prover.toml.

• Step 2: Paste the inputs into the Prover.toml file and issue nargo execute.

• Step 3: Issue bb write_vk -t evm -b ./target/hello_world.json -o ./target to generate the verification key.

• Step 4: Issue bb prove -t evm -b ./target/hello_world.json -w ./target/hello_world.gz -o ./target to generate the proof and public inputs artifacts.

• Step 5: Issue bb verify -t evm -p ./target/proof -k ./target/vk -i ./target/public_inputs and you should see the "Proof verification failed" message.

To see that the non-zk flavor succeeds, simply repeat the above process, replacing -t evm with -t evm-no-zk in steps 3-5. This time verification should actually succeed. If you generate the Solidity contract(s), you can see that the given program corresponds to LOG_N=26. I have not encountered this issue for smaller values of LOG_N.

Code Reference

The main.nr file contains the following program:

global PAD_FACTOR: u32 = 4300000;
fn main(x: u64, y1: pub u64, y2: pub u64, y3: pub u64, y4: pub u64, y5: pub u64, y6: pub u64, y7: pub u64, y8: pub u64, y9: pub u64, y10: pub u64, y11: pub u64, y12: pub u64, y13: pub u64, y14: pub u64, y15: pub u64, y16: pub u64, y17: pub u64, y18: pub u64, y19: pub u64, y20: pub u64, y21: pub u64, y22: pub u64, y23: pub u64, y24: pub u64, y25: pub u64, y26: pub u64, y27: pub u64, y28: pub u64, y29: pub u64, y30: pub u64, y31: pub u64, y32: pub u64) {
    assert(x != y1);
    assert(x != y2);
    assert(x != y3);
    assert(x != y4);
    assert(x != y5);
    assert(x != y6);
    assert(x != y7);
    assert(x != y8);
    assert(x != y9);
    assert(x != y10);
    assert(x != y11);
    assert(x != y12);
    assert(x != y13);
    assert(x != y14);
    assert(x != y15);
    assert(x != y16);
    assert(x != y17);
    assert(x != y18);
    assert(x != y19);
    assert(x != y20);
    assert(x != y21);
    assert(x != y22);
    assert(x != y23);
    assert(x != y24);
    assert(x != y25);
    assert(x != y26);
    assert(x != y27);
    assert(x != y28);
    assert(x != y29);
    assert(x != y30);
    assert(x != y31);
    assert(x != y32);

    let mut val = x;

    for _ in 0..PAD_FACTOR {
        val = (val + 1) - 1; 
    }

    assert(val == x);
}

#[test]
fn test_main() {
    main(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32);
}

The Prover.toml file contains the following inputs:

x = "0"
y1 = "1"
y2 = "2"
y3 = "3"
y4 = "4"
y5 = "5"
y6 = "6"
y7 = "7"
y8 = "8"
y9 = "9"
y10 = "10"
y11 = "11"
y12 = "12"
y13 = "13"
y14 = "14"
y15 = "15"
y16 = "16"
y17 = "17"
y18 = "18"
y19 = "19"
y20 = "20"
y21 = "21"
y22 = "22"
y23 = "23"
y24 = "24"
y25 = "25"
y26 = "26"
y27 = "27"
y28 = "28"
y29 = "29"
y30 = "30"
y31 = "31"
y32 = "32"

Finally, for full transparency, the Nargo.toml file is the following:

[package]
name = "hello_world"
type = "bin"
authors = [""]

[dependencies]

Aztec Version

bb 3.0.3 and nargo 1.0.0-beta.17

OS

MacOS

Browser (if relevant)

No response

Node Version

No response

Additional Context

In case hardware is relevant, I ran the above process on a MacBook M4 Pro with 48 GB of RAM.