feat: Implement RLC for iterators

[adr1anh]

For ordered collections of a type T where T is homomorphic with regards to a field F, we can implement the trait

trait RandomLinearCombination<F: Field> {
	type Item;
	
	fn random_linear_combination(&self, coefficient: F) -> Self::Item;
}

A default implementation for IntoIterator<Item = T> (or IntoIterator<Item = &T>) would remove a lot of boiler-plate code we currently have. In particular, we would not have to to compute powers of a challenge before zipping it with the iterator.

The random linear combination of items can be computed efficiently using Horner's method. More specifically, we need to iterate in reverse, then fold over the "last" element in the list.

impl RandomLinearCombination<F: Field> for I
where 
	I: Iterator
	I::Item : MulAssign<F> + AddAssign<T>
{
	fn rlc(items: &[T], coeff: F) -> T {
		let mut iter = items.into_iter().rev();
		let first = iter.next().unwrap().clone();
		iter.fold(first, |acc, item| {
			acc *= coefficient
			acc += item
		})
	}
}

Getting the type right here is slightly non-trivial, especially since we want to use it over

• field elements
• group elements/commitments
• vectors (polynomials) of field elements

[huitseeker]

I believe this can be done straightforwardly with the num traits.

Just to clarify: what justifies the adjective random used in the trait? IOW, is there a valid trait you could call LinearCombination that would do all the work you want, once the customer has come up on their own (e.g. randomly) with the coefficient?

[adr1anh]

Looking at the num_traits now, but it's not clear how it would interact with the existing arithmetic ops traits in Arecibo.

Regarding the name, the difference with an actual linear combination is that we would only pass a single challenge as input, rather than a vector of powers. The function can either compute these powers and call a linear combination, or use Horners method. If we are combining group elements for example, we may want to use Horner since we are only performing scalar multiplications with 128-bit challenge.

Now you mention it though, an extension for linear combinations would also be a nice semantic addition to the code.

[huitseeker]

I was using the "num" traits informally due to obscure associations of this name with abstractions that paper over numeric type differences, that was cryptic - sorry.

In precise terms, what you want is just a generic function on completely standard traits that groups and fields (and presumably the collections you have in mind) already implement:

fn rlc<T, F>(i: impl DoubleEndedIterator<Item = T>, coefficient: F) -> T 
  where T: MulAssign<F> + AddAssign<T>, F: Copy,
{
    i.rev().reduce(|mut acc, item| {
        acc *= coefficient;
        acc += item;
        acc
    }).expect("input iterator should not be empty!")
}

Playground link

If we want to do something else than Horner, for parallelism, it can become quite a bit more complicated.

[huitseeker]

See #260