traversev 0.2.0

A memory-hard proof-of-work scheme for trustless and permissioned proofs.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
#![cfg_attr(not(feature = "zeroize"), allow(unused_mut))]
#![doc = include_str!("../README.md")]
//! ## Example
//! ```
//! use traversev::{Params, TraverseV};
//!
//! fn main() {
//!     let params = Params::new(12 * 1024, 3, 8, 12).unwrap();
//!     let context = "65daysofstatic";
//!
//!     // Build a trustless instance
//!     let miner = TraverseV::new_trustless(context, params);
//!
//!     // Mine for a trustless proof over some input
//!     let input = b"65 Doesn't Understand You";
//!     let proof: u128 = miner.mine(input, 0u128, 1);
//!
//!     // Any trustless instance with the same configuration can verify
//!     let verifier = TraverseV::new_trustless(context, params);
//!     assert!(verifier.verify(input, proof));
//!
//!     // Build a permissioned instance with a shared secret
//!     let secret = b"One Time for All Time";
//!     let miner = TraverseV::new_permissioned(secret, context, params);
//!
//!     // A trustless instance cannot verify a permissioned proof
//!     let proof: u128 = miner.mine(input, 0u128, 1);
//!     assert!(!verifier.verify(input, proof));
//! }
//! ```
//!
//! ## Features
//!
//! The `zeroize` feature (disabled by default) implements `ZeroizeOnDrop` for
//! TraverseV, and zeroises intermediate values on a best-effort basis.
mod block;
mod errors;
mod memory;
mod mix;
mod params;

use blake3::Hasher;
use subtle::{Choice, ConstantTimeEq};
#[cfg(feature = "zeroize")]
use zeroize::{Zeroize, ZeroizeOnDrop};

pub use crate::block::Block;
pub use crate::errors::TraverseVErr;
pub use crate::memory::Mode;
use crate::memory::build_buffer;
use crate::mix::iter_mix;
pub use crate::params::Params;

/// TraverseV proof-of-work instance.
///
/// Construction fills a memory buffer using a fill adapted from Argon2d. Each
/// block is derived from its predecessor and a pseudorandomly selected earlier
/// block via Argon2's BLAKE2b-based compression function, repeated over
/// multiple passes.
///
/// Mining iteratively searches for a proof that satisfies this instance's
/// difficulty. Each candidate is evaluated by applying rounds of the
/// scryptROMix algorithm's second loop, mixing memory blocks into the
/// computation via Salsa20/8-based BlockMix.
#[cfg_attr(test, derive(Clone))]
pub struct TraverseV {
    mode: Mode,
    buffer: Vec<Block>,
    tag: [u8; 32],
    key: Option<[u8; 32]>,
    params: Params,
}

impl TraverseV {
    /// Build a new trustless `TraverseV` instance.
    ///
    /// Creates and fills a memory buffer, and stores this instance's
    /// application context and parameters.
    ///
    /// Proofs generated by this instance are trustless, meaning they are
    /// verifiable by any instance sharing the same application context and
    /// parameters.
    pub fn new_trustless(context: impl Into<String>, params: Params) -> Self {
        let context = context.into();
        let v = build_buffer(Mode::Trustless, None, &context, params);
        let mut tag = context_tag(&context);

        let this = Self {
            mode: Mode::Trustless,
            buffer: v,
            tag,
            key: None,
            params,
        };

        #[cfg(feature = "zeroize")]
        tag.zeroize();

        this
    }

    /// Build a new permissioned `TraverseV` instance.
    ///
    /// Creates and fills a memory buffer, and stores this instance's secret,
    /// application context, and parameters.
    ///
    /// Proofs generated by this instance are permissioned, meaning they are
    /// verifiable only by instances sharing the same application context,
    /// parameters, and shared secret.
    pub fn new_permissioned(
        secret: &[u8],
        context: impl Into<String>,
        params: Params,
    ) -> Self {
        let context = context.into();
        let v =
            build_buffer(Mode::Permissioned, Some(secret), &context, params);
        let mut tag = context_tag(&context);

        let mut hasher = Hasher::new_derive_key(&context);
        hasher.update(secret);
        let mut hash = hasher.finalize();
        let mut key: [u8; 32] = hash.into();

        let this = Self {
            mode: Mode::Permissioned,
            buffer: v,
            tag,
            key: Some(key),
            params,
        };

        #[cfg(feature = "zeroize")]
        {
            tag.zeroize();
            hasher.zeroize();
            hash.zeroize();
            key.zeroize();
        }

        this
    }

    /// Mine for a proof satisfying this instance's configured difficulty.
    ///
    /// Iteratively searches for candidates until one satisfies the difficulty.
    /// Runtime is unbounded on high difficulties. As the counter can overflow,
    /// the type must be wide enough to reach a satisfying proof, otherwise the
    /// counter wraps around causing an infinite loop.
    ///
    /// A [trustless](Self::new_trustless) instance mines for a trustless
    /// proof, and a [permissioned](Self::new_permissioned) instance mines for
    /// a permissioned proof.
    pub fn mine<T, N, I>(&self, input: &[u8], mut counter: T, increment: I) -> N
    where
        T: core::ops::AddAssign<I> + Into<N> + Copy,
        N: num_traits::ToBytes + Copy,
        I: Copy,
    {
        let mut hasher = Hasher::new();
        hasher.update(input);
        let mut hash = hasher.finalize();
        let mut prefix: [u8; 32] = hash.into();

        #[cfg(feature = "zeroize")]
        {
            hasher.zeroize();
            hash.zeroize();
        }

        let proof = loop {
            let v: N = counter.into();

            let mut candidate = self.evaluate(&prefix, v);
            let satisfied = self.check_n(&candidate);

            #[cfg(feature = "zeroize")]
            candidate.zeroize();

            // Break loop when the constraint is satisfied
            if bool::from(satisfied) {
                break v;
            }

            counter += increment
        };

        #[cfg(feature = "zeroize")]
        prefix.zeroize();

        proof
    }

    /// Verify that a proof satisfies this instance's difficulty.
    ///
    /// Successful verification requires the verifying instance's configuration
    /// to match the one the proof was mined with.
    ///
    /// A [trustless](Self::new_trustless) instance can only verify trustless
    /// proofs, and a [permissioned](Self::new_permissioned) instance can only
    /// verify permissioned proofs.
    pub fn verify<N: num_traits::ToBytes + Copy>(
        &self,
        input: &[u8],
        proof: N,
    ) -> bool {
        let mut hasher = Hasher::new();
        hasher.update(input);
        let mut hash = hasher.finalize();
        let mut prefix: [u8; 32] = hash.into();

        let mut candidate = self.evaluate(&prefix, proof);
        let satisfied = self.check_n(&candidate);

        #[cfg(feature = "zeroize")]
        {
            hasher.zeroize();
            hash.zeroize();
            prefix.zeroize();
            candidate.zeroize();
        }

        bool::from(satisfied)
    }

    /// This `TraverseV` instance's mode, as either trustless or permissioned.
    pub const fn mode(&self) -> Mode {
        self.mode
    }

    fn evaluate<N: num_traits::ToBytes + Copy>(
        &self,
        prefix: &[u8; 32],
        v: N,
    ) -> [u8; 32] {
        let mut hasher = if let Some(key) = &self.key {
            Hasher::new_keyed(key)
        } else {
            Hasher::new()
        };
        hasher.update(prefix);
        hasher.update(v.to_le_bytes().as_ref());
        hasher.update(&self.tag);

        let mut bytes = [0u8; Block::SIZE];
        let mut reader = hasher.finalize_xof();
        reader.fill(&mut bytes);
        let mut x = Block::new();
        x.copy_from_bytes(&bytes);

        let k = self.params.e_cost() as usize;
        iter_mix(&mut x, &self.buffer, k);
        let mut x_bytes = [0u8; Block::SIZE];
        x.copy_to_bytes(&mut x_bytes);
        let mut hash = blake3::hash(&x_bytes);
        let candidate: [u8; 32] = hash.into();

        #[cfg(feature = "zeroize")]
        {
            hasher.zeroize();
            reader.zeroize();
            bytes.zeroize();
            x.zeroize();
            x_bytes.zeroize();
            hash.zeroize();
        }

        candidate
    }

    fn check_n(&self, candidate: &[u8; 32]) -> Choice {
        let n = self.params.n_cost() as u8;
        let bytes = (n / 8) as usize;
        let bits = n % 8;

        // Verify first N bytes are zero, following N bits are zero
        let mut satisfied = Choice::from(1u8);
        for byte in &candidate[..bytes] {
            satisfied &= byte.ct_eq(&0u8);
        }
        if bits > 0 {
            let mask = (0xFF << (8 - bits)) as u8;
            satisfied &= (candidate[bytes] & mask).ct_eq(&0u8);
        }

        satisfied
    }
}

fn context_tag(context: &str) -> [u8; 32] {
    let mut hasher = Hasher::new();
    hasher.update(context.as_bytes());
    let mut hash = hasher.finalize();
    let tag: [u8; 32] = hash.into();

    #[cfg(feature = "zeroize")]
    {
        hasher.zeroize();
        hash.zeroize();
    }

    tag
}

impl Default for TraverseV {
    fn default() -> Self {
        let context = "";
        let params = Params::default();

        TraverseV::new_trustless(context, params)
    }
}

impl core::fmt::Debug for TraverseV {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("TraverseV")
            .field("mode", &self.mode)
            .field("params", &self.params)
            .finish_non_exhaustive()
    }
}

#[cfg(feature = "zeroize")]
impl Drop for TraverseV {
    fn drop(&mut self) {
        self.tag.zeroize();
        self.key.zeroize();
    }
}

#[cfg(feature = "zeroize")]
impl ZeroizeOnDrop for TraverseV {}

#[cfg(test)]
mod tests {
    use super::*;

    const CONTEXT: &str = "TRAVERSEV_TEST";
    const SECRET: &[u8] = b"This is a secret.";
    const INPUT: &[u8] = b"Some mining input.";

    /// Parameters for testing.
    ///
    /// 8 KiB memory, 2 memory fill iterations, 2 evaluation mixing rounds,
    /// and a difficulty of 12.
    fn params() -> Params {
        Params::new(8, 2, 2, 12).expect("test parameters are valid")
    }

    #[test]
    fn trustless_proof_verifies() {
        let miner = TraverseV::new_trustless(CONTEXT, params());
        let verifier = miner.clone();

        let proof: u128 = miner.mine(INPUT, 0u128, 1);
        assert!(verifier.verify(INPUT, proof));
    }

    #[test]
    fn permissioned_proof_verifies() {
        let miner = TraverseV::new_permissioned(SECRET, CONTEXT, params());
        let verifier = miner.clone();

        let proof: u128 = miner.mine(INPUT, 0u128, 1);
        assert!(verifier.verify(INPUT, proof));
    }

    #[test]
    fn trustless_rejects_permissioned_proof() {
        // At n = 12 a wrong instance accepts a proof with probability 1/4096.
        let miner = TraverseV::new_permissioned(SECRET, CONTEXT, params());
        let verifier = TraverseV::new_trustless(CONTEXT, params());

        assert_eq!(miner.mode(), Mode::Permissioned);
        assert_eq!(verifier.mode(), Mode::Trustless);

        let proof: u128 = miner.mine(INPUT, 0u128, 1);
        assert!(!verifier.verify(INPUT, proof));
    }

    #[test]
    fn verify_rejects_unsatisfied_difficulty() {
        let params = Params::new(2 * 1024, 2, 2, 255)
            .expect("test parameters are valid");

        let verifier = TraverseV::new_trustless(CONTEXT, params);
        assert!(!verifier.verify(INPUT, 0u128));
    }

    #[test]
    fn debug_omits_secret_state() {
        let params = params();
        let tv = TraverseV::new_permissioned(SECRET, CONTEXT, params);

        let output = format!("{tv:?}");

        assert!(output.contains("TraverseV"));
        assert!(output.contains(&format!("{:?}", tv.mode())));
        assert!(output.contains(&format!("{params:?}")));

        // No sensitive fields should appear
        for field in ["buffer", "tag", "key"] {
            assert!(!output.contains(field));
        }
    }
}