blake3_proof_of_work/
lib.rs

1//! # Proof of Work
2//!
3//! The classic proof of work system based on a cryptogarphic hash function,
4//! in this case Blake3. To be explicit, a proof of work for some `bytes : &[u8]`
5//! and `cost : u32` is a `nonce : [u8; NONCE_SIZE]` such that the Blake3
6//! hash of `nonce` appended to `bytes` has at least `cost` leading zeros.
7//!
8//! This crate provides functionality for `search`ing and `verify`ing this
9//! sort of proof of work.
10
11pub const NONCE_SIZE: usize = 10usize;
12
13/// Errors which can occur in searching for a proof of work.
14#[derive(Debug)]
15pub enum Error {
16    Rand(rand::Error),
17    MeterOverdrawn,
18}
19
20impl From<rand::Error> for Error {
21    fn from(error: rand::Error) -> Error {
22        Error::Rand(error)
23    }
24}
25
26/// # Proof search
27///
28/// Searches through random `nonce`s by guessing random length `NONCE_SIZE`
29/// arrays and checking if the hash of the `nonce` appended to `bytes` has a
30/// Blake3 hash with at least `cost` leading zeros. In other words, this
31/// searches for a valid proof of work for the given `bytes` at the given
32/// `cost`.
33///
34/// If we search through `meter` `nonce`s, we return an `Error::MeterOverdrawn`
35/// error.
36pub fn search(bytes: &[u8], cost: u32, meter: u32) -> Result<[u8; NONCE_SIZE], Error> {
37    use rand::Fill;
38    let mut rng = rand::thread_rng();
39    let mut nonce = [0u8; NONCE_SIZE];
40    let mut counter = 0;
41    loop {
42        nonce.try_fill(&mut rng)?;
43        let mut hasher = blake3::Hasher::new();
44        hasher.update(&nonce);
45        hasher.update(bytes);
46        let hash = hasher.finalize();
47        if leading_zeros(hash.as_bytes()) >= cost {
48            break;
49        }
50        counter += 1;
51        if counter > meter {
52            return Err(Error::MeterOverdrawn);
53        }
54    }
55    Ok(nonce)
56}
57
58/// # Proof verification
59///
60/// This checks that the hash of the `nonce` appended to the `bytes` has
61/// a Blake3 hash with `cost` or more leading zeros. In other words, it verifies
62/// wheher or not this nonce constitutes a valid proof of work for this cost
63/// and input.
64pub fn verify(bytes: &[u8], nonce: [u8; NONCE_SIZE], cost: u32) -> bool {
65    let mut hasher = blake3::Hasher::new();
66    hasher.update(&nonce);
67    hasher.update(bytes);
68    let hash = hasher.finalize();
69    leading_zeros(hash.as_bytes()) >= cost
70}
71
72/// Compute the number of leading zeros of the given byte array.
73pub fn leading_zeros(bytes: &[u8]) -> u32 {
74    let mut count = 0;
75    let mut ptr = bytes;
76    loop {
77        if ptr.len() == 0 {
78            break;
79        } else {
80            let lz = ptr[0].leading_zeros();
81            ptr = &ptr[1..];
82            count += lz;
83            if lz < 8 {
84                break;
85            }
86        }
87    }
88    count
89}
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94    #[test]
95    fn leading_zeros_works() {
96        assert_eq!(leading_zeros(b"\x4f"), 1);
97        assert_eq!(leading_zeros(b"\x2f"), 2);
98        assert_eq!(leading_zeros(b"\x1f"), 3);
99        assert_eq!(leading_zeros(b"\x0f"), 4);
100        assert_eq!(leading_zeros(b"\x06"), 5);
101        assert_eq!(leading_zeros(b"\x02"), 6);
102        assert_eq!(leading_zeros(b"\x01"), 7);
103        assert_eq!(leading_zeros(b"\x00"), 8);
104        assert_eq!(leading_zeros(b"\x00\x4f"), 9);
105        assert_eq!(leading_zeros(b"\x00\x01"), 15);
106        assert_eq!(leading_zeros(b"\x00\x00"), 16);
107        assert_eq!(leading_zeros(&[0; 10000]), 10000 * 8);
108        assert_eq!(leading_zeros(&[255; 10000]), 0);
109    }
110
111    #[test]
112    fn search_works() -> Result<(), Error> {
113        let cost = 20;
114        let meter = 100000000;
115        let bytes = b"124124125124214121";
116        let nonce = search(bytes, cost, meter)?;
117        assert!(verify(bytes, nonce, cost));
118        for _i in 1..5 {
119            let nonce = search(bytes, cost, meter)?;
120            assert!(verify(bytes, nonce, cost));
121        }
122        Ok(())
123    }
124}
blake3_proof_of_work/lib.rs

blake3_proof_of_work/
lib.rs
