zkSnark:将R1CS转换为QAP

Question

我正在阅读R1CS & QAP - https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649上Vitalin Buterin的页面。

我对他得到的部分很了解

A=\begin{pmatrix} 0&1&0&0&0&0 \\ 0&0&0&1&0&0 \\ 0&1&0&0&1&0 \\ 5&0&0&0&0&1 \\ \end{pmatrix}

B=\begin{pmatrix} 0&1&0&0&0&0 \\ 0&1&0&0&0&0 \\ 1&0&0&0&0&0 \\ 1&0&0&0&0&0 \\ \end{pmatrix}

C=\begin{pmatrix} 0&0&0&1&0&0 \\ 0&0&0&0&1&0 \\ 0&0&0&0&0&1 \\ 0&0&1&0&0&0 \\ \end{pmatrix}

现在，当他将R1CS转换为QAP时，他写道

也就是说，如果我们在x=1上求多项式，那么我们得到第一组向量，如果我们在x=2上求多项式，那么我们得到第二组向量，以此类推。

原始向量集A，B&C完全不是由任何x=1，x=2等创建的，它们有映射

['~one', 'x', '~out', 'sym\_1', 'y', 'sym\_2'] = [ 1, 3, 35, 9, 27, 30]

也就是说，它们是用x = 3 (即多项式x^3 + x + 5 = 35的根)计算的。

所以我不明白他怎么把这些等同于x=1，x=2等的抽样。

有人能解释一下吗？

Answer 1

首先，重要的是要理解，一个度d的多项式可以包含多少信息。它的特点是d+1图像(考虑拉格朗日多项式，以了解原因)。

所以，我们现在必须关注链接中的一个特定句子：“我们从长度为6到6的三次多项式的四组向量到六组三次多项式，在每个x坐标上的多项式表示其中的一个约束。”

这意味着每个组对应于一个特定值的多项式图像。(因为我们仲裁地决定这样解释它)，似乎惯例是考虑i^\text{th}组给出输入i的图像。

例如，如果我要计算第一个向量的第一个多项式P_{1,1}。我将计算度的P_{1,1}，最多是3，这样P_{1,1}(1)= x_1, P_{1,1}(2) = x_2, P_{1,1}(3) = x_3, P_{1,1}(4)=x_4，用x_i，i^{\text{th}}群的第一个向量的第一个坐标。

这些方程只确定一个多项式(我不确定能不能比链接中的一个做更好的解释)，但是如果你想对此有更多的了解，你可以阅读：https://en.wikipedia.org/wiki/Lagrange_多项式

更广泛地说，我们可以通过查看群的j^{\text{th}}向量的k^{\text{th}}坐标来计算k^{\text{th}}向量的D14多项式。