ledger_chain.rs (12176B)
1 use std::collections::{BTreeMap, BTreeSet}; 2 3 use anyhow::{Result, bail}; 4 5 use super::fork::{ForkChoice, ForkPoint, ForkQuality}; 6 use super::genesis::{build_genesis_block, utxos_after_genesis, validate_genesis_block}; 7 use super::ledger_ops::validate_genesis_allocations; 8 use super::ticket::genesis_tickets; 9 use super::{ 10 Amount, Block, ChainSnapshot, GenesisBurn, LaunchProfile, Ledger, MINE_REWARD, Transaction, 11 unix_now_ms, 12 }; 13 14 impl Ledger { 15 pub fn new(genesis_allocations: BTreeMap<String, Amount>, vdf_rounds: u64) -> Self { 16 Self::new_with_genesis_transactions(genesis_allocations, Vec::new(), vdf_rounds) 17 .expect("empty genesis transactions are valid") 18 } 19 20 pub fn new_with_genesis_burns( 21 genesis_allocations: BTreeMap<String, Amount>, 22 genesis_burns: Vec<GenesisBurn>, 23 vdf_rounds: u64, 24 ) -> Result<Self> { 25 let transactions = genesis_burns 26 .into_iter() 27 .map(|burn| { 28 let allocation = genesis_allocations 29 .get(&burn.from) 30 .copied() 31 .unwrap_or_default(); 32 Transaction::genesis_burn_with_allocation(burn.from, burn.amount, allocation) 33 }) 34 .collect::<Result<Vec<_>>>()?; 35 Self::new_with_genesis_transactions(genesis_allocations, transactions, vdf_rounds) 36 } 37 38 fn new_with_genesis_transactions( 39 genesis_allocations: BTreeMap<String, Amount>, 40 genesis_transactions: Vec<Transaction>, 41 vdf_rounds: u64, 42 ) -> Result<Self> { 43 validate_genesis_allocations(&genesis_allocations)?; 44 let launch_profile = LaunchProfile::default(); 45 let genesis = build_genesis_block(&genesis_allocations, genesis_transactions); 46 let utxos = utxos_after_genesis(&genesis_allocations, &genesis)?; 47 let tickets = genesis_tickets(&genesis_allocations, &genesis, &launch_profile)?; 48 Ok(Self { 49 chain: vec![genesis], 50 genesis_allocations: genesis_allocations.clone(), 51 utxos, 52 tickets, 53 pending: Vec::new(), 54 orphans: Vec::new(), 55 pending_blinded: Vec::new(), 56 pending_reveals: Vec::new(), 57 active_blinded: BTreeMap::new(), 58 mine_reward: MINE_REWARD, 59 initial_vdf_rounds: vdf_rounds, 60 vdf_rounds, 61 launch_profile, 62 }) 63 } 64 65 pub fn from_snapshot(snapshot: ChainSnapshot) -> Result<Self> { 66 Self::from_snapshot_at(snapshot, unix_now_ms()) 67 } 68 69 pub fn from_persisted_snapshot(snapshot: ChainSnapshot) -> Result<Self> { 70 Self::from_snapshot_at(snapshot, u64::MAX) 71 } 72 73 pub(crate) fn from_snapshot_at(snapshot: ChainSnapshot, now_ms: u64) -> Result<Self> { 74 Self::from_snapshot_with_vdf_policy(snapshot, true, now_ms) 75 } 76 77 fn from_snapshot_with_vdf_policy( 78 snapshot: ChainSnapshot, 79 verify_vdf: bool, 80 now_ms: u64, 81 ) -> Result<Self> { 82 let ChainSnapshot { 83 genesis_allocations, 84 vdf_rounds, 85 launch_profile, 86 blocks, 87 } = snapshot; 88 89 if blocks.is_empty() { 90 bail!("chain snapshot is empty"); 91 } 92 93 validate_genesis_allocations(&genesis_allocations)?; 94 let genesis = blocks[0].clone(); 95 validate_genesis_block(&genesis)?; 96 let expected_genesis = 97 build_genesis_block(&genesis_allocations, genesis.transactions.clone()); 98 if genesis != expected_genesis { 99 bail!("chain snapshot genesis does not match its allocations and transactions"); 100 } 101 let utxos = utxos_after_genesis(&genesis_allocations, &genesis)?; 102 103 let mut ledger = Self { 104 chain: vec![genesis], 105 genesis_allocations, 106 utxos, 107 tickets: Vec::new(), 108 pending: Vec::new(), 109 orphans: Vec::new(), 110 pending_blinded: Vec::new(), 111 pending_reveals: Vec::new(), 112 active_blinded: BTreeMap::new(), 113 mine_reward: MINE_REWARD, 114 initial_vdf_rounds: vdf_rounds, 115 vdf_rounds, 116 launch_profile, 117 }; 118 ledger.tickets = genesis_tickets( 119 &ledger.genesis_allocations, 120 ledger.tip(), 121 &ledger.launch_profile, 122 )?; 123 124 for block in blocks.into_iter().skip(1) { 125 if verify_vdf { 126 ledger.apply_block_at(block, now_ms)?; 127 } else { 128 ledger.apply_preverified_block_at(block, now_ms)?; 129 } 130 } 131 Ok(ledger) 132 } 133 134 pub fn extend_from_snapshot(&mut self, snapshot: ChainSnapshot) -> Result<bool> { 135 self.extend_from_snapshot_with_vdf_policy(snapshot, true, unix_now_ms()) 136 } 137 138 pub(crate) fn extend_from_preverified_snapshot_at( 139 &mut self, 140 snapshot: ChainSnapshot, 141 now_ms: u64, 142 ) -> Result<bool> { 143 self.extend_from_snapshot_with_vdf_policy(snapshot, false, now_ms) 144 } 145 146 pub(crate) fn missing_snapshot_blocks(&self, snapshot: &ChainSnapshot) -> Result<Vec<Block>> { 147 let remote_height = self.validate_snapshot_identity(snapshot)?; 148 if remote_height <= self.height() { 149 return Ok(Vec::new()); 150 } 151 let common_ancestor_height = self.common_ancestor_height(snapshot)?; 152 153 Ok(snapshot 154 .blocks 155 .iter() 156 .skip(common_ancestor_height as usize + 1) 157 .cloned() 158 .collect()) 159 } 160 161 fn extend_from_snapshot_with_vdf_policy( 162 &mut self, 163 snapshot: ChainSnapshot, 164 verify_vdf: bool, 165 now_ms: u64, 166 ) -> Result<bool> { 167 self.validate_snapshot_identity(&snapshot)?; 168 let candidate = Self::from_snapshot_with_vdf_policy(snapshot, verify_vdf, now_ms)?; 169 let fork_point = self.fork_point_with_candidate(&candidate)?; 170 171 if self.choose_fork(&candidate, fork_point) == ForkChoice::KeepLocal { 172 return Ok(false); 173 } 174 175 self.replace_with_better_chain(candidate, fork_point); 176 177 Ok(true) 178 } 179 180 fn validate_snapshot_identity(&self, snapshot: &ChainSnapshot) -> Result<u64> { 181 if snapshot.blocks.is_empty() { 182 bail!("chain snapshot is empty"); 183 } 184 if snapshot.vdf_rounds != self.initial_vdf_rounds { 185 bail!("chain snapshot initial VDF rounds do not match local chain"); 186 } 187 if snapshot.launch_profile != self.launch_profile { 188 bail!("chain snapshot launch profile does not match local chain"); 189 } 190 if snapshot.genesis_allocations != self.genesis_allocations { 191 bail!("chain snapshot genesis allocations do not match local chain"); 192 } 193 if snapshot.blocks[0].hash != self.genesis_hash() { 194 bail!("chain snapshot genesis does not match local chain"); 195 } 196 197 let remote_height = snapshot 198 .blocks 199 .last() 200 .map(|block| block.height) 201 .unwrap_or(0); 202 203 Ok(remote_height) 204 } 205 206 fn common_ancestor_height(&self, snapshot: &ChainSnapshot) -> Result<u64> { 207 self.validate_snapshot_identity(snapshot)?; 208 let max_common_index = self.chain.len().min(snapshot.blocks.len()) - 1; 209 for index in 0..=max_common_index { 210 if self.chain[index] != snapshot.blocks[index] { 211 if index == 0 { 212 bail!("chain snapshot has no common genesis block"); 213 } 214 return Ok(index as u64 - 1); 215 } 216 } 217 Ok(max_common_index as u64) 218 } 219 220 fn fork_point_with_candidate(&self, candidate: &Ledger) -> Result<ForkPoint> { 221 if candidate.genesis_hash() != self.genesis_hash() { 222 bail!("candidate chain has no common genesis block"); 223 } 224 let max_common_index = self.chain.len().min(candidate.chain.len()) - 1; 225 for index in 0..=max_common_index { 226 if self.chain[index] != candidate.chain[index] { 227 if index == 0 { 228 bail!("candidate chain has no common genesis block"); 229 } 230 return Ok(ForkPoint { 231 common_ancestor_height: index as u64 - 1, 232 }); 233 } 234 } 235 Ok(ForkPoint { 236 common_ancestor_height: max_common_index as u64, 237 }) 238 } 239 240 fn choose_fork(&self, candidate: &Ledger, fork_point: ForkPoint) -> ForkChoice { 241 let local_height = self.height(); 242 let remote_height = candidate.height(); 243 if remote_height == local_height && candidate.tip().hash == self.tip().hash { 244 return ForkChoice::KeepLocal; 245 } 246 247 let finalized_floor = local_height.saturating_sub(super::FORK_FINALITY_DEPTH); 248 if fork_point.common_ancestor_height < finalized_floor { 249 return ForkChoice::KeepLocal; 250 } 251 252 if remote_height > local_height { 253 return ForkChoice::SwitchToCandidate; 254 } 255 if remote_height < local_height { 256 return ForkChoice::KeepLocal; 257 } 258 259 match self.fork_quality(candidate, fork_point) { 260 ForkQuality::RemoteBetter => ForkChoice::SwitchToCandidate, 261 ForkQuality::LocalBetter | ForkQuality::Equal => ForkChoice::KeepLocal, 262 } 263 } 264 265 fn fork_quality(&self, candidate: &Ledger, fork_point: ForkPoint) -> ForkQuality { 266 let local_fork = self 267 .chain 268 .iter() 269 .skip(fork_point.first_diverging_height() as usize); 270 let remote_fork = candidate 271 .chain 272 .iter() 273 .skip(fork_point.first_diverging_height() as usize); 274 for (local, remote) in local_fork.zip(remote_fork) { 275 match local.leader_score().cmp(&remote.leader_score()) { 276 std::cmp::Ordering::Equal => continue, 277 ordering => return ForkQuality::from(ordering), 278 } 279 } 280 ForkQuality::Equal 281 } 282 283 fn replace_with_better_chain(&mut self, mut candidate: Ledger, fork_point: ForkPoint) { 284 let mut carry_forward = self.pending.clone(); 285 carry_forward.extend(self.orphans.clone()); 286 let mut carry_forward_blinded = self.pending_blinded.clone(); 287 let mut carry_forward_reveals = self.pending_reveals.clone(); 288 for block in self 289 .chain 290 .iter() 291 .skip(fork_point.first_diverging_height() as usize) 292 { 293 carry_forward.extend(block.transactions.clone()); 294 carry_forward_blinded.extend(block.blinded_transactions.clone()); 295 carry_forward_reveals.extend(block.all_blinded_reveals().into_iter().cloned()); 296 } 297 298 let mined_signatures = candidate 299 .chain 300 .iter() 301 .flat_map(|block| block.transactions.iter()) 302 .map(|tx| tx.signature().to_string()) 303 .collect::<BTreeSet<_>>(); 304 let mined_blinded_commitments = candidate 305 .chain 306 .iter() 307 .flat_map(|block| block.blinded_transactions.iter()) 308 .map(|transaction| transaction.commitment.clone()) 309 .collect::<BTreeSet<_>>(); 310 let mined_reveal_commitments = candidate 311 .chain 312 .iter() 313 .flat_map(|block| block.all_blinded_reveals()) 314 .map(|reveal| reveal.commitment.clone()) 315 .collect::<BTreeSet<_>>(); 316 317 for transaction in carry_forward { 318 if !mined_signatures.contains(transaction.signature()) { 319 let _ = candidate.submit_transaction(transaction); 320 } 321 } 322 for transaction in carry_forward_blinded { 323 if !mined_blinded_commitments.contains(&transaction.commitment) { 324 let _ = candidate.submit_blinded_transaction(transaction); 325 } 326 } 327 for reveal in carry_forward_reveals { 328 if !mined_reveal_commitments.contains(&reveal.commitment) { 329 let _ = candidate.submit_blinded_reveal(reveal); 330 } 331 } 332 333 *self = candidate; 334 } 335 }