Markov, Not Memoryless

The blockchain economics literature has confused two mathematical properties for a decade. The consequences are not trivial.

There is a word that does a great deal of unearned work in blockchain economics, and that word is “memoryless.” It appears in security analyses, game-theoretic treatments, equilibrium models, and attack-cost frameworks. It is applied to proof-of-work mining with the confidence of a settled fact. And it rests on a conflation so elementary that pointing it out feels almost impolite — like correcting someone’s Latin at a dinner party. But the correction matters, because theoretical conclusions have been built on the conflation, and those conclusions are wrong in ways that can be precisely quantified.

The conflation is between two mathematical properties: the memoryless property of the exponential distribution and the Markov property of a stochastic process. These are not the same thing. They are not approximately the same thing. They impose opposite restrictions on what a system is permitted to remember. One forbids history. The other permits arbitrarily rich history, provided it is encoded in the current state. The blockchain economics literature has treated them as interchangeable, and the result is a body of work that systematically underestimates the deterrence that proof-of-work protocols actually provide. The correction is not a matter of taste or emphasis. It is a matter of mathematical fact — and the quantitative consequences run to tens of millions of dollars for the largest mining operations.

The Distinction That Was Not Made

Let us be precise, since the entire argument turns on definitions that the literature has blurred.

A non-negative random variable is memoryless if the probability of waiting another t units, given that you have already waited s units, equals the probability of waiting t units from a fresh start. Among continuous distributions, only the exponential has this property. Among discrete distributions, only the geometric. This is a characterisation theorem — it admits no exceptions.

A stochastic process is Markov if the future evolution depends on the past only through the current state. The state may be trivial — a single number, carrying no information — or it may be an enormously rich object encoding the complete history of a complex system. The Markov property requires only that whatever the state contains is a sufficient statistic for the future. It says nothing about how much that state is permitted to remember.

A memoryless random variable defines a trivially Markov process: the remaining lifetime at any moment has the same distribution regardless of what has happened, so the “state” carries no information at all. A Markov process with a rich state is the opposite: the state may encode arbitrarily complex history, and future dynamics depend on that history through the state variable. The memoryless property is a special case of the Markov property — the degenerate case in which the state is empty. Confusing the general case with the degenerate case is, to put it charitably, an error.

In the specific context of proof-of-work mining, the distinction maps cleanly onto two levels of the protocol. At the local arrival level, the time for a miner to solve a block is exponentially distributed. This waiting time is memoryless: the distribution of the remaining time is independent of how long the miner has been working. This is true, useful, and not disputed by anyone.

At the game level — the level at which miners choose strategies, accumulate block rewards, decide whether to fork, and compete for canonical-chain status — the state is an entirely different object. It includes the full block tree, the identity of who mined each block, the allocation of miners across branches, accumulated vested interests, unmatured coinbase rewards, and the current difficulty parameter. This state is Markov (strategies depend on it, and it is a sufficient statistic for the future), but it is emphatically not memoryless. It encodes extensive history. That history determines equilibrium behaviour.

How the Conflation Entered the Literature

The persistence of the error is understandable, even if it is not forgivable. The word “Markov” appears in both “Markov perfect equilibrium” and “Markov chain,” and in the special case of a homogeneous Poisson process — which is both Markov and memoryless — the two properties coincide. When the exponential distribution is the first mathematical object encountered in a blockchain model, as it typically is (since inter-block arrivals are the natural starting point for any analysis), it is natural to carry the memoryless characterisation forward. The problem arises at the next step: when the game-level state is constructed on top of the arrival process, the memoryless property of the arrivals does not transfer to the state. The state inherits the Markov property — it is a sufficient statistic — but not the memoryless property — it encodes history. This is a standard result in the theory of stochastic processes. It has simply not been made explicit in blockchain economics.

The landmark game-theoretic treatment of proof-of-work equilibria is an instructive case. That work correctly identifies the inter-block waiting time as exponential (memoryless) and then constructs a stochastic game whose state encodes the full block tree, miner allocations, and a public coordination device. The game’s equilibrium is Markov perfect — strategies depend on the current state. But the state is a rich, history-encoding object. The authors prove that miners accumulate “vested interests” on their chain: the number of blocks a miner has solved on a given branch since the fork point determines whether deviation is profitable. This vested-interest count is a running tally of past play — it is history, encoded in the state, conditioning future strategy.

There is no ambiguity in this result. A game in which equilibrium behaviour depends on how many blocks each miner has accumulated on each branch is a game with memory. The memory is mediated through the state variable, which is precisely what the Markov property allows and the memoryless property forbids. The authors of that work understood this perfectly. The downstream literature did not.

What the State Actually Contains

Consider a concrete instance. Five miners. A fork at block ten. By the current time, the block tree contains two branches: an original chain with two post-fork blocks mined by miners one and two, and a fork with three blocks mined by miners three, four, and five. The state records all of this: the tree structure, the identity labels on each block, the allocation of miners across branches.

From this state, every payoff-relevant quantity can be read off. Miner one’s vested interest on the original chain is one block. Miner three’s vested interest on the fork is one block. These quantities determine whether miners find it profitable to stay on their current branch or switch. A miner with fifty blocks of vested interest on a chain faces a categorically different incentive landscape than a miner with zero blocks — even if the two miners are otherwise identical in hash rate, current rewards, and branch allocation.

A memoryless characterisation of this game would require that the continuation value be independent of how the current state was reached — that a miner with fifty vested blocks and a miner with zero vested blocks face the same incentives, simply because they might share the same current block height. That is precisely what the equilibrium analysis shows to be false. The accumulated vested interests determine behaviour. The game has memory.

Three Mechanisms the One-Shot Model Cannot See

The vested-interest mechanism already suffices to establish the point. But the actual Bitcoin protocol contains three additional features that enlarge the payoff-relevant state in ways that make the history dependence even more pronounced.

Coinbase maturity. Bitcoin’s consensus rules prohibit spending coinbase outputs — block rewards — until one hundred additional blocks have been built on top of the containing block. This makes the number of unmatured coinbase rewards on each chain a hard component of the protocol state, not merely a strategic effect. A miner who switches chains does not merely suffer marginal depreciation on past blocks; any unmatured rewards on the abandoned chain face total loss if that chain stalls. The additional per-block cost borne by unmatured blocks exceeds the marginal value-loss in the base game model. For a miner controlling 20% of the network hash rate, the stock of unmatured rewards at any given time is roughly twenty blocks — approximately 62.5 BTC at the current subsidy. This is locked capital that is destroyed if the miner initiates a fork that orphans the main chain. The one-shot framework does not account for it because the one-shot framework has no state variable to encode it.

Difficulty adjustment. Every 2,016 blocks, Bitcoin recalculates difficulty based on the elapsed wall-clock time over the preceding epoch. This makes the transition probabilities of the game — how fast blocks are solved, and therefore how quickly vested interests accumulate — functions of within-epoch history. After a fork, the two competing branches evolve independently. A minority chain that produces blocks slowly will have its difficulty reduced, accelerating production. A majority chain that produces blocks quickly will have its difficulty increased. The dynamics of fork resolution are therefore path-dependent: they depend on the entire history of block production since the fork, not merely on the current allocation of miners. This is a form of history dependence that operates through the transition law itself, not merely through the payoff function.

Fee accumulation. The value of the next block grows with elapsed time since the last block, as transaction fees accumulate in the mempool. The economic prize is not constant; it is a function of the current inter-block interval. A miner deciding whether to continue on a chain or switch must consider not only vested interests and maturity constraints but also the time-varying value of the block currently being competed for. This is yet another dimension of history dependence that the memoryless characterisation erases.

Each mechanism adds components to the state without altering the game structure. They are not exotic additions; they are constitutive features of the protocol as deployed. A model that omits them is not describing Bitcoin with simplifying assumptions. It is describing a different system.

The Quantitative Consequences

The most influential economic treatment of Bitcoin’s security models the mining game as effectively one-shot: no accumulated state, no vested interests, no maturity constraints. The conclusion is that the cost of attack is a “flow” — the recurring cost of honest mining for a short period. This is presented not as a simplifying assumption but as a characterisation of the protocol’s economic structure.

Once the richer state is admitted, the characterisation changes in a quantifiable direction. The corrected attack-cost inequality includes, alongside the flow cost, three additional terms: vested-interest deterrence (proportional to the number of blocks the potential attacker has mined on the main chain), maturity deterrence (proportional to unmatured coinbase rewards at risk of total loss), and difficulty-feedback cost (the expected impact of the difficulty adjustment working against a sustained attacker). All three are zero in a one-shot model. All three are positive in the actual protocol.

The magnitudes are not negligible. For a mining pool controlling 30% of the network hash rate — roughly the scale of the largest current pool — the maturity deterrence alone is approximately $3.6 million, the vested-interest deterrence after one difficulty epoch is approximately $11.7 million, and the combined stock-like deterrence adds roughly 12% to the epoch-level flow cost. These are terms that the one-shot framework sets to zero.

More importantly, the stock-like deterrence grows linearly with time on the chain, while the flow cost of an attack is fixed by the attack duration. There exists a computable threshold — approximately 63 blocks, or about ten and a half hours — beyond which the accumulated stock-like deterrence exceeds the flow cost of a standard six-confirmation attack. Since every major mining pool operates continuously and has been on the main chain for months or years, not hours, the stock-like deterrence is not a small correction to the flow-cost framework. It is the dominant deterrence term for every established miner.

This is not a rounding error. For a miner who has been active for one difficulty epoch — approximately two weeks — the stock-like deterrence exceeds the flow cost of a six-confirmation attack by a factor of roughly thirty-two. The one-shot model does not merely understate deterrence; it omits the term that dominates the incentive constraint for any miner with a non-trivial history.

The Representation Impossibility

A natural objection is that the one-shot model is a deliberate simplification — that it captures the essential economics while abstracting from state variables that are quantitatively secondary. This objection can be tested formally, and it fails.

Consider two states that are identical in every flow variable: the same number of miners, the same hash rates, the same difficulty, the same block reward, the same allocation of miners across branches. They differ in one respect only: in one state, a miner on the minority chain has accumulated fifty blocks of vested interest; in the other, that miner has accumulated zero. In the stochastic game, the equilibrium prescribes different actions in these two states — the fork persists in one (vested interests are large enough to deter deviation) and collapses in the other (no vested interests, so the miner switches to the majority chain). Any one-shot game whose payoffs depend only on flow variables must prescribe the same action in both states, because it cannot distinguish them. The one-shot framework is not merely an approximation. It involves a structural loss: it cannot reproduce the equilibrium strategies of the actual game.

Two mining environments that look identical to a flow-cost model — same miners, same hash rates, same rewards, same branch structure — produce different equilibrium behaviour in the stochastic game, because one has accumulated vested interests and the other does not. This is the sense in which the one-shot representation is inadequate, not merely imprecise.

The Extension to Proof of Stake

The logic extends naturally to proof-of-stake protocols, with an irony that is almost too neat. The stock-like deterrence mechanisms that proof-of-work generates as a byproduct of mining investment — vested interests, maturity constraints, difficulty feedback — are precisely the features that proof-of-stake protocols try to create by explicit design.

Locked stake serves the structural role of accumulated vested interests. Validators lock tokens as collateral; the locked amount depends on history and is chain-specific. An unbonding period — typically days to weeks — plays the role of the coinbase maturity rule, making locked capital illiquid and placing it at risk during a window in which the validator cannot respond to chain events. Slashing — the destruction of a fraction of a validator’s locked stake for signing conflicting attestations — is an explicitly history-dependent punishment that has no direct analogue in the base proof-of-work protocol.

The dominant economic framework classifies both proof-of-work and proof-of-stake under the same flow-cost rubric. The analysis above implies that this classification is incomplete for both: both protocol families generate accumulated state-dependent deterrence that the one-shot framework sets to zero. The nothing-at-stake problem in proof-of-stake is, in the framework developed here, the degenerate case in which vested interests are zero — the state carries no accumulated commitment, and the game collapses to a coordination problem with trivial state. Modern proof-of-stake designs exist precisely to escape that degeneracy, by engineering the kind of history-dependent deterrence that proof-of-work produces organically.

The threshold analysis transfers directly. In proof-of-work, stock-like deterrence dominates flow cost after roughly ten and a half hours because vested interests accumulate through mining. In proof-of-stake with slashing, the accumulation mechanism is different — staking rather than block-solving — but the threshold logic is the same: a validator whose stake has been locked for longer than the unbonding period has committed capital that exceeds the flow cost of any short-duration attack. Current major proof-of-stake implementations impose unbonding periods substantially longer than the proof-of-work threshold, implying that the stock-like deterrence in staking-with-slashing is, by design, even larger relative to flow cost than in mining. The one-shot framework mischaracterises both protocol families in the same way, and for the same reason: it has no state variable to encode what the protocol has accumulated.

The Broader Lesson

The conflation of “Markov” and “memoryless” is, in the end, an instance of a more general failure: the failure to distinguish a property of a component from a property of the system that contains it. The exponential waiting time is a component of the mining game. The mining game is a system built on top of that component, with feedback mechanisms, state variables, accumulation rules, and strategic interactions layered on. The memoryless property of the component does not survive the layering. What survives is the Markov property — which allows the state to encode as much history as the protocol puts into it. And the protocol, as it happens, puts in quite a lot.

The practical consequence is that the economics literature has been measuring the wrong thing. Attack cost has been identified with flow cost. But the actual protocol generates additional deterrence through accumulated vested interests, locked coinbase rewards, and stabilising difficulty feedback — all of which are stock-like, all of which grow with the depth and duration of a miner’s participation, and all of which the dominant framework sets to zero. The flow cost remains a necessary component of deterrence. It is not the only one, and it is not the dominant one.

The methodological consequence is simpler still: when modelling a protocol with state-dependent mechanisms, use a model with state. The Markov game framework already exists in the literature. It was there from the beginning. It correctly encodes the block tree, the vested interests, the strategic interdependencies. The error was not in the original game-theoretic treatment. The error was in the downstream literature’s reading of it — a reading that saw “Markov” and heard “memoryless,” and built a decade of security analysis on the confusion.

The protocol is not memoryless. It is Markov, with a state that encodes everything that matters. The distinction is not pedantic. It is the difference between a system that forgets and a system that remembers — and the system, quite deliberately, remembers.