Here we cover how to build a polynomial commitment scheme (PCS) from the FRI interactive oracle proof of proximity (FRI-IOPP). Specifically, we explain how to reduce an evaluation proof to a proof of proximity. It is assumed that the reader already understands the FRI-IOPP. Everything here was derived from reading Transparent PCS with polylogarithmic communication complexity (Vlasov & Panarin, 2019).
We assume the usual setup for FRI. Let denote a finite field, write for a subgroup of the group of units with a power of two. Let denote the vector space of functions , considered as vectors with entries indexed by some fixed enumeration of (we’ll call elements of “words”). Let denote the evaluation map, i.e. Write for the relative Hamming distance on , and let denote the Reed-Solomon code with degree bound . Fix throughout some degree bound . We will be concerned with two separate Reed-Solomon codes, namely and (note that both use the same evaluation points ). Write for the unique decoding radius of , i.e. is maximal such that, for any and ,
The data of a commitment in the FRI-PCS with degree bound is a word (more precisely: an oracle to ). Assume for now that the prover is honest. In the simplest case, for some . Crucially, however, we require something weaker than this of a commitment : it is sufficient that be within the unique decoding radius of some codeword , i.e. Any such is considered to be a valid commitment to its corresponding . Why is this subtlety necessary? Because if the stricter condition were required, then the (soon to be explained) reduction of an evaluation proof to an invocation of the FRI-IOPP wouldn’t be possible. The FRI-IOPP isn’t sufficiently sensitive to reliably distinguish between a codeword and nearby non-codewords (for an explicit demonstration, see here).
Assuming that the prover has sent a commitment to the verifier, an evaluation proof proceeds as follows. The verifier chooses an evaluation point and sends this to the prover, and the prover responds with the purported evaluation of the polynomial committed to (in the case of an honest prover, where is determined by ). The prover wants to establish Since if and only if is divisible by , and degree is additive under polynomial multiplication, this two part claim is equivalent to the following unified claim: Thus we are interested in the proximity of the commitment to a specific subset of , namely the subset consisting of codewords of the form . Note, however, that we can not immediately apply FRI-IOPP to establish this claim, since this subset is not itself a Reed-Solomon code (it isn’t even a linear subspace of ). The good news is that, with a small amount of work, it can be seen that the claim is equivalent to a claim that can be established using the FRI-IOPP (with degree bound ). This claim involves a vector derived from , which we’ll define below. And thus the FRI-PCS evaluation proof will be established using by a proximity proof!
Firstly, a note on oracles. Importantly, the verifier does not need to receive or read all of the that commits to . Since an evaluation proof reduces to an invocation of the FRI-IOPP, it is sufficient for the verifier to be supplied with a mechanism to query entries of at arbitrary indices . In an information theoretic presentation, this mechanism is abstracted as an oracle. In implementation, the oracle is typically instantiated with a Merkle commitment to the tree whose leaves are the (enumerated in some agreed upon manner). The prover binds itself to by sending the Merkle root to the verifier, and the verifier queries an entry by asking the prover for the Merkle path from the root to the corresponding leaf.
Let’s now derive the reduction of the evaluation proof to an instance of the FRI-IOPP. Given bijections for each , a bijection of the space of all words can be defined by Call such a map a “component-wise bijection”; it is immediate for any such map that For any and , define a component-wise bijection by Its inverse is given by from which it follows immediately that Combining and , we obtain and substituting this into the claim , we obtain the equivalent claim which the prover and verifier can establish using the FRI-IOPP! is nothing more than the statement that is -close to .
It is instructive to now consider the two possible cheating strategies for the prover in this reduction to the FRI-IOPP. The first is where the first claim of doesn’t hold, i.e. for all , is not within the unique decoding radius of some . Put differently, this is just saying that , i.e. “ is -far from the code ”. Thus, by , for any , and so claim is false, and will be caught with the soundness bound of the FRI-IOPP. The only other cheating strategy for the prover is that where the is in the unique decoding radius of for some , but the claimed evaluation is false, i.e. . Then for any , we have (since otherwise the evaluations at would match), and so and are distinct codewords. Thus, by , since can be within (the unique decoding radius) of at most one codeword (which is ).
Let be a finite field, and write for the polynomials of degree less than over . For any , write for the evaluation map. For any such choice of and of , let denote the corresponding Reed-Solomon code. We’ll require that the entries of are distinct, so that is a -dimensional subspace of and hence is a linear code. The ambient space is considered to be equipped with a fixed basis, and comparison of the coefficients of two vectors with respect to this basis defines the Hamming distance.
Equivalences of linear codes
Recall that two linear codes are equivalent if there exists a linear isomorphism that preserves the Hamming distance on the ambient and maps the codes to one another. Expressed with respect to the fixed bases, an equivalence of codes is a matrix with precisely one non-zero entry in each row and column.
Equivalences of Reed-Solomon codes
The construction of a Reed-Solomon code depends on the choice of evaluation points – but to what extent does it really matter which is chosen? It is easy to see that it doesn’t always matter. For instance, permuting the entries of gives an equivalent code. A more interesting example: if , then , i.e. the two codes are coincide. To see this, just notice that any polynomial has the same degree as , and that . Hence the codes coincide. This example generalizes immediately to invertible affine transformations of applied to coordinate-wise to .
Non-equivalent -Reed-Solomon codes
There are choices of that lead to non-equivalent , but this seems difficult to verify manually. A computational approach is to use Sage to compute the automorphism groups (i.e. group of self equivalences) of for various . Equivalent codes must have isomorphic automorphism groups. So it is sufficient to find two choices of such that the automorphism groups of the associated code have distinct orders. For example:
In order to find further examples of equivalences of Reed-Solomon codes, it turns out to be helpful to describe what at first appears to be a more general construction, but is in fact (up to equivalence of codes) simply a re-parameterization of the same objects. For with distinct entries and , let Then is linear, and the image of under this map is the generalized Reed-Solomon code. Notice that (trivially) a Reed-Solomon code is equivalent to every generalized Reed-Solomon code with the same evaluation points, i.e. So the GRS codes are just a more redundant parameterization of the RS codes – nothing new is gained! Indeed, “generalized Reed-Solomon code” is a misleading name. Yet the GRS codes are more convenient when it comes to constructing equivalences: in order to demonstrate , it suffices to find such that , and this is often easier.
For example, it turns out to be straight-forward to show the following (proof below) Indeed, works. Setting and invoking twice, this allows us to conclude that This is a pretty neat result!
Following is a proof of . While very simple, it seems to be peculiarly “linguistic” as it involves the re-ordering of some coefficients. We’ll explore this next.
(For more on the generalized Reed-Solomon codes and these equivalences, see these lecture notes).
Reed-Solomon codes as algebraic geometry codes
We’ve demonstrated that, if and can be related by a composition of entry-wise affine transformations and inversions, then . Being able to build code equivalences from two apparently distinct sorts of transformations of invites us to look for a more general context in which they are two instances of the same thing. A hint as to what that might be (if another was needed) is contained in the above proof of : in what context does reversing the order of the coefficients of a polynomial become meaningful? This transformation would be more naturally described as interchanging the indeterminates of bivariate polynomials of homogeneous degree . Indeed, the needed generalization uses the projective line in place of as the source of the evaluation points and uses “appropriate” functions on in place of . The natural notion of functions on are the “rational functions”: ratios of homogeneous bivariate polynomials where the numerator and denominator have the same degree. In this new context, the polynomials of degree become those rational functions that only have poles at the point at infinity , and then only of order . Importantly, these functions form a vector space, and the evaluation of any such function at an affine point is (since any pole could only be at infinity) an element of the field .
The first sort of equivalence of RS codes constructed above resulted from an affine transformation of . Just as invertible affine transformations transform the 1-dimensional affine space , homographies (i.e. isomorphisms of projective space) transform the projective line . A homography of the projective line has the form for some invertible 2×2 matrix . Let’s consider some special cases. Setting , this is (an extension of) an invertible affine transformation of . On the other hand, setting , , we have an extension of the map that inverts non-zero field elements (and induces an interchanging of the indeterminates of bivariate homogeneous polynomials!). So the homographies are sufficiently general to include the two sorts of transformations used above to construct our equivalences of RS codes.
Thus we might define a “projective RS code” by beginning with a sequence of distinct points and a constraint on the maximum order of poles at every point on (and such that no poles are permitted at any ). Call this constraint and write for the linear space of all rational functions that satisfy the constraint . Since no poles are permitted at the , the evaluation map is well-defined linear map. Indeed, given a further technical assumption on the constraint, is injective, and we’ve constructed an code where . Clearly it includes the familiar RS codes, and indeed it can be shown (see e.g. Walker Theorem 6.4 & Exercise 6.6) that all these codes are MDS codes. The natural generalization of the code equivalences constructed above are constructed from homographies of . The homographies transform the evaluation points as well as the functions being evaluated (along with their constraint). The advantage of this viewpoint is that now there is nothing to prove: the linear code is defined using structures in projective space, and since homographies are the structure preserving maps of projective space, it is vacuously true that homographies induce equivalences of codes.
Instead of defining such codes, we go just one step further, and consider an arbitrary non-singular projective plane curve in place of the projective line. There are distinct evaluation points , and the “constraint” on the order of the poles takes the form of a divisor on whose support does not contain the . The space of functions are the rational functions on the curve associated to the divisor , i.e. is the Riemann-Roch space. The dimension of the resulting algebraic geometry code is determined by the degree of the divisor and the genus of .
Further reading
These lecture notes are an excellent elementary introduction to equivalences of GRS codes. See Walker’s “Codes & Curves” for a speedy introduction to algebraic geometry codes, and read The automorphism groups of Reed-Solomon codes (Dür, 1987) for a description of the automorphism group of Reed-Solomon codes in terms of fractional linear transformations (i.e. homographies of the projective line).
(The following thought experiment was suggested to me by my colleague Ryan Cao; mistakes and invective are my own).
FRI is often described as a “low degree test”, which suggests that the verifier should reject with high probability if the degree is high. This is not the case, as the simple example below demonstrates. Indeed it is the polynomials of highest degree that have the highest chance of being erroneously accepted by the verifier. (What is true is that the FRI verifier rejects with high probability if the evaluations are far from the code: FRI is a proof of proximity).
Let be a field, with , and write for the evaluation map. For any , let be the Reed-Solomon code of evaluations of polynomials of degree strictly less than on .
Henceforth we assume that is a subgroup of the multiplicative group and that is a power of two. The degree bound will also be a power of two. For , let be the FRI folding operation (in the coefficient domain) and write for the corresponding operation in the evaluation domain. Then it’s not hard to check that for any and , we have
FRI operates by iterated folding, using challenges provided by the verifier. The claim of the proximity of to the code is reduced to the claim of the proximity of to the code for some . This process is repeated until the claim is that is close to the code , at which point the verifier queries entries from and checks if they all agree: if they do, it concludes that is (w.h.p.) close to its code, and hence that the original vector is (w.h.p.) close to the original code. Proving that FRI is indeed a good test of proximity is complicated. It is easy to show, however, that FRI is not (indeed never intended being) a reliable means of detecting polynomials of high degree, and that is what we’ll do here.
For any , let denote the Lagrange interpolation polynomial, i.e. Then , i.e. it has has maximal degree (given the size of the evaluation domain ). Its evaluations, however, are “one-hot” at and in this sense are maximally close to the code, while not being in the code (having Hamming distance from the zero codeword). It’s easy to see from that i.e. that except with negligible probability (when ), the folding will also have Hamming distance 1 from its code . Note, however, that the relative Hamming distance has doubled, since the size of the evaluation domain has halved.
So let’s set . Then after rounds of folding, is (except with negligible probability) non-zero in exactly one place, and its relative distance from the code (which consists of constant vectors) is i.e. the rate of the original code. The verifier thus accepts with probability . Given that is typically close to zero (e.g. ) and is always small, this probability is close to . For this reason, it is misleading (if commonplace) to describe FRI as a “low-degree test”: the polynomials , which have maximal degree are routinely accepted by the FRI verifier. Why? Because the evaluations of these polynomials are close (“proximal”) to the code. FRI is a proof of proximity, after all.