Introduction

Disks die. Servers catch fire. Whole data centers go dark. So if your file matters, you keep more than one copy. The brute-force answer is replication: store the file three times, and you can lose any two copies and still be fine. Simple — but you now pay for three times the storage to protect one file.

Erasure coding does dramatically better. Instead of copying the file, it transforms it into n pieces — called shards — with a magic property: any k of them are enough to reconstruct the original, and the other n−kn - k can vanish. Pick n = 6, k = 4 and you survive any two lost shards while paying only 1.5× the storage, not 3×.

How can fragments you've never seen rebuild data they don't literally contain? The answer is a piece of mathematics that quietly runs underneath your CDs, QR codes, hard-drive arrays and cloud buckets.

Try It: Lose Shards, Rebuild Anyway

Below, a secret value is encoded into 6 shards so that any 4 can rebuild it. Click shards to "destroy" them, then press Rebuild and watch the original reappear — or fail when too few survive.

<p class="hint">A secret value is encoded into <b>6 shards</b> using a degree-3 polynomial. <b>Any 4</b> shards can rebuild it. Click shards to destroy them, then press <b>Rebuild</b>. With 4 or more survivors it always works — with 3 or fewer it is mathematically impossible.</p>
<div class="secret">Secret value: <span id="secret">?</span></div>
<div id="shards" class="shards"></div>
<div class="status" id="status">6 of 6 shards alive — any 4 suffice.</div>
<div class="btns">
  <button id="rebuild" type="button">Rebuild from survivors</button>
  <button id="reset" type="button" class="ghost">New secret</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.secret { font-size: 1rem; font-weight: 600; margin: .3rem 0 .6rem; }
.secret span { font-family: ui-monospace, monospace; color: #1d3557; }
.shards { display: grid; grid-template-columns: repeat(6, 1fr); gap: 8px; margin: .5rem 0; }
.shard { padding: .6rem .3rem; border-radius: 10px; text-align: center; cursor: pointer;
         user-select: none; border: 2px solid #cdd9e3; background: #e8eef3; transition: all .12s; }
.shard:hover { border-color: #1d3557; }
.shard .lbl { font-size: .72rem; color: #57708a; }
.shard .val { font: 700 16px ui-monospace, monospace; color: #1d3557; margin-top: 2px; }
.shard.dead { background: #f3d6d9; border-color: #e0a4ab; opacity: .55; }
.shard.dead .val, .shard.dead .lbl { color: #b03a46; text-decoration: line-through; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Reed-Solomon-style erasure coding (over rationals for a clear visual):
//   secret S is the value at x=0 of a degree k-1 = 3 polynomial f.
//   The 6 shards are f(1)..f(6). Any k=4 of them uniquely fix f (interpolation),
//   so f(0)=S is recovered. With <4 survivors, infinitely many curves fit -> impossible.
const N = 6, K = 4;       // n shards, any k recover
const XS = [1,2,3,4,5,6]; // evaluation points for the shards
let coeffs = [];          // [a0(=secret), a1, a2, a3], f(x)=a0+a1 x+a2 x^2+a3 x^3
let shardVals = [];       // f(x) for x in XS
const dead = new Set();   // indices (0..5) of destroyed shards

function feval(c, x){ let r=0; for(let i=c.length-1;i>=0;i--) r=r*x+c[i]; return r; }

// Lagrange interpolation: recover f(0) from the surviving (x, y) points.
function recoverSecret(points){
  let s=0;
  for(let i=0;i<points.length;i++){
    let [xi,yi]=points[i], term=yi;
    for(let j=0;j<points.length;j++){ if(j===i) continue;
      const xj=points[j][0]; term *= (0 - xj)/(xi - xj); }
    s += term;
  }
  return Math.round(s);
}

function newSecret(){
  coeffs = [Math.floor(Math.random()*90)+10]; // secret 10..99
  for(let i=1;i<K;i++) coeffs.push(Math.floor(Math.random()*9)-4); // small coeffs
  shardVals = XS.map(x => feval(coeffs, x));
  dead.clear();
  document.getElementById('secret').textContent='?';
  render(); setStatus(fmt('%N% of %N% shards alive — any %K% suffice.', { N: N, K: K }),'');
}

function render(){
  const wrap=document.getElementById('shards'); wrap.innerHTML='';
  XS.forEach((x,i)=>{
    const d=document.createElement('div');
    d.className='shard'+(dead.has(i)?' dead':'');
    d.innerHTML=fmt('<div class="lbl">shard %i%%v% (x=%x%)</div><div class="val">%v2%</div>', { i: i, v: 1, x: x, v2: shardVals[i] });
    d.addEventListener('click',()=>{ dead.has(i)?dead.delete(i):dead.add(i);
      document.getElementById('secret').textContent='?'; render(); statusForAlive(); });
    wrap.appendChild(d);
  });
}
function alive(){ return XS.length - dead.size; }
function statusForAlive(){ const a=alive();
  setStatus(fmt('%a% of %N% shards alive — %v%', { a: a, N: N, v: a>=K?'enough to rebuild.':'NOT enough (need '+K+').' }), a>=K?'':'bad'); }
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function rebuild(){
  const pts=[]; XS.forEach((x,i)=>{ if(!dead.has(i)) pts.push([x, shardVals[i]]); });
  if(pts.length < K){
    document.getElementById('secret').textContent='✗ lost';
    setStatus(fmt('Only %length% shards left — need %K%. Data is unrecoverable.', { length: pts.length, K: K }),'bad'); return;
  }
  const s=recoverSecret(pts.slice(0,K)); // any K survivors give the same answer
  document.getElementById('secret').textContent=s;
  const ok = s===coeffs[0];
  setStatus(ok ? fmt('✓ Rebuilt the secret from %length% surviving shards!', { length: pts.length }) :
                 'unexpected mismatch', ok?'ok':'bad');
  console.log('secret', coeffs[0], 'recovered', s, 'from', pts.length, 'shards');
}

document.getElementById('rebuild').addEventListener('click',rebuild);
document.getElementById('reset').addEventListener('click',newSecret);
newSecret();
Result
Console

The trick is that the shards are points on a polynomial. Four points uniquely fix a degree-3 curve, so any four of the six points recover the same curve — and reading its value at x = 0 gives back the original data. Knock out three or more shards and only ≤3\le 3 points remain: infinitely many curves pass through them, so reconstruction becomes impossible. That sharp kk-point threshold is exactly what makes Reed-Solomon codes so reliable.

The Real Complexity

Erasure coding is a rare happy story in this site: the problem is solved, optimally, and efficiently.

  • The construction. The classic scheme is the Reed-Solomon code, introduced by Irving Reed and Gustave Solomon in 1960. Treat the data as the coefficients of a polynomial of degree k−1k - 1, then evaluate it at nn distinct points. Those nn values are the shards.
  • Why any k suffice. A degree k−1k - 1 polynomial is uniquely determined by any k of its values (polynomial interpolation). So any kk surviving shards rebuild the exact polynomial, and with it the original data — the missing n−kn - k are irrelevant.
  • It's provably optimal. Reed-Solomon codes are MDS (Maximum Distance Separable): they meet the Singleton bound, the information-theoretic limit. You cannot tolerate n−kn - k losses with fewer than kk survivors — no code can do better, and Reed-Solomon hits the line exactly.
  • And it's efficient. Encoding and decoding are matrix/polynomial operations over a finite field — fast, deterministic polynomial-time algorithms, not a brute-force search.

So unlike the P vs NP hard problems elsewhere on this site, erasure coding sits in the comfortable corner: the optimum is known, achievable, and cheap to compute.

Where It Matters

"Survive losses without paying for full copies" is one of the most valuable guarantees in computing, and erasure coding delivers it everywhere:

  • Cloud object storage: systems like Azure Storage, Facebook's HDFS and Ceph store data as nn-of-kk shards across machines and racks, cutting durability overhead from 200% (3× replication) to ~50%.
  • RAID arrays: RAID 6 is small-scale erasure coding — two parity shards let any two disks in an array fail without data loss.
  • CDs, DVDs and QR codes: Reed-Solomon error correction is why a scratched disc still plays and a partially obscured QR code still scans.
  • Deep-space communication: NASA missions code their telemetry so the data survives the noise of an interplanetary radio link, where retransmission is impossibly slow.

The same polynomial idea also shows up in error correction — see Hamming codes and Reed-Solomon codes for the closely related task of fixing bit errors rather than recovering lost shards.

Conclusion

Erasure coding takes the crude idea of "keep extra copies" and replaces it with something far more elegant: scatter your file into nn mathematically intertwined shards, and any kk of them rebuild the whole — no matter which kk. The redundancy is spread thin and used to the theoretical limit.

It is one of the satisfying results in this collection: a problem that is completely solved, with a construction that is both optimal (it meets the Singleton bound) and efficient (polynomial-time encode and decode). The next time a disk dies in a data center and nobody notices, thank a 1960 polynomial — and the quiet certainty that any kk survivors are all you ever needed.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/erasure-coding/Content licensed under CC BY-NC 4.0.