mod.rs (13616B)
1 use std::borrow::Cow; 2 use std::{ 3 sync::atomic::AtomicBool, 4 time::{Duration, Instant}, 5 }; 6 7 #[cfg(feature = "e2e")] 8 use std::sync::atomic::{AtomicU64, Ordering}; 9 10 use super::{Block, FinalizerMode, MAX_VDF_ROUNDS, VDF_TARGET_BLOCK_MS, decode_hex, hex_encode}; 11 12 #[cfg(test)] 13 mod arithmetic; 14 mod limb_arithmetic; 15 mod limbs; 16 mod prover; 17 #[cfg(test)] 18 mod reducer; 19 mod wesolowski; 20 21 #[cfg(test)] 22 mod reference; 23 24 const VDF_SOLUTION_PREFIX: &str = "classgroup-wesolowski-bqfc-v1:"; 25 const MIN_VDF_ROUNDS: u64 = 1; 26 #[cfg(feature = "e2e")] 27 static E2E_VDF_ROUND_DIVISOR: AtomicU64 = AtomicU64::new(1); 28 pub(super) const VDF_RETARGET_WINDOW_BLOCKS: usize = 20; 29 pub(super) const MAX_VDF_RETARGET_STEP_PERCENT: u128 = 2; 30 pub(super) const VDF_RETARGET_DEADBAND_PERCENT: u128 = 10; 31 pub(super) const MIN_VDF_RETARGET_OBSERVED_BLOCK_MS: u64 = VDF_TARGET_BLOCK_MS / 4; 32 pub(super) const MAX_VDF_RETARGET_OBSERVED_BLOCK_MS: u64 = VDF_TARGET_BLOCK_MS * 4; 33 34 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 35 pub struct VdfProgress { 36 pub completed_steps: u64, 37 pub total_steps: u64, 38 pub completed_phase_rounds: u64, 39 pub phase_rounds: u64, 40 pub phase: VdfProgressPhase, 41 } 42 43 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 44 pub enum VdfProgressPhase { 45 Output, 46 Proof, 47 } 48 49 /// Shortens newly produced and verified VDFs inside an isolated e2e test 50 /// process. Every participant in that process must use the same divisor. 51 #[cfg(feature = "e2e")] 52 pub fn configure_e2e_vdf_round_divisor_for_tests(divisor: u64) { 53 E2E_VDF_ROUND_DIVISOR.store(divisor.max(1), Ordering::Relaxed); 54 } 55 56 pub fn run_vdf(seed: &str, rounds: u64) -> String { 57 run_vdf_with_progress(seed, rounds, Duration::MAX, |_| {}) 58 } 59 60 pub fn run_vdf_with_progress( 61 seed: &str, 62 rounds: u64, 63 progress_interval: Duration, 64 progress: impl FnMut(VdfProgress), 65 ) -> String { 66 let cancelled = AtomicBool::new(false); 67 run_vdf_cancellable_with_progress(seed, rounds, progress_interval, &cancelled, progress) 68 .expect("non-cancellable VDF must finish") 69 } 70 71 pub fn run_vdf_cancellable_with_progress( 72 seed: &str, 73 rounds: u64, 74 progress_interval: Duration, 75 cancelled: &AtomicBool, 76 mut progress: impl FnMut(VdfProgress), 77 ) -> Option<String> { 78 let (proof_seed, proof_rounds) = vdf_proof_parameters(seed, rounds); 79 let total_steps = proof_rounds.saturating_mul(2); 80 let mut last_progress = Instant::now(); 81 let solution = wesolowski::prove_cancellable( 82 proof_seed.as_bytes(), 83 proof_rounds, 84 |phase, completed_phase_rounds| { 85 let completed_steps = match phase { 86 VdfProgressPhase::Output => completed_phase_rounds, 87 VdfProgressPhase::Proof => proof_rounds.saturating_add(completed_phase_rounds), 88 }; 89 maybe_report_vdf_progress( 90 &mut last_progress, 91 progress_interval, 92 VdfProgress { 93 completed_steps, 94 total_steps, 95 completed_phase_rounds, 96 phase_rounds: proof_rounds, 97 phase, 98 }, 99 &mut progress, 100 ); 101 }, 102 cancelled, 103 ) 104 .expect("valid IUNA VDF parameters must produce a class-group proof"); 105 solution.map(|solution| encode_vdf_solution(&solution)) 106 } 107 108 pub fn verify_vdf(seed: &str, rounds: u64, solution: &str) -> bool { 109 let Some(solution) = decode_vdf_solution(solution) else { 110 return false; 111 }; 112 let (proof_seed, proof_rounds) = vdf_proof_parameters(seed, rounds); 113 wesolowski::verify(proof_seed.as_bytes(), proof_rounds, &solution) 114 } 115 116 fn vdf_proof_parameters(seed: &str, rounds: u64) -> (Cow<'_, str>, u64) { 117 #[cfg(feature = "e2e")] 118 { 119 let divisor = E2E_VDF_ROUND_DIVISOR.load(Ordering::Relaxed); 120 if divisor > 1 { 121 return ( 122 Cow::Owned(format!("iuna-e2e-vdf:{rounds}:{seed}")), 123 rounds.div_ceil(divisor).max(MIN_VDF_ROUNDS), 124 ); 125 } 126 } 127 (Cow::Borrowed(seed), rounds) 128 } 129 130 pub(super) fn vdf_solution_placeholder() -> String { 131 format!( 132 "{VDF_SOLUTION_PREFIX}{}", 133 "f".repeat(wesolowski::SOLUTION_BYTES * 2) 134 ) 135 } 136 137 pub(super) fn retarget_vdf_rounds(current_rounds: u64, observed_block_ms: u64) -> u64 { 138 let current = u128::from(current_rounds); 139 let observed = u128::from(observed_block_ms.max(1)); 140 let target = u128::from(VDF_TARGET_BLOCK_MS); 141 let deadband = target * VDF_RETARGET_DEADBAND_PERCENT / 100; 142 if observed >= target.saturating_sub(deadband) && observed <= target.saturating_add(deadband) { 143 return current_rounds; 144 } 145 146 let raw_adjusted = current * target / observed; 147 let max_step = (current * MAX_VDF_RETARGET_STEP_PERCENT / 100).max(1); 148 let min_next = current 149 .saturating_sub(max_step) 150 .max(u128::from(MIN_VDF_ROUNDS)); 151 let max_next = current 152 .saturating_add(max_step) 153 .min(u128::from(MAX_VDF_ROUNDS)); 154 raw_adjusted.clamp(min_next, max_next) as u64 155 } 156 157 pub(super) fn clamped_vdf_retarget_observed_block_ms(observed_block_ms: u64) -> u64 { 158 observed_block_ms.clamp( 159 MIN_VDF_RETARGET_OBSERVED_BLOCK_MS, 160 MAX_VDF_RETARGET_OBSERVED_BLOCK_MS, 161 ) 162 } 163 164 pub(super) fn vdf_retarget_observed_block_ms(parent: &Block, child: &Block) -> Option<u64> { 165 if child.finalizer_mode != FinalizerMode::Ticket { 166 return None; 167 } 168 if child.finalizer_rank != 0 { 169 return None; 170 } 171 172 Some(clamped_vdf_retarget_observed_block_ms( 173 child.timestamp_ms - parent.timestamp_ms, 174 )) 175 } 176 177 pub(super) fn recent_vdf_retarget_average_observed_block_ms(chain: &[Block]) -> Option<u64> { 178 let observations = chain 179 .windows(2) 180 .rev() 181 .filter(|pair| pair[0].height > 0) 182 .filter_map(|pair| vdf_retarget_observed_block_ms(&pair[0], &pair[1])) 183 .take(VDF_RETARGET_WINDOW_BLOCKS) 184 .collect::<Vec<_>>(); 185 if observations.is_empty() { 186 return None; 187 } 188 let total = observations 189 .iter() 190 .map(|observed| u128::from(*observed)) 191 .sum::<u128>(); 192 Some((total / observations.len() as u128) as u64) 193 } 194 195 fn maybe_report_vdf_progress( 196 last_progress: &mut Instant, 197 progress_interval: Duration, 198 snapshot: VdfProgress, 199 progress: &mut impl FnMut(VdfProgress), 200 ) { 201 if snapshot.completed_steps == snapshot.total_steps 202 || last_progress.elapsed() >= progress_interval 203 { 204 progress(snapshot); 205 *last_progress = Instant::now(); 206 } 207 } 208 209 fn encode_vdf_solution(solution: &[u8]) -> String { 210 format!("{VDF_SOLUTION_PREFIX}{}", hex_encode(solution)) 211 } 212 213 fn decode_vdf_solution(solution: &str) -> Option<Vec<u8>> { 214 let hex = solution.strip_prefix(VDF_SOLUTION_PREFIX)?; 215 let solution = decode_hex(hex).ok()?; 216 (solution.len() == wesolowski::SOLUTION_BYTES).then_some(solution) 217 } 218 219 #[cfg(test)] 220 mod tests { 221 use std::{ 222 sync::atomic::{AtomicBool, Ordering}, 223 time::Duration, 224 }; 225 226 use super::{ 227 MAX_VDF_RETARGET_OBSERVED_BLOCK_MS, MAX_VDF_RETARGET_STEP_PERCENT, 228 MIN_VDF_RETARGET_OBSERVED_BLOCK_MS, VDF_RETARGET_DEADBAND_PERCENT, 229 VDF_RETARGET_WINDOW_BLOCKS, VDF_SOLUTION_PREFIX, VdfProgressPhase, 230 clamped_vdf_retarget_observed_block_ms, recent_vdf_retarget_average_observed_block_ms, 231 retarget_vdf_rounds, run_vdf, run_vdf_cancellable_with_progress, run_vdf_with_progress, 232 vdf_retarget_observed_block_ms, vdf_solution_placeholder, verify_vdf, wesolowski, 233 }; 234 use crate::domain::{Block, BurnBundleSection, FinalizerMode, VDF_TARGET_BLOCK_MS}; 235 236 fn block(height: u64, timestamp_ms: u64, mode: FinalizerMode, rank: u32) -> Block { 237 Block { 238 height, 239 prev_hash: format!("{height:064x}"), 240 timestamp_ms, 241 miner: "finalizer".to_string(), 242 reward_address: None, 243 reward_address_signature: None, 244 finalizer_mode: mode, 245 finalizer_rank: rank, 246 reward: 0, 247 vdf_rounds: 100, 248 vdf_output: format!("output-{height}"), 249 leader_proof: None, 250 burn_bundle_section: BurnBundleSection::default(), 251 transactions: Vec::new(), 252 transactions_v2: Vec::new(), 253 hash: format!("{:064x}", height + 1), 254 } 255 } 256 257 #[test] 258 fn vdf_retarget_parameters_and_boundaries_match_the_protocol() { 259 assert_eq!(VDF_RETARGET_WINDOW_BLOCKS, 20); 260 assert_eq!(VDF_RETARGET_DEADBAND_PERCENT, 10); 261 assert_eq!(MAX_VDF_RETARGET_STEP_PERCENT, 2); 262 assert_eq!(MIN_VDF_RETARGET_OBSERVED_BLOCK_MS, VDF_TARGET_BLOCK_MS / 4); 263 assert_eq!(MAX_VDF_RETARGET_OBSERVED_BLOCK_MS, VDF_TARGET_BLOCK_MS * 4); 264 265 assert_eq!( 266 retarget_vdf_rounds(1_000, VDF_TARGET_BLOCK_MS * 9 / 10), 267 1_000 268 ); 269 assert_eq!( 270 retarget_vdf_rounds(1_000, VDF_TARGET_BLOCK_MS * 11 / 10), 271 1_000 272 ); 273 assert_eq!(retarget_vdf_rounds(1_000, VDF_TARGET_BLOCK_MS / 2), 1_020); 274 assert_eq!(retarget_vdf_rounds(1_000, VDF_TARGET_BLOCK_MS * 2), 980); 275 assert_eq!( 276 clamped_vdf_retarget_observed_block_ms(1), 277 VDF_TARGET_BLOCK_MS / 4 278 ); 279 assert_eq!( 280 clamped_vdf_retarget_observed_block_ms(u64::MAX), 281 VDF_TARGET_BLOCK_MS * 4 282 ); 283 } 284 285 #[test] 286 fn vdf_retarget_observes_only_rank_zero_ticket_blocks() { 287 let parent = block(1, 1_000, FinalizerMode::Ticket, 0); 288 let primary = block(2, 1_000 + VDF_TARGET_BLOCK_MS, FinalizerMode::Ticket, 0); 289 let fallback = block(2, 1_000 + VDF_TARGET_BLOCK_MS, FinalizerMode::Ticket, 1); 290 let recovery = block(2, 1_000 + VDF_TARGET_BLOCK_MS, FinalizerMode::Recovery, 0); 291 292 assert_eq!( 293 vdf_retarget_observed_block_ms(&parent, &primary), 294 Some(VDF_TARGET_BLOCK_MS) 295 ); 296 assert_eq!(vdf_retarget_observed_block_ms(&parent, &fallback), None); 297 assert_eq!(vdf_retarget_observed_block_ms(&parent, &recovery), None); 298 } 299 300 #[test] 301 fn fallback_blocks_do_not_consume_the_twenty_primary_observation_window() { 302 let mut chain = vec![block(0, 0, FinalizerMode::Ticket, 0)]; 303 chain.push(block(1, VDF_TARGET_BLOCK_MS / 2, FinalizerMode::Ticket, 0)); 304 for height in 2..=21 { 305 chain.push(block( 306 height, 307 height * (VDF_TARGET_BLOCK_MS / 2), 308 FinalizerMode::Ticket, 309 0, 310 )); 311 } 312 for height in 22..=46 { 313 chain.push(block( 314 height, 315 height * (VDF_TARGET_BLOCK_MS / 2), 316 FinalizerMode::Ticket, 317 1, 318 )); 319 } 320 321 assert_eq!( 322 recent_vdf_retarget_average_observed_block_ms(&chain), 323 Some(VDF_TARGET_BLOCK_MS / 2) 324 ); 325 } 326 327 #[test] 328 fn vdf_solution_verifies_and_is_bound_to_seed_and_rounds() { 329 let solution = run_vdf("test-seed", 128); 330 331 assert!(verify_vdf("test-seed", 128, &solution)); 332 assert!(!verify_vdf("other-seed", 128, &solution)); 333 assert!(!verify_vdf("test-seed", 129, &solution)); 334 assert!(!verify_vdf("test-seed", 128, "not-a-vdf-solution")); 335 } 336 337 #[test] 338 fn vdf_progress_reports_output_and_proof_steps() { 339 let mut progress = Vec::new(); 340 let solution = run_vdf_with_progress("progress-seed", 4, Duration::ZERO, |snapshot| { 341 progress.push(snapshot); 342 }); 343 344 assert!(verify_vdf("progress-seed", 4, &solution)); 345 assert!( 346 progress 347 .iter() 348 .any(|snapshot| snapshot.phase == VdfProgressPhase::Output) 349 ); 350 assert!( 351 progress 352 .iter() 353 .any(|snapshot| snapshot.phase == VdfProgressPhase::Proof) 354 ); 355 assert_eq!( 356 progress.last().map(|snapshot| snapshot.completed_steps), 357 Some(8) 358 ); 359 assert_eq!( 360 progress.last().map(|snapshot| snapshot.total_steps), 361 Some(8) 362 ); 363 } 364 365 #[test] 366 fn cancellable_vdf_stops_during_output_or_proof() { 367 for phase in [VdfProgressPhase::Output, VdfProgressPhase::Proof] { 368 let cancelled = AtomicBool::new(false); 369 let solution = run_vdf_cancellable_with_progress( 370 "cancelled-seed", 371 128, 372 Duration::ZERO, 373 &cancelled, 374 |progress| { 375 if progress.phase == phase && progress.completed_phase_rounds >= 10 { 376 cancelled.store(true, Ordering::Relaxed); 377 } 378 }, 379 ); 380 381 assert!(solution.is_none(), "VDF did not stop during {phase:?}"); 382 } 383 } 384 385 #[test] 386 fn vdf_solution_uses_chia_bqfc_protocol_format() { 387 let solution = run_vdf("test-seed", 16); 388 let encoded = solution.strip_prefix(VDF_SOLUTION_PREFIX).unwrap(); 389 390 assert_eq!(encoded.len(), wesolowski::SOLUTION_BYTES * 2); 391 assert_eq!(solution.len(), vdf_solution_placeholder().len()); 392 } 393 394 #[test] 395 fn legacy_vdf_solution_formats_are_not_accepted() { 396 let rsa = format!("{}:{}", "f".repeat(512), "f".repeat(512)); 397 let gmp_class_group = format!("classgroup-wesolowski-v1:{}", "f".repeat(520)); 398 399 assert!(!verify_vdf("test-seed", 16, &rsa)); 400 assert!(!verify_vdf("test-seed", 16, &gmp_class_group)); 401 } 402 }