vdf.rs (9482B)
1 use std::sync::OnceLock; 2 3 use num_bigint::BigUint; 4 use num_traits::{One, Zero}; 5 use sha2::{Digest, Sha256}; 6 7 use super::{Block, FinalizerMode, MAX_VDF_ROUNDS, VDF_TARGET_BLOCK_MS}; 8 9 const VDF_RSA_2048_MODULUS_DECIMAL: &str = concat!( 10 "2519590847565789349402718324004839857142928212620403202777713783604366202070", 11 "7595556264018525880784406918290641249515082189298559149176184502808489120072", 12 "8449926873928072877767359714183472702618963750149718246911650776133798590957", 13 "0009733045974880842840179742910064245869181719511874612151517265463228221686", 14 "9987549182422433637259085141865462043576798423387184774447920739934236584823", 15 "8242811981638150106748104516603773060562016196762561338441436038339044149526", 16 "3443219011465754445417842402092461651572335077870774981712577246796292638635", 17 "6373289912154831438167899885040445364023527381951378636564391212010397122822", 18 "120720357", 19 ); 20 const VDF_ELEMENT_HEX_LEN: usize = 512; 21 const VDF_CHALLENGE_MIN: u64 = 1_073_741_827; 22 const MIN_VDF_ROUNDS: u64 = 1; 23 pub(super) const VDF_RETARGET_WINDOW_BLOCKS: usize = 20; 24 pub(super) const MAX_VDF_RETARGET_STEP_PERCENT: u128 = 2; 25 pub(super) const VDF_RETARGET_DEADBAND_PERCENT: u128 = 10; 26 pub(super) const MIN_VDF_RETARGET_OBSERVED_BLOCK_MS: u64 = VDF_TARGET_BLOCK_MS / 4; 27 pub(super) const MAX_VDF_RETARGET_OBSERVED_BLOCK_MS: u64 = VDF_TARGET_BLOCK_MS * 4; 28 29 pub fn run_vdf(seed: &str, rounds: u64) -> String { 30 let x = vdf_seed_element(seed); 31 let mut y = x.clone(); 32 for _ in 0..rounds { 33 y = square_mod(&y); 34 } 35 36 let challenge = vdf_challenge_prime(seed, rounds, &y); 37 let proof = vdf_proof(&x, rounds, challenge); 38 encode_vdf_solution(y, proof) 39 } 40 41 pub fn verify_vdf(seed: &str, rounds: u64, solution: &str) -> bool { 42 let Some((y, proof)) = decode_vdf_solution(solution) else { 43 return false; 44 }; 45 if y.is_zero() || y >= *vdf_modulus() || proof >= *vdf_modulus() { 46 return false; 47 } 48 49 let x = vdf_seed_element(seed); 50 let challenge = vdf_challenge_prime(seed, rounds, &y); 51 let remainder = BigUint::from(pow_mod_small(2, rounds, challenge)); 52 let verified = mul_mod( 53 &proof.modpow(&BigUint::from(challenge), vdf_modulus()), 54 &x.modpow(&remainder, vdf_modulus()), 55 ); 56 verified == y 57 } 58 59 pub(super) fn retarget_vdf_rounds(current_rounds: u64, observed_block_ms: u64) -> u64 { 60 let current = u128::from(current_rounds); 61 let observed = u128::from(observed_block_ms.max(1)); 62 let target = u128::from(VDF_TARGET_BLOCK_MS); 63 let deadband = target * VDF_RETARGET_DEADBAND_PERCENT / 100; 64 if observed >= target.saturating_sub(deadband) && observed <= target.saturating_add(deadband) { 65 return current_rounds; 66 } 67 68 let raw_adjusted = current * target / observed; 69 let max_step = (current * MAX_VDF_RETARGET_STEP_PERCENT / 100).max(1); 70 let min_next = current 71 .saturating_sub(max_step) 72 .max(u128::from(MIN_VDF_ROUNDS)); 73 let max_next = current 74 .saturating_add(max_step) 75 .min(u128::from(MAX_VDF_ROUNDS)); 76 raw_adjusted.clamp(min_next, max_next) as u64 77 } 78 79 pub(super) fn clamped_vdf_retarget_observed_block_ms(observed_block_ms: u64) -> u64 { 80 observed_block_ms.clamp( 81 MIN_VDF_RETARGET_OBSERVED_BLOCK_MS, 82 MAX_VDF_RETARGET_OBSERVED_BLOCK_MS, 83 ) 84 } 85 86 pub(super) fn vdf_retarget_observed_block_ms(parent: &Block, child: &Block) -> Option<u64> { 87 if child.finalizer_mode != FinalizerMode::Ticket { 88 return None; 89 } 90 if child.finalizer_rank != 0 { 91 return None; 92 } 93 94 Some(clamped_vdf_retarget_observed_block_ms( 95 child.timestamp_ms - parent.timestamp_ms, 96 )) 97 } 98 99 fn vdf_modulus() -> &'static BigUint { 100 static MODULUS: OnceLock<BigUint> = OnceLock::new(); 101 MODULUS.get_or_init(|| { 102 BigUint::parse_bytes(VDF_RSA_2048_MODULUS_DECIMAL.as_bytes(), 10) 103 .expect("VDF RSA-2048 modulus must parse") 104 }) 105 } 106 107 fn vdf_seed_element(seed: &str) -> BigUint { 108 let one = BigUint::one(); 109 let two = BigUint::from(2_u32); 110 for attempt in 0_u32.. { 111 let candidate = hash_to_modulus("iuna-vdf-seed-v2", seed, attempt); 112 if candidate <= one { 113 continue; 114 } 115 let element = candidate.modpow(&two, vdf_modulus()); 116 if element > one { 117 return element; 118 } 119 } 120 unreachable!("VDF seed hashing must eventually produce a usable element") 121 } 122 123 fn hash_to_modulus(domain: &str, seed: &str, attempt: u32) -> BigUint { 124 let byte_len = vdf_modulus().bits().div_ceil(8) as usize; 125 let mut bytes = Vec::with_capacity(byte_len); 126 let mut counter = 0_u32; 127 while bytes.len() < byte_len { 128 let digest = Sha256::digest(format!("{domain}:{seed}:{attempt}:{counter}").as_bytes()); 129 bytes.extend_from_slice(&digest); 130 counter = counter.saturating_add(1); 131 } 132 bytes.truncate(byte_len); 133 BigUint::from_bytes_be(&bytes) % vdf_modulus() 134 } 135 136 fn vdf_challenge_prime(seed: &str, rounds: u64, output: &BigUint) -> u64 { 137 let digest = Sha256::digest(format!("iuna-vdf-challenge:{seed}:{rounds}:{output:x}")); 138 let mut bytes = [0_u8; 8]; 139 bytes.copy_from_slice(&digest[..8]); 140 let candidate = VDF_CHALLENGE_MIN + (u64::from_be_bytes(bytes) % VDF_CHALLENGE_MIN); 141 next_odd_prime(candidate | 1) 142 } 143 144 fn vdf_proof(x: &BigUint, rounds: u64, challenge: u64) -> BigUint { 145 let mut proof = BigUint::one(); 146 let mut remainder = 1_u64 % challenge; 147 for _ in 0..rounds { 148 let doubled = remainder * 2; 149 let carry = doubled >= challenge; 150 proof = square_mod(&proof); 151 if carry { 152 proof = mul_mod(&proof, x); 153 } 154 remainder = doubled % challenge; 155 } 156 proof 157 } 158 159 fn encode_vdf_solution(output: BigUint, proof: BigUint) -> String { 160 format!( 161 "{output:0>width$x}:{proof:0>width$x}", 162 width = VDF_ELEMENT_HEX_LEN 163 ) 164 } 165 166 fn decode_vdf_solution(solution: &str) -> Option<(BigUint, BigUint)> { 167 let (output, proof) = solution.split_once(':')?; 168 if output.len() != VDF_ELEMENT_HEX_LEN || proof.len() != VDF_ELEMENT_HEX_LEN { 169 return None; 170 } 171 Some(( 172 BigUint::parse_bytes(output.as_bytes(), 16)?, 173 BigUint::parse_bytes(proof.as_bytes(), 16)?, 174 )) 175 } 176 177 fn square_mod(value: &BigUint) -> BigUint { 178 mul_mod(value, value) 179 } 180 181 fn mul_mod(left: &BigUint, right: &BigUint) -> BigUint { 182 (left * right) % vdf_modulus() 183 } 184 185 fn pow_mod_small(base: u64, exponent: u64, modulus: u64) -> u64 { 186 let mut result = 1_u128; 187 let mut base = u128::from(base % modulus); 188 let mut exponent = exponent; 189 let modulus = u128::from(modulus); 190 while exponent > 0 { 191 if exponent & 1 == 1 { 192 result = (result * base) % modulus; 193 } 194 base = (base * base) % modulus; 195 exponent >>= 1; 196 } 197 result as u64 198 } 199 200 fn next_odd_prime(mut candidate: u64) -> u64 { 201 while !is_odd_prime(candidate) { 202 candidate = candidate.saturating_add(2); 203 } 204 candidate 205 } 206 207 fn is_odd_prime(candidate: u64) -> bool { 208 if candidate < 3 || candidate % 2 == 0 { 209 return false; 210 } 211 let mut divisor = 3_u64; 212 while divisor * divisor <= candidate { 213 if candidate % divisor == 0 { 214 return false; 215 } 216 divisor += 2; 217 } 218 true 219 } 220 221 #[cfg(test)] 222 mod tests { 223 use super::{VDF_ELEMENT_HEX_LEN, pow_mod_small, run_vdf, vdf_modulus, verify_vdf}; 224 225 #[test] 226 fn vdf_solution_verifies_and_is_bound_to_seed_and_rounds() { 227 let solution = run_vdf("test-seed", 128); 228 229 assert!(verify_vdf("test-seed", 128, &solution)); 230 assert!(!verify_vdf("other-seed", 128, &solution)); 231 assert!(!verify_vdf("test-seed", 129, &solution)); 232 assert!(!verify_vdf("test-seed", 128, "not-a-vdf-solution")); 233 } 234 235 #[test] 236 fn vdf_solution_uses_2048_bit_elements() { 237 let solution = run_vdf("test-seed", 16); 238 let (output, proof) = solution.split_once(':').unwrap(); 239 240 assert_eq!(output.len(), VDF_ELEMENT_HEX_LEN); 241 assert_eq!(proof.len(), VDF_ELEMENT_HEX_LEN); 242 assert!(vdf_modulus().bits() >= 2048); 243 } 244 245 #[test] 246 fn legacy_factorable_modulus_attack_is_not_the_active_modulus() { 247 const LEGACY_MODULUS: u128 = 4_611_685_975_477_714_963; 248 const LEGACY_P: u128 = 2_147_483_629; 249 const LEGACY_Q: u128 = 2_147_483_647; 250 assert_eq!(LEGACY_P * LEGACY_Q, LEGACY_MODULUS); 251 assert_ne!(vdf_modulus().to_str_radix(10), LEGACY_MODULUS.to_string()); 252 253 let phi = (LEGACY_P - 1) * (LEGACY_Q - 1); 254 let seed = 42_u128; 255 let rounds = 10_000_u64; 256 let sequential = legacy_repeated_squaring(seed, rounds, LEGACY_MODULUS); 257 let shortcut_exponent = pow_mod_small(2, rounds, phi as u64) as u128; 258 let shortcut = legacy_mod_pow(seed, shortcut_exponent, LEGACY_MODULUS); 259 260 assert_eq!(shortcut, sequential); 261 } 262 263 fn legacy_repeated_squaring(mut value: u128, rounds: u64, modulus: u128) -> u128 { 264 for _ in 0..rounds { 265 value = (value * value) % modulus; 266 } 267 value 268 } 269 270 fn legacy_mod_pow(mut base: u128, mut exponent: u128, modulus: u128) -> u128 { 271 let mut result = 1_u128; 272 while exponent > 0 { 273 if exponent & 1 == 1 { 274 result = (result * base) % modulus; 275 } 276 base = (base * base) % modulus; 277 exponent >>= 1; 278 } 279 result 280 } 281 }