Sonic KZG10 can merge some pairing operations before pairing

[weikengchen]

Summary

In Aleo, we notice that Sonic/AuroraLight KZG10 has space for optimization in the pairing equation check.
https://github.com/arkworks-rs/poly-commit/blob/master/src/sonic_pc/mod.rs#L106

Problem Definition

Currently, when Sonic handle k combined comms, it provides k+2 entries to the Millier loop.

         for (degree_bound, comm) in combined_comms.into_iter() {
            let shift_power = if let Some(degree_bound) = degree_bound {
                vk.get_shift_power(degree_bound)
                    .ok_or(Error::UnsupportedDegreeBound(degree_bound))?
            } else {
                vk.prepared_h.clone()
            };

            g1_projective_elems.push(comm);
            g2_prepared_elems.push(shift_power);
        }

        g1_projective_elems.push(-combined_adjusted_witness);
        g2_prepared_elems.push(vk.prepared_h.clone());

        g1_projective_elems.push(-combined_witness);
        g2_prepared_elems.push(vk.prepared_beta_h.clone());

However, indeed you can reduce it to l+2 where l is the number of combined comms that require a degree bound. Basically, all the entries where the second term is prepared_h can be put together.

Proposal

Sum the combined comms that do not require a degree bound first and then combine it with the existing entry about witness, on prepared_h.

---

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned