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
use crate::*;
/// Rank 1 constraint system over a scalar field.
pub struct R1CS<E: FieldScalar> {
pub a: Matrix<E>,
pub b: Matrix<E>,
pub c: Matrix<E>,
}
impl<E: FieldScalar> R1CS<E> {
/// Sample a random R1CS instance and a witness that fulfills the instance.
///
/// This instance will be non-trivial and non-sparse. That is, finding a second
/// witness vector should be difficult (though not impossible). This function is
/// designed to create test R1CS instances.
pub fn sample_uniform<R: Rng>(height: usize, width: usize, rng: &mut R) -> (Self, Vector<E>) {
let wtns = Vector::<E>::sample_uniform(width, rng);
let a = Matrix::random(height, width, rng);
let b = Matrix::random(height, width, rng);
let aw = &a * &wtns;
let bw = &b * &wtns;
let abw = aw.clone() * &bw;
// now we need a c matrix that yields this abw value
// we're looking for abw[i] = <c[i], w>
let c = b
.iter()
.enumerate()
.map(|(i, row)| row.clone() * aw[i])
.collect::<Matrix<_>>();
debug_assert!(abw == &c * &wtns);
(Self { a, b, c }, wtns)
}
/// Generate an R1CS instance that is fulfilled by all witness vectors.
pub fn identity(height: usize, width: usize) -> Self {
let v = Matrix::zero(height, width);
Self {
a: v.clone(),
b: v.clone(),
c: v.clone(),
}
}
/// Evaluate the R1CS instance for an input witness. Returns the evaluation of
/// AwBw - Cw, which may be a non-zero vector.
///
/// For R1CS instances the output should be checked against the 0 value. For relaxed R1CS
/// instances the output should be checked against the e vector.
pub fn eval(&self, witness: &Vector<E>) -> Result<Vector<E>> {
self.assert_consistency()?;
let ab = (self.a.clone() * witness) * &(self.b.clone() * witness);
let c = self.c.clone() * witness;
Ok(ab - c)
}
/// Number of constraints in the system.
pub fn height(&self) -> usize {
self.a.height()
}
/// Number of elements in the witness vector.
pub fn width(&self) -> usize {
self.a.width()
}
/// Dimension of the constraint matrices.
pub fn dimension(&self) -> (usize, usize) {
self.a.dimension()
}
/// Assert consistency of matrix dimensions.
fn assert_consistency(&self) -> Result<()> {
let dimension = self.a.dimension();
if self.b.dimension() != dimension {
anyhow::bail!(
"R1CS A and B dimension mismatch, expected {:?}, got {:?}",
dimension,
self.b.dimension()
);
}
if self.c.dimension() != dimension {
anyhow::bail!(
"R1CS A and C dimension mismatch, expected {:?}, got {:?}",
dimension,
self.c.dimension()
);
}
Ok(())
}
}
#[test]
fn random_r1cs() {
type Field = MilliScalarMont;
let rng = &mut rand::rng();
let (r1cs, wtns) = R1CS::<Field>::sample_uniform(10, 20, rng);
for v in r1cs.eval(&wtns).iter() {
assert!(v.is_zero());
}
}