4 posts tagged with "trace-verification"

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 Leios team made significant progress in protocol development, focusing on improving simulation capabilities and analyzing protocol behavior under various network conditions. A comparison of Haskell and Rust simulations across 18 scenarios demonstrated that the Leios protocol scales effectively to mainnet-sized networks. However, congestion occurs when the input block rate reaches 30 IB/s.

Simulation comparison​

• Compared 18 scenarios between Haskell and Rust simulations at tag leios-2025w12
• Recent fixes and adjustments enabled meaningful comparison between simulations
• Identified differences when comparing the Haskell and Rust results, which are under active investigation.

Analysis of simulations​

• Completed the first simulation of Short Leios, evaluating IB production rate, IB size, and network topology
• Demonstrated that the Leios protocol scales effectively to mainnet-sized networks
• Identified congestion occurring when the input block rate exceeds 30 IB/s
• Suggested that allowing IBs larger than current Praos RBs may have advantages in TCP efficiency, network usage, and adapting to fluctuating transaction loads.

Peak CPU	Mean CPU

Haskell simulation​

• Implemented expiration of blocks:
  • Blocks are removed from the relay buffer once diffusion stops and cleared from other states as specified
• Developed an initial Full Leios implementation:
  • Currently in early testing
  • Added the praos-chain-quality configuration parameter for the \eta parameter from the specification.

Rust simulation​

• Developed an initial Full Leios implementation using estimated values for some parameters.

Formal methods​

• Short Leios trace verification: modeling local state evolution of a node
• Developed an initial trace verifier for Short Leios simulation traces in leios-trace-verifier.

This week in Leios development, the team focused on simulation analysis, formal methods, and documentation updates. Key accomplishments include in-depth analysis of simulations at tag leios-2025w10, advancements in formal methods through a working trace verifier, and the development of technical reports.

Cross-simulation analysis​

• Completed a comprehensive analysis of simulations at tag leios-2025w10:
  • Analyzed Haskell simulation performance with and without CPU usage considerations
  • Varying key protocol parameters:
    • IB production rate
    • IB size
    • Length of Leios stages
  • Identified the following aspects of Leios:
    • Delay between IB generation and receipt at nodes
    • Peak and mean CPU usage over time
    • Breakdown of CPU usage by task type
    • Sizes of IBs, EBs, and RBs
    • Duplicate IB references in EBs
    • Reference to EBs from RBs
    • Resource utilization in network traffic.

Protocol and formal methods​

• Began developing a trace verifier in Agda:
  • Implemented event trace parsing using the Haskell module leios-trace-hs.

Documentation and research​

• Completed the full draft of the Leios technical report #1
• Created a skeletal draft of the Leios CIP
• Aligned with the latest CIP template
• Developed a detailed simulation analysis for the 100-node Leios network.

Programming and testing​

• Resolved several simulation issues:
  • #235: RB size does not reflect the presence of a certificate
  • #234: Fast transmission of large blocks at moderate IB rate
  • #232: Monotonicity of EB inclusion in RBs
  • #230: EBs are not large enough to include their IBs
  • #229: Rust simulations panics from overflow
• Enabled the visualization of network traffic and logging messages for multiple predefined 'scenarios' instead of a single hard-coded trace
• Updated the visualization to display resource utilization in network traffic.

Rust simulation visualization​

• Improved visualization capabilities:
  • Added support for multiple predefined 'scenarios' instead of single hard-coded trace
  • Moved the visualization logic to the client-side web worker for better performance
  • Added the visualization of per-node network traffic breakdown by message type
• Fixed critical simulation bugs:
  • Resolved issue #229 causing time travel and crashes in high-traffic high-latency scenarios.

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.