1use anyhow::Result;
2use ark_ff::ToConstraintField;
3use ark_groth16::{
4 r1cs_to_qap::LibsnarkReduction, Groth16, PreparedVerifyingKey, Proof, ProvingKey,
5};
6use ark_r1cs_std::{prelude::*, uint8::UInt8};
7use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef};
8use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
9use ark_snark::SNARK;
10use base64::{engine::general_purpose, Engine as _};
11use decaf377::{r1cs::FqVar, Bls12_377, Fq, Fr};
12use decaf377_rdsa::{SpendAuth, VerificationKey};
13use penumbra_sdk_asset::{
14 balance::{self, commitment::BalanceCommitmentVar, Commitment},
15 Value,
16};
17use penumbra_sdk_keys::keys::{
18 AuthorizationKeyVar, Bip44Path, IncomingViewingKeyVar, NullifierKey, NullifierKeyVar,
19 RandomizedVerificationKey, SeedPhrase, SpendAuthRandomizerVar, SpendKey,
20};
21use penumbra_sdk_proof_params::{DummyWitness, VerifyingKeyExt, GROTH16_PROOF_LENGTH_BYTES};
22use penumbra_sdk_proto::{core::component::governance::v1 as pb, DomainType};
23use penumbra_sdk_sct::{Nullifier, NullifierVar};
24use penumbra_sdk_shielded_pool::{note, Note, Rseed};
25use penumbra_sdk_tct::{
26 self as tct,
27 r1cs::{PositionVar, StateCommitmentVar},
28 Root,
29};
30use std::str::FromStr;
31use tap::Tap;
32
33#[derive(Clone, Debug)]
35pub struct DelegatorVoteProofPublic {
36 pub anchor: tct::Root,
38 pub balance_commitment: balance::Commitment,
40 pub nullifier: Nullifier,
42 pub rk: VerificationKey<SpendAuth>,
44 pub start_position: tct::Position,
46}
47
48#[derive(Clone, Debug)]
50pub struct DelegatorVoteProofPrivate {
51 pub state_commitment_proof: tct::Proof,
53 pub note: Note,
55 pub v_blinding: Fr,
57 pub spend_auth_randomizer: Fr,
59 pub ak: VerificationKey<SpendAuth>,
61 pub nk: NullifierKey,
63}
64
65#[cfg(test)]
66fn check_satisfaction(
67 public: &DelegatorVoteProofPublic,
68 private: &DelegatorVoteProofPrivate,
69) -> Result<()> {
70 use penumbra_sdk_keys::keys::FullViewingKey;
71
72 let note_commitment = private.note.commit();
73 if note_commitment != private.state_commitment_proof.commitment() {
74 anyhow::bail!("note commitment did not match state commitment proof");
75 }
76
77 let nullifier = Nullifier::derive(
78 &private.nk,
79 private.state_commitment_proof.position(),
80 ¬e_commitment,
81 );
82 if nullifier != public.nullifier {
83 anyhow::bail!("nullifier did not match public input");
84 }
85
86 private.state_commitment_proof.verify(public.anchor)?;
87
88 let rk = private.ak.randomize(&private.spend_auth_randomizer);
89 if rk != public.rk {
90 anyhow::bail!("randomized spend auth key did not match public input");
91 }
92
93 let fvk = FullViewingKey::from_components(private.ak, private.nk);
94 let ivk = fvk.incoming();
95 let transmission_key = ivk.diversified_public(&private.note.diversified_generator());
96 if transmission_key != *private.note.transmission_key() {
97 anyhow::bail!("transmission key did not match note");
98 }
99
100 let balance_commitment = private.note.value().commit(private.v_blinding);
101 if balance_commitment != public.balance_commitment {
102 anyhow::bail!("balance commitment did not match public input");
103 }
104
105 if private.note.diversified_generator() == decaf377::Element::default() {
106 anyhow::bail!("diversified generator is identity");
107 }
108 if private.ak.is_identity() {
109 anyhow::bail!("ak is identity");
110 }
111
112 if public.start_position.commitment() != 0 {
113 anyhow::bail!("start position commitment index is not zero");
114 }
115
116 if private.state_commitment_proof.position() >= public.start_position {
117 anyhow::bail!("note did not exist prior to the start of voting");
118 }
119
120 Ok(())
121}
122
123#[cfg(test)]
124fn check_circuit_satisfaction(
125 public: DelegatorVoteProofPublic,
126 private: DelegatorVoteProofPrivate,
127) -> Result<()> {
128 use ark_relations::r1cs::{self, ConstraintSystem};
129
130 let cs = ConstraintSystem::new_ref();
131 let circuit = DelegatorVoteCircuit { public, private };
132 cs.set_optimization_goal(r1cs::OptimizationGoal::Constraints);
133 circuit
134 .generate_constraints(cs.clone())
135 .expect("can generate constraints from circuit");
136 cs.finalize();
137 if !cs.is_satisfied()? {
138 anyhow::bail!("constraints are not satisfied");
139 }
140 Ok(())
141}
142
143#[derive(Clone, Debug)]
145pub struct DelegatorVoteCircuit {
146 public: DelegatorVoteProofPublic,
147 private: DelegatorVoteProofPrivate,
148}
149
150impl ConstraintSynthesizer<Fq> for DelegatorVoteCircuit {
151 fn generate_constraints(self, cs: ConstraintSystemRef<Fq>) -> ark_relations::r1cs::Result<()> {
152 let note_var = note::NoteVar::new_witness(cs.clone(), || Ok(self.private.note.clone()))?;
155 let claimed_note_commitment = StateCommitmentVar::new_witness(cs.clone(), || {
156 Ok(self.private.state_commitment_proof.commitment())
157 })?;
158
159 let delegator_position_var = tct::r1cs::PositionVar::new_witness(cs.clone(), || {
160 Ok(self.private.state_commitment_proof.position())
161 })?;
162 let delegator_position_bits = delegator_position_var.to_bits_le()?;
163 let merkle_path_var = tct::r1cs::MerkleAuthPathVar::new_witness(cs.clone(), || {
164 Ok(self.private.state_commitment_proof)
165 })?;
166
167 let v_blinding_arr: [u8; 32] = self.private.v_blinding.to_bytes();
168 let v_blinding_vars = UInt8::new_witness_vec(cs.clone(), &v_blinding_arr)?;
169
170 let spend_auth_randomizer_var = SpendAuthRandomizerVar::new_witness(cs.clone(), || {
171 Ok(self.private.spend_auth_randomizer)
172 })?;
173 let ak_element_var: AuthorizationKeyVar =
175 AuthorizationKeyVar::new_witness(cs.clone(), || Ok(self.private.ak))?;
176 let nk_var = NullifierKeyVar::new_witness(cs.clone(), || Ok(self.private.nk))?;
177
178 let anchor_var = FqVar::new_input(cs.clone(), || Ok(Fq::from(self.public.anchor)))?;
180 let claimed_balance_commitment_var =
181 BalanceCommitmentVar::new_input(cs.clone(), || Ok(self.public.balance_commitment))?;
182 let claimed_nullifier_var =
183 NullifierVar::new_input(cs.clone(), || Ok(self.public.nullifier))?;
184 let rk_var = RandomizedVerificationKey::new_input(cs.clone(), || Ok(self.public.rk))?;
185 let start_position = PositionVar::new_input(cs.clone(), || Ok(self.public.start_position))?;
186
187 let note_commitment_var = note_var.commit()?;
189 note_commitment_var.enforce_equal(&claimed_note_commitment)?;
190
191 let nullifier_var =
193 NullifierVar::derive(&nk_var, &delegator_position_var, &claimed_note_commitment)?;
194 nullifier_var.enforce_equal(&claimed_nullifier_var)?;
195
196 merkle_path_var.verify(
198 cs.clone(),
199 &Boolean::TRUE,
200 &delegator_position_bits,
201 anchor_var,
202 claimed_note_commitment.inner(),
203 )?;
204
205 let computed_rk_var = ak_element_var.randomize(&spend_auth_randomizer_var)?;
207 computed_rk_var.enforce_equal(&rk_var)?;
208
209 let ivk = IncomingViewingKeyVar::derive(&nk_var, &ak_element_var)?;
211 let computed_transmission_key =
212 ivk.diversified_public(¬e_var.diversified_generator())?;
213 computed_transmission_key.enforce_equal(¬e_var.transmission_key())?;
214
215 let balance_commitment = note_var.value().commit(v_blinding_vars)?;
217 balance_commitment.enforce_equal(&claimed_balance_commitment_var)?;
218
219 let zero_constant = FqVar::constant(Fq::from(0u64));
222 let commitment = start_position.commitment()?;
223 commitment.enforce_equal(&zero_constant)?;
224
225 delegator_position_var.position.enforce_cmp(
235 &start_position.position,
236 core::cmp::Ordering::Less,
237 false,
238 )?;
239
240 Ok(())
241 }
242}
243
244impl DummyWitness for DelegatorVoteCircuit {
245 fn with_dummy_witness() -> Self {
246 let seed_phrase = SeedPhrase::from_randomness(&[b'f'; 32]);
247 let sk_sender = SpendKey::from_seed_phrase_bip44(seed_phrase, &Bip44Path::new(0));
248 let fvk_sender = sk_sender.full_viewing_key();
249 let ivk_sender = fvk_sender.incoming();
250 let (address, _dtk_d) = ivk_sender.payment_address(0u32.into());
251
252 let spend_auth_randomizer = Fr::from(1u64);
253 let rsk = sk_sender.spend_auth_key().randomize(&spend_auth_randomizer);
254 let nk = *sk_sender.nullifier_key();
255 let ak = sk_sender.spend_auth_key().into();
256 let note = Note::from_parts(
257 address,
258 Value::from_str("1upenumbra").expect("valid value"),
259 Rseed([1u8; 32]),
260 )
261 .expect("can make a note");
262 let v_blinding = Fr::from(1u64);
263 let rk: VerificationKey<SpendAuth> = rsk.into();
264 let nullifier = Nullifier(Fq::from(1u64));
265 let mut sct = tct::Tree::new();
266 let note_commitment = note.commit();
267 sct.insert(tct::Witness::Keep, note_commitment)
268 .expect("able to insert note commitment into SCT");
269 let anchor = sct.root();
270 let state_commitment_proof = sct
271 .witness(note_commitment)
272 .expect("able to witness just-inserted note commitment");
273 let start_position = state_commitment_proof.position();
274
275 let public = DelegatorVoteProofPublic {
276 anchor,
277 balance_commitment: balance::Commitment(decaf377::Element::GENERATOR),
278 nullifier,
279 rk,
280 start_position,
281 };
282 let private = DelegatorVoteProofPrivate {
283 state_commitment_proof,
284 note,
285 v_blinding,
286 spend_auth_randomizer,
287 ak,
288 nk,
289 };
290
291 Self { public, private }
292 }
293}
294
295#[derive(Debug, thiserror::Error)]
296pub enum VerificationError {
297 #[error("error deserializing compressed proof: {0:?}")]
298 ProofDeserialize(ark_serialize::SerializationError),
299 #[error("Fq types are Bls12-377 field members")]
300 Anchor,
301 #[error("balance commitment is a Bls12-377 field member")]
302 BalanceCommitment,
303 #[error("nullifier is a Bls12-377 field member")]
304 Nullifier,
305 #[error("could not decompress element points: {0:?}")]
306 DecompressRk(decaf377::EncodingError),
307 #[error("randomized spend key is a Bls12-377 field member")]
308 Rk,
309 #[error("start position is a Bls12-377 field member")]
310 StartPosition,
311 #[error("error verifying proof: {0:?}")]
312 SynthesisError(ark_relations::r1cs::SynthesisError),
313 #[error("delegator vote proof did not verify")]
314 InvalidProof,
315}
316
317#[derive(Clone, Debug, Copy)]
318pub struct DelegatorVoteProof([u8; GROTH16_PROOF_LENGTH_BYTES]);
319
320impl DelegatorVoteProof {
321 pub fn prove(
322 blinding_r: Fq,
323 blinding_s: Fq,
324 pk: &ProvingKey<Bls12_377>,
325 public: DelegatorVoteProofPublic,
326 private: DelegatorVoteProofPrivate,
327 ) -> anyhow::Result<Self> {
328 let circuit = DelegatorVoteCircuit { public, private };
329 let proof = Groth16::<Bls12_377, LibsnarkReduction>::create_proof_with_reduction(
330 circuit, pk, blinding_r, blinding_s,
331 )
332 .map_err(|err| anyhow::anyhow!(err))?;
333 let mut proof_bytes = [0u8; GROTH16_PROOF_LENGTH_BYTES];
334 Proof::serialize_compressed(&proof, &mut proof_bytes[..]).expect("can serialize Proof");
335 Ok(Self(proof_bytes))
336 }
337
338 #[tracing::instrument(
342 level="debug",
343 skip(self, vk),
344 fields(
345 self = ?general_purpose::STANDARD.encode(self.clone().encode_to_vec()),
346 vk = ?vk.debug_id()
347 )
348 )]
349 pub fn verify(
350 &self,
351 vk: &PreparedVerifyingKey<Bls12_377>,
352 DelegatorVoteProofPublic {
353 anchor: Root(anchor),
354 balance_commitment: Commitment(balance_commitment),
355 nullifier: Nullifier(nullifier),
356 rk,
357 start_position,
358 }: DelegatorVoteProofPublic,
359 ) -> Result<(), VerificationError> {
360 let proof = Proof::deserialize_compressed_unchecked(&self.0[..])
361 .map_err(VerificationError::ProofDeserialize)?;
362 let element_rk = decaf377::Encoding(rk.to_bytes())
363 .vartime_decompress()
364 .map_err(VerificationError::DecompressRk)?;
365
366 macro_rules! to_field_elements {
368 ($fe:expr, $err:expr) => {
369 $fe.to_field_elements().ok_or($err)?
370 };
371 }
372
373 use VerificationError::*;
374 let public_inputs = [
375 to_field_elements!(Fq::from(anchor), Anchor),
376 to_field_elements!(balance_commitment, BalanceCommitment),
377 to_field_elements!(nullifier, Nullifier),
378 to_field_elements!(element_rk, Rk),
379 to_field_elements!(start_position, StartPosition),
380 ]
381 .into_iter()
382 .flatten()
383 .collect::<Vec<_>>()
384 .tap(|public_inputs| tracing::trace!(?public_inputs));
385
386 let start = std::time::Instant::now();
387 Groth16::<Bls12_377, LibsnarkReduction>::verify_with_processed_vk(
388 vk,
389 public_inputs.as_slice(),
390 &proof,
391 )
392 .map_err(VerificationError::SynthesisError)?
393 .tap(|proof_result| tracing::debug!(?proof_result, elapsed = ?start.elapsed()))
394 .then_some(())
395 .ok_or(VerificationError::InvalidProof)
396 }
397}
398
399impl DomainType for DelegatorVoteProof {
400 type Proto = pb::ZkDelegatorVoteProof;
401}
402
403impl From<DelegatorVoteProof> for pb::ZkDelegatorVoteProof {
404 fn from(proof: DelegatorVoteProof) -> Self {
405 pb::ZkDelegatorVoteProof {
406 inner: proof.0.to_vec(),
407 }
408 }
409}
410
411impl TryFrom<pb::ZkDelegatorVoteProof> for DelegatorVoteProof {
412 type Error = anyhow::Error;
413
414 fn try_from(proto: pb::ZkDelegatorVoteProof) -> Result<Self, Self::Error> {
415 Ok(DelegatorVoteProof(proto.inner[..].try_into()?))
416 }
417}
418
419#[cfg(test)]
420mod tests {
421
422 use super::*;
423 use decaf377::{Fq, Fr};
424 use penumbra_sdk_asset::{asset, Value};
425 use penumbra_sdk_keys::keys::{SeedPhrase, SpendKey};
426 use penumbra_sdk_num::Amount;
427 use penumbra_sdk_sct::Nullifier;
428 use proptest::prelude::*;
429
430 fn fr_strategy() -> BoxedStrategy<Fr> {
431 any::<[u8; 32]>()
432 .prop_map(|bytes| Fr::from_le_bytes_mod_order(&bytes[..]))
433 .boxed()
434 }
435
436 prop_compose! {
437 fn arb_valid_delegator_vote_statement()(v_blinding in fr_strategy(), spend_auth_randomizer in fr_strategy(), asset_id64 in any::<u64>(), address_index in any::<u32>(), amount in any::<u64>(), seed_phrase_randomness in any::<[u8; 32]>(), rseed_randomness in any::<[u8; 32]>(), num_commitments in 0..100) -> (DelegatorVoteProofPublic, DelegatorVoteProofPrivate) {
438 let seed_phrase = SeedPhrase::from_randomness(&seed_phrase_randomness);
439 let sk_sender = SpendKey::from_seed_phrase_bip44(seed_phrase, &Bip44Path::new(0));
440 let fvk_sender = sk_sender.full_viewing_key();
441 let ivk_sender = fvk_sender.incoming();
442 let (sender, _dtk_d) = ivk_sender.payment_address(address_index.into());
443 let value_to_send = Value {
444 amount: Amount::from(amount),
445 asset_id: asset::Id(Fq::from(asset_id64)),
446 };
447 let note = Note::from_parts(
448 sender.clone(),
449 value_to_send,
450 Rseed(rseed_randomness),
451 ).expect("should be able to create note");
452 let note_commitment = note.commit();
453 let rsk = sk_sender.spend_auth_key().randomize(&spend_auth_randomizer);
454 let nk = *sk_sender.nullifier_key();
455 let ak: VerificationKey<SpendAuth> = sk_sender.spend_auth_key().into();
456
457 let mut sct = tct::Tree::new();
458
459 for i in 0..num_commitments {
462 let rseed = Rseed([i as u8; 32]);
464 let dummy_note_commitment = Note::from_parts(sender.clone(), value_to_send, rseed).expect("can create note").commit();
465 sct.insert(tct::Witness::Keep, dummy_note_commitment).expect("can insert note commitment into SCT");
466 }
467
468 sct.insert(tct::Witness::Keep, note_commitment).expect("can insert note commitment into SCT");
469 let anchor = sct.root();
470 let state_commitment_proof = sct.witness(note_commitment).expect("can witness note commitment");
471
472 sct.end_epoch().expect("should be able to end an epoch");
475 let first_note_commitment = Note::from_parts(sender.clone(), value_to_send, Rseed([u8::MAX; 32])).expect("can create note").commit();
476 sct.insert(tct::Witness::Keep, first_note_commitment).expect("can insert note commitment into SCT");
477 let start_position = sct.witness(first_note_commitment).expect("can witness note commitment").position();
478
479 let balance_commitment = value_to_send.commit(v_blinding);
480 let rk: VerificationKey<SpendAuth> = rsk.into();
481 let nullifier = Nullifier::derive(&nk, state_commitment_proof.position(), ¬e_commitment);
482
483 let public = DelegatorVoteProofPublic {
484 anchor,
485 balance_commitment,
486 nullifier,
487 rk,
488 start_position,
489 };
490 let private = DelegatorVoteProofPrivate {
491 state_commitment_proof,
492 note,
493 v_blinding,
494 spend_auth_randomizer,
495 ak,
496 nk,
497 };
498 (public, private)
499 }
500 }
501
502 proptest! {
503 #[test]
504 fn delegator_vote_happy_path((public, private) in arb_valid_delegator_vote_statement()) {
505 assert!(check_satisfaction(&public, &private).is_ok());
506 assert!(check_circuit_satisfaction(public, private).is_ok());
507 }
508 }
509
510 prop_compose! {
511 fn arb_invalid_delegator_vote_statement_nonzero_start()(v_blinding in fr_strategy(), spend_auth_randomizer in fr_strategy(), asset_id64 in any::<u64>(), address_index in any::<u32>(), amount in any::<u64>(), seed_phrase_randomness in any::<[u8; 32]>(), rseed_randomness in any::<[u8; 32]>(), num_commitments in 0..100) -> (DelegatorVoteProofPublic, DelegatorVoteProofPrivate) {
514 let seed_phrase = SeedPhrase::from_randomness(&seed_phrase_randomness);
515 let sk_sender = SpendKey::from_seed_phrase_bip44(seed_phrase, &Bip44Path::new(0));
516 let fvk_sender = sk_sender.full_viewing_key();
517 let ivk_sender = fvk_sender.incoming();
518 let (sender, _dtk_d) = ivk_sender.payment_address(address_index.into());
519 let value_to_send = Value {
520 amount: Amount::from(amount),
521 asset_id: asset::Id(Fq::from(asset_id64)),
522 };
523 let note = Note::from_parts(
524 sender.clone(),
525 value_to_send,
526 Rseed(rseed_randomness),
527 ).expect("should be able to create note");
528 let note_commitment = note.commit();
529 let rsk = sk_sender.spend_auth_key().randomize(&spend_auth_randomizer);
530 let nk = *sk_sender.nullifier_key();
531 let ak: VerificationKey<SpendAuth> = sk_sender.spend_auth_key().into();
532
533 let mut sct = tct::Tree::new();
534
535 for i in 0..num_commitments {
538 let rseed = Rseed([i as u8; 32]);
540 let dummy_note_commitment = Note::from_parts(sender.clone(), value_to_send, rseed).expect("can create note").commit();
541 sct.insert(tct::Witness::Keep, dummy_note_commitment).expect("can insert note commitment into SCT");
542 }
543
544 sct.insert(tct::Witness::Keep, note_commitment).expect("can insert note commitment into SCT");
545 let anchor = sct.root();
546 let state_commitment_proof = sct.witness(note_commitment).expect("can witness note commitment");
547
548 let rseed = Rseed([num_commitments as u8; 32]);
549 let not_first_note_commitment = Note::from_parts(sender, value_to_send, rseed).expect("can create note").commit();
550 sct.insert(tct::Witness::Keep, not_first_note_commitment).expect("can insert note commitment into SCT");
551 let start_position = sct.witness(not_first_note_commitment).expect("can witness note commitment").position();
554
555 let balance_commitment = value_to_send.commit(v_blinding);
556 let rk: VerificationKey<SpendAuth> = rsk.into();
557 let nullifier = Nullifier::derive(&nk, state_commitment_proof.position(), ¬e_commitment);
558
559 let public = DelegatorVoteProofPublic {
560 anchor,
561 balance_commitment,
562 nullifier,
563 rk,
564 start_position,
565 };
566 let private = DelegatorVoteProofPrivate {
567 state_commitment_proof,
568 note,
569 v_blinding,
570 spend_auth_randomizer,
571 ak,
572 nk,
573 };
574 (public, private)
575 }
576 }
577
578 proptest! {
579 #[test]
580 fn delegator_vote_invalid_start_position((public, private) in arb_invalid_delegator_vote_statement_nonzero_start()) {
581 assert!(check_satisfaction(&public, &private).is_err());
582 assert!(check_circuit_satisfaction(public, private).is_err());
583 }
584 }
585}