ledger_pending.rs (24080B)
1 use std::collections::{BTreeMap, BTreeSet}; 2 3 use anyhow::{Context, Result, bail}; 4 5 use super::blinded::{ 6 ActiveBlindedTransaction, blinded_envelope_fee_for_transaction, blinded_locked_output_total, 7 blinded_reveal_inputs_match, blinded_transaction_commitment, decrypt_blinded_transaction, 8 verify_blinded_input_signatures, 9 }; 10 use super::ledger_ops::{ 11 apply_spendable_pending_transaction, apply_transaction, best_selectable_blinded_index, 12 best_selectable_burn_from_index, best_selectable_transaction_index, 13 ensure_blinded_transaction_fits_empty_block, ensure_outputs_do_not_overflow, 14 ensure_single_input_owner, ensure_transaction_fits_empty_block, 15 estimated_block_selection_size_bytes, spend_blinded_inputs, spend_spendable_blinded_inputs, 16 transaction_has_missing_inputs, validate_transaction_inputs, validate_transaction_outputs, 17 }; 18 use super::mine_policy::{ 19 MINE_MAX_ANCHOR_AGE_BLOCKS, mine_anchor, mine_anchor_count_before_height, 20 }; 21 use super::selection::{ 22 BlockSelection, SelectableItem, TransactionKind, best_selectable_item, blinded_fee_rate_key, 23 fee_rate_key, 24 }; 25 use super::transaction::{ 26 UnsignedTxInput, transaction_inputs_available, transaction_inputs_spent_by, 27 }; 28 use super::validation::{ 29 validate_address, validate_hash, validate_signature, validate_stratum_header, 30 }; 31 use super::{ 32 Amount, BLINDED_KEY_BYTES, BLINDED_NONCE_BYTES, BlindedReveal, BlindedTransaction, Ledger, 33 MAX_BLINDED_TRANSACTION_EXPIRY_HEIGHTS, MAX_PENDING_TRANSACTIONS, 34 MINE_ACTIONS_PER_ANCHOR_LIMIT, OutPoint, Transaction, TxOutput, decode_hex, decode_hex_array, 35 }; 36 37 impl Ledger { 38 pub(super) fn valid_pending_transactions(&self) -> Vec<Transaction> { 39 let mut utxos = self.utxos.clone(); 40 let mut valid = Vec::new(); 41 let mut remaining = self.pending.iter().collect::<Vec<_>>(); 42 let mut selected_mine_anchor_counts = BTreeMap::new(); 43 44 while !remaining.is_empty() { 45 let mut progressed = false; 46 let mut still_pending = Vec::new(); 47 48 for tx in remaining { 49 if let Some(anchor) = mine_anchor(tx) { 50 let selected = selected_mine_anchor_counts 51 .get(anchor) 52 .copied() 53 .unwrap_or_default(); 54 if mine_anchor_count_before_height(&self.chain, anchor, self.height()) 55 .saturating_add(selected) 56 >= MINE_ACTIONS_PER_ANCHOR_LIMIT 57 { 58 continue; 59 } 60 } 61 if transaction_inputs_available(tx, &utxos) 62 && self.validate_transaction_terms(tx).is_ok() 63 && apply_transaction(tx, &mut utxos).is_ok() 64 { 65 if let Some(anchor) = mine_anchor(tx) { 66 selected_mine_anchor_counts 67 .entry(anchor) 68 .and_modify(|count| *count += 1) 69 .or_insert(1); 70 } 71 valid.push(tx.clone()); 72 progressed = true; 73 } else { 74 still_pending.push(tx); 75 } 76 } 77 78 if !progressed { 79 break; 80 } 81 82 remaining = still_pending; 83 } 84 85 valid 86 } 87 88 pub(super) fn select_block_transactions( 89 &self, 90 required_burn_signature: Option<&str>, 91 ) -> Result<BlockSelection> { 92 self.select_block_transactions_with_required_burn_owner(None, required_burn_signature) 93 } 94 95 pub(super) fn select_recovery_block_transactions( 96 &self, 97 miner: &str, 98 required_burn_signature: Option<&str>, 99 ) -> Result<BlockSelection> { 100 self.select_block_transactions_with_required_burn_owner( 101 Some(miner), 102 required_burn_signature, 103 ) 104 } 105 106 pub(super) fn select_block_transactions_with_required_burn_owner( 107 &self, 108 required_burn_owner: Option<&str>, 109 required_burn_signature: Option<&str>, 110 ) -> Result<BlockSelection> { 111 let mut utxos = self.utxos.clone(); 112 let mut remaining = self.valid_pending_transactions(); 113 let mut remaining_blinded = self.valid_pending_blinded_transactions(); 114 let mut selected = Vec::new(); 115 let mut selected_blinded = Vec::new(); 116 117 if let Some(signature) = required_burn_signature { 118 let index = remaining 119 .iter() 120 .position(|transaction| transaction.signature() == signature) 121 .with_context(|| format!("required burn {signature} is not pending"))?; 122 let tx = remaining.remove(index); 123 if !tx.is_burn() { 124 bail!("required block anchor must be a burn transaction"); 125 } 126 if let Some(owner) = required_burn_owner { 127 if tx.sender() != owner { 128 bail!("required block anchor burn must be from the recovery finalizer"); 129 } 130 } 131 let candidate = BlockSelection { 132 transactions: vec![tx.clone()], 133 blinded_transactions: selected_blinded.clone(), 134 }; 135 if estimated_block_selection_size_bytes(&candidate, required_burn_owner.is_some())? 136 > self.launch_profile.max_block_bytes 137 { 138 bail!("required block anchor burn does not fit in the block"); 139 } 140 apply_transaction(&tx, &mut utxos) 141 .context("required block anchor burn is not spendable")?; 142 selected.push(tx); 143 } 144 145 let needs_first_burn = !selected.iter().any(Transaction::is_burn); 146 let needs_owner_burn = required_burn_owner.is_some_and(|owner| { 147 !selected 148 .iter() 149 .any(|transaction| transaction.is_burn() && transaction.sender() == owner) 150 }); 151 if needs_first_burn || needs_owner_burn { 152 let first_burn_index = if let Some(owner) = required_burn_owner { 153 best_selectable_burn_from_index(&remaining, &utxos, owner) 154 } else { 155 best_selectable_transaction_index(&remaining, &utxos, Some(TransactionKind::Burn)) 156 }; 157 if let Some(index) = first_burn_index { 158 let tx = remaining.remove(index); 159 let mut candidate = BlockSelection { 160 transactions: selected.clone(), 161 blinded_transactions: selected_blinded.clone(), 162 }; 163 candidate.transactions.push(tx.clone()); 164 if estimated_block_selection_size_bytes(&candidate, required_burn_owner.is_some())? 165 <= self.launch_profile.max_block_bytes 166 { 167 apply_transaction(&tx, &mut utxos)?; 168 selected.push(tx); 169 } 170 } 171 } 172 173 while selected.len() < self.launch_profile.max_block_transactions { 174 let selected_count = selected.len() + selected_blinded.len(); 175 if selected_count >= self.launch_profile.max_block_transactions { 176 break; 177 } 178 179 let best_plain = best_selectable_transaction_index(&remaining, &utxos, None) 180 .map(|index| SelectableItem::Plain(index, fee_rate_key(&remaining[index]))); 181 let best_blinded = 182 best_selectable_blinded_index(&remaining_blinded, &utxos).map(|index| { 183 SelectableItem::Blinded(index, blinded_fee_rate_key(&remaining_blinded[index])) 184 }); 185 let Some(item) = best_selectable_item(best_plain, best_blinded) else { 186 break; 187 }; 188 189 match item { 190 SelectableItem::Plain(index, _) => { 191 let tx = remaining.remove(index); 192 let mut candidate = BlockSelection { 193 transactions: selected.clone(), 194 blinded_transactions: selected_blinded.clone(), 195 }; 196 candidate.transactions.push(tx.clone()); 197 if estimated_block_selection_size_bytes( 198 &candidate, 199 required_burn_owner.is_some(), 200 )? <= self.launch_profile.max_block_bytes 201 { 202 apply_transaction(&tx, &mut utxos)?; 203 selected.push(tx); 204 } 205 } 206 SelectableItem::Blinded(index, _) => { 207 let transaction = remaining_blinded.remove(index); 208 let mut candidate = BlockSelection { 209 transactions: selected.clone(), 210 blinded_transactions: selected_blinded.clone(), 211 }; 212 candidate.blinded_transactions.push(transaction.clone()); 213 if estimated_block_selection_size_bytes( 214 &candidate, 215 required_burn_owner.is_some(), 216 )? <= self.launch_profile.max_block_bytes 217 { 218 spend_blinded_inputs(&transaction, &mut utxos)?; 219 selected_blinded.push(transaction); 220 } 221 } 222 } 223 } 224 Ok(BlockSelection { 225 transactions: selected, 226 blinded_transactions: selected_blinded, 227 }) 228 } 229 230 pub(super) fn select_inputs( 231 &self, 232 address: &str, 233 amount: Amount, 234 ) -> Result<(Vec<UnsignedTxInput>, Amount)> { 235 let utxos = self.utxos_after_spendable_pending()?; 236 let mut selected = Vec::new(); 237 let mut total = 0_u64; 238 for (outpoint, output) in &utxos { 239 if output.address != address { 240 continue; 241 } 242 selected.push(UnsignedTxInput { 243 outpoint: outpoint.clone(), 244 owner: address.to_string(), 245 }); 246 total = total 247 .checked_add(output.amount) 248 .context("selected input total overflows")?; 249 if total >= amount { 250 return Ok((selected, total)); 251 } 252 } 253 bail!("insufficient funds for {address}") 254 } 255 256 pub(super) fn select_inputs_by_outpoint( 257 &self, 258 address: &str, 259 amount: Amount, 260 outpoints: &[OutPoint], 261 ) -> Result<(Vec<UnsignedTxInput>, Amount)> { 262 if outpoints.is_empty() { 263 bail!("at least one UTXO must be selected"); 264 } 265 let utxos = self.utxos_after_spendable_pending()?; 266 let mut seen = BTreeSet::new(); 267 let mut selected = Vec::new(); 268 let mut total = 0_u64; 269 for outpoint in outpoints { 270 if !seen.insert(outpoint.clone()) { 271 bail!("selected UTXO {} is duplicated", outpoint.id()); 272 } 273 let output = utxos 274 .get(outpoint) 275 .with_context(|| format!("selected UTXO {} is not spendable", outpoint.id()))?; 276 if output.address != address { 277 bail!("selected UTXO {} is not owned by {address}", outpoint.id()); 278 } 279 selected.push(UnsignedTxInput { 280 outpoint: outpoint.clone(), 281 owner: address.to_string(), 282 }); 283 total = total 284 .checked_add(output.amount) 285 .context("selected input total overflows")?; 286 } 287 if total < amount { 288 bail!("selected UTXOs do not cover amount plus fee"); 289 } 290 Ok((selected, total)) 291 } 292 293 pub(super) fn validate_new_transaction(&self, transaction: &Transaction) -> Result<()> { 294 self.validate_transaction_terms(transaction)?; 295 ensure_transaction_fits_empty_block(transaction, self.launch_profile.max_block_bytes)?; 296 self.validate_mine_anchor_available(transaction)?; 297 let mut utxos = self.utxos_after_spendable_pending()?; 298 apply_transaction(transaction, &mut utxos) 299 } 300 301 pub(super) fn validate_mine_anchor_available(&self, transaction: &Transaction) -> Result<()> { 302 if let Some(anchor) = mine_anchor(transaction) { 303 let known_count = mine_anchor_count_before_height(&self.chain, anchor, self.height()) 304 .saturating_add( 305 self.pending 306 .iter() 307 .filter(|tx| mine_anchor(tx) == Some(anchor)) 308 .count(), 309 ) 310 .saturating_add( 311 self.orphans 312 .iter() 313 .filter(|tx| { 314 mine_anchor(tx) == Some(anchor) 315 && tx.signature() != transaction.signature() 316 }) 317 .count(), 318 ); 319 if known_count >= MINE_ACTIONS_PER_ANCHOR_LIMIT { 320 bail!("mine transaction anchor limit reached"); 321 } 322 } 323 Ok(()) 324 } 325 326 pub(super) fn promote_orphan_transactions(&mut self) -> Result<()> { 327 loop { 328 if self.pending.len() >= MAX_PENDING_TRANSACTIONS { 329 return Ok(()); 330 } 331 let mut promoted_index = None; 332 let mut utxos = self.utxos_after_valid_pending_and_blinded()?; 333 for (index, transaction) in self.orphans.iter().enumerate() { 334 if transaction_inputs_spent_by(transaction, &self.pending) { 335 continue; 336 } 337 if transaction_has_missing_inputs(transaction, &utxos) { 338 continue; 339 } 340 if self.validate_new_transaction(transaction).is_ok() 341 && apply_transaction(transaction, &mut utxos).is_ok() 342 { 343 promoted_index = Some(index); 344 break; 345 } 346 } 347 348 let Some(index) = promoted_index else { 349 return Ok(()); 350 }; 351 self.pending.push(self.orphans.remove(index)); 352 } 353 } 354 355 pub(super) fn validate_transaction_terms(&self, transaction: &Transaction) -> Result<()> { 356 match transaction { 357 Transaction::Transfer { 358 inputs, 359 outputs, 360 signature, 361 .. 362 } => { 363 validate_transaction_inputs(inputs)?; 364 validate_transaction_outputs(outputs)?; 365 validate_signature(signature, "transaction signature")?; 366 } 367 Transaction::Burn { 368 inputs, 369 change, 370 signature, 371 .. 372 } => { 373 validate_transaction_inputs(inputs)?; 374 validate_transaction_outputs(change)?; 375 validate_signature(signature, "transaction signature")?; 376 } 377 Transaction::Mine { 378 recipient, 379 anchor, 380 difficulty_bits, 381 proof_header, 382 signature, 383 .. 384 } => { 385 validate_address(recipient, "mine recipient")?; 386 validate_hash(anchor, "mine transaction anchor")?; 387 validate_hash(signature, "mine transaction proof hash")?; 388 if let Some(proof_header) = proof_header { 389 validate_stratum_header(proof_header)?; 390 } 391 let anchor_block = self 392 .chain 393 .iter() 394 .find(|block| block.hash == *anchor) 395 .context("mine transaction anchor is not on this chain")?; 396 let anchor_age = self.tip().height.saturating_sub(anchor_block.height); 397 if anchor_age > MINE_MAX_ANCHOR_AGE_BLOCKS { 398 bail!("mine transaction anchor is too old"); 399 } 400 let required_difficulty = 401 self.mine_difficulty_bits_for_anchor_height(anchor_block.height); 402 if *difficulty_bits != required_difficulty { 403 bail!("mine transaction difficulty is invalid"); 404 } 405 } 406 } 407 Ok(()) 408 } 409 410 pub(super) fn validate_blinded_transaction( 411 &self, 412 transaction: &BlindedTransaction, 413 ) -> Result<()> { 414 validate_hash(&transaction.commitment, "blinded transaction commitment")?; 415 validate_hash( 416 &transaction.payload_hash, 417 "blinded transaction payload hash", 418 )?; 419 decode_hex_array::<BLINDED_NONCE_BYTES>(&transaction.nonce) 420 .context("invalid blinded transaction nonce")?; 421 let ciphertext = decode_hex(&transaction.ciphertext) 422 .context("invalid blinded transaction ciphertext")?; 423 if ciphertext.is_empty() { 424 bail!("blinded transaction ciphertext is empty"); 425 } 426 if ciphertext.len() != transaction.encrypted_size as usize { 427 bail!("blinded transaction encrypted size is invalid"); 428 } 429 if transaction.expires_at_height <= self.height() { 430 bail!("blinded transaction is expired"); 431 } 432 if transaction.expires_at_height 433 > self 434 .height() 435 .saturating_add(MAX_BLINDED_TRANSACTION_EXPIRY_HEIGHTS) 436 { 437 bail!("blinded transaction expiry is too far in the future"); 438 } 439 validate_transaction_inputs(&transaction.inputs)?; 440 if transaction.inputs.is_empty() && transaction.fee > 0 { 441 bail!("blinded transaction with a fee must lock visible inputs"); 442 } 443 if !transaction.inputs.is_empty() { 444 verify_blinded_input_signatures(transaction)?; 445 } 446 let expected = blinded_transaction_commitment(transaction)?; 447 if transaction.commitment != expected { 448 bail!("blinded transaction commitment is invalid"); 449 } 450 ensure_blinded_transaction_fits_empty_block( 451 transaction, 452 self.launch_profile.max_block_bytes, 453 )?; 454 Ok(()) 455 } 456 457 pub(super) fn validate_blinded_reveal_terms(&self, reveal: &BlindedReveal) -> Result<()> { 458 validate_hash(&reveal.commitment, "blinded reveal commitment")?; 459 decode_hex_array::<BLINDED_KEY_BYTES>(&reveal.key).context("invalid blinded reveal key")?; 460 Ok(()) 461 } 462 463 pub(super) fn valid_pending_blinded_transactions(&self) -> Vec<BlindedTransaction> { 464 let next_height = self.height().saturating_add(1); 465 self.pending_blinded 466 .iter() 467 .filter(|transaction| { 468 transaction.expires_at_height > next_height 469 && self.validate_blinded_transaction(transaction).is_ok() 470 }) 471 .cloned() 472 .collect() 473 } 474 475 pub(super) fn valid_pending_blinded_reveals(&self) -> Vec<BlindedReveal> { 476 self.pending_reveals 477 .iter() 478 .filter(|reveal| self.pending_reveal_transaction(reveal).is_ok()) 479 .cloned() 480 .collect() 481 } 482 483 pub(super) fn reveal_fee_order_key(&self, reveal: &BlindedReveal) -> (u128, Amount) { 484 let Some(active) = self.active_blinded.get(&reveal.commitment) else { 485 return (0, 0); 486 }; 487 let size = active.transaction.fee_rate_size_bytes(); 488 let rate = if size == 0 { 489 0 490 } else { 491 u128::from(active.transaction.fee) * 1_000_000 / size as u128 492 }; 493 (rate, active.transaction.fee) 494 } 495 496 pub(super) fn pending_reveal_transaction(&self, reveal: &BlindedReveal) -> Result<Transaction> { 497 self.validate_blinded_reveal_terms(reveal)?; 498 let active = self 499 .active_blinded 500 .get(&reveal.commitment) 501 .context("blinded reveal does not reference an active blinded transaction")?; 502 self.decrypt_active_blinded(active, reveal) 503 } 504 505 pub(super) fn decrypt_active_blinded( 506 &self, 507 active: &ActiveBlindedTransaction, 508 reveal: &BlindedReveal, 509 ) -> Result<Transaction> { 510 if self.height() >= active.transaction.expires_at_height { 511 bail!("blinded transaction reveal is expired"); 512 } 513 let transaction = decrypt_blinded_transaction(&active.transaction, reveal)?; 514 if matches!(transaction, Transaction::Mine { .. }) { 515 bail!("mine actions are public and cannot be blinded"); 516 } 517 if blinded_envelope_fee_for_transaction(&transaction) != active.transaction.fee { 518 bail!("blinded transaction reveal fee does not match envelope"); 519 } 520 if !blinded_reveal_inputs_match(active, &transaction) { 521 bail!("blinded transaction reveal inputs do not match envelope"); 522 } 523 self.validate_transaction_terms(&transaction)?; 524 Ok(transaction) 525 } 526 527 pub(super) fn apply_revealed_blinded_transaction( 528 &self, 529 active: &ActiveBlindedTransaction, 530 transaction: &Transaction, 531 utxos: &mut BTreeMap<OutPoint, TxOutput>, 532 ) -> Result<()> { 533 if matches!(transaction, Transaction::Mine { .. }) { 534 bail!("mine actions are public and cannot be blinded"); 535 } 536 transaction.verify_signature()?; 537 ensure_single_input_owner(transaction)?; 538 let input_total = blinded_locked_output_total(active)?; 539 let outputs = transaction.outputs(); 540 let output_total = outputs.iter().try_fold(0_u64, |total, output| { 541 total 542 .checked_add(output.amount) 543 .context("transaction outputs overflow") 544 })?; 545 let required = output_total 546 .checked_add(transaction.fee()) 547 .context("transaction outputs plus fee overflow")? 548 .checked_add(match transaction { 549 Transaction::Burn { amount, .. } => *amount, 550 Transaction::Transfer { .. } | Transaction::Mine { .. } => 0, 551 }) 552 .context("transaction outputs plus burn overflow")?; 553 if input_total != required { 554 bail!("blinded transaction inputs do not balance outputs, burn, and fee"); 555 } 556 ensure_outputs_do_not_overflow(utxos, &outputs)?; 557 for (index, output) in outputs.iter().enumerate() { 558 utxos.insert( 559 OutPoint { 560 txid: transaction.signature().to_string(), 561 index: index as u32, 562 }, 563 output.clone(), 564 ); 565 } 566 Ok(()) 567 } 568 569 pub(super) fn utxos_after_valid_pending(&self) -> Result<BTreeMap<OutPoint, TxOutput>> { 570 let mut utxos = self.utxos.clone(); 571 for pending in self.valid_pending_transactions() { 572 apply_transaction(&pending, &mut utxos)?; 573 } 574 Ok(utxos) 575 } 576 577 pub(super) fn utxos_after_valid_pending_and_blinded( 578 &self, 579 ) -> Result<BTreeMap<OutPoint, TxOutput>> { 580 let mut utxos = self.utxos_after_valid_pending()?; 581 for pending in self.valid_pending_blinded_transactions() { 582 spend_blinded_inputs(&pending, &mut utxos)?; 583 } 584 Ok(utxos) 585 } 586 587 pub(super) fn utxos_after_spendable_pending(&self) -> Result<BTreeMap<OutPoint, TxOutput>> { 588 let mut utxos = self.utxos.clone(); 589 for pending in self.valid_pending_transactions() { 590 if matches!(pending, Transaction::Mine { .. }) { 591 continue; 592 } 593 if apply_spendable_pending_transaction(&pending, &mut utxos).is_err() { 594 continue; 595 } 596 } 597 for pending in self.valid_pending_blinded_transactions() { 598 if spend_spendable_blinded_inputs(&pending, &mut utxos).is_err() { 599 continue; 600 } 601 } 602 Ok(utxos) 603 } 604 }