5 posts tagged with "topology"

This week, the Leios team focused on improving simulation analysis tools and creating more practical network topologies. Key achievements include enhancing the trace processor with additional data extraction capabilities and developing a smaller, more efficient 'miniature mainnet' topology for repeated experimentation.

Trace processor enhancements​

• Enhanced the leios-trace-processor to extract CPU, resource, and message-receipt data from simulation trace files
• Eliminated the need for using older, lower-performance scripts for analyzing simulation results
• Added comprehensive data output options:
  • Transaction lifecycle data
  • CPU utilization metrics
  • Resource consumption data
  • Message receipt tracking
• Improved analysis efficiency for large simulation datasets.

Miniature mainnet topology​

• Created a more practical 750-node topology that faithfully mimics mainnet characteristics while addressing performance limitations of the 10,000-node pseudo-mainnet
• Achieved a network diameter, stake distribution, and edge degree closely matching those of the mainnet
• Key network metrics:
  • 216 block producers and 534 relay nodes
  • 19,314 total connections with 5-hop network diameter
  • Average of 25.75 connections per node
  • Clustering coefficient of 0.332
  • Average latency of 64.8ms with maximum of 578.3ms
  • 84.85% asymmetry ratio
• Documented the methodology and results in topology-v2.ipynb
• Deployed the network configuration in topology-v2.yaml
• Enabled more practical, repeatable experimentation with realistic network characteristics.

This week, the Leios team focused on infrastructure improvements, formal methods advancement, and large-scale network simulation. The team successfully resolved outstanding CI issues, enhanced the formal specification with Full-Short Leios support, and began simulating a realistic 10,000-node pseudo-mainnet topology.

Infrastructure improvements​

• Fixed outstanding CI bugs #368 and #379, enabling all CI checks to pass.

Formal methods advancement​

• Added Full-Short Leios as a special case of Short Leios to the formal specification
• Implemented trace verification capabilities for Full-Short Leios.

Pseudo-mainnet topology simulation​

• Designed and initiated comprehensive simulations from 1 to 300 TPS using the new pseudo-mainnet topology
• Created a realistic 10,000-node network with:
  • 2,657 block producers and 7,343 relay nodes
  • Realistic stake distribution and geographic distribution
  • Two relays per block producer with realistic latencies
  • 298,756 total connections with 6-hop network diameter
• Observed significant performance challenges within the large-scale simulation:
  • Rust simulation: six minutes of network time in 10 hours at one TPS
  • Performance degradation at higher TPS rates (one minute network time in 10 hours at 300 TPS)
  • Haskell simulation requires optimization for practical large-network analysis.

Rust simulation enhancements​

• Implemented random sampling of transactions from the Leios memory pool to ensure different IBs contain different transactions when possible
• Added simulation support for the Leios variant, where IBs contain transaction references rather than full transaction bodies
• Enhanced transaction handling for high-traffic scenarios.

Analysis of conflicts and incentives​

• Completed comprehensive analysis of transaction conflicts, ledger design, and fee incentives
• Key findings on conflict management:
  • Honest duplicates and conflicts are unavoidable with local sortition
  • Memory pool rules can minimize conflicts through prompt transaction removal
  • Collateral requirements for failed transactions conflict with Cardano's guarantees
• Identified block producer compensation strategies for handling conflicting transactions
• Proposed EB-level optimization through bitmap-based transaction validation to reduce persistent storage of duplicates and conflicts.

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.

The Leios team continued refining Haskell and Rust simulations, standardizing inputs, outputs, and event logging for better comparability. The team defined standard formats for configuration parameters and network topology for running the Leios protocol. They also worked on logging identical simulation events to compare and feed them into the DeltaQ model and, consequently, the executable specification, ensuring alignment with formal methods.

Haskell simulation updates​

• The short-leios simulation now outputs diffusion latency data
• Added support for different input block (IB) diffusion strategies:
  • freshest-first: higher slot numbers requested first
  • peer-order: requested in order of peer announcement
• Added support for Vote (Send) and Vote (Recv) stages.

Rust simulation progress​

• Added an 'organic' topology generator that better matches mainnet topology
• The generator creates clusters of colocated stake pools and relays
• The simulation uses stake to determine relay connectivity
• Topology insights gathered from stake pool owners:
  • Most pools have multiple relays (2,312 relays across 1,278 pools)
  • Pool operators often run multiple colocated pools sharing relays
  • Relays typically maintain ~25 active outgoing connections
  • Incoming connections scale with stake weight (10-400+ connections).

DeltaQ update​

• Wrote a comprehensive 2025-01 report covering work since September 2024.

Formal methods​

• Finalizing executable specifications for simplified and short Leios
• Extracted short Leios specification to Haskell for conformance testing.

Simulation progress​

Haskell implementation​

• Enhanced parameter handling with support for reading configurations and topologies from disk
• Added a new generate-topology command for random topology generation
• Aligned Leios sortition with algorithms from sortition benchmarks and the technical report
• Completed analysis comparing the Praos simulation with the benchmark cluster
  • Adoption times within 10% of measured values
  • Review of simulation parameters pending
• Next steps identified:
  • Generate topologies with block producers behind relays
  • Begin comparison with the idealized diffusion model
  • Configure and run simulations for higher throughput.

Rust implementation​

• Completed the first pass of block-level visualization
• Updated topology files to include baked-in latencies
• Improved output with human-readable names from the shared topology format
• Enhanced simulation output comparability across different simulations.

Analysis and research​

Sortition analysis​

• Completed a detailed analysis of the 'Fiat Accompli' sortition scheme using mainnet stake distribution (Epoch 535)
• Key findings for 500-vote committees:
  • 406 largest stake block-producers would be deterministic voters
  • ~88 voters would be randomly selected
  • Significant certificate size reduction achieved through deterministic voter selection.

Downstream impact assessment​

Started comprehensive analysis of Leios's impact on the ecosystem:

• Identified impacts on indexers, explorers, SDKs, and APIs resulting from ledger and node changes
• Transaction construction and memory-pool sharding effects on DApps and wallets
• Physical layer visibility considerations for sophisticated use cases
• High throughput implications for event filtering efficiency
• Transaction journey time considerations from memory pool to Praos block reference.

DeltaQ analysis​

• Successfully matched ΔQ model for IB diffusion across both simulations and implementations
• Identified key differences in simulation approaches:
  • Haskell simulation includes bandwidth effects (328ms network delay per hop at 1MB/s)
  • Rust simulation currently excludes bandwidth effects
• Enabled cross-simulation topology sharing for consistent testing.