Earn Your Stripes

You can also read this blog post on commonware.xyz’s blog.

---

A blockchain can only finalize transactions as fast as it can disseminate them between validators. At high TPS, that means moving big blocks across the network.

Sending a full copy to every validator turns the leader’s upload into the bottleneck while everyone else’s bandwidth sits idle. Deliver Us in Pieces showed how erasure coding could be seamlessly integrated with Simplex to spread that load across the network: the leader sends a different shard to each validator, validators relay what they receive, and everyone reconstructs the full block once enough pieces arrive.

Those bandwidth savings come with a computational tradeoff: the leader must encode each block before sending it, and every validator must reconstruct it and verify its commitment before certification. Until recently, Reed-Solomon recovery bottlenecked on a single core. We removed that bottleneck by cutting every shard into matching stripes and recovering them in parallel.

Parallel Hashing, Serial Recovery

Reconstruction was already parallelized, but only while hashing missing shards to rebuild the Merkle root. Reed-Solomon recovery itself remained a single decoding pass. Vector instructions accelerated that pass on supported CPUs, but it still ran on one core.

Benchmarks on an Apple M5 Pro (8 MiB block, 250 chunks) show where recovery stops scaling. The all-original case does no recovery. The full-recovery case reconstructs every original:

From 1 to 16 workers, all-original end-to-end latency dropped from 34.96 ms to 7.90 ms. Full recovery improved through 8 workers, then changed little at 16, flattening near 26 ms. Because the cases hash different sets of missing shards, the gap between them does not isolate recovery time. The relevant signal is how they scale: the all-original path keeps improving, while the recovery-heavy path barely changes beyond 8 workers.

From One Decoder to Many

Reed-Solomon encoding represents the block as $k + m$ equal-length shards, with $k$ original shards and $m$ recovery shards. When original shards are missing, any $k$ shards can recover the original block. Before this change, recovery handed the full shard width to one Reed-Solomon decoder.

To recover one 16-bit symbol inside a missing shard, the decoder only needs the corresponding symbol column from the available shards. We turn that into parallel work by cutting the shard width into contiguous byte ranges, or stripes. Each stripe covers the same range across all shards and runs as its own Reed-Solomon job. The jobs run concurrently.

Let $a_i$ be the codeword index of supplied shard $S_i$, for $i = 1, \ldots, k$, and write $A = (a_1, \ldots, a_k)$. All supplied shards have the same even byte length. Split them into $p$ stripes at identical boundaries. Every non-final boundary is aligned to 64 bytes, so the original partial tail, if any, remains wholly in the final stripe. For every stripe $t$, the decoder receives the indexed slices $(a_i, S_i^{(t)})$, preserving each shard’s original codeword index:

$$S_i = S_i^{(0)} \mathbin\Vert S_i^{(1)} \mathbin\Vert \cdots \mathbin\Vert S_i^{(p-1)}.$$

Reed-Solomon recovery works independently at each symbol position. Stripe $t$ therefore recovers only stripe $t$ of the missing shard $D_1$:

$$D_1^{(t)} = \operatorname{recover}_{D_1,A}\!\left(S_1^{(t)}, \ldots, S_k^{(t)}\right), \qquad D_1 = D_1^{(0)} \mathbin\Vert \cdots \mathbin\Vert D_1^{(p-1)}.$$

No stripe reads or writes another stripe. The $p$ stripes can therefore be recovered in parallel, and concatenating their outputs produces the same $D_1$ as one full-width decode.

Commonware’s authenticated Reed-Solomon codec uses the novel-polynomial-basis FFT construction to evaluate polynomials over a binary extension field with a radix-2-style butterfly. Write the shard matrix as $X = [\mathbf{x}_0 \; \cdots \; \mathbf{x}_{w-1}]$, where $\mathbf{x}_j$ is the vector formed by symbol column $j$ across the shards. If $\mathcal{T}$ is the encoding or recovery transform, the butterfly acts independently on each column:

$$\mathcal{T}(X) = \left[\mathcal{T}(\mathbf{x}_0) \; \cdots \; \mathcal{T}(\mathbf{x}_{w-1})\right].$$

In theory, a stripe can therefore end at any symbol boundary.

The optimized arithmetic processes 32 columns as one batch. Modern CPUs can apply the same operation to several values with one vector instruction, so this layout lets each butterfly step update several columns at once:

$$32\ \text{columns} \times 2\ \text{bytes per column} = 64\ \text{bytes}.$$

A short final batch is padded. Cutting an interior stripe through a batch would turn that slice into a different padded tail, so every non-final stripe ends between complete batches. This implementation constraint preserves the column-wise decomposition above.

Recovery Scales

We reran the same worst-case decode before and after striping:

With one worker, one stripe follows the original full-width decode, so no parallel speedup is expected. With eight workers, parallel recovery cuts worst-case decode from 26.85 ms to 10.22 ms, a 2.63x speedup. With 16 workers, it falls to 7.67 ms, a 3.38x speedup. The recovery work that stayed on one core now scales with the available workers.

Removing the Second Transform

Splitting each shard into independent stripes made recovery parallel, but the verification path still ran Reed-Solomon twice. After it decoded missing originals, it re-encoded every recovery shard, compared any provided recoveries with that output, and rebuilt the Merkle root over the complete codeword. As explained in Deliver Us in Pieces, checking a shard against the commitment does not by itself show that all committed shards form one valid Reed-Solomon codeword.

By vendoring reed-solomon-simd, we could make the decoder return missing recovery positions and remove the second pass whenever an original shard was missing. The expensive decode transform had already evaluated those positions, but only missing originals were exposed.

Write the systematic generator matrix as

$$G = \begin{bmatrix} I_k \\ P \end{bmatrix}, \qquad C = GX,$$

where $X$ contains the $k$ original shards, $P$ generates the recovery shards, and $C$ is the complete codeword. In Figure 2, take the ordered row lists $A = (D_0, D_2, R_0)$ and $M = (D_1, R_1)$. Let $G_A$ and $G_M$ select rows of $G$ in those orders. Any $k$ codeword rows determine $X$, so one decode determines both missing rows:

$$\begin{bmatrix} D_1 \\ R_1 \end{bmatrix} = G_M G_A^{-1} \begin{bmatrix} D_0 \\ D_2 \\ R_0 \end{bmatrix}.$$

The old decoder returned only $D_1$. Verification then rebuilt the original vector and ran the encoder:

$$\begin{bmatrix} R_0 \\ R_1 \end{bmatrix} = P \begin{bmatrix} D_0 \\ D_1 \\ D_2 \end{bmatrix},$$

That re-encode repeated the expensive codeword transform to materialize canonical $R_1$. Decoding had already evaluated the $R_1$ position. Let $W_j$ be the intermediate value at a missing position $j$ after the IFFT, formal derivative, and FFT. The canonical codeword value differs only by the known erasure-locator scale $\lambda_j$:

$$C_j = \lambda_j^{-1} W_j.$$

Previously, this unscale was applied only to missing originals. Decode-reveal applies it to every symbol of each missing recovery shard, then normalizes a partial final 64-byte batch. Algebraically, revealing $r$ missing recovery shards of $q$ symbols each adds $rq$ field multiplications. Because the arithmetic runs in 32-symbol batches, the implementation touches

$$r \cdot 32\left\lceil \frac{q}{32} \right\rceil$$

lanes, including final-block padding. Re-encoding would instead rerun the encoder’s IFFT/FFT pipeline across every symbol column to recompute all $m$ recovery shards.

The recovery path now feeds exactly $k$ shards to the decoder. If more arrive, surplus recovery shards are treated as missing and reconstructed too. Let $\rho$ be the committed root of the binary Merkle tree (BMT). The acceptance condition is unchanged:

$$\operatorname{BMT}\!\left(H(C_0), \ldots, H(C_{k+m-1})\right) \stackrel{?}{=} \rho.$$

Checked positions reuse their verified digests, while reconstructed positions are hashed before the tree is rebuilt. We skip the encode, not the verification.

When the supplied set contains all $k$ original shards, no inverse decode runs and there are no hidden recovery rows to reveal. That path still computes $R = PX$.

The block itself only needs the missing originals. Missing recovery positions matter here because decode also verifies the commitment: rebuilding the BMT root requires a digest at every shard position.

Revealed recovery shards are byte-identical to the encoder’s output, including shard widths that are not 64-byte aligned.

Running the recovery-heavy benchmark first with striping alone and then with decode-reveal isolates the improvement:

These measurements cover the entire recovery-heavy verification path, not just the transforms themselves.

The final pull request combines striping with decode-reveal:

Finding Bugs (and Bottlenecks?)

Sunghyeon used QED’s research agent to find this optimization. The agent read the coding stack and noticed that hashing the missing shards in decode was parallelized, but Reed-Solomon recovery was not. It then tested whether recovery could be split into independent stripes and run in parallel.

The loop resembles the one QED uses for security audits. It scans the code, gathers repository evidence, forms hypotheses, and verifies them with tests and benchmarks. Repository context separates a useful finding from a known issue or an intentional design choice. QED had built that context by continuously auditing Commonware.

Tuning to the Limit

It is more practical than ever to tune low-level primitives to run at the limits of modern hardware. We are continuing to invest in low-level tuning across the Commonware Library, from our recent SHA-256 optimizations to ongoing work on faster Ed25519 signature verification.