merklesumtreechip sum constraint

[teddav]

I might be wrong, but it seems like the sum constraint in the MerkleSumTreeChip has a useless loop that just ends up creating the same constraint N_CURRENCIES times.

        meta.create_gate("sum constraint", |meta| {
            (0..N_CURRENCIES)
                .map(|_| {
                    let left_balance = meta.query_advice(col_a, Rotation::cur());
                    let right_balance = meta.query_advice(col_b, Rotation::cur());
                    let computed_sum = meta.query_advice(col_c, Rotation::cur());
                    let s = meta.query_selector(sum_selector);
                    s * (left_balance + right_balance - computed_sum)
                })
                .collect::<Vec<_>>()
        });

It loops from 0 to N_CURRENCIES and it seems like it's getting the exact same values at Rotation::cur. Or maybe my understanding of Halo2 is wrong, and each loop would increase the Rotation index?
If we looped, the correct code would be:

meta.create_gate("sum constraint", |meta| {
            (0..N_CURRENCIES)
                .map(|i| {
                    let left_balance = meta.query_advice(col_a, Rotation(i as i32));
                    let right_balance = meta.query_advice(col_b, Rotation(i as i32));
                    let computed_sum = meta.query_advice(col_c, Rotation(i as i32));
                    let s = meta.query_selector(sum_selector);
                    s * (left_balance + right_balance - computed_sum)
                })
                .collect::<Vec<_>>()
        });

But the sum_balances_per_level is supposed to take only the left and right currency and add them. The loop is actually performed in the MstInclusionCircuit, so we should get rid of the loop:

meta.create_gate("sum constraint", |meta| {
  let left_balance = meta.query_advice(col_a, Rotation::cur());
  let right_balance = meta.query_advice(col_b, Rotation::cur());
  let computed_sum = meta.query_advice(col_c, Rotation::cur());
  let s = meta.query_selector(sum_selector);
  vec![s * (left_balance + right_balance - computed_sum)]
});

[SleepingShell]

I agree that this seems like it is looping N^2 times instead of the expected N times (where N is number of currencies).

I don't think we should be taking the index and using it in the rotation since, as you pointed out, the caller is also looping over N.

I'll take a deeper look at this later when I have access to a computer.

[0xalizk]

Cc @alxkzmn