3 posts tagged with "optimization"

The Leios team completed a significant analysis of overcollateralization schemes and continued advancing the Rust simulation infrastructure. They also focused on understanding transaction duplication and conflict probabilities in shardless scenarios while enhancing simulation tooling to better track transaction lifecycle events.

Overcollateralization analysis​

• Completed comprehensive analysis of shardless overcollateralization, where transactions are randomly sampled from the memory pool
• Found that probabilities of duplication and conflicts are minimized when the concurrency period is as short as possible
• Determined that conflict probability is always greater than duplication probability
• Identified that longer transaction residence times correspond to lower probabilities of duplication or conflict, where transaction residency time is defined as the average time a transaction stays in the memory pool before reaching an IB (calculated as memory pool size divided by transaction throughput)
• Discovered that spatial efficiency is greater for longer residence times
• Found that the tradeoff between probabilities of duplication and conflict is insensitive to protocol parameters
• Showed that the expected number of conflicts in IBs scales proportionately with the fraction of conflicting transactions and transaction throughput
• Identified that, at a given throughput, reducing the probability of duplicates or conflicts can be at odds with minimizing the total number of conflicts
• Found that probabilistic computation of conflicts is about 20% lower than naive estimates
• Determined that at 100 TPS with favorable protocol parameters, an overcollateralization factor of nearly 400x is necessary in adversarial scenarios where the memory pool is filled with conflicting transactions
• Concluded that having successful transactions pay for all conflicting ones is too risky due to potential attacks on honest transactions using common UTXO inputs
• Identified that consuming collateral from conflicted transactions in IBs is more viable, though it breaks existing UX guarantees
• Noted ongoing discussions about the realism of creating 400 mutually conflicting transactions, given that individual mempools would not include conflicting transactions, and attack scenarios would require coordination across multiple nodes
• Documented detailed findings in the overcollateralization analysis notebook.

Simulation development​

Transaction lifecycle analysis​

• Analyzed protocol performance across transaction throughput scenarios up to 300 TPS
• Found that the protocol performs well with essentially every transaction reaching the ledger up to 300 TPS, where breakdown occurs
• Noted that the 100-node network is more stressful than a realistic mainnet would be
• Achieved space efficiency above 80% for moderate-throughput scenarios
• Measured average transaction latency of about 100 seconds (95th percentile at 200 seconds) to reach the ledger.

Rust simulation improvements​

• Added 'TXLost' events to the simulation output to detect transaction loss scenarios
• Enhanced the ability to track where Leios can lose transactions with various parameter choices.

Data processing optimization​

• Developed a new leios-trace-processor tool to replace script-based analyses
• Achieved significantly faster processing of simulation results compared to previous scripts
• Enabled analysis of much longer and larger simulation datasets
• Created standardized CSV output format for transaction lifecycle data, including creation, IB inclusion, EB inclusion, and RB inclusion timestamps.

This week, the team continued refining the protocol and its simulation capabilities, making significant progress in addressing various topics.

Simulation improvements​

Haskell simulation​

• Started specifying a new relay protocol for IB header diffusion without the body
• Improved the shared log format by removing redundancies and harmonizing naming
• Added support for additional events required by conformance testing, including SlotEvent and NoBlockEvent
  • These events can be enabled using the --conformance-events flag with --shared-log-format.

Rust simulation​

• Updated traces to match the new standardized trace format
• Fixed a critical bug in CPU scheduling where nodes were using more cores than allocated.

Analysis of workflow optimization​

The team significantly improved the workflow for analyzing both Haskell and Rust simulations:

• Replaced MongoDB with more efficient jq queries using map-reduce operations
• Created reusable library functions for plotting with R
• Revised and streamlined scripts for creating, executing, and analyzing simulations
• Made the Jupyter notebook for analyses more generic and reusable
• Successfully tested the new workflow on tag leios-2025w15.

These improvements will enable faster setup and execution of future simulation experiments, with quicker turnaround times for analysis. During this optimization work, several discrepancies between the Haskell and Rust simulations were identified and documented as GitHub issues for future investigation.

Edinburgh workshop recaps​

The Edinburgh workshop documentation has been made available, covering key discussions and decisions:

Day 1 highlights​

• Explored ledger design options comparing labeled UTXOs (explicit shards) vs accounts (implicit shards) approaches
• Discussed conformance testing strategies including QuickCheck dynamic and trace verification approaches
• Analyzed critical edge cases for user onboarding and system properties.

Day 2 highlights​

• Conducted a detailed analysis of Leios node costs across different TPS levels
• Key findings on resource usage:
  • At 10 TPS: 1.8x increase in egress and 6x increase in compute compared to Praos
  • At 1K TPS: significant scaling improvements with better resource efficiency
• Provided recommendations for potential integration with Peras, particularly to optimize the voting mechanism
• Discussed performance characteristics at both high and low throughput levels.

Day 3 highlights​

• Held an in-depth discussion on optimistic ledger state references, exploring three main approaches:
  1. RB reference: highest security but highest latency
  2. EB reference: balanced approach with medium security and latency
  3. EB-DAG: advanced approach using directed acyclic graph structure
• Key advantages of the EB-DAG approach:
  • Achieves low latency while maintaining security
  • Provides strong inclusion guarantees for EBs
  • Enables efficient state management and reconstruction
  • Creates a complete, verifiable chain history
• Discussed implementation considerations for state management and block ordering under the EB-DAG model.

For more information, please see the full workshop recaps in the Leios documentation.

Rust simulation​

• Optimized virtual clock to be lock-free, removing contention from the previous implementation.

Haskell simulation​

• Merged Leios visualizations on main
• Improved peer-to-peer (P2P) visualization with block type differentiation and latency charting.

Analysis of vote size and ALBA certificates​

• Estimated minimum possible size for votes using ephemeral keys or key evolving signatures (KES)
• Benchmarked central processing unit (CPU) time for ALBA certificates.