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