1//! Main module for the ZeroCheck protocol.
  2
  3use crate::{
  4    errors::PolyIOPErrors,
  5    structs::{IOPProof, SubClaim},
  6    sum_check::SumCheck,
  7    transcript::IOPTranscript,
  8    virtual_poly::{VPAuxInfo, VirtualPolynomial},
  9    PolyIOP,
 10};
 11use ark_ff::PrimeField;
 12use ark_std::{end_timer, start_timer};
 13
 14pub trait ZeroCheck<F: PrimeField> {
 15    type Proof;
 16    type VirtualPolynomial;
 17    type VPAuxInfo;
 18    type SubClaim;
 19    type Transcript;
 20
 21    /// Initialize the system with a transcript
 22    ///
 23    /// This function is optional -- in the case where a ZeroCheck is
 24    /// an building block for a more complex protocol, the transcript
 25    /// may be initialized by this complex protocol, and passed to the
 26    /// ZeroCheck prover/verifier.
 27    fn init_transcript() -> Self::Transcript;
 28
 29    /// initialize the prover to argue for the sum of polynomial over
 30    /// {0,1}^`num_vars` is zero.
 31    fn prove(
 32        poly: &Self::VirtualPolynomial,
 33        transcript: &mut Self::Transcript,
 34    ) -> Result<Self::Proof, PolyIOPErrors>;
 35
 36    /// verify the claimed sum using the proof
 37    fn verify(
 38        proof: &Self::Proof,
 39        aux_info: &Self::VPAuxInfo,
 40        transcript: &mut Self::Transcript,
 41    ) -> Result<Self::SubClaim, PolyIOPErrors>;
 42}
 43
 44impl<F: PrimeField> ZeroCheck<F> for PolyIOP<F> {
 45    type Proof = IOPProof<F>;
 46    type VirtualPolynomial = VirtualPolynomial<F>;
 47    type VPAuxInfo = VPAuxInfo<F>;
 48
 49    /// A ZeroCheck SubClaim consists of
 50    /// - the SubClaim from the ZeroCheck
 51    /// - the initial challenge r which is used to build eq(x, r)
 52    type SubClaim = (SubClaim<F>, Vec<F>);
 53    type Transcript = IOPTranscript<F>;
 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::Proof, 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"vector 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::Proof,
 99        fx_aux_info: &Self::VPAuxInfo,
100        transcript: &mut Self::Transcript,
101    ) -> Result<Self::SubClaim, 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"vector 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((subclaim, r))
124    }
125}
126
127#[cfg(test)]
128mod test {
129
130    use super::ZeroCheck;
131    use crate::{errors::PolyIOPErrors, PolyIOP, VirtualPolynomial};
132    use ark_bls12_381::Fr;
133    use ark_std::test_rng;
134
135    fn test_zerocheck(
136        nv: usize,
137        num_multiplicands_range: (usize, usize),
138        num_products: usize,
139    ) -> Result<(), PolyIOPErrors> {
140        let mut rng = test_rng();
141
142        {
143            // good path: zero virtual poly
144            let poly =
145                VirtualPolynomial::rand_zero(nv, num_multiplicands_range, num_products, &mut rng)?;
146
147            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
148            transcript.append_message(b"testing", b"initializing transcript for testing")?;
149            let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
150
151            let poly_info = poly.aux_info.clone();
152            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
153            transcript.append_message(b"testing", b"initializing transcript for testing")?;
154            let subclaim =
155                <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)?.0;
156            assert!(
157                poly.evaluate(&subclaim.point)? == subclaim.expected_evaluation,
158                "wrong subclaim"
159            );
160        }
161
162        {
163            // bad path: random virtual poly whose sum is not zero
164            let (poly, _sum) =
165                VirtualPolynomial::rand(nv, num_multiplicands_range, num_products, &mut rng)?;
166
167            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
168            transcript.append_message(b"testing", b"initializing transcript for testing")?;
169            let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
170
171            let poly_info = poly.aux_info.clone();
172            let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
173            transcript.append_message(b"testing", b"initializing transcript for testing")?;
174
175            assert!(
176                <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)
177                    .is_err()
178            );
179        }
180
181        Ok(())
182    }
183
184    #[test]
185    fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
186        let nv = 1;
187        let num_multiplicands_range = (4, 5);
188        let num_products = 1;
189
190        test_zerocheck(nv, num_multiplicands_range, num_products)
191    }
192    #[test]
193    fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
194        let nv = 5;
195        let num_multiplicands_range = (4, 9);
196        let num_products = 5;
197
198        test_zerocheck(nv, num_multiplicands_range, num_products)
199    }
200
201    #[test]
202    fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
203        let nv = 0;
204        let num_multiplicands_range = (4, 13);
205        let num_products = 5;
206
207        assert!(test_zerocheck(nv, num_multiplicands_range, num_products).is_err());
208        Ok(())
209    }
210}