Description

In circuits/src/utils/hashing.rs, the select_with_bitmask function is implemented as follows:

/// Selects the right `elements` using `bitmask`.
///
/// # Note
///
/// The elements in `bitmask` must be constrained to be booleans.
fn select_with_bitmask<F: EccPrimeField>(
    ctx: &mut Context<F>,
    chip: &GateChip<F>,
    bitmask: &[AssignedValue<F>],
    elements: Vec<Vec<AssignedValue<F>>>,
) -> Vec<AssignedValue<F>> {
    assert_eq!(
        bitmask.len(),
        elements.len(),
        "Bitmask and elements length mismatch"
    );
    let inner_len = elements
        .first()
        .expect("elements must have at least one element")
        .len();
    let mut result = Vec::with_capacity(inner_len);
    for index in 0..inner_len {
        let elmts = elements.iter().map(|inner_vec| inner_vec[index]);
        let bits = bitmask.iter().map(|b| QuantumCell::<F>::from(*b));
        result.push(chip.inner_product(ctx, elmts, bits))
    }
    result
}

This function is intended to select the inner list from the list of lists elements that is specified via the bitmask bitmask. So for example, if bitmask = [0, 1] and elements = [[x,y,z], [a,b,c]], then it would return a list of circuit variables constrained to be equal to [a,b,c]. The description so far would also make sense if the inner lists had different lengths. For example, it would be reasonable that for bitmask = [0, 1] and elements = [[x], [a,b,c]], the return value should still be [a,b,c]. However, as the implementation obtains the length of the list that is returned from the length of the first inner list, only [a] would be returned.

Impact

The current in-scope codebase does not appear to call select_with_bitmask with arguments elements where the lengths of the inner lists differ. However, future coding mistakes in seemingly unrelated parts of the code could cause issues. For example, if elements were prepended by an empty list by accident, then select_with_bitmask would always return an empty list without erroring, which could lead to, for example, not hashing elements that were intended to be hashed.

Recommendations

We recommend to document that this function assumes all inner lists are of the same length and to assert this in the implementation as well to prevent accidental incorrect uses in the future.

Remediation

This issue has been acknowledged by Nebra, and a fix was implemented in commit 59df2dc3↗.