A GKR Tutorial
Special thanks to Lev Soukhanov, Zhenfei Zhang, Zachary Williamson and Justin Drake for feedback and review
特别感谢 Lev Soukhanov、Zhenfei Zhang、Zachary Williamson 和 Justin Drake 的反馈和审核
If you're following the "cryptography side of crypto", at this point you've likely heard a lot about ultra-fast ZK-provers: ZK-EVM provers proving the Ethereum L1 in real-time with only about fifty consumer GPUs, people proving 2 million Poseidon hashes per second on consumer laptops, and zk-ML systems proving LLM inference with increasing speed.
如果您关注“加密货币的密码学方面”，此时您可能听说过很多有关超快 ZK 证明者的信息：ZK-EVM 证明者仅使用大约 50 个消费级 GPU 即可实时证明以太坊 L1，人们在消费级笔记本电脑上每秒证明 200 万个 Poseidon 哈希值，而 zk-ML 系统则以越来越快的速度证明 LLM 推理。
In this post, I will explain in detail a family of protocols that is behind the extreme speed of many of these proving systems: GKR .
在这篇文章中，我将详细解释许多此类证明系统极速背后的一系列协议：GKR。
I will focus on a GKR implementation for proving Poseidon hashes (and other computations that follow a similar pattern).
我将重点关注用于证明 Poseidon 哈希（以及遵循类似模式的其他计算）的 GKR 实现。
To see GKR in the context of more generic circuit evaluation, see Justin Thaler's note and this Lambdaclass post .
要在更通用的电路评估背景下查看 GKR，请参阅 Justin Thaler 的注释和这篇 Lambdaclass 帖子 。
Suppose that you have a computation that is "big" in two dimensions: it involves processing data through at least a medium number of (low-degree) "layers", and it involves applying the same function to a large number of inputs.
假设您有一个二维“大”计算：它涉及通过至少中等数量（低度）“层”处理数据，并且涉及将相同的函数应用于大量输入。
Something like this:
像这样的东西：
As it turns out, a lot of the biggest computation we do fits into this kind of pattern.
事实证明，我们所做的许多最大的计算都适合这种模式。
Cryptographers will notice that many computationally intensive proving operations involve proving lots of hashes, and each hash internally has that exact kind of internal structure.
密码学家会注意到，许多计算密集型证明操作涉及证明大量哈希值，并且每个哈希值内部都具有这种精确的内部结构。
AI researchers will notice that a neural network, the core building block of an LLM, has exactly that internal structure (both because you can prove inference of many tokens in parallel, and because within each token, you have a structure mixing element-wise neural layers with global matrix multiplication layers, which technically violate the cross-input independence in the diagram above but in practice are very easy to put into a GKR system).
AI 研究人员会注意到，LLM 的核心构建块神经网络正是具有这种内部结构（既因为您可以并行证明许多令牌的推理，也因为在每个令牌内，您都有一个将元素神经层与全局矩阵乘法层混合的结构，这在技术上违反了上图中的交叉输入独立性，但实际上很容易放入 GKR 系统中）。
GKR is a cryptographic scheme that is tailor-made for this pattern.
GKR 是专为这种模式量身定制的密码方案。
It achieves its efficiencies by avoiding the need to make commitments to any of the intermediate layers : you only need to commit to the inputs and the outputs.
它通过避免对任何中间层做出承诺来实现其效率：您只需要承诺输入和输出。
"Commitments" here mean putting the data into a cryptographic data structure, either a KZG or a Merkle tree, that allows you to prove queries about specific things about that data.
这里的“承诺”意味着将数据放入加密数据结构（KZG 或 Merkle 树）中，这样您就可以证明有关该数据的特定事物的查询。
The cheapest commitment, a Merkle tree of an erasure coding (used in STARKs ), requires you to hash 4-16 bytes for each byte you commit to: hundreds of additions and multiplications when the underlying operation you're proving at that step might be a single multiplication.
最便宜的承诺是纠删码的 Merkle 树（在 STARKs 中使用），要求您对提交的每个字节进行 4-16 个字节的哈希处理：当您在该步骤证明的基础操作可能是单个乘法时，需要进行数百次加法和乘法。
GKR avoids all of this, except at the very beginning and the very end.
GKR 避免了所有这些，除了在开始和结束时。
Note that GKR is not "zero knowledge": it only handles succinctness, not privacy.
请注意，GKR 并不是“零知识”：它只处理简洁性，而不处理隐私。
If you want zero knowledge, wrap the GKR proof in a ZK-SNARK or ZK-STARK.
如果您想要零知识，请将 GKR 证明包装在 ZK-SNARK 或 ZK-STARK 中。
Suppose you have a multivariate polynomial \(P(x_1, x_2 ...
假设您有一个多元多项式 \(P(x_1, x_2 ...
x_N)\) , which is low-degree in each dimension.
x_N)\) ，在每个维度上都是低度的。
You want to prove the sum of evaluations of that polynomial across a hypercube - that is, you want to prove the value of \(\sum_{i_k \in \{0,1\}} P(i_1, i_2 ...
您想要证明该多项式在超立方体上的评估总和 - 也就是说，您想要证明 \(\sum_{i_k \in \{0,1\}} P(i_1, i_2 ...
i_N)\) .
i_N)\) 。
There is a standard technique that reduces this problem to that of evaluating \(P\) at a random coordinate.
有一种标准技术可以将此问题简化为在随机坐标处评估 \(P\) 的问题。
That is, you can convert an "obligation" to prove \(\sum_{i_k \in \{0,1\}} P(i_1, i_2 ...
也就是说，你可以转换一个“义务”来证明 \(\sum_{i_k \in \{0,1\}} P(i_1, i_2 ...
i_N)\) into an obligation to prove \(P(c_1, c_2 ...
i_N)\) 成为证明 \(P(c_1, c_2 ...
c_N)\) , for some \(c_1, c_2 ...
c_N)\) ，对于某些 \(c_1, c_2 ...
c_N\) that get randomly generated as part of the proving process.
c_N\) 作为证明过程的一部分随机生成。
Here is what it looks like for a multilinear polynomial (one that is linear in each variable; so \(x_ix_j\) is allowed but not eg.
这是多线性多项式的样子（每个变量都是线性的；因此允许 \(x_ix_j\) ，但不允许例如。
\(x_i^2\) ):
\(x_i^2\) ):
At each step, the prover provides a sum for each half of the current hypercube.
在每一步中，证明者都会为当前超立方体的每一半提供总和。
These sums (and any previous randomness) get hashed together and used as randomness to choose an evaluation coordinate.
这些总和（以及任何先前的随机性）被散列在一起并用作选择评估坐标的随机性。
The prover then uses a simple linear combination of the two halves of the (dimension N) hypercube to compute the half-size (dimension N-1) hypercube of evaluations where the first coordinate is set to the evaluation coordinate that was just randomly chosen .
然后，证明者使用（维度 N）超立方体的两半的简单线性组合来计算评估的一半大小（维度 N-1）超立方体，其中第一个坐标设置为刚刚随机选择的评估坐标。
In the diagram above, the prover starts with evaluations at ((0,0,0), (0,0,1) ...
在上图中，证明者从 ((0,0,0), (0,0,1) ... 处的评估开始
(1,1,1)), and takes the top half plus 6 times the difference between the top half and the bottom half to compute the half-sized hypercube of evaluations at ((6,0,0), (6,0,1), (6,1,0), (6,1,1)).
(1,1,1))，并取上半部分加上上半部分与下半部分之差的 6 倍来计算 ((6,0,0), (6,0,1), (6,1,0), (6,1,1)) 处的评估的一半大小的超立方体。
This is a standard "random linear combination" trick: proving that a linear claim (in this case, a sum) is true for multiple values (here, two halves of the hypercube) by proving it for a random linear combination of those values.
这是一个标准的“随机线性组合”技巧：通过证明这些值的随机线性组合来证明线性声明（在本例中为总和）对于多个值（此处为超立方体的两半）成立。
A similar idea is used in bulletproofs .
类似的想法也用于防弹。
And like in bulletproofs, we use the random linear combination trick recursively: The prover continues turning a claim about a hypercube into a claim about a hypercube half the size, until the "hypercube" shrinks to one single value.
就像在防弹中一样，我们递归地使用随机线性组合技巧：证明者继续将关于超立方体的声明转变为关于一半大小的超立方体的声明，直到“超立方体”缩小到一个值。
This value is the evaluation of the original multivariate polynomial at a random point (here, (6, 4, 7)).
该值是原始多元多项式在随机点（此处为 (6, 4, 7)）的评估。
If the prover can prove that evaluation, then they've proven the original sum.
如果证明者可以证明该评估，那么他们就证明了原始总和。
A sumcheck is not useful by itself: after all, it simply converts one unproven claim about a bunch of numbers into another unproven claim about a bunch of numbers.
和检查本身并没有什么用处：毕竟，它只是将一个关于一组数字的未经证实的声明转换为关于一组数字的另一个未经证实的声明。
But it is an incredibly useful and powerful ingredient in a whole bunch of proof systems, including GKR.
但它在包括 GKR 在内的一大堆证明系统中是非常有用和强大的成分。
It is also very efficient : particularly, the prover does not need to commit to anything, and the prover and verifier only need to hash a small constant amount of data per round to generate the random coordinates.
它也非常高效：特别是，证明者不需要承诺任何事情，证明者和验证者只需要每轮散列少量恒定数量的数据即可生成随机坐标。
Now, let's get into GKR.
现在，让我们进入 GKR。
For this post, we'll focus on a single type of computation: proving a large number of hashes of the Poseidon2 hash function .
在这篇文章中，我们将重点关注单一类型的计算：证明 Poseidon2 哈希函数的大量哈希值。
The Poseidon2 hash function is quite simple; here's a full graphical description of the core permutation function that it uses:
Poseidon2 哈希函数非常简单；这是它使用的核心排列函数的完整图形描述：
Essentially, you do many rounds that alternate between multiplying the whole data by a matrix, and cubing and adding a constant to each element.
本质上，您会进行多次循环，交替将整个数据乘以矩阵，然后对每个元素求立方并添加一个常数。
The rounds in the middle are "partial rounds", where both operations are simplified: the matrix is an "easy" matrix ( \(diag + J\) in the diagram above) that can be evaluated as \(x_i \rightarrow x_i * d_i + sum(x_0, x_1 ...
中间的回合是“部分回合”，其中两个操作都被简化：矩阵是一个“简单”矩阵（上图中的 \(diag + J\)），可以计算为 \(x_i \rightarrow x_i * d_i + sum(x_0, x_1 ...
x_{15})\) , and only the first value gets cubed.
x_{15})\) ，并且只有第一个值被立方。
This combination of full and partial rounds has been deemed optimal for the tradeoff between performance and security, but it's not essential to the construction: you could do just full rounds with a random matrix if you wanted to.
这种完整轮和部分轮的组合被认为是性能和安全性之间权衡的最佳选择，但这对于构建来说并不是必需的：如果您愿意，您可以使用随机矩阵进行完整轮。
There are many versions and parameter choices of Poseidon2; the above is not meant to accurately depict any specific live implementation, rather it shows the general pattern.
Poseidon2有多种版本和参数选择；以上并不意味着准确描述任何特定的实时实现，而是显示了一般模式。
GKR is well-suited to prove a large number of executions like this in parallel.
GKR 非常适合证明这样的大量并行执行。
Let us go through how it works.
让我们看看它是如何工作的。
We will first start with a simplified version of Poseidon, where there are no partial rounds and no matrices - instead, you just do repeated \(x \rightarrow x^3 + r_j\) .
我们首先从 Poseidon 的简化版本开始，其中没有部分回合，也没有矩阵 - 相反，您只需重复 \(x \rightarrow x^3 + r_j\) 。
GKR works by running through the computation backwards :
GKR 的工作原理是向后运行计算：
Here's the top layer.
这是顶层。
For cleaner exposition (ie.
为了更清晰的展示（即
to avoid the numbers blowing up in size), in this example we will do all the math modulo 89.
为了避免数字增大），在本例中我们将进行所有以 89 为模的数学运算。
In reality, \(V\) is the outputs of the Poseidon computation and so it's numbers in a 32-bit prime field (often KoalaBear ( \(2^{31} - 2^{24} + 1\) )), and \(p_i\) (and hence \(W\) later on in this post) are over a degree-4 extension field (often represented as elements of the form \(x = a_0 + a_1v + a_2v^2 + a_3v^3\) where \(v^4 = 3\) ) to ensure (close to) 128-bit security.
实际上，\(V\) 是 Poseidon 计算的输出，因此它是 32 位素数域中的数字（通常是 KoalaBear (\(2^{31} - 2^{24} + 1\) ）），而 \(p_i\) （以及本文后面的 \(W\)）超过 4 度扩展域（通常表示为 \(x = a_0 + a_1v 形式的元素） + a_2v^2 + a_3v^3\) 其中 \(v^4 = 3\) ) 以确保（接近）128 位安全性。
Note that we have not yet done any sumchecks .
请注意，我们尚未进行任何 sumchecks 。
The first sumcheck we do will actually be on the second-last layer (ie.
我们所做的第一个和检查实际上将在倒数第二层（即
V 31 ).
V 31）。
And to do this we will need to introduce some extra machinery.
为此，我们需要引入一些额外的机器。
Particularly, the goal is not to prove the basic sum \(\sum_{i_k \in \{0,1\}} V_{31}(i_1, i_2 ...
特别是，目标不是证明基本和 \(\sum_{i_k \in \{0,1\}} V_{31}(i_1, i_2 ...
i_N)\) .
i_N)\) 。
Instead, we are proving \(\sum_{i_k \in \{0,1\}} (V_{31}(i_1, i_2 ...
相反，我们证明 \(\sum_{i_k \in \{0,1\}} (V_{31}(i_1, i_2 ...
i_N)^3 + r_{31}) * W_{31}(i_1, i_2 ...
i_N)^3 + r_{31}) * W_{31}(i_1, i_2 ...
i_N)\) .
i_N)\) 。
\(W_{31}\) here is the "weights" that correspond to "evaluate at \(p_{32}\) ".
\(W_{31}\) 这里是对应于“在 \(p_{32}\) 处评估”的“权重”。
Any evaluation of a multilinear polynomial can be represented by weights.
多线性多项式的任何评估都可以用权重表示。
For example, consider the 2D multilinear polynomial with evaluations [[1, 5], [3, 9]]:
例如，考虑具有评估 [[1, 5], [3, 9]] 的 2D 多重线性多项式：
Now, let's say we want the evaluation at (6, 4).
现在，假设我们想要在 (6, 4) 处进行评估。
We can compute this!
我们可以计算一下！
An easy way is to take the difference (eg.
一个简单的方法是取差值（例如
\(x_{01} - x_{00}\) ) along a horizontal or vertical line and re-apply it over and over to "extend" that line:
\(x_{01} - x_{00}\) ) 沿着水平或垂直线并一遍又一遍地重新应用它以“延伸”该线：
Here, [[15, -18], [-20, 24]] is the "weights" corresponding to "evaluate at (6, 4)".
这里，[[15, -18], [-20, 24]]是对应于“在(6, 4)处评估”的“权重”。
We can also compute the weights via a nice formula: \([[(1-4) * (1-6), (1-4) * 6], [4 * (1-6), 4 * 6]]\) .
我们还可以通过一个很好的公式计算权重： \([[(1-4) * (1-6), (1-4) * 6], [4 * (1-6), 4 * 6]]\) 。
A similar thing works in higher dimensions.
类似的事情也适用于更高的维度。
Going back to GKR.
回到GKR。
The expression we wanted to prove the value of is \(\sum_{i_k \in \{0,1\}} (V_{31}(i_1, i_2 ...
我们要证明的表达式是 \(\sum_{i_k \in \{0,1\}} (V_{31}(i_1, i_2 ...
i_N)^3 + r_{31}) * W_{31}(i_1, i_2 ...
i_N)^3 + r_{31}) * W_{31}(i_1, i_2 ...
i_N)\) .
i_N)\) 。
Because \(W_{31}\) is the weights corresponding to "evaluate at \(p_{31}\) ", this expression is exactly the same thing as saying "compute \((V_{31}(i_1,i_2...i_N)^3 + r_{31})(p_{31})\) ", which is itself the same thing as \(V_{32}(p_{31})\) .
因为 \(W_{31}\) 是对应于“在 \(p_{31}\) 处求值”的权重，所以该表达式与“计算 \((V_{31}(i_1,i_2...i_N)^3 + r_{31})(p_{31})\) ”完全相同，它本身与 \(V_{32}(p_{31})\) 相同。
Now, we do the sumcheck.
现在，我们进行总和检查。
It's like we did before, except at each step we provide partial sums not of the values themselves, but of the evaluations of the values.
就像我们之前所做的那样，除了在每一步中我们提供的不是值本身的部分和，而是值的评估的部分和。
Additionally, there is another nuance: because this is a degree-4 expression (degree 3 coming from \(V_{31}^3\) and degree 1 coming from \(W\) ), we need to provide five evaluations at each step, instead of just the left and right side.
此外，还有另一个细微差别：因为这是一个 4 度表达式（3 度来自 \(V_{31}^3\) ，1 度来自 \(W\) ），所以我们需要在每个步骤提供五个评估，而不仅仅是左侧和右侧。
This is all complex, so to avoid adding even more pain let's just set \(r_{31}\) to zero so we can just focus on the cubing.
这一切都很复杂，所以为了避免增加更多的痛苦，我们只需将 \(r_{31}\) 设置为零，这样我们就可以专注于立方。
Here we go:
我们开始吧：
As the bot loves to say, let's go through this step by step.
正如机器人喜欢说的那样，让我们一步一步地完成这个过程。
The prover starts off with the claim \(sum(V_{31}^3 * W_{31}) = 83\) (remember: this is the same thing as saying \(V_{32}(p_{32}) = 83\) ).
证明者从声明 \(sum(V_{31}^3 * W_{31}) = 83\) 开始（记住：这与说 \(V_{32}(p_{32}) = 83\) 是一样的）。
The prover computes and provides the five partial sums of \(sum(V_{31}^3(x, ...) * W_{31}(x, ...))\) for \(x \in \{0,1,2,3,4\}\) .
证明者计算并提供 \(x \in \{0,1,2,3,4\}\) 的 \(sum(V_{31}^3(x, ...) * W_{31}(x, ...))\) 的五个部分和。
The prover gets a random coordinate \(c_0 = 9\) , and computes half-sized hypercubes from \(V_{31}^3(9, ...)\) and \(W_{31}(9, ...)\) .
证明者获得一个随机坐标 \(c_0 = 9\) ，并根据 \(V_{31}^3(9, ...)\) 和 \(W_{31}(9, ...)\) 计算半大小的超立方体。
The prover then repeats.
然后证明者重复。
The verifier is able to check each step against the previous step.
验证者能够根据前一步检查每一步。
Particularly:
特别是：
You can check the example above yourself, and see that the linear combination of the values in each round with coefficients generated by this equals the next round's total (modulo 89).
您可以自己检查上面的示例，您会发现每轮中的值与由此生成的系数的线性组合等于下一轮的总和（模 89）。
At the end, the prover provides the evaluation \(V_{31}(9, 16, 8) = 39\) .
最后，证明者提供评估 \(V_{31}(9, 16, 8) = 39\) 。
Because \(W\) has a mathematical structure, the verifier can compute \(W_{31}(9, 16, 8) = 85\) themselves.
因为 \(W\) 具有数学结构，验证者可以自己计算 \(W_{31}(9, 16, 8) = 85\)。
Then, the verifier checks the equation (remember: you can check an equation between polynomials by checking an evaluation at a random point): \(39^3 * 85 = 87\) (all modulo 89 in our example).
然后，验证者检查方程（请记住：您可以通过检查随机点的评估来检查多项式之间的方程）：\(39^3 * 85 = 87\)（在我们的示例中均为模 89）。
What have we done?
我们做了什么？
We have reduced an unproven claim of the form \(V_{32}(p_{32}) = y_{32}\) to an unproven claim of the form \(V_{31}(p_{31}) = y_{31}\) , all without using any commitments!!!
我们已将 \(V_{32}(p_{32}) = y_{32}\) 形式的未经证实的声明简化为 \(V_{31}(p_{31}) = y_{31}\) 形式的未经证实的声明，所有这些都没有使用任何承诺！
We then proceed and keep going, until we get to a claim \(V_0(p_0) = y_0\) .
然后我们继续前进，直到得到一个声明 \(V_0(p_0) = y_0\) 。
Because \(V_0\) is just the inputs, and the verifier has the inputs, the verifier can just check this directly.
因为 \(V_0\) 只是输入，而验证者有输入，所以验证者可以直接检查它。
Let us recap the entire flow in diagram form:
让我们以图表的形式回顾一下整个流程：
Now, let's get back to one thing I left out here: the matrix multiplication layers.
现在，让我们回到我在这里遗漏的一件事：矩阵乘法层。
It turns out that there is a fairly easy way to generate weights that represent the idea "multiply \(V\) by a matrix \(M\) that only combines values that are within the same batch of 16, and then evaluate \(VM\) at point \(p\) ".
事实证明，有一种相当简单的方法来生成权重，该权重代表“将 \(V\) 乘以矩阵 \(M\)，该矩阵仅组合同一批次 16 中的值，然后在点 \(p\) 处评估 \(VM\)”。
There is also a fairly easy way to evaluate the polynomial generated by those weights at some other point \(q\) without actually needing to compute \(M\) (cryptographers seem to love Star Trek, so they sometimes say " materialize " \(M\) ).
还有一种相当简单的方法来评估这些权重在其他点 \(q\) 生成的多项式，而实际上不需要计算 \(M\) （密码学家似乎喜欢《星际迷航》，所以他们有时会说“实现”\(M\) ）。
This is important for the verifier to be able to check the link between \(V_{i-1}(p_{i-1})\) and \(V_i(p_{i-1})\) .
这对于验证者能够检查 \(V_{i-1}(p_{i-1})\) 和 \(V_i(p_{i-1})\) 之间的链接非常重要。
But there is also a much dumber way to do this, which does not lose much efficiency (in fact, it increases efficiency slightly on the prover side): just run 16 sumchecks in parallel, sharing the same randomness so they all get the same coordinates.
但还有一种更愚蠢的方法来做到这一点，它不会损失太多效率（事实上，它稍微提高了证明者方面的效率）：只需并行运行 16 个和检查，共享相同的随机性，以便它们都获得相同的坐标。
The verifier's "state" \(V_{i-1}(p_{i-1})\) will be a size-16 object, and the verifier can apply the matrix to that directly.
验证者的“状态”\(V_{i-1}(p_{i-1})\) 将是一个大小为 16 的对象，验证者可以直接将矩阵应用于该对象。
We can do a major optimization to the sumcheck above, reducing the number of sums computed and provided per round from 5 to 3.
我们可以对上面的和检查进行重大优化，将每轮计算和提供的和数从 5 个减少到 3 个。
This happens from two sources.
这种情况的发生有两个来源。
First, because we know the verifier can check \(sum_0 + sum_1\) against the previous total, we can instead take out \(x_1\) , and ask the verifier to just compute \(sum_1 = total - sum_0\) themselves.
首先，因为我们知道验证者可以根据之前的总数检查 \(sum_0 + sum_1\) ，所以我们可以取出 \(x_1\) ，并要求验证者自己计算 \(sum_1 = Total - sum_0\) 。
A second, more involved optimization is usually called Gruen's trick .
第二种更复杂的优化通常称为 Gruen 技巧。
Let us go back to the definition of the matrix \(W\) .
让我们回到矩阵 \(W\) 的定义。
Here is some python code for computing it:
下面是一些用于计算它的Python代码：
Let's first focus on the first round.
我们首先关注第一轮。
Notice that the only part of this calculation that depends on the first coordinate is the very last step.
请注意，此计算中唯一依赖于第一个坐标的部分是最后一步。
What happens if the prover computes \(V^3 * W\) using a half-sized version of \(W\) where we just skip the last step?
如果证明者使用 \(W\) 的一半大小版本来计算 \(V^3 * W\)，而我们只是跳过最后一步，会发生什么？
Here are the \(W_{half}\) and \(W\) for our example above (derived from \(p = [2, 7, 18]\) ), side by side:
这是上面示例中的 \(W_{half}\) 和 \(W\) （源自 \(p = [2, 7, 18]\) ），并排：
As with our earlier example, this is just \([[(1-7) * (1-18), (1-7) * 18], [7 * (1-18), 7 * 18]]\) , modulo 89.
与我们之前的示例一样，这只是 \([[(1-7) * (1-18), (1-7) * 18], [7 * (1-18), 7 * 18]]\) ，模 89。
The evaluations of \(W\) at some \(x\) can be found by taking \(W_{half}\) and multiplying in \(x * c + (1-x) * (1-c)\) where \(c\) is the current evaluation point (in this case, the \(2\) from \([2, 7, 18]\) ).
可以通过取 \(W_{half}\) 并乘以 \(x * c + (1-x) * (1-c)\) 来找到 \(W\) 在某些 \(x\) 处的评估，其中 \(c\) 是当前评估点（在本例中为 \([2, 7, 18]\) 中的 \(2\) ）。
At \(x=0\) , this just means multiplying by \(1 - 2 = -1\) (modulo 89), and you should be able to visually check that the front face of the right cube is exactly that.
在 \(x=0\) 处，这仅意味着乘以 \(1 - 2 = -1\) （模 89），并且您应该能够直观地检查右侧立方体的正面是否正是如此。
You can do the same thing with linear combinations of \(W\) : given the sum \(hsum_x = sum(V_{31}^3(x, ...) * W_{half}(...))\) , you can multiply it by \(x * c + (1-x) * (1-c)\) to get the "real sum" \(sum_x = sum(V_{31}^3(x, ...) * W_{31}(x, ...))\) .
您可以使用 \(W\) 的线性组合做同样的事情：给定总和 \(hsum_x = sum(V_{31}^3(x, ...) * W_{half}(...))\) ，您可以将其乘以 \(x * c + (1-x) * (1-c)\) 以获得“真实总和” \(sum_x = sum(V_{31}^3(x, ...) * W_{31}(x, ...))\) 。
This is another way to allow the prover to send four values instead of five: because \(W_{half}\) is independent of the current dimension, its evaluation will be the same for the top half of \(V\) and the bottom half, and for that matter for the extension \(V(2, ...)\) .
这是允许证明者发送四个值而不是五个值的另一种方式：因为 \(W_{half}\) 独立于当前维度，所以其评估对于 \(V\) 的上半部分和下半部分以及扩展 \(V(2, ...)\) 来说是相同的。
This means that, in the current dimension, \(V^3 * W_{half}\) is only degree-3 (and not degree-4), and so you only need four values ( \(hsum_0 ...
这意味着，在当前维度中，\(V^3 * W_{half}\) 仅为 3 度（而不是 4 度），因此您只需要四个值 ( \(hsum_0 ...
hsum_3\) ) to compute \(hsum_c\) with Lagrange coefficients.
hsum_3\) ) 用拉格朗日系数计算 \(hsum_c\)。
To check against the previous total, the verifier would check if \(hsum_0 * (1 - c) + hsum_1 * c = total\) .
为了检查之前的总数，验证者将检查是否 \(hsum_0 * (1 - c) + hsum_1 * c = 总数\) 。
But even better, we can combine the two tricks to let the prover only send three values !
但更好的是，我们可以结合这两个技巧，让证明者只发送三个值！
We do this by allowing the verifier themselves to compute \(hsum_1 = \frac{total - hsum_0 * (1 - c)}{c}\) .
我们通过允许验证者自己计算 \(hsum_1 = \frac{total - hsum_0 * (1 - c)}{c}\) 来做到这一点。
A third, smaller, optimization is that when \(r_i\) is not zero, we don't need to handle it inside the sumcheck; instead, the verifier can simply subtract it from \(V_i(p_i)\) at the appropriate time.
第三个较小的优化是，当 r_i 不为零时，我们不需要在和检查中处理它；相反，验证者可以在适当的时候简单地从 \(V_i(p_i)\) 中减去它。
The next source of optimization comes from moving to the real version of Poseidon2, where ¾ of the layers only cube one value per round.
下一个优化来源来自迁移到 Poseidon2 的真实版本，其中 3/4 层每轮仅立方一个值。
This means that 15 out of 16 values in each round stay the same.
这意味着每轮 16 个值中有 15 个保持不变。
Unfortunately, we can't skip doing a sumcheck over them entirely, because if the evaluation point for the cubed value shifts from \(p_i\) to \(p_{i-1}\) , we need to shift the evaluation point for the other values as well.
不幸的是，我们不能完全跳过对它们进行求和检查，因为如果立方值的评估点从 \(p_i\) 转移到 \(p_{i-1}\) ，我们也需要移动其他值的评估点。
But the good news is that (with Gruen's trick) it's only a linear sumcheck.
但好消息是（使用格鲁恩的技巧）它只是一个线性和检查。
The even better news is that you can batch it: you can prove \(sum(V_{(i, 1)}) ...
更好的消息是你可以批量处理它：你可以证明 \(sum(V_{(i, 1)}) ...
sum(V_{(i, 15)})\) by proving \(sum(\sum_{j=1}^{15} V_{(i,j}) * \alpha ^ j)\) for some random \(\alpha\) .
sum(V_{(i, 15)})\) 通过证明 \(sum(\sum_{j=1}^{15} V_{(i,j}) * \alpha ^ j)\) 对于一些随机 \(\alpha\) 。
Thus, most of the prover's work is just computing the random linear combination \(\sum_{j=1}^{15} V_{(i,j}) * \alpha ^ j\) .
因此，证明者的大部分工作只是计算随机线性组合 \(\sum_{j=1}^{15} V_{(i,j}) * \alpha ^ j\) 。
\(V_{(i,0)}\) gets cubed, so it does have to be handled with a cubic sumcheck (but sharing the same randomness), but this is now a much smaller cost.
\(V_{(i,0)}\) 被立方，所以它必须用立方和检查来处理（但共享相同的随机性），但现在成本要小得多。
You can find some sample code implementing these algorithms here: https://github.com/ethereum/research/tree/master/gkr
您可以在这里找到一些实现这些算法的示例代码：https://github.com/ethereum/research/tree/master/gkr
One thing that I threw under the rug in the above analysis is that in this whole example, the verifier is working with the full list of inputs and outputs "in the clear".
在上面的分析中，我隐藏的一件事是，在整个示例中，验证器正在“明确”地处理输入和输出的完整列表。
For such a protocol as written to be secure, this means that the verifier would have to hash that entire list to generate the Fiat-Shamir randomness.
对于这样一个安全的协议，这意味着验证者必须对整个列表进行哈希处理才能生成 Fiat-Shamir 随机性。
Thus, to receive a proof of the evaluations of \(N\) hashes, the verifier would have to compute...
因此，要接收\(N\)哈希值的评估证明，验证者必须计算......
\(N\) hashes.
\(N\) 个哈希值。
In a real-world protocol, no one is interested in the evaluations of lots of hashes in isolation.
在现实世界的协议中，没有人对孤立地评估大量哈希值感兴趣。
Instead, the idea is to prove the hashes, and then expose the set of hash inputs and hash outputs as a " lookup table " that can be used to prove some bigger computation that includes those hashes.
相反，其想法是证明哈希值，然后将哈希输入和哈希输出集公开为“查找表”，可用于证明包含这些哈希值的一些更大的计算。
For this, you could "just use FRI ".
为此，您可以“仅使用 FRI”。
The verifier needs to get a proof of \(V_{32}(p_{32})\) and \(V_0(p_0)\) , which would turn into a linear combination over the values encoded in the commitments.
验证者需要获得 \(V_{32}(p_{32})\) 和 \(V_0(p_0)\) 的证明，这将变成承诺中编码的值的线性组合。
This can be done, and is certainly much faster than proving the hashes inside the FRI.
这是可以做到的，而且肯定比在 FRI 内证明哈希值要快得多。
An alternative is to use polynomial commitment schemes that are native to multilinear polynomials.
另一种方法是使用多线性多项式固有的多项式承诺方案。
A common one is BaseFold , though there have been other more recent improvements (eg.
常见的一个是 BaseFold ，尽管最近还有其他改进（例如。
WHIR .
呼呼。
Realistically, the choice depends on what proof system you are using for the non-hash part of your computation.
实际上，选择取决于您为计算的非哈希部分使用的证明系统。
One important security consideration is an observation from 2025 : if the circuit being proved can also compute the Fiat–Shamir hash used to derive challenges fast enough within its own depth , a malicious prover might be able to predict challenges, and thus cheat the proof system.
一个重要的安全考虑因素是 2025 年的观察：如果被证明的电路还可以计算用于在其自身深度内足够快地导出挑战的 Fiat-Shamir 哈希，则恶意证明者可能能够预测挑战，从而欺骗证明系统。
This is not an issue for using GKR to prove hashes as in the example above, because (i) the scheme is designed around one fixed circuit that does not create room for an attacker to use these tricks, and (ii) the attack involves feeding GKR a circuit that internally computes both a hash and other computation, and so by definition there is not enough depth in a hash-only circuit to execute it.
对于使用 GKR 来证明哈希值（如上例所示）来说，这不是问题，因为（i）该方案是围绕一个固定电路设计的，不会为攻击者使用这些技巧创造空间，并且（ii）攻击涉及向 GKR 提供一个内部计算哈希值和其他计算的电路，因此根据定义，仅哈希电路中没有足够的深度来执行它。
However, for more complicated and general-purpose GKR use cases, it is an issue; one mitigation is to adjust the hash used to compute Fiat-Shamir challenges so that it requires more rounds to compute than the number of rounds the circuit has.
然而，对于更复杂和通用的 GKR 用例，这是一个问题；一种缓解措施是调整用于计算 Fiat-Shamir 挑战的哈希值，使其需要的计算轮数多于电路的轮数。
Let's continue to focus on the proving Poseidon hashes use case.
让我们继续关注证明 Poseidon 哈希用例。
Here is a spreadsheet I made that tallies up all the costs a demo implementation that I made :
这是我制作的电子表格，它统计了我制作的演示实施的所有成本：
Roughly a 15x theoretical overhead (!!).
大约是理论开销的 15 倍 (!!)。
This compares to a ~100x theoretical overhead for proving Poseidon with traditional STARKs.
相比之下，使用传统 STARK 证明 Poseidon 的理论开销约为 100 倍。
The gains come from the fact that the largest costs of the traditional STARK proof (see my prover here , see the "regular STARK" tab of my theorycraft spreadsheet here ) come from hashing and FFT 'ing the trace that consists of all intermediate values (though there is a clever trick that allows the proof to only require one trace value per inner round).
收益来自于这样一个事实：传统 STARK 证明（请参阅此处的证明者，请参阅此处的理论技术电子表格的“常规 STARK”选项卡）的最大成本来自对由所有中间值组成的迹线进行散列和 FFT（尽管有一个巧妙的技巧，允许证明每个内轮只需要一个迹值）。
Hence, we don't have to do any of that at all: the prover is only committing to the input and the output, for everything in the middle the prover is only doing a (much lighter) sumcheck at each round, and for linear work (ie.
因此，我们根本不必做任何事情：证明者仅提交输入和输出，对于中间的所有内容，证明者仅在每轮进行（更轻的）和检查，并且对于线性工作（即。
matmul) the prover needs to do nothing at all .
matmul）证明者根本不需要做任何事情。
But these numbers are just theory.
但这些数字只是理论。
There are two practical reasons why practice might differ from theory, that pull in opposite directions:
实践可能与理论不同，有两个实际原因，它们的方向相反：
And on top of this, there is the possibility that one or the other just happens to be harder to optimize in a given software or hardware context.
除此之外，在给定的软件或硬件环境中，其中一个或另一个可能更难优化。
Does my implementation match up with the theory?
我的实现与理论相符吗？
Well, let's see:
好吧，让我们看看：
Under 10x!!!
低于 10 倍！！！
Though I would not take this number as the "true overhead" either; it most likely means that my implementation of the raw execution is under-optimized.
尽管我也不会将这个数字视为“真正的开销”；这很可能意味着我对原始执行的实现优化不足。
Now, there still are some optimizations we have not tried.
现在，还有一些优化我们还没有尝试过。
Particularly, you can adjust the sumcheck so that the "hypercube" is an unbalanced prism, where the first dimension has a size larger than 2.
特别是，您可以调整和检查，使“超立方体”成为不平衡棱柱，其中第一个维度的尺寸大于 2。
This makes the first round larger, but makes all subsequent rounds smaller; the tradeoff is fine because in the first round \(V\) is in the base KoalaBear prime field whereas in later rounds everything is in the extension field, which is much more expensive.
这使得第一轮变大，但使所有后续轮变小；这种权衡很好，因为在第一轮中 \(V\) 位于基本 KoalaBear 素数域中，而在后面的轮次中，所有内容都位于扩展域中，这要昂贵得多。
If you're hashing larger amounts of data, you could also give up on the 2→1 structure, and hash eg.
如果您要散列大量数据，您也可以放弃 2→1 结构，并进行散列，例如。
4→1 or even more; as the width increases, the overhead of GKR approaches zero (!!!).
4→1个甚至更多；随着宽度的增加，GKR 的开销接近于零（！！！）。
Hence, proving hashes with single-digit overhead is very possible.
因此，用个位数的开销证明哈希值是很有可能的。
In this post, hashes were just an example; GKR is a family of techniques that is well-suited for proving many kinds of computations .
在这篇文章中，哈希只是一个例子； GKR 是一系列非常适合证明多种计算的技术。
If a computation can be expressed in the "batch and layers" format, where each layer can be expressed as a low-degree polynomial, then GKR can be applied directly.
如果计算可以用“批次和层”格式表示，其中每层可以表示为低次多项式，则可以直接应用 GKR。
But even if there are cross-interactions between different values in a large computation, there are often tricks that can be used.
但即使在大型计算中不同值之间存在交叉交互，通常也有可以使用的技巧。
This is relevant for proving LLM inference, and many other situations.
这与证明 LLM 推理和许多其他情况相关。
Most provers that strive for very high efficiency and very low overhead are going to use something like GKR in some form.
大多数追求极高效率和极低开销的证明者都会以某种形式使用 GKR 之类的东西。