Module ark_poly_commit::streaming_kzg

source ·
Expand description

Streaming polynomial commitment based on the construction in [[BCHO22, “Gemini”]][gemini] with batching techniques inspired by [[BDFG20]][bdfg].

[gemini]: [bdfg]: https://eprint.iacr.org/2020/081.pdf The KZG (or Kate) polynomial commitment, space- and time-efficient.

Background

[KZG] commitments are pretty simple:

  • A CommitterKey is consists of a sequence \(\vec G \defeq (G, \tau G, \dots, \tau^DG)\).
  • A Commitment is a polynomial \(f(x)\) is \(C \defeq \langle \vec f, \vec G \rangle \).
  • An EvaluationProof for the polynomial \(f\) in the evaluation point \(\alpha\) is a commitment to the quotient of \(f(x)\) by \((\tau - \alpha)\). The remainder is the evaluation \(f(\alpha)\). When evaluation over points \((\alpha_0, \dots, \alpha_m)\), we can consider at once the quotient of \(f(x)\) by \(Z\) (the polynomial whose roots are \(\alpha_i\)). The remainder is a polynomial \(r\) such that \(r(\alpha_i) = f(\alpha_i)\). We refer to the proof as \(\pi\).

To verify a proof \(\pi\) proving that \(f(\alpha) = \mu\), one considers the pairing equation: \[ e(C, \tau H - \mu H) = e(f - \mu G, H) \] To verify a proof \(\pi\) over a set of points \(f(\alpha_i) = \mu_i\), consider the polynomial \(\nu\) such that \(\nu(\alpha_i) = \mu_i \), and check: \[ e(C, Z) = e(f - \nu, H). \]

It is also possible to open multiple polynomials \(f_0, \dots, f_n\) on the same set of evaluation points by asking the verifier a random challenge \(\eta\), and opening instead \(\sum_i \eta^i f_i \).

Nota bene: despite it is also possible to open multiple polynomials over different points [BDFG20], however this is not currently supported by our implementation.

Examples

When creating a new SRS, one must specify a degree bound max_degree for the commitment polynomials, and a degree bound max_evals for the maximum number of opening points. From the SRS, it is possible to derive the verification key VerifierKey.

use ark_poly_commit::streaming_kzg::CommitterKey;
use ark_bls12_381::{Fr, Bls12_381};

let rng = &mut ark_std::test_rng();
let max_degree = 100;
let max_evals = 10;

let ck = CommitterKey::<Bls12_381>::new(max_degree, max_evals, rng);

Then to commit to a polynomial f:

ⓘ
let f = vec![Fr::from(1u64), Fr::from(2u64), Fr::from(4u64), Fr::from(8u64)];
let commitment  = ck.commit(&f);

To prove the evaluation of f in a point alpha:

ⓘ
let alpha = Fr::from(42u64);
let (evaluation, proof) = ck.open(&f, &alpha);

To veify that an opening is correct:

ⓘ
use gemini::kzg::VerifierKey;

let vk = VerifierKey::from(&ck);
assert!(vk.verify(&commitment, &alpha, &evaluation, &proof).is_ok())

Structs

  • Commitment
    A Kate polynomial commitment over a bilinear group, represented as a single \(\GG_1\) element.
  • CommitterKey
    The SRS for the polynomial commitment scheme for a max
  • CommitterKeyStream
    The streaming SRS for the polynomial commitment scheme consists of a stream of consecutive powers of g. It also implements functions for setup, commit and open.
  • EvaluationProof
    Polynomial evaluation proof, represented as a single \(\GG_1\) element.
  • FoldedPolynomialStream
    Stream implementation of foleded polynomial.
  • FoldedPolynomialStreamIter
    Iterator implementation of foleded polynomial.
  • FoldedPolynomialTree
    A Streamer folding a vector of coefficients with the given challenges, and producing a stream of items (i, v) where i indicates the depth, and v is the next coefficient. The stream can produce all foldings in the tree with a single pass over the initial stream.
  • FoldedPolynomialTreeIter
    Iterator of the polynomial tree.
  • VerificationError
    Error type denoting an incorrect evaluation proof.
  • VerifierKey
    The verification key for the polynomial commitment scheme. It also implements verification functions for the evaluation proof.