spongefish_pow/
fused.rs

1//! Proof of work using the Fiat–Shamir verifier-message oracle.
2//!
3//! The prover sends a nonce as an additional prover message before the
4//! verifier message. Both sides absorb the nonce and squeeze check bytes.
5//! The verifier rejects unless the low `d` bits are zero, where `d` is the
6//! difficulty. The prover uses the oracle to try candidate nonces on
7//! snapshots of the public sponge before sending one.
8
9use spongefish::{Encoding, FromNarg, NargReader, VerificationError};
10
11use crate::PowStrategy;
12
13/// A configuration for proof of work on the transcript sponge.
14///
15/// For `bits > 0`:
16///
17/// 1. The prover sends the least passing nonce `n < 2^(bits + 7)` as
18///    canonical unsigned LEB128.
19/// 2. The verifier checks the nonce encoding and range. Both parties absorb
20///    the nonce and squeeze `ceil(bits / 8)` check bytes. The verifier rejects
21///    unless their low `bits` bits, read little-endian, are zero.
22/// 3. Both parties derive the verifier message from the following sponge
23///    output via [`Transcript::verifier_message`](spongefish::Transcript::verifier_message).
24///
25/// At zero difficulty, both parties derive the verifier message directly.
26///
27/// # Security
28///
29/// For fresh, independent uniform sponge output, the check passes with
30/// probability `2^-bits`. The bytes after the check remain uniform.
31/// The soundness benefit depends on the protocol, sponge and challenge
32/// decoding. The difficulty, placement of this step and verifier-message
33/// type must be fixed by the protocol and bound in the session identifier.
34///
35/// # Performance
36///
37/// The default helper searches sequentially on the calling thread. On a
38/// [`ProverState`](spongefish::ProverState) whose public sponge is `Send`,
39/// `verifier_message_pow_parallel` (feature `parallel`) searches on the
40/// Rayon pool and writes the same proof. With a permutation-backed sponge,
41/// when the nonce, the check bytes and the returned message fit in one rate
42/// block, a search trial costs about one permutation.
43///
44/// # Errors
45///
46/// The prover returns [`VerificationError`] if:
47///
48/// - The search exhausts the nonce space.
49/// - At positive difficulty, a custom transcript provides no
50///   [`Transcript::verifier_message_oracle`](spongefish::Transcript::verifier_message_oracle).
51/// - The live transcript rejects the nonce that passed the oracle check.
52///   The nonce has already been written, so discard the prover state.
53///
54/// The verifier returns an error if the nonce is truncated, noncanonical or
55/// out of range, if the check bits are nonzero, or if the transcript has
56/// already been rejected.
57///
58/// # Panics
59///
60/// Panics if `bits > 57`: the `u64` nonce space must hold `2^(bits+7)` values.
61#[derive(Clone, Copy, Debug, PartialEq, Eq)]
62pub struct FusedPowConfig {
63    bits: u32,
64}
65
66impl FusedPowConfig {
67    /// Configure fused PoW at a protocol-fixed difficulty, from 0 through 57.
68    ///
69    /// # Panics
70    /// Panics if `bits > 57`.
71    pub const fn new(bits: u32) -> Self {
72        assert!(bits <= MAX_BITS, "bits must be at most 57");
73        Self { bits }
74    }
75}
76
77impl PowStrategy for FusedPowConfig {
78    type Nonce = Leb128;
79
80    fn enabled(&self) -> bool {
81        self.bits != 0
82    }
83
84    fn last_nonce(&self) -> u64 {
85        last_nonce(self.bits)
86    }
87
88    fn challenge_len(&self) -> usize {
89        word_len(self.bits)
90    }
91
92    fn accepts(&self, _nonce: u64, challenge: &[u8]) -> bool {
93        if challenge.len() != self.challenge_len() {
94            return false;
95        }
96        let mut word = [0; 8];
97        word[..challenge.len()].copy_from_slice(challenge);
98        accepts(self.bits, word)
99    }
100}
101
102// Reserve 2^7 times the expected work in the u64 nonce space.
103const MAX_BITS: u32 = 57;
104
105const fn last_nonce(bits: u32) -> u64 {
106    u64::MAX >> (MAX_BITS - bits)
107}
108
109const fn word_len(bits: u32) -> usize {
110    (bits as usize).div_ceil(8)
111}
112
113const fn accepts(bits: u32, word: [u8; 8]) -> bool {
114    u64::from_le_bytes(word) & ((1u64 << bits) - 1) == 0
115}
116
117/// A canonical unsigned LEB128 nonce, with no redundant trailing zero byte.
118#[derive(Clone, Copy)]
119pub struct Leb128(u64);
120
121impl From<u64> for Leb128 {
122    fn from(value: u64) -> Self {
123        Self(value)
124    }
125}
126
127impl From<Leb128> for u64 {
128    fn from(value: Leb128) -> Self {
129        value.0
130    }
131}
132
133impl Encoding for Leb128 {
134    fn encode(&self) -> impl AsRef<[u8]> {
135        let mut value = self.0;
136        let mut bytes = [0; 10];
137        let mut len = 0;
138        loop {
139            bytes[len] = (value & 0x7f) as u8;
140            value >>= 7;
141            len += 1;
142            if value == 0 {
143                return Leb128Bytes { bytes, len };
144            }
145            bytes[len - 1] |= 0x80;
146        }
147    }
148}
149
150struct Leb128Bytes {
151    bytes: [u8; 10],
152    len: usize,
153}
154
155impl AsRef<[u8]> for Leb128Bytes {
156    fn as_ref(&self) -> &[u8] {
157        &self.bytes[..self.len]
158    }
159}
160
161impl FromNarg for Leb128 {
162    fn from_narg(reader: &NargReader<'_>) -> Result<Self, VerificationError> {
163        let mut value = 0u64;
164        for i in 0..10 {
165            let byte: u8 = reader.read()?;
166            if i == 9 && byte > 1 {
167                return Err(VerificationError);
168            }
169            value |= u64::from(byte & 0x7f) << (7 * i);
170            if byte & 0x80 == 0 {
171                return if i == 0 || byte != 0 {
172                    Ok(Self(value))
173                } else {
174                    Err(VerificationError)
175                };
176            }
177        }
178        Err(VerificationError)
179    }
180}
181
182#[cfg(test)]
183mod tests {
184    use std::cell::RefCell;
185
186    use spongefish::{
187        instantiations::{Shake128, TurboShake128},
188        DuplexSpongeInit, DuplexSpongeInterface, Narg, ProverState, Transcript, VerificationError,
189        VerifierState, Witness,
190    };
191
192    use super::FusedPowConfig;
193    use crate::{verifier_message_pow_parallel, PowStrategy, PowTranscriptExt};
194    #[derive(Clone, Debug, PartialEq, Eq)]
195    enum Event {
196        Absorb(Vec<u8>),
197        Squeeze(usize),
198    }
199
200    thread_local! {
201        static EVENTS: RefCell<Vec<Event>> = const { RefCell::new(Vec::new()) };
202    }
203
204    fn events() -> Vec<Event> {
205        EVENTS.with_borrow(Clone::clone)
206    }
207
208    #[derive(Clone)]
209    struct RecordingSponge<const OUTPUT: u8 = 0>;
210
211    impl<const OUTPUT: u8> DuplexSpongeInterface for RecordingSponge<OUTPUT> {
212        type U = u8;
213
214        fn absorb(&mut self, input: &[u8]) -> &mut Self {
215            EVENTS.with_borrow_mut(|events| events.push(Event::Absorb(input.to_vec())));
216            self
217        }
218
219        fn squeeze(&mut self, output: &mut [u8]) -> &mut Self {
220            EVENTS.with_borrow_mut(|events| events.push(Event::Squeeze(output.len())));
221            output.fill(OUTPUT);
222            self
223        }
224    }
225
226    impl<const OUTPUT: u8> DuplexSpongeInit for RecordingSponge<OUTPUT> {
227        fn init(_session_id: &[u8; 32]) -> Self {
228            Self
229        }
230    }
231
232    /// A verifier over [`RecordingSponge`], with the log cleared after the
233    /// instance is absorbed.
234    fn recording_verifier(proof: &[u8]) -> VerifierState<'_, RecordingSponge> {
235        let session_id = Narg::derive_session_id(b"pow/tests/v1");
236        let verifier = VerifierState::new(&session_id, &0u32, proof);
237        EVENTS.with_borrow_mut(Vec::clear);
238        verifier
239    }
240
241    #[test]
242    fn missing_prover_oracle_returns_an_error_before_writing_a_nonce() {
243        struct MissingOracle;
244
245        impl Transcript for MissingOracle {
246            fn prover_message<T>(&mut self, _value: Witness<T>) -> Result<T, VerificationError>
247            where
248                T: spongefish::Encoding + spongefish::FromNarg,
249            {
250                panic!("a missing oracle must fail before writing a nonce")
251            }
252
253            fn verifier_message<T: spongefish::FromUniform>(&mut self) -> T {
254                panic!("a missing oracle must not produce a protected challenge")
255            }
256
257            fn public_message<T: spongefish::Encoding + ?Sized>(&mut self, _value: &T) {
258                panic!("unexpected public message")
259            }
260
261            fn prover_only<T>(&self, compute: impl FnOnce() -> T) -> Witness<T> {
262                Witness::known(compute())
263            }
264
265            fn sample<T: spongefish::FromUniform>(&mut self) -> Witness<T> {
266                panic!("PoW must not sample private randomness")
267            }
268
269            fn sample_vec<T: spongefish::FromUniform>(&mut self, _n: usize) -> Witness<Vec<T>> {
270                panic!("PoW must not sample private randomness")
271            }
272
273            fn check(&self, _holds: impl FnOnce() -> bool) -> Result<(), VerificationError> {
274                panic!("a missing oracle must fail before checking a nonce")
275            }
276        }
277
278        assert!(MissingOracle
279            .verifier_message_pow::<u64>(FusedPowConfig::new(1))
280            .is_err());
281    }
282
283    #[test]
284    fn exhausted_grinding_returns_an_error_without_sending_a_nonce() {
285        let session_id = Narg::derive_session_id(b"pow/tests/exhausted");
286        let mut prover =
287            ProverState::<RecordingSponge<255>>::new_with_seed(&session_id, &0u32, [7; 32]);
288        assert!(prover
289            .verifier_message_pow::<u64>(FusedPowConfig::new(1))
290            .is_err());
291        assert_eq!(prover.into_narg_string(), b"");
292        let mut parallel =
293            ProverState::<RecordingSponge<255>>::new_with_seed(&session_id, &0u32, [7; 32]);
294        assert!(
295            verifier_message_pow_parallel::<u64>(&mut parallel, FusedPowConfig::new(1)).is_err()
296        );
297        assert_eq!(parallel.into_narg_string(), b"");
298    }
299
300    #[test]
301    fn rejected_nonce_blocks_challenge_and_poisoning_persists() {
302        let session_id = Narg::derive_session_id(b"pow/tests/rejected");
303        let mut verifier = VerifierState::<RecordingSponge<255>>::new(&session_id, &0u32, &[0]);
304        EVENTS.with_borrow_mut(Vec::clear);
305        assert!(verifier
306            .verifier_message_pow::<u64>(FusedPowConfig::new(8))
307            .is_err());
308        // Only the check byte is squeezed; no protected challenge is produced.
309        assert_eq!(events(), [Event::Absorb(vec![0]), Event::Squeeze(1)]);
310        assert!(verifier
311            .verifier_message_pow::<u64>(FusedPowConfig::new(0))
312            .is_err());
313        assert_eq!(events(), [Event::Absorb(vec![0]), Event::Squeeze(1)]);
314        assert!(verifier
315            .check(|| panic!("a failed check must not run again"))
316            .is_err());
317        assert!(verifier.prover_message::<u8>().is_err());
318        assert!(verifier.prover_messages_vec::<u8>(0).is_err());
319        assert!(verifier
320            .verifier_message_pow::<u64>(FusedPowConfig::new(8))
321            .is_err());
322        assert!(verifier.check_eof().is_err());
323    }
324
325    fn leb128(nonce: u64) -> Vec<u8> {
326        spongefish::Encoding::encode(&super::Leb128::from(nonce))
327            .as_ref()
328            .to_vec()
329    }
330
331    fn reference_nonce(mut nonce: u64) -> Vec<u8> {
332        let mut bytes = Vec::new();
333        loop {
334            let digit = (nonce % 128) as u8;
335            nonce /= 128;
336            bytes.push(digit + if nonce == 0 { 0 } else { 128 });
337            if nonce == 0 {
338                return bytes;
339            }
340        }
341    }
342
343    fn reference_round<H: DuplexSpongeInit<U = u8>>(
344        bits: u32,
345        padding: usize,
346        skipped: usize,
347    ) -> (Vec<u8>, u64, u64) {
348        let session = Narg::derive_session_id(b"pow/tests/vectors/v1");
349        let mut before = H::init(session.as_bytes());
350        before.absorb(&0u32.to_le_bytes());
351        before.absorb(&vec![42; padding]);
352        let (proof, mut after) = if bits == 0 {
353            (Vec::new(), before)
354        } else {
355            (0..1u64 << (bits + 7))
356                .find_map(|nonce| {
357                    let proof = reference_nonce(nonce);
358                    let mut after = before.clone();
359                    after.absorb(&proof);
360                    let mut check = vec![0; bits.div_ceil(8) as usize];
361                    after.squeeze(&mut check);
362                    let passes =
363                        (0..bits).all(|bit| check[bit as usize / 8] & (1 << (bit % 8)) == 0);
364                    passes.then_some((proof, after))
365                })
366                .unwrap()
367        };
368        let challenge = u64::from_le_bytes(after.squeeze_array());
369        after.squeeze(&mut vec![0; skipped]);
370        let following = u64::from_le_bytes(after.squeeze_array());
371        (proof, challenge, following)
372    }
373
374    #[test]
375    fn roundtrips_match_an_independent_manual_reference() {
376        for (bits, padding, skipped) in [
377            (0, 0, 0),
378            (1, 0, 0),
379            (7, 163, 152),
380            (8, 0, 0),
381            (9, 164, 152),
382        ] {
383            assert_round::<TurboShake128>(bits, padding, skipped);
384        }
385        for (bits, padding, skipped) in [
386            (0, 0, 0),
387            (1, 0, 0),
388            (7, 131, 120),
389            (8, 0, 0),
390            (9, 132, 120),
391        ] {
392            assert_round::<spongefish::instantiations::Keccak>(bits, padding, skipped);
393        }
394    }
395
396    fn assert_round<H: DuplexSpongeInit<U = u8> + Send>(bits: u32, padding: usize, skipped: usize) {
397        let session = Narg::derive_session_id(b"pow/tests/vectors/v1");
398        let (proof, challenge, following) = reference_round::<H>(bits, padding, skipped);
399        let mut prover = ProverState::<H, Shake128>::new_with_seed(&session, &0u32, [7; 32]);
400        for _ in 0..padding {
401            prover.public_message(&42u8);
402        }
403        assert_eq!(
404            prover
405                .verifier_message_pow::<u64>(FusedPowConfig::new(bits))
406                .unwrap(),
407            challenge
408        );
409        for _ in 0..skipped {
410            let _ = prover.verifier_message::<u8>();
411        }
412        assert_eq!(prover.verifier_message::<u64>(), following);
413        assert_eq!(prover.into_narg_string(), proof);
414        let mut verifier = VerifierState::<H>::new(&session, &0u32, &proof);
415        for _ in 0..padding {
416            verifier.public_message(&42u8);
417        }
418        assert_eq!(
419            verifier
420                .verifier_message_pow::<u64>(FusedPowConfig::new(bits))
421                .unwrap(),
422            challenge
423        );
424        for _ in 0..skipped {
425            let _ = verifier.verifier_message::<u8>();
426        }
427        assert_eq!(verifier.verifier_message::<u64>(), following);
428        verifier.check_eof().unwrap();
429        #[cfg(all(feature = "parallel", not(target_arch = "wasm32")))]
430        for workers in [1, 3, 4] {
431            let pool = rayon::ThreadPoolBuilder::new()
432                .num_threads(workers)
433                .build()
434                .unwrap();
435            pool.install(|| {
436                let mut parallel =
437                    ProverState::<H, Shake128>::new_with_seed(&session, &0u32, [7; 32]);
438                for _ in 0..padding {
439                    parallel.public_message(&42u8);
440                }
441                assert_eq!(
442                    verifier_message_pow_parallel::<u64>(&mut parallel, FusedPowConfig::new(bits))
443                        .unwrap(),
444                    challenge
445                );
446                for _ in 0..skipped {
447                    let _ = parallel.verifier_message::<u8>();
448                }
449                assert_eq!(parallel.verifier_message::<u64>(), following);
450                assert_eq!(parallel.into_narg_string(), proof);
451            });
452        }
453    }
454
455    #[test]
456    fn verifier_message_pow_accepts_only_canonical_nonces_in_range() {
457        // The recording sponge squeezes zeros, so every nonce meets the
458        // target and only the encoding decides.
459        let accepted: &[(u64, u32, &[u8])] = &[
460            (0, 1, &[0]),
461            (127, 1, &[0x7f]),
462            (128, 1, &[0x80, 1]),
463            (255, 1, &[0xff, 1]),
464            (16383, 7, &[0xff, 0x7f]),
465            (16384, 8, &[0x80, 0x80, 1]),
466            (u64::from(u32::MAX), 25, &[0xff, 0xff, 0xff, 0xff, 0x0f]),
467            (1u64 << 32, 26, &[0x80, 0x80, 0x80, 0x80, 0x10]),
468            (
469                (1u64 << 63) - 1,
470                56,
471                &[0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f],
472            ),
473            (
474                1u64 << 63,
475                57,
476                &[0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 1],
477            ),
478            (
479                u64::MAX,
480                57,
481                &[0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 1],
482            ),
483        ];
484        for &(nonce, bits, proof) in accepted {
485            assert_eq!(leb128(nonce), proof);
486            let mut verifier = recording_verifier(proof);
487            assert!(
488                verifier
489                    .verifier_message_pow::<u64>(FusedPowConfig::new(bits))
490                    .is_ok(),
491                "{proof:?}"
492            );
493            assert!(verifier.check_eof().is_ok());
494        }
495        // A trailing zero byte, a nonce of 2^8 at 1 bit, a continuation past
496        // the longest encoding, 2^32 at 25 bits, and an overflowing u64 nonce.
497        let rejected: &[(u32, &[u8])] = &[
498            (1, &[0x80, 0x00]),
499            (8, &[0x81, 0x80, 0x00]),
500            (1, &[0x80, 0x02]),
501            (1, &[0x80, 0x80, 0x01]),
502            (25, &[0x80, 0x80, 0x80, 0x80, 0x10]),
503            (
504                56,
505                &[0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 1],
506            ),
507            (57, &[0x80; 10]),
508            (57, &[0xff; 10]),
509            (
510                57,
511                &[0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x02],
512            ),
513        ];
514        for &(bits, proof) in rejected {
515            let mut verifier = recording_verifier(proof);
516            assert!(
517                verifier
518                    .verifier_message_pow::<u64>(FusedPowConfig::new(bits))
519                    .is_err(),
520                "{proof:?}"
521            );
522            assert!(verifier.check_eof().is_err());
523        }
524        // The largest nonce is valid at 57 bits; every proper prefix is incomplete.
525        let proof = leb128(u64::MAX);
526        for length in 0..proof.len() {
527            let mut verifier = recording_verifier(&proof[..length]);
528            assert!(verifier
529                .verifier_message_pow::<u64>(FusedPowConfig::new(57))
530                .is_err());
531            assert!(!events()
532                .iter()
533                .any(|event| matches!(event, Event::Squeeze(_))));
534            assert!(verifier.check_eof().is_err());
535        }
536    }
537
538    #[test]
539    fn acceptance_checks_exactly_the_requested_low_bits() {
540        for bits in [0, 1, 7, 8, 9, 56, 57] {
541            let config = FusedPowConfig::new(bits);
542            let len = config.challenge_len();
543            for supplied in 0..=9 {
544                assert_eq!(config.accepts(0, &[0; 9][..supplied]), supplied == len);
545            }
546            for bit in 0..64 {
547                let word = (1u64 << bit).to_le_bytes();
548                assert_eq!(
549                    config.accepts(0, &word[..len]),
550                    bit >= bits,
551                    "bits={bits}, bit={bit}"
552                );
553            }
554        }
555    }
556
557    #[test]
558    #[should_panic(expected = "bits must be at most 57")]
559    fn verifier_message_pow_rejects_unsupported_difficulty() {
560        let _ = FusedPowConfig::new(58);
561    }
562}
spongefish_pow/fused.rs

spongefish_pow/
fused.rs
