iota_pow/
lib.rs

1#![warn(
2    missing_debug_implementations,
3    missing_docs,
4    rust_2018_idioms,
5    unreachable_pub
6)]
7
8//! Proof of Work in Iota
9
10use crossbeam::Sender;
11use failure::ensure;
12
13use std::sync::{Arc, RwLock};
14
15pub use iota_conversion::{Trinary, Trit, Trytes};
16
17use crossbeam::crossbeam_channel::unbounded;
18
19type Result<T> = ::std::result::Result<T, failure::Error>;
20
21/// State represents the various states that PearlDiver
22/// will be in throughout its life
23#[derive(Copy, Clone, Debug, PartialEq)]
24pub enum PearlDiverState {
25    /// Represents an instance of PearlDiver that hasn't been started yet.
26    NotStarted,
27    /// Represents an instance of PearlDiver that is currently running
28    Running,
29    /// Represents an instance of PearlDiver that has been cancelled
30    Cancelled,
31    /// Represents an instance of PearlDiver that has completed
32    Completed,
33}
34
35const TRANSACTION_LENGTH: usize = 8019;
36const CURL_HASH_LENGTH: usize = 243;
37const CURL_STATE_LENGTH: usize = CURL_HASH_LENGTH * 3;
38const HIGH_BITS: u64 =
39    0b1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111;
40const LOW_BITS: u64 =
41    0b0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000;
42
43/// The PearlDiver struct allows you to start, stop, and check in on
44/// PoW while its working
45///```rust
46/// use iota_pow::{PearlDiver, PowOptions};
47/// use iota_crypto::{Curl, Sponge};
48/// use rand::{thread_rng, Rng};
49///
50/// const HASH_SIZE: usize = 243;
51/// const MIN_WEIGHT_MAGNITUDE: usize = 9;
52///
53/// let mut rng = thread_rng();
54/// let mut curl = Curl::default();
55/// let trits: Vec<i8> = (0..8019).map(|_| rng.gen_range(-1, 2)).collect();
56/// let mut pearl_diver = PearlDiver::default();
57/// let result_trits = pearl_diver
58///     .search(trits, PowOptions{min_weight_magnitude: 9, ..PowOptions::default()})
59///     .unwrap();
60/// let mut hash_trits = [0; HASH_SIZE];
61/// curl.reset();
62/// curl.absorb(&result_trits).unwrap();
63/// curl.squeeze(&mut hash_trits).unwrap();
64/// for j in (HASH_SIZE - MIN_WEIGHT_MAGNITUDE..HASH_SIZE - 1).rev() {
65///     assert_eq!(hash_trits[j], 0);
66/// }
67///```
68#[derive(Debug)]
69pub struct PearlDiver {
70    running: Arc<RwLock<PearlDiverState>>,
71}
72
73impl Default for PearlDiver {
74    fn default() -> Self {
75        PearlDiver {
76            running: Arc::new(RwLock::new(PearlDiverState::NotStarted)),
77        }
78    }
79}
80
81/// Options of PoW configuration
82#[derive(Debug)]
83pub struct PowOptions {
84    /// * `min_weight_magnitude` - Difficulty factor to use for Proof of Work
85    pub min_weight_magnitude: usize,
86    /// * `threads` - The number of threads to use
87    pub threads: usize,
88}
89
90/// Provides reasonable defaults for PoW.
91/// * `min_weight_magnitude` = 14
92/// * `threads` = number of CPUs
93impl Default for PowOptions {
94    fn default() -> Self {
95        PowOptions {
96            min_weight_magnitude: 14,
97            threads: num_cpus::get(),
98        }
99    }
100}
101
102impl PearlDiver {
103    /// Creates a new PearlDiver instance
104    pub fn new() -> PearlDiver {
105        PearlDiver::default()
106    }
107
108    /// If you have multiple references to the same PearlDriver, this will allow
109    /// you to cancel the proof of work. For this to be useful, you'll probably need
110    /// to wrap the PearlDiver in an `Arc`
111    ///```rust
112    /// use iota_pow::PearlDiver;
113    /// let mut pearl_diver = PearlDiver::new();
114    /// // ... start running a pearl diver on another thread ...
115    /// pearl_diver.cancel();
116    ///```
117    pub fn cancel(&mut self) {
118        *self.running.write().unwrap() = PearlDiverState::Cancelled;
119    }
120
121    /// Returns the current status of PoW.
122    pub fn status(&self) -> PearlDiverState {
123        *self.running.read().unwrap()
124    }
125
126    /// Performs proof of work in place
127    ///
128    /// * `input` - Anything implementing the Trinary trait
129    /// * `options` - PoW options
130    pub fn search(&mut self, input: impl Trinary, options: PowOptions) -> Result<Vec<Trit>> {
131        let transaction_trits = input.trits();
132        let min_weight_magnitude = options.min_weight_magnitude;
133        ensure!(
134            transaction_trits.len() == TRANSACTION_LENGTH,
135            "Transaction length [{}], expected [{}]",
136            transaction_trits.len(),
137            TRANSACTION_LENGTH
138        );
139        ensure!(
140            min_weight_magnitude <= CURL_HASH_LENGTH,
141            "Min Weight Magnitude must be less than {} but it is {}",
142            min_weight_magnitude,
143            CURL_HASH_LENGTH
144        );
145        *self.running.write().unwrap() = PearlDiverState::Running;
146
147        let mut mid_state_low = [0; CURL_STATE_LENGTH];
148        let mut mid_state_high = [0; CURL_STATE_LENGTH];
149        initialize_mid_curl_states(&transaction_trits, &mut mid_state_low, &mut mid_state_high);
150
151        let actual_thread_count = num_cpus::get();
152        let threads = if options.threads == 0 {
153            1
154        } else if options.threads > actual_thread_count {
155            actual_thread_count
156        } else {
157            options.threads
158        };
159
160        let (tx, rx) = unbounded();
161        crossbeam::scope(|scope| {
162            for _ in 0..threads {
163                increment(
164                    &mut mid_state_low,
165                    &mut mid_state_high,
166                    162 + CURL_HASH_LENGTH / 9,
167                    162 + (CURL_HASH_LENGTH / 9) * 2,
168                );
169                let local_state_arc = Arc::clone(&self.running);
170                let ref_tx_trits = &transaction_trits;
171                let tx_clone = tx.clone();
172                scope.spawn(move |_| {
173                    get_runnable(
174                        &local_state_arc,
175                        &ref_tx_trits,
176                        tx_clone,
177                        min_weight_magnitude,
178                        mid_state_low,
179                        mid_state_high,
180                    );
181                });
182            }
183        })
184        .unwrap();
185        ensure!(
186            *self.running.read().unwrap() == PearlDiverState::Completed,
187            "Something went wrong."
188        );
189        let res = rx.recv().unwrap();
190        Ok(res)
191    }
192}
193
194fn get_runnable(
195    state: &Arc<RwLock<PearlDiverState>>,
196    transaction_trits: &[Trit],
197    tx: Sender<Vec<Trit>>,
198    min_weight_magnitude: usize,
199    mut mid_state_copy_low: [u64; CURL_STATE_LENGTH],
200    mut mid_state_copy_high: [u64; CURL_STATE_LENGTH],
201) {
202    let mut state_low = [0; CURL_STATE_LENGTH];
203    let mut state_high = [0; CURL_STATE_LENGTH];
204
205    let mut scratchpad_low = [0; CURL_STATE_LENGTH];
206    let mut scratchpad_high = [0; CURL_STATE_LENGTH];
207
208    let mask_start_index = CURL_HASH_LENGTH - min_weight_magnitude;
209    let mut mask = 0;
210
211    while mask == 0 && *state.read().unwrap() == PearlDiverState::Running {
212        increment(
213            &mut mid_state_copy_low,
214            &mut mid_state_copy_high,
215            162 + (CURL_HASH_LENGTH / 9) * 2,
216            CURL_HASH_LENGTH,
217        );
218        copy(
219            &mid_state_copy_low,
220            &mid_state_copy_high,
221            &mut state_low,
222            &mut state_high,
223        );
224        transform(
225            &mut state_low,
226            &mut state_high,
227            &mut scratchpad_low,
228            &mut scratchpad_high,
229        );
230
231        mask = HIGH_BITS;
232        for i in mask_start_index..CURL_HASH_LENGTH {
233            mask &= !(state_low[i] ^ state_high[i]);
234            if mask == 0 {
235                break;
236            }
237        }
238    }
239
240    if mask != 0 && *state.read().unwrap() == PearlDiverState::Running {
241        let mut out_mask = 1;
242        while (out_mask & mask) == 0 {
243            out_mask <<= 1;
244        }
245        let mut locked_transaction_trits = transaction_trits.to_vec();
246        for i in 0..CURL_HASH_LENGTH {
247            locked_transaction_trits[TRANSACTION_LENGTH - CURL_HASH_LENGTH + i] =
248                if (mid_state_copy_low[i] & out_mask) == 0 {
249                    1
250                } else if (mid_state_copy_high[i] & out_mask) == 0 {
251                    -1
252                } else {
253                    0
254                };
255        }
256        tx.send(locked_transaction_trits).unwrap();
257        *state.write().unwrap() = PearlDiverState::Completed;
258    }
259}
260
261fn copy(src_low: &[u64], src_high: &[u64], dest_low: &mut [u64], dest_high: &mut [u64]) {
262    dest_low[0..CURL_STATE_LENGTH].copy_from_slice(&src_low[0..CURL_STATE_LENGTH]);
263    dest_high[0..CURL_STATE_LENGTH].copy_from_slice(&src_high[0..CURL_STATE_LENGTH]);
264}
265
266fn initialize_mid_curl_states(
267    transaction_trits: &[Trit],
268    mid_state_low: &mut [u64],
269    mid_state_high: &mut [u64],
270) {
271    for i in CURL_HASH_LENGTH..CURL_STATE_LENGTH {
272        mid_state_low[i] = HIGH_BITS;
273        mid_state_high[i] = HIGH_BITS;
274    }
275
276    let mut offset = 0;
277    let mut curl_scratchpad_low = [0; CURL_STATE_LENGTH];
278    let mut curl_scratchpad_high = [0; CURL_STATE_LENGTH];
279    for _ in (0..(TRANSACTION_LENGTH - CURL_HASH_LENGTH) / CURL_HASH_LENGTH).rev() {
280        for j in 0..CURL_HASH_LENGTH {
281            match transaction_trits[offset] {
282                0 => {
283                    mid_state_low[j] = HIGH_BITS;
284                    mid_state_high[j] = HIGH_BITS;
285                }
286                1 => {
287                    mid_state_low[j] = LOW_BITS;
288                    mid_state_high[j] = HIGH_BITS;
289                }
290                _ => {
291                    mid_state_low[j] = HIGH_BITS;
292                    mid_state_high[j] = LOW_BITS;
293                }
294            }
295            offset += 1;
296        }
297        transform(
298            mid_state_low,
299            mid_state_high,
300            &mut curl_scratchpad_low,
301            &mut curl_scratchpad_high,
302        );
303    }
304    for i in 0..162 {
305        match transaction_trits[offset] {
306            0 => {
307                mid_state_low[i] = HIGH_BITS;
308                mid_state_high[i] = HIGH_BITS;
309            }
310            1 => {
311                mid_state_low[i] = LOW_BITS;
312                mid_state_high[i] = HIGH_BITS;
313            }
314            _ => {
315                mid_state_low[i] = HIGH_BITS;
316                mid_state_high[i] = LOW_BITS;
317            }
318        }
319        offset += 1;
320    }
321    mid_state_low[162] =
322        0b1101_1011_0110_1101_1011_0110_1101_1011_0110_1101_1011_0110_1101_1011_0110_1101;
323    mid_state_high[162] =
324        0b1011_0110_1101_1011_0110_1101_1011_0110_1101_1011_0110_1101_1011_0110_1101_1011;
325    mid_state_low[162 + 1] =
326        0b1111_0001_1111_1000_1111_1100_0111_1110_0011_1111_0001_1111_1000_1111_1100_0111;
327    mid_state_high[162 + 1] =
328        0b1000_1111_1100_0111_1110_0011_1111_0001_1111_1000_1111_1100_0111_1110_0011_1111;
329    mid_state_low[162 + 2] =
330        0b0111_1111_1111_1111_1110_0000_0000_1111_1111_1111_1111_1100_0000_0001_1111_1111;
331    mid_state_high[162 + 2] =
332        0b1111_1111_1100_0000_0001_1111_1111_1111_1111_1000_0000_0011_1111_1111_1111_1111;
333    mid_state_low[162 + 3] =
334        0b1111_1111_1100_0000_0000_0000_0000_0000_0000_0111_1111_1111_1111_1111_1111_1111;
335    mid_state_high[162 + 3] =
336        0b0000_0000_0011_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111;
337}
338
339fn transform(
340    state_low: &mut [u64],
341    state_high: &mut [u64],
342    scratchpad_low: &mut [u64],
343    scratchpad_high: &mut [u64],
344) {
345    let mut scratch_index = 0;
346    for _ in 0..81 {
347        copy(state_low, state_high, scratchpad_low, scratchpad_high);
348        for state_index in 0..CURL_STATE_LENGTH {
349            let alpha = scratchpad_low[scratch_index];
350            let beta = scratchpad_high[scratch_index];
351            if scratch_index < 365 {
352                scratch_index += 364;
353            } else {
354                scratch_index -= 365;
355            }
356            let gamma = scratchpad_high[scratch_index];
357            let delta = (alpha | (!gamma)) & (scratchpad_low[scratch_index] ^ beta);
358
359            state_low[state_index] = !delta;
360            state_high[state_index] = (alpha ^ gamma) | delta;
361        }
362    }
363}
364
365fn increment(mid_low: &mut [u64], mid_high: &mut [u64], from_index: usize, to_index: usize) {
366    let mut carry = 1;
367    let mut low: u64;
368    let mut hi: u64;
369    let mut i = from_index;
370    while i < to_index && carry != 0 {
371        low = mid_low[i];
372        hi = mid_high[i];
373        mid_low[i] = hi ^ low;
374        mid_high[i] = low;
375        carry = hi & (!low);
376        i += 1;
377    }
378}
iota_pow/lib.rs

iota_pow/
lib.rs
