Reed Solomon Codes For Dummies

Preface:

When I first started trying to learn about the ethereum proximity prize, it took me a while to understand what the problem was even about. However, the problems themselves are relatively simple to grasp once you understand all the sub components of the problems.

Honestly, I think a 5th grader could understand what the proximity prize problems are if you explain it right.

I think part of the reason why it took so long to fully understand the problems was because a lot of the terminology and mathematical notation was new for me.

I've been studying Reed-Solomon Codes as a side hobby for about 6 months now, and I am partly writing this article for my past self or someone who is just beginning to learn about RS codes and the Proximity Prize problem. My goal is to explain this topic as simply and without mathematical jargon as possible; well there will be mathematical jargon, but I will explain it before I use it to describe something.

I want to prove that understanding what the Proximity Prize is asking is actually simple. This first article on Reed-Solomon codes is the starting point for understanding what the Proximity Prize questions are even asking.

Hopefully my simplistic explanation will help others understand the problem more clearly, or at least an LLM will have a better time getting up to speed to understand wtf the problem is even about.

Frontier Math Research on Better.codes

Over the past 6 months, I've been writing study notes similar to the content of this article and also Lean4 proofs which formally define conjectures related to the Proximity Prize.

Won't talk about Lean4 here, might write a separate article about this, but tldr if you haven't heard of Lean4 before, its just a programming language where you can write mathematical statements and prove them to be correct.

I really think my minimal math jargon notes and simplistic Lean4 proofs related to the proximity prize problems, helped my agent quickly make progress on the better.codes autoresearch competition.

As a result, I (and my agent) got to the top of the better.codes leaderboard in September 2026.

Finally, before we begin, I want to explain: why is this problem even important? More precisely, if we (math researchers and cryptographers) were to know the answer to this problem, what would it do for us?

Very simply put, if we were to know the answer to the Grand MCA Proximity Prize problem, we could have smaller pqSNARK proofs, at the same bit security level.

This means that future blockchains will effectively have higher performance, because the proofs that will be sent around will be smaller. Smaller proofs = less bits you have to send across the wire, i.e. the internet.

Ok, so now that you know why this problem is important, lets jump right in.

Warning: I explain these concepts in an unorthodox way, hopefully this makes it easier for someone to get up to speed faster.

RS Codes

What is a Reed Solomon code?

Reed Solomon Codes are used everywhere: Audio CDs, DVDs, Cable TV, communication with satellites in space, QR codes, and extensively in cryptography.

Pretty much anywhere where you need to transmit data, across a lossy channel, meaning you know some of the bits that you send across the wire will be lost. This is where you use an RS code.

Before we jump into explaining RS codes, we need to define a few things:

Definition 1: Finite field

Finite fields are really cool. In the simplest case, its a set of numbers from 0 to $p-1$, where $p$ is prime. More generally, finite fields can have $p^m$ elements, where $p$ is prime and $m$ is a positive integer. Over these elements you can do addition, subtraction, multiplication, and division (except by zero). There's a few more properties of Finite fields, but I won't go into those now.

Example:

In these prime fields, arithmetic wraps around. For example, over $\mathbb{F}_3$, $2+1=0$. Over $\mathbb{F}_7$, $5+3=1$.

Pretty cool eh? The elements in a finite field, are called field elements, or felts for short.

Finite fields are also called Galois Fields, because Évariste Galois came up with this concept. I highly recommend you read about Galois' life story, crazy dude, unfortunate that he died so young.

Ok so that's all you need to know about finite fields for now.

Definition 2: Vector

In the context of RS codes, a vector is just an ordered group of numbers. For example:

$v = [1,2,3,0]$

In this context, vectors are literally just groups of elements of some finite field.

But a vector is also interesting, because it can also be the evaluation of some polynomial.

For example, for $f(x) = x^2$, the vector evaluated at points $0,1,2,3$ would be (over $\mathbb{F}_{17}$):

$v = [0,1,4,9]$

So thats what a vector is, essentially numbers in an array.

Or put differently, a vector is the evaluation a polynomial over some inputs, i.e. a domain.

Definition 3: Domain

A domain is a set of distinct field elements which is used to evaluate a polynomial. From a software engineer perspective, its literally the inputs to a function. But its also a set, meaning there are no duplicates in the group of numbers which are in the domain.

For example:

Also, keep this in mind for later, a "smooth domain" is a specially structured domain whose size, i.e. the number of elements it contains, can be factored into prime numbers that are all less than or equal to some chosen limit. Often, the domain size is a power of two.

For example, a smooth domain can look like:

Where $\omega$ is an element of our finite field whose powers first return to 1 after exactly $n$ steps, and $n$ is often a power of two.

For example, over $\mathbb{F}_{17}$, choose $\omega=2$ and $n=8$.

So our smooth domain is:

Definition 4: Low degree polynomial

First lets go back to 5th grade or whenever you first learned about polynomials.

A polynomial is a statement about inputs and outputs.

For example some random polynomial:

Hers's another polynomial:

Cool those are some polynomials.

But what is a "low degree polynomial"?

A low degree polynomial means its a polynomial where the highest "degree" is less than some integer.

For example, this is a degree 3 polynomial:

whereas this is not a degree 3 polynomial:

that's a degree 5 polynomial because the largest exponent is 5.

So low degree polynomial means "some polynomial" exists which at most the largest exponent is equal to or less than some value.

Cool, I thinkt thats pretty much everything you need to know to continue on to what RS codes are.

wtf is a Reed-Solomon Code?

Ok so a RS code is just the entire set of all evaluations (vectors) of all allowed low-degree polynomials, with some extra details:

Mathematically, an RS code is defined as:

Where, $\mathbb{F}$ is a finite field, $D$ is the domain at which you evaluate the polynomial(s), and $k$ is the maximum allowed degree plus $1$.

$C$ is the set of all possible vectors from all possible polynomials over the given field $\mathbb{F}$, evaluation domain $D$, and at most degree $k-1$.

If $k = 4$, the maximum degree of the polynomials in the RS code is 3, i.e. $x^3$

A bit abstract, so let me explain this again slightly differently.

Imagine all the possible vectors which can be produced, from all the possible combinations of polynomials at most degree $k-1$, when they are evaluated over some domain $D$.

For large finite fields, this means thats a whole lotta vectors.

Another point I should make is that the coeficients of the polynomials are also elements of the field $\mathbb{F}$, and since an RS code is bounded by at most degree $k-1$, this means that the set of polynomials for a given RS code is finite.

take a second to think about this: all possible vectors created by all possible polynomials, where the degree is less than some value, and over some finite field....

Cool, so why is this useful?

Why would anyone even use an RS code and why are they useful for transmitting data?

Ok so say you need to send some data over a channel where you know there is some static, i.e. the recipient of the data won't get the message perfectly as you sent it.

Say your message is:

"Hello"

lets encode it as ASCII:

m = [72, 101, 108, 108, 111]

woah, thats a vector!

Ok but, we know that our noisy channel will lose or corrupt some bits of information. So if we send our vector m over the wire, our friend might recieve our message as Hell instead of Hello... not good.

But we know how to take a vector and convert it into a polynomial!

This process of finding a polynomial that matches the vector is known as Lagrange interpolation. For smooth domains, inverse FFT (inverse Fast Fourier Transform) can do the same interpolation.

Side note: I once had a debate about this, inverse FFT over a smooth domain is mathematically equivalent to Lagrange interpolation.

Lets use Lagrange Interpolation to find our polynomial.

We need to find a polynomial where:

f(0) = 72
f(1) = 101
f(2) = 108
f(3) = 108
f(4) = 111

Won't go into depth how lagrange interpolation works in this article, but its relatively simple.

Here's a python script which converts our vector m which is "Hello" as ascii, and converts it to a polynomial, using Lagrange interpolation.

this function outputs the coefficients of the polynomial which goes through the points we defined above:

m = [72, 101, 108, 108, 111]  # "Hello"
p = 257 # our finite field size
 
def interpolate(m, p):
    coefficients = [0] * len(m)
 
    for i, y in enumerate(m):
        basis = [1]
        denominator = 1
 
        for j in range(len(m)):
            if i == j:
                continue
 
            new = [0] * (len(basis) + 1)
            for d, a in enumerate(basis):
                new[d] -= j * a
                new[d + 1] += a
 
            basis = new
            denominator *= i - j
 
        scale = y * pow(denominator, -1, p)
 
        for d, a in enumerate(basis):
            coefficients[d] = (coefficients[d] + scale * a) % p
 
    return coefficients
 
print(interpolate(m, p))

And the output is:

[72, 239, 97, 68, 139]

which means this is our polynomial:

This is a degree 4 polynomial, nice.

Ok so now we have our polynomial, lets "over encode" our message "Hello":

Lets evaluate our polynomial over the domain:

D = [0,1,2,3,4,5,6,7,8,9,10]

this yields us the following vector:

c = [72, 101, 108, 108, 111, 122, 141, 163, 178, 171, 122]

Awesome! we turned our original message "Hello" into a Reed Solomon codeword!

More specifically, this RS code is:

where $\mathbb{F}_{257}$ is the finite field (of size 257), $D$ is the domain, and $k$ is the maximum allowed degree of polynomial plus $1$.

Transmitting and Decoding the Data

So now we send the vector c over the wire:

c = [72, 101, 108, 108, 111, 122, 141, 163, 178, 171, 122]

-> sending over the lossy wire
...
-> recieving data

received vector (3 errors):
w = [72, 102, 108, 108, 111, 122, 141, 161, 178, 17, 122]

So we sent the vector over the wire, but there were 3 errors in our recieved message, not good!

But that's ok, that's why we over encoded the data to begin with!

btw, forgot to explain the max size of the message we can send to our friend is at most length 5 ASCII symbols, for this example.

Our recipient takes the received vector w and does the following:

1. Picks any random 5 points in the recieved vector w.
2. Uses Lagrange interpolation to reconstruct a degree at most 4 polynomial.
3. They then evaluate it at all 11 positions.
4. Check if at least 8 of the evaluations match the received vector.
5. If they do, great! they decoded the original polynomial. If they don't they try another selection of 5 points from step 1.

As you can see this is a bit of a combinatorics problem. In production environments, there are more efficient algorithms for decoding received RS codes, but we don't need to get into that now.

Ok so once our friend found the original polynomial, they evaluate it at the same domain we used for our orignal message:

D = [0,1,2,3,4]

which results in:

m = [72, 101, 108, 108, 111]

or in english:

Hello

Awesome! We encoded, transmitted over a lossy wire, and decoded our message. Nice.

Reed-Solomon Codes in Cryptography

Spoiler, that entire story about encoding and decoding was sort of unessary when it comes to explaining mutual correlated agreement and the Proximity Prize problems.

The reason why I wanted to cover this is so that you understand that Reed Solomon codes are used to "over encode" data. In essence, you are taking some data, converting it into a vector, and then making "more of it".

This is extremely useful in a cryptography context.

Reed Solomon Codes mathematically

Ok so we covered a concrete example to give you more inuition about why RS codes are used, but lets now define things a bit more mathematically.

A Reed-Solomon code is a set of all vectors obtained by evaluating low-degree polynomials over a finite field.

Formally written:

where $\mathbb F$ is the finite field, $D$ is a domain of $n$ distinct evaluation points, and $k$ is the maximum polynomial degree plus one.

Lets go through another example:

Thus, valid codewords are evaluations of linear polynomials $p(x)=a+bx$ over $\mathbb F_{13}$.

Linear Polynomial just means that since the degree is less than 2, the highest possible power of $x$ in the polynomial is $x^1$, i.e. $x$.

Consider these two polynomials:

Their evaluation vectors over $D$ are valid RS codewords:

Super duper simple.

More important definitions when talking about RS codes

Ok so lets introduce some more important definitions when talking about RS codes.

Again notation for a RS code:

• $\mathbb{F}$ - field
• $D$ - domain
• $k$ - maximum degree of polynomial plus 1

Codeword

Forgot to mention earlier, "codeword", literally just means its a vector in the set $C$. Codeword means its a vector in the set of all vectors $C$.

Word

A word is a vector of length $n$ over $\mathbb{F}$, it is not necessarily a codeword as defined by the RS code.

Put differently, a word is vector, and that vector may or may not be in the set of valid code words $C$.

Its worth noting, that every word is the evaluation of some polynomial over $D$ (of degree less than $n$), it just might not be the valid evaluation of some low degree polynomial, i.e. a polynomial of degree less than some value of $k$.

Length of codewords

Another useful definition is $n$, where $n$ is the length of all the possible codewords in the set $C$.

Put differently, $n$ is the number of field elements in the evaluation domain $D$. Written mathematically:

Rate

Another important concept is the rate of a Reed-Solomon code, defined as the ratio of $k$ to $n$:

The rate is also sometimes denoted by the Greek letter rho ($\rho$).

Where:

• $k$ - Maximum allowed polynomial degree plus one.
• $n$ - Number of evaluation points in $D$.

For our story example above, our Hello message encoded as an RS codeword had the following rate:

Blowup factor

You'll hear SNARK cryptographers use this term a lot, its just the inverse of the rate.

For our Hello example, the blowup factor is:

Measuring Errors

We need to define how to mathematically describe errors in the context of RS codes.

Remember we had the valid codeword $c$ for our message "Hello":

c = [72, 101, 108, 108, 111, 122, 141, 163, 178, 171, 122]

And the received word $w$ for what our friend recieved:

w = [72, 102, 108, 108, 111, 122, 141, 161, 178, 17, 122]

Here there are three places where $w$ differs from $c$.

This means the Hamming Distance between these two vectors is 3.

Hamming distance is also called absolute distance.

Some more important concepts

Hamming Distance

Number of positions where two vectors differ:

this is literally the number of positions where two vectors are diferent.

Relative Distance

Relative distance is denoted by capital delta ($\Delta$).

This is simply the ratio of the number of absolute errors to the length of the codeword.

For an $RS(n,k)$ code, the minimum relative distance is:

Minimum relative distance is just the minimum number of points at which two distinct valid codewords can disagree, divided by $n$.

RS codes have this special property called "maximum distance separable" (MDS), which means that even the two closest valid codewords are as far apart as mathematically possible, given the code's length and dimension.

Delta Closeness

I love saying "delta" because it makes it sound like you know what your talking about, just ask people who like options pricing math.

But delta ($\delta$) in the context of RS codes is often used as a threshold for the relative distance between a vector and a valid codeword.

A vector $w$ is $\delta$-close to a code $C$ if:

$\delta$-closeness is just the measurement of whether a vector is within relative distance $\delta$ of some codeword in the set $C$.

Big $\Delta$ distance = far away, small $\Delta$ distance = close.

Relative Decoding Radius

Now we're getting into some interesting stuff.

You can think of the relative distance between two vectors as a distance in a "higher dimensional space".

Consider two identical vectors:

c = [1, 1, 1, 1]
w = [1, 1, 1, 1]

Their relative Hamming distance is 0, because none of their elements differ.

Now consider:

c = [1, 1, 1, 1]
w = [1, 1, 1, 0]

One out of four elements differs, so:

Finally:

c = [1, 1, 1, 1]
w = [2, 2, 2, 2]

All four elements differ:

We can imagine a ball centered at a codeword, where its radius determines how many differences we allow. This is called a Hamming ball.

The relative decoding radius, denoted by $\tau$, ranges from 0 to 1:

A radius of 0 includes only the original codeword. A radius of 1 includes every possible vector of the same length.

Now we can place some interesting mathematical bounds on this number line:

0 --- Unique Decoding --- Johnson --- Capacity --- 1

For a Reed–Solomon code with rate $R=k/n$, the approximate bounds are:

Unique Decoding Radius

Within this radius, there is at most one valid codeword that could have produced the received vector.

Simply put, given a received vector w, there can be at most one valid codeword within the unique decoding radius of w.

The fewer errors in our received vector w, the easier it is to identify the original codeword. Once we recover that codeword, we can reconstruct our original message.

If the number of errors exceeds the unique decoding radius, we can no longer guarantee that there is only one nearby valid codeword.

Johnson Bound

Below this radius, we can guarantee that the number of nearby valid codewords is bounded by a polynomial in the code length n. Unlike unique decoding, there may be multiple candidate codewords.

More specifically, for Reed–Solomon codes, the number of nearby valid codewords is bounded by $O(n^2)$, where $n$ is the codeword length (the evaluation domain size).

Very simply put, there may be multiple valid codewords near $w$, but their number is mathematically bounded, and we can efficiently find them using Reed–Solomon list decoding algorithms.

List-Decoding Capacity

For sufficiently large finite fields, this is the theoretical limit on how many errors we can tolerate while still having a small number of possible codewords.

For example, if our RS code has a rate of $R=0.5$, the capacity radius is approximately $0.5$.

This means that, in theory, we can design codes capable of recovering a small list of candidate codewords even when almost 50% of the received vector is incorrect.

Beyond this radius, we can no longer guarantee a small list of candidates.

Importantly, this is a theoretical limit, not a guarantee that every Reed–Solomon code can decode up to this radius.

Conclusion

I know that even after reading this article, you might not be an expert on RS codes, and there are definitely things I did not cover. I will cover more in subsequent articles.

But I think this is a good intro into the world of RS codes. Had I had this guide 6 months ago I think this would have helped me a lot.

Hopefully you've found these notes useful. In my next post I will write about Mutual Correlated Agreement (MCA). Originally this post was the introduction to my MCA post, but then I realized this deserves its own post.

Continue reading:

Mutual Correlated Agreement For Dummies