nova-snark 0.71.0

High-speed recursive arguments from folding schemes
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

//! Circuit representation of a univariate polynomial
use crate::{
  frontend::{num::AllocatedNum, ConstraintSystem, SynthesisError},
  spartan::polys::univariate::UniPoly,
  traits::{Engine, ROCircuitTrait},
};
use ff::Field;

/// An in-circuit representation of `UniPoly` type
pub struct AllocatedUniPoly<E: Engine> {
  coeffs: Vec<AllocatedNum<E::Scalar>>,
}

impl<E: Engine> AllocatedUniPoly<E> {
  /// Allocates the given `UniPoly` as a witness of the circuit
  pub fn alloc<CS: ConstraintSystem<<E as Engine>::Scalar>>(
    mut cs: CS,
    degree: usize,
    poly: Option<&UniPoly<E::Scalar>>,
  ) -> Result<Self, SynthesisError> {
    // we allocate degree + 1 coefficients as BigNat
    let coeffs = (0..degree + 1)
      .map(|i| {
        AllocatedNum::alloc(cs.namespace(|| format!("allocate coeff[{}]", i)), || {
          Ok(poly.map_or(E::Scalar::ZERO, |poly| poly.coeffs[i]))
        })
      })
      .collect::<Result<Vec<_>, _>>()?;

    Ok(Self { coeffs })
  }

  /// checks if poly(0) + poly(1) = c
  pub fn check_poly_zero_poly_one_with<CS: ConstraintSystem<E::Scalar>>(
    &self,
    mut cs: CS,
    c: &AllocatedNum<E::Scalar>,
  ) -> Result<(), SynthesisError> {
    // eval_at_0 = constant term and eval_at_1 = sum of all coefficients
    // eval_at_0 + eval_at_1 = constant_term + sum of all coefficients including the constant term
    cs.enforce(
      || "eval at 0 + eval at 1 = c",
      |lc| lc + c.get_variable(),
      |lc| lc + CS::one(),
      |lc| {
        self
          .coeffs
          .iter()
          .fold(lc + self.coeffs[0].get_variable(), |lc, v| {
            lc + v.get_variable()
          })
      },
    );

    Ok(())
  }

  /// Evaluate the polynomial at the provided point
  pub fn evaluate<CS: ConstraintSystem<<E as Engine>::Scalar>>(
    &self,
    mut cs: CS,
    r: &AllocatedNum<E::Scalar>,
  ) -> Result<AllocatedNum<E::Scalar>, SynthesisError> {
    let mut acc = self.coeffs[0].clone();
    let mut power = r.clone();
    for (i, coeff) in self.coeffs.iter().skip(1).enumerate() {
      // acc_new = acc_old + power * coeff
      // allocate acc_new
      let acc_new = AllocatedNum::alloc(cs.namespace(|| format!("{i} allocate acc_new")), || {
        let acc_old = acc.get_value().ok_or(SynthesisError::AssignmentMissing)?;
        let power = power.get_value().ok_or(SynthesisError::AssignmentMissing)?;
        let coeff = coeff.get_value().ok_or(SynthesisError::AssignmentMissing)?;
        Ok(acc_old + power * coeff)
      })?;

      // check that acc_new - acc_old = power * coeff
      cs.enforce(
        || format!("{i} enforce acc_new - acc_old = power * coeff"),
        |lc| lc + power.get_variable(),
        |lc| lc + coeff.get_variable(),
        |lc| lc + acc_new.get_variable() - acc.get_variable(),
      );

      // power_new = power_old * r
      let power_new =
        AllocatedNum::alloc(cs.namespace(|| format!("{i} allocate power_new")), || {
          let power_old = power.get_value().ok_or(SynthesisError::AssignmentMissing)?;
          let r = r.get_value().ok_or(SynthesisError::AssignmentMissing)?;
          Ok(power_old * r)
        })?;
      cs.enforce(
        || format!("{i} enforce power_new = power_old * r"),
        |lc| lc + power.get_variable(),
        |lc| lc + r.get_variable(),
        |lc| lc + power_new.get_variable(),
      );

      power = power_new;
      acc = acc_new;
    }
    Ok(acc)
  }

  /// Absorb the provided instance in the RO
  pub fn absorb_in_ro(&self, ro: &mut E::RO2Circuit) {
    for coeff in self.coeffs.iter() {
      ro.absorb(coeff);
    }
  }
}