ark_bulletproofs/r1cs/
linear_combination.rs

1//! Definition of linear combinations.
2
3use ark_ff::PrimeField;
4use ark_std::{
5    iter::FromIterator,
6    ops::{Add, Mul, Neg, Sub},
7    vec,
8    vec::Vec,
9};
10use core::marker::PhantomData;
11
12/// Represents a variable in a constraint system.
13#[derive(Copy, Clone, Debug, PartialEq)]
14pub enum Variable<F: PrimeField> {
15    /// Represents an external input specified by a commitment.
16    Committed(usize),
17    /// Represents the left input of a multiplication gate.
18    MultiplierLeft(usize),
19    /// Represents the right input of a multiplication gate.
20    MultiplierRight(usize),
21    /// Represents the output of a multiplication gate.
22    MultiplierOutput(usize),
23    /// Represents the constant 1.
24    One(),
25    /// Phantom.
26    Phantom(PhantomData<F>),
27}
28
29impl<F: PrimeField> From<Variable<F>> for LinearCombination<F> {
30    fn from(v: Variable<F>) -> LinearCombination<F> {
31        LinearCombination {
32            terms: vec![(v, F::one())],
33        }
34    }
35}
36
37impl<F: PrimeField> From<F> for LinearCombination<F> {
38    fn from(s: F) -> LinearCombination<F> {
39        LinearCombination {
40            terms: vec![(Variable::One(), s)],
41        }
42    }
43}
44
45// Arithmetic on variables produces linear combinations
46
47impl<F: PrimeField> Neg for Variable<F> {
48    type Output = LinearCombination<F>;
49
50    fn neg(self) -> Self::Output {
51        -LinearCombination::from(self)
52    }
53}
54
55impl<F: PrimeField, L: Into<LinearCombination<F>>> Add<L> for Variable<F> {
56    type Output = LinearCombination<F>;
57
58    fn add(self, other: L) -> Self::Output {
59        LinearCombination::from(self) + other.into()
60    }
61}
62
63impl<F: PrimeField, L: Into<LinearCombination<F>>> Sub<L> for Variable<F> {
64    type Output = LinearCombination<F>;
65
66    fn sub(self, other: L) -> Self::Output {
67        LinearCombination::from(self) - other.into()
68    }
69}
70
71impl<F: PrimeField, S: Into<F>> Mul<S> for Variable<F> {
72    type Output = LinearCombination<F>;
73
74    fn mul(self, other: S) -> Self::Output {
75        LinearCombination {
76            terms: vec![(self, other.into())],
77        }
78    }
79}
80
81/// Represents a linear combination of
82/// [`Variables`](::r1cs::Variable).  Each term is represented by a
83/// `(Variable, Fr)` pair.
84#[derive(Clone, Debug, PartialEq)]
85pub struct LinearCombination<F: PrimeField> {
86    pub(super) terms: Vec<(Variable<F>, F)>,
87}
88
89impl<F: PrimeField> Default for LinearCombination<F> {
90    fn default() -> Self {
91        LinearCombination { terms: Vec::new() }
92    }
93}
94
95impl<F: PrimeField> FromIterator<(Variable<F>, F)> for LinearCombination<F> {
96    fn from_iter<T>(iter: T) -> Self
97    where
98        T: IntoIterator<Item = (Variable<F>, F)>,
99    {
100        LinearCombination {
101            terms: iter.into_iter().collect(),
102        }
103    }
104}
105
106impl<'a, F: PrimeField> FromIterator<&'a (Variable<F>, F)> for LinearCombination<F> {
107    fn from_iter<T>(iter: T) -> Self
108    where
109        T: IntoIterator<Item = &'a (Variable<F>, F)>,
110    {
111        LinearCombination {
112            terms: iter.into_iter().cloned().collect(),
113        }
114    }
115}
116
117// Arithmetic on linear combinations
118
119impl<F: PrimeField, L: Into<LinearCombination<F>>> Add<L> for LinearCombination<F> {
120    type Output = Self;
121
122    fn add(mut self, rhs: L) -> Self::Output {
123        self.terms.extend(rhs.into().terms.iter().cloned());
124        LinearCombination { terms: self.terms }
125    }
126}
127
128impl<F: PrimeField, L: Into<LinearCombination<F>>> Sub<L> for LinearCombination<F> {
129    type Output = Self;
130
131    fn sub(mut self, rhs: L) -> Self::Output {
132        self.terms.extend(
133            rhs.into()
134                .terms
135                .iter()
136                .map(|(var, coeff)| (*var, coeff.neg())),
137        );
138        LinearCombination { terms: self.terms }
139    }
140}
141
142impl<F: PrimeField> Neg for LinearCombination<F> {
143    type Output = Self;
144
145    fn neg(mut self) -> Self::Output {
146        for (_, s) in self.terms.iter_mut() {
147            *s = -*s
148        }
149        self
150    }
151}
152
153impl<F: PrimeField, S: Into<F>> Mul<S> for LinearCombination<F> {
154    type Output = Self;
155
156    fn mul(mut self, other: S) -> Self::Output {
157        let other = other.into();
158        for (_, s) in self.terms.iter_mut() {
159            *s *= other
160        }
161        self
162    }
163}
ark_bulletproofs/r1cs/linear_combination.rs

ark_bulletproofs/r1cs/
linear_combination.rs
