This document catalogs Leios-related findings and artifacts that were created subsequent to the Leios CIP.
- Markovian model of Linear Leios
- Analysis of UTxO set size and UTxO lifetime
- CPU cost of
Apply,Reapply, and Plutus ledger operations - Mempool and constraint modeling
Markovian simulation of Linear Leios computes the probability of EB certifications as RBs are produced.
The protocol state is represented by three quantities.
- The number of RBs that have been produced.
- The number of EBs that have been produced.
- Whether an honest RB was produced.
- Whether a certificate is ready for inclusion in the next RB.
Time is tracked in terms of block-forging opportunities instead of in terms of slots.
Transitions occur in several substeps:
- Forge RB: create a new RB.
- Certify: include a certificate in the RB.
- Forge EB: create a new EB.
- Vote: cast votes to reach a quorum.
The linleios program executes the Markov model for EB production in Linear Leios. The protocol parameters and network characteristic are specified as flags on the command line. The program outputs the following information:
- The efficiencies, on
/dev/stdout.- RB efficiency: the fraction of possible RBs that were actually produced.
- EB efficiency: the fraction of possible EBs that were actually produced.
- Efficiency: the fraction o possible payload bytes that were actual produced.
- The "missing probability" resulting from the finite-resolution arithmetic of the computations, on
/dev/stderr. - Optionally, a JSON file containing the probabilities of the given number of certified EBs.
The figure below shows example results for the probability distribution of the number of EBs generated per 100 RBs. This directly relates to Leios efficiency.
Analysis of Cardano mainnet indicates that the number of active UTxOs has leveled off at approximately 11 million unspent transaction outputs. The data likely is not sufficient to build a statistical model to forecast the size of the UTxO set as a function of demand: a more speculative model would be needed.
In terms of lifetime, UTxOs have a trimodal distribution:
- About 3% of UTxOs are spent in the same block that they are created.
- About 65% of the UTxOs are active less than one day.
- The remainder are active for multiple days, sometimes for months or years.
The left plot is on a square-root scale horizontally, so one can see how big the dynamic range of lifetimes is; it also includes the 3.0% of txs that are spent in the same block that they are created. The right plot is the same data on a logarithmic scale (omitting zero lifetime), so that one can see the multimodal structure above and below the one-day lifetime.
 |
 |
Simulation studies indicate that the high connectivity of the network topology promotes rapid diffusion, resists fragmentation, and thwarts adversaries.
| Demand ≲ Capacity | Demand ≳ Capacity | Demand ≫ Capacity | |
|---|---|---|---|
| Speed of diffusion | fast | fast | may degrade |
| Global synchronization | ≳ 90% | inversely proportional to global demand | inversely proportional to global demand |
| Fragmentation | ≲ 10% | proportional to global demand | proportional to global demand |
Implications for protocol parameters:
- In the absense of adversaries, transactions soon arrive at non-voting nodes.
- In the presence of adversaries, Ldiff must account for intentional late release of transaction bodies.
- Larger mempools result in less fragmentation.
- Only a fraction of transactions are susceptible to front running.
- The attack surface also depends upon the dapp design.
- Front-running a transaction in the memory pool critically depends upon how quickly an adversary can craft a competing transaction.
| Locus of front running | Required resources | Success rate |
|---|---|---|
| Memory pool | Relay nodes | Depends upon the number of relays and upon how fast the competing transaction is crafted |
| Block producer | Stake | Proportional to stake |
Implications for protocol parameters: none.
- There are two major sources of time delays:
- Waiting for transaction bodies.
- Applying transactions to the ledger.
- Signature verification and Plutus execution tend not to cause delays because they are parallelizable.
- Ledger application is modestly parallelizable except in adversity.
- 3 CPU cores are sufficient for typical 12 MB endorser blocks.
- Adversarial late release of transaction bodies can double peak CPU.
Implications for protocol parameters:
- Maximum transactions per EB, maximum EB size, and Plutus limits must accord with CPU resources.