Solana Shred Recovery: When Valid Shreds Form an Invalid Erasure Batch

A Solana block reaches validators as shreds, in batches of 32 data shreds and 32 coding shreds tied together by one Merkle root that the leader signs. Every shred in a batch can carry a valid signature and a valid Merkle proof while the batch itself is wrong, because nothing in the signature says the coding shreds are the parity of the data.

SIMD-0504 says the rules for a batch apply to rebuilt shreds as much as to received ones, and between 24 October and 5 November Agave rebuilt its recovery path to enforce that: every validator now rebuilds every batch, so a batch like this fails everywhere. We modelled the old and new paths with the Reed–Solomon library Agave uses and ran four kinds of malformed batch past simulated validators losing packets. Under the old code, what a validator ended up doing depended on which shreds it happened to receive. Under the new code, every validator that collects 32 shreds rejects the batch: none of 800,000 rebuilds of a malformed batch passed.

How an erasure batch is built

The leader cuts its block into data shreds and, for every 32 of them, computes 32 coding shreds with a Reed–Solomon code. Any 32 of the 64 are enough to rebuild the other 32, so a validator can lose half of a batch to the network and still have the block. Then the leader hashes all 64 shreds into a Merkle tree, signs the root and attaches to each shred its path to that root. A validator checks each shred on arrival: the signature over the root, and the path from the shred to the root.

What the signature does not cover

The Merkle root commits to the bytes of each of the 64 shreds. It says nothing about how they relate. A leader can compute its coding shreds from different data, or change one byte of a shred after encoding, then build the tree and sign. Each shred still verifies on its own. The batch is not a Reed–Solomon codeword: rebuilding it from different subsets of shreds gives different answers.

Until 29 October, Agave ran Reed–Solomon only when data shreds were missing and at least 32 shreds of the batch were present, tried again after every new insert of shreds, and logged a failed attempt at info level before moving on. The Merkle check made sure a rebuilt shred was byte-for-byte what the leader had signed, so a bad batch could never smuggle in different block data. But whether a validator noticed anything depended on which shreds it held. In our simulation of 2,000 validators per row, adding one shred per insert, each row counts the validators that completed the batch from data shreds alone · recovered without noticing the bad shred · were left waiting for repair:

Those in the first group never looked at a coding shred. With the first coding shred corrupted, every recovery that used it failed, about 31 failed attempts per validator even with no loss, and at 5% loss four validators in five could not complete the batch from Turbine. Repair fixes that, because it hands out the shreds the leader signed, but it takes longer. With the last coding shred corrupted, most recoveries never touched it and quietly succeeded. A corrupted data shred, or coding shreds computed from other data, behaved like the first case. Nothing in any row was rejected.

SIMD-0504: the batch is the unit of validity

SIMD-0504, written by Philip Taffet of Firedancer, replaces the shred rules each client inferred from Agave’s code with a written list. Sixteen checks apply to each shred: index ranges, the fixed 32:32 layout, a Merkle tree of exactly six levels, flag and size rules. A shred that fails them is dropped. Eight checks apply to the batch as a whole: one slot, one shred version, one chained Merkle root, one parent across the data shreds, padding only at the end. A block containing a batch that fails them is invalid. Under TowerBFT a validator must not vote for it, and under Alpenglow it must vote skip.

None of the sixteen or eight checks says the coding shreds must be the parity of the data. That follows from the proposal’s note on recovery: the batch checks apply to received and rebuilt shreds alike, so a validator that received all 32 data shreds must still check the coding shreds. The proposal says why: to eliminate any divergence based on whether a validator received or recovered a shred. A rule that only the validators who happened to need recovery could check would split the cluster the first time a leader broke it. Agave enforces the note by rebuilding every batch, and a batch whose coding shreds aren’t the parity of its data cannot be rebuilt to the root the leader signed.

“Always recover”: how Agave checks every batch

Agave landed the change in a series of pull requests: #16194 wired the rebuild into blockstore on 29 October, #16378 added the feature gate and enforcement a day later, and #16639 stopped retrying a batch that cannot be rebuilt once SIMD-0504 is active. In the code at the time of writing, a batch is rebuilt exactly once, in the insert that first brings it to 32 shreds, whether or not any data shred is missing:

received exactly 32:  reconstruct the other 32 shards
received more than 32: reconstruct missing data from 32 of them,
                       re-encode all 32 coding shards,
                       compare with the coding shards received
then:                  rebuild the Merkle tree from all 64 leaves,
                       compare with the signed root
fail either check:     with SIMD-0504 active, mark the slot dead
                       (unless it was already full before this insert)

The gate is stricter_shred_validation, key s5o4YoA9zUrw9j4v335ncdG5PpznDBsrgM6CvUGrasA. On 6 November at 03:18 UTC its feature account did not exist on mainnet, testnet or devnet. Until it is activated, Agave runs every check and reports failures to its metrics, but rejects nothing it did not reject before.

Same verdict, whatever arrived

Our model follows that code with the same library, version and features (reed-solomon-erasure 6.0.0 with simd-accel), 987-byte shards and Agave’s Merkle construction. We built four malformed batches, the first or last coding shred flipped by one bit after encoding, one data shred flipped, and all coding shreds computed from different data, and rebuilt each from 200,000 random subsets of every size from 32 to 64 shreds:

The reason is simple once written down. The rebuild produces one Reed–Solomon codeword from the shreds it used. For the batch to pass, that codeword must equal the signed shreds at every position the validator did not receive (or the Merkle root differs) and at every coding position it did receive (or the parity check fails). The positions it used to rebuild match by construction. So passing requires the codeword to match all 64 signed shreds, which only happens if the batch was a valid codeword to begin with.

In the packet-loss simulation every validator that reached 32 shreds flagged every malformed batch, at every loss rate from 0 to 45%, and passed the honest one. That held with one shred per insert, and again with inserts of a random 1 to 16 shreds, where about half the failures of the last-coding-shred batch came from the parity comparison rather than the Merkle root. The only validators without a verdict were those that never collected 32 shreds through Turbine, 16 to 19% of them at 45% loss and none at 20% or less; they run the same check when repair brings the batch to 32.

What rebuilding every batch costs

Less than it sounds. The old code already rebuilt a batch whenever a data shred was missing when it reached 32 shreds, and that is nearly always. The leader sends a batch’s data and coding shreds together, and Turbine routes each shred down its own tree. If they arrive in random order, the first 32 are exactly the 32 data shreds with probability 1 in C(64, 32), about 5.5 × 10⁻¹⁹, which fits the pull request’s estimate that the old code skipped recovery less than once in a trillion batches. What is new is re-encoding the received coding shreds when an insert pushes a batch past 32 at once, and rebuilding batches made only of data shreds. Timed on our model, per batch:

Most of that is hashing the 64 leaves of the Merkle tree, about 214 µs here, which both versions do; encoding 32 coding shreds takes about 83 µs. For the same 32 shreds the new path costs exactly what the old one did, and re-encoding the received coding shreds adds about 9% when more than 32 are present. These are timings of our model on an Apple M1 Pro; absolute numbers depend on the hardware, SHA-256 speed above all.

Two Turbine changes around it

Rebuilt coding shreds are now retransmitted. A validator forwards rebuilt shreds to its children in Turbine, so one dropped packet upstream doesn’t starve everyone below. When an insert brings only data shreds, the rebuild produces coding shreds the validator never received, and the first version of always-recover, keeping Agave’s old output, threw them away. #16622 forwards them as well, which its description notes Firedancer already did.

Leaders no longer rebroadcast. When a leader’s own slot had not been seen by enough stake, Agave’s replay stage asked the broadcast stage to send every data and coding shred of that slot again, after 5 seconds and then at doubling intervals up to 320 seconds. On 5 November #16595 removed Tower consensus from Agave’s replay stage as part of its Alpenglow cleanup, and the request went with it. Hours later #16713 deleted the broadcast worker that served those requests. The issue behind it had called the mechanism redundant if repair works. A validator missing shreds now has two ways to get them: rebuild them from the batch, or ask a peer through repair.

What this does not show

We ran a model of Agave’s rebuild, not Agave: shred headers, signatures, the per-shred checks and the batch header checks are not in it, and a malformed batch here differs from an honest one only in its erasure coding. Arrival order and loss are random and independent, which real Turbine is not, and inserts are one shred or a random 1 to 16. We had no cluster, so nothing here was measured on a network; the timings are from an Apple M1 Pro, not validator hardware. Firedancer’s implementation of the same rules was out of scope.

Shred Recovery: Questions People Actually Ask

The one-line version

A leader can sign an erasure batch whose shreds each verify but whose coding shreds aren’t the parity of its data; SIMD-0504 makes that batch invalid, and Agave now rebuilds every batch once it has 32 shreds, so every validator rejects it the same way, whichever shreds reached it.

Sources: SIMD-0504 at commit 33c75cff; Agave #16194, #16378, #16639, #16622, #16595 and #16713, read at commit 9eacc06d; the old recovery path at dd6f564f. The model, simulation and timings are our own.