arkworks-rs / arkworks-rs/poly-commit
Sonic KZG10 can merge some pairing operations before pairing
- Dominant language
- Rust
- Stars
- 440
- Forks
- 160
- PR merge metrics
- No merged PRs in 30d
Description
## 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.
```rust
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
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.