bellman_keccak256/
lib.rs

1use bellman::gadgets::boolean::Boolean;
2use bellman::SynthesisError;
3use bellman::ConstraintSystem;
4
5use ff::ScalarEngine;
6
7mod uint64;
8use uint64::UInt64;
9
10#[allow(clippy::unreadable_literal)]
11const ROUND_CONSTANTS: [u64; 24] = [
12    1u64,
13    0x8082u64,
14    0x800000000000808au64,
15    0x8000000080008000u64,
16    0x808bu64,
17    0x80000001u64,
18    0x8000000080008081u64,
19    0x8000000000008009u64,
20    0x8au64,
21    0x88u64,
22    0x80008009u64,
23    0x8000000au64,
24    0x8000808bu64,
25    0x800000000000008bu64,
26    0x8000000000008089u64,
27    0x8000000000008003u64,
28    0x8000000000008002u64,
29    0x8000000000000080u64,
30    0x800au64,
31    0x800000008000000au64,
32    0x8000000080008081u64,
33    0x8000000000008080u64,
34    0x80000001u64,
35    0x8000000080008008u64,
36];
37const ROTR: [usize; 25] = [
38    0, 1, 62, 28, 27, 36, 44, 6, 55, 20, 3, 10, 43, 25, 39, 41, 45, 15, 21, 8, 18, 2, 61, 56, 14,
39];
40
41fn xor_2<E, CS>(mut cs: CS, a: &UInt64, b: &UInt64) -> Result<UInt64, SynthesisError>
42where
43    E: ScalarEngine,
44    CS: ConstraintSystem<E>,
45{
46    // a ^ b
47    a.xor(cs.namespace(|| "xor_2"), b)
48}
49
50fn xor_5<E, CS>(
51    mut cs: CS,
52    a: &UInt64,
53    b: &UInt64,
54    c: &UInt64,
55    d: &UInt64,
56    e: &UInt64,
57) -> Result<UInt64, SynthesisError>
58where
59    E: ScalarEngine,
60    CS: ConstraintSystem<E>,
61{
62    // a ^ b ^ c ^ d ^ e
63    let ab = a.xor(cs.namespace(|| "xor_5 first"), b)?;
64    let abc = ab.xor(cs.namespace(|| "xor_5 second"), c)?;
65    let abcd = abc.xor(cs.namespace(|| "xor_5 third"), d)?;
66    abcd.xor(cs.namespace(|| "xor_5 fourth"), e)
67}
68
69fn xor_not_and<E, CS>(
70    mut cs: CS,
71    a: &UInt64,
72    b: &UInt64,
73    c: &UInt64,
74) -> Result<UInt64, SynthesisError>
75where
76    E: ScalarEngine,
77    CS: ConstraintSystem<E>,
78{
79    // a ^ ((!b) & c)
80    let nb = b.not();
81    let nbc = nb.and(cs.namespace(|| "xor_not_and second"), c)?;
82    a.xor(cs.namespace(|| "xor_not_and third"), &nbc)
83}
84
85fn round_1600<E, CS>(mut cs: CS, a: Vec<UInt64>, rc: u64) -> Result<Vec<UInt64>, SynthesisError>
86where
87    E: ScalarEngine,
88    CS: ConstraintSystem<E>,
89{
90    assert_eq!(a.len(), 25);
91
92    // # θ step
93    // C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4],   for x in 0…4
94    let mut c = Vec::new();
95    for x in 0..5 {
96        let cs = &mut cs.namespace(|| format!("omega c {}", x));
97
98        c.push(xor_5(
99            cs,
100            &a[x + 0usize],
101            &a[x + 5usize],
102            &a[x + 10usize],
103            &a[x + 15usize],
104            &a[x + 20usize],
105        )?);
106    }
107
108    // panic!("c: {:?}", c);
109
110    // D[x] = C[x-1] xor rot(C[x+1],1),                             for x in 0…4
111    let mut d = Vec::new();
112    for x in 0..5 {
113        let cs = &mut cs.namespace(|| format!("omega d {}", x));
114
115        d.push(xor_2(
116            cs,
117            &c[(x + 4usize) % 5usize],
118            &c[(x + 1usize) % 5usize].rotl(1),
119        )?);
120    }
121
122    // A[x,y] = A[x,y] xor D[x],                           for (x,y) in (0…4,0…4)
123    let mut a_new1 = Vec::new();
124    for y in 0..5 {
125        for x in 0..5 {
126            let cs = &mut cs.namespace(|| format!("omega {},{}", x, y));
127
128            a_new1.push(xor_2(cs, &a[x + (y * 5usize)], &d[x])?);
129        }
130    }
131
132    // # ρ and π steps
133    // B[y,2*x+3*y] = rot(A[x,y], r[x,y]),                 for (x,y) in (0…4,0…4)
134    let mut b = a_new1.clone();
135    for y in 0..5 {
136        for x in 0..5 {
137            b[y + ((((2 * x) + (3 * y)) % 5) * 5usize)] =
138                a_new1[x + (y * 5usize)].rotl(ROTR[x + (y * 5usize)]);
139        }
140    }
141
142    let mut a_new2 = Vec::new();
143
144    // # χ step
145    // A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]),  for (x,y) in (0…4,0…4)
146    for y in 0..5 {
147        for x in 0..5 {
148            let cs = &mut cs.namespace(|| format!("chi {},{}", x, y));
149
150            a_new2.push(xor_not_and(
151                cs,
152                &b[x + (y * 5usize)],
153                &b[((x + 1usize) % 5usize) + (y * 5usize)],
154                &b[((x + 2usize) % 5usize) + (y * 5usize)],
155            )?);
156        }
157    }
158
159    // // # ι step
160    // // A[0,0] = A[0,0] xor RC
161    let rc = UInt64::constant(rc);
162    a_new2[0] = a_new2[0].xor(cs.namespace(|| "xor RC"), &rc)?;
163
164    Ok(a_new2)
165}
166
167fn keccak_f_1600<E, CS>(mut cs: CS, input: Vec<Boolean>) -> Result<Vec<Boolean>, SynthesisError>
168where
169    E: ScalarEngine,
170    CS: ConstraintSystem<E>,
171{
172    assert_eq!(input.len(), 1600);
173
174    let mut a = input
175        .chunks(64)
176        .map(|e| UInt64::from_bits(e))
177        .collect::<Vec<_>>();
178
179    for i in 0..24 {
180        let cs = &mut cs.namespace(|| format!("keccack round {}", i));
181
182        a = round_1600(cs, a, ROUND_CONSTANTS[i])?;
183    }
184
185    let a_new = a.into_iter().flat_map(|e| e.into_bits()).collect();
186
187    return Ok(a_new);
188}
189
190pub fn keccak256<E, CS>(cs: CS, input: &[Boolean]) -> Result<Vec<Boolean>, SynthesisError>
191where
192    E: ScalarEngine,
193    CS: ConstraintSystem<E>,
194{
195    assert_eq!(input.len(), 512);
196
197    let mut m = Vec::new();
198    for i in 0..1600 {
199        if i < 512 {
200            m.push(input[i].clone());
201        } else {
202            m.push(Boolean::Constant(false));
203        }
204    }
205
206    // # Padding
207    // d = 2^|Mbits| + sum for i=0..|Mbits|-1 of 2^i*Mbits[i]
208    // P = Mbytes || d || 0x00 || … || 0x00
209    // P = P xor (0x00 || … || 0x00 || 0x80)
210    //0x0100 ... 0080
211    m[512] = Boolean::Constant(true);
212    m[1087] = Boolean::Constant(true);
213
214    // # Initialization
215    // S[x,y] = 0,                               for (x,y) in (0…4,0…4)
216
217    // # Absorbing phase
218    // for each block Pi in P
219    //   S[x,y] = S[x,y] xor Pi[x+5*y],          for (x,y) such that x+5*y < r/w
220    //   S = Keccak-f[r+c](S)
221
222    let m = keccak_f_1600(cs, m)?;
223
224    // # Squeezing phase
225    // Z = empty string
226    let mut z = Vec::new();
227
228    // while output is requested
229    //   Z = Z || S[x,y],                        for (x,y) such that x+5*y < r/w
230    //   S = Keccak-f[r+c](S)
231    for i in 0..256 {
232        z.push(m[i].clone());
233    }
234
235    return Ok(z);
236}
bellman_keccak256/lib.rs

bellman_keccak256/
lib.rs
