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, rc::Rc};
102
103    use spongefish::{
104        instantiations::{Shake128, TurboShake128},
105        Argument, DuplexSpongeInterface, Narg, ProverState, Transcript, VerificationError,
106        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    #[derive(Clone)]
265    struct RecordingSponge(Rc<RefCell<Vec<Event>>>);
266
267    impl DuplexSpongeInterface for RecordingSponge {
268        type U = u8;
269
270        fn absorb(&mut self, input: &[u8]) -> &mut Self {
271            self.0.borrow_mut().push(Event::Absorb(input.to_vec()));
272            self
273        }
274
275        fn squeeze(&mut self, output: &mut [u8]) -> &mut Self {
276            self.0.borrow_mut().push(Event::Squeeze(output.len()));
277            output.fill(0);
278            self
279        }
280    }
281
282    #[derive(Clone)]
283    struct FixedPredicate<const ACCEPT: bool>;
284
285    impl<const ACCEPT: bool> PowStrategy for FixedPredicate<ACCEPT> {
286        fn new(_challenge: [u8; 32], _bits: f64) -> Self {
287            Self
288        }
289
290        fn check(&mut self, _nonce: u64) -> bool {
291            ACCEPT
292        }
293
294        fn solution(&self, nonce: u64) -> PoWSolution {
295            PoWSolution {
296                challenge: [0; 32],
297                nonce,
298            }
299        }
300
301        fn solve(&mut self) -> Option<PoWSolution> {
302            assert!(!ACCEPT, "verifier must not run the nonce search");
303            None
304        }
305    }
306
307    #[test]
308    fn exhausted_grinding_returns_an_error_without_sending_a_nonce() {
309        let mut prover = prover();
310        assert!(prover
311            .verifier_message_pow::<u64, FixedPredicate<false>>(8.0)
312            .is_err());
313        assert_eq!(prover.into_narg_string(), []);
314    }
315
316    #[test]
317    fn argument_cannot_accept_a_caught_pow_failure() {
318        struct SwallowsFailure;
319        impl Argument for SwallowsFailure {
320            type Instance = u32;
321            type Witness = ();
322            type Output = ();
323
324            fn run<T: Transcript>(
325                transcript: &mut T,
326                _instance: &u32,
327                _witness: Witness<&()>,
328            ) -> Result<(), VerificationError> {
329                let _ = transcript.verifier_message_pow::<u64, FixedPredicate<false>>(8.0);
330                Ok(())
331            }
332        }
333        assert!(Narg::verify::<SwallowsFailure>(b"caught PoW failure", &0, &[0; 8]).is_err());
334    }
335
336    #[test]
337    fn rejected_nonce_produces_no_challenge_and_poisoning_survives_caught_errors() {
338        let events = Rc::new(RefCell::new(Vec::new()));
339        let mut verifier = VerifierState::from_parts(RecordingSponge(events.clone()), &[0; 8]);
340        assert!(verifier
341            .verifier_message_pow::<u64, FixedPredicate<false>>(8.0)
342            .is_err());
343        // The nonce is an ordinary prover message. Its failed check prevents
344        // the protected challenge, even though all proof bytes were consumed.
345        assert_eq!(
346            *events.borrow(),
347            [Event::Squeeze(32), Event::Absorb(vec![0; 8])]
348        );
349        assert!(verifier
350            .check(|| panic!("a failed check must not run again"))
351            .is_err());
352        assert!(verifier.prover_message::<u8>().is_err());
353        assert!(verifier.prover_messages_vec::<u8>(0).is_err());
354        assert!(verifier
355            .verifier_message_pow::<u64, FixedPredicate<false>>(8.0)
356            .is_err());
357        assert!(verifier.check_eof().is_err());
358    }
359
360    #[test]
361    fn valid_nonce_is_absorbed_before_the_protected_challenge() {
362        let events = Rc::new(RefCell::new(Vec::new()));
363        let proof = 42u64.to_le_bytes();
364        let mut verifier = VerifierState::from_parts(RecordingSponge(events.clone()), &proof);
365        assert_eq!(
366            verifier
367                .verifier_message_pow::<u64, FixedPredicate<true>>(8.0)
368                .unwrap(),
369            0
370        );
371        assert_eq!(
372            *events.borrow(),
373            [
374                Event::Squeeze(32),
375                Event::Absorb(proof.to_vec()),
376                Event::Squeeze(8)
377            ]
378        );
379        assert!(verifier.check_eof().is_ok());
380    }
381
382    #[test]
383    fn every_truncated_nonce_is_rejected() {
384        for length in 0..8 {
385            let events = Rc::new(RefCell::new(Vec::new()));
386            let proof = vec![0; length];
387            let mut verifier = VerifierState::from_parts(RecordingSponge(events.clone()), &proof);
388            // Even an always-accepting predicate cannot rescue a short nonce.
389            assert!(verifier
390                .verifier_message_pow::<u64, FixedPredicate<true>>(8.0)
391                .is_err());
392            assert_eq!(*events.borrow(), [Event::Squeeze(32)]);
393            assert!(verifier.check_eof().is_err());
394        }
395    }
396}
spongefish_pow/protocol.rs

spongefish_pow/
protocol.rs
