spongefish_pow/
lib.rs

1pub mod blake3;
2pub mod keccak;
3
4use spongefish::{
5    ByteDomainSeparator, BytesToUnitDeserialize, BytesToUnitSerialize, DuplexSpongeInterface,
6    ProofError, ProofResult, ProverState, Unit, UnitToBytes, VerifierState,
7};
8
9/// [`spongefish::DomainSeparator`] for proof-of-work challenges.
10pub trait PoWDomainSeparator {
11    /// Adds a [`PoWChallenge`] to the [`spongefish::DomainSeparator`].
12    ///
13    /// In order to squeeze a proof-of-work challenge, we extract a 32-byte challenge using
14    /// the byte interface, and then we find a 16-byte nonce that satisfies the proof-of-work.
15    /// The nonce a 64-bit integer encoded as an unsigned integer and written in big-endian and added
16    /// to the protocol transcript as the nonce for the proof-of-work.
17    ///
18    /// The number of bits used for the proof of work are **not** encoded within the [`spongefish::DomainSeparator`].
19    /// It is up to the implementor to change the domain separator or the label in order to reflect changes in the proof
20    /// in order to preserve simulation extractability.
21    #[must_use]
22    fn challenge_pow(self, label: &str) -> Self;
23}
24
25impl<DomainSeparator> PoWDomainSeparator for DomainSeparator
26where
27    DomainSeparator: ByteDomainSeparator,
28{
29    fn challenge_pow(self, label: &str) -> Self {
30        // 16 bytes challenge and 16 bytes nonce (that will be written)
31        self.challenge_bytes(32, label).add_bytes(8, "pow-nonce")
32    }
33}
34
35pub trait PoWChallenge {
36    /// Extension trait for generating a proof-of-work challenge.
37    fn challenge_pow<S: PowStrategy>(&mut self, bits: f64) -> ProofResult<()>;
38}
39
40impl<H, U, R> PoWChallenge for ProverState<H, U, R>
41where
42    U: Unit,
43    H: DuplexSpongeInterface<U>,
44    R: rand::CryptoRng + rand::RngCore,
45    Self: BytesToUnitSerialize + UnitToBytes,
46{
47    fn challenge_pow<S: PowStrategy>(&mut self, bits: f64) -> ProofResult<()> {
48        let challenge = self.challenge_bytes()?;
49        let nonce = S::new(challenge, bits)
50            .solve()
51            .ok_or(ProofError::InvalidProof)?;
52        self.add_bytes(&nonce.to_be_bytes())?;
53        Ok(())
54    }
55}
56
57impl<H, U> PoWChallenge for VerifierState<'_, H, U>
58where
59    U: Unit,
60    H: DuplexSpongeInterface<U>,
61    Self: BytesToUnitDeserialize + UnitToBytes,
62{
63    fn challenge_pow<S: PowStrategy>(&mut self, bits: f64) -> ProofResult<()> {
64        let challenge = self.challenge_bytes()?;
65        let nonce = u64::from_be_bytes(self.next_bytes()?);
66        if S::new(challenge, bits).check(nonce) {
67            Ok(())
68        } else {
69            Err(ProofError::InvalidProof)
70        }
71    }
72}
73
74pub trait PowStrategy: Clone + Sync {
75    /// Creates a new proof-of-work challenge.
76    /// The `challenge` is a 32-byte array that represents the challenge.
77    /// The `bits` is the binary logarithm of the expected amount of work.
78    /// When `bits` is large (i.e. close to 64), a valid solution may not be found.
79    fn new(challenge: [u8; 32], bits: f64) -> Self;
80
81    /// Check if the `nonce` satisfies the challenge.
82    fn check(&mut self, nonce: u64) -> bool;
83
84    /// Finds the minimal `nonce` that satisfies the challenge.
85    #[cfg(not(feature = "parallel"))]
86    fn solve(&mut self) -> Option<u64> {
87        // TODO: Parallel default impl
88        (0..=u64::MAX).find(|&nonce| self.check(nonce))
89    }
90
91    #[cfg(feature = "parallel")]
92    fn solve(&mut self) -> Option<u64> {
93        // Split the work across all available threads.
94        // Use atomics to find the unique deterministic lowest satisfying nonce.
95
96        use std::sync::atomic::{AtomicU64, Ordering};
97
98        use rayon::broadcast;
99        let global_min = AtomicU64::new(u64::MAX);
100        let _ = broadcast(|ctx| {
101            let mut worker = self.clone();
102            let nonces = (ctx.index() as u64..).step_by(ctx.num_threads());
103            for nonce in nonces {
104                // Use relaxed ordering to eventually get notified of another thread's solution.
105                // (Propagation delay should be in the order of tens of nanoseconds.)
106                if nonce >= global_min.load(Ordering::Relaxed) {
107                    break;
108                }
109                if worker.check(nonce) {
110                    // We found a solution, store it in the global_min.
111                    // Use fetch_min to solve race condition with simultaneous solutions.
112                    global_min.fetch_min(nonce, Ordering::SeqCst);
113                    break;
114                }
115            }
116        });
117        match global_min.load(Ordering::SeqCst) {
118            u64::MAX => self.check(u64::MAX).then_some(u64::MAX),
119            nonce => Some(nonce),
120        }
121    }
122}
spongefish_pow/lib.rs

spongefish_pow/
lib.rs
