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

use super::*;
use crate::*;

/// Argues knowledge of two BDLOP commitments such that
/// c_a = g * c_b
pub struct BDLOPLinearNIZKArg<const N: usize, E: FieldScalar> {
    pub g: Polynomial<N, E>,
    pub c_a: BDLOP<N, E>,
    pub c_b: BDLOP<N, E>,
    pub t_1: Vector<Polynomial<N, E>>,
    pub t_2: Vector<Polynomial<N, E>>,
    pub u: Vector<Polynomial<N, E>>,
    pub z_1: Vector<Polynomial<N, E>>,
    pub z_2: Vector<Polynomial<N, E>>,
}

impl<const N: usize, E: FieldScalar> BDLOPLinearNIZKArg<N, E> {
    /// Generate a NIZK argument of linear relation between two commitments.
    /// Argues `c_a = g * c_b`.
    pub fn new<R: Rng>(
        (c_a, r_a): (BDLOP<N, E>, &Vector<Polynomial<N, E>>),
        (c_b, r_b): (BDLOP<N, E>, &Vector<Polynomial<N, E>>),
        g: Polynomial<N, E>,
        rng: &mut R,
    ) -> Result<Self> {
        assert!(c_a.a_1 == c_b.a_1);
        assert!(c_a.a_2 == c_b.a_2);
        let a_1 = &c_a.a_1;
        let a_2 = &c_a.a_2;
        loop {
            let y_1 = (0..a_1.width())
                .map(|_| Polynomial::sample_gaussian(SIGMA, rng).into_eval_form())
                .collect::<Vector<_>>();
            let y_2 = (0..a_1.width())
                .map(|_| Polynomial::sample_gaussian(SIGMA, rng).into_eval_form())
                .collect::<Vector<_>>();

            let t_1 = a_1.as_ref() * &y_1;
            let t_2 = a_1.as_ref() * &y_2;

            let u = g.batch_mul(a_2.as_ref() * &y_1) - a_2.as_ref() * &y_2;

            let hash = blake3::hash(
                &t_1.iter()
                    .chain(t_2.iter())
                    .chain(u.iter())
                    .flat_map(|p| p.as_le_bytes())
                    .collect::<Vec<_>>(),
            );
            let mut csprng = rand_chacha::ChaCha20Rng::from_seed(hash.into());

            let d: Polynomial<N, E> = std::array::from_fn(|_| ternary_sample(&mut csprng)).into();

            let z_1 = y_1 + &(d.batch_mul(r_a.clone()));
            let z_2 = y_2 + &(d.batch_mul(r_b.clone()));
            // TODO: rejection sampling
            // if p.norm_l2() >= 2.0 * sigma * (self.a_1.width() as f64).sqrt() {
            //     // reject and try again
            //     continue;
            // }
            return Ok(Self {
                c_a,
                c_b,
                t_1,
                t_2,
                u,
                g,
                z_1,
                z_2,
            });
        }
    }

    /// Verify the lattice relations
    pub fn verify(&self, g: Polynomial<N, E>) -> Result<()> {
        if g != self.g {
            anyhow::bail!("BDLOPLinearNIZKArg g value mismatch");
        }
        // check z terms norm bounds
        let l2_norm_bound = 4.0 * SIGMA * (N as f64).sqrt();
        for (z_1, z_2) in self.z_1.iter().zip(self.z_2.iter()) {
            if z_1.norm_l2() >= l2_norm_bound {
                anyhow::bail!("BDLOPLinearNIZKArg z_1 is beyond bounds");
            }
            if z_2.norm_l2() >= l2_norm_bound {
                anyhow::bail!("BDLOPLinearNIZKArg z_2 is beyond bounds");
            }
        }
        // compute the d value
        let hash = blake3::hash(
            &self
                .t_1
                .iter()
                .chain(self.t_2.iter())
                .chain(self.u.iter())
                .flat_map(|p| p.as_le_bytes())
                .collect::<Vec<_>>(),
        );
        let mut csprng = rand_chacha::ChaCha20Rng::from_seed(hash.into());

        let d: Polynomial<N, E> = std::array::from_fn(|_| ternary_sample(&mut csprng)).into();

        // check equalities
        if self.c_a.a_1.as_ref() * &self.z_1 != self.t_1.clone() + &(self.c_a.c_1.clone() * d) {
            anyhow::bail!("BDLOPLinearNIZKArg z_1 equality mismatch");
        }
        if self.c_a.a_1.as_ref() * &self.z_2 != self.t_2.clone() + &(self.c_b.c_1.clone() * d) {
            anyhow::bail!("BDLOPLinearNIZKArg z_2 equality mismatch");
        }

        let lhs = self.c_a.a_2.as_ref() * &self.z_1 * self.g - self.c_a.a_2.as_ref() * &self.z_2;
        let rhs = (self.c_a.c_2.clone() * self.g - &self.c_b.c_2) * d + &self.u;
        if lhs != rhs {
            anyhow::bail!("BDLOPLinearNIZKArg final equality mismatch");
        }

        Ok(())
    }
}

#[test]
fn bdlop_open_linear_zk() -> Result<()> {
    type Field = MilliScalarMont;
    const RING_DEGREE: usize = 512;
    let rng = &mut rand::rng();
    let msg_len = 1;
    let lattice = BDLOP::<RING_DEGREE, Field>::lattice_for(msg_len, rng);
    // sample a constant term
    let g = Polynomial::<RING_DEGREE, Field>::sample_uniform(rng);
    // sample our committed terms
    let a = Vector::sample_uniform(msg_len, rng);
    let b = a.clone() * g;

    // commit to terms
    let (c_a, r_a) = BDLOP::commit(a, &lattice, rng);
    let (c_b, r_b) = BDLOP::commit(b, &lattice, rng);

    // try to argue zk relation
    let arg = BDLOPLinearNIZKArg::new((c_a, &r_a), (c_b, &r_b), g, rng)?;
    arg.verify(g)?;

    Ok(())
}