CPD

Ouroboros Randomness Generation Sub-Protocol - The coin-flipping Problem

Cardano Problem Definition (CPD)

This document is a Cardano Problem Definition (CPD), from which the Cardano Problem Statement (CPS): Ouroboros Randomness Manipulation is derived.

While the CPS is being structured for formal submission with a focus on accessibility, and alignment with the CIP process, this CPD retains the full depth of technical material that shaped the problem understanding. It preserves detailed modeling, cost definitions, and adversarial analysis that could not be fully included in the CPS due to scope and formatting constraints.

The CPD thus complements the CPS by serving as its technical foundation and extended reference, providing the complete analytical context behind the identified problem.

Abstract

A well-designed consensus protocol is inherently modular, comprising multiple sub-protocols that collectively ensure security, efficiency, and decentralization. Among these, the Randomness Generation Sub-Protocol is pivotal in tackling the Coin-Flipping Problem—the challenge of generating fair, unbiased, and unpredictable randomness in a distributed environment.

This issue is especially critical in Ouroboros, where randomness underpins essential sub-protocols like leader election. A robust and tamper-resistant randomness mechanism is vital to maintaining the protocol’s security, fairness, and integrity.

This CPD delineates this challenge within the context of Ouroboros Praos, analyzing its approach and its vulnerability to grinding attacks, where adversaries attempt to manipulate leader election outcomes. The document offers:

• An analysis of attack vectors, their economic and computational prerequisites, and Cardano’s current resilience.
• A quantification of attack feasibility, highlighting escalation beyond a 20% stake threshold.
• Pivotal questions: Is manipulation occurring? What is Cardano’s vulnerability? How might threats be mitigated?

Rather than prescribing specific solutions, this CPD urges the Cardano community to take responsibility for addressing these risks, potentially through advancements in detection, stake distribution, or protocol design. It establishes a rigorous foundation for understanding these issues and solicits collaborative efforts to bolster Ouroboros’ resilience against evolving adversarial strategies.

Summary of Findings

This CPD undertakes a thorough examination of the Randomness Generation Sub-Protocol within the Ouroboros framework, focusing on the Coin-Flipping Problem and its implications for the security of the Cardano blockchain. The principal findings are as follows:

• Randomness Mechanism: Ouroboros Praos utilizes VRFs for efficient randomness generation, yet this design exposes vulnerabilities to grinding attacks, wherein adversaries manipulate nonce values to influence leader election processes.
• Attack Feasibility: The likelihood and impact of successful attacks rise significantly when an adversary controls >20% of total stake (~4.36 billion ADA, March 2025), while lesser stakes (e.g., 5%) render such efforts statistically improbable over extended periods.
• Economic Considerations: Acquiring substantial stake entails a significant financial commitment—on the order of billions of USD for a 20% share—further complicated by potential asset devaluation if an attack undermines network integrity.
• Computational Requirements: Scenario analysis across varying grinding depths ($\rho$) reveals a spectrum of feasibility:
  • Minor attacks (e.g., $\rho=20$, costing ~$56) are readily achievable.
  • Significant manipulations (e.g., $\rho=50$, costing ~$3.1 billion) demand resources ranging from feasible to borderline infeasible, contingent upon adversary capabilities.
  • The cost disparity between the most resource-intensive scenario (Owl Survey) and the least (Ant Glance) is substantial, with a consistent $\Delta \log_{10}(\text{Cost (USD)}) \sim 6.3$, indicating Owl Survey costs approximately $10^{6.3}$ times more than Ant Glance, driven by the significant influence of $T_{\text{eval}}$ (evaluation complexity) and $w_T$ (target window scope).

The table below delineates the $\rho$ values at which each scenario transitions across feasibility categories, illustrating the computational and economic thresholds:

✏️ Note: For a detailed explanation of these scenarios and their feasibility thresholds, refer to Section 3.5 - Scenarios within this CPD.

This document deliberately avoids advocating specific countermeasures, instead presenting these findings to highlight extant vulnerabilities and their associated costs. It is incumbent upon the Cardano community to assess and address these challenges, potentially through:

• Development of enhanced detection mechanisms,
• Improvement of stake pool diversity, or
• Introduction of protocol-level innovations.

Stakeholders are invited to engage with this CPD in its entirety to validate the analysis, deepen their comprehension, and assume ownership of subsequent solutions. Contributions are welcomed via the ongoing discourse at https://github.com/cardano-foundation/CIPs/pull/1009, aimed at collectively fortifying the Ouroboros protocol.

1. Preliminaries

This section introduces the pertinent parts of the Cardano proof- of-stake consensus protocol. We focus on randomness generation and leader selection and omit irrelevant protocol details.

1.1 Fundamental Properties

A protocol implements a robust transaction ledger if it maintains the ledger as a sequence of blocks, where each block is associated with a specific slot. Each slot can contain at most one ledger block, and this strict association ensures a well-defined and immutable ordering of transactions within the ledger.

The protocol must satisfy the following two critical properties (Persistence & Liveness), which ensure that blocks and transactions are securely committed and cannot be easily manipulated by adversaries. Persistence and liveness, can be derived to fundamental chain properties which are used to explain how and why the leader election mechanism has been designed in this manner.

1.1.1 Transaction Ledger Properties

1.1.1.1 Persistence with the security parameter $` \text{k} \in \mathbb{N} `$

Once a node of the system proclaims a certain transaction tx in the stable part of its ledger, all nodes, if queried, will either report tx in the same position of that ledger or report a stable ledger which is a prefix of that ledger. Here the notion of stability is a predicate that is parameterized by a security parameter $` \text{k} `$. Specifically, a transaction is declared stable if and only if it is in a block that is more than $` \text{k} `$ blocks deep in the ledger.

1.1.1.2 Liveness with the transaction confirmation time parameter $` u \in \mathbb{N} `$

If all honest nodes in the system attempt to include a certain transaction then, after the passing of time corresponding to $`\text{u}`$ slots (called the transaction confirmation time), all nodes, if queried and responding honestly, will report the transaction as stable.

1.1.2 Chain properties

Persistence and liveness can be derived from basic chain properties, provided that the protocol structures the ledger as a blockchain—a sequential data structure. The following key chain properties ensure that the blockchain behaves securely and efficiently:

1.1.2.1 Common Prefix (CP): With the security parameter $`k \in \mathbb{N}`$.

Consider 2 chains $C_1$ and $C_2$ adopted by 2 honest parties at the onset of slots $sl_1$ and $sl_2$, respectively, where $sl_1 \leq sl_2$. The chains must satisfy the condition:

Where:

• $C_1^{\lceil k \rceil}$ represents the chain obtained by removing the last $k$ blocks from $C_1$.
• $\preceq$ denotes the prefix relation.

This ensures that the shorter chain is a prefix of the longer one, ensuring consistency across honest parties.

1.1.2.2 Existential Chain Quality (∃CQ): With parameter $s \in \mathbb{N}$ (Minimum Honest Block Inclusion Interval).

Consider a chain $C$ adopted by an honest party at the onset of a slot. For any portion of $C$ spanning $s$ prior slots, there must be at least one honestly-generated block within this portion. This ensures that the chain includes contributions from honest participants. In practical terms, $s$ defines the length of a "safety window" where honest contributions are guaranteed.

1.1.2.3 Chain Growth (CG): With parameters $\tau \in (0, 1]$ (speed coefficient) and $s \in \mathbb{N}$ (Minimum Honest Block Inclusion Interval).

The Chain Growth (CG) property is a more general concept that combines both the speed of block production and the frequency of honest contributions. It uses two parameters: $\tau$, the speed coefficient, which governs how fast the chain grows, and $s$, the Minimum Honest Block Inclusion Interval, which ensures that honest blocks are consistently produced within a given interval of slots.

Consider a chain $C$ held by an honest party at the onset of a slot. For any portion of $C$ spanning $s$ contiguous prior slots . The number of blocks in this portion must be at least $\tau s$. The parameter $\tau$ determines the fraction of slots in which blocks are produced. For example, if $\tau = 0.5$ and $s = 10$, there should be at least 5 blocks produced within that span.

For example, if $\tau = 0.5$ and $s = 10$, then at least $\tau s = 0.5 \cdot 10 = 5$ honest blocks must be produced over the span of those 10 slots.

1.2 The Coin-Flipping Problem

The Coin-Flipping Problem is a fundamental challenge in distributed systems that require a fair, unbiased, and unpredictable source of randomness—without allowing any single participant to manipulate the outcome.

1.2.1 Defining the Problem

Consider a scenario where multiple untrusted parties must flip a coin to reach a decision. The challenge is ensuring that:

1. 🎲 The outcome remains random and unpredictable.
2. 🔒 No participant can bias or influence the result in their favor.
3. ⚖️ The process is fair and secure, even in the presence of dishonest or colluding actors.

In blockchain consensus protocols, randomness is crucial for leader election, committee selection, and cryptographic lotteries. If an adversary can bias the randomness, they can increase their influence over block production, delay settlements, or disrupt network security.

1.2.2 Strategies for Randomness Generation

Various cryptographic techniques exist to address the coin-flipping problem in decentralized settings. These methods differ in security, efficiency, and resistance to adversarial manipulation.

1.2.3 The Historical Evolution of Ouroboros Randomness Generation

The Ouroboros family of protocols has evolved over time to optimize randomness generation while balancing security, efficiency, and decentralization. Initially, Ouroboros Classic used a secure multi-party computation (MPC) protocol with Publicly Verifiable Secret Sharing (PVSS) to ensure unbiased randomness. While providing strong security guarantees, PVSS required quadratic message exchanges between committee members, introducing significant communication overhead. This scalability bottleneck limited participation and hindered the decentralization of Cardano's consensus process.

Recognizing these limitations, Ouroboros Praos moved to a VRF-based randomness generation mechanism where each individual randomness contribution is generated with VRFs. Here, each block includes a VRF value computed from a determinitic message. The randomn nonce for an epoch is then derived from the concatenation and hashing of all these values from a specific section of the previous epoch’s chain. This significantly reduces communication complexity to linear in the number of block producers, making randomness generation scalable and practical while maintaining adequate security properties.

However, this efficiency gain comes at a cost: it introduces a limited avenue for randomness manipulation. Adversaries can attempt grinding attacks, evaluating multiple potential nonces and selectively influencing randomness outcomes. While constrained, this trade-off necessitates further countermeasures to limit adversarial influence while maintaining protocol scalability.

1.2.4 Comparing Ouroboros Randomness Generation with Ethereum

Ethereum RANDAO protocol was first based on a commit and reveal approach where each block producer would commit to random values in a first period, i.e. publish the hash of a locally generated random value during block proposal, before revealing them in a second. As the latter period finished, all revealed values were combined, more specifically XORed, together to finally get the random nonce.

Ethereum's Post-Merge RANDAO protocol remains mostly the same, but instead of using a commit-reveal approach, each contributor generate randomness deterministically by using VRF, making these values verifiables. These values are finally, as before, sequentially aggregated using XOR, forming the final randomness output used in validator shuffling and protocol randomness. This version of the protocol is very similar to Ouroboros Praos' where hashing is used instead of XOR to combine contributors' randomness together, and does not rely on commitees.

While decentralized and computationally lightweight, RANDAO still suffers from last-revealer bias, where the final proposers in an epoch can withhold their reveals to manipulate randomness. As such, Ethereum has spent some time studying Verifiable Delayed Functions (VDFs) to prevent the last revealer attack. Subsequently, Ethereum decided against integrating Verifiable Delay Functions due to feasibility concerns, including the difficulty of practical deployment and the risk of centralization stemming from specialized hardware dependencies. The instead opted for a frequent reseeding mechanism to strengthen the commitee selection in order to mitigate biases which, unfortunately does not fully eliminate last-mover manipulation concerns.

VDFs are designed to provide unpredictable, verifiable randomness by requiring a sequential computation delay before revealing the output. This makes them resistant to grinding attacks since adversaries cannot efficiently evaluate multiple outcomes. However, they introduce significant computational costs, require specialized hardware for efficient verification, and demand additional synchronization mechanisms.

1.2.5 Conclusion: The reasons behind Ouroboros Praos

Despite some security trade-offs, non-interactively combining VRFs was selected for Ouroboros Praos due to its balance between efficiency, scalability, and security. Unlike PVSS, we do not require a multi-party commit-reveal process or quadratic communication overhead.

However, ongoing research continues to explore potential enhancements to mitigate grinding risks, including hybrid randomness beacons that combine VRFs with cryptographic delay mechanisms.

1.3 Leader Election in Praos

1.3.1 Oblivious Leader Selection

As Explained into DGKR18 - Ouroboros Praos_ An adaptively-secure, semi-synchronous proof-of-stake blockchain, Praos protocol possesses the following basic characteristics :

• Privacy: Only the selected leader knows they have been chosen as slot leader until they reveal themselves, often by publishing a proof. This minimizes the risk of targeted attacks against the leader since other network participants are unaware of the leader's identity during the selection process.

• Verifiable Randomness: The selection process uses verifiable randomness functions (VRFs) to ensure that the leader is chosen fairly, unpredictably, and verifiably. The VRF output acts as a cryptographic proof that the selection was both random and valid, meaning others can verify it without needing to know the leader in advance.

• Low Communication Overhead: Since the identity of the leader is hidden until the proof is revealed, Oblivious Leader Selection can reduce communication overhead and minimize the chance of network-level attacks, such as Distributed Denial of Service (DDoS) attacks, aimed at preventing the leader from performing their role.

Based on their local view, a party is capable of deciding, in a publicly verifiable way, whether they are permitted to produce the next block, they are called a slot leader. Assuming the block is valid, other parties update their local views by adopting the block, and proceed in this way continuously. At any moment, the probability of being permitted to issue a block is proportional to the relative stake a player has in the system, as reported by the blockchain itself :

1. potentially, multiple slot leaders may be elected for a particular slot (forming a slot leader set);
2. frequently, slots will have no leaders assigned to them; This is defined by the Active Slot Coefficient f
3. a priori, only a slot leader is aware that it is indeed a leader for a given slot; this assignment is unknown to all the other stakeholders—including other slot leaders of the same slot—until the other stakeholders receive a valid block from this slot leader.

1.3.2 Application of Verifiable Random Function (VRF)

The VRF is used to generate randomness locally in the protocol, making the leader election process unpredictable. It ensures that:

• A participant is privately and verifiably selected to create a block for a given slot.
• The VRF output is both secret (only known to the selected leader) and verifiable (publicly checkable).

To determine whether a participant is the slot leader of $`\text{slot}_t`$ in epoch $`\text{epoch}_e`$, they first generate a VRF output and proof using their secret VRF key out of the slot number $`\text{slot}_t`$ and current epoch random nonce $`\eta_\text{e}`$. They then compare this value with a threshold $`\text{Threshold}^\text{participant}_\text{e}`$ that is computed from the participant's relative stake at the beginning of the epoch. If the VRF output is smaller than the threshold, they become the slot leader of $`\text{slot}_t`$. In that case, when publishing a block for this slot, they include in the block header $` \text{BlockHeader}_\text{t} `$, the $` \text{SlotLeaderProof}_\text{t} `$ comprising the VRF proof.

-- | The body of the header is the part which gets hashed to form the hash
-- chain.
data HeaderBody crypto = HeaderBody
  { -- | block number
    hbBlockNo  :: !BlockNo,
    -- | block slot
    hbSlotNo   :: !SlotNo,
    -- | Hash of the previous block header
    hbPrev     :: !(PrevHash crypto),
    -- | verification key of block issuer
    hbVk       :: !(VKey 'BlockIssuer crypto),
    -- | VRF verification key for block issuer
    hbVrfVk    :: !(VerKeyVRF crypto),
    -- | Certified VRF value
    hbVrfRes   :: !(CertifiedVRF crypto InputVRF),
    -- | Size of the block body
    hbBodySize :: !Word32,
    -- | Hash of block body
    hbBodyHash :: !(Hash crypto EraIndependentBlockBody),
    -- | operational certificate
    hbOCert    :: !(OCert crypto),
    -- | protocol version
    hbProtVer  :: !ProtVer
  }
  deriving (Generic)
 
-- | Input to the verifiable random function. Consists of the hash of the slot
-- and the epoch nonce.
newtype InputVRF = InputVRF {unInputVRF :: Hash Blake2b_256 InputVRF}
  deriving (Eq, Ord, Show, Generic)
  deriving newtype (NoThunks, ToCBOR)
 
-- | Construct a unified VRF value
mkInputVRF ::
  SlotNo ->
  -- | Epoch nonce
  Nonce ->
  InputVRF
mkInputVRF (SlotNo slot) eNonce =
  InputVRF
    . Hash.castHash
    . Hash.hashWith id
    . runByteBuilder (8 + 32)
    $ BS.word64BE slot
      <> ( case eNonce of
             NeutralNonce -> mempty
             Nonce h      -> BS.byteStringCopy (Hash.hashToBytes h)
         )
 
-- | Assert that a natural is bounded by a certain value. Throws an error when
-- this is not the case.
assertBoundedNatural ::
  -- | Maximum bound
  Natural ->
  -- | Value
  Natural ->
  BoundedNatural
assertBoundedNatural maxVal val =
  if val <= maxVal
    then UnsafeBoundedNatural maxVal val
    else error $ show val <> " is greater than max value " <> show maxVal
 
-- | The output bytes of the VRF interpreted as a big endian natural number.
--
-- The range of this number is determined by the size of the VRF output bytes.
-- It is thus in the range @0 ..  2 ^ (8 * sizeOutputVRF proxy) - 1@.
--
getOutputVRFNatural :: OutputVRF v -> Natural
getOutputVRFNatural = bytesToNatural . getOutputVRFBytes
 
-- This is fast enough to use in production.
bytesToNatural :: ByteString -> Natural
bytesToNatural = GHC.naturalFromInteger . bytesToInteger
 
bytesToInteger :: ByteString -> Integer
bytesToInteger (BS.PS fp (GHC.I# off#) (GHC.I# len#)) =
  -- This should be safe since we're simply reading from ByteString (which is
  -- immutable) and GMP allocates a new memory for the Integer, i.e., there is
  -- no mutation involved.
  unsafeDupablePerformIO $
    withForeignPtr fp $ \(GHC.Ptr addr#) ->
      let addrOff# = addr# `GHC.plusAddr#` off#
       in -- The last parmaeter (`1#`) tells the import function to use big
          -- endian encoding.
          importIntegerFromAddr addrOff# (GHC.int2Word# len#) 1#
  where
    importIntegerFromAddr :: Addr# -> Word# -> Int# -> IO Integer
#if __GLASGOW_HASKELL__ >= 900
-- Use the GHC version here because this is compiler dependent, and only indirectly lib dependent.
    importIntegerFromAddr addr sz = integerFromAddr sz addr
#else
    importIntegerFromAddr = GMP.importIntegerFromAddr
#endif
 
 
-- | Check that the certified VRF output, when used as a natural, is valid for
-- being slot leader.
checkLeaderValue ::
  forall v.
  VRF.VRFAlgorithm v =>
  VRF.OutputVRF v ->
  Rational ->
  ActiveSlotCoeff ->
  Bool
checkLeaderValue certVRF σ f =
  checkLeaderNatValue (assertBoundedNatural certNatMax (VRF.getOutputVRFNatural certVRF)) σ f
  where
    certNatMax :: Natural
    certNatMax = (2 :: Natural) ^ (8 * VRF.sizeOutputVRF certVRF)
 
-- | Check that the certified input natural is valid for being slot leader. This
-- means we check that
--
-- p < 1 - (1 - f)^σ
--
-- where p = certNat / certNatMax.
--
-- The calculation is done using the following optimization:
--
-- let q = 1 - p and c = ln(1 - f)
--
-- then           p < 1 - (1 - f)^σ
-- <=>  1 / (1 - p) < exp(-σ * c)
-- <=>  1 / q       < exp(-σ * c)
--
-- This can be efficiently be computed by `taylorExpCmp` which returns `ABOVE`
-- in case the reference value `1 / (1 - p)` is above the exponential function
-- at `-σ * c`, `BELOW` if it is below or `MaxReached` if it couldn't
-- conclusively compute this within the given iteration bounds.
--
-- Note that  1       1               1                         certNatMax
--           --- =  ----- = ---------------------------- = ----------------------
--            q     1 - p    1 - (certNat / certNatMax)    (certNatMax - certNat)
checkLeaderNatValue ::
  -- | Certified nat value
  BoundedNatural ->
  -- | Stake proportion
  Rational ->
  ActiveSlotCoeff ->
  Bool
checkLeaderNatValue bn σ f =
  if activeSlotVal f == maxBound
    then -- If the active slot coefficient is equal to one,
    -- then nearly every stake pool can produce a block every slot.
    -- In this degenerate case, where ln (1-f) is not defined,
    -- we let the VRF leader check always succeed.
    -- This is a testing convenience, the active slot coefficient should not
    -- bet set above one half otherwise.
      True
    else case taylorExpCmp 3 recip_q x of
      ABOVE _ _ -> False
      BELOW _ _ -> True
      MaxReached _ -> False
  where
    c, recip_q, x :: FixedPoint
    c = activeSlotLog f
    recip_q = fromRational (toInteger certNatMax % toInteger (certNatMax - certNat))
    x = -fromRational σ * c
    certNatMax = bvMaxValue bn
    certNat = bvValue bn
 
  -- | Evolving nonce type.
data Nonce
  = Nonce !(Hash Blake2b_256 Nonce)
  | -- | Identity element
    NeutralNonce
  deriving (Eq, Generic, Ord, Show, NFData)
 
-- | Evolve the nonce
(⭒) :: Nonce -> Nonce -> Nonce
Nonce a ⭒ Nonce b =
  Nonce . castHash $
    hashWith id (hashToBytes a <> hashToBytes b)
x ⭒ NeutralNonce = x
NeutralNonce ⭒ x = x
 
-- | Hash the given value, using a serialisation function to turn it into bytes.
--
hashWith :: forall h a. HashAlgorithm h => (a -> ByteString) -> a -> Hash h a
hashWith serialise =
    UnsafeHashRep
  . packPinnedBytes
  . digest (Proxy :: Proxy h)
  . serialise
 
instance HashAlgorithm Blake2b_224 where
  type SizeHash Blake2b_224 = 28
  hashAlgorithmName _ = "blake2b_224"
  digest _ = blake2b_libsodium 28
 
blake2b_libsodium :: Int -> B.ByteString -> B.ByteString
blake2b_libsodium size input =
  BI.unsafeCreate size $ \outptr ->
    B.useAsCStringLen input $ \(inptr, inputlen) -> do
      res <- c_crypto_generichash_blake2b (castPtr outptr) (fromIntegral size) (castPtr inptr) (fromIntegral inputlen) nullPtr 0 -- we used unkeyed hash
      unless (res == 0) $ do
        errno <- getErrno
        ioException $ errnoToIOError "digest @Blake2b: crypto_generichash_blake2b" errno Nothing Nothing
 
 

1.3.3 Epoch Structure

In Praos and Genesis, an epoch consists of 3 logical phases to compute these 2 key variables—active stake distribution and randomness beacon—by going through the following phases:

The sequential flow of these 3 phases is deliberately structured by designed :

1.3.4 Epoch & Phases Length

While there is no theoretical upper bound on the epoch size—since it is defined by social and practical considerations (e.g., $10 \, \text{k}/f$ slots, 5 days)—the epoch does have a defined lower bound. Phases 1 and 3 have fixed sizes of $3 \, \text{k}/f$ and $4 \, \text{k}/f$, respectively. The size of Phase 2, "Honest Randomness in $\eta_\text{e}$," is adjustable with a minimum size of $1 \, \text{k}/f$.

The structure of an epoch is often described by the ratio 3:3:4:

• Phase 1 occupies 3 parts of the total epoch.
• Phase 2 also occupies 3 parts of the epoch (adjusted slightly to ensure the total reaches 10 parts in total.).
• Phase 3 takes up the remaining 4 parts of the epoch.

1.3.5 The Randomness Generation Sub-Protocol

To select the slots leaders, which stake pool is eligible to produce and propose a slot's block, we need to rely on random numbers. As economic reward and transaction inclusion depends on these numbers, the generation of these number is of critical importance to the protocol and its security. We show in this section how these random numbers, or random nonces are defined.

The $\eta^\text{evolving}$ Stream Definition

The random nonces $\eta$ are defined iteratively from a genesis value, as the hash of the previous epoch's nonce and the VRF outputs published between the Phase 2 of consecutive epochs. We thus talk about evolving nonces $\eta^\text{evolving}$ as their value can be updated with the VRF output comprised in each block.

The $`\eta^\text{candidates}`$

• As multiple competing forks can exist at any given time, we also encounter multiple nonce candidates, denoted as $`\eta^\text{candidates}`$. More precisely, the nonce candidate of a specific fork for epoch $`e`$ is derived from the previous epoch’s nonce $`\eta_{e-1}`$, the Verifiable Random Function (VRF) outputs from the candidate chain starting from epoch $`e-2`$, and the VRF outputs of the fork itself up to the end of Phase 2 of epoch $`e-1`$.

• These components together form a candidate nonce for epoch $`e`$, corresponding to the last derived evolving nonce $`\eta^{\text{evolving}}_{\text{t}}`$ at the conclusion of Phase 2 of epoch $`e-1`$:

The $`\eta`$ Generations

• This is the final nonce used to determine participant eligibility during epoch $`e`$.
• The value of $`\eta_\text{e}`$ is derived from the $`\eta_e^\text{candidate}`$ contained within the fork that is ultimately selected as the canonical chain at the conclusion of $`\text{epoch}_{e-1}`$.
• It originates from $`\eta_e^\text{candidate}`$ concatenated with $`\eta^\text{evolving}`$ of the last block of the previous epoch followed by a BLAKE2b-256 hash computation , which becomes stabilized at the conclusion of $`\text{epoch}_{e-1}`$ and transitions into $`\text{epoch}_e`$.

As one of these fork will become the canonical main chain, so will the candidate nonce. Hence, the epoch nonce $\eta_e$ is the candidate nonce of the longest chain at Phase 2, which is determined once the chain stabilises.

For a detailed formalization of the consensus mechanisms discussed herein, refer to the Consensus Specifications in the Cardano Formal Specifications repository maintained by IntersectMBO.

 
  -- | Evolving nonce type.
data Nonce
  = Nonce !(Hash Blake2b_256 Nonce)
  | -- | Identity element
    NeutralNonce
  deriving (Eq, Generic, Ord, Show, NFData)
 
-- | Evolve the nonce
(⭒) :: Nonce -> Nonce -> Nonce
Nonce a ⭒ Nonce b =
  Nonce . castHash $
    hashWith id (hashToBytes a <> hashToBytes b)
x ⭒ NeutralNonce = x
NeutralNonce ⭒ x = x
 
-- | Hash the given value, using a serialisation function to turn it into bytes.
--
hashWith :: forall h a. HashAlgorithm h => (a -> ByteString) -> a -> Hash h a
hashWith serialise =
    UnsafeHashRep
  . packPinnedBytes
  . digest (Proxy :: Proxy h)
  . serialise
 
instance HashAlgorithm Blake2b_224 where
  type SizeHash Blake2b_224 = 28
  hashAlgorithmName _ = "blake2b_224"
  digest _ = blake2b_libsodium 28
 
blake2b_libsodium :: Int -> B.ByteString -> B.ByteString
blake2b_libsodium size input =
  BI.unsafeCreate size $ \outptr ->
    B.useAsCStringLen input $ \(inptr, inputlen) -> do
      res <- c_crypto_generichash_blake2b (castPtr outptr) (fromIntegral size) (castPtr inptr) (fromIntegral inputlen) nullPtr 0 -- we used unkeyed hash
      unless (res == 0) $ do
        errno <- getErrno
        ioException $ errnoToIOError "digest @Blake2b: crypto_generichash_blake2b" errno Nothing Nothing
 
 

1.4 Forks, Rollbacks, Finality, and Settlement Times

With Ouroboros Praos, as with Nakamoto consensus in general, transaction finality is probabilistic rather than immediate. This means a transaction isn't guaranteed to be permanently stored in the ledger when it's first included in a block. Instead, each additional block added on top strengthens its permanence, gradually decreasing the likelihood of a rollback.

Ouroboros Praos guarantees that after $k$ blocks have been produced, the likelihood of a rollback diminishes to the point where those blocks can be regarded as secure and permanent within the ledger. However, before these $k$ blocks are finalized, multiple versions of the blockchain—commonly referred to as "forks"—may coexist across the network. Each fork represents a potential ledger state until finality is ultimately achieved.

The consensus layer operates with a structure that resembles a branching "tree" of blockchains before finality stabilizes:

Why Do Blockchain Forks Occur?

Blockchain forks can happen for several reasons:

• Multiple slot leaders can be elected for a single slot, potentially resulting in the production of multiple blocks within that slot.
• Block propagation across the network takes time, causing nodes to have differing views of the current chain.
• Nodes can dynamically join or leave the network, which is a fundamental challenge in decentralized systems, affecting synchronization and consensus stability.
• An adversarial node is not obligated to agree with the most recent block (or series of blocks); it can instead choose to append its block to an earlier block in the chain.

Short Forks vs. Long Forks

Short forks, typically just a few blocks long, occur frequently and are usually non-problematic. The rolled-back blocks are often nearly identical, containing the same transactions, though they might be distributed differently among the blocks or have minor differences.

However, longer forks can have harmful consequences. For example, if an end-user (the recipient of funds) makes a decision—such as accepting payment and delivering goods to another user (the sender of the transaction)—based on a transaction that is later rolled back and does not reappear because it was invalid (e.g., due to double-spending a UTxO), it creates a risk of fraud.

2. The Grinding Attack Algorithm

This section describes the grinding attack, detailing its objectives, mechanics, and the adversary’s strategy to maximize its effectiveness.

2.1 Randomness Manipulation

We describe here the grinding attack Cardano's randomness generation protocol suffers from, from passively waiting for its chance or actively maximizing its attack surface, to choosing the best attack vector - stake distribution - to achieve its goal, be it maximizing rewards to controlling target blocks.

2.1.1 Exposure

In its current version, Praos has a vulnerability where an adversary can manipulate the nonce $\eta_\text{e}$, the random value used for selecting block producers. This allows the adversary to incrementally and iteratively undermine the uniform distribution of slot leaders, threatening the fairness and unpredictability of the leader selection process.

At the conclusion of Phase 2, when the $\eta^\text{candidate}_{e}$ nonce is determined, the distribution of slot leaders for the next epoch becomes deterministic in a private manner. This means that, at this point, the adversary gains precise knowledge of the slots in which they will be elected but lacks detailed knowledge of the slot distribution for honest participants.

For example, if the adversary acts as the slot leader immediately before this phase transition, they can choose whether to produce a block or not. This decision grants them the ability to compute and compare two valid nonces - one with one fewer VRF update than the other -, evaluate different slot leader distributions for the upcoming epoch and potentially maximize their future gains at the cost of lesser rewards at this epoch. The more blocks the adversary controls before Phase 2's end, the more nonces they may grind and choose from, and the more critical the attack becomes. In essence, the adversary gains access to up to $2^x$ possible combinations of slot leader distributions, where $x$ denotes the number of controlled leader slots at this particular stage of the protocol.

This marks the beginning of a grinding attack, where the adversary's initial goal is to maximize the number of adversarial blocks at this critical juncture, either passively by waiting, or actively by reaching a snowball effect. By doing so, they expand the range of potential slot leader distributions they can choose from, significantly enhancing their influence over the protocol. We use the term "exposure" here because the adversary is first setting the stage for its attack.

2.1.2 Slot Leader Distribution Selection

This is the pivotal moment where the adversary's prior efforts pay off. They are now in a position with x blocks at the critical juncture. At this stage, the adversary can generate up to $2^x$ possible $η$ nonces, compute the next epoch's slot leader distribution for each of them, and strategically select the nonce and distribution that best aligns with their goal. This positioning enables them to deploy the attack effectively in the subsequent epoch.

As the adversary accumulates blocks, the attack's bottleneck swiftly shifts from waiting for enough blocks at the critical juncture to the computational power needed to compute enough nonces to achieve their goal.

Accumulating a significant number of leader slots at this position necessitates, except when owning a significant portion of the total stake, an underlying intent to exploit or destabilize the protocol. Achieving such a level of control requires significant coordination, making it highly unlikely to occur without deliberate adversarial motives. Once an attacker reaches this threshold, their objectives extend beyond a single exploit and diversify into various strategic threats.

2.1.3 Potential Outcomes of Grinding Attacks

Below is a non-exhaustive list of potential attack vectors, ranging from minor disruptions in system throughput to severe breaches that compromise the protocol’s integrity and structure.

Economic Exploitation

Manipulating slot leader distributions to prioritize transactions that benefit the adversary or to extract higher fees.

Censorship Attacks

Selectively excluding transactions from specific stakeholders to suppress competition or dissent.

Minority Stake Exploitation

Amplifying the influence of a small adversarial stake by targeting specific epoch transitions.

Fork Manipulation

Creating and maintaining malicious forks to destabilize consensus or execute double-spend attacks.

Settlement Delays

Strategically delaying block confirmation to undermine trust in the protocol's settlement guarantees.

Double-Spend Attacks

Exploiting control over slot leader distributions to reverse confirmed transactions and execute double-spends.

Chain-Freezing Attacks

Using nonce selection to stall block production entirely, halting the protocol and causing network paralysis.

2.2. Non-Exhaustive Manipulation Stategy List

The Ethereum community recently published an insightful paper titled Forking the RANDAO: Manipulating Ethereum's Distributed Randomness Beacon. Since the system model used to analyze randomness manipulation in Ethereum is also applicable to Cardano, we will extensively reference their work to explore various manipulation strategies within the Cardano ecosystem.

2.2.1 System Model

A block can exist in one of four states:

• H / Proposed – The validator successfully proposes a valid block, which is accepted by the supermajority of validators and included in the canonical chain. Honest validators always follow this behavior in our analysis, while adversarial validators may consider alternative strategies, such as withholding blocks.

• R / Reorged – The validator proposes a valid block, but it ends up on a non-canonical branch of the blockchain. This block is no longer considered part of the main chain by the supermajority of the stake.

• M / Missed – The validator fails to publish a block during its designated slot. For an honest validator, this typically results from connectivity issues or other operational failures.

• P / Private – The validator constructs a block but does not immediately publish it during its assigned slot. Instead, an adversarial validator selectively shares the block with validators within its staking pool. Later, the private block may be introduced into the canonical chain by forking the next block—a strategy known as an ex-ante reorg attack. Alternatively, depending on the evolving chain state, the attacker may decide to withhold the block entirely, a tactic we refer to as regret.

Block statuses are denoted as $H^e_i, R^e_i, M^e_i, P^e_i$ indicating that the block in the $i$ th slot in epoch $e$ was proposed, reorged, missed, or built privately, respectively. Reorged and missed blocks do not contribute to the generation of $\eta_e$ since they are not part of the canonical chain.

2.2.2 Self Mixing Strategy

The adversary can selectively propose or miss blocks to manipulate $\eta_e$. Assume that $\mathcal{A}$ is assigned with $t$ consecutive tail blocks, formally $\mathcal{A}^{t}$ of epoch $e$, then $\mathcal{A}$ can choose arbitrarily between $2^t$ $\eta_e$ by missing or proposing each tail block. Thus, it is trivial that $\mathcal{A}^{t} \in AS_{\alpha}(m,n)$ for $0 \leq t \leq m$, as $\mathcal{A}$ can compute $\eta_e$ corresponding to $C^t$.

The manipulative power for $t = 2$ is the following decision tree

e.g : The adversary chooses option $\{H^e_{30}, M^e_{31}\}$ if the calculated $\eta_e$ eventually leads to the highest number of blocks. In this case, sacrificing Slot 30 and 31 is worthwhile, as it results in a significantly higher number of blocks in epoch $e + 2$.

2.2.3 Forking Strategies

To achieve the goal of maximizing $x$ trailing blocks at this critical juncture, the adversary leverages the forking nature of the consensus protocol by introducing a private chain. By strategically applying the Longest-Chain rule to their advantage, the adversary ensures that the last honest trailing blocks are excluded at this pivotal moment. With this added dimension, gaining access to $2^x$ possible combinations of slot leader distributions becomes equivalent to $x = |A| - |H|$, where $|A|$ and $|H|$ represent the number of adversarial and honest blocks, respectively, within this specific interval of the protocol :

The adversary can choose between two forking strategies depending on when they act:

• Preemptive Forking (Ex-Ante Reorging): The adversary forks before the randomness update, ensuring that only adversarial VRF contributions are included while honest ones are discarded. This allows them to manipulate $\eta_e$ before it is finalized, biasing leader selection for the next epoch.

• Reactive Forking (Ex-Post Reorging): Instead of acting in advance, the adversary waits until all honest VRF contributions are revealed before deciding whether to fork. If the observed $\eta_e$ is unfavorable, they publish an alternative chain, replacing the honest blocks and modifying the randomness post-facto.

Both strategies undermine fairness in leader election, with Preemptive Forking favoring proactive randomness manipulation and Reactive Forking enabling selective, informed chain reorganizations.

3. The Cost of Grinding: Adversarial Effort and Feasibility

3.1 Definitions

3.1.1 $\alpha$-Heavy and Heaviness

We define the heaviness of an interval as the percentage of blocks an adversary controls. Let $X_A(w)$ be the number of adversarial blocks and similarly $X_H(w)$ the number of honest blocks in the an interval of $w$ blocks. The heaviness of an interval of size $w$ is thus the ratio $\frac{X_A(w)}{w}$. Heaviness thus vary between 0, where the interval only comprises honest blocks, and 1 where the adversary control them all.

We say that the interval is $\mathbf{\alpha}$-heavy if $\frac{X_A(w)}{w} > \alpha$. We furthermore say that the adversary dominates the interval if $\alpha > 0.5$. We shall look from now on to the longest suffix the adversary dominates at the critical juncture, hence the longest interval $w_\text{max}$ where $\alpha > 0.5$.

3.1.2 Grinding Power g

An $\alpha$-heavy suffix must be present at the critical juncture for a grinding attack to be considered. The heavier $w$ , for a fixed $w$, the greater the adversary’s grinding power.

The grinding power $g$ of an adversary $A$ is the number of distinct values that $A$ can choose from when determining for the epoch nonce $\eta$. This quantifies the adversary's ability to manipulate randomness by selectively withholding, recomputing, or biasing values.

Let $g_w(X_A)$ be the number of possible grinding attempts in an interval of size $w$ when controlling $X_A$ blocks. We have,

The grinding power for a given interval of size $w$ is the sum of $g_w(X)(X_A)$ when the adversary controls a majority of the blocks.

Similarly, we define the grinding depth, $\rho$, as the logarithm of the grinding power: $\rho = \log_2 g$, and bound it by $0 \leq \rho \leq 256$. It determines the entropy reduction caused by an adversary's nonce manipulation, directly impacting the protocol's resistance to randomness biasing, that is the number of bits of randomness an adversary can manipulate.

In a simplified model where the multi-slot leader feature is not considered, the probability an adversary with $\text{stake}_A \in (0,1)$ stake controls $X_A$ out of $w$ blocks is:

where:

• $\binom{x}{y}$ represents the number of ways to select $x$ blocks out of $y$.
• $\text{stake}_A$ is the percentage of stake controlled by the adversary.

We can now define the expected grinding power $\mathbb{E}(g)$:

In Cardano mainnet, the nonce size used in the randomness beacon is 256 bits, meaning the theoretical maximum grinding power is $g_{\max} = 2^{256}$. However, practical grinding power is typically limited by computational constraints and stake distribution dynamics.

3.1.3 Grinding Windows

3.1.3.1 Opportunity Windows $w_O$

The grinding opportunity window $w_O$ is the time interval at the end of Phase 2 during which an adversary, dominating a suffix of size $w$, can compute and reveal one of $g$ possible $\eta_e^\text{candidate}$ nonces before the honest chain outpaces their chosen chain.

Phase 2 spans $S_2 = \frac{6k}{f}$ slots (with $f = \frac{1}{20}$, $k = 2,160$, $S_2 = 259,200$), ending at slot $S_2$, where $\eta_e^\text{candidate}$ is sampled from $\eta^\text{evolving}$ based on the VRF outputs of blocks up to that point (see Section 1.3.5).

Assuming the adversary controls the $X_A(w)$ slots (between slot numbered $S_2 - w + 1$ and $S_2$), they can manipulate $X_A(w)$ VRF outputs to generate up to $2^{X_A(w)}$ possible nonces by selectively revealing or withholding each output. After $S_2$, a chain with their chosen nonce —ranging in length from $X_H(w)$ (revealing no blocks, withholding all) to $w$ (revealing all)— is set.

For simplicity, we consider that a honest block is produced at slot $S_2 + 1$. As such, the grinding oppotunity window is bounded by,

N.B. Contrary to the grinding power that is upper-bounded by $2^{256}$, the grinding window is not.

• Parameters:
  • $f$: Active slot coefficient (e.g., $\frac{1}{20}$), the fraction of slots with a leader.
  • Slot duration = 1 second.

✏️ Note: The code to generate this graph is available at ➡️ this link.

Let's consider the worst case where the adversary controls all trailing slots ($g = 1 \Leftrightarrow w=X_A(w)$):

• $w = 16$:
  • $w_O = \frac{16}{\frac{1}{20}} = 16 \cdot 20 = 320$ seconds (~5.3 minutes).
  • Starts at $S_2 - w + 1 = 259,200 - 16 + 1 = 259,185$, ends at $S_2 + \frac{1}{f} = 259,200 + 20 = 259,220$ (adjusted for reveal timing).
• $w = 32$:
  • $w_O = \frac{32}{\frac{1}{20}} = 32 \cdot 20 = 640$ seconds (~10.7 minutes).
  • Starts at $S_2 - w + 1 = 259,200 - 32 + 1 = 259,169$, ends at $259,200 + 20 = 259,220$.
• $w = 256$:
  • $w_O = \frac{256}{\frac{1}{20}} = 256 \cdot 20 = 5,120$ seconds (~85.3 minutes).
  • Starts at $S_2 - w + 1 = 259,200 - 256 + 1 = 258,945$, ends at $259,200 + 20 = 259,220$.

This sizing ensures the adversary has time to act before honest chain growth threatens even a length-1 chain, providing a practical and conservative bound for grinding feasibility.

3.1.3.2 Target Window $w_T$

Once the adversary obtains a potential candidate nonce ($\eta_e^{\text{candidate}}$) for epoch $e$, they can compute their private slot leader distribution for the entire epoch, spanning:

We define the grinding target window $w_T$ as the slot interval an adversary targets based on their attack strategy, where $1 \leq w_T \leq 4.32 \cdot 10^5 \text{ slots}$.

3.1.3 Grinding Attempt

A grinding attempt is a single evaluation of a possible $\eta$ nonce by the adversary within the grinding target window $w_O$.
Each attempt follows three key steps:

1. Computing a candidate $\eta$ nonce by selectively revealing or withholding VRF outputs.
2. Simulating the resulting slot leader distribution over the target window $w_T$.
3. Evaluating the strategic benefit of choosing this $\eta$ nonce for their attack objectives.

The number of grinding attempts an adversary can make is constrained by their grinding power $g$, and is upper-bounded by:

where the adversary dominates the suffix of size $w$ at the critical juncture and $X_A(w)$ represents the number of blocks they control in that interval.

3.2 Entry Ticket: Acquiring Stake to Play the Lottery

Before an adversary can execute a grinding attack, they must first acquire enough stake, akin to buying an entry ticket to participate in a lottery.
In this case, the lottery is the leader election process, where the probability of winning a slot—and thus influencing the $\eta$ nonce—is directly proportional to the stake held.

Just like in a lottery, the more tickets an adversary buys (stake accumulated), the greater their chances of winning.
By securing a significant share of stake, they increase the likelihood of being selected as a slot leader in key trailing positions, providing the foundation needed to execute a grinding attack.

Thus, the first cost of a grinding attack is not computational but economic —the price of acquiring enough stake to play the lottery.

To estimate the cost of these entry tickets, we address the following question:

How many blocks can an adversary control on average with a given adversarial stake, ensuring a reasonable probability—such as at least one successful grinding opportunity within 10 years of continuous epoch-by-epoch execution in Cardano, where each epoch lasts 5 days?

Specifically, for a given adversarial stake, we seek the maximum $X_A(w)$ for which the probability of obtaining a dominating $\alpha$-heavy suffix $w_O$ is at least once over 10 years, meaning at least one occurrence within 3,650 epochs.

N.B.: A 10-year period spans two full technological innovation cycles, significantly increasing the likelihood of disruptive advancements in cryptographic research, computing power, or consensus protocols. This timeframe provides a long enough horizon for:

• Assessing long-term adversarial feasibility and whether stake-based grinding remains viable at scale.
• Observing historical adversarial behaviors, particularly in decentralized networks with shifting governance dynamics.
• Giving the Cardano community sufficient time to introduce fundamental protocol-level improvements to Ouroboros that could completely mitigate or transform this issue.

The Data

We are computing here the expected number of grinding attempts for both the self-mixing and forking strategies.

Self-Mixing

We present here the average number of years required for an adversary with a stake of $\text{stake}_A$ to control N blocks. We chose to emphasize frequencies below 10 years, as it is reasonable to assume the protocol will have evolved after such a period.

(*) We make the simplification to consider the 21,600 blocks directly, that is: there is only 21,600 slots and to each to slot is exactly assigned one slot leader.

We present the expected number (i.e., moment) of grinding attempts during self-mixing, which refers to trailing blocks within an epoch.

We conclude that the self-mixing attack is neither highly probable nor particularly critical.

Forking

We extend here the self-mixing strategy with forking and show how this renders the attack viable.

We first introduce the formula for the probability for an adversary having $\text{stake}_A$ stake of having an advantage of $|X_A - X_H| = N$ blocks, that is an adversary controlling a majority of $N$ blocks, in any given interval smaller than $s$ blocks where $s$ is from the $s$-CQ property.

As the formula is not computationally friendly, instead of showing numbers for an interval of size $s$, we look at a smaller interval of size $precision$, to give us a lower-bound on these numbers. We now display a lower bound on the probabilities of having an advantage of $|X_A - X_H| = N$ blocks, and an upper-bound on the frequency of a corresponding grinding attack per year.

We now tabulatethe grinding power's expectation when looking at different precision $s$. While the expectation converges quickly for small stake, smaller than 20%, we can note it significicantly rises afterwards.

We can approximate the expected grinding power as an exponential function of the precision, i.e. $E(g, n)= \text{poly}(n) \cdot \zeta^n$. Looking at the exponential's based, $\zeta$ can tell us precisely when the grinding power becomes rises exponentially, that is when $\zeta = 1$ the exponentiaition starts growing instead of decaying. The following graph indeed confirms that 20% is the threshold.

The details of the calculations underlying this table can be found in the following Google Spreadsheet: Details of Calculations.

For example, with 5% adversarial stake, it would take about 1800 years in average for an adversary to obtain an advantage of of exactly 4 blocks at the critical juncture.

The Results

N.B : This analysis does not account for recursion in addition to the forking and self-mixing strategy, so the curve should actually be even steeper than in the graph above.

This investment is non-trivial and serves as an implicit deterrent to attacks, as the adversary must weigh the risks of financial exposure against potential gains. While stake acquisition might appear as a sunk cost, it can, in some cases, be viewed as an active investment in the blockchain ecosystem. For instance, an adversary with a large stake may not only attempt manipulation but could also seek to benefit from staking rewards, governance influence, or other economic incentives, adding an additional layer of strategic decision-making.

Results suggests that crossing the 20% stake threshold dramatically increases an adversary’s probability of influencing leader elections. With such control, their ability to manipulate leader election outcomes becomes exponentially and primarily constrained by computational feasibility rather than probabilistic limitations.

As of March 1, 2025, acquiring a 20% stake in Cardano would require an investment exceeding 4.36 billion ADA, a substantial sum that introduces a fundamental game-theoretic disincentive:

• A successful attack could undermine the blockchain’s integrity, leading to loss of trust and stake devaluation.
• If the attack is detected, reputational damage, delegator withdrawals, or protocol-level countermeasures could make the adversary's stake significantly less valuable.

This reinforces transparency as a natural deterrent: publicly observable grinding attempts expose adversarial stake pool operators (SPOs) to severe economic and social consequences.

3.3 Cost of a Grinding Attempt

As previously explained, each attempt consists of three key steps:

1. Computing a candidate $\eta$ nonce by selectively revealing or withholding VRF outputs.
2. Simulating the resulting slot leader distribution over the target window $w_T$.
3. Evaluating the strategic benefit of choosing this $\eta$ nonce for adversarial objectives.

Let's analyze each of these steps.

3.3.1 Nonce Generation

We will denote this step as $T_{\text{nonce}}^\rho$ moving forward.

Nonce generation consists of:

1. VRF Evaluation: Computes a candidate $\eta$ nonce.
2. $\ast$ Operation: Concatenation + BLAKE2b-256 hashing.

Since the VRF outputs can be precomputed, we can discard them from the computational cost of a grinding attack. As for the computational cost, as the hash functions are protected against extension attacks, we have to consider the average cost of hashing of all nonces when considering a fixed grinding depth $\rho$.

We make the assumption that hashing $n$ inputs takes as much time as hashing $n$ times two inputs, that is that the finalization step of a hashing function is not significant. We also look at the worst case scenario, for simplification, and assume that $g = 2^{X_A(w)}$.

N.B. We may drop the superscript $\rho$ for readibility.

N.B. This represents the average time to compute a nonce. While each nonce can be computed in parallel, we cannot easily parallelize the generation of one nonce as the computation is sequential.

3.3.2 Slot Leader Distribution Evaluation

We will denote this step as $T_{\text{distribution}}$ moving forward.

After generating a candidate nonce, the adversary must evaluate its impact on slot leader election over an target window $w_T$ :

1. Computing VRF outputs for all slots in $w_T$ of interest.
2. Evaluating the eligibilty of these values to know when the adversary is the slot leader.

Since leader eligibility is unknown in advance, the adversary must verify all slots in $w_T$.

Define:

• $w_T$ → target window size (seconds).
• $T_{\mathsf{VRF}}$ → VRF evaluation time.
• $T_{\text{eligibility}}$ → Slot eligilibity check.

Each slot requires one VRF verification, leading to:

This represents the total time of the leader distribution evaluation. Once a nonce is computed, we can generate and check the eligibility of the VRF outputs in parallel.

3.3.3 Strategic Benefit Evaluation

We denote this step as $T_{\text{eval}}$ moving forward.

After simulating the leader election distribution, the adversary must determine whether the selected $\eta$ nonce provides a strategic advantage by:

1. Assessing block production gains relative to honest stake.
2. Estimating adversarial control over leader election.
3. Comparing multiple nonces to select the most effective one.

Nature of the Computational Workload

Unlike previous steps, this phase does not perform a single deterministic computation but operates as an evaluation loop over a dataset of adversarial leader election scenarios. The attacker’s dataset includes:

• Nonce-to-leader mappings → which nonces yield better leadership control.
• Stake distributions → impact of adversarial stake on slot control.
• Slot timing predictions → evaluating when it's best to control a block.
• Secondary constraints → network conditions, latency factors, or additional attack-specific considerations.

Since this "database" of possible leader elections depends on adversarial strategies, the cost is too diverse to define precisely. While the exact cost varies, this step is compulsory and must be factored into the total grinding time.

3.3.4 Total Estimated Time per Grinding Attempt

The total grinding time is the sum of:

1. Nonce Generation ($T_{\text{nonce}}$) → VRF evaluation + hashing.
2. Slot Leader Simulation ($T_{\text{distribution}}$) → Eligibility checks over $w_T$.
3. Strategic Evaluation ($T_{\text{eval}}$) → Nonce selection analysis.

Total Grinding Time Formula

Expanding each term:

• Nonce Generation: : $T_{\text{nonce}} = \frac{\rho}{2} \cdot T_{\text{BLAKE2b}}$
• Slot Leader Verification : $T_{\text{verify}} = w_T \cdot ( T_{\mathsf{VRF}} + T_{\text{eligibility}} )$
• Strategic Evaluation : $T_{\text{eval}}$ (attack-dependent term)

Final expression:

Where:

• $T_{\mathsf{VRF}}$ is the VRF evaluation time.
• $T_{\text{eligibility}}$ is the eligibility checktime.
• $T_{\text{BLAKE2b}}$ is the time for the hashing operation.
• $w_T$ is the target window size (seconds).
• $\rho$ is the grinding power.
• $T_{\text{eval}}$ is the nonce selection and evaluation time, which is attack-specific.

3.4 Cost of a Grinding Attack

3.4.1 Formula

A grinding attack consists of multiple grinding attempts executed within the grinding opportunity window $w_O$. Since each grinding attempt takes time to compute, the feasibility of the attack depends on whether the total computation can be completed within this window.

We define the total attack time as:

where:

• $\rho$ = grinding depth (bits of entropy the adversary can manipulate),
• $T_{\text{grinding}}$ = time required for one grinding attempt,
• $N_{\text{CPU}}$ = number of CPUs available for parallel execution.

For the attack to be feasible, this total time must fit within the grinding opportunity window $w_O$:

which leads to the lower bound on computational power ($N_CPU$) :

Expanding $T_{\text{grinding}}$

From Section 3.3, the per-attempt grinding time is:

Substituting this into the inequality:

Expanding $w_O$ in Terms of $\rho$ and $f$

From previous sections, the grinding opportunity window is:

Substituting this into our equation:

We end up with this final expression :

3.4.2 Estimated Formula Using Mainnet Cardano Parameters

Starting from the final expression at the end of the last section:

Applying Cardano Mainnet Parameters

Using Cardano’s mainnet values:

• $T_{\mathsf{VRF}} = 10^{-6}$ seconds (1 microsecond) – Time to evaluate a Verifiable Random Function.
• $T_{\text{BLAKE2b}} = 10^{-8}$ seconds (0.01 microseconds) – Time for a BLAKE2b-256 hash operation.
• $f = \frac{1}{20} = 0.05$ – Active slot coefficient.
• Slot duration = 1 second.

Since the eligibility check is negligible, set $T_{\text{eligibility}} \approx 0$:

Substitute into the expression:

• First term: $f \cdot 2^{\rho-1} \cdot T_{\text{BLAKE2b}} = 0.05 \cdot 2^{\rho-1} \cdot 10^{-8} = 5 \cdot 10^{-10} \cdot 2^{\rho-1}$,
• Second term: $\frac{f}{\rho} \cdot 2^{\rho-1} \cdot \left( w_T \cdot ( T_{\mathsf{VRF}} + T_{\text{eligibility}} ) + T_{\text{eval}} \right) = \frac{0.05}{\rho} \cdot 2^{\rho-1} \cdot \left( w_T \cdot (10^{-6} + 0) + T_{\text{eval}} \right) = \frac{0.05 \cdot 2^{\rho-1}}{\rho} \cdot (10^{-6} w_T + T_{\text{eval}})$.

Thus, the expression becomes: