arkworks-rs / arkworks-rs/poly-commit

Add possibility to commit to sparse polynomials in KZG

Open
#169 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
440
Forks
160
PR merge metrics
No merged PRs in 30d

Description

## Summary

Add a commitment methods that allows to compute (non hiding, non degree-bounding) commitments of sparse polynomials.

## Problem Definition

Currently, KZG only allows commitment to DensePoly, then runs an MSM, which takes some time. However, a verifier might need to compute commitments of monomials or sparse polys, e.g. X^(n-k), X - a or X^n - 1. In these situations, a naive computation from the powers of g gives a boost when compared to MSM, since there are very few group elements to multiply together.

Of course, the feature only makes sense in the case where there is no hiding polynomial added to the commitment, but this is always the case for the verifier. The API documentation should make clear that this new method is only intended for verifier purposes.

## Proposal

The first idea I had was to extend the impl definition of `KZG10<_, P: DenseUVPolynomial>` to maybe `DenseOrSparsePolynomial`, but this would open a rabbit whole that does not look promising.

Instead, I suggest to add a method `commit_sparse(powers:&Powers<'_, E>, sparse_polynomial: &SparsePolynomial)`, that will naively compute prod (g^(alpha^i))^p_i. This modification also implies to make the `coeffs` field of SparsePolynomial public.

In my code (using poly_commit v0.3.0), this reduced verifier time by 95%, when working on Domains of size 2^18. I did not see any regression on smaller domains (say 2^8) either.

In order to limit confusion as to when to use this new method, it might be better to name it "sparse_commit_for_verifier" or something similar, but I think "sparse_commit" with a good enough documentation is sufficient.
____

#### 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.