grin_core/pow/
cuckarood.rs

1// Copyright 2021 The Grin Developers
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Implementation of Cuckarood Cycle, based on Cuckoo Cycle designed by
16//! John Tromp. Ported to Rust from https://github.com/tromp/cuckoo.
17//!
18//! Cuckarood is a variation of Cuckaroo that's tweaked at the first HardFork
19//! to maintain ASIC-Resistance, as introduced in
20//! https://forum.grin.mw/t/mid-july-pow-hardfork-cuckaroo29-cuckarood29
21//! It uses a tweaked siphash round in which the rotation by 21 is replaced by
22//! a rotation by 25, halves the number of graph nodes in each partition,
23//! and requires cycles to alternate between even- and odd-indexed edges.
24
25use crate::global;
26use crate::pow::common::CuckooParams;
27use crate::pow::error::Error;
28use crate::pow::siphash::siphash_block;
29use crate::pow::{PoWContext, Proof};
30
31/// Instantiate a new CuckaroodContext as a PowContext. Note that this can't
32/// be moved in the PoWContext trait as this particular trait needs to be
33/// convertible to an object trait.
34pub fn new_cuckarood_ctx(edge_bits: u8, proof_size: usize) -> Result<Box<dyn PoWContext>, Error> {
35	let params = CuckooParams::new(edge_bits, edge_bits - 1, proof_size)?;
36	Ok(Box::new(CuckaroodContext { params }))
37}
38
39/// Cuckarood cycle context. Only includes the verifier for now.
40pub struct CuckaroodContext {
41	params: CuckooParams,
42}
43
44impl PoWContext for CuckaroodContext {
45	fn set_header_nonce(
46		&mut self,
47		header: Vec<u8>,
48		nonce: Option<u32>,
49		_solve: bool,
50	) -> Result<(), Error> {
51		self.params.reset_header_nonce(header, nonce)
52	}
53
54	fn find_cycles(&mut self) -> Result<Vec<Proof>, Error> {
55		unimplemented!()
56	}
57
58	fn verify(&self, proof: &Proof) -> Result<(), Error> {
59		let size = proof.proof_size();
60		if size != global::proofsize() {
61			return Err(Error::Verification("wrong cycle length".to_owned()));
62		}
63		let nonces = &proof.nonces;
64		let mut uvs = vec![0u64; 2 * size];
65		let mut ndir = vec![0usize; 2];
66		let mut xor0: u64 = 0;
67		let mut xor1: u64 = 0;
68		let mask = u64::MAX >> (size as u64).leading_zeros(); // round size up to 2-power - 1
69													  // the next two arrays form a linked list of nodes with matching bits 4..0|dir
70		let mut headu = vec![2 * size; 1 + mask as usize];
71		let mut headv = vec![2 * size; 1 + mask as usize];
72		let mut prev = vec![0usize; 2 * size];
73
74		for n in 0..size {
75			let dir = (nonces[n] & 1) as usize;
76			if ndir[dir] >= size / 2 {
77				return Err(Error::Verification("edges not balanced".to_owned()));
78			}
79			if nonces[n] > self.params.edge_mask {
80				return Err(Error::Verification("edge too big".to_owned()));
81			}
82			if n > 0 && nonces[n] <= nonces[n - 1] {
83				return Err(Error::Verification("edges not ascending".to_owned()));
84			}
85			// cuckarood uses a non-standard siphash rotation constant 25 as anti-ASIC tweak
86			let edge: u64 = siphash_block(&self.params.siphash_keys, nonces[n], 25, false);
87			let idx = 4 * ndir[dir] + 2 * dir;
88			let u = edge & self.params.node_mask;
89			let v = (edge >> 32) & self.params.node_mask;
90
91			uvs[idx] = u;
92			let ubits = ((u << 1 | dir as u64) & mask) as usize;
93			prev[idx] = headu[ubits];
94			headu[ubits] = idx;
95
96			uvs[idx + 1] = v;
97			let vbits = ((v << 1 | dir as u64) & mask) as usize;
98			prev[idx + 1] = headv[vbits];
99			headv[vbits] = idx + 1;
100
101			xor0 ^= u;
102			xor1 ^= v;
103			ndir[dir] += 1;
104		}
105		if xor0 | xor1 != 0 {
106			return Err(Error::Verification("endpoints don't match up".to_owned()));
107		}
108		let mut n = 0;
109		let mut i = 0;
110		let mut j;
111		loop {
112			// follow cycle
113			j = i;
114			let mut k = if i & 1 == 0 {
115				headu[((uvs[i] << 1 | 1) & mask) as usize]
116			} else {
117				headv[((uvs[i] << 1 | 0) & mask) as usize]
118			};
119			while k != 2 * size {
120				if uvs[k] == uvs[i] {
121					// find reverse edge endpoint identical to one at i
122					if j != i {
123						return Err(Error::Verification("branch in cycle".to_owned()));
124					}
125					j = k;
126				}
127				k = prev[k];
128			}
129			if j == i {
130				return Err(Error::Verification("cycle dead ends".to_owned()));
131			}
132			i = j ^ 1;
133			n += 1;
134			if i == 0 {
135				break;
136			}
137		}
138		if n == size {
139			Ok(())
140		} else {
141			Err(Error::Verification("cycle too short".to_owned()))
142		}
143	}
144}
145
146#[cfg(test)]
147mod test {
148	use super::*;
149
150	// empty header, nonce 64
151	static V1_19_HASH: [u64; 4] = [
152		0x89f81d7da5e674df,
153		0x7586b93105a5fd13,
154		0x6fbe212dd4e8c001,
155		0x8800c93a8431f938,
156	];
157	static V1_19_SOL: [u64; 42] = [
158		0xa00, 0x3ffb, 0xa474, 0xdc27, 0x182e6, 0x242cc, 0x24de4, 0x270a2, 0x28356, 0x2951f,
159		0x2a6ae, 0x2c889, 0x355c7, 0x3863b, 0x3bd7e, 0x3cdbc, 0x3ff95, 0x430b6, 0x4ba1a, 0x4bd7e,
160		0x4c59f, 0x4f76d, 0x52064, 0x5378c, 0x540a3, 0x5af6b, 0x5b041, 0x5e9d3, 0x64ec7, 0x6564b,
161		0x66763, 0x66899, 0x66e80, 0x68e4e, 0x69133, 0x6b20a, 0x6c2d7, 0x6fd3b, 0x79a8a, 0x79e29,
162		0x7ae52, 0x7defe,
163	];
164
165	// empty header, nonce 15
166	static V2_29_HASH: [u64; 4] = [
167		0xe2f917b2d79492ed,
168		0xf51088eaaa3a07a0,
169		0xaf4d4288d36a4fa8,
170		0xc8cdfd30a54e0581,
171	];
172	static V2_29_SOL: [u64; 42] = [
173		0x1a9629, 0x1fb257, 0x5dc22a, 0xf3d0b0, 0x200c474, 0x24bd68f, 0x48ad104, 0x4a17170,
174		0x4ca9a41, 0x55f983f, 0x6076c91, 0x6256ffc, 0x63b60a1, 0x7fd5b16, 0x985bff8, 0xaae71f3,
175		0xb71f7b4, 0xb989679, 0xc09b7b8, 0xd7601da, 0xd7ab1b6, 0xef1c727, 0xf1e702b, 0xfd6d961,
176		0xfdf0007, 0x10248134, 0x114657f6, 0x11f52612, 0x12887251, 0x13596b4b, 0x15e8d831,
177		0x16b4c9e5, 0x17097420, 0x1718afca, 0x187fc40c, 0x19359788, 0x1b41d3f1, 0x1bea25a7,
178		0x1d28df0f, 0x1ea6c4a0, 0x1f9bf79f, 0x1fa005c6,
179	];
180
181	#[test]
182	fn cuckarood19_29_vectors() {
183		global::set_local_chain_type(global::ChainTypes::Mainnet);
184		let mut ctx19 = new_impl(19, 42);
185		ctx19.params.siphash_keys = V1_19_HASH;
186		assert!(ctx19.verify(&Proof::new(V1_19_SOL.to_vec())).is_ok());
187		assert!(ctx19.verify(&Proof::zero(42)).is_err());
188		let mut ctx29 = new_impl(29, 42);
189		ctx29.params.siphash_keys = V2_29_HASH;
190		assert!(ctx29.verify(&Proof::new(V2_29_SOL.to_vec())).is_ok());
191		assert!(ctx29.verify(&Proof::zero(42)).is_err());
192	}
193
194	fn new_impl(edge_bits: u8, proof_size: usize) -> CuckaroodContext {
195		let params = CuckooParams::new(edge_bits, edge_bits - 1, proof_size).unwrap();
196		CuckaroodContext { params }
197	}
198}
grin_core/pow/cuckarood.rs

grin_core/pow/
cuckarood.rs
