Mutual Correlated Agreement (MCA) for Dummies

Preface:

When I first started trying to learn what MCA was, I didn't get it. I think it took me about 2 weeks to fully understand what MCA actually was, even though its actually really simple and could probably be explained in 10 minutes. I think a 5th grader could understand what MCA is.

I think part of the reason why it took so long for MCA to "click" was because a lot of the terminology 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.

This article is called Mutual Correlated Agreement (MCA) for Dummies because I want to make MCA as simple as possible to understand.

My goal is to explain this topic as simply and without mathematical jargon as possible; well, there will be mathematical jargon but I will at least explain it before I use it to describe something.

I want to prove that understanding what the Proximity Prize Problems are even asking is actually simple. 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.

getting on the better.codes leaderboard:

Over the course of the past ~6 months, I've been writing study notes and lean4 proofs to better understand the Proximity Prize problems.

I really think my no math jargon notes and proofs 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 as a coauthor.

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: some mathematicians might not like how I explain this, but I'm quite certain the math is correct, I might just be explaining it in an unorthodox way.

WARNING!

I use math jargon below, please read my other article Titled Reed Solomon Codes for Dummies if you are not familiar with RS codes yet.

Read this article first, if you're still an RS code dummy.

If you're not an RS Code dummy anymore you can continue ;)

Prerequisite Definitions

Before we jump into explaining Mutual Correlated Agreement, we need to lay out some definitions.

Definition 1: Random Linear Combination

A random linear combination is the process of adding two vectors together, where one of the vectors is multiplied by some value, alpha.

Let's first consider two arbitrary vectors $f,g\in\mathbb F_{17}^{8}$ , using the RS code:

C=\operatorname{RS}[\mathbb F_{17},D,2],\qquad D=\{1,2,4,8,16,15,13,9\}.

So our field has $17$ elements, our domain has $n=8$ evaluation points, and our codewords are evaluations of linear polynomials (since $k=2$ , largest degree of $x$ , is $x^1$ ). We'll write the vector entries in the same order as the points in $D$ .

\begin{aligned} f&=[1,2,4,8,\mathbf 1,15,13,9],\\ g&=[0,0,0,0,\mathbf 5,0,0,0]. \end{aligned}

Neither $f$ nor $g$ is a valid codeword for this RS code. For example, $f$ differs from the valid codeword for $p(x)=x$ at the domain point $x=16$ , and $g$ is nonzero only at that point.

Now we randomly sample some field element alpha and form the following statement:

\boxed{h_\alpha=f+\alpha g.}

In english, this is: "h alpha is equal to f plus alpha times g".

Simply put, we multiply all elements in vector $g$ by $\alpha$ , then add $f$ to $\alpha$ * $g$ , (all modulo $17$ ).

For the particular sample $\alpha=3$ ,

\begin{aligned} h=h_3&=f+3g\pmod{17}\\ &=[1,2,4,8,16,15,13,9]. \end{aligned}

So $h$ is the "random linear combination" of $f + 3g$ .

Here's an image of the same thing above:

Vectors f and g combine as h = f + 3g modulo 17, changing the fifth entry from 1 to 16 and producing a valid Reed-Solomon codeword. — Figure 1. The random linear combination $h=f+\alpha g$ with $\alpha=3$ over $\mathbb F_{17}$ . Select the image to view it at full size.

Something interesting I want to point out: even if $f$ and $g$ are not codewords for a given RS code, their random linear combination potentially could be.

Lemme say that again:

It is possible that the random linear combination of $f$ and $g$ , with some random $\alpha$ , results in $h$ being a valid codeword.

This is exactly what happened in the example above. Our $h_3$ is the valid codeword for $p(x)=x$ , even though neither $f$ nor $g$ is a codeword.

For fixed non codewords $f$ and $g$ , the probability of this happening is at most $1/|\mathbb F|$ . More precisely, the probability is not always $1/|\mathbb F|$ ; it can also be zero. For two distinct values of alpha to both produce codewords, $f$ and $g$ would already have to be codewords themselves.

For these particular vectors, it happens only when $\alpha=3$ , so the probability is exactly $1/17$ .

Definition 2: Agreement Set

But, even if the result of a random linear combination of two non codeword vectors, $h$ , is not a valid codeword, it might be close to one.

Put another way, if $h$ is not a valid codeword, it may agree with a codeword at some evaluation points.

Let's use another pair of vectors, but keep the exact same RS code $C=\operatorname{RS}[\mathbb F_{17},D,2]$ :

\begin{aligned} f&=[0,0,0,0,0,0,15,14],\\ g&=[0,0,0,0,0,0,1,1]. \end{aligned}

Again, neither $f$ nor $g$ is a valid codeword.

We compute their random linear combination $h$ where alpha is $2$ :

\boxed{h_2=f+2g.}

This results in the vector $h$ which is not a valid codeword:

h_2=[0,0,0,0,0,0,0,16].

However, it is close to the valid codeword $c$ , which is simply the zero polynomial evaluated over $D$ :

c=[0,0,0,0,0,0,0,0].

The vector $h_2$ is $1/8$ -close to $c$ . Or put differently, their Hamming distance is $1$ .

The vectors $h_2$ and $c$ overlap at all points except one. They disagree at the last position, which corresponds to the domain point $x=9$ .

We call the matching domain points the agreement set:

S=\{x\in D:h_2(x)=c(x)\}.

Or in this case the set $S$ is:

S=D\setminus\{9\}=\{1,2,4,8,16,15,13\}.

The agreement set is a subset of the evaluation domain $D$ .

$S$ contains the evaluation points where the two vectors agree, not the values of those vectors.

Put mathematically, $S\subseteq D$ , meaning $S$ is a subset of $D$ .

The vector h with alpha 2 agrees with the zero codeword at seven positions. Only the last position, x7 = 9, differs: 16 versus 0. — Figure 2. $h_2$ agrees with the valid codeword $c$ at 7 of 8 evaluation points. The one mismatch is at $x=9$ , so $S=D\setminus\{9\}$ . The figure labels domain points in order as $x_0,\ldots,x_7$ ; in particular, $x_6=13$ and $x_7=9$ .

Definition 3: Restriction to a Set

Another piece of mathematical notation we need is called restriction.

The notation $f|_S$ (read as "f restricted to S") just means we only look at the values of $f$ at the evaluation points in $S$ .

For example, since $S$ contains every point in $D$ except $9$ , we get:

f|_S=[0,0,0,0,0,0,15].

And since $h_2$ and $c$ agree at every point in $S$ , we can write:

\boxed{h_2|_S=c|_S.}

"h2 restricted to S is equal to c restricted to S"

That's literally all restriction means here. We are just looking at the same vectors, but only at the positions in $S$ .

Definition 4: Sufficiently Large Set

So what does it mean when someone says the agreement set $S$ must be "sufficiently large"?

All this means is that the set must contain at least some chosen fraction of the evaluation domain:

\boxed{|S|\geq(1-\delta)n,\qquad n=|D|.}

Where $\delta$ is the maximum relative distance we're allowing.

For example, if $n=8$ and $\delta=1/4$ , then $S$ must contain at least $6$ evaluation points.

That's exactly what we have above (and more): $|S|=7$ . The threshold depends on the particular $\delta$ you're studying.

The Mutual Correlated Agreement Question

Ok so we now have enough terminology to describe MCA.

Again, MCA is a question which reduces to yes or no, true or false.

This is the question:

We produce a random linear combination $h_\alpha=f+\alpha g$ of two potentially non codeword vectors with a randomly sampled alpha.

$h_\alpha$ is delta close to some codeword $c$ . More specifically, it agrees with $c$ on some sufficiently large set $S\subseteq D$ :

h_\alpha|_S=c|_S.

Question, are there two valid codewords $u_0$ and $u_1$ which, when restricted to that same agreement set $S$ , agree with the vectors $f$ and $g$ ?

\boxed{f|_S=u_0|_S\qquad\text{and}\qquad g|_S=u_1|_S.}

If yes, excellent. For a sufficiently large $S$ with at least $k$ points, these codewords also satisfy $c=u_0+\alpha u_1$ .

If no, we have an MCA failure on that agreement set.

One important detail: for a fixed $\alpha$ , this has to work for every sufficiently large agreement set $S$ . If there is even one set where the answer is NO, that is an MCA failure.

2nd attempt at explaining wtf MCA is

We've already covered what it means when a vector is delta close to a codeword. You can say vector $w$ is $\delta$ -close to codeword $c$ over domain $D$ .

\Delta_D(w,c)\leq\delta

The domain $D$ is the evaluation set.

But we can also have this notion of closeness over some subset $S\subseteq D$ :

\Delta_S(w,c)=\frac{|\{x\in S:w(x)\neq c(x)\}|}{|S|}

So the question MCA is asking:

The random linear combination $h_\alpha=f+\alpha g$ is $\delta$ -close to some codeword $c$ . When you restrict the domain $D$ to where $h_\alpha$ and $c$ agree, we get the set $S$ .

S=\{x\in D:h_\alpha(x)=c(x)\}

Since $h_\alpha$ is $\delta$ -close to $c$ , we know:

|S|\geq(1-\delta)|D|

We can say $h_\alpha$ agrees exactly with $c$ on $S$ , mathematically:

\Delta_S(h_\alpha,c)=0

The question is, do vectors $f$ and $g$ also agree exactly on that same set $S$ with some other valid codewords $u_0$ and $u_1$ ?

\boxed{\Delta_S(f,u_0)=0\quad\text{and}\quad\Delta_S(g,u_1)=0}

If the answer is yes, amazing, if no, that's called an MCA failure event for that agreement set.

Super short explanation of MCA:

If $h_\alpha$ agrees with a codeword $c$ on a sufficiently large set $S$ , do the vectors $f$ and $g$ also agree with some valid codewords on exactly that same set $S$ ?

MCA Success Event: $\alpha=1$

Let's use the second pair of vectors, with $\alpha=1$ :

\begin{aligned} f&=[0,0,0,0,0,0,15,14],\\ g&=[0,0,0,0,0,0,1,1]. \end{aligned}

This time:

h_1=f+g=[0,0,0,0,0,0,16,15].

$h_1$ agrees with the zero codeword $c$ on:

S_0=D\setminus\{13,9\}=\{1,2,4,8,16,15\}.

That's $6$ out of $8$ points, so $|S_0|=6$ meets our threshold $\delta=1/4$ .

Now look at these two valid RS codewords, both obtained by evaluating the zero polynomial:

\begin{aligned} u_0&=[0,0,0,0,0,0,0,0],\\ u_1&=[0,0,0,0,0,0,0,0]. \end{aligned}

Both $u_0$ and $u_1$ agree with our original $f$ and $g$ on exactly the same set $S_0$ :

\boxed{f|_{S_0}=u_0|_{S_0},\qquad g|_{S_0}=u_1|_{S_0}.}

And:

c=u_0+u_1.

So, YES, this is an MCA success. Even though $f$ and $g$ are not valid codewords over the whole domain, they both agree with valid codewords on the same $6$ points.

There's no other sufficiently large agreement set with a different codeword hiding here: a nonzero linear polynomial can only be zero at one point, whereas $h_1$ is zero at the first six points.

MCA Failure Event: $\alpha=2$ or $\alpha=3$

Now here's the interesting part. We keep the same $f$ and $g$ . Let's just choose a different alpha:

\alpha=2.

We already computed:

h_2=[0,0,0,0,0,0,0,16].

$h_2$ is not a valid codeword, but it agrees with the zero codeword on 7 points:

S_2=D\setminus\{9\}=\{1,2,4,8,16,15,13\}.

But remember, $f$ and $g$ are not zero at the domain point $13$ , which belongs to this agreement set.

Could there be different valid codewords $u_0,u_1$ that agree with $f$ and $g$ on all of $S_2$ ? No. Both $f$ and $g$ are zero at the first six points. A polynomial of degree less than $2$ that is zero at six different points has to be the zero polynomial. But the zero polynomial doesn't match either vector at $13$ .

So there are no valid codewords $u_0,u_1$ satisfying:

f|_{S_2}=u_0|_{S_2},\qquad g|_{S_2}=u_1|_{S_2}.

For this agreement set, the answer is NO. That's an MCA failure event, even though $h_2$ itself is not a codeword.

MCA fails on the same agreement set: f and g are zero at six points but nonzero at x6 = 13, so neither can match a valid linear-polynomial codeword throughout S. — Figure 3. The original vectors disagree with the only possible valid codewords at the point $13$ (labeled $x_6$ ), which is inside the agreement set $S_2$ .

And it gets even more interesting. With $\alpha=3$ :

h_3=f+3g=[0,0,0,0,0,0,1,0].

Now it agrees with the zero codeword at every point except $13$ :

S_3=D\setminus\{13\}=\{1,2,4,8,16,15,9\}.

But $f$ and $g$ both have nonzero values at $9$ , which is now inside the agreement set. Same problem: no valid codewords $u_0,u_1$ can agree with both original vectors there.

So $\alpha=2$ and $\alpha=3$ both cause MCA failure, without either random linear combination becoming a valid codeword.

For all other $\alpha$ , the combination agrees with the zero codeword on exactly the first six points, and both $f$ and $g$ agree with valid codewords on those same six points.

Therefore, for this particular pair:

\boxed{\Pr_{\alpha\leftarrow\mathbb F_{17}}[\text{MCA failure}]=\frac{2}{17}.}

Another MCA Failure: $h$ Is Actually a Valid Codeword

Remember our first pair of vectors, from Definition 1:

\begin{aligned} f&=[1,2,4,8,1,15,13,9],\\ g&=[0,0,0,0,5,0,0,0]. \end{aligned}

With $\alpha=3$ we got:

h_3=f+3g=[1,2,4,8,16,15,13,9].

This vector is a valid RS codeword, because it's the evaluation of $p(x)=x$ over $D$ .

So $h_3$ agrees with a valid codeword at every point of the domain. We can choose:

S=D=\{1,2,4,8,16,15,13,9\}.

But remember, neither $f$ nor $g$ is a valid codeword on the entire domain. There are no valid codewords $u_0,u_1\in C$ such that:

f|_D=u_0|_D,\qquad g|_D=u_1|_D.

So for this agreement set, the answer is NO. That's another MCA failure event.

Notice the difference: this time the random linear combination is perfectly valid. In our previous example, it wasn't a codeword at all, just close to one.

For this first pair, only $\alpha=3$ causes MCA failure, so the probability is exactly $1/17$ .

The Probability of MCA Failure

Here's where the probability comes in.

We now have two different examples using the same RS code and the same distance threshold $\delta=1/4$ :

In the first example, the combination becomes an actual codeword for one value of alpha: failure probability $1/17$ .
In the second example, the combination gets close to a codeword on a set that the original vectors can't explain, for two values of alpha: failure probability $2/17$ .

But neither $1/17$ nor $2/17$ is a general formula for MCA failure. The probability depends on the RS code, the vectors $f$ and $g$ , and the distance $\delta$ .

The bigger mathematical question is: how large can the failure probability get, even if somebody chooses the worst possible $f$ and $g$ ?

We call that worst-case probability the MCA error:

\begin{aligned} \varepsilon_{\mathrm{mca}}(C,\delta) &=\max_{f,g\in\mathbb F^D} \Pr_{\alpha\leftarrow\mathbb F}\\ &\quad[\text{MCA failure for }f,g,\alpha\text{ at distance }\delta]. \end{aligned}

The Grand MCA Proximity Prize problem asks how large we can make $\delta$ while keeping this worst-case failure probability extremely small. Better bounds can help cryptographic proofs reach very high soundness levels, for example $2^{-128}$ .

Why MCA Matters for Cryptographic Proofs

Reed–Solomon proximity tests appear in STARKs and related proof systems. Random linear combinations help combine checks about several evaluation vectors into checks about one vector.

The concern is that invalid vectors might accidentally combine into something that looks like a low-degree polynomial on many evaluation points. MCA measures how reliably agreement of that combination implies simultaneous agreement of the inputs on those same points.

A stronger bound on MCA failure probability can improve soundness analysis of such tests and, for appropriate proof-system parameters, help reduce verification queries and proof size.

Conclusion

MCA begins with two arbitrary vectors, a random field element, and their random linear combination:

h_\alpha=f+\alpha g.

If $h_\alpha$ agrees with a valid Reed–Solomon codeword on a sufficiently large set $S$ , do valid codewords $u_0$ and $u_1$ agree with $f$ and $g$ on exactly that same set?

For a fixed challenge and agreement set, that is a yes-or-no question. Over random choices of $\alpha$ , a NO answer can occur with some probability. Bounding that probability is the mathematical problem studied by Mutual Correlated Agreement.