[TOC]

# Using Random Linear Combinations in Proof System Design

One of the major "tricks" in the toolkit for designing proof systems is to *combine polynomials using verifier randomness.* This is often described as "batching" or "folding," but the underlying mathematical technique is a *random linear combination.*

This note unpacks these ideas a bit, using the terms "batching," "folding," and "random linear combination" interchangeably.

## Motivation: Using randomized folding reduces work
Let's start by motivating why folding is useful. Put simply, this approach can be used to "reduce" many problems into a single problem, and to "reduce" hard problems into easier problems.

As a concrete example of reducing two problems into one, suppose the Prover wants to prove some property is true for two functions $f$ and $g$. To introduce some notation, let's define $\mathcal{L}$ as the set of all functions for which this property is true. Using this notation, our aim is to prove that both $f$ and $g$ are elements of $\mathcal{L}$.

Let's suppose further we know a protocol $\mathcal{P}$ that can be used to prove $f\in\mathcal{L}$ and $g\in\mathcal{L}$. Assume $\mathcal{P}$ is expensive, and we'd like to avoid running it twice. Rather than running $\mathcal{P}$ on both $f$ and $g$, we can use the following technique:

1. Prover commits to polynomials $f$ and $g$.
2. Verifier provides a random value $r$.
3. Prover commits to $f+r\cdot g$
4. Run $\mathcal{P}$ on $f+r\cdot g$

Now, we only run $\mathcal{P}$ *once* -- demonstrating that the sum $f+r\cdot g$ is an element of $\mathcal{L}$.

Assuming certain characteristics about $\mathcal{L}$ and the commitment scheme being used, this is sufficient to convince the Verifier (with high probability) that both $f$ and $g$ are in $\mathcal{L}$.

## Folding more than two functions

Above, we considered folding together 2 functions, $f$ and $g$.
Now, let's broaden the scope to include folding more than 2 functions.

Suppose we have $f_0, f_1, \ldots, f_{n-1}$, and we want to fold them to construct a single function $g$. There are various ways to proceed.

In this section, we describe two techniques for randomly combining $f_0, f_1, \ldots, f_{n-1}$. In the language of the [Proximity Gaps](https://eprint.iacr.org/2020/654) paper, the first approach is called "affine batching," and the second is called "parametric batching." The first technique uses $n-1$ random values, while the second uses only a single random value. In a later section, we describe a tensor-based technique that uses logarithmically many random values.

### Affine Batching
Verifier sends one value $r_1,\ldots,r_n$ per function $f_i$, and compute $g$ as the sum $$g = f_0 + \sum_{i=1}^n r_i f_i$$

### Parametric Batching
Verifier sends a single random value $r$, and compute $g$ as the sum $$g = \sum_{i=0}^n r^i f_i$$

In practice, using parametric batching offers some savings in communication complexity, at the cost of a few bits of soundness (depending on the number of functions being folded together).

### Tensor-based Batching
In 2023, the [first](https://eprint.iacr.org/2023/630) in a series of publications by Diamond & Posen introduced a middle path between the two options described above. We refer to this new approach as "tensor batching."

Choose random values, $r_0,\ldots,r_{\log(n)-1}$ and compute $g$ as the tensor product $$g = \otimes_{i=0}^{\log(n)}\begin{bmatrix}r_i & 1-r_i\end{bmatrix}\cdot[f_0\ldots f_{n-1}]$$

We briefly summarize the tradeoffs for these three approaches, when used to batch $n$ functions. The table makes clear that the tensor-batching approach offers a compelling option, with both low communication complexity and low soundness loss.

| Batching Method | Algebraic Description | Communication Complexity | Soundness Loss |
| --------------- | --------------------- | ------------------------ | -------------- |
| Affine | $\sum r_i f_i$ | $\mathcal{O}(n)$ | None |
| Tensor | $\otimes_{i=0}^{\log(n)-1}\begin{bmatrix}r_i & 1-r_i\end{bmatrix}\cdot[f_0\ldots f_{n-1}]$ | $\mathcal{O}(\log(n))$ | $\mathcal{O}(\log(n))$
|Parametric | $\sum r^i f_i$ | $\mathcal{O}(1)$ | $\mathcal{O}(n)$ |

## Folding in FRI
To give some more concrete context, let's discuss how these techniques get used in the Batched FRI protocol.

Recall that the "Batched FRI Protocol" consists of:
1. A BATCHING Phase
2. A COMMIT Phase
3. A QUERY Phase

Put briefly, the BATCHING phase uses folding to reduce a collection of FRI problems to a single FRI problem, and each round of the COMMIT Phase uses folding to reduce a FRI problem to a smaller FRI problem.

In the [Proximity Gaps paper](https://eprint.iacr.org/2020/654), which serves as the backbone for state-of-the-art soundness analysis for FRI, the protocol is presented using *affine* folding for the BATCHING phase and *parametric* folding for the COMMIT phase. In practice, most (all?) projects using FRI today are using parametric batching for both the BATCHING phase and the COMMIT phase. Some newer work (e.g. Binius) is making use of tensor-based folding, but AFAIK this technique is not being used in production today.

For a more detailed introduction to FRI, check out my talk on the [Mechanics of FRI](https://tr.ee/qMPxUJcquP) and/or lessons 10-12 of [STARK by Hand](https://tr.ee/As7jT9WJSq).

## Mathematical Intuition: Linear Combinations
"Linear combinations" are ubiquitous and foundational in mathematics.

A function $f$ is called **linear** if it respects addition and respects scalar multiplication. In other words, $f$ is linear if the following properties hold for any vectors $\vec{a}$ and $\vec{b}$, and any scalar $k$:
1. $f(\vec{a}+\vec{b})=f(\vec{a})+f(\vec{b})$
2. $f(k\vec{a})=kf(\vec{a})$

A simple example of a linear combination is a "weighted sum," and that's the technique being used in all the folding techniques discussed in this note.

Given some choice of *weights* $a_i$, and some things to combine $f_0\ldots,f_{n-1}$ (which you can view as vectors or as functions, as you prefer), we can construct a linear combination of the $f_i$ by writing the sum $\sum_{i=0}^{n-1}a_if_i$.

It's straight-forward to see that properties (1) and (2) both hold, i.e., that:
$$\sum_{i=0}^{n-1}a_if_i + \sum_{i=0}^{n-1}a_ig_i= \sum_{i=0}^{n-1} a_i(f_i+g_i) \quad \quad \text{and}
\quad \quad \sum_{i=0}^{n-1}a_ikf_i = k\sum_{i=0}^{n-1}a_if_i$$

Given *any* choice of weights $a_i$, this construction is a linear combination -- and we can choose the weights in any number of ways. Affine folding, parametric folding, and the upcoming tensor-based folding represent *different mechanisms for choosing the weights*.

Affine folding chooses weights based on many random values, and parametric folding chooses weights based on a single random value. Tensor-based folding offers a middle-ground between the two, using $\log(n)$ random values.

## Mathematical Intuition: Linearity of a Property
Moving beyond the world of linear combinations, the word "linear" can be used to describe "properties." Recall from above that we introduced the notation $\mathcal{L}$ to represent the set of functions that have some property.

If $\mathcal{L}$ is *closed under addition* and *closed under scalar multiplication*, then it makes sense to say that the property we're discussing is linear. For simplicity, if the property that defines $\mathcal{L}$ is linear, we'll say $\mathcal{L}$ is linear.

In practice, the property we're interested in is often one of the following:
- $f$ evaluates to 0 at every element of some set $H$ (in other words, $f$ vanishes on $H$)
or
- $f$ is close to a Reed-Solomon codeword

And indeed, both of these properties are linear!

If $f$ and $g$ satisfy either of the properties mentioned above, then linear combinations of $f$ and $g$ will also satisfy that property.

Returning to the context of proving that $f$ and $g$ are in $\mathcal{L}$, we can say that if:
1. $\mathcal{L}$ is linear, and
2. $f,g$ are both in $\mathcal{L}$,

then $f+rg$ is also in $\mathcal{L}$.

## Mathematical Intuition: Completeness and Soundness
In the context of the reduction described in the beginning of this article, the two core properties we need are *completeness* and *soundness*.

Completeness means the honest provers will never fail, and soundness means that malicioius provers will get caught with high probability.

In other words, to prove completeness of our reduction, we need to show that if $f$ and $g$ are both in $\mathcal{L}$, then $f+rg$ will also be in $\mathcal{L}$. As discussed in the previous section, if $\mathcal{L}$ linear, this holds for any choice of $r$.

Soundness is trickier. To prove soundness, we need to show that if $f+gr$ is in $\mathcal{L}$, then with high probability (over the choice of $r$) both $f$ and $g$ are also be in $\mathcal{L}$.

Consider the example where $\mathcal{L}$ is defined as the set of functions that evaluate to 0 at some fixed point $\alpha$. If $f(\alpha)=2$ and $g(\alpha)=-2$, then neither $f$ nor $g$ is in $\mathcal{L}$, but $f+g$ is. This is an example of soundness error. If the Verifier provided the random value $r=1$, the reduction above would result in the Verifier accepting the Prover's false assertion.

To analyze soundness, we need to quantify the likelihood of such an error. Of all the possible values the Verifier might provide for $r$, what is the likelihood that $f+rg\in\mathcal{L}$, while one or both of $f,g$ are *not* in $\mathcal{L}$?

If $\mathcal{L}$ is particularly nice (such as the example described in the previous paragraphs), we find a soundness error of $\frac{1}{k}$ for affine batching, and $\frac{n}{k}$ for parametric batching, where $k$ is the number of possible choices for $r$ and $n$ is the number of functions being batched.

In the context of FRI and a number of related protocols, the property of interest is *proximity* to a *linear code*. In other words, we're not trying to prove that $f$ is *in* $\mathcal{L}$, but rather that there is some element of $\mathcal{L}$ that is *close* to $f$. In this case, analyzing soundness requires that we turn toward the more subtle topic of *[proximity gaps](https://www.youtube.com/watch?v=8AMiZdWA1eM&list=PLcPzhUaCxlCjdhONxEYZ1dgKjZh3ZvPtl&index=10)*.

## Thanks for reading!
Questions/comments/suggestions?
This doc is open for commenting, or you can e-mail Paul at [e-mail]

For more of my writing & videos, check out my [Linktree](https://linktr.ee/pgafzk).