Return value witnesses being sorted results in incorrect ABI decoding

rahul-kothari commented 1 year ago

Aim

Computation is done incorrectly when I take a input (public) and return it.

This seems to be a new issue with 0.4.0

Expected behavior

Perform computation as the code is written

Bug

Computation seems be done incorrectly. See the below code snippet where I specifically return a field supplied from the input called rollup_type Input = 1 Output = 0x3 ???? (even though I am simply returning this)

Similarly, I get the current rollup_subtree_height from the input and increment it. Input = 2 Output = 0x83 ????

There are many other cases too that I have not written here for brevity. For example in one case I pass a struct to the input called "constants". And I simply return that in my output struct. Somehow the output constants is very very different!

To reproduce

Code:

use dep::std;
struct ConstantRollupData {
    private_kernel_vk_tree_root: Field,
    public_kernel_vk_tree_root: Field,
    base_rollup_vk_hash: Field,
    merge_rollup_vk_hash: Field,
}
struct BaseOrMergeRollupPublicInputs {
    rollup_type: u1,
    rollup_subtree_height: Field, 
    constants: ConstantRollupData,
    calldata_hash: [u8; 32],
}
struct PreviousRollupData {
    base_or_merge_rollup_public_inputs: BaseOrMergeRollupPublicInputs
}

struct MergeRollupInputs {
    previous_rollup_data_0: PreviousRollupData,
    previous_rollup_data_1: PreviousRollupData,
}

// combine previous two hashes to create a new hash: 
fn compute_calldata_hash(left: BaseOrMergeRollupPublicInputs, right: BaseOrMergeRollupPublicInputs) -> [u8; 32] {
    let mut combined_arr: [u8; 64] = [0; 64];
    for i in 0..32 {
        combined_arr[i] = left.calldata_hash[i];
        combined_arr[i + 32] = right.calldata_hash[i];
    }
    std::hash::sha256(combined_arr)
}

fn main(merge_rollup_inputs: pub MergeRollupInputs) -> pub BaseOrMergeRollupPublicInputs {
    let left: BaseOrMergeRollupPublicInputs = merge_rollup_inputs.previous_rollup_data_0.base_or_merge_rollup_public_inputs;
    let right: BaseOrMergeRollupPublicInputs = merge_rollup_inputs.previous_rollup_data_1.base_or_merge_rollup_public_inputs;

    constrain left.rollup_type == right.rollup_type;
    constrain left.rollup_subtree_height == right.rollup_subtree_height;
    let current_height = left.rollup_subtree_height;

    let new_calldata_hash = compute_calldata_hash(left, right);
    BaseOrMergeRollupPublicInputs {
        rollup_type: left.rollup_type,
        rollup_subtree_height: current_height + 1,
        constants: left.constants,
        calldata_hash: new_calldata_hash,
    }
}

Prover.toml:

[merge_rollup_inputs.previous_rollup_data_0.base_or_merge_rollup_public_inputs]
calldata_hash = [44, 242, 77, 186, 95, 176, 163, 14, 38, 232, 59, 42, 197, 185, 226, 158, 27, 22, 30, 92, 31, 167, 66, 94, 115, 4, 51, 98, 147, 139, 152, 36]
rollup_subtree_height = "2"
rollup_type = "1"
[merge_rollup_inputs.previous_rollup_data_0.base_or_merge_rollup_public_inputs.constants]
private_kernel_vk_tree_root = 0
public_kernel_vk_tree_root = 0
base_rollup_vk_hash = 0
merge_rollup_vk_hash = 0

[merge_rollup_inputs.previous_rollup_data_1.base_or_merge_rollup_public_inputs]
calldata_hash = [44, 242, 77, 186, 95, 176, 163, 14, 38, 232, 59, 42, 197, 185, 226, 158, 27, 22, 30, 92, 31, 167, 66, 94, 115, 4, 51, 98, 147, 139, 152, 36]
rollup_subtree_height = "2"
rollup_type = "1"
[merge_rollup_inputs.previous_rollup_data_1.base_or_merge_rollup_public_inputs.constants]
private_kernel_vk_tree_root = 0
public_kernel_vk_tree_root = 0
base_rollup_vk_hash = 0
merge_rollup_vk_hash = 0

I ran nargo prove p

Verifier's return value is:

[return]

calldata_hash = [...]
rollup_subtree_height = "0x0000000000000000000000000000000000000000000000000000000000000083"
rollup_type = "0x0000000000000000000000000000000000000000000000000000000000000003"

[return.constants]
base_rollup_vk_hash = "0x0000000000000000000000000000000000000000000000000000000000000069"
merge_rollup_vk_hash = "0x0000000000000000000000000000000000000000000000000000000000000062"
private_kernel_vk_tree_root = "0x0000000000000000000000000000000000000000000000000000000000000093"
public_kernel_vk_tree_root = "0x00000000000000000000000000000000000000000000000000000000000000b1"

Note here how

rollup_type: in Noir I do rollup_type = 1 yet return.rollup_type = 0x3
rollup_subtree_height: i increment this in noir. Input =1. Output = 0x83????
constants struct is also very very different to whatever my input was!

Installation method

Binary

Nargo version

nargo 0.4.0 (git version hash: a4b196a248fdef9e80bf8c0551d83b1cf23c4a39, is dirty: false)

@noir-lang/noir_wasm version

No response

@noir-lang/barretenberg version

No response

@noir-lang/aztec_backend version

No response

Additional context

No response

Submission Checklist

[ ] Once I hit submit, I will assign this issue to the Project Board with the appropriate tags.

TomAFrench commented 1 year ago

Hey @rahul-kothari, your reproduction code doesn't compile. Could you fix this so I can try to reproduce/debug?

TomAFrench commented 1 year ago

Ok, I've got down to the minimal reproduction:

Given the same input:

// Prover.toml
[merge_rollup_inputs.previous_rollup_data_0.base_or_merge_rollup_public_inputs]
rollup_subtree_height = "2"
rollup_type = "1"

[merge_rollup_inputs.previous_rollup_data_1.base_or_merge_rollup_public_inputs]
rollup_subtree_height = "2"
rollup_type = "1"

This program executes correctly:

use dep::std;

struct BaseOrMergeRollupPublicInputs {
    rollup_type: u1,
    rollup_subtree_height: Field, 
}
struct PreviousRollupData {
    base_or_merge_rollup_public_inputs: BaseOrMergeRollupPublicInputs
}

struct MergeRollupInputs {
    previous_rollup_data_0: PreviousRollupData,
    previous_rollup_data_1: PreviousRollupData,
}

fn main(merge_rollup_inputs: pub MergeRollupInputs) -> pub BaseOrMergeRollupPublicInputs {
    let left: BaseOrMergeRollupPublicInputs = merge_rollup_inputs.previous_rollup_data_0.base_or_merge_rollup_public_inputs;
    let right: BaseOrMergeRollupPublicInputs = merge_rollup_inputs.previous_rollup_data_1.base_or_merge_rollup_public_inputs;

    constrain left.rollup_type == right.rollup_type;
    constrain left.rollup_subtree_height == right.rollup_subtree_height;
    let current_height = left.rollup_subtree_height;

    BaseOrMergeRollupPublicInputs {
        rollup_subtree_height: current_height,
        rollup_type: left.rollup_type,
    }
}

// Verifier.toml
[merge_rollup_inputs.previous_rollup_data_0.base_or_merge_rollup_public_inputs]
rollup_subtree_height = "0x0000000000000000000000000000000000000000000000000000000000000002"
rollup_type = "0x0000000000000000000000000000000000000000000000000000000000000001"

[merge_rollup_inputs.previous_rollup_data_1.base_or_merge_rollup_public_inputs]
rollup_subtree_height = "0x0000000000000000000000000000000000000000000000000000000000000002"
rollup_type = "0x0000000000000000000000000000000000000000000000000000000000000001"

[return]
rollup_subtree_height = "0x0000000000000000000000000000000000000000000000000000000000000002"
rollup_type = "0x0000000000000000000000000000000000000000000000000000000000000001"

however if we add 1 to the current_height when constructing BaseOrMergeRollupPublicInputs

use dep::std;

struct BaseOrMergeRollupPublicInputs {
    rollup_type: u1,
    rollup_subtree_height: Field, 
}
struct PreviousRollupData {
    base_or_merge_rollup_public_inputs: BaseOrMergeRollupPublicInputs
}

struct MergeRollupInputs {
    previous_rollup_data_0: PreviousRollupData,
    previous_rollup_data_1: PreviousRollupData,
}

fn main(merge_rollup_inputs: pub MergeRollupInputs) -> pub BaseOrMergeRollupPublicInputs {
    let left: BaseOrMergeRollupPublicInputs = merge_rollup_inputs.previous_rollup_data_0.base_or_merge_rollup_public_inputs;
    let right: BaseOrMergeRollupPublicInputs = merge_rollup_inputs.previous_rollup_data_1.base_or_merge_rollup_public_inputs;

    constrain left.rollup_type == right.rollup_type;
    constrain left.rollup_subtree_height == right.rollup_subtree_height;
    let current_height = left.rollup_subtree_height;

    BaseOrMergeRollupPublicInputs {
        rollup_subtree_height: current_height + 1,
        rollup_type: left.rollup_type,
    }
}

// Verifier.toml
[merge_rollup_inputs.previous_rollup_data_0.base_or_merge_rollup_public_inputs]
rollup_subtree_height = "0x0000000000000000000000000000000000000000000000000000000000000002"
rollup_type = "0x0000000000000000000000000000000000000000000000000000000000000001"

[merge_rollup_inputs.previous_rollup_data_1.base_or_merge_rollup_public_inputs]
rollup_subtree_height = "0x0000000000000000000000000000000000000000000000000000000000000002"
rollup_type = "0x0000000000000000000000000000000000000000000000000000000000000001"

[return]
rollup_subtree_height = "0x0000000000000000000000000000000000000000000000000000000000000001"
rollup_type = "0x0000000000000000000000000000000000000000000000000000000000000003"

Notice the difference in the return values.

TomAFrench commented 1 year ago

Taking a look at the ABI for both cases. In the working case the return value is made up of witness elements [1,2] (as it's just regurgitating one of the inputs), and in the broken case the return value is made up of witness elements [2,11].

Witness values:

// Working
{Witness(1): 2, Witness(2): 1, Witness(3): 2, Witness(4): 1, Witness(5): 0, Witness(6): 0, Witness(7): 0, Witness(8): 0, Witness(9): 0, Witness(10): 0}

// Non-working
{Witness(1): 2, Witness(2): 1, Witness(3): 2, Witness(4): 1, Witness(5): 0, Witness(6): 0, Witness(7): 0, Witness(8): 0, Witness(9): 0, Witness(10): 0, Witness(11): 3}

TomAFrench commented 1 year ago

For completeness, the issue here is that we're sorting the return witness indices before we construct the ABI. This means when it comes to decoding the return value we're pulling values from "random" witness indices.

noir-lang / noir