ledger_lineage.rs (11354B)
1 use std::collections::BTreeMap; 2 3 use anyhow::{Context, Result, bail}; 4 5 use super::{Amount, OutPoint, Transaction, TxOutput}; 6 7 #[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)] 8 pub(super) struct UtxoLineageRoot { 9 pub(super) outpoint: OutPoint, 10 pub(super) height: u64, 11 } 12 13 pub(super) type LineageOwnerValues = 14 BTreeMap<UtxoLineageRoot, BTreeMap<String, BTreeMap<OutPoint, Amount>>>; 15 16 pub(super) fn spend_inputs_with_lineage( 17 transaction: &Transaction, 18 utxos: &mut BTreeMap<OutPoint, TxOutput>, 19 utxo_lineage: &mut BTreeMap<OutPoint, UtxoLineageRoot>, 20 lineage_values: &mut BTreeMap<UtxoLineageRoot, Amount>, 21 lineage_owners: &mut LineageOwnerValues, 22 ) -> Result<(Amount, Option<UtxoLineageRoot>)> { 23 let mut seen = std::collections::BTreeSet::new(); 24 let mut total = 0_u64; 25 let mut inherited_root = None; 26 for input in transaction.inputs() { 27 if !seen.insert(input.outpoint.clone()) { 28 bail!("duplicate input in transaction"); 29 } 30 let output = utxos.remove(&input.outpoint).with_context(|| { 31 format!("transaction spends missing output {}", input.outpoint.id()) 32 })?; 33 if output.address != input.owner { 34 bail!("transaction input owner does not match spent output"); 35 } 36 total = total 37 .checked_add(output.amount) 38 .context("transaction input total overflows")?; 39 if let Some(root) = utxo_lineage.remove(&input.outpoint) { 40 subtract_lineage_value(lineage_values, &root, output.amount)?; 41 subtract_lineage_owner_value(lineage_owners, &root, &output.address, &input.outpoint)?; 42 inherited_root = newest_lineage_root(inherited_root, Some(root)); 43 } 44 } 45 Ok((total, inherited_root)) 46 } 47 48 pub(super) fn insert_output_with_lineage( 49 outpoint: OutPoint, 50 output: TxOutput, 51 root: Option<UtxoLineageRoot>, 52 utxos: &mut BTreeMap<OutPoint, TxOutput>, 53 utxo_lineage: &mut BTreeMap<OutPoint, UtxoLineageRoot>, 54 lineage_values: &mut BTreeMap<UtxoLineageRoot, Amount>, 55 lineage_owners: &mut LineageOwnerValues, 56 ) -> Result<()> { 57 if utxos.insert(outpoint.clone(), output.clone()).is_some() { 58 bail!("created output replaces existing UTXO {}", outpoint.id()); 59 } 60 if let Some(root) = root { 61 utxo_lineage.insert(outpoint.clone(), root.clone()); 62 let value = lineage_values.entry(root.clone()).or_insert(0); 63 *value = value 64 .checked_add(output.amount) 65 .context("lineage value overflows")?; 66 lineage_owners 67 .entry(root) 68 .or_default() 69 .entry(output.address) 70 .or_default() 71 .insert(outpoint, output.amount); 72 } 73 Ok(()) 74 } 75 76 pub(super) fn newest_lineage_root( 77 left: Option<UtxoLineageRoot>, 78 right: Option<UtxoLineageRoot>, 79 ) -> Option<UtxoLineageRoot> { 80 match (left, right) { 81 (None, None) => None, 82 (Some(root), None) | (None, Some(root)) => Some(root), 83 (Some(left), Some(right)) => { 84 if (right.height, &right.outpoint) > (left.height, &left.outpoint) { 85 Some(right) 86 } else { 87 Some(left) 88 } 89 } 90 } 91 } 92 93 pub(super) fn output_lineage_root_for_transaction( 94 transaction: &Transaction, 95 block_height: u64, 96 inherited_root: Option<UtxoLineageRoot>, 97 ) -> Option<UtxoLineageRoot> { 98 match transaction { 99 Transaction::Mine { .. } => Some(UtxoLineageRoot { 100 outpoint: OutPoint { 101 txid: transaction.signature().to_string(), 102 index: 0, 103 }, 104 height: block_height, 105 }), 106 Transaction::Transfer { .. } | Transaction::Burn { .. } => inherited_root, 107 } 108 } 109 110 fn subtract_lineage_value( 111 lineage_values: &mut BTreeMap<UtxoLineageRoot, Amount>, 112 root: &UtxoLineageRoot, 113 amount: Amount, 114 ) -> Result<()> { 115 let value = lineage_values 116 .get_mut(root) 117 .context("lineage index is missing spent root")?; 118 *value = value 119 .checked_sub(amount) 120 .context("lineage value underflows")?; 121 if *value == 0 { 122 lineage_values.remove(root); 123 } 124 Ok(()) 125 } 126 127 fn subtract_lineage_owner_value( 128 lineage_owners: &mut LineageOwnerValues, 129 root: &UtxoLineageRoot, 130 owner: &str, 131 outpoint: &OutPoint, 132 ) -> Result<()> { 133 let owners = lineage_owners 134 .get_mut(root) 135 .context("lineage owner index is missing spent root")?; 136 let outputs = owners 137 .get_mut(owner) 138 .context("lineage owner index is missing spent owner")?; 139 outputs 140 .remove(outpoint) 141 .context("lineage owner index is missing spent output")?; 142 if outputs.is_empty() { 143 owners.remove(owner); 144 } 145 if owners.is_empty() { 146 lineage_owners.remove(root); 147 } 148 Ok(()) 149 } 150 151 pub(super) fn remove_spent_output_lineage( 152 outpoint: &OutPoint, 153 output: &TxOutput, 154 utxo_lineage: &mut BTreeMap<OutPoint, UtxoLineageRoot>, 155 lineage_values: &mut BTreeMap<UtxoLineageRoot, Amount>, 156 lineage_owners: &mut LineageOwnerValues, 157 ) -> Result<Option<UtxoLineageRoot>> { 158 let Some(root) = utxo_lineage.remove(outpoint) else { 159 return Ok(None); 160 }; 161 subtract_lineage_value(lineage_values, &root, output.amount)?; 162 subtract_lineage_owner_value(lineage_owners, &root, &output.address, outpoint)?; 163 Ok(Some(root)) 164 } 165 166 pub(super) fn attach_existing_output_lineage( 167 outpoint: OutPoint, 168 output: &TxOutput, 169 root: UtxoLineageRoot, 170 utxo_lineage: &mut BTreeMap<OutPoint, UtxoLineageRoot>, 171 lineage_values: &mut BTreeMap<UtxoLineageRoot, Amount>, 172 lineage_owners: &mut LineageOwnerValues, 173 ) -> Result<()> { 174 if utxo_lineage 175 .insert(outpoint.clone(), root.clone()) 176 .is_some() 177 { 178 bail!("created output replaces existing UTXO lineage"); 179 } 180 let value = lineage_values.entry(root.clone()).or_insert(0); 181 *value = value 182 .checked_add(output.amount) 183 .context("lineage value overflows")?; 184 lineage_owners 185 .entry(root) 186 .or_default() 187 .entry(output.address.clone()) 188 .or_default() 189 .insert(outpoint, output.amount); 190 Ok(()) 191 } 192 193 #[cfg(test)] 194 mod tests { 195 use super::*; 196 use crate::domain::{TxInput, Wallet}; 197 198 fn root(txid: char, height: u64) -> UtxoLineageRoot { 199 UtxoLineageRoot { 200 outpoint: OutPoint { 201 txid: txid.to_string().repeat(64), 202 index: 0, 203 }, 204 height, 205 } 206 } 207 208 #[test] 209 fn newest_lineage_uses_height_then_deterministic_outpoint_tiebreak() { 210 let old = root('f', 4); 211 let same_age_low = root('1', 5); 212 let same_age_high = root('2', 5); 213 214 assert_eq!( 215 newest_lineage_root(Some(old), Some(same_age_low.clone())), 216 Some(same_age_low.clone()) 217 ); 218 assert_eq!( 219 newest_lineage_root(Some(same_age_low), Some(same_age_high.clone())), 220 Some(same_age_high) 221 ); 222 assert_eq!(newest_lineage_root(None, None), None); 223 } 224 225 #[test] 226 fn transfer_descendants_inherit_the_newest_spent_mine_root() { 227 let wallet = Wallet::from_seed("lineage-merge-wallet"); 228 let older = root('1', 4); 229 let newer = root('2', 5); 230 let older_outpoint = OutPoint { 231 txid: "a".repeat(64), 232 index: 0, 233 }; 234 let newer_outpoint = OutPoint { 235 txid: "b".repeat(64), 236 index: 0, 237 }; 238 let transaction = Transaction::Transfer { 239 inputs: vec![ 240 TxInput { 241 outpoint: older_outpoint.clone(), 242 owner: wallet.address().to_string(), 243 signature: "s".repeat(128), 244 }, 245 TxInput { 246 outpoint: newer_outpoint.clone(), 247 owner: wallet.address().to_string(), 248 signature: "s".repeat(128), 249 }, 250 ], 251 outputs: vec![TxOutput { 252 address: wallet.address().to_string(), 253 amount: 12, 254 }], 255 fee: 1, 256 signature: "s".repeat(128), 257 }; 258 let mut utxos = BTreeMap::from([ 259 ( 260 older_outpoint.clone(), 261 TxOutput { 262 address: wallet.address().to_string(), 263 amount: 5, 264 }, 265 ), 266 ( 267 newer_outpoint.clone(), 268 TxOutput { 269 address: wallet.address().to_string(), 270 amount: 8, 271 }, 272 ), 273 ]); 274 let mut utxo_lineage = BTreeMap::from([ 275 (older_outpoint.clone(), older.clone()), 276 (newer_outpoint.clone(), newer.clone()), 277 ]); 278 let mut lineage_values = BTreeMap::from([(older.clone(), 5), (newer.clone(), 8)]); 279 let mut lineage_owners = BTreeMap::from([ 280 ( 281 older.clone(), 282 BTreeMap::from([( 283 wallet.address().to_string(), 284 BTreeMap::from([(older_outpoint, 5)]), 285 )]), 286 ), 287 ( 288 newer.clone(), 289 BTreeMap::from([( 290 wallet.address().to_string(), 291 BTreeMap::from([(newer_outpoint, 8)]), 292 )]), 293 ), 294 ]); 295 296 let (_, inherited) = spend_inputs_with_lineage( 297 &transaction, 298 &mut utxos, 299 &mut utxo_lineage, 300 &mut lineage_values, 301 &mut lineage_owners, 302 ) 303 .unwrap(); 304 assert_eq!(inherited, Some(newer.clone())); 305 306 let descendant = OutPoint { 307 txid: "c".repeat(64), 308 index: 0, 309 }; 310 insert_output_with_lineage( 311 descendant.clone(), 312 TxOutput { 313 address: wallet.address().to_string(), 314 amount: 12, 315 }, 316 inherited, 317 &mut utxos, 318 &mut utxo_lineage, 319 &mut lineage_values, 320 &mut lineage_owners, 321 ) 322 .unwrap(); 323 324 assert_eq!(utxo_lineage.get(&descendant), Some(&newer)); 325 assert_eq!(lineage_values, BTreeMap::from([(newer, 12)])); 326 } 327 328 #[test] 329 fn mine_outputs_start_roots_and_unrooted_outputs_stay_unweighted() { 330 let mine = Transaction::Mine { 331 recipient: "recipient".to_string(), 332 anchor: "a".repeat(64), 333 salt: 1, 334 nonce: 1, 335 difficulty_bits: 10, 336 proof_header: None, 337 signature: "b".repeat(64), 338 }; 339 let transfer = Transaction::Transfer { 340 inputs: Vec::new(), 341 outputs: Vec::new(), 342 fee: 1, 343 signature: "c".repeat(128), 344 }; 345 346 assert_eq!( 347 output_lineage_root_for_transaction(&mine, 20, None), 348 Some(UtxoLineageRoot { 349 outpoint: OutPoint { 350 txid: "b".repeat(64), 351 index: 0, 352 }, 353 height: 20, 354 }) 355 ); 356 assert_eq!( 357 output_lineage_root_for_transaction(&transfer, 20, None), 358 None 359 ); 360 } 361 }