penumbra_sdk_shielded_pool/
nullifier_derivation.rs

1use base64::prelude::*;
2use std::str::FromStr;
3
4use anyhow::Result;
5use ark_r1cs_std::prelude::*;
6use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
7use decaf377::{Bls12_377, Fq};
8
9use ark_ff::ToConstraintField;
10use ark_groth16::{
11    r1cs_to_qap::LibsnarkReduction, Groth16, PreparedVerifyingKey, Proof, ProvingKey,
12};
13use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef};
14use ark_snark::SNARK;
15use penumbra_sdk_proto::{penumbra::core::component::shielded_pool::v1 as pb, DomainType};
16use penumbra_sdk_tct as tct;
17use rand::{CryptoRng, Rng};
18use tct::StateCommitment;
19
20use crate::{Note, Rseed};
21use penumbra_sdk_asset::Value;
22use penumbra_sdk_keys::keys::{Bip44Path, NullifierKey, NullifierKeyVar, SeedPhrase, SpendKey};
23use penumbra_sdk_proof_params::{DummyWitness, VerifyingKeyExt, GROTH16_PROOF_LENGTH_BYTES};
24use penumbra_sdk_sct::{Nullifier, NullifierVar};
25
26/// The public input for a ['NullifierDerivationProof'].
27#[derive(Clone, Debug)]
28pub struct NullifierDerivationProofPublic {
29    /// The position of the spent note.
30    pub position: tct::Position,
31    /// A commitment to the spent note.
32    pub note_commitment: StateCommitment,
33    /// nullifier of the spent note.
34    pub nullifier: Nullifier,
35}
36
37/// The private input for a ['NullifierDerivationProof'].
38#[derive(Clone, Debug)]
39pub struct NullifierDerivationProofPrivate {
40    /// The nullifier deriving key.
41    pub nk: NullifierKey,
42}
43
44#[cfg(test)]
45fn check_satisfaction(
46    public: &NullifierDerivationProofPublic,
47    private: &NullifierDerivationProofPrivate,
48) -> Result<()> {
49    let nullifier = Nullifier::derive(&private.nk, public.position, &public.note_commitment);
50    if nullifier != public.nullifier {
51        anyhow::bail!("nullifier did not match public input");
52    }
53    Ok(())
54}
55
56#[cfg(test)]
57fn check_circuit_satisfaction(
58    public: NullifierDerivationProofPublic,
59    private: NullifierDerivationProofPrivate,
60) -> Result<()> {
61    use ark_relations::r1cs::{self, ConstraintSystem};
62
63    let cs = ConstraintSystem::new_ref();
64    let circuit = NullifierDerivationCircuit { public, private };
65    cs.set_optimization_goal(r1cs::OptimizationGoal::Constraints);
66    circuit
67        .generate_constraints(cs.clone())
68        .expect("can generate constraints from circuit");
69    cs.finalize();
70    if !cs.is_satisfied()? {
71        anyhow::bail!("constraints are not satisfied");
72    }
73    Ok(())
74}
75
76/// Groth16 proof for correct nullifier derivation.
77///
78/// # Safety
79///
80/// This proof is only for client-side use and not on chain. The nullifier-deriving
81/// key is not linked in the circuit to the address associated with the note commitment.
82#[derive(Clone, Debug)]
83pub struct NullifierDerivationCircuit {
84    public: NullifierDerivationProofPublic,
85    private: NullifierDerivationProofPrivate,
86}
87
88impl ConstraintSynthesizer<Fq> for NullifierDerivationCircuit {
89    fn generate_constraints(self, cs: ConstraintSystemRef<Fq>) -> ark_relations::r1cs::Result<()> {
90        // Witnesses
91        let nk_var = NullifierKeyVar::new_witness(cs.clone(), || Ok(self.private.nk))?;
92
93        // Public inputs
94        let claimed_nullifier_var =
95            NullifierVar::new_input(cs.clone(), || Ok(self.public.nullifier))?;
96        let note_commitment_var = tct::r1cs::StateCommitmentVar::new_input(cs.clone(), || {
97            Ok(self.public.note_commitment)
98        })?;
99        let position_var = tct::r1cs::PositionVar::new_input(cs, || Ok(self.public.position))?;
100
101        // Nullifier integrity.
102        let nullifier_var = NullifierVar::derive(&nk_var, &position_var, &note_commitment_var)?;
103        nullifier_var.conditional_enforce_equal(&claimed_nullifier_var, &Boolean::TRUE)?;
104
105        Ok(())
106    }
107}
108
109impl DummyWitness for NullifierDerivationCircuit {
110    fn with_dummy_witness() -> Self {
111        let seed_phrase = SeedPhrase::from_randomness(&[b'f'; 32]);
112        let sk_sender = SpendKey::from_seed_phrase_bip44(seed_phrase, &Bip44Path::new(0));
113        let fvk_sender = sk_sender.full_viewing_key();
114        let ivk_sender = fvk_sender.incoming();
115        let (address, _dtk_d) = ivk_sender.payment_address(0u32.into());
116
117        let nk = *sk_sender.nullifier_key();
118        let note = Note::from_parts(
119            address,
120            Value::from_str("1upenumbra").expect("valid value"),
121            Rseed([1u8; 32]),
122        )
123        .expect("can make a note");
124        let nullifier = Nullifier(Fq::from(1u64));
125        let mut sct = tct::Tree::new();
126        let note_commitment = note.commit();
127        sct.insert(tct::Witness::Keep, note_commitment)
128            .expect("able to insert note commitment into SCT");
129        let state_commitment_proof = sct
130            .witness(note_commitment)
131            .expect("able to witness just-inserted note commitment");
132        let position = state_commitment_proof.position();
133
134        let public = NullifierDerivationProofPublic {
135            position,
136            note_commitment,
137            nullifier,
138        };
139        let private = NullifierDerivationProofPrivate { nk };
140
141        Self { public, private }
142    }
143}
144
145#[derive(Clone, Debug)]
146pub struct NullifierDerivationProof([u8; GROTH16_PROOF_LENGTH_BYTES]);
147
148impl NullifierDerivationProof {
149    pub fn prove<R: CryptoRng + Rng>(
150        rng: &mut R,
151        pk: &ProvingKey<Bls12_377>,
152        public: NullifierDerivationProofPublic,
153        private: NullifierDerivationProofPrivate,
154    ) -> anyhow::Result<Self> {
155        let circuit = NullifierDerivationCircuit { public, private };
156        let proof = Groth16::<Bls12_377, LibsnarkReduction>::prove(pk, circuit, rng)
157            .map_err(|err| anyhow::anyhow!(err))?;
158        let mut proof_bytes = [0u8; GROTH16_PROOF_LENGTH_BYTES];
159        Proof::serialize_compressed(&proof, &mut proof_bytes[..]).expect("can serialize Proof");
160        Ok(Self(proof_bytes))
161    }
162
163    /// Called to verify the proof using the provided public inputs.
164    #[tracing::instrument(level="debug", skip(self, vk), fields(self = ?BASE64_STANDARD.encode(&self.0), vk = ?vk.debug_id()))]
165    pub fn verify(
166        &self,
167        vk: &PreparedVerifyingKey<Bls12_377>,
168        public: NullifierDerivationProofPublic,
169    ) -> anyhow::Result<()> {
170        let proof =
171            Proof::deserialize_compressed_unchecked(&self.0[..]).map_err(|e| anyhow::anyhow!(e))?;
172
173        let mut public_inputs = Vec::new();
174        public_inputs.extend(
175            public
176                .nullifier
177                .0
178                .to_field_elements()
179                .ok_or_else(|| anyhow::anyhow!("could not convert nullifier to field elements"))?,
180        );
181        public_inputs.extend(
182            public
183                .note_commitment
184                .0
185                .to_field_elements()
186                .ok_or_else(|| {
187                    anyhow::anyhow!("could not convert note commitment to field elements")
188                })?,
189        );
190        public_inputs.extend(
191            public
192                .position
193                .to_field_elements()
194                .ok_or_else(|| anyhow::anyhow!("could not convert position to field elements"))?,
195        );
196
197        tracing::trace!(?public_inputs);
198        let start = std::time::Instant::now();
199        let proof_result = Groth16::<Bls12_377, LibsnarkReduction>::verify_with_processed_vk(
200            vk,
201            public_inputs.as_slice(),
202            &proof,
203        )
204        .map_err(|err| anyhow::anyhow!(err))?;
205        tracing::debug!(?proof_result, elapsed = ?start.elapsed());
206        proof_result
207            .then_some(())
208            .ok_or_else(|| anyhow::anyhow!("nullifier derivation proof did not verify"))
209    }
210}
211
212impl DomainType for NullifierDerivationProof {
213    type Proto = pb::ZkNullifierDerivationProof;
214}
215
216impl From<NullifierDerivationProof> for pb::ZkNullifierDerivationProof {
217    fn from(proof: NullifierDerivationProof) -> Self {
218        pb::ZkNullifierDerivationProof {
219            inner: proof.0.to_vec(),
220        }
221    }
222}
223
224impl TryFrom<pb::ZkNullifierDerivationProof> for NullifierDerivationProof {
225    type Error = anyhow::Error;
226
227    fn try_from(proto: pb::ZkNullifierDerivationProof) -> Result<Self, Self::Error> {
228        Ok(NullifierDerivationProof(proto.inner[..].try_into()?))
229    }
230}
231
232#[cfg(test)]
233mod tests {
234    use super::*;
235    use penumbra_sdk_asset::{asset, Value};
236    use penumbra_sdk_keys::keys::{SeedPhrase, SpendKey};
237    use penumbra_sdk_num::Amount;
238    use penumbra_sdk_sct::Nullifier;
239    use proptest::prelude::*;
240
241    use crate::Note;
242
243    prop_compose! {
244        fn arb_valid_nullifier_derivation_statement()(amount in any::<u64>(), address_index in any::<u32>(), position in any::<(u16, u16, u16)>(), asset_id64 in any::<u64>(), seed_phrase_randomness in any::<[u8; 32]>(), rseed_randomness in any::<[u8; 32]>()) -> (NullifierDerivationProofPublic, NullifierDerivationProofPrivate) {
245            let seed_phrase = SeedPhrase::from_randomness(&seed_phrase_randomness);
246            let sk_sender = SpendKey::from_seed_phrase_bip44(seed_phrase, &Bip44Path::new(0));
247            let fvk_sender = sk_sender.full_viewing_key();
248            let ivk_sender = fvk_sender.incoming();
249            let (sender, _dtk_d) = ivk_sender.payment_address(address_index.into());
250            let nk = *sk_sender.nullifier_key();
251            let note = Note::from_parts(
252                sender,
253                Value {
254                    amount: Amount::from(amount),
255                    asset_id: asset::Id(Fq::from(asset_id64)),
256                },
257                Rseed(rseed_randomness),
258            ).expect("should be able to create note");
259            let nullifier = Nullifier::derive(&nk, position.into(), &note.commit());
260            let public = NullifierDerivationProofPublic {
261                position: position.into(),
262                note_commitment: note.commit(),
263                nullifier
264            };
265            let private = NullifierDerivationProofPrivate {
266                nk,
267            };
268            (public, private)
269        }
270    }
271
272    prop_compose! {
273        // An invalid nullifier derivation statement is derived here by
274        // adding a random value to the nullifier key. The circuit should
275        // be unsatisfiable if the witnessed nullifier key is incorrect, i.e.
276        // does not match the nullifier key used to derive the nullifier.
277        fn arb_invalid_nullifier_derivation_statement()(amount in any::<u64>(), address_index in any::<u32>(), position in any::<(u16, u16, u16)>(), invalid_nk_randomness in any::<[u8; 32]>(), asset_id64 in any::<u64>(), seed_phrase_randomness in any::<[u8; 32]>(), rseed_randomness in any::<[u8; 32]>()) -> (NullifierDerivationProofPublic, NullifierDerivationProofPrivate) {
278            let seed_phrase = SeedPhrase::from_randomness(&seed_phrase_randomness);
279            let sk_sender = SpendKey::from_seed_phrase_bip44(seed_phrase, &Bip44Path::new(0));
280            let fvk_sender = sk_sender.full_viewing_key();
281            let ivk_sender = fvk_sender.incoming();
282            let (sender, _dtk_d) = ivk_sender.payment_address(address_index.into());
283            let nk = *sk_sender.nullifier_key();
284            let incorrect_nk = NullifierKey(nk.0 + Fq::from_le_bytes_mod_order(&invalid_nk_randomness));
285            let note = Note::from_parts(
286                sender,
287                Value {
288                    amount: Amount::from(amount),
289                    asset_id: asset::Id(Fq::from(asset_id64)),
290                },
291                Rseed(rseed_randomness),
292            ).expect("should be able to create note");
293            let nullifier = Nullifier::derive(&nk, position.into(), &note.commit());
294
295            let public = NullifierDerivationProofPublic {
296                position: position.into(),
297                note_commitment: note.commit(),
298                nullifier
299            };
300            let private = NullifierDerivationProofPrivate {
301                nk: incorrect_nk,
302            };
303            (public, private)
304        }
305    }
306
307    proptest! {
308        #[test]
309        fn nullifier_derivation_proof_happy_path((public, private) in arb_valid_nullifier_derivation_statement()) {
310            assert!(check_satisfaction(&public, &private).is_ok());
311            assert!(check_circuit_satisfaction(public, private).is_ok());
312        }
313    }
314
315    proptest! {
316        #[test]
317        fn nullifier_derivation_proof_unhappy_path((public, private) in arb_invalid_nullifier_derivation_statement()) {
318            assert!(check_satisfaction(&public, &private).is_err());
319            assert!(check_circuit_satisfaction(public, private).is_err());
320        }
321    }
322}
penumbra_sdk_shielded_pool/nullifier_derivation.rs

penumbra_sdk_shielded_pool/
nullifier_derivation.rs
