Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_hash/src/pow.rs

18.8 KiB, 34 runs

created by r1870400018:359, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1pub use oxedyne_fe2o3_core::{
2 prelude::*,
3 alt::Gnomon,
4 //bot::CtrlMsg,
5 channels::{
6 Recv,
7 simplex,
8 Simplex,
9 },
10 rand::Rand,
11 thread::{
12 Semaphore,
13 Sentinel,
14 thread_channel,
15 },
16};
17use oxedyne_fe2o3_iop_hash::api::Hasher;
18
19use std::{
20 thread,
21 time::{
22 SystemTime,
23 Duration,
24 },
25};
26
27use num_cpus;
28
29#[derive(Clone, Debug, Default)]
30pub struct PowResult {
31 pub nonce: Option<Vec<u8>>,
32 pub hash: Option<Vec<u8>>,
33 pub ithread: usize,
34 pub count: usize,
35 pub elapsed: Duration,
36}
37
38//#[derive(Clone, Debug, Default)]
39#[derive(Clone, Debug)]
40pub struct PowSearchResult {
41 pub found: bool,
42 pub artefact: Vec<u8>,
43 pub hash_len: usize,
44 pub ncpus: usize,
45 pub total_count: usize,
46 pub elapsed: Duration,
47 pub err: Option<Error<ErrTag>>,
48}
49
50/// A hash takes an input called the "pre-image". For a proof of work this is made up of what we
51/// call the "pow pre-image", consisting of an unchanging "pristine" and the nonce, which is varied
52/// in order to achieve a hash with the desired properties (conventionally a given number of
53/// leading zero bits).
54pub trait Pristine<
55 const P0: usize,
56 const P1: usize,
57>:
58 Clone
59 + Send
60 + Sync
61{
62 const PREFIX_BYTE_LEN: usize = P0;
63 const BYTE_LEN: usize = P1;
64 fn len(&self) -> usize { Self::BYTE_LEN }
65 fn prefix_len(&self) -> usize { Self::PREFIX_BYTE_LEN }
66
67 /// We can't use `oxedyne_fe2o3_core::bytes::ToBytes` because we want an array output.
68 fn to_bytes(&self) -> Outcome<[u8; P1]>;
69 fn prefix(&self, byts: &mut [u8]) -> Outcome<usize>;
70 fn timestamp_valid(&self, artefact: &[u8]) -> Outcome<bool>;
71}
72
73#[derive(Clone, Debug)]
74pub enum PowMsg {
75 Result(Outcome<PowResult>),
76 TimedOut(PowResult),
77}
78
79#[derive(Clone, Debug)]
80pub struct PowCreateParams<
81 const P0: usize,
82 const P1: usize,
83 PRIS: Pristine<P0, P1>,
84> {
85 pub pvars: PowVars<P0, P1, PRIS>,
86 pub time_lim: Duration,
87 pub count_lim: usize,
88}
89
90/// Capture the required (when receiving) and expected (when sending) Proof of Work parameters.
91#[derive(Clone, Debug, Default)]
92pub struct PowVars<
93 const P0: usize,
94 const P1: usize,
95 PRIS: Pristine<P0, P1>,
96> {
97 pub zbits: ZeroBits,
98 pub pristine: PRIS,
99}
100
101/// Proof of work scheme using a given hash scheme.
102#[derive(Clone, Debug)]
103pub struct ProofOfWork<
104 H: Hasher
105 //+ Send
106 //+ 'static
107> {
108 pub hasher: H,
109 pub len: usize,
110}
111
112pub type ZeroBits = u16;
113
114impl<
115 H: Hasher + Send + 'static,
116>
117 ProofOfWork<H>
118{
119
120 pub fn new(hasher: H) -> Outcome<Self> {
121 if hasher.is_identity() {
122 return Err(err!(
123 "The identity hash is not suitable for a proof of work.";
124 Invalid, Input));
125 }
126 let len = match hasher.hash_length() {
127 Gnomon::Known(len) => len,
128 _ => return Err(err!(
129 "The hash length is not known a priori.";
130 Invalid, Input)),
131 };
132 Ok(Self { hasher, len })
133 }
134
135 /// Launch the worker and if we can't send the result via the channel issue a last, desperate
136 /// message to the screen.
137 pub fn work_launcher<
138 const N: usize, // Input length.
139 const P1: usize, // Pristine length.
140 >(
141 hasher: H,
142 pristine: &[u8; P1],
143 zbits: ZeroBits,
144 time_lim: Duration,
145 count_lim: usize,
146 ithread: usize,
147 channel: Simplex<PowMsg>,
148 semaphore: Semaphore,
149 ) {
150 let result = Self::work::<N, P1>(
151 hasher,
152 pristine,
153 zbits,
154 time_lim,
155 count_lim,
156 ithread,
157 semaphore,
158 );
159 match channel.send(PowMsg::Result(result)) {
160 Err(e) => debug!("Proof of work worker thread {}: {}", ithread, e),
161 Ok(_) => (),
162 }
163 }
164
165 /// Search until a hash is found with the number of consecutive zeros at the least significant
166 /// end matching at least `ZeroBits` bits, unless the given count or time limits are exceeded.
167 /// The given `pristine` and a random nonce make up a input sequence of bytes that is hashed.
168 /// The nonce, loop count and hash is returned.
169 #[allow(unused_assignments)]
170 pub fn work<
171 const N: usize, // Input length.
172 const P1: usize, // Pristine length.
173 >(
174 hasher: H,
175 pristine: &[u8; P1],
176 zbits: ZeroBits,
177 time_lim: Duration,
178 count_lim: usize,
179 ithread: usize,
180 semaphore: Semaphore,
181 )
182 -> Outcome<PowResult>
183 {
184 if zbits == 0 {
185 return Err(err!(
186 "You probably want to the number of zero bits to be more than zero.";
187 Invalid, Input));
188 }
189 if N <= P1 {
190 return Err(err!(
191 "No room left for nonce with a pristine length {} and a specified input \
192 length of {}. Make pristine smaller, or input length longer.", P1, N;
193 Invalid, Input));
194 }
195 let zbits = zbits as usize;
196 let hash_len = match hasher.hash_length() {
197 Gnomon::Known(len) => len,
198 _ => return Err(err!(
199 "The hash length is not known a priori.";
200 Invalid, Input)),
201 };
202 if zbits > 8 * hash_len {
203 return Err(err!(
204 "The number of zero bits specified, {}, exceeds the hash size of {} bits.",
205 zbits, 8 * hash_len;
206 Invalid, Input));
207 }
208 let mut input = [0u8; N];
209 let zbyts = zbits / 8;
210 let zbits = zbits % 8;
211 let mask = if zbits == 0 {
212 0
213 } else {
214 !(u8::MAX << zbits)
215 };
216 for i in 0..P1 {
217 input[i] = pristine[i];
218 }
219 let mut elapsed = Duration::default();
220 let mut count = 0;
221 let start = SystemTime::now();
222 while semaphore.is_alive() {
223 let hasher_clone = hasher.clone();
224 Rand::fill_u8(&mut input[P1..]);
225
226 let mut found = true;
227 let hash = hasher_clone.hash(&[&input], []).as_vec();
228 // Compare zero bytes.
229 for z in 0..zbyts {
230 if hash[hash.len() - z - 1] != 0 {
231 found = false;
232 continue;
233 }
234 }
235 // Compare remaining zero bits.
236 if zbits > 0 {
237 if (hash[hash.len() - zbyts - 1] & mask) != 0 {
238 found = false;
239 continue;
240 }
241 }
242
243 count += 1;
244 if count > count_lim {
245 break;
246 }
247 if count % 1_000 == 0 {
248 elapsed = res!(start.elapsed());
249 if elapsed > time_lim {
250 break;
251 }
252 }
253 if found {
254 elapsed = res!(start.elapsed());
255 let pow_res = PowResult {
256 nonce: Some(input[P1..].to_vec()),
257 hash: Some(hash),
258 ithread,
259 count,
260 elapsed,
261 };
262 return Ok(pow_res);
263 }
264 }
265
266 elapsed = res!(start.elapsed());
267 let pow_res = PowResult {
268 nonce: None,
269 hash: None,
270 ithread,
271 count,
272 elapsed,
273 };
274 Ok(pow_res)
275 }
276
277 /// The `ProofOfWork` hasher must produce a hash that:
278 /// - contains the minimum number of leading zero bits, and
279 /// - matches the given hash.
280 pub fn validate_work<
281 //const S: usize,
282 >(
283 &self,
284 pristine_prefix: &[u8],
285 artefact_hash: &[u8],
286 artefact_prefix: &[u8],
287 zbits: ZeroBits,
288 //salt: [u8; S],
289 )
290 -> Outcome<bool>
291 {
292 debug!("");
293 let zbits = zbits as usize;
294 let zbyts = zbits / 8;
295 let zbits = zbits % 8;
296 let mask = if zbits == 0 {
297 0
298 } else {
299 !(u8::MAX << zbits)
300 };
301
302 let hasher = self.hasher.clone();
303 let hash2 = hasher.hash(
304 &[&pristine_prefix, &artefact_prefix],
305 [], // A salt is not necessary in proof of work.
306 ).as_vec();
307
308 //////// Debugging only
309 trace!("pristine prefix [{:>4}]: {:02x?}", pristine_prefix.len(), pristine_prefix);
310 trace!("artefact prefix [{:>4}]: {:02x?}", artefact_prefix.len(), artefact_prefix);
311 trace!("given pow hash [{:>4}]: {:02x?}", artefact_hash.len(), artefact_hash);
312 trace!("validation hash [{:>4}]: {:02x?}", hash2.len(), hash2);
313 ////////
314
315 // Compare zero bytes.
316 for z in 0..zbyts {
317 if hash2[hash2.len() - z - 1] != 0 {
318 return Ok(false);
319 }
320 }
321 // Compare remaining zero bits.
322 if zbits > 0 {
323 if (hash2[hash2.len() - zbyts - 1] & mask) != 0 {
324 return Ok(false);
325 }
326 }
327 if artefact_hash.len() != hash2.len() {
328 return Ok(false);
329 }
330 for (i, b) in artefact_hash.iter().enumerate() {
331 if hash2[i] != *b {
332 return Ok(false);
333 }
334 }
335 Ok(true)
336 }
337
338 /// ```ignore
339 /// ___________________ artefact _____________________
340 /// / \
341 /// ___________________ input N __________________
342 /// / \
343 /// ___________ pristine P1 __________
344 /// / \
345 /// +-------+---------------------------+-----------+-----------+
346 /// | | pristine artefact | nonce | hash |
347 /// +-------+---------------------------+-----------+-----------+
348 /// \_____/ \_____________________________________/ \_________/
349 /// | | |
350 /// pristine artefact artefact
351 /// prefix P0 prefix hash
352 ///
353 /// ```
354 pub fn create<
355 const N: usize, // Input length.
356 const P0: usize, // Pristine prefix length.
357 const P1: usize, // Pristine length.
358 PRIS: Pristine<P0, P1>,
359 >(
360 &self,
361 params: &PowCreateParams<P0, P1, PRIS>,
362 )
363 -> Outcome<PowSearchResult>
364 {
365 let pristine = res!(params.pvars.pristine.to_bytes());
366
367 // Launch work threads to discover a valid nonce.
368 let ncpus = num_cpus::get();
369 let mut sentinels = Vec::new();
370 let channel = simplex();
371 let mut pow_res = PowResult::default();
372 let mut errs = Vec::new();
373 let params = params.clone();
374 for i in 0..ncpus {
375 let (semaphore, sentinel) = thread_channel();
376 sentinels.push(sentinel);
377 let channel_clone = channel.clone();
378 let hasher_clone = self.hasher.clone();
379 // TODO make into async thread?
380 thread::spawn(move || {
381 Self::work_launcher::<{N}, {P1}>(
382 hasher_clone,
383 &pristine,
384 params.pvars.zbits,
385 params.time_lim,
386 params.count_lim,
387 i,
388 channel_clone,
389 semaphore,
390 );
391 });
392 }
393
394 // Periodically check on thread status and stop remaining threads if one has finished.
395 let mut total_count: usize = 0;
396 let mut waiting_for = ncpus;
397 let mut found = false;
398 while waiting_for > 0 {
399 match channel.try_recv() {
400 Recv::Empty => (),
401 Recv::Result(res) => {
402 waiting_for -= 1;
403 match res {
404 Err(e) | Ok(PowMsg::Result(Err(e))) => errs.push(Box::new(e)),
405 Ok(PowMsg::Result(Ok(res))) => {
406 if res.nonce.is_some() {
407 match total_count.checked_add(res.count) {
408 Some(sum) => total_count = sum,
409 None => debug!(
410 "Thread {}: Attempt to add count of {} to total count of \
411 {} for successful thread failed due to overflow.",
412 res.ithread, res.count, total_count,
413 ),
414 }
415 pow_res = res;
416 found = true;
417 for j in 0..ncpus {
418 if j != pow_res.ithread {
419 if !sentinels[j].is_finished() {
420 sentinels[j].stop();
421 }
422 }
423 }
424 }
425 },
426 Ok(PowMsg::TimedOut(res)) => {
427 match total_count.checked_add(res.count) {
428 Some(sum) => total_count = sum,
429 None => debug!(
430 "Thread {}: Attempt to add count of {} to total count of \
431 {} for unsuccessful thread failed due to overflow.",
432 res.ithread, res.count, total_count,
433 ),
434 };
435 },
436 //msg => return Err(err!(
437 // "Unrecognised message {:?} from worker thread.", msg,
438 //), Bug, Unreachable)),
439 }
440 },
441 }
442 std::thread::sleep(Duration::from_millis(10));
443 }
444 debug!("{:?}", pow_res);
445 // Discard the pristine prefix in the publicly visible artefact.
446 let start = params.pvars.pristine.prefix_len();
447 let mut artefact = pristine[start..].to_vec();
448 if let Some(mut nonce) = pow_res.nonce {
449 artefact.append(&mut nonce);
450 }
451 if let Some(mut hash) = pow_res.hash {
452 debug!("hash [{}]: {}",hash.len(),
453 hash.iter().map(|b| fmt!("{:08b}", b)).collect::<Vec<_>>().join("_"));
454 artefact.append(&mut hash);
455 }
456 Ok(PowSearchResult {
457 found,
458 artefact,
459 hash_len: self.len,
460 ncpus,
461 total_count,
462 elapsed: if found { pow_res.elapsed } else { params.time_lim },
463 err: if errs.len() == 0 { None } else { Some(Error::Collection(errs)) },
464 })
465 }
466
467 pub fn validate<
468 const P0: usize,
469 const P1: usize,
470 //const S: usize,
471 PRIS: Pristine<P0, P1>,
472 >(
473 &self,
474 powvars: &PowVars<P0, P1, PRIS>,
475 artefact: &[u8],
476 //salt: [u8; S],
477 )
478 -> Outcome<bool>
479 {
480 if !res!(powvars.pristine.timestamp_valid(&artefact)) {
481 debug!("Timestamp invalid");
482 return Ok(false);
483 }
484 let mut pristine_prefix = [0u8; P0];
485 res!(powvars.pristine.prefix(&mut pristine_prefix));
486 debug!("");
487 self.validate_work(
488 &pristine_prefix,
489 &artefact[artefact.len() - self.len..],
490 &artefact[..artefact.len() - self.len],
491 powvars.zbits,
492 //salt,
493 )
494 }
495}
496
497#[cfg(test)]
498mod tests {
499 use super::*;
500 use crate::hash::HashScheme;
501
502 #[derive(Clone, Debug)]
503 struct TestPristine<const P1: usize> {
504 byts: [u8; P1]
505 }
506
507 impl<const P1: usize> Default for TestPristine<P1> {
508 fn default() -> Self {
509 let mut byts = [0; P1];
510 Rand::fill_u8(&mut byts[..]);
511 Self {
512 byts,
513 }
514 }
515 }
516
517 impl<
518 const P0: usize,
519 const P1: usize,
520 >
521 Pristine<P0, P1> for TestPristine<P1>
522 {
523 const PREFIX_BYTE_LEN: usize = 0;
524 fn to_bytes(&self) -> Outcome<[u8; P1]> { Ok(self.byts) }
525 fn prefix(&self, _byts: &mut [u8]) -> Outcome<usize> { Ok(0) }
526 fn timestamp_valid(&self, _artefact: &[u8]) -> Outcome<bool> { Ok(true) }
527 }
528
529 #[test]
530 fn test_concurrent_work() -> Outcome<()> {
531 let zbits = 25;
532 const P1: usize = 8;
533 const NONCE: usize = 8; // Nonce size
534 let pristine = TestPristine::<P1>::default();
535 let pow = res!(ProofOfWork::new(HashScheme::new_seahash()));
536 let pvars = PowVars {
537 zbits,
538 pristine: pristine.clone(),
539 };
540 let powp = PowCreateParams {
541 pvars: pvars.clone(),
542 time_lim: Duration::from_secs(200),
543 count_lim: usize::MAX,
544 };
545 match pow.create::<{P1+NONCE}, 0, P1, TestPristine<P1>>(&powp) {
546 Ok(PowSearchResult{
547 found,
548 artefact,
549 hash_len,
550 ncpus: _,
551 total_count,
552 elapsed,
553 err,
554 }) => {
555 if found {
556 debug!("total count = {}", total_count);
557 debug!("elapsed = {:.2?}", elapsed);
558 debug!("pristine = {:02x?}", pristine);
559 debug!("zero bits = {}", zbits);
560 debug!("artefact [{}] = {:02x?}", artefact.len(), artefact);
561 let hash = &artefact[artefact.len() - hash_len..];
562 debug!("hash: ");
563 println!("{:02x?}", hash);
564 for byt in hash {
565 print!(" {:08b}", byt);
566 }
567 println!();
568 if let Some(e) = err {
569 debug!("{}", e);
570 }
571 assert!(res!(pow.validate(
572 &pvars,
573 &artefact,
574 )));
575 // Change a byte and ensure it does not validate.
576 let mut mangled = artefact.clone();
577 mangled[2] = 134;
578 match pow.validate(
579 &pvars,
580 &mangled,
581 ) {
582 Ok(true) => return Err(err!(
583 "The proof of work, with one byte changed, should not have validated.";
584 Input, Invalid)),
585 _ => (),
586 }
587 } else {
588 debug!("Proof of work timed out.");
589 }
590 },
591 Err(e) => return Err(e),
592 }
593 Ok(())
594 }
595}