wesolowski.rs (7407B)
1 use std::sync::atomic::AtomicBool; 2 3 use kyn_vdf::{ 4 Form, KynVdfError, create_discriminant, deserialize_form, isqrt_fourth, serialize_form, 5 verify_wesolowski, 6 }; 7 use num_traits::Signed; 8 9 use super::{VdfProgressPhase, prover}; 10 11 pub(super) const DISCRIMINANT_BITS: usize = 1024; 12 const FORM_BYTES: usize = 100; 13 pub(super) const SOLUTION_BYTES: usize = FORM_BYTES * 2; 14 15 #[cfg(test)] 16 pub(super) fn prove( 17 seed: &[u8], 18 rounds: u64, 19 progress: impl FnMut(VdfProgressPhase, u64), 20 ) -> Result<Vec<u8>, KynVdfError> { 21 let cancelled = AtomicBool::new(false); 22 prove_cancellable(seed, rounds, progress, &cancelled)?.ok_or_else(|| { 23 KynVdfError::ArithmeticError("non-cancellable VDF was cancelled".to_string()) 24 }) 25 } 26 27 pub(super) fn prove_cancellable( 28 seed: &[u8], 29 rounds: u64, 30 mut progress: impl FnMut(VdfProgressPhase, u64), 31 cancelled: &AtomicBool, 32 ) -> Result<Option<Vec<u8>>, KynVdfError> { 33 if rounds == 0 { 34 return Err(KynVdfError::InvalidIterations(rounds)); 35 } 36 37 let discriminant = create_discriminant(seed, DISCRIMINANT_BITS)?; 38 let generator = 39 Form::generator(&discriminant).ok_or(KynVdfError::InvalidDiscriminantIdentity)?; 40 let threshold = isqrt_fourth(&discriminant.abs()); 41 42 let Some((output, proof)) = prover::prove_cancellable( 43 &discriminant, 44 &generator, 45 &threshold, 46 rounds, 47 &mut progress, 48 cancelled, 49 )? 50 else { 51 return Ok(None); 52 }; 53 serialize_solution(&output, &proof).map(Some) 54 } 55 56 pub(super) fn verify(seed: &[u8], rounds: u64, solution: &[u8]) -> bool { 57 if rounds == 0 || solution.len() != SOLUTION_BYTES { 58 return false; 59 } 60 61 let Some(discriminant) = create_discriminant(seed, DISCRIMINANT_BITS).ok() else { 62 return false; 63 }; 64 let Some(generator) = Form::generator(&discriminant) else { 65 return false; 66 }; 67 68 let (output_bytes, proof_bytes) = solution.split_at(FORM_BYTES); 69 let Some(output) = canonical_form(&discriminant, output_bytes) else { 70 return false; 71 }; 72 let Some(proof) = canonical_form(&discriminant, proof_bytes) else { 73 return false; 74 }; 75 76 verify_wesolowski(&discriminant, &generator, &output, &proof, rounds).unwrap_or(false) 77 } 78 79 fn canonical_form(discriminant: &num_bigint::BigInt, bytes: &[u8]) -> Option<Form> { 80 let form = deserialize_form(discriminant, bytes).ok()?; 81 (serialize_form(&form, DISCRIMINANT_BITS).ok()?.as_slice() == bytes).then_some(form) 82 } 83 84 pub(super) fn serialize_solution(output: &Form, proof: &Form) -> Result<Vec<u8>, KynVdfError> { 85 let mut solution = serialize_form(output, DISCRIMINANT_BITS)?; 86 solution.extend_from_slice(&serialize_form(proof, DISCRIMINANT_BITS)?); 87 debug_assert_eq!(solution.len(), SOLUTION_BYTES); 88 Ok(solution) 89 } 90 91 #[cfg(test)] 92 mod tests { 93 #[cfg(target_os = "macos")] 94 use std::process::Command; 95 96 use super::{SOLUTION_BYTES, prove, verify}; 97 98 const CHIA_CHALLENGE_42_PROOF_HEX: &str = concat!( 99 "0300032167dfd0eb393ed5d544e6499ba24def860ecd8a3600490f2f87b003c3e7855763969d34e2d1c60910297df3aead9f078a1f4d3973903f532977f9639f693cdbd331e8ba96bd61c895726dd157d67310ae98d1632c9bb9f28e0d7337403c0a0100", 100 "04000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", 101 ); 102 const CHIA_CHALLENGE_42_NONTRIVIAL_PROOF_HEX: &str = concat!( 103 "0000235f6d0bfcbadbd5a0d6619a8611345eb63891876d37150fdef725695ab80c6deef7684c38fe0e086355baf4786fed8a5f843d0b7a62bf1125765b016dfe965b493cfc9bcde723c5299db8db25885d130f9aef4b029f98f42831aaf53e51e3350100", 104 "0300d2b31e34c399ec49288e3fccb6ebaf0f3fb2e814c7c21e8579c17b5f2600b1a64d9d5b94435084b3458a9343fd1bcd3f0b9e5874556f1ab1529347b54788af1eb9268a5ee888fba85934c81b199a4228a41cb01c10b3195c95b26c17f16ff7020100", 105 ); 106 107 #[test] 108 fn prover_matches_chia_known_vector() { 109 let solution = prove(&[0x42; 32], 100, |_, _| {}).unwrap(); 110 111 assert_eq!( 112 solution, 113 crate::domain::decode_hex(CHIA_CHALLENGE_42_PROOF_HEX).unwrap() 114 ); 115 assert!(verify(&[0x42; 32], 100, &solution)); 116 } 117 118 #[test] 119 fn prover_matches_chia_nontrivial_proof_vector() { 120 let solution = prove(&[0x42; 32], 300, |_, _| {}).unwrap(); 121 122 assert_eq!( 123 solution, 124 crate::domain::decode_hex(CHIA_CHALLENGE_42_NONTRIVIAL_PROOF_HEX).unwrap() 125 ); 126 assert!(verify(&[0x42; 32], 300, &solution)); 127 } 128 129 #[cfg(target_os = "macos")] 130 #[test] 131 #[ignore = "requires the optional Python chiavdf package"] 132 fn prover_matches_chiavdf_python_binding() { 133 for (seed, rounds) in [([0x42; 32], 100), ([0x42; 32], 300)] { 134 let expected = chiavdf_prove(&seed, rounds); 135 let actual = prove(&seed, rounds, |_, _| {}).unwrap(); 136 137 assert_eq!(actual, expected, "rounds={rounds}"); 138 assert!(verify(&seed, rounds, &actual)); 139 } 140 } 141 142 #[test] 143 fn proof_is_exactly_two_bqfc_forms() { 144 let solution = prove(b"iuna-vdf-wire-format", 16, |_, _| {}).unwrap(); 145 146 assert_eq!(solution.len(), SOLUTION_BYTES); 147 } 148 149 #[test] 150 fn malformed_and_mismatched_proofs_are_rejected() { 151 let solution = prove(b"iuna-vdf-negative-test", 300, |_, _| {}).unwrap(); 152 let mut tampered = solution.clone(); 153 tampered[50] ^= 1; 154 155 assert!(!verify(b"iuna-vdf-negative-test", 300, &tampered)); 156 assert!(!verify(b"iuna-vdf-negative-test", 301, &solution)); 157 assert!(!verify(b"other-seed", 300, &solution)); 158 assert!(!verify(b"iuna-vdf-negative-test", 300, &solution[..199])); 159 } 160 161 #[test] 162 fn non_canonical_special_form_encodings_are_rejected() { 163 let mut solution = prove(&[0x42; 32], 100, |_, _| {}).unwrap(); 164 assert_eq!(solution[100], 0x04, "the known proof is the identity"); 165 166 solution[199] = 1; 167 168 assert!(!verify(&[0x42; 32], 100, &solution)); 169 } 170 171 #[cfg(target_os = "macos")] 172 fn chiavdf_prove(seed: &[u8; 32], rounds: u64) -> Vec<u8> { 173 let python = std::env::var("IUNA_CHIAVDF_PYTHON").unwrap_or_else(|_| "python3".to_owned()); 174 let seed_hex = crate::domain::hex_encode(seed); 175 let script = r#" 176 import sys 177 import tempfile 178 179 from chiavdf import prove 180 181 seed = bytes.fromhex(sys.argv[1]) 182 rounds = int(sys.argv[2]) 183 initial_el = b"\x08" + (b"\x00" * 99) 184 185 with tempfile.NamedTemporaryFile(prefix="iuna-chiavdf-shutdown-") as shutdown: 186 solution = prove(seed, initial_el, 1024, rounds, shutdown.name) 187 188 sys.stdout.write(bytes(solution).hex()) 189 "#; 190 191 let output = Command::new(&python) 192 .args(["-c", script, &seed_hex, &rounds.to_string()]) 193 .output() 194 .unwrap_or_else(|error| panic!("failed to run {python}: {error}")); 195 196 assert!( 197 output.status.success(), 198 "chiavdf subprocess failed with status {:?}\nstdout:\n{}\nstderr:\n{}", 199 output.status.code(), 200 String::from_utf8_lossy(&output.stdout), 201 String::from_utf8_lossy(&output.stderr) 202 ); 203 204 let stdout = String::from_utf8(output.stdout).expect("chiavdf stdout must be UTF-8 hex"); 205 crate::domain::decode_hex(stdout.trim()).expect("chiavdf stdout must be hex") 206 } 207 }