use std::convert::TryFrom;
use std::ops::{AddAssign, MulAssign};
use blstrs::Compress;
use ff::{Field, PrimeField};
use group::{prime::PrimeCurveAffine, Curve};
use log::{debug, info};
use rayon::prelude::*;
use serde::Serialize;
use super::{
commit,
commit::{VKey, WKey},
compress, inner_product,
poly::DensePolynomial,
structured_scalar_power,
transcript::Transcript,
AggregateProof, AggregateProofAndInstance, GipaProof, KZGOpening, ProverSRS,
ProverSRSInputAggregation, TippMippProof,
};
use crate::groth16::{aggregate::AggregateVersion, multiscalar::*, Proof};
use bellpepper_core::SynthesisError;
use pairing::{Engine, MultiMillerLoop};
pub fn aggregate_proofs<E>(
srs: &ProverSRS<E>,
transcript_include: &[u8],
proofs: &[Proof<E>],
version: AggregateVersion,
) -> Result<AggregateProof<E>, SynthesisError>
where
E: MultiMillerLoop + std::fmt::Debug,
E::Fr: Serialize,
<E::Fr as PrimeField>::Repr: Send + Sync,
<E as Engine>::Gt: Compress + Serialize,
E::G1: Serialize,
E::G1Affine: Serialize,
E::G2Affine: Serialize,
{
info!("aggregate_proofs [version {}]", version);
if proofs.len() < 2 {
return Err(SynthesisError::MalformedProofs(
"aggregating less than 2 proofs is not allowed".to_string(),
));
}
if !proofs.len().is_power_of_two() {
return Err(SynthesisError::NonPowerOfTwo);
}
if !srs.has_correct_len(proofs.len()) {
return Err(SynthesisError::MalformedSrs);
}
par! {
let a = proofs.iter().map(|proof| proof.a).collect::<Vec<_>>(),
let b = proofs.iter().map(|proof| proof.b).collect::<Vec<_>>(),
let c = proofs.iter().map(|proof| proof.c).collect::<Vec<_>>()
};
let refa = &a;
let refb = &b;
let refc = &c;
try_par! {
let com_ab = commit::pair::<E>(&srs.vkey, &srs.wkey, refa, refb),
let com_c = commit::single_g1::<E>(&srs.vkey, refc)
};
let hcom = Transcript::<E>::new("hcom")
.write(&com_ab)
.write(&com_c)
.into_challenge();
let r = Transcript::<E>::new("random-r")
.write(&hcom)
.write(&transcript_include)
.into_challenge();
let r_vec: Vec<E::Fr> = structured_scalar_power(proofs.len(), &*r);
let r_inv = r_vec
.par_iter()
.map(|ri| ri.invert().unwrap())
.collect::<Vec<_>>();
let b_r = b
.par_iter()
.zip(r_vec.par_iter())
.map(|(bi, ri)| (bi.to_curve() * ri).to_affine())
.collect::<Vec<_>>();
let refb_r = &b_r;
let refr_vec = &r_vec;
try_par! {
let ip_ab = inner_product::pairing::<E>(refa, refb_r),
let agg_c = inner_product::multiexponentiation::<E::G1Affine>(refc, refr_vec)
};
let wkey_r_inv = srs.wkey.scale(&r_inv)?;
let tmipp = prove_tipp_mipp::<E>(
srs,
&a,
&b_r,
&c,
&wkey_r_inv,
&r_vec,
&ip_ab,
&agg_c,
&hcom,
version,
)?;
debug_assert!({
let computed_com_ab = commit::pair::<E>(&srs.vkey, &wkey_r_inv, &a, &b_r).unwrap();
com_ab == computed_com_ab
});
Ok(AggregateProof {
com_ab,
com_c,
ip_ab,
agg_c,
tmipp,
})
}
pub fn aggregate_proofs_and_instances<E: Engine + std::fmt::Debug>(
srs: &ProverSRSInputAggregation<E>,
transcript_include: &[u8],
statements: &[Vec<E::Fr>],
proofs: &[Proof<E>],
version: AggregateVersion,
) -> Result<AggregateProofAndInstance<E>, SynthesisError>
where
E: MultiMillerLoop + std::fmt::Debug,
E::Fr: Serialize,
<E::Fr as PrimeField>::Repr: Send + Sync,
<E as Engine>::Gt: Compress + Serialize,
E::G1: Serialize,
E::G1Affine: Serialize,
E::G2Affine: Serialize,
{
if statements.len() < 2 {
return Err(SynthesisError::MalformedProofs(
"aggregating less than 2 proofs is not allowed".to_string(),
));
}
assert!(statements.len() > 1);
let n = statements[0].len();
for s in statements {
if s.len() != n {
return Err(SynthesisError::MalformedProofs(
"all statements must be equally sized".to_string(),
));
}
}
let mut com_f: Vec<E::G1> = Vec::new();
let mut com_w0: Vec<E::G1> = Vec::new();
let mut com_wd: Vec<E::G1> = Vec::new();
let mut f_eval: Vec<E::Fr> = Vec::new();
let mut f_eval_proof: Vec<E::G1> = Vec::new();
let mut poly_f: Vec<Vec<E::Fr>> = Vec::new();
for j in 0..n / 2 {
let mut poly_f_j: Vec<E::Fr> = Vec::new();
let mut poly_w0: Vec<E::Fr> = Vec::new();
for i in 0..proofs.len() {
poly_f_j.push(statements[i][j]);
if i < (proofs.len() - 1) {
poly_w0.push(statements[i + 1][j]);
}
}
let poly_f_cp = poly_f_j.clone();
let poly_f_cp_2 = poly_f_j.clone();
let calc_multiscalar = |left: &[E::Fr], table, len: usize| {
let getter = |i: usize| -> <E::Fr as PrimeField>::Repr { left[i].to_repr() };
par_multiscalar::<_, E::G1Affine>(
&ScalarList::Getter(getter, len),
table,
std::mem::size_of::<<E::Fr as PrimeField>::Repr>() * 8,
)
};
let com_f_j = calc_multiscalar(&poly_f_j, &srs.g_alpha_powers_table, proofs.len());
let com_w0_j = calc_multiscalar(&poly_w0, &srs.g_alpha_powers_table, proofs.len() - 1);
let com_wd_j = calc_multiscalar(&poly_f_cp, &srs.g_alpha_powers_end_table, proofs.len());
com_f.push(com_f_j);
com_w0.push(-com_w0_j);
com_wd.push(-com_wd_j);
poly_f.push(poly_f_cp_2);
}
let transcript_new = Transcript::<E>::new("transcript-with-coms")
.write(&com_f)
.write(&com_w0)
.write(&com_wd)
.write(&transcript_include)
.into_bytes();
let pi_agg = aggregate_proofs(srs, &transcript_new, proofs, version).unwrap();
let hcom = Transcript::<E>::new("hcom")
.write(&pi_agg.com_ab)
.write(&pi_agg.com_c)
.into_challenge();
let r = Transcript::<E>::new("random-r")
.write(&hcom)
.write(&transcript_new)
.into_challenge();
for poly_f_j in poly_f {
let mut poly_eval = E::Fr::ZERO;
let mut r_pow = E::Fr::ONE;
for poly_f_j_i in &poly_f_j {
poly_eval += *poly_f_j_i * r_pow;
r_pow *= &*r;
}
f_eval.push(poly_eval);
f_eval_proof.push(
create_kzg_opening_for_instance::<E>(
&srs.g_alpha_powers_table,
DensePolynomial::from_coeffs(poly_f_j.clone()),
poly_eval,
&*r,
)
.unwrap(),
);
}
Ok(AggregateProofAndInstance {
num_inputs: u32::try_from(n).expect("too many statements"),
pi_agg,
com_f,
com_w0,
com_wd,
f_eval,
f_eval_proof,
})
}
#[allow(clippy::too_many_arguments)]
fn prove_tipp_mipp<E>(
srs: &ProverSRS<E>,
a: &[E::G1Affine],
b: &[E::G2Affine],
c: &[E::G1Affine],
wkey: &WKey<E>, r_vec: &[E::Fr],
ip_ab: &<E as Engine>::Gt,
agg_c: &E::G1,
hcom: &E::Fr,
version: AggregateVersion,
) -> Result<TippMippProof<E>, SynthesisError>
where
E: MultiMillerLoop,
E::Fr: Serialize,
<E::Fr as PrimeField>::Repr: Send + Sync,
<E as Engine>::Gt: Compress + Serialize,
E::G1: Serialize,
E::G1Affine: Serialize,
E::G2Affine: Serialize,
{
let r_shift = r_vec[1];
let (proof, mut challenges, mut challenges_inv, extra_challenge) =
gipa_tipp_mipp::<E>(a, b, c, &srs.vkey, wkey, r_vec, ip_ab, agg_c, hcom, version)?;
challenges.reverse();
challenges_inv.reverse();
let r_inverse = r_shift.invert().unwrap();
let z = match version {
AggregateVersion::V1 => Transcript::<E>::new("random-z")
.write(&challenges[0])
.write(&proof.final_vkey.0)
.write(&proof.final_vkey.1)
.write(&proof.final_wkey.0)
.write(&proof.final_wkey.1)
.into_challenge(),
AggregateVersion::V2 => Transcript::<E>::new("random-z")
.write(&extra_challenge)
.write(&proof.final_vkey.0)
.write(&proof.final_vkey.1)
.write(&proof.final_wkey.0)
.write(&proof.final_wkey.1)
.write(&proof.final_a)
.write(&proof.final_b)
.write(&proof.final_c)
.into_challenge(),
};
par! {
let vkey_opening = prove_commitment_v(
&srs.h_alpha_powers_table,
&srs.h_beta_powers_table,
srs.n,
&challenges_inv,
&z,
),
let wkey_opening = prove_commitment_w(
&srs.g_alpha_powers_table,
&srs.g_beta_powers_table,
srs.n,
&challenges,
&r_inverse,
&z,
)
};
Ok(TippMippProof {
gipa: proof,
vkey_opening: vkey_opening?,
wkey_opening: wkey_opening?,
})
}
#[allow(
clippy::many_single_char_names,
clippy::type_complexity,
clippy::too_many_arguments
)]
fn gipa_tipp_mipp<E>(
a: &[E::G1Affine],
b: &[E::G2Affine],
c: &[E::G1Affine],
vkey: &VKey<E>,
wkey: &WKey<E>, r: &[E::Fr],
ip_ab: &<E as Engine>::Gt,
agg_c: &E::G1,
hcom: &E::Fr,
version: AggregateVersion,
) -> Result<(GipaProof<E>, Vec<E::Fr>, Vec<E::Fr>, E::Fr), SynthesisError>
where
E: MultiMillerLoop,
E::Fr: Serialize,
<E::Fr as PrimeField>::Repr: Sync,
<E as Engine>::Gt: Serialize,
E::G1: Serialize,
E::G1Affine: Serialize,
E::G2Affine: Serialize,
{
let (mut m_a, mut m_b) = (a.to_vec(), b.to_vec());
let (mut m_c, mut m_r) = (c.to_vec(), r.to_vec());
let (mut vkey, mut wkey) = (vkey.clone(), wkey.clone());
let mut comms_ab = Vec::new();
let mut comms_c = Vec::new();
let mut z_ab = Vec::new();
let mut z_c = Vec::new();
let mut challenges: Vec<E::Fr> = Vec::new();
let mut challenges_inv: Vec<E::Fr> = Vec::new();
let mut c_inv: E::Fr = *Transcript::<E>::new("gipa-0")
.write(hcom)
.write(ip_ab)
.write(agg_c)
.write(&r[1])
.into_challenge();
let mut c = c_inv.invert().unwrap();
let mut i = 0;
while m_a.len() > 1 {
let split = m_a.len() / 2;
let (a_left, a_right) = m_a.split_at_mut(split);
let (b_left, b_right) = m_b.split_at_mut(split);
let (c_left, c_right) = m_c.split_at_mut(split);
let (r_left, r_right) = m_r.split_at_mut(split);
let (vk_left, vk_right) = vkey.split(split);
let (wk_left, wk_right) = wkey.split(split);
let (rvk_left, rvk_right) = (&vk_left, &vk_right);
let (rwk_left, rwk_right) = (&wk_left, &wk_right);
let (ra_left, ra_right) = (&a_left, &a_right);
let (rb_left, rb_right) = (&b_left, &b_right);
let (rc_left, rc_right) = (&c_left, &c_right);
let (rr_left, rr_right) = (&r_left, &r_right);
try_par! {
let tab_l = commit::pair::<E>(rvk_left, rwk_right, ra_right, rb_left),
let tab_r = commit::pair::<E>(rvk_right, rwk_left, ra_left, rb_right),
let zab_l = inner_product::pairing::<E>(ra_right, rb_left),
let zab_r = inner_product::pairing::<E>(ra_left, rb_right),
let zc_l = inner_product::multiexponentiation::<E::G1Affine>(rc_right, rr_left),
let zc_r = inner_product::multiexponentiation::<E::G1Affine>(rc_left, rr_right),
let tuc_l = commit::single_g1::<E>(rvk_left, rc_right),
let tuc_r = commit::single_g1::<E>(rvk_right, rc_left)
};
if i == 0 {
match version {
AggregateVersion::V1 => {
}
AggregateVersion::V2 => {
c_inv = *Transcript::<E>::new("gipa-0")
.write(&c_inv)
.write(&zab_l)
.write(&zab_r)
.write(&zc_l)
.write(&zc_r)
.write(&tab_l.0)
.write(&tab_l.1)
.write(&tab_r.0)
.write(&tab_r.1)
.write(&tuc_l.0)
.write(&tuc_l.1)
.write(&tuc_r.0)
.write(&tuc_r.1)
.into_challenge();
c = c_inv.invert().unwrap();
}
};
} else {
c_inv = *Transcript::<E>::new(&format!("gipa-{}", i))
.write(&c_inv)
.write(&zab_l)
.write(&zab_r)
.write(&zc_l)
.write(&zc_r)
.write(&tab_l.0)
.write(&tab_l.1)
.write(&tab_r.0)
.write(&tab_r.1)
.write(&tuc_l.0)
.write(&tuc_l.1)
.write(&tuc_r.0)
.write(&tuc_r.1)
.into_challenge();
c = c_inv.invert().unwrap();
}
info!("prover: challenge {} -> {:?}", i, c);
compress(&mut m_a, split, &c);
compress(&mut m_b, split, &c_inv);
compress(&mut m_c, split, &c);
r_left
.par_iter_mut()
.zip(r_right.par_iter_mut())
.for_each(|(r_l, r_r)| {
r_r.mul_assign(&c_inv);
r_l.add_assign(*r_r);
});
let len = r_left.len();
m_r.resize(len, E::Fr::ZERO); vkey = vk_left.compress(&vk_right, &c_inv)?;
wkey = wk_left.compress(&wk_right, &c)?;
comms_ab.push((tab_l, tab_r));
comms_c.push((tuc_l, tuc_r));
z_ab.push((zab_l, zab_r));
z_c.push((zc_l, zc_r));
challenges.push(c);
challenges_inv.push(c_inv);
i += 1;
}
assert!(m_a.len() == 1 && m_b.len() == 1);
assert!(m_c.len() == 1 && m_r.len() == 1);
assert!(vkey.a.len() == 1 && vkey.b.len() == 1);
assert!(wkey.a.len() == 1 && wkey.b.len() == 1);
let (final_a, final_b, final_c) = (m_a[0], m_b[0], m_c[0]);
let (final_vkey, final_wkey) = (vkey.first(), wkey.first());
let (final_zab_l, final_zab_r) = z_ab.last().unwrap();
let (final_zc_l, final_zc_r) = z_c.last().unwrap();
let (final_tab_l, final_tab_r) = comms_ab.last().unwrap();
let (final_tuc_l, final_tuc_r) = comms_c.last().unwrap();
let extra_challenge = *Transcript::<E>::new("gipa-extra-link")
.write(&challenges.last().unwrap())
.write(&final_a)
.write(&final_b)
.write(&final_c)
.write(&final_zab_l)
.write(&final_zab_r)
.write(&final_zc_l)
.write(&final_zc_r)
.write(&final_tab_l.0)
.write(&final_tab_l.1)
.write(&final_tab_r.0)
.write(&final_tab_r.1)
.write(&final_tuc_l.0)
.write(&final_tuc_l.1)
.write(&final_tuc_r.0)
.write(&final_tuc_r.1)
.into_challenge();
debug!("prover: extra challenge {:?}", extra_challenge);
Ok((
GipaProof {
nproofs: a.len() as u32, comms_ab,
comms_c,
z_ab,
z_c,
final_a,
final_b,
final_c,
final_vkey,
final_wkey,
},
challenges,
challenges_inv,
extra_challenge,
))
}
fn prove_commitment_v<G>(
srs_powers_alpha_table: &dyn MultiscalarPrecomp<G>,
srs_powers_beta_table: &dyn MultiscalarPrecomp<G>,
n: usize,
transcript: &[G::Scalar],
kzg_challenge: &G::Scalar,
) -> Result<KZGOpening<G>, SynthesisError>
where
G: PrimeCurveAffine,
<G::Scalar as PrimeField>::Repr: Send + Sync,
{
let vkey_poly = DensePolynomial::from_coeffs(polynomial_coefficients_from_transcript(
transcript,
&G::Scalar::ONE,
));
let vkey_poly_z = polynomial_evaluation_product_form_from_transcript(
transcript,
kzg_challenge,
&G::Scalar::ONE,
);
create_kzg_opening(
srs_powers_alpha_table,
srs_powers_beta_table,
n,
vkey_poly,
vkey_poly_z,
kzg_challenge,
)
}
fn prove_commitment_w<G>(
srs_powers_alpha_table: &dyn MultiscalarPrecomp<G>,
srs_powers_beta_table: &dyn MultiscalarPrecomp<G>,
n: usize,
transcript: &[G::Scalar],
r_shift: &G::Scalar,
kzg_challenge: &G::Scalar,
) -> Result<KZGOpening<G>, SynthesisError>
where
G: PrimeCurveAffine,
<G::Scalar as PrimeField>::Repr: Send + Sync,
{
let mut fcoeffs = polynomial_coefficients_from_transcript(transcript, r_shift);
let mut fwcoeffs = vec![G::Scalar::ZERO; n];
fwcoeffs.append(&mut fcoeffs);
let fw = DensePolynomial::from_coeffs(fwcoeffs);
par! {
let fz = polynomial_evaluation_product_form_from_transcript(transcript, kzg_challenge, r_shift),
let zn = kzg_challenge.pow_vartime(&[n as u64])
};
let mut fwz = fz;
fwz.mul_assign(&zn);
create_kzg_opening(
srs_powers_alpha_table,
srs_powers_beta_table,
2 * n, fw,
fwz,
kzg_challenge,
)
}
fn create_kzg_opening_for_instance<E: Engine>(
srs_powers_alpha_table: &dyn MultiscalarPrecomp<E::G1Affine>, poly: DensePolynomial<E::Fr>,
eval_poly: E::Fr,
kzg_challenge: &E::Fr,
) -> Result<E::G1, SynthesisError> {
let neg_kzg_challenge = -*kzg_challenge;
let quotient_polynomial = &(&poly - &DensePolynomial::from_coeffs(vec![eval_poly]))
/ &(DensePolynomial::from_coeffs(vec![neg_kzg_challenge, E::Fr::ONE]));
let quotient_polynomial_coeffs = quotient_polynomial.into_coeffs();
let pi_open = {
let getter =
|i: usize| -> <E::Fr as PrimeField>::Repr { quotient_polynomial_coeffs[i].to_repr() };
par_multiscalar::<_, E::G1Affine>(
&ScalarList::Getter(getter, quotient_polynomial_coeffs.len()),
srs_powers_alpha_table,
std::mem::size_of::<<E::Fr as PrimeField>::Repr>() * 8,
)
};
Ok(pi_open)
}
fn create_kzg_opening<G>(
srs_powers_alpha_table: &dyn MultiscalarPrecomp<G>, srs_powers_beta_table: &dyn MultiscalarPrecomp<G>, srs_powers_len: usize,
poly: DensePolynomial<G::Scalar>,
eval_poly: G::Scalar,
kzg_challenge: &G::Scalar,
) -> Result<KZGOpening<G>, SynthesisError>
where
G: PrimeCurveAffine,
<G::Scalar as PrimeField>::Repr: Send + Sync,
{
let neg_kzg_challenge = -*kzg_challenge;
if poly.coeffs().len() != srs_powers_len {
return Err(SynthesisError::MalformedSrs);
}
let quotient_polynomial = &(&poly - &DensePolynomial::from_coeffs(vec![eval_poly]))
/ &(DensePolynomial::from_coeffs(vec![neg_kzg_challenge, G::Scalar::ONE]));
let quotient_polynomial_coeffs = quotient_polynomial.into_coeffs();
let quotient_polynomial_coeffs_len = quotient_polynomial_coeffs.len();
let getter = |i: usize| -> <G::Scalar as PrimeField>::Repr {
if i >= quotient_polynomial_coeffs_len {
return G::Scalar::ZERO.to_repr();
}
quotient_polynomial_coeffs[i].to_repr()
};
Ok(rayon::join(
|| {
par_multiscalar::<_, G>(
&ScalarList::Getter(getter, srs_powers_len),
srs_powers_alpha_table,
std::mem::size_of::<<G::Scalar as PrimeField>::Repr>() * 8,
)
.to_affine()
},
|| {
par_multiscalar::<_, G>(
&ScalarList::Getter(getter, srs_powers_len),
srs_powers_beta_table,
std::mem::size_of::<<G::Scalar as PrimeField>::Repr>() * 8,
)
.to_affine()
},
))
}
pub(super) fn polynomial_evaluation_product_form_from_transcript<F: Field>(
transcript: &[F],
z: &F,
r_shift: &F,
) -> F {
let mut power_zr = *z;
power_zr.mul_assign(r_shift);
let one = F::ONE;
let mut res = one + (transcript[0] * power_zr);
for x in &transcript[1..] {
power_zr = power_zr.square();
res.mul_assign(one + (*x * power_zr));
}
res
}
fn polynomial_coefficients_from_transcript<F: Field>(transcript: &[F], r_shift: &F) -> Vec<F> {
let mut coefficients = vec![F::ONE];
let mut power_2_r = *r_shift;
for (i, x) in transcript.iter().enumerate() {
let n = coefficients.len();
if i > 0 {
power_2_r = power_2_r.square();
}
for j in 0..n {
let coeff = coefficients[j] * (*x * power_2_r);
coefficients.push(coeff);
}
}
coefficients
}