Introduction
In the previous post, we went over Fʀᴀᴄᴛᴀʟ at a very high level, describing its features and what kind of subprotocols we would need to make it work. This post is a little more dense and details how these subprotocols work.
Univariate Sumcheck for Rational Functions
As we mentioned in the previous post, there is a result that says $\sum_{s \in S} f(s) = \sigma$ if and only if $f(x) = \Gamma_{g, \sigma}(x)$ where $\Gamma_{g, \sigma} = x \cdot g(x) + \sigma / |S|$ and $g(x)$ is a polynomial of degree strictly less than $|S|-1$. To extend this to rational functions, let's first do a little bit of algebra. What we wish to show is
\[ \frac{p(\alpha)}{q(\alpha)} \ \equiv_S \ \Gamma_{g, \sigma}(\alpha) \]
where $f \equiv_S g$ means that $f$ and $g$ agree on all values of $S$. Then we would have
\[ p(\alpha) \ \equiv_S \ \Gamma_{g, \sigma}(\alpha) \cdot q(\alpha) \]
But we're not done. Due to the multiplication of $\Gamma_{g, \sigma}$ and $q$, the polynomial function interpolating each side generally has much higher degree than we want. So we make one more adjustment to get
\[ 0 \ \equiv_S \ \Gamma_{g, \sigma}(\alpha) \cdot q(\alpha) - p(\alpha). \]
Now we still have a "high" degree polynomial on the right-hand side, but it is zero on all of $S$. This doesn't necessarily mean that it is zero on all of $\mathbb{F}$, but it does mean that the polynomial interpolating the right hand side is divisible by the nonzero polynomial of minimal degree that is zero on $S$, constructed as $Z_S(x) = \displaystyle\prod_{s \in S} (x - s)$. So even though $\Gamma_{g, \sigma}(x) \cdot q(x) - p(x)$ isn't necessarily low-degree, the polynomial interpolating $\dfrac{\Gamma_{g, \sigma}(x) \cdot q(x) - p(x)}{Z_S(x)}$ on $S$ is.
Holographic Lincheck
In the previous post, we mentioned the need for some $u$ which is a vector of linearly independent polynomials. We could choose the entries to be something simple such as a power basis $1, x, x^2 \ldots$ but to give it a little more structure, we will choose the entries of $u$ to be the partial evaluations of the bivariate "diagonal polynomial on $H$"
\[ D_H(x,y) = \frac{Z_H(x) - Z_H(y)}{x-y} \]
as $y$ ranges over $H$. Two things to note about this polynomial are
- first, it does give linearly independent polynomial entries. To see this (and to see why we call it a diagonal polynomial) imagine a square matrix with indices in $H \times H$ which has the value $D_H(a,b)$ in the $a,b$ entry. When $a$ and $b$ are both in $H$, but not equal to each other, the numerator of the rational function defining $D_H$ is zero, but the denominator is not. When $a=b$ we get an indeterminate form, but it can be resolved because
- the minimal-degree nonzero polynomial which is zero on a multiplicative group is of the form $Z_H(x) = x^{|H|}-1$ so the numerator is $x^{|H|}-y^{|H|}$, which is divisible by $x-y$ no matter the size of $H$ and so despite defining it as a rational function, $D_H$ does indeed describe a polynomial function.
The indexer $\mathbf{I}$ receives $\langle A \rangle$, the sparse representation of the matrix $A$, and computes a sparse representation of $A^\ast$, a matrix defined so that $M_{a, b}^\ast = M_{b,a} \cdot D_H(b,b)$. The reason for defining it this way is so that the interpolating bivariate polynomial $\hat{A^*}(x,y)$ is equal to the bivariate polynomial $\hat{u_A(x,y)}$ where $u_A(x, \alpha)$ is the polynomial entry in the vector $A \cdot u$ at the position indexed by $\alpha$.
This is the oracle that $\mathbf{V}$ gets access to.
The holographic lincheck protocol proceeds as follows:
- $\mathbf{V}$ sends a random $\alpha \in \mathbb{F}$ that is not in $H$ (so that the polynomial $\hat{u_A}(x, \alpha)$ is defined, but there is no entry in the vector $A \cdot u$ corresponding to $\alpha$).
- $\mathbf{P}$ responds with the evaluation of $t(x) = \hat{u_A}(x, \alpha)$ on $L$.
- $\mathbf{P}$, $\mathbf{V}$ perform a sumcheck. i.e. $\mathbf{P}$ sends an evaluation of some function $g$ on some coset $L \subset \mathbb{F}$ where $L$ is larger than $H$, but the degree of $\hat{g}$ is strictly less than $|H|-1$. $\mathbf{V}$ outputs two rational constraints, the first attesting that the degree of $\hat{g}$ is indeed strictly less than $|H|-1$ and the second one attests that the degree of $\hat{h} \leq d-1$ for a function $h$ defined on $L$ as
\[ h(x) = \frac{D_H(x,a) f_a(x) - t(x) f_z(x) - \Gamma_{g, 0}(x)}{Z_H(x)} .\] - $\mathbf{V}$ sends $\beta \in \mathbb{F} \setminus H$ uniformly at random.
- $\mathbf{P}$ sends $\gamma = u_A(\beta, \alpha) = \hat{t}(\beta)$ and $\mathbf{V}$ outputs a boundary constraint asserting that $\gamma = \hat{t}(\beta)$. So at this point $\mathbf{P}$ has comitted to the value of $\hat{t}(\beta)$ because if it's not the case that $\hat{t}(\beta) = \gamma$ then this boundary condition will not be satisfied so Fʀᴀᴄᴛᴀʟ's verifier will not accept the proof.\item $\mathbf{P}$, $\mathbf{V}$ perform the sparse matrix arithmetization protocol to verify that $A^*_{\beta, \alpha} = \gamma$.
Sparse Matrix Arithmetization
If we're given a matrix $M$ containing mostly zeroes, it's to our benefit to find a way to represent the matrix so that we only need to store information about the nonzero entries (as much as possible). The way we do this is with a sparse matrix representation $\langle M \rangle$ which is a function defined over some set $K \subset \mathbb{F}$ whose values are all ordered triples of the form $(a, \ b, \ \gamma)$ with $a, b \in H$ and $\gamma \in \mathbb{F}$. So [assuming $M$ has at most $|K|$ nonzero entries], if for some $k \in K$ we have $\langle M \rangle (k) = (a, \ b, \ \gamma)$ then the entry in the $a, b$ position of $M$ is $\gamma$. Any entries not covered by the sparse matrix arithmetization protocol are zero.
This is where holography comes in. The matrices $A$, $B$, and $C$ are part of the index $i$. What makes this proof system holographic is that the verifier $\mathbf{V}$ does not have access to $i$. Instead, an indexer $\mathbf{I}$ will take $i$ and output a set of oracles that $\mathbf{V}$ can query. The benefit of this, is that it allows the verifier's runtime to grow sublinearly with the size of the circuit. Without holography (or some form of preprocessing) this isn't possible, because at the very least the verifier would have to read the entire circuit. A "preprocessing" SNARG is a SNARG where a preprocessing step is computed once for each index (i.e. it doesn't need to be repeated for each proof) and any holographic IOP can be converted into a preprocessing SNARG by taking the indexer's oracle and putting it into a Merkle tree. Then the root of this tree is published as the index's 'verification key'. After this step, the prover can be trusted to answer the verifier's (real or simulated) queries to the holographic oracle if it provides an authentication path that can be checked against the verification key.
In this case, for each matrix $M$ the indexer outputs oracles for the functions defined so that if $\langle M \rangle(k) = (a, \ b, \ \gamma)$
\[ \mathsf{row}_{\langle M \rangle} (k) = a \]
\[ \mathsf{col}_{\langle M \rangle} (k) = b \]
\[ \mathsf{val}_{\langle M \rangle} (k) = \frac{\gamma}{D_H(a, a) \cdot D_H(b, b)} \]
The Verifier
The verifier splits naturally into two parts; one verifying the RS-encoded IOP and a second part that checks the transformation to a SNARG was done correctly.
Both of these involve computing many hashes. Writing standard hash functions, such as SHA-256, in an arithmetic circuit requires a lot of gates; too many for us to feasibly express the verifier entirely within an arithmetic circuit. However, we need to be able to do this if we want to recursively verify Fʀᴀᴄᴛᴀʟ instances, as Fʀᴀᴄᴛᴀʟ only verifies computations in arithmetic circuits (converted to R1CS instances). The proof of correctness for Fʀᴀᴄᴛᴀʟ works in the Random Oracle Model, where the specific hash function is not specified, but is assumed to have some desirable properties. The hash function chosen for implementation is Rescue, which was designed to have low complexity when expressed as an arithmetic circuit.
Conclusion
Fʀᴀᴄᴛᴀʟ, and its predecessor Aurora, are difficult to compare qualitatively to other SNARKs and STARKs, and not just because of its unique achievements of post-quantum security and recursive composability. In almost every aspect of the construction above, the authors of Fʀᴀᴄᴛᴀʟ have come up with a solution or used fairly recent constructions tailored very specifically to their needs, from the RS encoding to the new hash function. In fact, every novel sub-protocol described in this post is required just to make the IOP work!
Written by Nat Bunner, zero-knowledge cryptography researcher & protocol developer at Metastate.
Image credits: Denali National Park and the photographer Ken Conger.
Metastate has ceased its activities on the 31st of January 2021. The team members have joined a new company and working on a new project. If you're interested in zero-knowledge cryptography and cutting-edge cryptographic protocols engineering positions in Rust, check out the open positions at Heliax.
If you have any feedback or questions on this article, please do not hesitate to contact us: hello@heliax.dev.