• Look at Leios spec for inspiration
• CIP-001 guidelines

Abstract

We propose Peras, an enhancement to the Ouroboros Praos protocol that introduces a voting layer for optimistic fast settlement.

Peras, or more precisely Ouroboros Peras, is an extension of Ouroboros Praos that addresses one of the known issues of blockchains based on Nakamoto-style consensus, namely settlement time. Peras achieves that goal while being self-healing, preserving the security of Praos, and being light on resources.

Motivation: why is this CIP necessary?

• Define clearly what settlement is (and how it differs from finality)

  • Checkout https://docs.google.com/spreadsheets/d/1s_LfDQ4Qg3BArMgr6GskGGzG_Ibg-VbPdMmlRWvZ75o/edit#gid=431199162
  • See Peter Gazi comment -> settlement as a probability or measure of risk to be taken into account by users making transactions
  • Hans's take: Settlement occurs before finality. Settled transactions can be reversible, finalized Txs are irreversible. The difference is in the degree of certainty. A settled Tx is considered valid and is likely to be included in the final, immutable history of blockchain. Depending on the specific use case, different levels of certainity might be required - i.e. a multi-day finality could be a feature of a system. It seems that in traditional finance the long settlement time is often used as an escrow - e.g. for the the buyer to verify the purchase, or for regulatory compliance to be reached.

• Explain settlement on Cardano with Ouroboros Praos

  • Include data -> settlement probabilities (is this sensitive?)

• Explain the required changes to Praos maybe in terms of current limitations of Praos

  • Low cost solution
  • "Overlay" protocol, adding incremental behaviour, no fundamental change to Praos

• Distinguish from orthogonal protocol upgrades such as Genesis, Leios, etc.

• Worst-case vs. optimistic case

  • Praos is geared towards worst case but Peras takes advantage of the opportunities afforded by the optimistic or average case (eg. when things are fine, go faster)

Specification

Non-normative overview of the Peras protocol

The following informal, non-normative, pseudo-imperative summary of the Peras protocol is provided as an index into the formal Agda specification. Peras relies on a few key concepts:

• The progression of the blockchain's slots is partitioned in rounds of equal length.
• In each round a committee of voters is selected via a sortition algorithm.
• Members of the committee may vote for a block in the history of their preferred chain.
• A quorum of votes during the same round for the same block is memorialized as a certificate.
• A quorum of votes for a block gives that block's weight a boost.
• The weight of a chain is its length plus the total of the boosts its blocks have received.
• The lack of a quorum in a round typically triggers a cool-down period where no voting occurs.
• Relevant vote certificates are typically recorded in a block near the start and finish of a cool-down period.
• Certificates expire after a specified number of slots if they haven't been included in a block.

The protocol keeps track of the following variables, initialized to the values below:

• \(C_\text{pref} \gets C_\text{genesis}\): preferred chain;
• \(\mathcal{C} \gets \{C_\text{genesis}\}\): set of chains;
• \(\mathcal{V} \gets \emptyset\): set of votes;
• \(\mathsf{Certs} \gets \{\mathsf{cert}_\text{genesis}\}\): set of certificates;
• \(\mathsf{cert}^\prime \gets \mathsf{cert}_\text{genesis}\): the latest certificate seen;
• \(\mathsf{cert}^* \gets \mathsf{cert}_\text{genesis}\): the latest certificate on chain.

A fetching operation occurs at the beginning of each slot:

• Fetch new chains \(\mathcal{C}_\text{new}\) and votes \(\mathcal{V}_\text{new}\).
• Add any new chains in \(\mathcal{C}_\text{new}\) to \(\mathcal{C}\), add any new certificates contained in chains in \(\mathcal{C}_\text{new}\) to \(\mathsf{Certs}\).
  • Discard any equivocated blocks or certificates: i.e., do not add them to \(\mathcal{C}\) or \(\mathsf{Certs}\).
• Add \(\mathcal{V}_\text{new}\) to \(\mathcal{V}\) and turn any new quorum in \(\mathcal{V}\) into a certificate \(\mathsf{cert}\) and add \(\mathsf{cert}\) to \(\mathsf{Certs}\).
  • Discard any equivocated votes: i.e., do not add the to \(\mathcal{V}\).
• Set \(C_\text{pref}\) to the heaviest (w.r.t. \(\mathsf{Wt}_\mathsf{P}(\cdot)\)) valid chain in \(\mathcal{C}\).
  • If several chains have the same weight, select the one whose tip has the smallest block hash as the preferred one.
  • Each party \(\mathsf{P}\) assigns a certain weight to every chain \(C\), based on \(C\)'s length and all certificates that vote for blocks in \(C\) that \(\mathsf{P}\) has seen so far (and thus stored in a local list \(\mathsf{Certs}\)).
  • Let \(\mathsf{certCount}_\mathsf{P}(C)\) denote the number of such certificates, i.e., \(\mathsf{certCount}_\mathsf{P}(C) := \left| \left\{ \mathsf{cert} \in \mathsf{Certs} : \mathsf{cert} \text{ votes for a block on } C \right\} \right|\).
  • Then, the weight of the chain \(C\) in \(\mathsf{P}\)'s view is \(\mathsf{Wt}_\mathsf{P}(C) := \mathsf{len}(C) + B \cdot \mathsf{certCount}_\mathsf{P}(C)\) for a protocol parameter \(B\).
• Set \(\mathsf{cert}^\prime\) to the certificate with the highest round number in \(\mathsf{Certs}\).
• Set \(\mathsf{cert}^*\) to the certificate with the highest round number on (i.e., included in) \(C_\text{pref}\).

Block creation occurs whenever party \(\mathsf{P}\) is slot leader in a slot \(s\), belonging to some round \(r\):

• Create a new block \(\mathsf{block} = (s, \mathsf{P}, h, \mathsf{cert}, ...)\), where
  • \(h\) is the hash of the last block in \(C_\text{pref}\),
  • \(\mathsf{cert}\) is set to \(\mathsf{cert}^\prime\) if
    • there is no round-\((r-2)\) certificate in \(\mathsf{Certs}\), and
    • \(r - \mathsf{round}(\mathsf{cert}^\prime) \leq A\), and
    • \(\mathsf{round}(\mathsf{cert}^\prime) > \mathsf{round}(\mathsf{cert}^*)\),
    • and to \(\bot\) otherwise,
• Extend \(C_\text{pref}\) by \(\mathsf{block}\), add the new \(C_\text{pref}\) to \(\mathcal{C}\) and diffuse it.

During voting, each party \(\mathsf{P}\) does the following at the beginning of each voting round \(r\):

• Let \(\mathsf{block}\) be the youngest block at least \(L\) slots old on \(C_\text{pref}\).
• If party \(\mathsf{P}\) is (voting) committee member in a round \(r\),
  • either
    • : \(\mathsf{round}(\mathsf{cert}^\prime) = r-1\) and \(\mathsf{cert}^\prime\) was received before the end of round \(r-1\), and
    • : \(\mathsf{block}\) extends (i.e., has the ancestor or is identical to) the block certified by \(\mathsf{cert}^\prime\),
  • or
    • : \(r \geq \mathsf{round}(\mathsf{cert}^\prime) + R\), and
    • : \(r = \mathsf{round}(\mathsf{cert}^*) + c \cdot K\) for some \(c > 0\),
  • then create a vote \(v = (r, \mathsf{P}, h,...)\),
  • Add \(v\) to \(\mathcal{V}\) and diffuse it.

Normative protocol specification in Agda

The following relational specification for Peras uses Agda 2.6.4.1 and the Agda Standard Library 2.0. The repository github:input-output-hk/peras-design provides a Nix-based environment for compiling and executing Peras's specification.

module Peras.SmallStep where

The small-step semantics of the Ouroboros Peras protocol define the
evolution of the global state of the system modelling honest and adversarial
parties. The number of parties is fixed during the execution of the protocol and
the list of parties has to be provided as a module parameter. In addition the
model is parameterized by the lotteries (for slot leadership and voting
committee membership) as well as the type of the block tree. Furthermore
adversarial parties share generic, adversarial state.

References:

• Formalizing Nakamoto-Style Proof of Stake, Søren Eller Thomsen and Bas Spitters

Parameters

The parameters for the Peras protocol and hash functions are defined as
instance arguments of the module.

module _ ⦃ _ : Hashable Block ⦄
         ⦃ _ : Hashable (List Tx) ⦄
         ⦃ _ : Params ⦄
         ⦃ _ : Network ⦄
         ⦃ _ : Postulates ⦄

         where

The block tree, resp. the validity of the chain is defined with respect of the
parameters.

  open Hashable ⦃...⦄
  open Params ⦃...⦄
  open Network ⦃...⦄
  open Postulates ⦃...⦄

Messages

Messages for sending and receiving chains and votes. Note, in the Peras protocol
certificates are not diffused explicitly.

  data Message : Type where
    ChainMsg : Chain → Message
    VoteMsg : Vote → Message

Block-tree

A block-tree is defined by properties - an implementation of the block-tree
has to fulfil all the properties mentioned below:

  record IsTreeType {T : Type}
                    (tree₀ : T)
                    (newChain : T → Chain → T)
                    (allChains : T → List Chain)
                    (preferredChain : T → Chain)
                    (addVote : T → Vote → T)
                    (votes : T → List Vote)
                    (certs : T → List Certificate)
                    (cert₀ : Certificate)
         : Type₁ where

    field

Properties that must hold with respect to chains, certificates and votes.

      instantiated :
        preferredChain tree₀ ≡ []

      instantiated-certs :
        certs tree₀ ≡ cert₀ ∷ []

      instantiated-votes :
        votes tree₀ ≡ []

      extendable-chain : ∀ (t : T) (c : Chain)
        → certs (newChain t c) ≡ certsFromChain c ++ certs t

      valid : ∀ (t : T)
        → ValidChain (preferredChain t)

      optimal : ∀ (c : Chain) (t : T)
        → let
            b = preferredChain t
            cts = certs t
          in
          ValidChain c
        → c ∈ allChains t
        → ∥ c ∥ cts ≤ ∥ b ∥ cts

      self-contained : ∀ (t : T)
        → preferredChain t ∈ allChains t

      valid-votes : ∀ (t : T)
        → All ValidVote (votes t)

      unique-votes : ∀ (t : T) (v : Vote)
        → let vs = votes t
          in
          v ∈ vs
        → vs ≡ votes (addVote t v)

      no-equivocations : ∀ (t : T) (v : Vote)
        → let vs = votes t
          in
          Any (v ∻_) vs
        → vs ≡ votes (addVote t v)

      quorum-cert : ∀ (t : T) (b : Block) (r : ℕ)
        → length (filter (λ {v →
                    (getRoundNumber (votingRound v) ≟ r)
              ×-dec (blockHash v ≟-BlockHash hash b)}
            ) (votes t)) ≥ τ
        → Any (λ {c →
            (getRoundNumber (round c) ≡ r)
          × (blockRef c ≡ hash b) }) (certs t)

In addition to chains the block-tree manages votes and certificates as well.
The block-tree type is defined as follows:

  record TreeType (T : Type) : Type₁ where

    field
      tree₀ : T
      newChain : T → Chain → T
      allChains : T → List Chain
      preferredChain : T → Chain

      addVote : T → Vote → T

      votes : T → List Vote
      certs : T → List Certificate

    cert₀ : Certificate
    cert₀ = MkCertificate (MkRoundNumber 0) (MkHash emptyBS)

    field
      is-TreeType : IsTreeType
                      tree₀ newChain allChains preferredChain
                      addVote votes certs cert₀

    latestCertOnChain : T → Certificate
    latestCertOnChain =
      latestCert cert₀ ∘ catMaybes ∘ map certificate ∘ preferredChain

    latestCertSeen : T → Certificate
    latestCertSeen = latestCert cert₀ ∘ certs

    hasCert : RoundNumber → T → Type
    hasCert (MkRoundNumber r) = Any ((r ≡_) ∘ roundNumber) ∘ certs

    hasCert? : (r : RoundNumber) (t : T) → Dec (hasCert r t)
    hasCert? (MkRoundNumber r) = any? ((r ≟_) ∘ roundNumber) ∘ certs

    hasVote : RoundNumber → T → Type
    hasVote (MkRoundNumber r) = Any ((r ≡_) ∘ votingRound') ∘ votes

    hasVote? : (r : RoundNumber) (t : T) → Dec (hasVote r t)
    hasVote? (MkRoundNumber r) = any? ((r ≟_) ∘ votingRound') ∘ votes

    preferredChain′ : SlotNumber → T → Chain
    preferredChain′ (MkSlotNumber sl) =
      let cond = (_≤? sl) ∘ slotNumber'
      in filter cond ∘ preferredChain

    allBlocks : T → List Block
    allBlocks = concat ∘ allChains

Additional parameters

In order to define the semantics the following parameters are required
additionally:

• The type of the block-tree
• adversarialState₀ is the initial adversarial state
• Tx selection function per party and slot number
• The list of parties

  module Semantics
           {T : Type} {blockTree : TreeType T}
           {S : Type} {adversarialState₀ : S}
           {txSelection : SlotNumber → PartyId → List Tx}
           {parties : Parties} -- TODO: use parties from blockTrees
                               -- i.e. allow dynamic participation

           where

    open TreeType blockTree

    instance
      Default-T : Default T
      Default-T .def = tree₀

Block-tree update

Updating the block-tree upon receiving a message for vote and block messages.

    data _[_]→_ : T → Message → T → Type where

      VoteReceived : ∀ {v t} →
          ────────────────────────────
          t [ VoteMsg v ]→ addVote t v

      ChainReceived : ∀ {c t} →
          ──────────────────────────────
          t [ ChainMsg c ]→ newChain t c

Vote in round

When does a party vote in a round? The protocol expects regular voting, i.e. if
in the previous round a quorum has been achieved or that voting resumes after a
cool-down phase.

BlockSelection

    BlockSelection : SlotNumber → T → Maybe Block
    BlockSelection (MkSlotNumber s) =
      head ∘ filter (λ {b → (slotNumber' b) ≤? (s ∸ L)}) ∘ preferredChain

    ChainExtends : Maybe Block → Certificate → Chain → Type
    ChainExtends nothing _ _ = ⊥
    ChainExtends (just b) c =
      Any (λ block → (hash block ≡ blockRef c))
        ∘ L.dropWhile (λ block' → ¬? (hash block' ≟-BlockHash hash b))

Voting rules

VR-1A: A party has seen a certificate cert-r−1 for round r−1

    VotingRule-1A : RoundNumber → T → Type
    VotingRule-1A (MkRoundNumber r) t = r ≡ roundNumber (latestCertSeen t) + 1

VR-1B: The extends the block certified by cert-r−1,

    VotingRule-1B : SlotNumber → T → Type
    VotingRule-1B s t =
      Any (ChainExtends (BlockSelection s t) (latestCertSeen t)) (allChains t)

VR-1: Both VR-1A and VR-1B hold

    VotingRule-1 : SlotNumber → T → Type
    VotingRule-1 s t =
        VotingRule-1A (v-round s) t
      × VotingRule-1B s t

VR-2A: The last certificate a party has seen is from a round at least R rounds back

    VotingRule-2A : RoundNumber → T → Type
    VotingRule-2A (MkRoundNumber r) t = r ≥ roundNumber (latestCertSeen t) + R

VR-2B: The last certificate included in a party's current chain is from a round exactly
c⋆K rounds ago for some c : ℕ, c ≥ 0

    VotingRule-2B : RoundNumber → T → Type
    VotingRule-2B (MkRoundNumber r) t =
        r > roundNumber (latestCertOnChain t)
      × r mod K ≡ (roundNumber (latestCertOnChain t)) mod K

VR-2: Both VR-2A and VR-2B hold

    VotingRule-2 : RoundNumber → T → Type
    VotingRule-2 r t =
        VotingRule-2A r t
      × VotingRule-2B r t

If either VR-1A and VR-1B or VR-2A and VR-2B hold, voting is expected

    VotingRule : SlotNumber → T → Type
    VotingRule s t =
        VotingRule-1 s t
      ⊎ VotingRule-2 (v-round s) t

State

The small-step semantics rely on a global state, which consists of the following fields:

• Current slot of the system
• Map with local state per party
• All the messages that have been sent but not yet been delivered
• All the messages that have been sent
• Adversarial state

    record State : Type where
      constructor ⟦_,_,_,_,_⟧
      field
        clock : SlotNumber
        blockTrees : AssocList PartyId T
        messages : List Envelope
        history : List Message
        adversarialState : S

      blockTrees' : List T
      blockTrees' = map proj₂ blockTrees

      v-rnd : RoundNumber
      v-rnd = v-round clock

      v-rnd' : ℕ
      v-rnd' = getRoundNumber v-rnd

Progress

Rather than keeping track of progress, we introduce a predicate stating that all
messages that are not delayed have been delivered. This is a precondition that
must hold before transitioning to the next slot.

    Fetched : State → Type
    Fetched = All (λ { z → delay z ≢ 𝟘 }) ∘ messages
      where open State

Predicate for a global state stating that the current slot is the last slot of
a voting round.

    LastSlotInRound : State → Type
    LastSlotInRound M =
      suc (rnd (getSlotNumber clock)) ≡ rnd (suc (getSlotNumber clock))
      where open State M

    LastSlotInRound? : (s : State) → Dec (LastSlotInRound s)
    LastSlotInRound? M =
      suc (rnd (getSlotNumber clock)) ≟ rnd (suc (getSlotNumber clock))
      where open State M

Predicate for a global state stating that the next slot will be in a new voting
round.

    NextSlotInSameRound : State → Type
    NextSlotInSameRound M =
      rnd (getSlotNumber clock) ≡ rnd (suc (getSlotNumber clock))
      where open State M

    NextSlotInSameRound? : (s : State) → Dec (NextSlotInSameRound s)
    NextSlotInSameRound? M =
      rnd (getSlotNumber clock) ≟ rnd (suc (getSlotNumber clock))
      where open State M

Predicate for a global state asserting that parties of the voting committee for
a the current voting round have voted. This is needed as a condition when
transitioning from one voting round to another.

TODO: Properly define the condition for required votes

    RequiredVotes : State → Type
    RequiredVotes M =
         Any (VotingRule clock ∘ proj₂) blockTrees
       → Any (hasVote (v-round clock) ∘ proj₂) blockTrees
      where open State M

Ticking the global clock increments the slot number and decrements the delay of
all the messages in the message buffer.

    tick : State → State
    tick M =
      record M
        { clock = next clock
        ; messages =
            map (λ where e → record e { delay = pred (delay e) })
              messages
        }
      where open State M

Updating the global state inserting the updated block-tree for a given party,
adding messages to the message buffer for the other parties and appending the
history

    _,_,_,_⇑_ : Message → Delay → PartyId → T → State → State
    m , d , p , l ⇑ M =
      record M
        { blockTrees = set p l blockTrees
        ; messages =
            map (uncurry ⦅_,_, m , d ⦆)
              (filter (¬? ∘ (p ≟_) ∘ proj₁) parties)
            ++ messages
        ; history = m ∷ history
        }
      where open State M

    add_to_diffuse_ : (Message × Delay × PartyId) → T → State → State
    add (m@(ChainMsg x) , d , p) to t diffuse M = m , d , p , newChain t x ⇑ M
    add (m@(VoteMsg x) , d , p) to t diffuse M = m , d , p , addVote t x ⇑ M

Fetching

A party receives messages from the global state by fetching messages assigned to
the party, updating the local block tree and putting the local state back into
the global state.

    data _⊢_[_]⇀_ : {p : PartyId} → Honesty p → State → Message → State → Type
      where

An honest party consumes a message from the global message buffer and updates
the local state

      honest : ∀ {p} {t t′} {m} {N} → let open State N in
          blockTrees ⁉ p ≡ just t
        → (m∈ms : ⦅ p , Honest , m , 𝟘 ⦆ ∈ messages)
        → t [ m ]→ t′
          ---------------------------------------------
        → Honest {p} ⊢
          N [ m ]⇀ record N
            { blockTrees = set p t′ blockTrees
            ; messages = messages ─ m∈ms
            }

An adversarial party might delay a message

      corrupt : ∀ {p} {as} {m} {N} → let open State N in
          (m∈ms : ⦅ p , Corrupt , m , 𝟘 ⦆ ∈ messages)
          ----------------------------------------------
        →  Corrupt {p} ⊢
          N [ m ]⇀ record N
            { messages = m∈ms ∷ˡ= ⦅ p , Corrupt , m , 𝟙 ⦆
            ; adversarialState = as
            }

Voting

Helper function for creating a vote

    createVote : SlotNumber → PartyId → MembershipProof → Signature → Hash Block → Vote
    createVote s p prf sig hb =
      record
        { votingRound = v-round s
        ; creatorId = p
        ; proofM = prf
        ; blockHash = hb
        ; signature = sig
        }

A party can vote for a block, if

• the current slot is the first slot in a voting round
• the party is a member of the voting committee
• the chain is not in a cool-down phase

Voting updates the party's local state and for all other parties a message
is added to be consumed immediately.

    infix 2 _⊢_⇉_

    data _⊢_⇉_ : {p : PartyId} → Honesty p → State → State → Type where

      honest : ∀ {p} {t} {M} {π} {σ} {b}
        → let
            open State
            s = clock M
            r = v-round s
            v = createVote s p π σ (hash b)
          in
        ∙ BlockSelection s t ≡ just b
        ∙ blockTrees M ⁉ p ≡ just t
        ∙ IsVoteSignature v σ
        ∙ StartOfRound s r
        ∙ IsCommitteeMember p r π
        ∙ VotingRule s t
          ───────────────────────────────────
          Honest {p} ⊢
            M ⇉ add (VoteMsg v , 𝟘 , p) to t
                diffuse M

Rather than creating a delayed vote, an adversary can honestly create it and
delay the message.

Block creation

Certificates are conditionally added to a block. The following function determines
if there needs to be a certificate provided for a given voting round and a local
block-tree. The conditions are as follows

a) There is no certificate from 2 rounds ago in certs
b) The last seen certificate is not expired
c) The last seen certificate is from a later round than
the last certificate on chain

    needCert : RoundNumber → T → Maybe Certificate
    needCert (MkRoundNumber r) t =
      let
        cert⋆ = latestCertOnChain t
        cert′ = latestCertSeen t
      in
        if not (any (λ {c → ⌊ roundNumber c + 2 ≟ r ⌋}) (certs t)) -- (a)
           ∧ (r ≤ᵇ A + roundNumber cert′)                          -- (b)
           ∧ (roundNumber cert⋆ <ᵇ roundNumber cert′)              -- (c)
        then just cert′
        else nothing

Helper function for creating a block

    createBlock : SlotNumber → PartyId → LeadershipProof → Signature → T → Block
    createBlock s p π σ t =
      record
        { slotNumber = s
        ; creatorId = p
        ; parentBlock =
            let open IsTreeType
            in tipHash (is-TreeType .valid t)
        ; certificate =
            let r = v-round s
            in needCert r t
        ; leadershipProof = π
        ; bodyHash =
            let txs = txSelection s p
            in blockHash
                 record
                   { blockHash = hash txs
                   ; payload = txs
                   }
        ; signature = σ
        }

A party can create a new block by adding it to the local block tree and
diffuse the block creation messages to the other parties. Block creation is
possible, if as in Praos

• the block signature is correct
• the party is the slot leader

Block creation updates the party's local state and for all other parties a
message is added to the message buffer

    infix 2 _⊢_↷_

    data _⊢_↷_ : {p : PartyId} → Honesty p → State → State → Type where

      honest : ∀ {p} {t} {M} {π} {σ}
        → let
            open State
            s = clock M
            b = createBlock s p π σ t
            pref = preferredChain t
          in
        ∙ blockTrees M ⁉ p ≡ just t
        ∙ ValidChain (b ∷ pref)
          ───────────────────────────
          Honest {p} ⊢
            M ↷ add (
                  ChainMsg (b ∷ pref)
                , 𝟘
                , p) to t
                diffuse M

Small-step semantics

The small-step semantics describe the evolution of the global state.

    variable
      M N O : State
      p : PartyId
      h : Honesty p

The relation allows

• Fetching messages at the beginning of each slot
• Block creation
• Voting
• Transitioning to next slot in the same voting round
• Transitioning to next slot in a new voting round

Note, when transitioning to the next slot we need to distinguish whether the
next slot is in the same or a new voting round. This is necessary in order to
detect adversarial behaviour with respect to voting (adversarialy not voting
in a voting round)

    data _↝_ : State → State → Type where

      Fetch : ∀ {m} →
        ∙ h ⊢ M [ m ]⇀ N
          ──────────────
          M ↝ N

      CreateVote :
        ∙ Fetched M
        ∙ h ⊢ M ⇉ N
          ─────────
          M ↝ N

      CreateBlock :
        ∙ Fetched M
        ∙ h ⊢ M ↷ N
          ─────────
          M ↝ N

      NextSlot :
        ∙ Fetched M
        ∙ NextSlotInSameRound M
          ─────────────────────
          M ↝ tick M

      NextSlotNewRound :
        ∙ Fetched M
        ∙ LastSlotInRound M
        ∙ RequiredVotes M
          ─────────────────
          M ↝ tick M

Reflexive, transitive closure

List-like structure for defining execution paths.

    infix  2 _↝⋆_
    infixr 2 _↣_
    infix  3 ∎

    data _↝⋆_ : State → State → Type where
      ∎ : M ↝⋆ M
      _↣_ : M ↝ N → N ↝⋆ O → M ↝⋆ O

Transitions of voting rounds

Transitioning of voting rounds can be described with respect of the small-step
semantics.

    data _↦_ : State → State → Type where

      NextRound : let open State in
          suc (v-rnd' M) ≡ v-rnd' N
        → M ↝⋆ N
        → M ↦ N

Reflexive, transitive closure

List-like structure for executions for voting round transitions

    infix  2 _↦⋆_
    infixr 2 _⨾_
    infix  3 ρ

    data _↦⋆_ : State → State → Type where
      ρ : M ↦⋆ M
      _⨾_ : M ↦ N → N ↦⋆ O → M ↦⋆ O

Specification of votes

Overview

Voting in Peras is mimicked after the sortition algorithm used in Praos, e.g it is based on the use of a Verifiable Random Function (VRF) by each stake-pool operator guaranteeing the following properties:

• The probability for each voter to cast their vote in a given round is correlated to their share of total stake,
• It should be computationally impossible to predict a given SPO's schedule without access to their secret key VRF key,
• Verification of a voter's right to vote in a round should be efficiently computable,
• A vote should be unique and non-malleable. (This is a requirement for the use of efficient certificates aggregation, see below.)

Additionally we would like the following property to be provided by our voting scheme:

• Voting should require minimal additional configuration (i.e., key management) for SPOs,
• Voting and certificates construction should be fast in order to ensure we do not interfere with other operations happening in the node.

We have experimented with two different algorithms for voting, which we detail below.

Structure of votes

We have used an identical structure for single Votes, for both algorithms. We define this structure as a CDDL grammar, inspired by the block header definition from cardano-ledger:

vote =
  [ voter_id         : hash32
  , voting_round     : round_no
  , block_hash       : hash32
  , voting_proof     : vrf_cert
  , voting_weight    : voting_weight
  , kes_period       : kes_period
  , kes_vkey         : kes_vkey
  , kes_signature    : kes_signature
  ]

This definition relies on the following primitive types (drawn from Ledger definitions in crypto.cddl)

round_no = uint .size 8
voting_weight = uint .size 8
vrf_cert = [bytes, bytes .size 80]
hash32 = bytes .size 32
kes_vkey = bytes .size 32
kes_signature = bytes .size 448
kes_period = uint .size 8

As already mentioned, Vote mimicks the block header's structure which allows Cardano nodes to reuse their existing VRF and KES keys. Some additional notes:

• Total vote size is 710 bytes with the above definition,
• Unless explicitly mentioned, hash function exclusively uses 32-bytes Blake2b-256 hashes,
• The voter_id is it's pool identifier, ie. the hash of the node's cold key.

Casting a vote

A vote is cast by a node using the following process which paraphrases the actual code

1. Define nonce as the hash of the epoch nonce concatenated to the peras string and the round number voted for encoded as 64-bits big endian value,
2. Generate a VRF Certificate using the node's VRF key from this nonce,
3. Use the node's KES key with current KES period to sign the VRF certificate concatenated to the block hash the node is voting for,
4. Compute voting weight from the VRF certificate using sortition algorithm (see details below).

Verifying a vote

Vote verification requires access to the current epoch's stake distribution and stake pool registration information.

1. Lookup the voter_id in the stake distribution and registration map to retrieve their current stake and VRF verification key,
2. Compute the nonce (see above),
3. Verify VRF certificate matches nonce and verification key,
4. Verify KES signature,
5. Verify provided KES verification key based on stake pool's registered cold verification key and KES period,
6. Verify provided voting weight according to voting algorithm.

Approaches to voter election

Leader-election like voting

The first algorithm is basically identical to the one used for Mithril signatures, and is also the one envisioned for Leios (see Appendix D of the recent Leios paper). It is based on the following principles:

• The goal of the algorithm is to produce a number of votes targeting a certain threshold such that each voter receives a number of vote proportionate to \(\sigma\), their fraction of total stake, according to the basic probability function \(\phi(\sigma) = 1 - (1 - f)^\sigma\),
• There are various parameters to the algorithm:
  • \(f\) is the fraction of slots that are "active" for voting
  • \(m\) is the number of lotteries each voter should try to get a vote for,
  • \(k\) is the target total number of votes for each round (e.g., quorum) \(k\) should be chosen such that \(k = m \cdot \phi(0.5)\) to reach a majority quorum,
• When its turn to vote comes, each node run iterates over an index \(i \in [1 \dots m]\), computes a hash from the nonce and the index \(i\), and compares this hash with \(f(\sigma)\): if it is lower than or equal, then the node has one vote.
  • Note the computation \(f(\sigma)\) is exactly identical to the one used for leader election.

We prototyped this approach in Haskell.

Sortition-like voting

The second algorithm is based on the sortition process initially invented by Algorand and implemented in their node. It is based on the same idea, namely that a node should have a number of votes proportional to their fraction of total stake, given a target "committee size" expressed as a fraction of total stake \(p\). And it uses the fact the number of votes a single node should get based on these parameters follows a binomial distribution.

The process for voting is thus:

• Compute the individual probability of each "coin" to win a single vote \(p\) as the ratio of expected committee size over total stake.
• Compute the binomial distribution \(B(n,p)\) where \(n\) is the node's stake.
• Compute a random number between 0 and 1 using nonce as the denominator over maximum possible value (e.g., all bits set to 1) for the nonce as denominator.
• Use bisection method to find the value corresponding to this probability in the CDF for the aforementioned distribution.

This yields a vote with some weight attached to it "randomly" computed so that the overall sum of weights should be around expected committee size.

This method has also been prototyped in Haskell.

Specification of certificates

Mithril certificates

Mithril certificates' construction is described in details in the Mithril paper and is implemented in the mithril network. It's also described in the Leios paper, in the appendix, as a potential voting scheme for Leios, and implicitly Peras.

Mithril certificates have the following features:

• They depend on BLS-curve signatures aggregation to produce a so-called State based Threshold Multi-Signature that's easy to verify,
• Each node relies on a random lottery as described in the previous section to produce a vote weighted by their share of total stake,
• The use of BLS signatures implies nodes will need to generate and exchange specialized keys for the purpose of voting, something we know from Mithril is somewhat tricky as it requires some form of consensus to guarantee all nodes have the exact same view of the key set.

ALBA

Approximate Lower Bound Arguments or ALBAs in short, are a novel cryptographic algorithm based on a telescope construction providing a fast way to build compact certificates out of a large number of unique items. A lot more details are provided in the paper, on the website and the GitHub repository where implementation is being developed, we only provide here some key information relevant to the use of ALBAs in Peras.

Proving & verification time

ALBA's expected proving time is benchmarked in the following picture which shows mean execution time for generating a proof depending on: The total number of votes, the actual number of votes (\(s_p\)), the honest ratio (\(n_p\)). Note that as proving time increases exponentially when \(s_p \rightarrow total \cdot n_p\), we only show here the situation when \(s_p = total\) and \(s_p = total - total \cdot n_p / 2\) to ensure graph stays legible.

The following diagram is an excerpt from the ALBA benchmarks highlighting verification. Note these numbers do not take into account the time for verifying individual votes. As one can observe directly from these graphs, verification time is independent from the number of items and only depends on the \(n_p/n_f\) ratio.

In practice, as the number of votes is expected to be in the 1000-2000 range, and there is ample time in a round to guarantee those votes are properly delivered to all potential voting nodes (see below), we can safely assume proving time of about 5 ms, and verification time under a millisecond.

Certificate size

For a given set of parameters, namely fixed values for \(\lambda_{sec}\), \(\lambda_{rel}\), and \(n_p/n_f\), the proof size is perfectly linear and only depends on the size of each vote.

Varying the security parameter and the honest votes ratio for a fixed set of 1000 votes of size 200 yields the following diagram, showing the critical factor in proof size increase is the \(n_p/n_f\) ratio: As this ratio decreases, the number of votes to include in proof grows superlinearly.

Benchmarks

In the following tables we compare some relevant metrics between the two different kind of certificates we studied, Mithril certificates (using BLS signatures) and ALBA certificates (using KES signatures): Size of certificate in bytes, proving time (e.g., the time to construct a single vote), aggregation time (the time to build a certificate), and verification time.

For Mithril certificates, assuming parameters similar to mainnet's (\(k=2422, m=20973, f=0.2\)):

For ALBA certificates, assuming 1000 votes, a honest to faulty ratio of 80/20, and security parameter \(λ=128\). Note the proving time does not take into account individual vote verification time, whereas certificate's verification time includes votes verification time.

Network diffusion of votes

Building on previous work, we built a ΔQ model to evaluate the expected delay to reach quorum.
The model works as follows:

• We start from a base uniform distribution of single MTU latency between 2 nodes, assuming a vote fits in a single TCP frame. The base latencies are identical as the one used in previous report.
• We then use the expected distribution of paths length for a random graph with 15 average connections, to model the latency distribution across the network, again reusing previously known values.
• We then apply the NToFinish 75 combinator to this distribution to compute the expected distribution to reach 75% of the votes (quorum).
• An important assumption is that each vote diffusion across the network is expected to be independent from all other votes.
• Verification time for a single vote is drawn from the above benchmarks, but we also want to take into account the verification time of a single vote, which we do in two different ways:
  • One distribution assumes a node does all verifications sequentially, one vote at a time
  • Another assumes all verifications can be done in parallel
  • Of course, the actual verification time should be expected to be in between those 2 extremes

Using the "old" version of ΔQ library based on numerical (e.g., Monte-Carlo) sampling, yields the following graph:

This graph tends to demonstrate vote diffusion should be non-problematic, with a quorum expected to be reached in under 1 second most of the time to compare with a round length of about 2 minutes.

At the time of this writing, a newer version of the ΔQ library based on piecewise polynomials is available. Our attempts to use it to model votes diffusion were blocked by the high computational cost of this approach and the time it takes to compute a model, specifically about 10 minutes in our case. The code for this experiment is available as a draft PR #166.

In the old version of ΔQ based on numerical sampling, which have vendored in our codebase, we introduced a NToFinish combinator to model the fact we only take into account some fraction of the underlying model. In our case, we model the case where we only care about the first 75% of votes that reach a node.

Given convolutions are the most computationally intensive part of a ΔQ model, it seems to us a modeling approach based on discrete sampling and vector/matrices operations would be quite efficient. We did some experiment in that direction, assessing various approaches in Haskell: A naive direct computation using Vectors, FFT-based convolution using vectors, and hmatrix' convolution function.

This quick-and-dirty spike lead us to believe we could provide a fast and accurate ΔQ modelling library using native vector operations provided by all modern architectures, and even scale to very large model using GPU libraries.

Rationale: how does this CIP achieve its goals?

• relate the spec with the motivation? -> ticking the boxes
• Provide numbers from simulations/models

We have refined our analysis and understanding of Peras protocol, taking into account its latest evolution:

• A promising solution for votes and certificates construction has been identified based on existing VRF/KES keys and ALBAs certificates.
  • This solution relies on existing nodes' infrastructure and cryptographic primitives and therefore should be straightforward to implement and deploy.
• Peras's votes and certificates handling will have a negligible impact on existing node CPU, network bandwidth, and memory requirements.
  • They will have a moderate impact on storage requirements leading to a potential increase of disk storage of 15 to 20%..
  • Peras might have a moderate economical impact for SPOs running their nodes with cloud providers due to increasing network egress traffic.
• Peras's impact on settlement probabilities depends strongly upon the specific choices for protocol parameters and upon which stakeholder use case(s) those have been tuned for.
  • Settlement can be as fast as two minutes, with an infinitesimal probability of rollback after that, but there is an appreciable probability of rollback prior to that time if a strong adversary attacks.
  • Stakeholders will have to reach consensus about the relative importance of settlement time versus pre-settlement resistance to attacks.
• We think development of a pre-alpha prototype integrated with the cardano-node should be able to proceed.

Peras provides demonstrably fast settlement without weakening security or burdening nodes. The settlement time varies as a function of the protocol-parameter settings and the prevalence of adversarial stake. For a use case that emphasizes rapid determination of whether a block is effectively finally incorporated into the preferred chain, it is possible to achieve settlement times as short as two minutes, but at the expense of having to resubmit rolled-back transactions in cases where there is a strong adversarial stake.

The impact of Peras upon nodes falls into four categories: network, CPU, memory, and storage. We have provided evidence that the CPU time required to construct and verify votes and certificates is much smaller than the duration of a voting round. Similarly, the memory needed to cache votes and certificates and the disk space needed to persist certificates is trivial compared to the memory needed for the UTXO set and the disk needed for the blocks.

On the networking side, our ΔQ studies demonstrate that diffusion of Peras votes and certificates consumes minimal bandwidth and would not interfere with other node operations such as memory-pool and block diffusion. However, diffusion of votes and certificates across a network will still have a noticeable impact on the volume of data transfer, in the order of 20%, which might translate to increased operating costs for nodes deployed in cloud providers.

In terms of development impacts and resources, Peras requires only a minimal modification to the ledger CDDL and block header. Around cool-down periods, a certificate hash will need to be included in the block header and the certificate itself in the block. Implementing Peras does not require any new cryptographic keys, as the existing VRF/KES will be leveraged. It will require an implementation of the ALBA algorithm for creating certificates. It does require a new mini-protocol for diffusion of votes and certificates. The node's logic for computing the chain weight needs to be modified to account for the boosts provided by certificates. Nodes will have to persist all certificates and will have to cache unexpired votes. They will need a thread (or equivalent) for verifying votes and certificates. Peras only interacts with Genesis and Leios in the chain-selection function and it is compatible with the historical evolution of the blockchain. A node-level specification and conformance test will also need to be written.

In no way does Peras weaken any of the security guarantees provided by Praos or Genesis. Under strongly adversarial conditions, where an adversary can trigger a Peras voting cool-down period, the protocol in essence reverts to the Praos (or Genesis) protocol, but for a duration somewhat longer than the Praos security parameter. Otherwise, settlement occurs after each Peras round. This document has approximately mapped the trade-off between having a short duration for each round (and hence faster settlement) versus having a high resistance to an adversary forcing the protocol into a cool-down period. It also estimates the tradeoff between giving chains a larger boost for each certificate (and hence stronger anchoring of that chain) versus keeping the cool-down period shorter.

Use Cases

Main benefit is that Peras drastically decreases the need to wait for confirmation for transactions, from minutes/hours to seconds/minutes

• I would highlight Peras making Cardano more attractive option for interoperability solutions like LayerZero, Axelar, WormHole, etc. Maybe we can even go as far to state that Peras is a pre-requisite for this?
• Sidechains
• Exchanges?
• DApps/service providers, basically anyone accepting or using ADAs, and anyone building some service on top of cardano with some kind of sensitivity to time

Attacks and Mitigations

Resource Requirements

In this section, we evaluate the impact on the day-to-day operations of the Cardano network and cardano nodes of the deployment of Peras protocol, based on the data gathered over the course of project.

In this section, we evaluate the impact on the day-to-day operations of the Cardano network and cardano nodes of the deployment of Peras protocol, based on the data gathered over the course of project.

Network

Network traffic

For a fully synced nodes, the impact of Peras on network traffic is modest:

• For votes, assuming \(U \approx 100\), a committee size of 2000 SPOs, a single vote size of 700 bytes, means we will be adding an average of 14 kB/s to the expected traffic to each node,
• For certificates, assuming an average of 50 kB size (half way between Mithril and ALBA sizes) means an negligible increase of 0.5 kB/s on average. Note that a node will download either votes or certificate for a given round, but never both so these numbers are not cumulative.

A non fully synced nodes will have to catch-up with the tip of the chain and therefore download all relevant blocks and certificates. At 50% load (current monthly load is 34% as of this writing), the chain produces a 45 kB block every 20 s on average. Here are back-of-the-napkin estimates of the amount of data a node would have to download (and store) for synchronizing, depending on how long it has been offline:

Network costs

We did some research on network pricing for a few major Cloud and well-known VPS providers, based on the share of stakes each provider is reported to support, and some typical traffic pattern as exemplified by the following picture (courtesy of Markus Gufler).

The next table compares the cost (in US$/month) for different outgoing data transfer volumes expressed as bytes/seconds, on similar VMs tailored to cardano-node's hardware requirements (32GB RAM, 4+ Cores, 500GB+ SSD disk). The base cost of the VM is added to the network cost to yield total costs depending on transfer rate.

For an AWS hosted SPO, which represent about 20% of the SPOs, a 14 kB/s increase in traffic would lead to a cost increase of $3.8/mo (34 GB times $0.11/GB). This represents an average across the whole network: depending on the source of the vote and its diffusion pattern, some nodes might need to send a vote to more than one downstream peer which will increase their traffic, while other nodes might end up not needing to send a single vote to their own peers. Any single node in the network is expected to download each vote at most once.

Persistent storage

Under similar assumptions, we can estimate the storage requirements entailed by Peras: Ignoring the impact of cooldown periods, which last for a period at least as long as \(k\) blocks, the requirement to store certificates for every round increases node's storage by about 20%.

Votes are expected to be kept in memory so their impact on storage will be null.

CPU

In the Votes & Certificates section we've provided some models and benchmarks for votes generation, votes verification, certificates proving and certificates verification, and votes diffusion. Those benchmarks are based on efficient sortition-based voting and ALBAs certificate, and demonstrate the impact of Peras on computational resources for a node will be minimal. Moreover, the most recent version of the algorithm detailed in this report is designed in such a way the voting process runs in parallel with block production and diffusion and therefore is not on this critical path.

Voting:

• Single Voting (Binomial): 139.5 μs
• Single Verification (binomial): 160.9 μs
• Single Voting (Taylor): 47.02 ms

The implementation takes some liberty with the necessary rigor suitable for cryptographic code, but the timings provided should be consistent with real-world production grade code. In particular, when using nonce as a random value, we only use the low order 64 bits of the nonce, not the full 256 bits.

Memory

A node is expected to need to keep in memory:

• Votes for the latest voting round: For a committee size of 1000 and individual vote size of 700 bytes, that's 700 kB.
• Cached certificates for voting rounds up to settlement depth, for fast delivery to downstream nodes: With a boost of 10/certificate, settlement depth would be in the order of 216 blocks, or 4320 seconds, which represent about 10 rounds of 400 slots. Each certificate weighing 50 kB, that's another 500 kB of data a node would need to cache in memory.

Peras should not have any significant impact on the memory requirements of a node.

Path to Active

Acceptance Criteria

• Conformance test suite passes on cardano-node

Implementation Plan

• Updated CIP Specification with full detail - assuming we will publish the CIP with some details to be figured out.
• Need to figure out IOI/Intersect dance?
• Sketch a generic plan
• Some incremental deployment possible?
  • Vote casting and diffusion
  • Certificate baking and diffusion
  • Chain selection based on weight as heuristic
  • Full chain selection

Integration into Cardano Node

In the previous report, we already studied how Peras could be concretely implemented in a Cardano node. Most of the comments there are still valid, and we only provide here corrections and additions when needed. We have addressed resources-related issue in a previous section.

The following picture summarizes a possible architecture for Peras highlighting its interactions with other components of the system.

The main impacts identified so far are:

• There is no impact in the existing block diffusion process, and no changes to block headers structure.
• Block body structure needs to be changed to accomodate for a certificate when entering cooldown period.
• Consensus best chain selection algorithm needs to be aware of the existence of a quorum to compute the weight of a possible chain, which is manifested by a certificate from the Peras component.
  • Consensus will need to maintain or query a list of valid certificates (e.g., similar to volatile blocks) as they are received or produced.
  • Chain selection and headers diffusion is not dependent on individual votes.
• Peras component can be treated as another chain follower to which new blocks and rollbacks are reported.
  • Peras component will also need to be able to retrieve current stake distribution.
  • It needs to have access to VRF and KES keys for voting, should we decide to forfeit BLS signature scheme.
• Dedicated long term storage will be needed for certificates.
• Networking layer will need to accomodate (at least) two new mini-protocols for votes and certificates diffusion.
  • This seems to align nicely with current joint effort on Mithril integration.
• Our remarks regarding the possible development of a standalone prototype interacting with a modifified adhoc node still stands and could be a good next step.

Defining Protocol Parameters values

In order to provide useful recommendations for the protocol parameters, we first need to understand what is their admissible range of values, e.g. the constraints stemming from practical and theoretical needs, and to analyse their impact on the settlement probabilities.

Constraints on Peras Parameters

The following constraints on Peras parameters arise for both theoretical and practical considerations.

Settlement probabilities

In the estimates below, we define the non-settlement probability as the probability that a transaction (or block) is rolled back. Note that this does not preclude the possibility that the transaction could be included in a later block because it remained in the memory pool of a node that produced a subsequent block. Because there are approximately 1.5 million blocks produced per year, even small probabilities of non-settlement can amount to an appreciable number of discarded blocks.

Case 1: Blocks without boosted descendants

Blocks that are not cemented by a boost to one of their descendant (successor) blocks are most at risk for being rolled back because they are not secured by the extra weight provided by a boost.

The Variant 2 scenario in the Adversarial chain receives boost section above dominates the situation where a transaction is recorded in a block but an adversarial fork later is boosted by a certificate to become the preferred chain. This scenario plays out as follows:

1. Both the honest chain and an initially private adversarial chain have a common prefix that follows the last boosted block.
2. The adversary privately grows their chain and does not include transactions in the memory pool.
3. When the time comes where the last block is first eligible for later being voted upon, the adversarial chain is published and all parties see that it is longer than the honest chain.
4. Hence the newly published adversarial chain becomes the preferred chain, and all parties build upon that.
5. Later, when voting occurs, the chain that had been adversarial will received the boost.
6. Because the adversarial prefix has been boosted, there is a negligible probability that the discarded portion of the honest chain will ever become part of the preferred chain.
7. Therefore the preferred chain does not include any transactions that were in blocks of the honest chain after the common prefix and before the adversarially boosted block.

Note that this is different from the situation where a transaction is included on honest forks because such a transaction typically reaches the memory pool of the block producers on each fork and is included on each. The adversary refrains from including the transaction on their private chain.

The active-slot coefficient (assumed to be 5%), the length of the rounds, and the adversary's fraction of stake determine the probability of non-settlement in such a scenario. The table below estimates this probability. For example, in the presence of a 5% adversary and a round length of 360 slots, one could expect about two blocks to be reverted per year in such an attack.

Using the approach of Gaži, Ren, and Russell (2023) and setting \(\Delta = 5 \text{\,slots}\) to compute the upper bound on the probability of failure to settle results in similar, but not identical probabilities.

Case 2: Blocks with boosted descendants

Once one of a block's descendants (successors) has been boosted by a certificate, it is much more difficult for an adversary to cause it to be rolled back because they adversary must overcome both count of blocks on the preferred, honest chain and the boost that chain has already received.

The Healing from adversarial boost section above provides the machinery for estimating the probability of an adversary building a private fork that has more weight than a preferred, honest chain that has been boosted. The scenario plays out as follows:

1. Both the honest chain and an initially private adversarial chain have a common prefix that precedes the last boosted block.
2. The adversary privately grows their chain.
3. When the adversary's chain is becomes long enough to overcome both the honest blocks and the boost, the adversarial chain is published and all parties see that it is longer than the honest chain.
4. Hence the newly published adversarial chain becomes the preferred chain, and all parties build upon that.
5. Therefore the preferred chain does not include any transactions that were in blocks of the honest chain after the common prefix.

Typically, the adversary would only have a round's length of slots to build sufficient blocks to overcome the boosted, honest, preferred fork. After that, the preferred fork would typically receive another boost, making it even more difficult for the adversary to overcome it. The table below shows the probability that of non-settlement for a block after the common prefix but not after the subsequent boosted block on the honest chain, given a 5% active slot coefficient and a 5 blocks/certificate boost.

A boost of 10 blocks/certificate makes the successful adversarial behavior even less likely.

A boost of 15 blocks/certificate makes the successful adversarial behavior even less likely.

Recommendations for Peras parameters

Based on the analysis of adversarial scenarios, a reasonable set of default protocol parameters for further study and simulation is show in the table below. The optimal values for a real-life blockchain would depend strongly upon external requirements such as balancing settlement time against resisting adversarial behavior at high values of adversarial stake. This set of parameters is focused on the use case of knowing soon whether a block is settled or rolled back; other sets of parameters would be optimal for use cases that reduce the probability of roll-back at the expense of waiting longer for settlement.

A block-selection offset of \(L = 30 \text{\,slots}\) allows plenty of time for blocks to diffuse to voters before a vote occurs. Combining this with a round length of \(U = 90 \text{\, slots}\) ensures that there is certainty in \(U + L = 120 \text{\,slots}\) as to whether a block has been cemented onto the preferred chain by the presence of a certificate for a subsequent block. That certainty of not rolling back certified blocks is provided by a certification boost of \(B = 15 \text{\,blocks}\) because of the infinitesimal probability of forging that many blocks on a non-preferred fork within the time \(U\). Thus, anyone seeing a transaction appearing in a block need wait no more than two minutes to be certain whether the transaction is on the preferred chain (effectively permanently, less than a one in a trillion probability even at 45% adversarial stake) versus having been discarded because of a roll back. Unless the transaction has a stringent time-to-live (TTL) constraint, it can be resubmitted in the first \(U - L = 60 \text{\,slots}\) of the current round, or in a subsequent round.

The Praos security parameter \(k_\text{praos} = 2160 \text{\,blocks} \approx 43200 \text{\,slots} = 12 \text{\,hours}\) implies a ~17% probability of a longer private adversarial chain at 49% adversarial stake. At that same probability, having to overcome a \(B = 15 \text{\,blocks}\) adversarial boost would require \(k_\text{peras} \approx 70200 \text{\,slots} = 3510 \text{\,blocks} = 19.5 \text{\,hours}\). This determines the certificate-expiration time as \(A = k_\text{peras} - k_\text{praos} = 27000 \text{\,slots}\), the chain-ignorance period as \(R = \left\lceil A / U \right\rceil = 300 \text{\,rounds}\), and the cool-down period as \(K = \left\lceil k_\text{peras} / U \right\rceil = 780 \text{\,rounds}\).

The committee size of \(n = 900 \text{\,parties}\) corresponds to a one in a million chance of not reaching a quorum if 10% of the parties do not vote for the majority block (either because they are adversarial, offline, didn't receive the block, or chose to vote for a block on a non-preferred fork). This "no quorum" probability is equivalent to one missed quorum in every 1.2 years. The quorum size of \(\tau = \left\lceil 3 n / 4 \right\rceil = 675 \text{\,parties}\) is computed from this.

Copyright

This CIP is licensed under Apache-2.0.