[M-1] Unbounded instance sizes allow verifier DoS

[this-vishalsingh]

Context: halo2_backend/src/plonk/verifier.rs

Description

verify_proof_with_strategy only checks the number of instance columns but does not bound the number of rows (length) per instance column.
A caller can provide extremely large instances vectors, causing the verifier to
(1) hash all provided scalars into the transcript and
(2) allocate and compute l_i_range(...) over a range derived from max_instance_len,
which can lead to very large memory allocations and expensive exponentiations/inversions.

In a service that verifies attacker-supplied proofs/public inputs, this becomes a trivial CPU/memory denial-of-service.

Impacted code :

// Check that instances matches the expected number of instance columns
for instances in instances.iter() {
    if instances.len() != vk.cs.num_instance_columns {
        return Err(Error::InvalidInstances);
    }
}

// Hash instances into transcript
for instance in instances.iter() {
    for instance in instance.iter() {
        for value in instance.iter() {
            transcript.common_scalar(*value)?;
        }
    }
}

let max_instance_len = instances
    .iter()
    .flat_map(|instance| instance.iter().map(|instance| instance.len()))
    .max_by(Ord::cmp)
    .unwrap_or_default();
let l_i_s = &vk.domain.l_i_range(
    *x,
    xn,
    -max_rotation..max_instance_len as i32 + min_rotation.abs(),
);

Recommendation

Enforce a strict bound on each instance column length before hashing/processing (typically equal to the circuit/domain size, e.g., params.n()
or
another VK-defined expected row count).

Reject proofs with oversized (or otherwise unexpected) instance lengths early, before transcript absorption and l_i_range computation.

[adamsmo]

if you are calling params.n() you already allocaeted that memory,
for it to make sense the limit should be placed on deserializing instances and proof, those are provided here
the limit should not be baked into the library that is processing the data
and what the exact bound suppose to be, 42? 42k?