lettuce 0.1.3

Healthy lattice consructions in pure Rust.
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236

use anyhow::Result;

use crate::*;

/// This is a transparent, binding only, argument of vector by matrix multiplication, collapsed to
/// an inner sum. This structure optimizes by rolling all row multiplications into a single
/// logarithmic commitmnet.
pub struct TransparentMatInnerProd<const C: usize, E: FieldScalar> {
    /// Committed intermediate cross products
    pub comms: (Vector<E>, Vector<E>),
    /// Amplify security of the inner product argument with multiple challenges at each step
    /// used for verification of self
    pub inner_prod_args: [E; C],
    /// Used to check equality of inner products with other Self
    pub claim_rlc: [E; C],
    /// The matrix vector product before summation
    pub hadamard_checksum: [u8; 32],
    /// checksum of the vector term
    pub vec_checksum: [u8; 32],
    /// checksum of the matrix term
    pub mat_checksum: [u8; 32],
}

impl<const C: usize, E: FieldScalar> TransparentMatInnerProd<C, E> {
    pub fn new(mat: &Matrix<E>, vec: Vector<E>) -> Result<Self> {
        panic!();
        assert_eq!(
            mat.width(),
            vec.len(),
            "TransparentMatInnerProd matrix/vector dimension mismatch"
        );

        // TODO: commit to 0 appended vec and mat
        let mut vec_transcript = Transcript::new();
        vec_transcript.append_vector(&vec);
        let vec_checksum = vec_transcript.random::<[u8; 32]>();

        let mut mat_transcript = Transcript::new();
        mat_transcript.append_matrix(mat);
        let mat_checksum = mat_transcript.random::<[u8; 32]>();

        let zeroes = if 2usize.pow(vec.len().ilog2()) == vec.len() {
            vec![]
        } else {
            vec![E::zero(); 2usize.pow(vec.len().ilog2() + 1) - vec.len()]
        };
        let row_len = vec.len() + zeroes.len();
        let total_elements = (vec.len() + zeroes.len()) * mat.height();
        let zero = E::zero();

        let mat_index = |offset| {
            let row_i = offset / row_len;
            let col_i = offset % row_len;
            if col_i >= mat.width() {
                return &zero;
            }
            &mat[row_i][col_i]
        };

        let vec_index = |offset| {
            let i = offset % row_len;
            if i >= vec.len() {
                return &zero;
            }
            &vec[i]
        };

        let mat_inner_i = |i, depth: usize| {
            if depth == 0 {
                return *mat_index(i);
            }
            let total_sum_len = 2usize.pow(depth as u32);
            let skip = total_elements / (2usize.pow(depth as u32));
            let mut sum = E::zero();
            for j in 0..total_sum_len {
                sum += *mat_index(i + j * skip);
            }
            sum
        };

        let vec_inner_i = |i, depth: usize| {
            if depth == 0 {
                return *vec_index(i);
            }
            let total_sum_len = 2usize.pow(depth as u32);
            let skip = total_elements / (2usize.pow(depth as u32));
            let mut sum = E::zero();
            for j in 0..total_sum_len {
                sum += *vec_index(i + j * skip);
            }
            sum
        };

        let mut hadamard_transcript = Transcript::new();
        for i in 0..mat.height() {
            let mut sum = E::zero();
            for j in 0..row_len {
                sum += *mat_index(i * row_len + j) * *vec_index(i * row_len + j);
            }
            hadamard_transcript.append(&sum);
        }
        let hadamard_checksum = hadamard_transcript.random::<[u8; 32]>();

        let mut claim_transcript = Transcript::<E>::new();
        claim_transcript.append_bytes(&mat_checksum);
        claim_transcript.append_bytes(&vec_checksum);
        claim_transcript.append_bytes(&hadamard_checksum);
        let mut claim_rlc = [E::zero(); C];
        for i in 0..C {
            let mut challenge = E::sample_uniform(&mut claim_transcript);
            for j in 0..total_elements {
                claim_rlc[i] += *mat_index(j) * *vec_index(j) * challenge;
                challenge *= challenge;
            }
        }
        let claim_rlc = claim_rlc;
        let mut inner_prod_args = claim_rlc.clone();

        // we'll treat this as if the vector being multiplied were expanded by repetition, and the
        // matrix was converted to a vector by concatenating each row
        //
        let mut inner_product_transcript = Transcript::new();
        inner_product_transcript.domain_separator("vec");
        inner_product_transcript.append_bytes(&vec_checksum);
        inner_product_transcript.domain_separator("mat");
        inner_product_transcript.append_bytes(&mat_checksum);
        inner_product_transcript.domain_separator("hadamard");
        inner_product_transcript.append_bytes(&hadamard_checksum);
        inner_product_transcript.domain_separator("claim_rlc");
        inner_product_transcript.append_vector(&claim_rlc.to_vec().into());
        inner_product_transcript.domain_separator("args");

        let mut comms = (Vec::new(), Vec::new());

        let mut depth = 0;
        while 2usize.pow(depth as u32 + 1) < total_elements / 2 {
            let len = total_elements / 2usize.pow(depth as u32 + 1);

            let lhs_inner_prod = (0..len)
                .map(|i| mat_inner_i(i, depth))
                .zip((len..2 * len).map(|i| vec_inner_i(i, depth)))
                .map(|(l, r)| l * r)
                .sum::<E>();
            let rhs_inner_prod = (len..2 * len)
                .map(|i| mat_inner_i(i, depth))
                .zip((0..len).map(|i| vec_inner_i(i, depth)))
                .map(|(l, r)| l * r)
                .sum::<E>();

            comms.0.push(lhs_inner_prod);
            comms.1.push(rhs_inner_prod);
            inner_product_transcript.append(&lhs_inner_prod);
            inner_product_transcript.append(&rhs_inner_prod);

            // sample many challenges to amplify soundness
            for i in 0..C {
                let challenge = E::sample_uniform(&mut inner_product_transcript);
                let challenge_inv = challenge.inverse();

                let a = (challenge_inv * challenge_inv) * lhs_inner_prod;
                let b = (challenge * challenge) * rhs_inner_prod;
                inner_prod_args[i] += a + b;
            }
            depth += 1;
        }
        Ok(Self {
            comms: (comms.0.into(), comms.1.into()),
            inner_prod_args,
            claim_rlc,
            mat_checksum,
            vec_checksum,
            hadamard_checksum,
        })
    }

    pub fn verify(&self) -> Result<()> {
        let mut transcript = Transcript::new();
        transcript.domain_separator("vec");
        transcript.append_bytes(&self.vec_checksum);
        transcript.domain_separator("mat");
        transcript.append_bytes(&self.mat_checksum);
        transcript.domain_separator("hadamard");
        transcript.append_bytes(&self.hadamard_checksum);
        transcript.domain_separator("claim_rlc");
        transcript.append_vector(&self.claim_rlc.to_vec().into());
        transcript.domain_separator("args");
        let mut claims = self.claim_rlc.clone();
        for (l, r) in self.comms.0.iter().zip(self.comms.1.iter()) {
            transcript.append(l);
            transcript.append(r);
            for i in 0..C {
                let challenge = E::sample_uniform(&mut transcript);
                let challenge_inv = challenge.inverse();

                let a = (challenge_inv * challenge_inv) * *l;
                let b = (challenge * challenge) * *r;
                claims[i] += a + b;
            }
        }
        for i in 0..C {
            if claims[i] != self.inner_prod_args[i] {
                anyhow::bail!("TransparentInnerProd: inner product mismatch");
            }
        }
        Ok(())
    }
}

#[test]
fn mat_innerprod() -> Result<()> {
    const LEN: usize = 20;
    type Field = MilliScalarMont;
    let rng = &mut rand::rng();
    let mat = Matrix::<Field>::random(LEN * 2, LEN, rng);
    let vec = Vector::<Field>::sample_uniform(LEN, rng);

    let mut vec_transcript = Transcript::new();
    vec_transcript.append_vector(&vec);
    let mut mat_transcript = Transcript::new();
    mat_transcript.append_matrix(&mat);

    let hadamard = &mat * &vec;
    let mut hadamard_transcript = Transcript::new();
    hadamard_transcript.append_vector(&hadamard);

    let arg = TransparentMatInnerProd::<5, _>::new(&mat, vec)?;
    arg.verify()?;

    assert_eq!(vec_transcript.random::<[u8; 32]>(), arg.vec_checksum);
    assert_eq!(mat_transcript.random::<[u8; 32]>(), arg.mat_checksum);
    assert_eq!(
        hadamard_transcript.random::<[u8; 32]>(),
        arg.hadamard_checksum
    );
    Ok(())
}