ready.rs
1 // Copyright (c) 2025-2026 ACDC Network 2 // This file is part of the alphaos library. 3 // 4 // Alpha Chain | Delta Chain Protocol 5 // International Monetary Graphite. 6 // 7 // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com). 8 // They built world-class ZK infrastructure. We installed the EASY button. 9 // Their cryptography: elegant. Our modifications: bureaucracy-compatible. 10 // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours. 11 // 12 // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0 13 // All modifications and new work: CC0 1.0 Universal Public Domain Dedication. 14 // No rights reserved. No permission required. No warranty. No refunds. 15 // 16 // https://creativecommons.org/publicdomain/zero/1.0/ 17 // SPDX-License-Identifier: CC0-1.0 18 19 use alphavm::{ 20 console::prelude::*, 21 ledger::{ 22 block::Transaction, 23 narwhal::{Data, Transmission, TransmissionID}, 24 puzzle::{Solution, SolutionID}, 25 }, 26 }; 27 28 use indexmap::{IndexMap, IndexSet}; 29 use std::collections::{hash_map::Entry::Vacant, HashMap, VecDeque}; 30 31 /// Maintains a queue of verified ("ready") transmissions. 32 #[derive(Clone, Debug)] 33 pub struct Ready<N: Network> { 34 /// Maps each transmission ID to its logical index (physical index + offset) 35 /// in `transmissions`. 36 transmission_ids: HashMap<TransmissionID<N>, i64>, 37 /// An ordered collection of (transmission ID, transmission). 38 transmissions: VecDeque<(TransmissionID<N>, Transmission<N>)>, 39 /// An offset used to adjust logical indices when elements are inserted or 40 /// removed at the front. 41 offset: i64, 42 } 43 44 impl<N: Network> Default for Ready<N> { 45 /// Initializes a new instance of the ready queue. 46 fn default() -> Self { 47 Self::new() 48 } 49 } 50 51 impl<N: Network> Ready<N> { 52 /// Initializes a new instance of the ready queue. 53 pub fn new() -> Self { 54 Self { transmission_ids: Default::default(), transmissions: Default::default(), offset: Default::default() } 55 } 56 57 /// Returns `true` if the ready queue is empty. 58 pub fn is_empty(&self) -> bool { 59 self.transmissions.is_empty() 60 } 61 62 /// Returns the number of transmissions in the ready queue. 63 pub fn num_transmissions(&self) -> usize { 64 self.transmissions.len() 65 } 66 67 /// Returns the number of ratifications in the ready queue. 68 pub fn num_ratifications(&self) -> usize { 69 self.transmission_ids.keys().filter(|id| matches!(id, TransmissionID::Ratification)).count() 70 } 71 72 /// Returns the number of solutions in the ready queue. 73 pub fn num_solutions(&self) -> usize { 74 self.transmission_ids.keys().filter(|id| matches!(id, TransmissionID::Solution(..))).count() 75 } 76 77 /// Returns the number of transactions in the ready queue. 78 pub fn num_transactions(&self) -> usize { 79 self.transmission_ids.keys().filter(|id| matches!(id, TransmissionID::Transaction(..))).count() 80 } 81 82 /// Returns the transmission IDs in the ready queue. 83 pub fn transmission_ids(&self) -> IndexSet<TransmissionID<N>> { 84 self.transmission_ids.keys().copied().collect() 85 } 86 87 /// Returns the transmissions in the ready queue. 88 pub fn transmissions(&self) -> IndexMap<TransmissionID<N>, Transmission<N>> { 89 self.transmissions.iter().cloned().collect() 90 } 91 92 /// Returns the solutions in the ready queue. 93 pub fn solutions(&self) -> Vec<(SolutionID<N>, Data<Solution<N>>)> { 94 self.transmissions 95 .iter() 96 .filter_map(|(id, transmission)| match (id, transmission) { 97 (TransmissionID::Solution(id, _), Transmission::Solution(solution)) => Some((*id, solution.clone())), 98 _ => None, 99 }) 100 .collect() 101 } 102 103 /// Returns the transactions in the ready queue. 104 pub fn transactions(&self) -> Vec<(N::TransactionID, Data<Transaction<N>>)> { 105 self.transmissions 106 .iter() 107 .filter_map(|(id, transmission)| match (id, transmission) { 108 (TransmissionID::Transaction(id, _), Transmission::Transaction(tx)) => Some((*id, tx.clone())), 109 _ => None, 110 }) 111 .collect() 112 } 113 } 114 115 impl<N: Network> Ready<N> { 116 /// Returns `true` if the ready queue contains the specified `transmission ID`. 117 pub fn contains(&self, transmission_id: impl Into<TransmissionID<N>>) -> bool { 118 self.transmission_ids.contains_key(&transmission_id.into()) 119 } 120 121 /// Returns the transmission, given the specified `transmission ID`. 122 pub fn get(&self, transmission_id: impl Into<TransmissionID<N>>) -> Option<Transmission<N>> { 123 self.transmission_ids 124 .get(&transmission_id.into()) 125 .and_then(|&index| self.transmissions.get((index - self.offset) as usize)) 126 .map(|(_, transmission)| transmission.clone()) 127 } 128 129 /// Inserts the specified (`transmission ID`, `transmission`) to the ready queue. 130 /// Returns `true` if the transmission is new, and was added to the ready queue. 131 pub fn insert(&mut self, transmission_id: impl Into<TransmissionID<N>>, transmission: Transmission<N>) -> bool { 132 let physical_index = self.transmissions.len(); 133 let transmission_id = transmission_id.into(); 134 135 if let Vacant(entry) = self.transmission_ids.entry(transmission_id) { 136 entry.insert(physical_index as i64 + self.offset); 137 self.transmissions.push_back((transmission_id, transmission)); 138 true 139 } else { 140 false 141 } 142 } 143 144 /// Inserts the specified (`transmission ID`, `transmission`) at the front 145 /// of the ready queue. 146 /// Returns `true` if the transmission is new, and was added to the ready queue. 147 pub fn insert_front( 148 &mut self, 149 transmission_id: impl Into<TransmissionID<N>>, 150 transmission: Transmission<N>, 151 ) -> bool { 152 let transmission_id = transmission_id.into(); 153 if let Vacant(entry) = self.transmission_ids.entry(transmission_id) { 154 self.offset -= 1; 155 let index = self.offset; 156 157 entry.insert(index); 158 self.transmissions.push_front((transmission_id, transmission)); 159 true 160 } else { 161 false 162 } 163 } 164 165 /// Removes and returns the transmission at the front of the queue. 166 pub fn remove_front(&mut self) -> Option<(TransmissionID<N>, Transmission<N>)> { 167 if let Some((transmission_id, transmission)) = self.transmissions.pop_front() { 168 self.transmission_ids.remove(&transmission_id); 169 170 if self.transmission_ids.is_empty() { 171 debug_assert!(self.transmissions.is_empty()); 172 self.offset = 0; 173 } else { 174 self.offset += 1; 175 } 176 177 Some((transmission_id, transmission)) 178 } else { 179 None 180 } 181 } 182 183 /// Removes all solution transmissions from the queue (O(n)). 184 pub fn clear_solutions(&mut self) { 185 self.transmissions.retain(|(_, transmission)| !matches!(transmission, Transmission::Solution(_))); 186 187 // Rebuild the index and reset the offset. 188 self.transmission_ids.clear(); 189 self.offset = 0; 190 for (i, (id, _)) in self.transmissions.iter().enumerate() { 191 self.transmission_ids.insert(*id, i as i64); 192 } 193 } 194 } 195 196 #[cfg(test)] 197 mod tests { 198 use super::*; 199 use alphavm::{ledger::narwhal::Data, prelude::Field}; 200 201 use ::bytes::Bytes; 202 203 type CurrentNetwork = alphavm::prelude::MainnetV0; 204 205 #[test] 206 fn test_ready() { 207 let rng = &mut TestRng::default(); 208 209 // Sample random fake bytes. 210 let data = 211 |rng: &mut TestRng| Data::Buffer(Bytes::from((0..512).map(|_| rng.r#gen::<u8>()).collect::<Vec<_>>())); 212 213 // Initialize the ready queue. 214 let mut ready = Ready::<CurrentNetwork>::new(); 215 216 // Initialize the solution IDs. 217 let solution_id_1 = TransmissionID::Solution( 218 rng.r#gen::<u64>().into(), 219 rng.r#gen::<<CurrentNetwork as Network>::TransmissionChecksum>(), 220 ); 221 let solution_id_2 = TransmissionID::Solution( 222 rng.r#gen::<u64>().into(), 223 rng.r#gen::<<CurrentNetwork as Network>::TransmissionChecksum>(), 224 ); 225 let solution_id_3 = TransmissionID::Solution( 226 rng.r#gen::<u64>().into(), 227 rng.r#gen::<<CurrentNetwork as Network>::TransmissionChecksum>(), 228 ); 229 230 // Initialize the solutions. 231 let solution_1 = Transmission::Solution(data(rng)); 232 let solution_2 = Transmission::Solution(data(rng)); 233 let solution_3 = Transmission::Solution(data(rng)); 234 235 // Insert the solution IDs. 236 assert!(ready.insert(solution_id_1, solution_1.clone())); 237 assert!(ready.insert(solution_id_2, solution_2.clone())); 238 assert!(ready.insert(solution_id_3, solution_3.clone())); 239 240 // Check the number of transmissions. 241 assert_eq!(ready.num_transmissions(), 3); 242 243 // Check the transmission IDs. 244 let transmission_ids = vec![solution_id_1, solution_id_2, solution_id_3].into_iter().collect::<IndexSet<_>>(); 245 assert_eq!(ready.transmission_ids(), transmission_ids); 246 transmission_ids.iter().for_each(|id| assert!(ready.contains(*id))); 247 248 // Check that an unknown solution ID is not in the ready queue. 249 let solution_id_unknown = TransmissionID::Solution( 250 rng.r#gen::<u64>().into(), 251 rng.r#gen::<<CurrentNetwork as Network>::TransmissionChecksum>(), 252 ); 253 assert!(!ready.contains(solution_id_unknown)); 254 255 // Check the transmissions. 256 assert_eq!(ready.get(solution_id_1), Some(solution_1.clone())); 257 assert_eq!(ready.get(solution_id_2), Some(solution_2.clone())); 258 assert_eq!(ready.get(solution_id_3), Some(solution_3.clone())); 259 assert_eq!(ready.get(solution_id_unknown), None); 260 261 // Drain the ready queue. 262 let mut transmissions = Vec::with_capacity(3); 263 for _ in 0..3 { 264 transmissions.push(ready.remove_front().unwrap()) 265 } 266 267 // Check the number of transmissions. 268 assert!(ready.is_empty()); 269 // Check the transmission IDs. 270 assert_eq!(ready.transmission_ids(), IndexSet::new()); 271 // Check the transmissions. 272 assert_eq!(transmissions, vec![ 273 (solution_id_1, solution_1), 274 (solution_id_2, solution_2), 275 (solution_id_3, solution_3) 276 ]); 277 } 278 279 #[test] 280 fn test_ready_duplicate() { 281 use rand::RngCore; 282 let rng = &mut TestRng::default(); 283 284 // Sample random fake bytes. 285 let mut vec = vec![0u8; 512]; 286 rng.fill_bytes(&mut vec); 287 let data = Data::Buffer(Bytes::from(vec)); 288 289 // Initialize the ready queue. 290 let mut ready = Ready::<CurrentNetwork>::new(); 291 292 // Initialize the solution ID. 293 let solution_id = TransmissionID::Solution( 294 rng.r#gen::<u64>().into(), 295 rng.r#gen::<<CurrentNetwork as Network>::TransmissionChecksum>(), 296 ); 297 298 // Initialize the solution. 299 let solution = Transmission::Solution(data); 300 301 // Insert the solution ID. 302 assert!(ready.insert(solution_id, solution.clone())); 303 assert!(!ready.insert(solution_id, solution)); 304 305 // Check the number of transmissions. 306 assert_eq!(ready.num_transmissions(), 1); 307 } 308 309 #[test] 310 fn test_insert_front() { 311 let rng = &mut TestRng::default(); 312 let data = 313 |rng: &mut TestRng| Data::Buffer(Bytes::from((0..512).map(|_| rng.r#gen::<u8>()).collect::<Vec<_>>())); 314 315 // Initialize the ready queue. 316 let mut ready = Ready::<CurrentNetwork>::new(); 317 318 // Initialize the solution IDs. 319 let solution_id_1 = TransmissionID::Solution( 320 rng.r#gen::<u64>().into(), 321 rng.r#gen::<<CurrentNetwork as Network>::TransmissionChecksum>(), 322 ); 323 let solution_id_2 = TransmissionID::Solution( 324 rng.r#gen::<u64>().into(), 325 rng.r#gen::<<CurrentNetwork as Network>::TransmissionChecksum>(), 326 ); 327 328 // Initialize the solutions. 329 let solution_1 = Transmission::Solution(data(rng)); 330 let solution_2 = Transmission::Solution(data(rng)); 331 332 // Insert the two solutions at the front, check the offset. 333 assert!(ready.insert_front(solution_id_1, solution_1.clone())); 334 assert_eq!(ready.offset, -1); 335 assert!(ready.insert_front(solution_id_2, solution_2.clone())); 336 assert_eq!(ready.offset, -2); 337 338 // Check retrieval. 339 assert_eq!(ready.get(solution_id_1), Some(solution_1.clone())); 340 assert_eq!(ready.get(solution_id_2), Some(solution_2.clone())); 341 342 // Remove from the front, offset should have increased by 1. 343 let removed_solution = ready.remove_front().unwrap(); 344 assert_eq!(removed_solution, (solution_id_2, solution_2)); 345 assert_eq!(ready.offset, -1); 346 347 // Remove another transmission from the front, the offset should be back to 0. 348 let removed_solution = ready.remove_front().unwrap(); 349 assert_eq!(removed_solution, (solution_id_1, solution_1)); 350 assert_eq!(ready.offset, 0); 351 } 352 353 #[test] 354 fn test_clear_solutions() { 355 let rng = &mut TestRng::default(); 356 let solution_data = 357 |rng: &mut TestRng| Data::Buffer(Bytes::from((0..512).map(|_| rng.r#gen::<u8>()).collect::<Vec<_>>())); 358 let transaction_data = 359 |rng: &mut TestRng| Data::Buffer(Bytes::from((0..512).map(|_| rng.r#gen::<u8>()).collect::<Vec<_>>())); 360 361 // Initialize the ready queue. 362 let mut ready = Ready::<CurrentNetwork>::new(); 363 364 // Initialize the solution IDs. 365 let solution_id_1 = TransmissionID::Solution( 366 rng.r#gen::<u64>().into(), 367 rng.r#gen::<<CurrentNetwork as Network>::TransmissionChecksum>(), 368 ); 369 let solution_id_2 = TransmissionID::Solution( 370 rng.r#gen::<u64>().into(), 371 rng.r#gen::<<CurrentNetwork as Network>::TransmissionChecksum>(), 372 ); 373 let transaction_id = TransmissionID::Transaction( 374 <CurrentNetwork as Network>::TransactionID::from(Field::rand(rng)), 375 <CurrentNetwork as Network>::TransmissionChecksum::from(rng.r#gen::<u128>()), 376 ); 377 378 // Initialize the transmissions. 379 let solution_1 = Transmission::Solution(solution_data(rng)); 380 let solution_2 = Transmission::Solution(solution_data(rng)); 381 let transaction = Transmission::Transaction(transaction_data(rng)); 382 383 // Insert the solution, check the offset should be decremented. 384 assert!(ready.insert_front(solution_id_1, solution_1.clone())); 385 assert_eq!(ready.offset, -1); 386 387 // Insert the transaction and the second solution, the offset should remain unchanged. 388 assert!(ready.insert(transaction_id, transaction.clone())); 389 assert_eq!(ready.offset, -1); 390 assert!(ready.insert(solution_id_2, solution_2.clone())); 391 assert_eq!(ready.offset, -1); 392 393 // Clear all solution transmissions. 394 ready.clear_solutions(); 395 // Only the transaction should remain. 396 assert_eq!(ready.num_transmissions(), 1); 397 // The offset should now be reset to 0. 398 assert_eq!(ready.offset, 0); 399 // The remaining transmission is the transaction. 400 assert_eq!(ready.get(transaction_id), Some(transaction)); 401 } 402 }