Cairn: a chain whose validation state does not grow

The problem is the cost of verifying, not the cost of transacting

A permissionless currency works because many independent parties check it. Nobody is in charge, so the checking is what prevents cheating. The security of the system is therefore a function of how many people can afford to be one of those parties.

That number falls as the chain succeeds. A full node holds the set of unspent outputs and validates every rule against it, and that set grows with adoption. Bitcoin's is past 170 million entries and roughly 11 GB ^[2]. Ethereum's state has driven a research programme spanning state expiry, weak statelessness and Verkle trees, which its own roadmap places several years out and dependent on two other unfinished efforts ^[3].

The usual answer is that hardware gets cheaper. Perhaps, but the direction is still wrong: the ratio between what a chain demands and what an ordinary person owns moves against the person. Light clients do not resolve this. They change who is trusted rather than removing the need to trust.

Cairn treats the growth of validation state as the design problem, not as an operational detail to be managed later.

Notes, and why they are not balances

Cairn keeps notes rather than accounts. A note is a value locked to an address, which is the hash of a public key, identified by the transaction that created it and its index among that transaction's outputs. It is written once and consumed once. This is the unspent output model, as in Bitcoin. The key appears on the chain when a note paid to an address is first spent, in the input that spends it, and every note that address still holds, change included, sits behind that published key from then on: an address shields its notes only up to a wallet's first payment. The shipped wallet pays every payment's change back to the one address it uses, so keeping the property afterward needs a fresh key drawn per payment, a decision the open questions paper already took and has not started. Reading a note costs a node no curve arithmetic either way.

The choice is not stylistic. An account balance must be read and written, so the account has to be held. A note is created once and destroyed once, which means a node can hold a commitment to it instead of the note itself, and can forget it entirely while remaining certain about what remains. Everything that follows depends on this property.

Ordering over note identifiers is defined, so the note set has exactly one canonical enumeration, which the state commitment depends on. Transfer identifiers exclude signatures and witnesses, and the keys that travel with the signatures. That gives malleability resistance, and more importantly it means a stale inclusion proof can be replaced with a fresh one without changing any identifier that anything else has committed to. A block commits to all three, so a block has one body.

Hashing is BLAKE3 with a distinct derived key per domain, so a value hashed as a note leaf can never be read as a header leaf or a Merkle node. Signatures are Ed25519 with four restrictions beyond what the standard requires. A key must be canonically encoded, not of small order, and in the prime order subgroup, all three asked of the key an input carries once its hash has matched the note's owner, so two byte strings can never name one key and no spend is taken under a key nobody holds. A note can be paid to an address nobody holds a key for, as on every chain that pays to the hash of a key; an address is written with a checksum that refuses any typo of up to four characters, which is what stops one being typed by mistake. And a signature is checked by the cofactorless equation against an R that is canonical and not of small order, the choice the standard leaves open and verifiers in use make differently, so a signature one node takes is one every node takes. Every signature commits to the network, the version, the transaction identifier, the input index, and the value and owner of the note being spent. Committing to the spent note is the lesson of transaction formats that could be deceived about their own inputs.

Two tiers, and only one of them is held

Validation state is split in two by a consensus rule.

3.1The hot set

A sparse Merkle tree, persistent through structural sharing so that a reorganisation restores the previous root without a rebuild. Eviction is by age, oldest first, in batches at block boundaries. The measured cost is 516 bytes per note, which is the note, its identifier, and its share of the tree. Rather more than half of that is the tree, which makes a leaner tree the clearest remaining optimisation; it changes no rule.

3.2The cold set

An append-only forest of perfect binary trees, held as one root per possible height. This is the structure introduced by Utreexo ^[4], and Cairn does not claim it.

The property the whole design turns on is that adding a leaf requires only the roots. A node holding none of the set can still extend the accumulator correctly, which is not true of a plain Merkle tree. On insertion the new leaf rides on the right of every merge, so the trees it swallows are its own siblings in order, and the inclusion proof falls out of the addition itself at no extra cost.

Removal is batched. Every proof in a block is verified against the pre-block root before anything is applied, then applied in order with the remaining proofs refreshed, so two cold spends in the same block cannot invalidate each other.

3.3Where Cairn differs from prior accumulator work

Utreexo is a node-level optimisation. Any operator may adopt it independently, the protocol is unchanged, and the underlying set remains unbounded. Accumulator schemes over RSA groups, such as MiniChain ^[5] and CompactChain ^[6], achieve constant-size commitments but require a group of unknown order, meaning either a trusted setup or class groups, and likewise leave the set unbounded.

Mina takes the opposite route to the same goal, compressing the entire chain to about 22 kB with recursive zero-knowledge proofs ^[12]. It works, and it is the most complete answer to this problem in production. The price is proof of stake, with the initial distribution that implies, and a cryptographic stack almost nobody can audit. Cairn pays a different price for a weaker guarantee: the state is bounded rather than eliminated, and everything used to do it is old and widely understood.

Cairn's contribution is not the accumulator. It is the pairing of a consensus-enforced cap on the held tier with an accumulator for the remainder, so that what a validator must hold is bounded by rule rather than by the operator's choice of implementation.

Spending what nobody holds

A spender of a fallen note supplies an inclusion proof. The node verifies it against roots it already has and never needs the set. Two windows make this workable rather than merely correct.

4.1A proof is worth what it is worth now

A proof is checked against the cold set as it stands, and against nothing else. Earlier versions accepted one matching any of the last thirty two states, so that a transfer written while a block was being found was not invalid through no fault of its author. That was half a rule. Removing a note folds the empty leaf along the path the proof carries, and an old path does not reach the root that is there now, so the removal did nothing, reported it through a value no caller read, and the note stayed to be spent again. Every node computed the same wrong state, so the network agreed and nothing forked.

Completing the rule instead of removing it would mean carrying, as committed state, whatever changed between an old root and the current one. That is bounded, at roughly four megabytes, but it is bought for a convenience that costs nothing to have another way. A transfer's identifier excludes its witness by design, so refreshing a proof does not make a different transfer. One that waited too long is the same transfer offered again; the pool already drops what the state no longer accepts, and a wallet already keeps its own proofs current as the forest grows.

4.2The grace window

A note that has just fallen remains spendable with no proof at all for GRACE_BLOCKS = 64 blocks, bounded also at GRACE_NOTES = 8 192 entries. Every node still holds both the note and its proof during that window, so nothing is asked of the spender. Without it the boundary between tiers would be a cliff that a payer falls off for no reason of their own.

Which of the two bounds is met depends on how fast notes are falling. On a quiet chain it is the 64 blocks. At the eviction cap, 1 024 notes a block, the 8 192 notes are met first and the window spans 8 blocks. That rate can be bought, by anybody, at a price: every note a transfer adds to the hot set destroys a fixed price, the place price, paid as part of its fee. It is destroyed rather than paid to whoever mines the block, so a miner filling its own blocks pays it like anyone else. What a flood costs, and what it does to the people it pushes out, is in the limitations.

Utreexo has a comparable observation, that outputs created and spent within one block need not enter the accumulator at all ^[4], and roughly 40% of outputs live fewer than twenty blocks. There it is an optimisation each node may choose. Here it is a rule the whole network applies, which turns a likelihood into a guarantee for whoever is paying.

4.3Archivists

A wallet keeps its own proofs current from what every block already carries, and asks nobody. A wallet that has been offline long enough, or that has lost its records, needs someone who kept the cold set. Archivists are optional nodes that do. Nobody pays them, and the network does not depend on them: joining a chain takes the headers, which every node keeps at 182 bytes each, and a wallet that kept its own proofs asks no one. What an archivist offers is recovery for a wallet that lost theirs.

They were in the design from the first day, for an intuition. Section 8 explains why they turn out to be structural rather than convenient.

What an archivist costs is a number that had never been written down, and it is worth writing down beside the claim it is the exception to. Measured over 3.2 million notes falling to the cold set, a plain node's ledger stays flat between 15 and 20 MB, from 319 000 notes to ten times that. An archiving node costs 104 bytes for every fallen note still standing: the note's leaf, the one inner node that leaf completes, at thirty two bytes each, and forty bytes saying where the leaf sits, so that finding a note is a lookup rather than a pass over the whole archive. A note that is spent keeps its two hashes and gives up its place in the index. That is the size of the exception, and it is the price of being able to rebuild a proof for somebody who lost theirs.

It is memory, and it is rebuilt: an archiving node holds the archive in the process rather than in a file, and reads the whole chain again at every start to put it back together. On a thirty year chain that is every block ever mined, read in order before the node answers anybody.

That figure is structural rather than measured, and saying which is the point. What an archive holds is 104 bytes a standing note and does not vary. What a process holding one occupies is more and moves about: the hashes live in vectors that grow by doubling, so between two doublings a vector carries up to its own length again in capacity nobody is using, and the index is a hash table carrying buckets nobody is using either. A slope read off a handful of points lands wherever those points happened to fall on that swing, which is how the explorer came to serve 72, measured before the index existed. The design costs 104. What a process costs is a fact about an allocator.

The figure was 64 here for a week after the index went in, because the one accessor anything read counted the hashes and not the index.

The measurements here were first published wrong, and how is worth more than the correction. They were read with ps, which reports the pages a process has resident. A cold set is written once and never read again, which is exactly what an operating system's memory compressor takes away, so the instrument was measuring the one thing it could not see: it reported 9 MB where the process was actually holding 204. A twenty-one-fold under-report, in the direction that flatters. The figures above are read with the footprint the kernel actually charges. The lesson is not that the first number was wrong, it is that a measured number is worth exactly what the instrument is worth, and nobody had asked what this one measured.

An audit found that the role had no protocol at all: nothing in the message set let a wallet ask an archivist for anything, and the error a stuck wallet showed named an archivist as though asking one were possible. That is closed. A wallet now asks for the paths it is missing, by position, and it folds every answer against the root its own node worked out from blocks it checked itself, so the answer can come from a stranger. A position is not a disguise. The question carries no name, but anyone with the chain can say which note sits at a place, whose it is and what it is worth, so the archivist learns whose money is stuck and how much, from the address the question came from, and can move none of it. The wallet therefore asks only nodes that say they keep the cold set, and a node that does not keep it answers nobody out of the paths it keeps for its own owner, which would tell a stranger whose node it is.

What is left of it is narrower and is still a real hole. A path is asked for by where the note sits, and where a note sits is learned as it falls. A wallet that was not running when its note fell, and kept no record of it, has nothing to ask about: the question is asked by place, and no message asks for a note by its owner. That wallet's money is on the chain and is its own, and nothing here can reach it. Compensating archivists remains open as well, and is the lesser of the two.

Consensus

5.1Proof of work, and why not stake

The reason is the beginning rather than the steady state. Proof of stake requires an initial distribution before it can function, which means somebody decides who holds influence on day one. Proof of work requires nobody to decide anything: the network opens and the first block goes to whoever mines it. For a currency whose claim is that no party is privileged, the opening is exactly where that claim is tested.

5.2Difficulty and timestamps

Difficulty retargets every block against a schedule fixed at the network's first block. The rule is ASERT, which Bitcoin Cash has run since 2020: a chain one half life ahead of its schedule is asked for twice the difficulty its first block carried and one half life behind for half, the half life is sixty blocks, an hour on the public networks, and no single retarget moves the difficulty by more than a factor of four either way. What a block is asked depends on where its chain stands, not on the path it took there, so a large miner arriving or leaving changes the rate without stranding the chain.

It replaced a moving average over ninety blocks, and the reason is worth stating because the testnet found it. On 2 October 2026 a stranger with about twelve hundred times the honest hash rate mined eighty blocks in two minutes and left. The moving average rose by its whole bound a block while the burst lasted and fell back only as the burst's blocks left its window, ninety slow blocks later: the next block was asked 768 times what the one before the burst carried, and the network nearly stopped for 33 hours. The schedule reads the same eighty blocks as a chain 4 656 seconds ahead of itself and asks the next block for 2.45 times the difficulty, and the honest miner walks back onto the schedule on its own.

What a departing miner leaves behind grows with the logarithm of what it paid rather than with what it paid. Reaching a difficulty X times the honest one takes a branch log2(X) half lives ahead of its schedule, about X times the honest rate for tau / ln 2; the next honest block waits about X target times, and the honest chain gives back the branch's lead, log2(X) half lives, in all. Both rules, measured on one basis:

The plan's simulator, re-run with both rules exactly as the code computes them, the schedule's bound of four included: random block times, the honest miner's clock on its blocks, the median of six seeds. The 2 October rows start from the real chain's last ninety blocks before the burst. The real chain's next hundred blocks came 31 hours late, the first of them luckier than the median; the schedule's figures are held by the tests in tests/the_difficulty_follows_the_clock.rs.

For the same effort the honest chain is held up thirteen to twenty six times less than under the moving average, and each further hour of delay costs more than the last. A burst as small as the 2 October one still costs the honest chain about half of what it paid: the schedule keeps it small, an hour, rather than cheap.

Lying about time buys little under it, and that was not always true. The moving average's first version read a solve time as the gap from the parent, floored at one second, so a miner dating its own blocks six minutes ahead took six minutes out of the measurement and the honest block after it put one second back; past roughly a sixth of the hash rate the difficulty fell to its floor within the hour. Under the schedule only the parent's timestamp is read, so a block dated as late as a reader accepts lowers the next difficulty by about eleven per cent and the next honest timestamp takes all of it back. Simulated against every share up to a half, the fastest a liar can make the chain run is the target.

The schedule starts at the first block, which makes that block's date a rule for good. A network opened long after its first block is dated stands behind its schedule from the start, and every block until it has caught up is asked the floor: nearly free, and about half a million of them for a devnet opened four weeks late. So a public network's first block is minted the day it opens.

Timestamps are validated against the median of the previous 11 blocks rather than against the parent. A miner writes its own timestamp but holds one vote in a median, which removes the single-block manipulation that a later-than-parent rule permits. A block may not be dated more than ten blocks ahead of the receiving node's clock, ten minutes on the public networks, nor before the moment the network opened. The allowance is counted in blocks because the retarget's half life is, and ten is a sixth of it on every network: at two hours, which is what it was, a minority dating its blocks at the allowance held the median in the future and made the chain run half again as slowly as its target.

5.3Fork choice

By cumulative work, not length. Ties keep the branch already followed, so churning the tip costs work rather than nothing, and two tips of one height are a tie until one carries more than half a block of extra work. The band is there because a block's difficulty follows its parent's timestamp: of two branches of one length, the one dated earlier is asked a little more above its first block and so weighs a little more, and switching on that surplus would hand every such race to whoever dated its blocks earliest, a withholding miner above all, rather than to the block heard first. That surplus grows with the depth of the match, so even within the band a withholder that dates its blocks as early as the median allows takes matches seven or more blocks deep, and loses more to the difficulty than it gains. A switch is applied atomically: each applied block records its own inverse, and a bad block discovered partway through a switch returns the node exactly where it was.

Undo records are kept for the most recent MAX_REORG_DEPTH = 1 024 blocks. The switch is refused at the network’s own burial, which is the same 1 024 here and which is what a handover is anchored at and what a reward matures at. Those three are one number on purpose: a node that undid past its burial would hand a newcomer a ledger anchored at a block it went on to orphan, and would take back a reward its own rules had called spendable. Keeping records further back than the refusal would be harmless, and a shorter test network makes use of that.

The depth itself is a local safety policy rather than a consensus rule: two nodes with different limits build the same chain and differ only after a reorganisation deeper than either would accept, which on a live network means an attack or a partition lasting most of a day.

Emission

Nothing is allocated. There is no sale, no founder allocation and no reserve; on the day a network opens the supply is zero and every unit since has been paid for the work of finding a block. The first blocks of both existing networks pay nobody at all.

The reward begins at 50 CAIRN and halves every 1 051 200 blocks, about two years at a one minute block time, until halving would take it below a floor of 0.01 CAIRN, which is then paid indefinitely. Roughly 105 million CAIRN exist by the time the floor takes over. The smallest unit is the pebble, at 10⁸ to one CAIRN.

The perpetual tail is deliberate. Whether transaction fees alone can fund security in the long run is an open question, and a chain whose central promise is verifiability in thirty years cannot rest its security budget on an open question. The price is a known, small and permanently decreasing rate of dilution.

A block reward cannot be spent until its block is past the deepest reorganisation the rules accept. It is the one kind of note whose existence depends on its own block surviving: a payment undone by a reorganisation can be mined again on the branch that won, a reward cannot. Without the wait, a two-block reorganisation took back money somebody had already been paid, with no rule broken and nothing to complain, which is why it is a rule here rather than a convention. The question is asked of the coinbase every note names, not of the tier the note is sitting in, because the hot set, the grace window and the cold set are three ways of holding the same note and a rule covering one of them would be a way to launder the other two.

The state root carries the money as well as the notes. A node can say how much exists and a header commits to the answer, so a defect that minted a pebble is a fork rather than something every node agrees about. That is not hypothetical: this chain was renumbered once for a defect whose own description reads money out of nothing, agreed by every node, so nothing forked and nothing complained. Eight bytes and one checked addition per block buys the ability to notice.

Joining a chain without downloading it

A bounded steady-state cost is not the whole promise if arrival is unbounded, and this is where the design was weakest.

7.1The measured cost of arrival

On this implementation, at one block per minute with blocks carrying 64 ordinary payments, thirty years of chain is 229 GB to download and every one of its blocks to revalidate, to arrive at a validation state weighing 68 MB.

7.2What headers commit to

Every header carries two fields beyond its own block, for 48 bytes:

Accumulated work. The work behind this block and every block before it, checked against the parent's, so a block cannot claim work it did not do.

A commitment to every earlier header. The root of an append-only forest holding one leaf per header, carried by a node as sixty four hashes exactly like the cold set, at a cost of one append per block.

These were added before any network carried value, because they could not be added afterwards: changing the shape of a header invalidates every block already mined. The test network took the next number when they landed, which cost nothing at the time and would have cost everything later.

A header also commits to every byte of its body. Its transaction root is taken over each transfer's whole encoding, signatures and proofs included, so a block has one body. A transfer's identifier leaves both out, so that a proof can be refreshed without making it a different transfer; the block commits to the version its miner carried. Before testnet-7 the root was taken over identifiers, and anybody relaying a block could make a copy with another signature or another proof under the same header, which a node could hold, and inside the grace window even apply, in place of the real one.

7.3What sampling does not settle

Weighing settles which chain carries the most work. It settles nothing about what that chain's ledger says, and the two are easily confused. A header commits to a state root, and proof of work says that somebody spent electricity on those bytes, not that the state in them is what honest transactions would have produced. A node that read the chain knows the difference because it watched every transaction go past. A newcomer has watched none.

So a newcomer that took the ledger of the heaviest tip would be buying an arbitrary ledger for the price of one block: mine one on top of the real chain, commit to any state you like, be heaviest for the moment somebody arrives. The honest network is unharmed (every node that read the chain rejects that block on sight), but the newcomer, which is the party this whole construction exists to serve, is not.

Cairn does not take a ledger at the tip. It takes one from BURIAL = 1 024 blocks below it and validates every block in between itself, checking every rule as any node does. A lie must therefore be buried that deep, and to be that deep while still being the heaviest chain on offer, its author had to out-mine everybody else for as long as it took to build them. That is the assumption the chain already rests on. The arrival stops being the weak part, and it stops being a light client: what a newcomer ends on is a ledger it built, from a starting point nobody could have written without doing the work.

The depth is the same as the deepest reorganisation a node accepts, so a newcomer lands exactly where a node that was away and came back lands, with the same ability to be moved off it by a heavier chain. What it costs is the blocks in between, once, and that cost does not grow with the chain: in thirty years it is still a thousand blocks.

7.4Sampled verification

One assumption is load-bearing here and was not stated before: that at least one of the peers a newcomer is talking to is honest and can answer. Joining is trust-minimised, not trust-free. Every chain offered proves its own work, and the checks below are what make that true rather than merely intended, but a newcomer surrounded entirely by one party's nodes is shown only what that party chooses to show. That is the same assumption every proof-of-work client makes at the moment it first connects, and it is worth writing down rather than implying it away.

With those commitments, a newcomer holding only the tip can be handed a logarithmic sample of old headers, verify that each sits where it claims in the tip's commitment, and conclude what work stands behind the tip without reading the headers in between. This is FlyClient ^[7], whose security rests on the same assumption as the chain itself, that no adversary controls a majority of the work.

The earlier superblock approach, NIPoPoW ^[11], achieves a similar compression by showing only unusually heavy blocks, but is vulnerable to bribing the miners who find them into withholding them. FlyClient's sampling has no equivalent target and is the construction to follow.

Cairn takes the published construction with its proven distribution rather than devising its own. It is implemented: a newcomer draws 4 096 headers against accumulated work rather than height, with a Fiat-Shamir seed taken from the tip, and each opened header is checked against the tip's own commitment. Weighing a thirty year chain costs about 3 MB, of which the run described below is 110 kB.

Four checks sit around the draw, and they are not decoration. An audit of the implementation found that without them a stranger could hand a newcomer a chain nobody had mined, for a single hash. It took the honest chain's headers, which any node serves to anyone who asks, put them in a commitment of its own, appended a thousand leaves that were not headers at all, and mined a tip at the difficulty floor declaring one unit more work than the honest chain. Every draw landed in the honest work below and every one was answered by a genuine header with a genuine proof. The lesson is worth stating plainly: a commitment places a header at a position, and a position is not a chain.

So the tip must open the header it was built on, at the height below it, carrying the work its own total leaves over, which a tip mined on nothing cannot produce. A number of blocks implies a least amount of work, because the difficulty falls by at most a fixed factor per block and never below the floor, so the stretches between opened headers cost something whether or not a draw looked at them: a thousand blocks cannot be worth one hash. And the run of headers between a handed-over ledger and the tip travels with it, so a newcomer rebuilds the commitment from the anchor upward and sees whether it arrives where the tip says it should, which catches a substituted header wherever it sat.

That last one is also what makes the burial cost work rather than block count. The run is checked block by block against the difficulty its own window demands, so the sender does not choose the price of its burial: before that check existed, a thousand blocks of burial could be laid at the difficulty floor for a thousand hashes, and the phrase bought nothing.

Those three were written first and were not enough, which is worth recording rather than tidying away. The draw stopped resolving about a thousand blocks from the tip at the time, deliberately, and nothing else looked up there either. So a forger left the honest chain untouched, appended its own headers at the difficulty floor, one hash each, and put the work it was inventing inside the band the draw never reaches. Every check above passes: the tip has a parent, because the forger mined one; the blocks between opened headers are worth what they say, because a cheap run honestly states that it is cheap; and the ledger's own run reaches the tip, because the whole run is the forger's. The anchor a newcomer is handed is then one of its headers, with whatever ledger it likes.

What was missing is that the top of a chain was tied to no difficulty anybody could check. So the run from the deepest header the draw actually landed on, up to the tip, travels with the weighing and is walked under the retarget: each header carries the difficulty its parent demands against the network's schedule, dates after the median of the window below it, and adds its own work. The window below the pinned header comes along too and is honest by construction, because those headers have to chain into it, and swapping them would mean having mined the pinned header on top of one's own.

The tip's timestamp is then measured against the reader's own clock, which is what turns the whole thing into a cost. Blocks at the difficulty floor have to stand behind their schedule, and past the half life of slack the floor's edge gives they average the target or the retarget demands more of them, so the thousand cheap blocks a forger needs span more than sixteen hours of stated time, and they cannot be backdated because they have to date after the honest window they descend from. More than ten blocks ahead of the reader is refused. What the attack costs is therefore real waiting, and the honest chain out-mines it while it waits.

How much work stands behind a tip is not the only question a newcomer has to ask. Which chain this is has three answers, and all three are cheap: every header a weighing opens names this network, every one is dated after the network opened, and the chain is shown to start from the block the software pins, opened at position zero of the tip's own commitment. A chain that starts anywhere else is refused whatever work stands behind it. The audit that closed the last of those reads the other way round: until it was closed, a chain started from another first block, carrying the right network number and dated after the opening, was weighed on its work alone and taken.

That run is capped, at 8 282 headers, about 1.5 MB, and the cap is a real limit rather than a formality: past it a chain cannot be weighed at all, and a newcomer reads it block by block instead. The run is a band of work rather than a distance from the tip, so its length in blocks is that band divided by the difficulty at the tip, and it grows as the tip's difficulty falls below what the chain averaged over its life. Measured over this implementation's own draw, on chains from three months to thirty years old: a chain that loses twenty four to forty eight times its hash rate, depending on its length, and does not recover cannot be weighed from about five days after the loss until months or years after it. While that lasts, every honest node answering is refused in the same words a forger would be. The cap is kept rather than raised, because raising it moves the cliff instead of removing it: the same measurement puts the run a thirty year chain needs a year after a four thousand fold loss at 526 027 headers and 96 MB, sixty three times the cap, and nothing in the shape of the problem stops the next chain needing more: the run is work divided by a difficulty whose only floor is one. Every metre of whatever number were chosen instead would be memory a stranger decides a newcomer will allocate before one check about the chain has been made. What the cap costs is the shorter way in, not the chain.

A second limit sits beside it, and it is about the price of a question rather than the size of an answer. The draw is seeded by the tip, so a forger that dislikes its questions buys another tip, and the retarget would let it walk its run down to the difficulty floor, where a tip costs one hash. So a newcomer refuses a tip more than 32 times below the hardest header of its run. That puts a tip at no less than a thousandth of an average block on a chain that ran to schedule, measured at 2^18.9 hashes at the public test network's opening difficulty as a lower bound, and it costs an honest chain what the cap does: one that loses more than about twenty times its hash rate is read rather than weighed, on the test network from about eight hours after the loss and for under five and a half days beyond what the cap already refuses. A burst that lifts the difficulty more than 32 times and leaves does the same: after bursts to 128 times, for up to fifteen hours on an old chain and thirty five on a young one, and after a burst to 1 024 times, for 100 to 124 hours on a chain a few days old. It costs whoever causes it about two days of the honest rate for every thirty two times: sixty days of it for the larger burst, which the 2 October intruder's rate pays in seventy minutes. A newcomer refused this way holds it against nobody and reads the chain block by block from a peer that kept it, which on a young chain every node does unless told otherwise.

The count follows from the assumption the chain already makes. A forger cannot mine what it did not mine, so a chain heavier than the honest one, presented by a party holding a share s of the world's work, has at least 1 − s/(1−s) of itself invented: work no block of it spans. At a third of the world's work that is half the chain. What does not follow (and an earlier version of this paper said it did) is that a draw lands in that invented part with the same probability. It would if the draw were uniform, and it is deliberately not: the density is one over the distance from the tip. That is what makes the bound indifferent to how deep a forger forks, and its price is a factor of the number of halvings on every draw. A draw lands in the gap with probability ln(1/(1−lie)) / levels, not lie, and that factor is the whole of the correction.

That factor is an input, and for six networks it was one a prover wrote down. levels is the number of halvings the draw spreads over, and it was computed from the height the tip states. A height is not work: the only rule holding the two together prices a stretch nobody opened at the difficulty floor, one unit a block, and a forest of any size costs what is opened in it and nothing for the rest. So a chain whose blocks averaged difficulty d could state a height d times its own, buy log2(d) halvings with it in work it was already inventing, and take that many slices off what every draw was worth. At a real chain's numbers that is fifty odd halvings against the fifteen the count is set for, and it took a forger at 40% from missing every draw with 2^-207 to missing them with 2^-58, against the 2^-128 this paper publishes. The count now comes from how old the tip says its chain is, over the block time the network aims at, and never past its height. A node refuses a tip more than ten blocks ahead of its own clock and the opening moment is written into the software, so no chain can say it is older than the network: a prover reaches the honest count rather than passing it. Understating it is left open and buys nothing, because fewer halvings make every draw worth more and widen the band nearest the tip, which is the run of headers the prover then has to hand over in full.

Setting the count from the real expression gives 4 096 draws, holding against every forger up to at least 42.96% of the world's work over a thirty year chain, measured against the function this implementation ships, and against forgeries built and put through the check. At least, and the word is exact: the figure is a maximum over hundreds of placements, each a hit rate taken over a finite number of seeds, and a maximum over noisy estimates runs high, so the threshold reads low and reads lower the fewer seeds are spent. It is published as a floor. This paper claims 40%, keeping the rest for the difference between a staircase of halvings and the smooth density it stands for. Past 50% nothing helps: a forger at half the work has nothing left to invent and can mine the chain.

The guarantee is a depth, and it is worth stating as one. The draw stops resolving 512 blocks from the tip, deliberately, because resolving finer would cost the count again to separate chains nothing else here separates either. So a forger cannot put a newcomer on a branch differing from the real one by more than about 633 blocks (ten hours). Inside that it can, and so can a slow peer: it is where any node sits for its first blocks after connecting.

That depth is the same whatever share of the work the forger holds, and this paragraph used to imply otherwise. Measured over the shipped draw, a forger at 5% of the world's work reaches exactly the depth a forger at 40% reaches: 633 blocks in both cases, and at every share between. The reason is that the crossing sits below the deepest band the draw resolves, where the overlap does not depend on the share at all. So the 40% is not a bound on how far a newcomer can be moved. It is the point past which there is no bound: past the share the count holds to, the same measurement gives millions of blocks. The failure is a cliff and not a slope, and a reader who took "a forger at 40%" to mean a weaker forger does less damage was reading something this paper did not check.

That depth sits inside the node's own reorganisation limit, and getting the two to line up is what the 512 is for. MAX_REORG_DEPTH is 1 024 and the effective undo limit is the lesser of that and the network's burial, so on the public test network, whose burial is the full 1 024, a newcomer put on a branch at the far end of the guarantee is somewhere the ordinary reorganisation rule can carry it back from. Devnet is the exception and is meant to be: its burial is 32 so a throwaway chain matures in minutes, it undoes 32 blocks against a guarantee of 633, and what makes that acceptable is that it names no seed, so a newcomer there joins its own operator's machines and no stranger is placed to weigh it onto a branch. This paragraph named the lesser-of rule and then concluded as though the lesser were always the constant. It was not always so. The draw stopped at 1 024, the same number, which looked like the two rules agreeing and was not: the guarantee is not the band, it is the band plus what the staircase costs at its edges, and that measured 1 240 against a limit of 1 024. This paper stated that gap and named three ways of closing it. The first of them is what was done, and what it cost is one more level of halving: a draw is now worth a fifteenth of a uniform one rather than a fourteenth, which takes the share the count holds to from 43.37% to 42.96%. The published 40% did not move, and an earlier version of this paragraph said the opposite of all of it, that the depth was shallower than the deepest reorganisation, which its own two figures at the time refute.

The first version of this paper claimed 512 draws and 45.7%, on the assumption that a draw lands in invented work with probability lie. Measured against the shipped function, the placement that suits a forger best left that at 2^-5.8 rather than 2^-128. The count and the density above are the correction; the claim went from 45.7% to 40%, and the cost went up eightfold with the draws. None of this is a proof in the other direction: it is a measurement over one family of placements, made in-house, and it is the part of this design that most wants an outside eye.

Measurement checks the derivation the other way, by forging chains and watching them fail, and it also shows why the distribution must be taken and not improvised: under a uniform draw, a forger who keeps the real chain and fakes only the last twenty blocks goes unnoticed 88% of the time, which is precisely why FlyClient samples the recent end of the chain more densely.

Serving that sample takes the headers and the forest they make, which a node keeps on disk at 182 bytes a header and 64 for its place in the forest: 129 MB a year, against 50 GB a year for Bitcoin and 200 for Ethereum. Every node keeps them, so joining a chain does not depend on anyone volunteering to carry its history. Blocks a node has already applied are dropped once it has written down the ledger they add up to, which is what stops a node's disk from growing with the chain.

One practical note in Cairn's favour. A production study of FlyClient reports that proof size is dominated by header size, and that restructuring headers would reduce proofs by 71% at the cost of a consensus change the chain it studied can no longer make ^[8]. That chain's header is 1 487 bytes, of which 1 344 is one Equihash solution. A Cairn header is 182 bytes, which is the same lesson taken before rather than after.

The limit that applies, and where Cairn falls

Christ and Bonneau prove an information-theoretic result about any system of this shape ^[1]: there is no useful trade-off point. A system must either hold a global state linear in the number of accounts, or require a near-linear rate of local proof updates as coins are spent. They add, and this bears directly on the design here, that so long as the succinct state is too small to capture the full state, enlarging it helps little.

Cairn falls on the proof-update side of that dilemma, deliberately, and had accepted the cost before knowing it was proven inevitable.

A wallet refreshes its own proofs from what every block already carries. The hot set does not repeal the result; what it changes is who is affected. Notes that have moved recently, which are the ones ordinarily spent, are held in full by every node and require no proof at all. The obligation falls only on value that has not moved recently. How recently is worth stating plainly rather than leaving to the word: the hot set is capped at a number of notes, so how long a note stays in it depends on how busy the chain is. Measured at full blocks (587 payments a block, which is what success looks like), a note falls to the cold set in 3.7 hours, and the grace window that follows lasts about fourteen minutes. At a tenth of that traffic it is 37 hours, and at a hundredth, fifteen days.

So the honest statement is that the validator's cost is capped and the saver's inconvenience is not: the busier the chain, the more of anyone's money needs an inclusion proof to spend. That is the Christ–Bonneau cost this design accepts rather than escapes, and it lands hardest exactly when the chain succeeds. A wallet that stays online refreshes its own proofs and never notices. One that does not must keep them, or find somebody who did.

The authors name proof-serving nodes, third parties holding the full state and producing current witnesses for others, as the natural relaxation, and call for work on how such parties would be compensated. Those are Cairn's archivists. They were included for an intuition and turn out to be structural.

Cairn does not answer the compensation question; it narrows what rests on it. Two services were bundled under the name: showing a newcomer which chain carries the most work, which the network cannot do without, and rebuilding the proof of a note whose owner lost theirs, which it can. The first was separated out and made small enough that every node performs it (182 bytes a header and 64 for its place in the forest, 129 MB a year), so nothing in the protocol now depends on a party being paid. What is left is recovery for a wallet that kept no records, and a wallet that keeps its own needs no one.

What this borrows, stated plainly

Overclaiming is the fastest way to lose the only readers whose opinion matters.

The append-only forest carried by its roots is Utreexo's ^[4]. Spender-supplied inclusion proofs are the common model of Utreexo, MiniChain and CompactChain. The header commitment and work-weighted sampling are FlyClient's ^[7]. The archivists are the proof-serving nodes of Christ and Bonneau ^[1], arrived at independently. None of the cryptography is novel, and it is not meant to be: BLAKE3 and Ed25519, both with domain separation and canonical encoding enforced, and no trusted setup anywhere.

What a survey of the field did not find an equivalent of: a hot set capped by consensus rule; the two tiers paired, holding a bounded set in full while carrying the remainder in constant space; a grace window as a network rule rather than a per-node cache; and bounding state without destroying anything. Ergo charges storage rent and lets a miner take a box left idle for four years ^[9]; a December 2025 proposal to the bitcoin-dev list would render outputs below a moving floor permanently unspendable ^[10]. Both bound the state by removing value from its owner, which the first guarantee here forbids.

A search is not proof of absence, and this section should be read as a claim about what was found rather than about what exists.

Parameters and measurements

Every figure below is measured on the implementation rather than estimated, on one core of an ordinary machine.

The first two rows are what arriving used to cost, and section 7 is how it stopped costing that. Arriving now has three parts, and it is worth adding them up rather than quoting the smallest: about 3 MB to weigh the chain; the ledger, which is 11 MB of hot set, and at most 29 MB once the grace window and a path for every note in it are counted, as they are on any chain that has seen traffic; and the thousand blocks between that ledger and the tip, which a newcomer validates itself. Those blocks are at most 134 MB, the block size limit a thousand and twenty four times over, and in practice far less, since a block is only as large as the traffic that filled it. Against a hundred and ninety-seven gigabytes of reading, and none of the three grows with the chain's age.

What a node holds is every row marked as its own, and the largest of them is not the hot set. A node keeps a record of every block it could still undo, what the block did and how to take it back, and at 64 payments a block those records come to the 51 MB above; they come to 400 MB on a chain of full blocks, where every block spends and creates nine times as much. That term was left out of this table until the records were counted, and it is the one that decides what a phone has to hold on a busy chain. Beside it, the paths a node keeps for the notes in its grace window are priced at the tallest tree a forest can hold, and are a few megabytes on a real chain. The block bodies a node keeps are the sixty four most recent and the headers of the rest; it reads an older body back off its own disk on the one occasion that needs it, a switch that fails partway. What the store allows itself is larger, at most 168 MB of blocks, rival branches included. And one row grows: an identifier every 1 024 heights for everything older than the window, 16 kB a year, which is what lets two nodes agree where to look without either holding its whole branch.

Seven of the figures above were wrong until this draft, and how is worth more than the correction. A block carrying 64 payments was published at 3 211 bytes. The program that measured it asked for 64 transfers a block and could fund only 16, because a coinbase carries at most 16 outputs and the purse it spent from was refilled by the coinbase alone; so a figure labelled 64 was the cost of 16, and the thirty-year download built on it was short by four times over. Underneath that, the block sizes and the timings were taken before headers carried the two commitments described in 7.2. The header row was corrected for those 48 bytes and the block rows were not, so the table disagreed with itself by exactly the number it stated a page earlier. Both are the same failure as the memory readings in 4.3: not arithmetic, but nobody asking what the instrument was pointed at. The figures here are now checked against the running build every time the tests are run.

Limitations

Nothing here has been audited. No external review has taken place. The only network in existence is a test network whose currency is worthless by design and which will be reset.

A node that started from a handed ledger is not the same node as one that read the chain. A validator that applied every block from the first refuses an invalid history however much work stands behind it, and no amount of mining takes that from it. A node that started at an anchor has that property for every block above the anchor and not for the blocks below it: for those it has the work, and the commitments the headers carry, and nothing else. The difference is invisible until somebody out-mines the network for the length of the burial, which is the assumption the chain already rests on, so the fast start adds no new one. What it does is turn a check that held against any amount of work into one that holds against less than a majority of it, and that is worth saying rather than leaving to be inferred.

The block by block way in needs blocks somebody kept. It is named above as what a newcomer falls back to when a chain cannot be weighed, and it checks more rather than less, which is true. What is also true is that an ordinary node keeps a bounded number of bytes of blocks and drops the rest once its ledger is written, and no rule obliges anyone to keep more. Headers are kept for ever and a header does not rebuild a body. So the fallback rests on somebody having chosen to archive, and on a newcomer being able to find them. A node says what its own retention costs a newcomer when asked, which is the half an operator can act on; the other half, finding an archivist on a network that has none, is not solved here.

The sampling bound is measured, not proved. 4 096 draws hold to 40% of the world's work and a depth of about 633 blocks, and both figures come from measuring the placement a forger would choose rather than from a theorem. The first version of this claimed 512 draws and 45.7% from a derivation that assumed a uniform draw; measurement put it at 2^-5.8 instead of 2^-128, which is how the correction was found. That the same thing is not still hiding one level down is exactly what nobody outside this project has checked, and it is where an outside review should start.

There is a second reason to start there. The next thing found was not in the bound at all but beside it: the sampling was sound about how much work a chain carried and said nothing about whether the tip stood at the end of that chain, which let a forger borrow a weight somebody else had mined. Three checks close it and they are described in 7.4. What is worth taking from the episode is that the failure was not in the arithmetic everybody looks at. It was in an assumption the arithmetic never made and the surrounding code quietly relied on.

A chain that loses most of its miners cannot be weighed while it recovers. The run of headers a weighing carries is capped at 8 282, and a chain whose difficulty at the tip has fallen far below its lifetime average needs a longer one. Measured over this implementation's own draw: a loss of twenty four to forty eight times the hash rate, depending on the chain's length, puts a chain out of reach of the short way in from about five days after the loss until months or years after it. Nothing is lost and nobody is attacked. Newcomers read the chain block by block, which checks more rather than less; what it costs is the bandwidth and the hours the sampling exists to save, at the moment a chain is least able to spare either. The cap is deliberate, because the run needed has no bound of its own. What was wrong, and is mended, is that a node meeting it told nobody: the two refusals were discarded where they were made, so an operator saw a node asking peers, dropping them and taking hours, with no reason anywhere. It now says, when several peers fail in the same words, that the chain in front of it is what those failures have in common.

A rule changes at a height, and a node that has not updated by then is on another chain. Renumbering the network, which is what the test networks did seven times, throws every balance away with the chain; on a network carrying value that is not a mechanism but a loss. So a rule that changes names the height it takes effect at, and blocks below it go on being judged by the rule that judged them: nothing already mined becomes invalid. Nobody votes on it. The height is in the software, published long before it arrives, and miner signalling is refused for the reason proof of stake is: it would hand whoever mines a veto over the rules. What none of that fixes is the node that did not update: it is following a chain the network has left. It is told which version it lacks, and stops, because a wallet reading a balance off an abandoned chain answers confidently and wrongly.

A node that joined cannot take in a newcomer. Showing which chain carries the most work takes the headers from the first block, and a node handed a ledger has them only from where it was handed on. It can become one by reading the chain; nothing else is lost.

The wire is neither private nor bound to a peer. Nothing between two nodes is encrypted or authenticated, so whoever sits on the path, a provider, a host or the network in a café, can be every peer a node has without running a node at all: it can withhold or delay blocks, and it reads every transfer a wallet sends as it leaves. What it cannot do is forge, since every block carries its work and every transfer its signatures. The rules that keep one party from filling a node's peers are rules about addresses, and this adversary needs none. Whether to encrypt the transport is a decision this project has not taken; Bitcoin took it in BIP 324.

The comfort of a quiet chain can be bought away. How long a note stays hot, and the 64 blocks of grace after it falls, are what a quiet chain gives when nobody pays to change them, and not guarantees. The protocol cannot tell a flood from a busy chain and does not try. What it does is price the flood: every place a transfer takes in the hot set destroys 6 000 pebbles, paid once, as part of the fee, by whoever takes it, and a miner pays it too because it is destroyed rather than claimed. Its own coinbase is the one exception: up to fifteen extra outputs beyond the one that claims the reward take a place each for nothing, so a miner with a tenth of the work adds about one and a half unpriced places a block this way, and one mining alone up to fifteen. Pushing every note out of the hot set therefore costs 131 072 places, 7.9 CAIRN destroyed and about half a CAIRN more in byte fees, and the eviction cap spreads it over at least 128 blocks, about 130 at the pace a miner's software builds them: a little over two hours. Measured on the implementation, cairn-chain/examples/flood.rs flushed a full tier in 130 blocks of 1 009 evictions each. While a flood lasts the grace window spans 8 blocks rather than 64, and a spend waiting in a pool with a proof is let go of whenever the tree its proof belongs to changes, which in the measured flood was about one block in two, unless its wallet offers it again with the proof its node keeps current. Nothing is taken: the notes are pushed out, not removed, and a note is never charged for where it sits. Their owners spend them with a proof, which is about six hundred bytes more, and that is what the price is measured to cover. It is not set higher because every payment with change pays it once too: a price of a block reward for the whole tier, about 38 000 pebbles a place, would multiply an ordinary payment's floor by five and still leave a miner with a tenth of the work able to flush the tier for one of the 144 rewards it earns a day.

The theorem's cost is real. A wallet offline long enough, or one that lost its records, must ask an archivist. Nobody is paid for that service and the network runs without it, which bounds the problem rather than solving it: a wallet in that position depends on someone having chosen to keep the cold set.

Smaller. An archivist rebuilds a proof in time proportional to the depth of the set rather than its size. Over half of what a hot note costs is the tree that commits to it, which is where the room left is.

The implementation is roughly 86 000 lines of Rust with 2 500 tests, no unsafe code, no asynchronous runtime, and five dependencies. Arithmetic side effects, slice indexing, and panicking helpers are denied at the workspace level. It is small enough to be read, which is the point: a chain asking people to verify for themselves should be verifiable in more than one sense.

References

1. M. Christ and J. Bonneau. Limits on revocable proof systems, with applications to stateless blockchains. Financial Cryptography and Data Security, 2023. eprint.iacr.org/2022/1478
2. Bitcoin Optech. Utreexo topic page, UTXO set size figures. bitcoinops.org/en/topics/utreexo
3. Ethereum Foundation. Statelessness, state expiry and history expiry. ethereum.org/roadmap/statelessness
4. T. Dryja. Utreexo: a dynamic hash-based accumulator optimized for the Bitcoin UTXO set. MIT Digital Currency Initiative, 2019. eprint.iacr.org/2019/611
5. MiniChain: a lightweight protocol to combat the UTXO growth in public blockchain. Journal of Parallel and Distributed Computing, 2020.
6. CompactChain: an efficient stateless chain for UTXO-model blockchain. Frontiers of Computer Science, 2023. arxiv.org/abs/2211.06735
7. B. Bünz, L. Kiffer, L. Luu and M. Zamani. FlyClient: super-light clients for cryptocurrencies. IEEE Symposium on Security and Privacy, 2020. eprint.iacr.org/2019/226
8. Catching the Fly: practical challenges in making blockchain FlyClient real. 2026. arxiv.org/abs/2604.26736
9. Ergo Platform. Storage rent. docs.ergoplatform.com/dev/protocol/storage-rent
10. Reducing RAM requirements with dynamic dust. bitcoin-dev mailing list, December 2025. groups.google.com/g/bitcoindev
11. A. Kiayias, A. Miller and D. Zindros. Non-interactive proofs of proof-of-work. 2017. eprint.iacr.org/2017/963
12. O(1) Labs. Mina: a 22 kB blockchain, technical reference. minaprotocol.com