1//! Main module for the ZeroCheck protocol.
  2
  3use std::fmt::Debug;
  4
  5use crate::poly_iop::{errors::PolyIOPErrors, sum_check::SumCheck, PolyIOP};
  6use arithmetic::eq_eval;
  7use ark_ff::PrimeField;
  8use ark_std::{end_timer, start_timer};
  9use transcript::IOPTranscript;
 10
 11/// A zero check IOP subclaim for `f(x)` consists of the following:
 12///   - the initial challenge vector r which is used to build eq(x, r) in
 13///     SumCheck
 14///   - the random vector `v` to be evaluated
 15///   - the claimed evaluation of `f(v)`
 16#[derive(Clone, Debug, Default, PartialEq, Eq)]
 17pub struct ZeroCheckSubClaim<F: PrimeField> {
 18    // the evaluation point
 19    pub point: Vec<F>,
 20    /// the expected evaluation
 21    pub expected_evaluation: F,
 22    // the initial challenge r which is used to build eq(x, r)
 23    pub init_challenge: Vec<F>,
 24}
 25
 26/// A ZeroCheck for `f(x)` proves that `f(x) = 0` for all `x \in {0,1}^num_vars`
 27/// It is derived from SumCheck.
 28pub trait ZeroCheck<F: PrimeField>: SumCheck<F> {
 29    type ZeroCheckSubClaim: Clone + Debug + Default + PartialEq;
 30    type ZeroCheckProof: Clone + Debug + Default + PartialEq;
 31
 32    /// Initialize the system with a transcript
 33    ///
 34    /// This function is optional -- in the case where a ZeroCheck is
 35    /// an building block for a more complex protocol, the transcript
 36    /// may be initialized by this complex protocol, and passed to the
 37    /// ZeroCheck prover/verifier.
 38    fn init_transcript() -> Self::Transcript;
 39
 40    /// initialize the prover to argue for the sum of polynomial over
 41    /// {0,1}^`num_vars` is zero.
 42    fn prove(
 43        poly: &Self::VirtualPolynomial,
 44        transcript: &mut Self::Transcript,
 45    ) -> Result<Self::ZeroCheckProof, PolyIOPErrors>;
 46
 47    /// verify the claimed sum using the proof
 48    fn verify(
 49        proof: &Self::ZeroCheckProof,
 50        aux_info: &Self::VPAuxInfo,
 51        transcript: &mut Self::Transcript,
 52    ) -> Result<Self::ZeroCheckSubClaim, PolyIOPErrors>;
 53}
 54
 55impl<F: PrimeField> ZeroCheck<F> for PolyIOP<F> {
 56    type ZeroCheckSubClaim = ZeroCheckSubClaim<F>;
 57    type ZeroCheckProof = Self::SumCheckProof;
 58
 59    fn init_transcript() -> Self::Transcript {
 60        IOPTranscript::<F>::new(b"Initializing ZeroCheck transcript")
 61    }
 62
 63    fn prove(
 64        poly: &Self::VirtualPolynomial,
 65        transcript: &mut Self::Transcript,
 66    ) -> Result<Self::ZeroCheckProof, PolyIOPErrors> {
 67        let start = start_timer!(|| "zero check prove");
 68
 69        let length = poly.aux_info.num_variables;
 70        let r = transcript.get_and_append_challenge_vectors(b"0check r", length)?;
 71        let f_hat = poly.build_f_hat(r.as_ref())?;
 72        let res = <Self as SumCheck<F>>::prove(&f_hat, transcript);
 73
 74        end_timer!(start);
 75        res
 76    }
 77
 78    fn verify(
 79        proof: &Self::ZeroCheckProof,
 80        fx_aux_info: &Self::VPAuxInfo,
 81        transcript: &mut Self::Transcript,
 82    ) -> Result<Self::ZeroCheckSubClaim, PolyIOPErrors> {
 83        let start = start_timer!(|| "zero check verify");
 84
 85        // check that the sum is zero
 86        if proof.proofs[0].evaluations[0] + proof.proofs[0].evaluations[1] != F::zero() {
 87            return Err(PolyIOPErrors::InvalidProof(format!(
 88                "zero check: sum {} is not zero",
 89                proof.proofs[0].evaluations[0] + proof.proofs[0].evaluations[1]
 90            )));
 91        }
 92
 93        // generate `r` and pass it to the caller for correctness check
 94        let length = fx_aux_info.num_variables;
 95        let r = transcript.get_and_append_challenge_vectors(b"0check r", length)?;
 96
 97        // hat_fx's max degree is increased by eq(x, r).degree() which is 1
 98        let mut hat_fx_aux_info = fx_aux_info.clone();
 99        hat_fx_aux_info.max_degree += 1;
100        let sum_subclaim =
101            <Self as SumCheck<F>>::verify(F::zero(), proof, &hat_fx_aux_info, transcript)?;
102
103        // expected_eval = sumcheck.expect_eval/eq(v, r)
104        // where v = sum_check_sub_claim.point
105        let eq_x_r_eval = eq_eval(&sum_subclaim.point, &r)?;
106        let expected_evaluation = sum_subclaim.expected_evaluation / eq_x_r_eval;
107
108        end_timer!(start);
109        Ok(ZeroCheckSubClaim {
110            point: sum_subclaim.point,
111            expected_evaluation,
112            init_challenge: r,
113        })
114    }
115}
116
117#[cfg(test)]
118mod test {
119
120    use super::ZeroCheck;
121    use crate::poly_iop::{errors::PolyIOPErrors, PolyIOP};
122    use arithmetic::VirtualPolynomial;
123    use ark_bls12_381::Fr;
124    use ark_std::test_rng;
125
126    fn test_zerocheck(
127        nv: usize,
128        num_multiplicands_range: (usize, usize),
129        num_products: usize,
130    ) -> Result<(), PolyIOPErrors> {
131        let mut rng = test_rng();
132
133        {
134            // good path: zero virtual poly
135            let poly =
136                VirtualPolynomial::rand_zero(nv, num_multiplicands_range, num_products, &mut rng)?;
137
138            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
139            transcript.append_message(b"testing", b"initializing transcript for testing")?;
140            let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
141
142            let poly_info = poly.aux_info.clone();
143            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
144            transcript.append_message(b"testing", b"initializing transcript for testing")?;
145            let zero_subclaim =
146                <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)?;
147            assert!(
148                poly.evaluate(&zero_subclaim.point)? == zero_subclaim.expected_evaluation,
149                "wrong subclaim"
150            );
151        }
152
153        {
154            // bad path: random virtual poly whose sum is not zero
155            let (poly, _sum) =
156                VirtualPolynomial::<Fr>::rand(nv, num_multiplicands_range, num_products, &mut rng)?;
157
158            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
159            transcript.append_message(b"testing", b"initializing transcript for testing")?;
160            let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
161
162            let poly_info = poly.aux_info.clone();
163            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
164            transcript.append_message(b"testing", b"initializing transcript for testing")?;
165
166            assert!(
167                <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)
168                    .is_err()
169            );
170        }
171
172        Ok(())
173    }
174
175    #[test]
176    fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
177        let nv = 1;
178        let num_multiplicands_range = (4, 5);
179        let num_products = 1;
180
181        test_zerocheck(nv, num_multiplicands_range, num_products)
182    }
183    #[test]
184    fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
185        let nv = 5;
186        let num_multiplicands_range = (4, 9);
187        let num_products = 5;
188
189        test_zerocheck(nv, num_multiplicands_range, num_products)
190    }
191
192    #[test]
193    fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
194        let nv = 0;
195        let num_multiplicands_range = (4, 13);
196        let num_products = 5;
197
198        assert!(test_zerocheck(nv, num_multiplicands_range, num_products).is_err());
199        Ok(())
200    }
201}