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