arkworks-rs / arkworks-rs/poly-commit

Sonic KZG10 can merge some pairing operations before pairing

Open
#85 0 comments 0 reactions 0 assignees View on GitHub
D-easy P-medium T-performance
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.