spongefish_pow/
protocol.rs

1//! An interactive proof-of-work step shared by every transcript implementation.
2
3use spongefish::{FromUniform, Transcript, VerificationError};
4
5use crate::{PoWGrinder, PowStrategy};
6
7/// Proof-of-work-protected verifier messages for interactive transcripts.
8///
9/// This extension is available on every [`Transcript`], including concrete
10/// [`ProverState`](spongefish::ProverState) and
11/// [`VerifierState`](spongefish::VerifierState) values and the generic transcript
12/// passed to [`Argument::run`](spongefish::Argument::run).
13///
14/// Both parties run the same protocol: obtain a 32-byte grinding challenge,
15/// exchange a little-endian `u64` nonce, check it, then obtain the protected
16/// verifier message. Grinding is a prover-only computation; the verifier checks
17/// the received nonce without running the search.
18///
19/// A rejected nonce fails [`Transcript::check`], permanently rejecting the
20/// verifier's transcript even if the error is caught. The protected message is
21/// produced only after a successful check. Truncated nonces fail during the
22/// prover-message read.
23///
24/// # Protocol parameters
25///
26/// The PoW strategy, difficulty, position of this step, and the codec of the
27/// protected message must be fixed by the protocol and accounted for in its
28/// session tag. The difficulty must not come from an untrusted proof value.
29/// Any soundness benefit depends on the surrounding protocol and PoW strategy.
30///
31/// # Example
32///
33/// ```
34/// # #[cfg(feature = "blake3")]
35/// # {
36/// use spongefish::{Argument, Narg, Transcript, VerificationError, Witness};
37/// use spongefish_pow::{blake3::Blake3PoW, PowTranscriptExt};
38///
39/// struct PowRound;
40/// impl Argument for PowRound {
41///     type Instance = u32;
42///     type Witness = ();
43///     type Output = u32;
44///
45///     fn run<T: Transcript>(
46///         transcript: &mut T,
47///         _instance: &u32,
48///         _witness: Witness<&()>,
49///     ) -> Result<u32, VerificationError> {
50///         transcript.verifier_message_pow::<u32, Blake3PoW>(8.0)
51///     }
52/// }
53///
54/// let tag = b"example/v1/blake3-pow-8/u32";
55/// let (proof, challenge) = Narg::prove::<PowRound>(tag, &0, &())?;
56/// let replay = Narg::verify::<PowRound>(tag, &0, &proof)?;
57/// assert_eq!(challenge, replay);
58/// # }
59/// # Ok::<(), spongefish::VerificationError>(())
60/// ```
61pub trait PowTranscriptExt: Transcript {
62    /// Obtain a verifier message after a proof-of-work step using `S`.
63    ///
64    /// Both the prover and verifier return `Result<T, VerificationError>`.
65    /// `bits` is the binary logarithm of the expected work, subject to the
66    /// chosen strategy's supported range.
67    ///
68    /// # Errors
69    ///
70    /// The prover returns [`VerificationError`] if grinding exhausts the nonce
71    /// space. The verifier returns it if the nonce is invalid, the proof is
72    /// truncated, or an earlier read or check rejected the transcript.
73    ///
74    /// # Panics
75    ///
76    /// Either side may panic if the strategy rejects an unsupported difficulty.
77    fn verifier_message_pow<T, S>(&mut self, bits: f64) -> Result<T, VerificationError>
78    where
79        T: FromUniform,
80        S: PowStrategy,
81    {
82        let challenge = self.verifier_message::<[u8; 32]>();
83        let nonce = self
84            .prover_only(|| {
85                PoWGrinder::<S>::new(challenge, bits)
86                    .grind()
87                    .map(|solution| solution.nonce)
88                    .ok_or(VerificationError)
89            })
90            .transpose()?;
91        let nonce = self.prover_message(nonce)?;
92        self.check(|| PoWGrinder::<S>::new(challenge, bits).verify(nonce))?;
93        Ok(self.verifier_message())
94    }
95}
96
97impl<T: Transcript + ?Sized> PowTranscriptExt for T {}
98
99#[cfg(test)]
100mod tests {
101    use std::cell::RefCell;
102
103    use spongefish::{
104        instantiations::{Shake128, TurboShake128},
105        Argument, DuplexSpongeInit, DuplexSpongeInterface, Narg, ProverState, Transcript,
106        VerificationError, VerifierState, Witness,
107    };
108
109    use super::PowTranscriptExt;
110    #[cfg(feature = "blake3")]
111    use crate::PoWGrinder;
112    use crate::{PoWSolution, PowStrategy};
113
114    #[cfg(any(feature = "blake3", feature = "keccak"))]
115    const BITS: f64 = 8.0;
116
117    // Use different public/private sponges to exercise the refactored RNG bound.
118    fn prover() -> ProverState<TurboShake128, Shake128> {
119        let session_id = Narg::derive_session_id(b"pow/tests/v1");
120        ProverState::new_with_seed(&session_id, &0u32, [7; 32])
121    }
122
123    #[cfg(any(feature = "blake3", feature = "keccak"))]
124    fn verifier(proof: &[u8]) -> VerifierState<'_, TurboShake128> {
125        let session_id = Narg::derive_session_id(b"pow/tests/v1");
126        VerifierState::new(&session_id, &0u32, proof)
127    }
128
129    #[cfg(any(feature = "blake3", feature = "keccak"))]
130    fn round_trip<S: PowStrategy>() {
131        let mut prover = prover();
132        prover.prover_message(&123u32);
133        let first: u64 = prover.verifier_message_pow::<u64, S>(BITS).unwrap();
134        prover.prover_message(&456u32);
135        let second: [u8; 32] = prover.verifier_message_pow::<[u8; 32], S>(BITS).unwrap();
136        let proof = prover.into_narg_string();
137        assert_eq!(proof.len(), 4 + 8 + 4 + 8);
138
139        let mut verifier = verifier(&proof);
140        assert_eq!(verifier.prover_message::<u32>().unwrap(), 123);
141        assert_eq!(
142            verifier.verifier_message_pow::<u64, S>(BITS).unwrap(),
143            first
144        );
145        assert_eq!(verifier.prover_message::<u32>().unwrap(), 456);
146        assert_eq!(
147            verifier.verifier_message_pow::<[u8; 32], S>(BITS).unwrap(),
148            second
149        );
150        assert!(verifier.check_eof().is_ok());
151    }
152
153    #[cfg(feature = "blake3")]
154    #[test]
155    fn blake3_round_trip() {
156        round_trip::<crate::blake3::Blake3PoW>();
157    }
158
159    #[cfg(feature = "keccak")]
160    #[test]
161    fn keccak_round_trip() {
162        round_trip::<crate::keccak::KeccakPoW>();
163    }
164
165    #[cfg(feature = "blake3")]
166    #[test]
167    fn argument_and_direct_state_apis_produce_the_same_proof_and_challenge() {
168        use crate::blake3::Blake3PoW;
169
170        struct PowRound;
171        impl Argument for PowRound {
172            type Instance = u32;
173            type Witness = ();
174            type Output = u64;
175
176            fn run<T: Transcript>(
177                transcript: &mut T,
178                _instance: &u32,
179                _witness: Witness<&()>,
180            ) -> Result<u64, VerificationError> {
181                transcript.verifier_message_pow::<u64, Blake3PoW>(BITS)
182            }
183        }
184
185        let tag = b"pow/tests/v1";
186        let (proof, challenge) = Narg::prove::<PowRound>(tag, &0, &()).unwrap();
187        assert_eq!(
188            Narg::verify::<PowRound>(tag, &0, &proof).unwrap(),
189            challenge
190        );
191
192        let mut direct = prover();
193        assert_eq!(
194            direct.verifier_message_pow::<u64, Blake3PoW>(BITS).unwrap(),
195            challenge
196        );
197        assert_eq!(direct.into_narg_string(), proof);
198        let mut direct = verifier(&proof);
199        assert_eq!(
200            direct.verifier_message_pow::<u64, Blake3PoW>(BITS).unwrap(),
201            challenge
202        );
203        assert!(direct.check_eof().is_ok());
204    }
205
206    #[cfg(feature = "blake3")]
207    #[test]
208    fn matches_manual_transcript_and_nonce_encoding() {
209        use crate::blake3::Blake3PoW;
210
211        let mut manual = prover();
212        let challenge = manual.verifier_message::<[u8; 32]>();
213        let solution = PoWGrinder::<Blake3PoW>::new(challenge, BITS)
214            .grind()
215            .unwrap();
216        manual.prover_message(&solution.nonce);
217        let expected = manual.verifier_message::<u64>();
218
219        let mut bundled = prover();
220        assert_eq!(
221            bundled
222                .verifier_message_pow::<u64, Blake3PoW>(BITS)
223                .unwrap(),
224            expected
225        );
226        assert_eq!(bundled.into_narg_string(), solution.nonce.to_le_bytes());
227        assert_eq!(manual.into_narg_string(), solution.nonce.to_le_bytes());
228    }
229
230    #[cfg(feature = "blake3")]
231    #[test]
232    fn rejects_a_nonce_that_only_meets_the_lower_difficulty() {
233        use crate::blake3::Blake3PoW;
234
235        let challenge = verifier(&[]).verifier_message::<[u8; 32]>();
236        let mut easy = PoWGrinder::<Blake3PoW>::new(challenge, BITS);
237        let mut hard = PoWGrinder::<Blake3PoW>::new(challenge, BITS + 8.0);
238        // Explicitly choose a nonce that fails the harder predicate; a valid
239        // low-difficulty nonce can also satisfy a higher difficulty.
240        let nonce = (0..=u64::MAX)
241            .find(|&n| easy.verify(n) && !hard.verify(n))
242            .unwrap();
243        let proof = nonce.to_le_bytes();
244        let mut easy_verifier = verifier(&proof);
245        assert!(easy_verifier
246            .verifier_message_pow::<u64, Blake3PoW>(BITS)
247            .is_ok());
248        assert!(easy_verifier.check_eof().is_ok());
249
250        let mut hard_verifier = verifier(&proof);
251        assert!(hard_verifier
252            .verifier_message_pow::<u64, Blake3PoW>(BITS + 8.0)
253            .is_err());
254        assert!(hard_verifier.prover_messages_vec::<u8>(0).is_err());
255        assert!(hard_verifier.check_eof().is_err());
256    }
257
258    #[derive(Clone, Debug, PartialEq, Eq)]
259    enum Event {
260        Absorb(Vec<u8>),
261        Squeeze(usize),
262    }
263
264    thread_local! {
265        static EVENTS: RefCell<Vec<Event>> = const { RefCell::new(Vec::new()) };
266    }
267
268    fn events() -> Vec<Event> {
269        EVENTS.with_borrow(Clone::clone)
270    }
271
272    #[derive(Clone)]
273    struct RecordingSponge;
274
275    impl DuplexSpongeInterface for RecordingSponge {
276        type U = u8;
277
278        fn absorb(&mut self, input: &[u8]) -> &mut Self {
279            EVENTS.with_borrow_mut(|events| events.push(Event::Absorb(input.to_vec())));
280            self
281        }
282
283        fn squeeze(&mut self, output: &mut [u8]) -> &mut Self {
284            EVENTS.with_borrow_mut(|events| events.push(Event::Squeeze(output.len())));
285            output.fill(0);
286            self
287        }
288    }
289
290    impl DuplexSpongeInit for RecordingSponge {
291        fn init(_session_id: &[u8; 32]) -> Self {
292            Self
293        }
294    }
295
296    /// A verifier over [`RecordingSponge`], with the log cleared after the
297    /// instance is absorbed.
298    fn recording_verifier(proof: &[u8]) -> VerifierState<'_, RecordingSponge> {
299        let session_id = Narg::derive_session_id(b"pow/tests/v1");
300        let verifier = VerifierState::new(&session_id, &0u32, proof);
301        EVENTS.with_borrow_mut(Vec::clear);
302        verifier
303    }
304
305    #[derive(Clone)]
306    struct FixedPredicate<const ACCEPT: bool>;
307
308    impl<const ACCEPT: bool> PowStrategy for FixedPredicate<ACCEPT> {
309        fn new(_challenge: [u8; 32], _bits: f64) -> Self {
310            Self
311        }
312
313        fn check(&mut self, _nonce: u64) -> bool {
314            ACCEPT
315        }
316
317        fn solution(&self, nonce: u64) -> PoWSolution {
318            PoWSolution {
319                challenge: [0; 32],
320                nonce,
321            }
322        }
323
324        fn solve(&mut self) -> Option<PoWSolution> {
325            assert!(!ACCEPT, "verifier must not run the nonce search");
326            None
327        }
328    }
329
330    #[test]
331    fn exhausted_grinding_returns_an_error_without_sending_a_nonce() {
332        let mut prover = prover();
333        assert!(prover
334            .verifier_message_pow::<u64, FixedPredicate<false>>(8.0)
335            .is_err());
336        assert_eq!(prover.into_narg_string(), []);
337    }
338
339    #[test]
340    fn argument_cannot_accept_a_caught_pow_failure() {
341        struct SwallowsFailure;
342        impl Argument for SwallowsFailure {
343            type Instance = u32;
344            type Witness = ();
345            type Output = ();
346
347            fn run<T: Transcript>(
348                transcript: &mut T,
349                _instance: &u32,
350                _witness: Witness<&()>,
351            ) -> Result<(), VerificationError> {
352                let _ = transcript.verifier_message_pow::<u64, FixedPredicate<false>>(8.0);
353                Ok(())
354            }
355        }
356        assert!(Narg::verify::<SwallowsFailure>(b"caught PoW failure", &0, &[0; 8]).is_err());
357    }
358
359    #[test]
360    fn rejected_nonce_produces_no_challenge_and_poisoning_survives_caught_errors() {
361        let mut verifier = recording_verifier(&[0; 8]);
362        assert!(verifier
363            .verifier_message_pow::<u64, FixedPredicate<false>>(8.0)
364            .is_err());
365        // The nonce is an ordinary prover message. Its failed check prevents
366        // the protected challenge, even though all proof bytes were consumed.
367        assert_eq!(events(), [Event::Squeeze(32), Event::Absorb(vec![0; 8])]);
368        assert!(verifier
369            .check(|| panic!("a failed check must not run again"))
370            .is_err());
371        assert!(verifier.prover_message::<u8>().is_err());
372        assert!(verifier.prover_messages_vec::<u8>(0).is_err());
373        assert!(verifier
374            .verifier_message_pow::<u64, FixedPredicate<false>>(8.0)
375            .is_err());
376        assert!(verifier.check_eof().is_err());
377    }
378
379    #[test]
380    fn valid_nonce_is_absorbed_before_the_protected_challenge() {
381        let proof = 42u64.to_le_bytes();
382        let mut verifier = recording_verifier(&proof);
383        assert_eq!(
384            verifier
385                .verifier_message_pow::<u64, FixedPredicate<true>>(8.0)
386                .unwrap(),
387            0
388        );
389        assert_eq!(
390            events(),
391            [
392                Event::Squeeze(32),
393                Event::Absorb(proof.to_vec()),
394                Event::Squeeze(8)
395            ]
396        );
397        assert!(verifier.check_eof().is_ok());
398    }
399
400    #[test]
401    fn every_truncated_nonce_is_rejected() {
402        for length in 0..8 {
403            let proof = vec![0; length];
404            let mut verifier = recording_verifier(&proof);
405            // Even an always-accepting predicate cannot rescue a short nonce.
406            assert!(verifier
407                .verifier_message_pow::<u64, FixedPredicate<true>>(8.0)
408                .is_err());
409            assert_eq!(events(), [Event::Squeeze(32)]);
410            assert!(verifier.check_eof().is_err());
411        }
412    }
413}
spongefish_pow/protocol.rs

spongefish_pow/
protocol.rs
