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