20 posts tagged with "rust-simulation"

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 Leios team focused on improving simulation capabilities, enhancing transaction processing, and expanding the test coverage. The team also made significant progress in addressing transaction inclusion rates and developing a comprehensive conformance testing framework.

Simulation improvements​

Rust simulation​

• Investigated and addressed poor transaction inclusion rates
• Implemented 'late IB inclusion' extension to Full Leios, significantly improving transaction ledger inclusion odds
• Identified and addressed issues with non-sharded input transactions causing excessive duplication
• Made several key enhancements:
  • Enabled late IB inclusion by default
  • Fixed the off-by-one error in late IB inclusion logic
  • Added praos-fallback-enabled setting for throughput investigation
  • Improved transaction deduplication in Praos blocks.

Testing framework​

Conformance testing​

• Developed a comprehensive catalog of potential conformance tests
• Implemented a property-based testing suite for trace verification
• Added both positive and negative test cases covering:
  • Genesis slot operations
  • Block production (RB, IB, EB)
  • Vote generation
  • Various production patterns (sporadic, noisy)
  • Invalid scenarios (equivocation, gaps)
• Successfully verified golden traces against the Agda specification.

Documentation​

Formal specification​

• Launched comprehensive web-based documentation for the Ouroboros Leios formal specification at leios.cardano-scaling.org/formal-spec
• Enhanced documentation features:
  • Interactive exploration of Leios modules
  • Type linking between related components
  • Full text search capabilities
  • Improved accessibility of formal specification details.

Transaction lifecycle analysis​

• Conducted detailed analysis of transaction processing efficiency
• Generated a cumulative probability model for transaction ledger inclusion
• Analyzed the relationship between IB production rate and stage length
• Created visualization of transaction-to-block inclusion probabilities.

Next steps​

• Continue monitoring and optimizing transaction inclusion rates
• Expand conformance test coverage as the Agda specification evolves
• Further investigate transaction sharding strategies
• Refine transaction lifecycle model based on simulation results.

This week, the team made significant progress on simulation improvements, trace verification, and a comprehensive analysis of Leios' transaction processing capacity.

Trace verification​

• Improved the trace verifier with better error handling and reporting
• Added support for starting verification from non-initial states
• Created manually curated test cases for the Leios trace verifier
  • Valid traces
  • Invalid traces
• Integrated the trace verifier into Nix infrastructure and CI builds
• Removed deterministic conformance testing in favor of a trace-based approach.

Simulation improvements​

Haskell simulation​

• Conducted an informal review assessing code quality, design, and implementation
• Analyzed the simulation organization and identified areas for future improvement
• Found that most prospective changes to the Leios protocol would only involve a small fraction of the codebase
• Determined that adding memory pool and transactions would take approximately 100-200 hours of labor.

The review of the Haskell simulator was documented in detail in PR#353, covering its statistics, organization, code quality, design, implementation, and documentation aspects.

Rust simulation​

• Added tx-start-time and tx-stop-time parameters to avoid effects of slow starts or sudden terminations on transaction analysis
• Created a new Leios variant full-without-ibs where endorser blocks directly reference transactions.

Documentation and analysis​

• Relocated the original Leios report to avoid confusion, while preserving valuable background information
• Added partially-drafted technical reports on Haskell simulations to Nix and CI builds:
  • Ouroboros Leios network specification
  • Ouroboros Leios simulation: building confidence in the performance results.

The team ran higher excess-capacity simulations to test hypotheses about transaction inclusion. The transaction lifecycle simulations raised the question of whether duplicated transactions in IBs were preventing other transactions from ever being included. The team ran simulations with IBs produced at three times the normal rate to test this, providing ample space for transaction duplication.

Detailed analysis showed that transaction loss persisted despite increased capacity, indicating that other factors are preventing transactions from reaching the ledger. The results are documented in:

• Analysis overview
• Results at 1x IB capacity
• Results at 3x IB capacity.

This week, the team focused on simulation analysis, security improvements, and protocol documentation, making significant progress across multiple areas.

Simulation analysis and performance​

The team executed the first high-throughput simulations of Leios using the Rust simulator, with transaction rates reaching up to 1,000 TPS. They introduced two key efficiency metrics to quantify system performance:

• Temporal efficiency, which measures the fraction of submitted transactions that make it into the ledger, with nearly 100% indicating optimal transaction inclusion
• Spatial efficiency, which represents the ratio of transaction size to total ledger size (including IBs, EBs, and RBs), with higher values indicating better storage optimization.

Recent revisions to Full Short Leios have shown promising improvements in both efficiency metrics. The simulations revealed an average transaction lifecycle of approximately 100 seconds from submission to ledger inclusion.

The analysis produced several key visualizations that demonstrate the system's performance:

Protocol documentation and analysis​

The team conducted an extensive analysis of transaction throughput and block characteristics, producing several key visualizations:

The team also completed a comprehensive profitability analysis for Leios SPOs, considering various deployment scenarios:

• Evaluated infrastructure costs across premium and value cloud providers
• Demonstrated profitability without reserve contributions at 50+ TPS
• Documented the impact of diminishing future rewards due to reserve depletion
• Analyzed comparative economics between Praos and Leios SPOs.

Security and infrastructure improvements​

The team addressed several security vulnerabilities in web applications through a series of patches:

• Fixed minor and moderate security issues in #321, #322, #323, and #325 pull requests.

Protocol enhancements​

Recent protocol improvements include:

• Implementation of revisions to Full Short Leios design to enhance both temporal and spatial efficiency
• Optimization of protocol parameters for improved transaction processing
• Development of a new sharding strategy in Rust simulation
• Enhanced logging system for tracking spatial efficiency metrics.

For more detailed information about the simulations and analysis, please refer to the analysis documentation and the profitability analysis notebook.

This week, the Leios team made significant progress in protocol documentation, simulation improvements, and transaction lifecycle analysis. The team completed a draft of the Leios CIP, enhanced simulation visualization capabilities, and conducted detailed analysis of transaction processing times in Full Leios.

Simulation and analysis​

• Completed simulation of 270 Full Leios scenarios at tag leios-2025w17
• Resolved all outstanding discrepancies between Rust and Haskell simulation results
• Conducted detailed transaction lifecycle analysis:
  • Average IB inclusion time: 2.4 seconds
  • Average EB referencing time: 27.6 seconds
  • Average RB referencing time: 67.2 seconds
  • Identified issues with transaction referencing and duplication in current Full Leios implementation.

Protocol documentation​

• Drafted major sections of the Leios CIP using standard CIP template
• Documented evidence-based arguments for Leios necessity and viability
• Pending completion of Full Leios protocol sections due to ongoing discussions.

Rust implementation​

• Publicly hosted visualization as part of the Leios documentation
• Added new "transactions" view showing transaction state graphs over time
• Fixed stability issues in long-running simulations
• Implemented leios-late-ib-inclusion extension for referencing older pipeline IBs.

Plutus benchmarking​

• Documented workflow for benchmarking Plutus
• Prepared methodology for potential experiments with increased Plutus execution budgets
• Established framework for relating Plutus execution units to CPU time measurements.

Next steps​

• Address transaction referencing and duplication issues in Full Leios
• Complete remaining Full Leios protocol sections in CIP
• Investigate higher transaction rates after resolution of #305
• Continue monitoring and optimizing transaction lifecycle performance.

This week, the team made substantial progress in both the Haskell and Rust simulations, refined cost estimates, and carried out detailed analyses of the transaction lifecycle and Full Leios simulations.

Simulation improvements​

Haskell simulation​

• Completed the first draft of new mini protocols for Leios diffusion
  • Modeled protocols after block-fetch and node-to-node transaction submission from ouroboros-network
  • Included IB relay, EB relay, and vote relay for header diffusion and body announcements
  • Included IB fetch and EB fetch for body diffusion
  • Worked on the CatchUp protocol for older blocks
  • See simulation/docs/network-spec for full protocol details
• Renamed short-leios command to leios as it now covers the full variant as well
  • short-leios is kept as alias for compatibility.

Rust simulation​

• Fixed conformance issues with the shared trace format
• Fixed a bug in the voting logic that prevented EBs from receiving enough votes to be included on-chain
• Updated visualizations to use smaller trace files in preparation for hosting on the documentation site.

Revisions to the cost dashboard​

The cost dashboard was updated with lower and more realistic IO estimates.

Transaction lifecycle analysis​

The Jupyter notebook Analysis of transaction lifecycle estimates the delay introduced at each of the seven stages of Full Leios as a transaction progresses from the memory pool to being referenced by a Praos block.

Key findings from the analysis:

1. Reducing stage lengths below 10 slots offers little benefit
2. The number of shards should remain low enough to maintain a high IB rate per shard relative to the stage length
3. Low EB rates result in many orphaned IBs
4. With realistic parameters, the delay from transaction submission to its inclusion in an RB is approximately two minutes.

Potential next steps:

• Translate the model into Delta QSD to capture network effects
• Compare the model's output with results from the Rust simulator
• Extend the model to account for different memory pool and ledger variants under evaluation.

Simulation and analysis of Full Leios​

The team conducted comprehensive simulations using both Haskell and Rust simulators at tag leios-2025w16. The simulations covered 648 scenarios of Full and Short Leios with varied parameters:

• IB production rate
• IB size
• EB production rate
• Stage length
• CPU constraints.

Two new output files were generated:

1. A summary of network, disk, and CPU resource usage over the course of the simulation
2. The vertices and edges of the Leios graph, showing linkages between transactions, IBs, EBs, RBs, and votes (can be visualized as an interactive web page).

Key findings:

• The Rust and Haskell simulations show generally close agreement
• The Haskell simulation encounters network congestion at 16 IB/s, while the Rust simulation does not
• The Rust simulation consumes more CPU at high IB rates than the Haskell simulation
• In some cases, the Rust simulation does not produce enough votes to certify an EB.

Detailed results are available in the Jupyter notebook analysis/sims/2025w16/analysis.ipynb.

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.

This week, the Leios team continued working on various aspects of the protocol and its simulation capabilities. They made progress in implementing and testing the Haskell and Rust simulators, focusing on protocol behavior under different network conditions.

Simulation progress​

• Haskell simulation

  • Moved configuration and topology parsers to the leios-trace-hs package for reuse in formal methods
  • Investigated differences in IBs referenced with Rust simulation: identified that inconsistencies were caused by the same sequence of random samples being used across different runs
  • Simplified sortition code by using an external statistics package
  • Tested Full Leios, resolving tension between r_EB/eb-max-age-slots and praos-chain-quality/η
  • Fixed cabal run ols -- generate-topology close-and-random, listing producers properly and decreasing variance in upstream peers.

• Rust simulation

  • Investigated anomalies in simulation results: identified that earlier IB production failures were caused by low connectivity and lower CPU usage compared to the Haskell simulation
  • Refined Full Leios implementation
  • Added Full Leios support to the visualizer
  • Migrated the visualizer from Next.js to Vite.

Analysis of simulations​

• Tag leios-2025w13: simulated 198 Short Leios scenarios, varying IB production rate, IB size, network topology, CPU limits, and protocol flags
• CPU limits: analyzed the impact of CPU constraints on IB propagation, finding that diffusion can be affected under stress conditions
• Vote propagation: compared freshest-first and oldest-first vote propagation, with freshest-first potentially improving IB delivery reliability
• Extended voting period: compared an extended voting period to a limited one in the Haskell simulation, observing minimal differences except for occasional improvements in reliable vote delivery.

Ongoing investigations​

• Investigating qualitative discrepancies between Haskell and Rust simulation results to determine whether they stem from differences in simulator resolution or simulation infidelities.

Additional resources​

• Monthly review meeting – March 2025.

This week in Leios development, the team focused on simulation analysis and formal methods. Key accomplishments include detailed analyses of both Haskell and Rust simulations, initial work on a protocol dashboard, and advancements in formal methods through trace verification in Agda.

Cross-simulation analysis​

• Completed a comprehensive analysis of simulations at tag leios-2025w09:
  • Refactored the ELT workflow to improve simulation data processing
  • Modified the Rust simulator to generate fixed-size input blocks (IBs) for comparison with Haskell
  • Partially resolved discrepancies in congestion metrics between simulators
  • Developed detailed analyses of:
    • IB generation to receipt elapsed time
    • Time-in-flight over node-to-node links
  • Identified the dual role of network bandwidth and CPU bottlenecks in high throughput congestion.

Protocol dashboard initiative​

• Initiated the design of an interactive protocol dashboard with planned features:
  • Protocol parameter configuration
  • Stake distribution settings
  • Performance visualization:
    • Block arrival efficiency
    • Transaction duplication
    • Leios operation rewards
    • Resource utilization
  • Security metrics visualization:
    • Quorum failure analysis
    • Certificate forgery detection
    • Adversarial block tracking.

Rust simulation​

• Enhanced parallel message handling capabilities:
  • Implemented parallel mini-protocol message transmission
  • Added even bandwidth distribution between mini-protocols
  • Introduced the simulate-transactions configuration option
  • Updated simulation output for better Haskell compatibility
  • Improved block visualization for scenarios with high IB counts.

Formal methods​

• Commenced trace verifier development in Agda:
  • Added decidability to Short Leios protocol relational specification
  • Implemented a proof-by-computation approach for execution traces
  • Applied the successful methodology from Streamlet formalization.

This week, the Leios team made significant progress across multiple areas. Major developments included detailed DeltaQ analysis of network topologies, extensive BLS cryptography benchmarking, and improvements to both simulations. The team also explored succinct schemes for BLS key registration and conducted a detailed certificate performance analysis. Both Haskell and Rust simulations received substantial updates to improve visualization and support more realistic testing conditions.

DeltaQ analysis​

• Enhanced the topology-checker with ΔQSD analysis capabilities:
  • Extracts inter-node latencies from given topologies
  • Classifies latencies into near/far components
  • Builds parameterized ΔQ models
  • Outputs fitted models in delta_q web app syntax
• Key findings from topology analysis:
  • Clear distinction between near/far components in examined topologies
  • Unexpectedly high hop counts in latency-weighted Dijkstra paths:
    • Min 4-5, max 8 for topology - 100
    • Min 8, max 20 for 'realistic' topology
  • Model fitting achieved rough shape matching but showed significant deviations at low latencies
  • Resource usage tracking goals remain unmet due to complexity in understanding load multiplication factors.

BLS cryptography​

• Completed comprehensive benchmarking of certificate operations:
  • Detailed performance analysis across committee sizes (500-1000 seats)
  • Certificate generation: 63.4ms - 92.5ms
  • Certificate verification: 104.8ms - 144.9ms
  • Certificate weighing: ~12ms consistently
• Explored succinct schemes for key registration:
  • Proposed 90-day key evolution with 124-byte KZG commitments
  • Analyzed message sizes for key opening (316 bytes per pool)
  • Investigated SNARK-based alternatives for proof of possession
• Added BLS crypto to the CI pipeline with automated testing
• Documented parallelization strategies for certificate operations.

Formal methods​

• Added a conformance testing client for the executable Short Leios specification
• Successfully merged the executable specification for Simplified Leios into main.

Haskell simulation​

• Updated configuration defaults for block sizes and timings
• Added support for idealized simulation conditions:
  • Single-peer block body requests
  • TCP congestion window modeling
  • Mini-protocol multiplexing
  • Unlimited bandwidth links support
• Enhanced simulation output and analysis:
  • Added raw field for accumulated data
  • Implemented block diffusion CDF extraction
  • Created multi-CDF plotting capabilities.

Rust simulation​

• Enhanced visualization capabilities:
  • Added block size breakdown display
  • Implemented total bytes sent/received tracking
  • Added total TX count and CPU time metrics
• Improved event handling:
  • Updated to standard timestamp format (seconds)
  • Enhanced CPU task event structure
  • Added CBOR output support
• Added support for multiple strategies:
  • Implemented ib-diffusion-strategy (freshest-first, oldest-first, peer-order)
  • Added relay-strategy affecting TXs, IBs, EBs, votes, and RBs
  • Enabled unlimited EB and vote bundle downloads from peers.