wgtk/net/
cuckoo.rs

1//! Cuckoo cycle challenge implementation.
2
3use std::collections::HashSet;
4
5use sha2::{Sha256, Digest};
6
7
8pub const SHIFT_SIZE: usize = 25;
9pub const PROOF_SIZE: usize = 42;
10pub const MAX_PATH_LEN: usize = 8192;
11
12pub const FULL_SIZE: usize = 1 << SHIFT_SIZE;
13pub const HALF_SIZE: usize = FULL_SIZE / 2;
14pub const NODE_MASK: usize = HALF_SIZE - 1;
15pub const CUCKOO_SIZE: usize = FULL_SIZE + 1;
16
17
18#[derive(Clone)]
19pub struct SipHashContext {
20    v0: u64,
21    v1: u64,
22    v2: u64,
23    v3: u64,
24}
25
26impl SipHashContext {
27
28    pub fn with_prefix(prefix: &[u8]) -> Self {
29        
30        let hash_raw = Sha256::new_with_prefix(prefix).finalize();
31        let hash = hash_raw.as_slice();
32        let k0 = u64::from_le_bytes(hash[0..8].try_into().unwrap());
33        let k1 = u64::from_le_bytes(hash[8..16].try_into().unwrap());
34
35        Self {
36            v0: k0 ^ 0x736f6d6570736575,
37            v1: k1 ^ 0x646f72616e646f6d,
38            v2: k0 ^ 0x6c7967656e657261,
39            v3: k1 ^ 0x7465646279746573,
40        }
41
42    }
43
44    pub fn round(&mut self) {
45        self.v0 += self.v1;
46        self.v2 += self.v3;
47        self.v1 = self.v1.rotate_left(13);
48        self.v3 = self.v3.rotate_left(16);
49        self.v1 ^= self.v0;
50        self.v3 ^= self.v2;
51        self.v0 = self.v0.rotate_left(32);
52        self.v2 += self.v1;
53        self.v0 += self.v3;
54        self.v1 = self.v1.rotate_left(17);
55        self.v3 = self.v3.rotate_left(21);
56        self.v1 ^= self.v2;
57        self.v3 ^= self.v0;
58        self.v2 = self.v2.rotate_left(32);
59    }
60
61    pub fn sip_hash24(&self, nonce: u64) -> u64 {
62        
63        let mut sip = self.clone();
64
65        sip.v3 ^= nonce;
66        sip.round();
67        sip.round();
68        sip.v0 ^= nonce;
69        sip.v2 ^= 0xFF;
70        sip.round();
71        sip.round();
72        sip.round();
73        sip.round();
74        
75        sip.v0 ^ sip.v1 ^ sip.v2 ^ sip.v3
76
77    }
78
79    pub fn sip_node(&self, nonce: u64, uorv: u32) -> usize {
80        (self.sip_hash24(2 * nonce + uorv as u64) & NODE_MASK as u64) as usize
81    }
82
83    pub fn sip_edge(&self, nonce: u64) -> (usize, usize) {
84        (
85            self.sip_node(nonce, 0),
86            self.sip_node(nonce, 1),
87        )
88    }
89
90}
91
92
93pub struct CuckooContext {
94    sip_hash: SipHashContext,
95    easiness: u64,
96    cuckoo: Box<[usize; CUCKOO_SIZE]>
97}
98
99impl CuckooContext {
100
101    pub fn new(easiness: u64, prefix: &[u8]) -> Self {
102        Self {
103            easiness,
104            sip_hash: SipHashContext::with_prefix(prefix),
105            cuckoo: Box::new([0; CUCKOO_SIZE])
106        }
107    }
108
109    pub fn work(&mut self) -> Option<Vec<u64>> {
110
111        let mut us = Box::new([0; MAX_PATH_LEN]);
112        let mut vs = Box::new([0; MAX_PATH_LEN]);
113
114        for nonce in 0..self.easiness {
115
116            let (mut u0, mut v0) = self.sip_hash.sip_edge(nonce);
117            u0 += 1;
118            v0 += 1 + HALF_SIZE;
119
120            let u = self.cuckoo[u0];
121            let v = self.cuckoo[v0];
122
123            if u == v0 || v == u0 {
124                continue // ignore duplicate edges
125            }
126
127            us[0] = u0;
128            vs[0] = v0;
129
130            let mut nu = path(&self.cuckoo, u, &mut us).unwrap();
131            let mut nv = path(&self.cuckoo, v, &mut vs).unwrap();
132
133            if us[nu] == vs[nv] {
134
135                let min = nu.min(nv);
136                loop {
137                    nu -= min;
138                    nv -= min;
139                    if us[nu] != vs[nv] {
140                        break;
141                    }
142                    nu += 1;
143                    nv += 1;
144                }
145
146                let len = nu + nv + 1;
147
148                if len == PROOF_SIZE {
149                    return Some(self.solution(&us, nu, &vs, nv));
150                }
151
152            } else if nu < nv {
153                while nu != 0 {
154                    nu -= 1;
155                    self.cuckoo[us[nu + 1]] = us[nu];
156                }
157                self.cuckoo[u0] = v0;
158            } else {
159                while nv != 0 {
160                    nv -= 1;
161                    self.cuckoo[vs[nv + 1]] = vs[nv];
162                }
163                self.cuckoo[v0] = u0;
164            }
165
166        }
167
168        None
169
170    }
171
172    pub fn solution(&self, us: &[usize; MAX_PATH_LEN], nu: usize, vs: &[usize; MAX_PATH_LEN], nv: usize) -> Vec<u64> {
173
174        let mut cycle = HashSet::new();
175        let mut solution = Vec::new();
176
177        cycle.insert((us[0], vs[0]));
178        
179        for nu in (0..nu).rev() {
180            cycle.insert((us[(nu + 1) & !1], us[nu | 1]));
181        }
182
183        for nv in (0..nv).rev() {
184            cycle.insert((vs[nv | 1], vs[(nv + 1) & !1]));
185        }
186
187        for nonce in 0..self.easiness {
188            
189            let mut edge = self.sip_hash.sip_edge(nonce);
190            edge.0 += 1;
191            edge.1 += 1;
192
193            if cycle.remove(&edge) {
194                solution.push(nonce);
195            }
196
197        }
198
199        solution
200
201    }
202
203}
204
205
206fn path(cuckoo: &[usize; CUCKOO_SIZE], mut u: usize, us: &mut [usize; MAX_PATH_LEN]) -> Option<usize> {
207
208    let mut nu = 0isize;
209
210    while u != 0 {
211
212        u = cuckoo[u];
213        nu += 1;
214
215        if nu >= MAX_PATH_LEN as _ {
216
217            loop {
218                nu -= 1;
219                if nu == 0 && us[nu as usize] != u {
220                    break;
221                }
222            }
223
224            if nu < 0 {
225                return None;
226            }
227
228        }
229
230        us[nu as usize] = u;
231
232    }
233
234    Some(nu as usize)
235
236}
wgtk/net/cuckoo.rs

wgtk/net/
cuckoo.rs
