# Random Linear Combination Trick

In a circuit, say you have an array `arr` with `N` elements and you want to prove that an index `selector` (that is dynamically computed) is equal to 0. Normally, you would have to use a `mux` to access the element of the array, which incurs a linear cost for an array access (linear in the length of the array). At a high-level, a `mux` simply iterates over each element of the array, and computes the following quantity

accumulator = 0
for (i = 0; i < 10; i++) {
    include = IsZero(i - selector)
    accumulator += arr[i] * include
}
my_value = accumulator

Given 2 arrays, if you want to prove that `a[a_offset:a_offset+len] == b[b_offset:b_offset+len]`, where `a_offset, b_offset, len` are all variables in the circuit (not constants), then a naive algorithm with `mux` would involve `N^2` cost if both arrays have size `N`.

However, there is a better way. We can instead get randommness from our verifier and compute a random linear combination (RLC for short) of array elements in both arrays that represent the selected range. Then we can assert that these random linear combinations are equal to prove that the subarrays are equal. In particular we compute the following:

// a_rlc = commitment to a[a_offset:a_offset+len]
// b_rlc = commitment to b[b_offset:b_offset+len]

r = random()
a_r = r
b_r = r
a_rlc = 0
b_rlc = 0
for (i = 0; i < N; i++) {
    a_r *= (i > a_offset) ? r : 1
    b_r *= (i > b_offset) ? r : 1
    a_rlc += a[i] * a_r * (i >= a_offset) * (i < a_offset+len)
    b_rlc += b[i] * b_r * (i >= b_offset) * (i < b_offset+len)
}

See if you can convince yourself that `a_rlc == b_rlc` with high probability iff `a[a_offset:a_offset+len] == b[b_offset:b_offset+len]`.

The above is simple to implement in a circuit and only takes `N` cost instead of `N^2`!

## RLC in Plonky2

This is an example of a RLC trick that our team member implemented (don't need to understand exactly what's going on below, but hopefully it's some helpful context)

use plonky2::iop::challenger::RecursiveChallenger;

// Parse the data root field.
// For this, we will use a generator to extract the data root field from the header bytes.
// To verify that it is correct, we will use a method similar to reduce a row to a value
// (https://wiki.polygon.technology/docs/miden/design/multiset#computing-a-virtual-tables-trace-column).
// To retrieve the randomness, we use plonky2's recursive challenger seeding it with 3 elements of 56 bits from the header hash.
// We do the verification twice to increase the security of it.
let mut data_root_target = Vec::new();

let mut challenger = RecursiveChallenger::<F, PoseidonHash, D>::new(self);
// Seed the challenger with 3 elements of 56 bits from the header hash.
let mut seed = Vec::new();
for i in 0..3 {
    let seed_bytes: [Target; 7] = header_hash.0[i * 7..i * 7 + 7].try_into().unwrap();

    // This code is splitting the bytes into bits and then recombining them into a 56 bit target.
    // TODO:  This can be done by just combining the bytes directly.
    let seed_bits = seed_bytes
        .iter()
        .flat_map(|t| self.split_le(*t, 8))
        .collect::<Vec<_>>();

    seed.push(self.le_sum(seed_bits.iter()));
}

challenger.observe_elements(&seed);

for _i in 0..2 {
    let challenges = challenger.get_n_challenges(self, 32);
    let data_root_size = self.constant(F::from_canonical_usize(32));
    let data_root_start_idx = self.sub(header.header_size, data_root_size);
    let mut within_sub_array = self.zero();
    let one = self.one();

    let mut accumulator1 = self.zero();
    let mut j_target = self.zero();
    for j in 0..MAX_HEADER_SIZE {
        let at_start_idx = self.is_equal(j_target, data_root_start_idx);
        within_sub_array = self.add(within_sub_array, at_start_idx.target);
        let at_end_idx = self.is_equal(j_target, header.header_size);
        within_sub_array = self.sub(within_sub_array, at_end_idx.target);

        let mut subarray_idx = self.sub(j_target, data_root_start_idx);
        subarray_idx = self.mul(subarray_idx, within_sub_array);
        let challenge = self.random_access(subarray_idx, challenges.clone());
        let mut product = self.mul(header.header_bytes[j], challenge);
        product = self.mul(within_sub_array, product);
        accumulator1 = self.add(accumulator1, product);

        j_target = self.add(j_target, one);
    }

    let mut accumulator2 = self.zero();
    for j in 0..HASH_SIZE {
        let product = self.mul(data_root_target[j], challenges[j]);
        accumulator2 = self.add(accumulator2, product);
    }

    self.connect(accumulator1, accumulator2);
}