为了让从 R1CS 到 QAP 的转换不那么抽象，我们来看一个真实的例子。
假设我们要对以下算术电路进行编码
将其转换为秩 1 约束系统后，变为
我们需要为将要进行操作的有限域选择一个特征值。当我们稍后将其与椭圆曲线结合时，我们的素数域的阶需要等于椭圆曲线的阶。（这两者不匹配是一个非常常见的错误）。
但现在，为了便于管理，我们将选择一个较小的数字。我们选择素数 79。
首先，我们定义矩阵 、 和 如下：
import numpy as np
# 1, out, x, y, v1, v2, v3
L = np.array([
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, -5, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1],
])
R = np.array([
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
])
O = np.array([
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, -1, 0],
])
为了验证我们正确构建了 R1CS（手动操作时很容易出错！），我们创建一个有效的 witness 并进行矩阵乘法运算：
x = 4
y = -2
v1 = x * x
v2 = v1 * v1 # x^4
v3 = -5*y * y
z = v3*v1 + v2 # -5y^2 * x^2
# witness
a = np.array([1, z, x, y, v1, v2, v3])
assert all(np.equal(np.matmul(L, a) * np.matmul(R, a), np.matmul(O, a))), "not equal"
Python 中的有限域算术
下一步是将它转换为一个域数组。在 Numpy 中进行模运算会变得非常混乱，但使用 galois 库则非常直观。这在我们关于有限域的文章中已经介绍过，但这里简要回顾一下如何使用它：
import galois
GF = galois.GF(79)
a = GF(70)
b = GF(10)
print(a + b)
# prints 1
我们不能向它传递像 GF(-1) 这样的负值，否则会抛出异常。要将负数转换为它们在域中的同余表示，我们可以将曲线的阶加到它们上面。为了避免正值“溢出”，我们对其取曲线阶的模。
L = (L + 79) % 79
R = (R + 79) % 79
O = (O + 79) % 79
我们的新矩阵是
## New values of L, R, O
'''
L
[[ 0 0 1 0 0 0 0]
[ 0 0 0 0 1 0 0]
[ 0 0 0 74 0 0 0]
[ 0 0 0 0 0 0 1]]
R
[[ 0 0 1 0 0 0 0]
[ 0 0 0 0 1 0 0]
[ 0 0 0 1 0 0 0]
[ 0 0 0 0 1 0 0]]
O
[[ 0 0 0 0 1 0 0]
[ 0 0 0 0 0 1 0]
[ 0 0 0 0 0 0 1]
[ 0 1 0 0 0 78 0]]
'''
现在，我们只需用 GF 将它们包裹起来，就可以将它们转换为域数组。我们还需要重新计算我们的 witness，因为它包含负值。
L_galois = GF(L)
R_galois = GF(R)
O_galois = GF(O)
x = GF(4)
y = GF(-2 + 79) # we are using 79 as the field size, so 79 - 2 is -2
v1 = x * x
v2 = v1 * v1 # x^4
v3 = GF(-5 + 79)*y * y
out = v3*v1 + v2 # -5y^2 * x^2
witness = GF(np.array([1, out, x, y, v1, v2, v3]))
assert all(np.equal(np.matmul(L_galois, witness) * np.matmul(R_galois, witness), np.matmul(O_galois, witness))), "not equal"
有限域中的多项式插值
现在，我们需要将矩阵的每一列转换为一个用于对该列进行插值的 galois 多项式列表。我们将要插值的点是 x = [1,2,3,4]，因为我们有 4 行。
def interpolate_column(col):
xs = GF(np.array([1,2,3,4]))
return galois.lagrange_poly(xs, col)
# axis 0 is the columns.
# apply_along_axis is the same as doing a for loop over the columns and collecting the results in an array
U_polys = np.apply_along_axis(interpolate_column, 0, L_galois)
V_polys = np.apply_along_axis(interpolate_column, 0, R_galois)
W_polys = np.apply_along_axis(interpolate_column, 0, O_galois)
如果我们再次查看矩阵的内容，我们预期 U_polys 和 V_polys 的前两个多项式为零，并且 W_polys 的第一列也为零。
我们运行以下合理性检查：
print(U_polys[:2])
print(V_polys[:2])
print(W_polys[:1])
# [Poly(0, GF(79)) Poly(0, GF(79))]# [Poly(0, GF(79)) Poly(0, GF(79))]# [Poly(0, GF(79))]
项 Poly(0, GF(79)) 仅仅是一个所有系数均为零的多项式。
鼓励读者在 R1CS 中的对应值处对多项式进行求值，以验证它们是否正确地插值了矩阵的值。
计算 h(x)
我们已经知道 将是 ，因为有四行。
提醒一下，这是 Quadratic Arithmetic Program 的公式。向量 是 witness：
每一项都是将 witness 与列插值多项式求内积。也就是说，每个求和项实际上是 和 之间的内积。
def inner_product_polynomials_with_witness(polys, witness):
mul_ = lambda x, y: x * y
sum_ = lambda x, y: x + y
return reduce(sum_, map(mul_, polys, witness))
term_1 = inner_product_polynomials_with_witness(U_polys, witness)
term_2 = inner_product_polynomials_with_witness(V_polys, witness)
term_3 = inner_product_polynomials_with_witness(W_polys, witness)
为了计算 ，我们只需对其进行求解。注意，除非我们有一个有效的 witness，否则无法计算 ，不然就会产生余数。
# t = (x - 1)(x - 2)(x - 3)(x - 4)
t = galois.Poly([1, 78], field = GF) * galois.Poly([1, 77], field = GF) * galois.Poly([1, 76], field = GF) * galois.Poly([1, 75], field = GF)
h = (term_1 * term_2 - term_3) // t
与 numpy 中的 poly1d 不同，galois 库不会向我们指示是否存在余数，因此我们需要检查 QAP 公式是否仍然成立。
assert term_1 * term_2 == term_3 + h * t, "division has a remainder"
上面执行的检查与验证者将要检查的内容非常相似。
当我们在 trusted setup（可信设置）的隐藏点上计算多项式时，上述方案将不起作用。然而，执行 trusted setup 的计算机仍然需要执行上述许多计算。
总结
在本文中，我们展示了用于将 R1CS 转换为 QAP 的 Python 代码。
通过 RareSkills 了解更多
本材料摘自我们的零知识证明课程。