ark_relations/gr1cs/predicate/
polynomial_constraint.rs

1//! This module contains the implementation of the Polynomial Predicate struct.
2//! A polynomial predicate is a kind of predicate which is defined in <https://eprint.iacr.org/2024/1245>.
3//! Other kinds of  predicates can be added in the future such as lookup
4//! table predicates.
5
6use ark_ff::Field;
7use ark_poly::{
8    multivariate::{SparsePolynomial, SparseTerm, Term},
9    DenseMVPolynomial, Polynomial,
10};
11use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
12use ark_std::vec::Vec;
13
14/// A polynomial predicat is just a polynomial
15#[derive(Debug, Clone, CanonicalSerialize, CanonicalDeserialize)]
16pub struct PolynomialPredicate<F: Field> {
17    /// The sparse polynomial for the predicate
18    pub polynomial: SparsePolynomial<F, SparseTerm>,
19}
20
21impl<F: Field> PolynomialPredicate<F> {
22    /// Create a new polynomial predicate with a given number of variables (= arity) and
23    /// number of terms.
24    ///
25    /// Here `terms` is a list of tuples of the form `(variable`, `power`) where
26    /// `variable` is the index of the variable and `power` is the exponent of the variable.
27    ///
28    /// So, for example, if `terms` is `[F::ONE, [(0, 1), (1, 2)]]`, then the polynomial is
29    /// `x_0 + x_1^2`.
30    pub fn new(arity: usize, terms: impl IntoIterator<Item = (F, Vec<(usize, usize)>)>) -> Self {
31        let sparse_terms = terms
32            .into_iter()
33            .map(|(coeff, term)| (coeff, SparseTerm::new(term.clone())))
34            .collect();
35        Self {
36            polynomial: SparsePolynomial::from_coefficients_vec(arity, sparse_terms),
37        }
38    }
39}
40
41/// This is the implementation of the Predicate trait for PolynomialPredicate.
42/// The evaluation of a polynomial predicate is the evaluation of the underlying
43/// polynomial and the arity is the number of variables in the polynomial.
44impl<F: Field> PolynomialPredicate<F> {
45    /// Check if the predicate is satisfied by the given variables.
46    pub fn is_satisfied(&self, variables: &[F]) -> bool {
47        self.polynomial.evaluate(&variables.to_vec()).is_zero()
48    }
49
50    /// Evaluate the predicate on the given variables.
51    pub fn eval(&self, variables: &[F]) -> F {
52        self.polynomial.evaluate(&variables.to_vec())
53    }
54
55    /// Get the arity of the polynomial predicate.
56    /// For example, the arity of P(x1, x2, ..., xn) is n.
57    pub fn arity(&self) -> usize {
58        self.polynomial.num_vars()
59    }
60
61    /// Get the degree of the polynomial predicate.
62    /// For example, the degree of x1 + x2^4 + x3^2 is 4.
63    pub fn degree(&self) -> usize {
64        self.polynomial.degree()
65    }
66}
67
68/// A label for the R1CS predicate.
69pub const R1CS_PREDICATE_LABEL: &str = "R1CS";
70
71/// A label for the Square R1CS predicate introduced in
72/// [\[Groth-Maller17\]](https://eprint.iacr.org/2017/540).
73pub const SR1CS_PREDICATE_LABEL: &str = "SR1CS";
ark_relations/gr1cs/predicate/polynomial_constraint.rs

ark_relations/gr1cs/predicate/
polynomial_constraint.rs
