在Python中将R1CS转换为有限域上的二次算术程序

为了使 R1CS 到 QAP 的转换不那么抽象，让我们使用一个真实的例子。

假设我们要编码以下算术电路：

$$z = x⁴ – 5y²x²$$

转换为秩 1 约束系统，这变为：

$$\begin{align} v_1 &= xx \\ v_2 &= v_1 v_1 && //x^4\\ v_3 &= -5yy \\ -v_2 + z &= v_3 v_1 && //-5y^2 x^2\\ \end{align*}$$

我们需要选择一个特征，以便在有限域上进行。稍后，当我们将其与椭圆曲线结合时，我们的素数域的阶数需要与椭圆曲线的阶数相等。（不匹配这两者是一个很常见的错误）

但现在，我们将选择一个小数字以便于处理。我们选择素数 79。

首先，我们按如下定义我们的矩阵 $\mathbf{L}$、$\mathbf{R}$ 和 $\mathbf{O}$：

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（在手动操作时很容易出错!），我们创建一个有效的见证并进行矩阵乘法：

x = 4
y = -2
v1 = x * x
v2 = v1 * v1        # x^4
v3 = -5*y * y
z = v3*v1 + v2    # -5y^2 * x^2

## 见证
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))), "不相等"

Python 中的有限域算术

下一步是将其转换为域数组。在 Numpy 中进行模运算会变得非常麻烦，但使用 galois 库非常简单。这在我们关于有限域的文章中已经介绍过，这里是如何使用它的简要回顾：

import galois

GF = galois.GF(79)

a = GF(70)
b = GF(10)

print(a + b)
## 输出 1

我们不能给负值，例如 GF(-1)，否则它将引发异常。要将负数转换为其在域中的同余表示，我们可以将曲线的阶数加到它们上面。为了避免“溢出”正值，我们用曲线的阶数进行取模运算。

L = (L + 79) % 79
R = (R + 79) % 79
O = (O + 79) % 79

我们的新矩阵为：

### 新的 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 包装来简单地转换为域数组。同时，我们还需要重新计算我们的见证，因为它包含负值。

L_galois = GF(L)
R_galois = GF(R)
O_galois = GF(O)

x = GF(4)
y = GF(-2 + 79) # 我们使用 79 作为域大小，所以 79 - 2 是 -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))), "不相等"

有限域中的多项式插值

现在，我们需要将每个矩阵的列转换为插值列的 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 是列。
## apply_along_axis 与对列进行 for 循环并收集结果在数组中相同
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)

我们已经知道 $t(x)$ 将是 $(x – 1)(x – 2)(x – 3)(x – 4)$，因为有四行。

提醒一下，这就是二次算术程序的公式。向量 $\mathbf{a}$ 是见证：

$$ \underbrace{\sum_{i=1}^{m} a_i ui(x)}\text{项 1} \underbrace{\sum_{i=1}^m a_i vi(x)}\text{项 2} = \underbrace{\sum_{i=1}^{m} a_i wi(x)}\text{项 3} + h(x)t(x) $$

每个项都在将见证与列插值多项式进行内积。也就是说，每个求和项都是 $[a₁, …, aₘ]$ 和 $[u₁(x), …, uₘ(x)]$ 之间的有效内积。

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)

要计算 $h(x)$，我们只需为其求解。请注意，除非我们有有效的见证，否则无法计算 $h(x)$，否则将会有余数。

## 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, "除法存在余数"

上面执行的检查与验证者将检查的内容非常相似。

当我们在受信设置中的隐藏点上评估多项式时，上述方案将不起作用。然而，执行受信设置的计算机仍需执行上述许多计算。

总结

在本文中，我们展示了将 R1CS 转换为 QAP 的 Python 代码。

通过 RareSkills 深入学习

这部分材料来自我们的 零知识课程。

• 原文链接： rareskills.io/post/r1cs-...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～