Erasure Coding in Go

A from-scratch implementation of Reed-Solomon Erasure Coding in Go, using Cauchy matrices over Galois Field $GF(2^8)$. This project demonstrates how data can be split into $K$ data shards and $M$ parity shards, allowing full reconstruction from any $K$ of the $N = K + M$ total shards.

This implementation specifically defaults to a 5-of-9 configuration (5 data shards, 4 parity shards), similar to how distributed storage systems like Amazon S3 or MinIO handle data redundancy, though those systems often use larger parameters.

Features

• Galois Field Arithmetic: Complete implementation of $GF(2^8)$ arithmetic (addition, subtraction, multiplication, and division) using lookup tables for performance.
• Cauchy Matrix Construction: Uses Cauchy matrices to ensure that any $K \times K$ submatrix is invertible, which is a requirement for Reed-Solomon coding.
• Matrix Inversion: Gaussian elimination with partial pivoting in $GF(2^8)$.
• Flexible Sharding: Encodes data into $K$ data shards and $M$ parity shards.
• Data Reconstruction: Recovers the original data as long as at least $K$ shards are available.
• Interactive CLI: Includes a built-in demo and support for custom messages or files.

How it Works

1. Encoding: The original data is split into $K$ equal-sized blocks (shards). If the data size isn't a multiple of $K$, it is padded. These $K$ blocks are then used to generate $M$ parity blocks using a generator matrix.
2. Storage: The total $N = K + M$ shards can be stored on different nodes/drives.
3. Loss: If up to $M$ shards are lost or corrupted, the data is still safe.
4. Decoding: By picking any $K$ available shards and using the inverse of the corresponding generator submatrix, the original $K$ data shards are reconstructed.

Getting Started

Prerequisites

• Go 1.21 or later.

Installation

git clone https://github.com/Avik-creator/easure-coding.git
cd easure-coding

Usage

Run the built-in demo to see encoding and reconstruction in action:

go run main.go

The demo will:

1. Encode a sample message into 9 shards (5 data + 4 parity).
2. Simulate the loss of 4 random shards.
3. Successfully reconstruct the original message from the remaining 5 shards.

Custom Message

To encode your own message:

go run main.go -msg "Hello, Erasure Coding!"

File Processing

To test with a file:

go run main.go -file yourfile.txt

Example Output

╔═══════════════════════════════════════════════════════╗
║       S3-Style Erasure Coding Demo (5-of-9 RS)        ║
║   Reed-Solomon over GF(2^8) — implemented from scratch ║
╚═══════════════════════════════════════════════════════╝

━━━  SIMULATED LOSS TEST (4 SHARDS GONE)  ━━━

  Original data (431 bytes): "The quick brown fox jumps over the lazy dog..."

  Step 1 — Encode into 9 shards (5 data + 4 parity)
  Encoded in 150µs

  Shard        Type       Status      First 8 bytes (hex)
  ──────────────────────────────────────────────────────────
  [ 0]         DATA       ✓ OK        5468652071756963
  [ 1]         DATA       ✗ LOST      —
  [ 2]         DATA       ✓ OK        6f76657220746865
  [ 3]         DATA       ✗ LOST      —
  [ 4]         DATA       ✓ OK        2e204a757374206c
  [ 5]         PARITY     ✗ LOST      —
  [ 6]         PARITY     ✓ OK        a3f210bc4e5a2109
  [ 7]         PARITY     ✗ LOST      —
  [ 8]         PARITY     ✓ OK        1234abcd5678ef00

  Step 2 — Simulate loss of 4 shard(s): [1 3 5 7]

  Step 3 — Reconstruct from remaining shards
  ✓ Reconstruction SUCCESS in 250µs
  Recovered: "The quick brown fox jumps over the lazy dog..."

License

MIT