Higher resolution studies of CPU usage

[bwbush]

Problem statement

Analysis and simulation has highlighted that Linear Leios has some fairly stringent constraints on CPU usage. Previous simulation work has demonstrated the feasibility of (1) the "happy path" for Plutus and non-Plutus workloads and (2) resilience to attacks involving late release of transactions and/or EBs. However, these conclusion are based on several assumptions that may require further investigation:

1. The Rust simulator faithfully represents and sequences the CPU operations and threading that would occur on the a node under a wide variety of conditions (happy path, heavy Plutus, attacks, etc.).
   • The Rust simulator does not model the ledger or UTxO set.
   • The Rust simulator does not model updates to the memory pool in detail.
   • The Rust simulator may be overly optimistic in that it is performing operations before sufficient information is available (e.g., conflicting txs might be applied on different threads in parallel even though that couldn't occur in a real node).
2. The CPU costs of Apply and Reapply that were derived from measuring Cardano mainnet with db-analyser are accurate enough for use in modeling Leios. - We already know that these data are extremely noisy.
   • We don't have sufficient evidence that that Plutus cost model corresponds directly and linearly to CPU usage.
   • It is likely that the existing ledger state, the size of ledger's active UTxO set, and the number of transaction inputs/outputs strongly affect the ledger-update time.
3. A unified memory pool is possible even though transactions with size or Plutus that exceeds the RB limits would have to appear in an EB.
   • An "oversize" transaction (required to be in an EB) might have to be re-applied whenever a smaller transaction (suitable for an RB) is inserted before it in the memory pool.
   • At the very least, a sophisticated data structure or index would be needed for the memory pool, and that might incur extra CPU cost.

Proposed tasks

• Carefully review the existing Apply and Reapply operations in cardano-node and other implementations in order to assess . . .
  • how much Leios will affect these, and
  • what opportunities for parallelism, caching, memorization, etc. are feasible for Leios.
• Revisit the db-analyser tool and data set.
  • Alter db-analyser to provide finer-grained output of measured ledger-update and transaction-validation operations.
  • Study the relationships between Plutus units and actual CPU usage, in the context of the complexity of the script context.
  • Study the relationship between the size of the ledger's active UTxO set and the Reapply time.
  • Study the relationship between the number of a transactions inputs/outputs and the Reapply time.
• Consider upgrading the Rust simulator and/or the Haskell prototype to more faithfully model of CPU usage.
  • Run both optimistic vs pessimistic simulations of application and re-application of transactions to ledger.
• Develop a fine-grained mathematical model for constraints on sequencing CPU-intensive operations.
  • Prove that RB production/liveness will not be affected by CPU bottlenecks.
  • Quantify how much throughput can be reduced by CPU bottlenecks.
  • Apply the model to attacks aimed at overwhelming a node's CPUs (or forcing it into single-threaded operation) by triggering highly concentrated Apply/Reapply operations just prior to voting, block production, etc.

[bwbush]

FYI, here is a first attempt at drawing Petri nets to represent three of the key processes that consume network and CPU resources in Linear Leios, along with constraints on their sequencing. These processes account for the majority of the delays in operating the protocol. The Petri nets are approximate and do not capture the full details of mini-protocols or all of the opportunities for parallelism. The diagrams are notional and are mean to communicate the outlines of the process rather than to formally or precisely specify them.

Updating the ledger after receiving an RB header

The following Petri net illustrates network and CPU operations from the arrival of a new RB header to the complete update of the ledger state, where there are $m$ transactions in the RB and $n$ transactions in the EB: for simplicity in the diagram we assume $m >0$ and $n > 0$. The choice between the Apply Tx and Reapply Tx transition occurs depending upon whether the transaction is already present in the memory pool, Check mempool. The diagram approximates that as many as $c$ transactions may be fetched simultaneously. It omits potential parallelism in updating the ledger.

graph LR

    AwaitRH(("Awaiting
    RB header
    ⬤"))
    
    ArriveRH["<strong>RB header
    arrives</strong>"]
    AwaitRH --"1"--> ArriveRH

    FetchRB((Fetching
    RB body))
    ArriveRH -."1".-> FetchRB

    ArriveRB["RB body
    arrives"]
    FetchRB --"1"--> ArriveRB

    UnvalidatedRbTx(("Awaiting Tx
    application"))
    ArriveRB -."m".-> UnvalidatedRbTx

    CheckRbTx["Check
    mempool"]
    UnvalidatedRbTx --"1"--> CheckRbTx

    ReadyRbTx(("Ready to
    (re)apply Tx"))
    CheckRbTx -."1".-> ReadyRbTx

    ApplyRbTx["Apply Tx"]
    ReadyRbTx --"1"--> ApplyRbTx

    ReapplyRbTx["Reapply Tx"]
    ReadyRbTx --"1"--> ReapplyRbTx

    LedgerRbTx(("Ledger
    updated"))
    ApplyRbTx -."1".-> LedgerRbTx
    ReapplyRbTx -."1".-> LedgerRbTx

    ApplyRB["RB applied"]
    LedgerRbTx --"m"--> ApplyRB

    ReadyLedger(("Ledger ready
    for EB"))
    ApplyRB -."1".-> ReadyLedger

    FetchEH(("Fetching
    EB header"))
    ArriveRH -."1".-> FetchEH

    ArriveEH["EB header
    arrives"]
    FetchEH --"1"--> ArriveEH

    FetchEB(("Fetching
    EB body"))
    ArriveEH -."1".-> FetchEB

    ArriveEB["EB body
    arrives"]
    FetchEB --"1"--> ArriveEB

    AwaitTx(("Awaiting Tx"))
    ArriveEB -."n".-> AwaitTx

    FetchTx["Fetching Tx"]
    AwaitTx --"k ∈ [1, min(c, n)]"--> FetchTx

    UnvalidatedEbTx(("Awaiting Tx
    application"))
    FetchTx -."k".-> UnvalidatedEbTx

    CheckEbTx["Check
    mempool"]
    UnvalidatedEbTx --"1"--> CheckEbTx
    ReadyLedger --"1"--> CheckEbTx

    ReadyEbTx(("Ready to
    (re)apply Tx"))
    CheckEbTx -."1".-> ReadyEbTx

    ApplyEbTx["Apply Tx"]
    ReadyEbTx --"1"--> ApplyEbTx
    ApplyEbTx -."1".-> ReadyLedger

    ReapplyEbTx["Reapply Tx"]
    ReadyEbTx --"1"--> ReapplyEbTx
    ReapplyEbTx -."1".-> ReadyLedger

    LedgerEbTx(("Ledger
    updated"))
    ApplyEbTx -."1".-> LedgerEbTx
    ReapplyEbTx -."1".-> LedgerEbTx

    ApplyEB["<strong>EB validated</strong>"]
    LedgerEbTx --"n"--> ApplyEB
    ReadyLedger --"1"--> ApplyEB

    ApplyEB -."1".-> AwaitRH

Loading

The timing inputs to the two critical voting constraints, RB header arrives and EB validated, are highlighted above.

Updating the memory pool

The Petri net below illustrates a simplified version of transaction mini-protocol and application of transactions to the memory pool. In it $m$ transactions IDs are received and the transaction bodies for the previously unseen $n$ of them are fetched. The diagram approximates that as many as $c$ transactions may be fetched simultaneously. Transactions are only added to memory pool if they are successfully applied.

graph LR

    ReadyTxId(("Ready for
    TxIds ⬤"))

    AnnounceTx["TxIds 
    announced"]
    ReadyTxId --"1"--> AnnounceTx

    UncheckTx(("Candidate
    Txs"))
    AnnounceTx -."m".-> UncheckTx

    CheckTx["Check
    mempool"]
    UncheckTx --"m"--> CheckTx

    FetchTx(("Fetching
    Txs"))
    CheckTx -."n".-> FetchTx
    CheckTx -."1".-> ReadyTxId

    AnyTxs["Any Txs
    to fetch"]
    FetchTx --"n"--> AnyTxs
    ReadyTxs --"1"--> AnyTxs

    FetchTxs(("Txs to
    fetch"))
    AnyTxs -."n".-> FetchTxs

    ArriveTx["Txs 
    arrive"]
    FetchTxs --"k ∈ [1, min(c, n)]"--> ArriveTx

    ReadyTx(("Ready to
    apply Tx"))
    ArriveTx -."k".-> ReadyTx

    ApplyTx["Apply Tx"]
    ReadyTx --"1"--> ApplyTx

    AppliedTx(("Applied
    Txs"))
    ApplyTx -."1".-> AppliedTx

    UpdateMempool["Update
    mempool"]
    AppliedTx --"n"--> UpdateMempool

    ReadyTxs(("Ready for
    Txs ⬤"))
    UpdateMempool -."1".-> ReadyTxs

Loading

Tallying and certifying votes

In actuality votes would be transmitted as "bundles" of as many votes as fit in a single TCP MTU, and validated in parallel. The diagram below ignores the presence of bundles.

graph LR

  AwaitVote(("Awaiting
  vote ⬤"))

  ArriveVote["Vote
  arrives"]
  AwaitVote --"1"--> ArriveVote

  UnvalidateVote(("Vote not
  validated"))
  ArriveVote -."1".-> UnvalidateVote

  ValidateVote["Validating
  vote"]
  UnvalidateVote --"1"--> ValidateVote

  EligibleCheck(("Check
  committee
  membership"))
  ValidateVote -."1".-> EligibleCheck

  SignatureCheck(("Verify
  signature"))
  ValidateVote -."1".-> SignatureCheck

  Member["checked"]
  EligibleCheck --"1"--> Member

  Verified["verified"]
  SignatureCheck --"1"--> Verified

  VerifiedMember(("Checked and
  verified"))
  Member -."1".-> VerifiedMember
  Verified -."1".-> VerifiedMember
  
  Valid["Validated"]
  VerifiedMember --"2"--> Valid
  Valid -."1".-> AwaitVote

  ValidVotes(("Votes
  validated"))
  Valid -."1".-> ValidVotes

  AwaitQuorum(("Awaiting
  quorum ⬤"))

  Quorum["Quorum
  of stake"]
  AwaitQuorum --"1"--> Quorum
  ValidVotes --"τ"--> Quorum

  GenerateCert(("Generating
  certificate"))
  Quorum -."1".-> GenerateCert

  GeneratedCert["Generated
  certificate"]
  GenerateCert --"1"--> GeneratedCert

  Cert(("Certificate"))
  GeneratedCert -."1".-> Cert

Loading

[bwbush]

CC: @ch1bo