#![allow(clippy::too_many_arguments)]
#![allow(clippy::type_complexity)]
use super::commitments::{Commitments, MultiCommitGens};
use super::dense_mlpoly::DensePolynomial;
use super::errors::ProofVerifyError;
use super::group::{CompressedGroup, GroupElement, VartimeMultiscalarMul};
use super::nizk::DotProductProof;
use super::random::RandomTape;
use super::scalar::Scalar;
use super::transcript::{AppendToTranscript, ProofTranscript};
use super::unipoly::{CompressedUniPoly, UniPoly};
use core::iter;
use itertools::izip;
use merlin::Transcript;
use serde::{Deserialize, Serialize};
#[derive(Serialize, Deserialize, Debug)]
pub struct SumcheckInstanceProof {
compressed_polys: Vec<CompressedUniPoly>,
}
impl SumcheckInstanceProof {
pub fn new(compressed_polys: Vec<CompressedUniPoly>) -> SumcheckInstanceProof {
SumcheckInstanceProof { compressed_polys }
}
pub fn verify(
&self,
claim: Scalar,
num_rounds: usize,
degree_bound: usize,
transcript: &mut Transcript,
) -> Result<(Scalar, Vec<Scalar>), ProofVerifyError> {
let mut e = claim;
let mut r: Vec<Scalar> = Vec::new();
assert_eq!(self.compressed_polys.len(), num_rounds);
for i in 0..self.compressed_polys.len() {
let poly = self.compressed_polys[i].decompress(&e);
assert_eq!(poly.degree(), degree_bound);
assert_eq!(poly.eval_at_zero() + poly.eval_at_one(), e);
poly.append_to_transcript(b"poly", transcript);
let r_i = transcript.challenge_scalar(b"challenge_nextround");
r.push(r_i);
e = poly.evaluate(&r_i);
}
Ok((e, r))
}
}
#[derive(Serialize, Deserialize, Debug)]
pub struct ZKSumcheckInstanceProof {
comm_polys: Vec<CompressedGroup>,
comm_evals: Vec<CompressedGroup>,
proofs: Vec<DotProductProof>,
}
impl ZKSumcheckInstanceProof {
pub fn new(
comm_polys: Vec<CompressedGroup>,
comm_evals: Vec<CompressedGroup>,
proofs: Vec<DotProductProof>,
) -> Self {
ZKSumcheckInstanceProof {
comm_polys,
comm_evals,
proofs,
}
}
pub fn verify(
&self,
comm_claim: &CompressedGroup,
num_rounds: usize,
degree_bound: usize,
gens_1: &MultiCommitGens,
gens_n: &MultiCommitGens,
transcript: &mut Transcript,
) -> Result<(CompressedGroup, Vec<Scalar>), ProofVerifyError> {
assert_eq!(gens_n.n, degree_bound + 1);
assert_eq!(self.comm_polys.len(), num_rounds);
assert_eq!(self.comm_evals.len(), num_rounds);
let mut r: Vec<Scalar> = Vec::new();
for i in 0..self.comm_polys.len() {
let comm_poly = &self.comm_polys[i];
comm_poly.append_to_transcript(b"comm_poly", transcript);
let r_i = transcript.challenge_scalar(b"challenge_nextround");
let res = {
let comm_claim_per_round = if i == 0 {
comm_claim
} else {
&self.comm_evals[i - 1]
};
let comm_eval = &self.comm_evals[i];
comm_claim_per_round.append_to_transcript(b"comm_claim_per_round", transcript);
comm_eval.append_to_transcript(b"comm_eval", transcript);
let w = transcript.challenge_vector(b"combine_two_claims_to_one", 2);
let comm_target = GroupElement::vartime_multiscalar_mul(
w.iter(),
iter::once(&comm_claim_per_round)
.chain(iter::once(&comm_eval))
.map(|pt| pt.decompress().unwrap())
.collect::<Vec<GroupElement>>(),
)
.compress();
let a = {
let a_sc = {
let mut a = vec![Scalar::one(); degree_bound + 1];
a[0] += Scalar::one();
a
};
let a_eval = {
let mut a = vec![Scalar::one(); degree_bound + 1];
for j in 1..a.len() {
a[j] = a[j - 1] * r_i;
}
a
};
assert_eq!(a_sc.len(), a_eval.len());
(0..a_sc.len())
.map(|i| w[0] * a_sc[i] + w[1] * a_eval[i])
.collect::<Vec<Scalar>>()
};
self.proofs[i]
.verify(
gens_1,
gens_n,
transcript,
&a,
&self.comm_polys[i],
&comm_target,
)
.is_ok()
};
if !res {
return Err(ProofVerifyError::InternalError);
}
r.push(r_i);
}
Ok((self.comm_evals[self.comm_evals.len() - 1], r))
}
}
impl SumcheckInstanceProof {
pub fn prove_cubic<F>(
claim: &Scalar,
num_rounds: usize,
poly_A: &mut DensePolynomial,
poly_B: &mut DensePolynomial,
poly_C: &mut DensePolynomial,
comb_func: F,
transcript: &mut Transcript,
) -> (Self, Vec<Scalar>, Vec<Scalar>)
where
F: Fn(&Scalar, &Scalar, &Scalar) -> Scalar,
{
let mut e = *claim;
let mut r: Vec<Scalar> = Vec::new();
let mut cubic_polys: Vec<CompressedUniPoly> = Vec::new();
for _j in 0..num_rounds {
let mut eval_point_0 = Scalar::zero();
let mut eval_point_2 = Scalar::zero();
let mut eval_point_3 = Scalar::zero();
let len = poly_A.len() / 2;
for i in 0..len {
eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
eval_point_2 += comb_func(
&poly_A_bound_point,
&poly_B_bound_point,
&poly_C_bound_point,
);
let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
eval_point_3 += comb_func(
&poly_A_bound_point,
&poly_B_bound_point,
&poly_C_bound_point,
);
}
let evals = vec![eval_point_0, e - eval_point_0, eval_point_2, eval_point_3];
let poly = UniPoly::from_evals(&evals);
poly.append_to_transcript(b"poly", transcript);
let r_j = transcript.challenge_scalar(b"challenge_nextround");
r.push(r_j);
poly_A.bound_poly_var_top(&r_j);
poly_B.bound_poly_var_top(&r_j);
poly_C.bound_poly_var_top(&r_j);
e = poly.evaluate(&r_j);
cubic_polys.push(poly.compress());
}
(
SumcheckInstanceProof::new(cubic_polys),
r,
vec![poly_A[0], poly_B[0], poly_C[0]],
)
}
pub fn prove_cubic_batched<F>(
claim: &Scalar,
num_rounds: usize,
poly_vec_par: (
&mut Vec<&mut DensePolynomial>,
&mut Vec<&mut DensePolynomial>,
&mut DensePolynomial,
),
poly_vec_seq: (
&mut Vec<&mut DensePolynomial>,
&mut Vec<&mut DensePolynomial>,
&mut Vec<&mut DensePolynomial>,
),
coeffs: &[Scalar],
comb_func: F,
transcript: &mut Transcript,
) -> (
Self,
Vec<Scalar>,
(Vec<Scalar>, Vec<Scalar>, Scalar),
(Vec<Scalar>, Vec<Scalar>, Vec<Scalar>),
)
where
F: Fn(&Scalar, &Scalar, &Scalar) -> Scalar,
{
let (poly_A_vec_par, poly_B_vec_par, poly_C_par) = poly_vec_par;
let (poly_A_vec_seq, poly_B_vec_seq, poly_C_vec_seq) = poly_vec_seq;
let mut e = *claim;
let mut r: Vec<Scalar> = Vec::new();
let mut cubic_polys: Vec<CompressedUniPoly> = Vec::new();
for _j in 0..num_rounds {
let mut evals: Vec<(Scalar, Scalar, Scalar)> = Vec::new();
for (poly_A, poly_B) in poly_A_vec_par.iter().zip(poly_B_vec_par.iter()) {
let mut eval_point_0 = Scalar::zero();
let mut eval_point_2 = Scalar::zero();
let mut eval_point_3 = Scalar::zero();
let len = poly_A.len() / 2;
for i in 0..len {
eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C_par[i]);
let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
let poly_C_bound_point = poly_C_par[len + i] + poly_C_par[len + i] - poly_C_par[i];
eval_point_2 += comb_func(
&poly_A_bound_point,
&poly_B_bound_point,
&poly_C_bound_point,
);
let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
let poly_C_bound_point = poly_C_bound_point + poly_C_par[len + i] - poly_C_par[i];
eval_point_3 += comb_func(
&poly_A_bound_point,
&poly_B_bound_point,
&poly_C_bound_point,
);
}
evals.push((eval_point_0, eval_point_2, eval_point_3));
}
for (poly_A, poly_B, poly_C) in izip!(
poly_A_vec_seq.iter(),
poly_B_vec_seq.iter(),
poly_C_vec_seq.iter()
) {
let mut eval_point_0 = Scalar::zero();
let mut eval_point_2 = Scalar::zero();
let mut eval_point_3 = Scalar::zero();
let len = poly_A.len() / 2;
for i in 0..len {
eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
eval_point_2 += comb_func(
&poly_A_bound_point,
&poly_B_bound_point,
&poly_C_bound_point,
);
let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
eval_point_3 += comb_func(
&poly_A_bound_point,
&poly_B_bound_point,
&poly_C_bound_point,
);
}
evals.push((eval_point_0, eval_point_2, eval_point_3));
}
let evals_combined_0 = (0..evals.len()).map(|i| evals[i].0 * coeffs[i]).sum();
let evals_combined_2 = (0..evals.len()).map(|i| evals[i].1 * coeffs[i]).sum();
let evals_combined_3 = (0..evals.len()).map(|i| evals[i].2 * coeffs[i]).sum();
let evals = vec![
evals_combined_0,
e - evals_combined_0,
evals_combined_2,
evals_combined_3,
];
let poly = UniPoly::from_evals(&evals);
poly.append_to_transcript(b"poly", transcript);
let r_j = transcript.challenge_scalar(b"challenge_nextround");
r.push(r_j);
for (poly_A, poly_B) in poly_A_vec_par.iter_mut().zip(poly_B_vec_par.iter_mut()) {
poly_A.bound_poly_var_top(&r_j);
poly_B.bound_poly_var_top(&r_j);
}
poly_C_par.bound_poly_var_top(&r_j);
for (poly_A, poly_B, poly_C) in izip!(
poly_A_vec_seq.iter_mut(),
poly_B_vec_seq.iter_mut(),
poly_C_vec_seq.iter_mut()
) {
poly_A.bound_poly_var_top(&r_j);
poly_B.bound_poly_var_top(&r_j);
poly_C.bound_poly_var_top(&r_j);
}
e = poly.evaluate(&r_j);
cubic_polys.push(poly.compress());
}
let poly_A_par_final = (0..poly_A_vec_par.len())
.map(|i| poly_A_vec_par[i][0])
.collect();
let poly_B_par_final = (0..poly_B_vec_par.len())
.map(|i| poly_B_vec_par[i][0])
.collect();
let claims_prod = (poly_A_par_final, poly_B_par_final, poly_C_par[0]);
let poly_A_seq_final = (0..poly_A_vec_seq.len())
.map(|i| poly_A_vec_seq[i][0])
.collect();
let poly_B_seq_final = (0..poly_B_vec_seq.len())
.map(|i| poly_B_vec_seq[i][0])
.collect();
let poly_C_seq_final = (0..poly_C_vec_seq.len())
.map(|i| poly_C_vec_seq[i][0])
.collect();
let claims_dotp = (poly_A_seq_final, poly_B_seq_final, poly_C_seq_final);
(
SumcheckInstanceProof::new(cubic_polys),
r,
claims_prod,
claims_dotp,
)
}
}
impl ZKSumcheckInstanceProof {
pub fn prove_quad<F>(
claim: &Scalar,
blind_claim: &Scalar,
num_rounds: usize,
poly_A: &mut DensePolynomial,
poly_B: &mut DensePolynomial,
comb_func: F,
gens_1: &MultiCommitGens,
gens_n: &MultiCommitGens,
transcript: &mut Transcript,
random_tape: &mut RandomTape,
) -> (Self, Vec<Scalar>, Vec<Scalar>, Scalar)
where
F: Fn(&Scalar, &Scalar) -> Scalar,
{
let (blinds_poly, blinds_evals) = (
random_tape.random_vector(b"blinds_poly", num_rounds),
random_tape.random_vector(b"blinds_evals", num_rounds),
);
let mut claim_per_round = *claim;
let mut comm_claim_per_round = claim_per_round.commit(blind_claim, gens_1).compress();
let mut r: Vec<Scalar> = Vec::new();
let mut comm_polys: Vec<CompressedGroup> = Vec::new();
let mut comm_evals: Vec<CompressedGroup> = Vec::new();
let mut proofs: Vec<DotProductProof> = Vec::new();
for j in 0..num_rounds {
let (poly, comm_poly) = {
let mut eval_point_0 = Scalar::zero();
let mut eval_point_2 = Scalar::zero();
let len = poly_A.len() / 2;
for i in 0..len {
eval_point_0 += comb_func(&poly_A[i], &poly_B[i]);
let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
eval_point_2 += comb_func(&poly_A_bound_point, &poly_B_bound_point);
}
let evals = vec![eval_point_0, claim_per_round - eval_point_0, eval_point_2];
let poly = UniPoly::from_evals(&evals);
let comm_poly = poly.commit(gens_n, &blinds_poly[j]).compress();
(poly, comm_poly)
};
comm_poly.append_to_transcript(b"comm_poly", transcript);
comm_polys.push(comm_poly);
let r_j = transcript.challenge_scalar(b"challenge_nextround");
poly_A.bound_poly_var_top(&r_j);
poly_B.bound_poly_var_top(&r_j);
let (proof, claim_next_round, comm_claim_next_round) = {
let eval = poly.evaluate(&r_j);
let comm_eval = eval.commit(&blinds_evals[j], gens_1).compress();
comm_claim_per_round.append_to_transcript(b"comm_claim_per_round", transcript);
comm_eval.append_to_transcript(b"comm_eval", transcript);
let w = transcript.challenge_vector(b"combine_two_claims_to_one", 2);
let target = w[0] * claim_per_round + w[1] * eval;
let comm_target = GroupElement::vartime_multiscalar_mul(
w.iter(),
iter::once(&comm_claim_per_round)
.chain(iter::once(&comm_eval))
.map(|pt| pt.decompress().unwrap())
.collect::<Vec<GroupElement>>(),
)
.compress();
let blind = {
let blind_sc = if j == 0 {
blind_claim
} else {
&blinds_evals[j - 1]
};
let blind_eval = &blinds_evals[j];
w[0] * blind_sc + w[1] * blind_eval
};
assert_eq!(target.commit(&blind, gens_1).compress(), comm_target);
let a = {
let a_sc = {
let mut a = vec![Scalar::one(); poly.degree() + 1];
a[0] += Scalar::one();
a
};
let a_eval = {
let mut a = vec![Scalar::one(); poly.degree() + 1];
for j in 1..a.len() {
a[j] = a[j - 1] * r_j;
}
a
};
assert_eq!(a_sc.len(), a_eval.len());
(0..a_sc.len())
.map(|i| w[0] * a_sc[i] + w[1] * a_eval[i])
.collect::<Vec<Scalar>>()
};
let (proof, _comm_poly, _comm_sc_eval) = DotProductProof::prove(
gens_1,
gens_n,
transcript,
random_tape,
&poly.as_vec(),
&blinds_poly[j],
&a,
&target,
&blind,
);
(proof, eval, comm_eval)
};
claim_per_round = claim_next_round;
comm_claim_per_round = comm_claim_next_round;
proofs.push(proof);
r.push(r_j);
comm_evals.push(comm_claim_per_round);
}
(
ZKSumcheckInstanceProof::new(comm_polys, comm_evals, proofs),
r,
vec![poly_A[0], poly_B[0]],
blinds_evals[num_rounds - 1],
)
}
pub fn prove_cubic_with_additive_term<F>(
claim: &Scalar,
blind_claim: &Scalar,
num_rounds: usize,
poly_A: &mut DensePolynomial,
poly_B: &mut DensePolynomial,
poly_C: &mut DensePolynomial,
poly_D: &mut DensePolynomial,
comb_func: F,
gens_1: &MultiCommitGens,
gens_n: &MultiCommitGens,
transcript: &mut Transcript,
random_tape: &mut RandomTape,
) -> (Self, Vec<Scalar>, Vec<Scalar>, Scalar)
where
F: Fn(&Scalar, &Scalar, &Scalar, &Scalar) -> Scalar,
{
let (blinds_poly, blinds_evals) = (
random_tape.random_vector(b"blinds_poly", num_rounds),
random_tape.random_vector(b"blinds_evals", num_rounds),
);
let mut claim_per_round = *claim;
let mut comm_claim_per_round = claim_per_round.commit(blind_claim, gens_1).compress();
let mut r: Vec<Scalar> = Vec::new();
let mut comm_polys: Vec<CompressedGroup> = Vec::new();
let mut comm_evals: Vec<CompressedGroup> = Vec::new();
let mut proofs: Vec<DotProductProof> = Vec::new();
for j in 0..num_rounds {
let (poly, comm_poly) = {
let mut eval_point_0 = Scalar::zero();
let mut eval_point_2 = Scalar::zero();
let mut eval_point_3 = Scalar::zero();
let len = poly_A.len() / 2;
for i in 0..len {
eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i], &poly_D[i]);
let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
let poly_D_bound_point = poly_D[len + i] + poly_D[len + i] - poly_D[i];
eval_point_2 += comb_func(
&poly_A_bound_point,
&poly_B_bound_point,
&poly_C_bound_point,
&poly_D_bound_point,
);
let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
let poly_D_bound_point = poly_D_bound_point + poly_D[len + i] - poly_D[i];
eval_point_3 += comb_func(
&poly_A_bound_point,
&poly_B_bound_point,
&poly_C_bound_point,
&poly_D_bound_point,
);
}
let evals = vec![
eval_point_0,
claim_per_round - eval_point_0,
eval_point_2,
eval_point_3,
];
let poly = UniPoly::from_evals(&evals);
let comm_poly = poly.commit(gens_n, &blinds_poly[j]).compress();
(poly, comm_poly)
};
comm_poly.append_to_transcript(b"comm_poly", transcript);
comm_polys.push(comm_poly);
let r_j = transcript.challenge_scalar(b"challenge_nextround");
poly_A.bound_poly_var_top(&r_j);
poly_B.bound_poly_var_top(&r_j);
poly_C.bound_poly_var_top(&r_j);
poly_D.bound_poly_var_top(&r_j);
let (proof, claim_next_round, comm_claim_next_round) = {
let eval = poly.evaluate(&r_j);
let comm_eval = eval.commit(&blinds_evals[j], gens_1).compress();
comm_claim_per_round.append_to_transcript(b"comm_claim_per_round", transcript);
comm_eval.append_to_transcript(b"comm_eval", transcript);
let w = transcript.challenge_vector(b"combine_two_claims_to_one", 2);
let target = w[0] * claim_per_round + w[1] * eval;
let comm_target = GroupElement::vartime_multiscalar_mul(
w.iter(),
iter::once(&comm_claim_per_round)
.chain(iter::once(&comm_eval))
.map(|pt| pt.decompress().unwrap())
.collect::<Vec<GroupElement>>(),
)
.compress();
let blind = {
let blind_sc = if j == 0 {
blind_claim
} else {
&blinds_evals[j - 1]
};
let blind_eval = &blinds_evals[j];
w[0] * blind_sc + w[1] * blind_eval
};
assert_eq!(target.commit(&blind, gens_1).compress(), comm_target);
let a = {
let a_sc = {
let mut a = vec![Scalar::one(); poly.degree() + 1];
a[0] += Scalar::one();
a
};
let a_eval = {
let mut a = vec![Scalar::one(); poly.degree() + 1];
for j in 1..a.len() {
a[j] = a[j - 1] * r_j;
}
a
};
assert_eq!(a_sc.len(), a_eval.len());
(0..a_sc.len())
.map(|i| w[0] * a_sc[i] + w[1] * a_eval[i])
.collect::<Vec<Scalar>>()
};
let (proof, _comm_poly, _comm_sc_eval) = DotProductProof::prove(
gens_1,
gens_n,
transcript,
random_tape,
&poly.as_vec(),
&blinds_poly[j],
&a,
&target,
&blind,
);
(proof, eval, comm_eval)
};
proofs.push(proof);
claim_per_round = claim_next_round;
comm_claim_per_round = comm_claim_next_round;
r.push(r_j);
comm_evals.push(comm_claim_per_round);
}
(
ZKSumcheckInstanceProof::new(comm_polys, comm_evals, proofs),
r,
vec![poly_A[0], poly_B[0], poly_C[0], poly_D[0]],
blinds_evals[num_rounds - 1],
)
}
}