ticket.rs (19721B)
1 use std::collections::BTreeMap; 2 3 use anyhow::{Context, Result, bail}; 4 use sha2::{Digest, Sha256}; 5 6 use super::{ 7 Amount, Block, FinalizerMode, GRINDING_RESISTANCE_ACTIVATION_HEIGHT, LaunchProfile, 8 MAX_VDF_ROUNDS, Transaction, TransactionV2, VDF_TARGET_BLOCK_MS, decode_hex, hex_encode, 9 hex_hash, 10 }; 11 12 pub(super) const MISSED_FALLBACK_TICKET_INVALIDATION_HEIGHT: u64 = 300; 13 14 #[derive(Clone, Debug, Eq, PartialEq)] 15 pub(super) struct BurnTicket { 16 pub(super) id: String, 17 pub(super) owner: String, 18 pub(super) amount: Amount, 19 pub(super) eligible_from_height: u64, 20 pub(super) eligible_until_height: u64, 21 } 22 23 pub(super) fn ranked_tickets_for_height( 24 parent: &Block, 25 target_height: u64, 26 tickets: &[BurnTicket], 27 ) -> Vec<BurnTicket> { 28 let mut remaining = tickets 29 .iter() 30 .filter(|ticket| ticket_is_eligible_for_height(ticket, target_height)) 31 .cloned() 32 .collect::<Vec<_>>(); 33 let mut ranked = Vec::with_capacity(remaining.len()); 34 35 for rank in 0.. { 36 let Some(selected_index) = 37 select_weighted_ticket_index(parent, target_height, rank, &remaining) 38 else { 39 break; 40 }; 41 ranked.push(remaining.remove(selected_index)); 42 } 43 44 ranked 45 } 46 47 fn select_weighted_ticket_index( 48 parent: &Block, 49 target_height: u64, 50 rank: u32, 51 tickets: &[BurnTicket], 52 ) -> Option<usize> { 53 let total_weight = tickets.iter().try_fold(0_u128, |total, ticket| { 54 total.checked_add(u128::from(ticket.amount)) 55 })?; 56 if total_weight == 0 { 57 return None; 58 } 59 60 let draw = weighted_ticket_draw(parent, target_height, rank, total_weight); 61 let mut cumulative = 0_u128; 62 for (index, ticket) in tickets.iter().enumerate() { 63 cumulative = cumulative.checked_add(u128::from(ticket.amount))?; 64 if draw < cumulative { 65 return Some(index); 66 } 67 } 68 None 69 } 70 71 fn weighted_ticket_draw(parent: &Block, target_height: u64, rank: u32, total_weight: u128) -> u128 { 72 let seed = ticket_draw_seed(parent, target_height, rank); 73 let digest = Sha256::digest(seed.as_bytes()); 74 let mut bytes = [0_u8; 16]; 75 bytes.copy_from_slice(&digest[..16]); 76 u128::from_be_bytes(bytes) % total_weight 77 } 78 79 pub(super) fn draw_parent_randomness(parent: &Block, target_height: u64) -> String { 80 if target_height >= GRINDING_RESISTANCE_ACTIVATION_HEIGHT { 81 format!("{}:{}", parent.vdf_seed(), parent.vdf_output) 82 } else { 83 format!("{}:{}", parent.hash, parent.vdf_output) 84 } 85 } 86 87 fn ticket_draw_seed(parent: &Block, target_height: u64, rank: u32) -> String { 88 let parent_randomness = draw_parent_randomness(parent, target_height); 89 if rank == 0 { 90 format!("iuna-ticket-draw:{target_height}:{parent_randomness}") 91 } else { 92 format!("iuna-ticket-draw-rank:{target_height}:{rank}:{parent_randomness}") 93 } 94 } 95 96 pub(super) fn vdf_rounds_for_finalizer_rank(base_rounds: u64, rank: u32) -> Result<u64> { 97 let rounds = base_rounds 98 .checked_mul(u64::from( 99 rank.checked_add(1).context("finalizer rank overflows")?, 100 )) 101 .context("finalizer rank VDF rounds overflow")?; 102 if rounds > MAX_VDF_ROUNDS { 103 bail!("finalizer rank VDF rounds exceed maximum"); 104 } 105 Ok(rounds) 106 } 107 108 fn finalizer_rank_slot_delay_ms(rank: u32) -> Result<u64> { 109 VDF_TARGET_BLOCK_MS 110 .checked_mul(2) 111 .context("finalizer rank time slot overflow")? 112 .checked_mul(u64::from(rank)) 113 .context("finalizer rank time slot overflow") 114 } 115 116 pub(super) fn ticket_block_min_timestamp(parent: &Block, rank: u32) -> Result<u64> { 117 if rank == 0 { 118 return parent 119 .timestamp_ms 120 .checked_add(1) 121 .context("finalizer rank minimum timestamp overflow"); 122 } 123 124 parent 125 .timestamp_ms 126 .checked_add(finalizer_rank_slot_delay_ms(rank)?) 127 .context("finalizer rank minimum timestamp overflow") 128 } 129 130 pub(super) fn base_vdf_rounds_for_finalizer_rank(vdf_rounds: u64, rank: u32) -> u64 { 131 vdf_rounds / u64::from(rank.saturating_add(1).max(1)) 132 } 133 134 pub(super) fn tickets_created_by_block( 135 block: &Block, 136 profile: &LaunchProfile, 137 ) -> Result<Vec<BurnTicket>> { 138 let mut tickets = tickets_created_by_transactions(block.height, &block.transactions, profile)?; 139 for envelope in &block.transactions_v2 { 140 let encoded = decode_hex(envelope).context("transaction v2 envelope is not hexadecimal")?; 141 let (domain, transaction) = TransactionV2::decode(&encoded)?; 142 if !transaction.is_burn() { 143 continue; 144 } 145 let owner = transaction 146 .burn_legacy_owner()? 147 .context("transaction v2 burn owner is missing")?; 148 let amount = transaction.amount(); 149 let target_height = block 150 .height 151 .checked_add(profile.ticket_maturity_delay_heights) 152 .with_context(|| format!("ticket target height overflow at block {}", block.height))?; 153 let eligible_until_height = target_height 154 .checked_add(profile.ticket_expiry_window_heights - 1) 155 .with_context(|| format!("ticket expiry height overflow at block {}", block.height))?; 156 tickets.push(BurnTicket { 157 id: hex_encode(transaction.transaction_id(&domain)?), 158 owner, 159 amount, 160 eligible_from_height: target_height, 161 eligible_until_height, 162 }); 163 } 164 Ok(tickets) 165 } 166 167 pub(super) fn tickets_created_by_transactions( 168 block_height: u64, 169 transactions: &[Transaction], 170 profile: &LaunchProfile, 171 ) -> Result<Vec<BurnTicket>> { 172 if profile.ticket_expiry_window_heights == 0 { 173 bail!("ticket expiry window must be at least one height"); 174 } 175 let mut tickets = Vec::new(); 176 for tx in transactions { 177 let Transaction::Burn { 178 inputs, 179 amount, 180 signature, 181 .. 182 } = tx 183 else { 184 continue; 185 }; 186 let Some(owner) = inputs.first().map(|input| input.owner.clone()) else { 187 continue; 188 }; 189 if *amount == 0 { 190 continue; 191 } 192 let target_height = block_height 193 .checked_add(profile.ticket_maturity_delay_heights) 194 .with_context(|| format!("ticket target height overflow at block {block_height}"))?; 195 let eligible_until_height = target_height 196 .checked_add(profile.ticket_expiry_window_heights - 1) 197 .with_context(|| format!("ticket expiry height overflow at block {block_height}"))?; 198 tickets.push(BurnTicket { 199 id: signature.clone(), 200 owner, 201 amount: *amount, 202 eligible_from_height: target_height, 203 eligible_until_height, 204 }); 205 } 206 Ok(tickets) 207 } 208 209 pub(super) fn genesis_tickets( 210 genesis_allocations: &BTreeMap<String, Amount>, 211 genesis: &Block, 212 profile: &LaunchProfile, 213 ) -> Result<Vec<BurnTicket>> { 214 if profile.ticket_maturity_delay_heights == 0 { 215 return tickets_created_by_block(genesis, profile); 216 } 217 218 let burn_tickets = genesis 219 .transactions 220 .iter() 221 .filter_map(|tx| { 222 let Transaction::Burn { 223 inputs, 224 amount, 225 signature, 226 .. 227 } = tx 228 else { 229 return None; 230 }; 231 let owner = inputs.first()?.owner.clone(); 232 (*amount > 0).then(|| (owner, *amount, signature.clone())) 233 }) 234 .collect::<Vec<_>>(); 235 236 if !burn_tickets.is_empty() { 237 return genesis_bootstrap_tickets(burn_tickets, profile, genesis); 238 } 239 240 let Some((owner, amount)) = genesis_allocations 241 .iter() 242 .rev() 243 .find(|(_, amount)| **amount > 0) 244 else { 245 return Ok(Vec::new()); 246 }; 247 genesis_bootstrap_tickets( 248 vec![( 249 owner.clone(), 250 1, 251 hex_hash(format!( 252 "iuna-genesis-ticket:{owner}:{amount}:{}", 253 genesis.hash 254 )), 255 )], 256 profile, 257 genesis, 258 ) 259 } 260 261 fn genesis_bootstrap_tickets( 262 source_tickets: Vec<(String, Amount, String)>, 263 profile: &LaunchProfile, 264 genesis: &Block, 265 ) -> Result<Vec<BurnTicket>> { 266 let mut tickets = Vec::new(); 267 for height in 1..=profile.ticket_maturity_delay_heights { 268 for (owner, amount, source_id) in &source_tickets { 269 tickets.push(BurnTicket { 270 id: hex_hash(format!( 271 "iuna-genesis-bootstrap-ticket:{}:{source_id}:{height}", 272 genesis.hash 273 )), 274 owner: owner.clone(), 275 amount: *amount, 276 eligible_from_height: height, 277 eligible_until_height: height, 278 }); 279 } 280 } 281 Ok(tickets) 282 } 283 284 pub(super) fn apply_finalizer_ticket_effects( 285 parent: &Block, 286 block: &Block, 287 tickets: &mut Vec<BurnTicket>, 288 ) -> Result<()> { 289 match block.finalizer_mode { 290 FinalizerMode::Ticket => consume_leader_ticket(parent, block, tickets), 291 FinalizerMode::Recovery => { 292 tickets.retain(|ticket| { 293 !ticket_is_eligible_for_height(ticket, block.height) 294 && ticket.eligible_until_height > block.height 295 }); 296 Ok(()) 297 } 298 } 299 } 300 301 pub(super) fn consume_leader_ticket( 302 parent: &Block, 303 block: &Block, 304 tickets: &mut Vec<BurnTicket>, 305 ) -> Result<()> { 306 let Some(proof) = &block.leader_proof else { 307 bail!("block is missing leader proof"); 308 }; 309 if !tickets.iter().any(|ticket| { 310 ticket.id == proof.ticket_id && ticket_is_eligible_for_height(ticket, block.height) 311 }) { 312 bail!("leader ticket is not pending for block {}", block.height); 313 }; 314 let invalidated = invalidated_ticket_ids(parent, block, tickets, &proof.ticket_id); 315 tickets.retain(|ticket| { 316 !invalidated.contains(&ticket.id) && ticket.eligible_until_height > block.height 317 }); 318 Ok(()) 319 } 320 321 fn invalidated_ticket_ids( 322 parent: &Block, 323 block: &Block, 324 tickets: &[BurnTicket], 325 leader_ticket_id: &str, 326 ) -> std::collections::BTreeSet<String> { 327 let ranked_tickets = ranked_tickets_for_height(parent, block.height, tickets); 328 let Some(finalizer_index) = ranked_tickets 329 .iter() 330 .position(|ticket| ticket.id == leader_ticket_id) 331 else { 332 return [leader_ticket_id.to_string()].into(); 333 }; 334 if block.height < MISSED_FALLBACK_TICKET_INVALIDATION_HEIGHT || finalizer_index == 0 { 335 return [leader_ticket_id.to_string()].into(); 336 } 337 338 let missed_and_finalizer_owners = ranked_tickets 339 .iter() 340 .take(finalizer_index + 1) 341 .map(|ticket| ticket.owner.clone()) 342 .collect::<std::collections::BTreeSet<_>>(); 343 344 tickets 345 .iter() 346 .filter(|ticket| { 347 ticket_is_eligible_for_height(ticket, block.height) 348 && missed_and_finalizer_owners.contains(&ticket.owner) 349 }) 350 .map(|ticket| ticket.id.clone()) 351 .collect() 352 } 353 354 pub(super) fn ticket_is_eligible_for_height(ticket: &BurnTicket, height: u64) -> bool { 355 ticket.eligible_from_height <= height && height <= ticket.eligible_until_height 356 } 357 358 pub(super) fn mine_action_count(block: &Block) -> u64 { 359 block 360 .transactions 361 .iter() 362 .filter(|transaction| matches!(transaction, Transaction::Mine { .. })) 363 .count() as u64 364 } 365 366 #[cfg(test)] 367 mod tests { 368 use super::*; 369 use crate::domain::{BurnBundleSection, LeaderProof, TxInput}; 370 371 fn parent(height: u64) -> Block { 372 Block { 373 height, 374 prev_hash: "0".repeat(64), 375 timestamp_ms: 1_000, 376 miner: "parent".to_string(), 377 reward_address: None, 378 reward_address_signature: None, 379 finalizer_mode: FinalizerMode::Ticket, 380 finalizer_rank: 0, 381 reward: 0, 382 vdf_rounds: 100, 383 vdf_output: "parent-vdf-output".to_string(), 384 leader_proof: None, 385 burn_bundle_section: BurnBundleSection::default(), 386 transactions: Vec::new(), 387 transactions_v2: Vec::new(), 388 hash: "1".repeat(64), 389 } 390 } 391 392 #[test] 393 fn ticket_draw_stops_using_grindable_parent_hash_at_height_1000() { 394 let mut legacy_left = parent(GRINDING_RESISTANCE_ACTIVATION_HEIGHT - 2); 395 legacy_left.hash = "1".repeat(64); 396 let mut legacy_right = legacy_left.clone(); 397 legacy_right.hash = "2".repeat(64); 398 399 assert_ne!( 400 ticket_draw_seed(&legacy_left, GRINDING_RESISTANCE_ACTIVATION_HEIGHT - 1, 0), 401 ticket_draw_seed(&legacy_right, GRINDING_RESISTANCE_ACTIVATION_HEIGHT - 1, 0) 402 ); 403 404 let mut activated_left = parent(GRINDING_RESISTANCE_ACTIVATION_HEIGHT - 1); 405 activated_left.hash = "1".repeat(64); 406 let mut activated_right = activated_left.clone(); 407 activated_right.hash = "2".repeat(64); 408 assert_eq!( 409 ticket_draw_seed(&activated_left, GRINDING_RESISTANCE_ACTIVATION_HEIGHT, 0), 410 ticket_draw_seed(&activated_right, GRINDING_RESISTANCE_ACTIVATION_HEIGHT, 0) 411 ); 412 } 413 414 fn ticket(id: char, owner: &str, from: u64, until: u64) -> BurnTicket { 415 BurnTicket { 416 id: id.to_string().repeat(64), 417 owner: owner.to_string(), 418 amount: 1, 419 eligible_from_height: from, 420 eligible_until_height: until, 421 } 422 } 423 424 fn ticket_block(parent: &Block, height: u64, rank: u32, selected: &BurnTicket) -> Block { 425 Block { 426 height, 427 prev_hash: parent.hash.clone(), 428 timestamp_ms: ticket_block_min_timestamp(parent, rank).unwrap(), 429 miner: selected.owner.clone(), 430 reward_address: None, 431 reward_address_signature: None, 432 finalizer_mode: FinalizerMode::Ticket, 433 finalizer_rank: rank, 434 reward: 0, 435 vdf_rounds: vdf_rounds_for_finalizer_rank(100, rank).unwrap(), 436 vdf_output: "child-vdf-output".to_string(), 437 leader_proof: Some(LeaderProof { 438 ticket_id: selected.id.clone(), 439 public_key: selected.owner.clone(), 440 signature: "2".repeat(128), 441 }), 442 burn_bundle_section: BurnBundleSection::default(), 443 transactions: Vec::new(), 444 transactions_v2: Vec::new(), 445 hash: "3".repeat(64), 446 } 447 } 448 449 #[test] 450 fn burns_create_tickets_after_three_blocks_for_three_heights() { 451 let burn = Transaction::Burn { 452 inputs: vec![TxInput { 453 outpoint: super::super::OutPoint { 454 txid: "a".repeat(64), 455 index: 0, 456 }, 457 owner: "burner".to_string(), 458 signature: "b".repeat(128), 459 }], 460 change: Vec::new(), 461 amount: 42, 462 fee: 1, 463 anchor: None, 464 signature: "b".repeat(128), 465 }; 466 467 let tickets = 468 tickets_created_by_transactions(10, &[burn], &LaunchProfile::default()).unwrap(); 469 470 assert_eq!(tickets.len(), 1); 471 assert_eq!(tickets[0].amount, 42); 472 assert_eq!(tickets[0].eligible_from_height, 13); 473 assert_eq!(tickets[0].eligible_until_height, 15); 474 } 475 476 #[test] 477 fn ticket_draw_has_a_fixed_parent_vdf_height_rank_and_weight_vector() { 478 let parent = parent(41); 479 let tickets = vec![ 480 BurnTicket { 481 amount: 2, 482 ..ticket('a', "alice", 42, 42) 483 }, 484 BurnTicket { 485 amount: 3, 486 ..ticket('b', "bob", 42, 42) 487 }, 488 BurnTicket { 489 amount: 5, 490 ..ticket('c', "carol", 42, 42) 491 }, 492 ]; 493 494 let ranked = ranked_tickets_for_height(&parent, 42, &tickets) 495 .into_iter() 496 .map(|ticket| ticket.id) 497 .collect::<Vec<_>>(); 498 499 assert_eq!(ranked, vec!["c".repeat(64), "a".repeat(64), "b".repeat(64)]); 500 } 501 502 #[test] 503 fn fallback_consumes_missed_owners_current_tickets_but_keeps_future_tickets() { 504 assert_eq!(MISSED_FALLBACK_TICKET_INVALIDATION_HEIGHT, 300); 505 let parent = parent(299); 506 let mut tickets = vec![ 507 ticket('a', "alice", 300, 302), 508 ticket('b', "bob", 300, 302), 509 ticket('c', "carol", 300, 302), 510 ticket('d', "alice", 300, 302), 511 ticket('e', "bob", 301, 303), 512 ]; 513 let ranked = ranked_tickets_for_height(&parent, 300, &tickets); 514 let selected = ranked[1].clone(); 515 let missed_owner = ranked[0].owner.clone(); 516 let selected_owner = selected.owner.clone(); 517 let block = ticket_block(&parent, 300, 1, &selected); 518 519 consume_leader_ticket(&parent, &block, &mut tickets).unwrap(); 520 521 assert!(tickets.iter().all(|ticket| { 522 ticket.eligible_from_height > 300 523 || (ticket.owner != missed_owner && ticket.owner != selected_owner) 524 })); 525 assert!( 526 tickets.iter().any(|ticket| ticket.id == "e".repeat(64)), 527 "future tickets must remain pending" 528 ); 529 } 530 531 #[test] 532 fn fallback_before_activation_consumes_only_the_finalizing_ticket() { 533 let parent = parent(MISSED_FALLBACK_TICKET_INVALIDATION_HEIGHT - 2); 534 let height = MISSED_FALLBACK_TICKET_INVALIDATION_HEIGHT - 1; 535 let mut tickets = vec![ 536 ticket('a', "alice", height, height + 2), 537 ticket('b', "bob", height, height + 2), 538 ticket('c', "alice", height, height + 2), 539 ]; 540 let ranked = ranked_tickets_for_height(&parent, height, &tickets); 541 let missed_ticket_id = ranked[0].id.clone(); 542 let selected = ranked[1].clone(); 543 let block = ticket_block(&parent, height, 1, &selected); 544 545 consume_leader_ticket(&parent, &block, &mut tickets).unwrap(); 546 547 assert_eq!(tickets.len(), 2); 548 assert!(tickets.iter().all(|ticket| ticket.id != selected.id)); 549 assert!( 550 tickets.iter().any(|ticket| ticket.id == missed_ticket_id), 551 "the missed rank-0 ticket must survive before activation" 552 ); 553 } 554 555 #[test] 556 fn rank_zero_consumes_only_its_winning_ticket() { 557 let parent = parent(300); 558 let mut tickets = vec![ 559 ticket('a', "alice", 301, 303), 560 ticket('b', "alice", 301, 303), 561 ticket('c', "bob", 301, 303), 562 ]; 563 let selected = ranked_tickets_for_height(&parent, 301, &tickets)[0].clone(); 564 let block = ticket_block(&parent, 301, 0, &selected); 565 566 consume_leader_ticket(&parent, &block, &mut tickets).unwrap(); 567 568 assert_eq!(tickets.len(), 2); 569 assert!(tickets.iter().all(|ticket| ticket.id != selected.id)); 570 } 571 572 #[test] 573 fn fallback_vdf_rounds_and_time_slots_scale_with_rank() { 574 let parent = parent(10); 575 576 assert_eq!(vdf_rounds_for_finalizer_rank(100, 0).unwrap(), 100); 577 assert_eq!(vdf_rounds_for_finalizer_rank(100, 1).unwrap(), 200); 578 assert_eq!(vdf_rounds_for_finalizer_rank(100, 2).unwrap(), 300); 579 assert_eq!(ticket_block_min_timestamp(&parent, 0).unwrap(), 1_001); 580 assert_eq!( 581 ticket_block_min_timestamp(&parent, 1).unwrap(), 582 1_000 + 2 * VDF_TARGET_BLOCK_MS 583 ); 584 assert_eq!( 585 ticket_block_min_timestamp(&parent, 2).unwrap(), 586 1_000 + 4 * VDF_TARGET_BLOCK_MS 587 ); 588 } 589 }