R1CS

Rank-1 Constraint System (R1CS) 是一种数学形式，用于表达和约束问题中的计算逻辑。它通常被用在零知识证明（如 zk-SNARK 和 zk-STARK）中，用来对一个计算过程进行建模，并确保计算过程的正确性。简单来说，R1CS 是一组多项式等式约束。

$a*b=c$

c 是与变量相关的线性表达式。它被称为“Rank-1”，因为每个约束中仅包含一项乘积。

以下是通过简单计算公式展示R1CS的构造和验证过程。

问题

验证以下计算是否正确： $z = x \cdot y + x$ 其中：

• $x$ 和 $y$ 是输入值；
• $z$ 是计算结果。

---

步骤 1：引入中间变量

为了将公式分解成简单的步骤，我们引入一个中间变量 $w_1$，使得：

1. $w_1 = x \cdot y$
2. $z = w_1 + x$

步骤 2：构造R1CS约束

R1CS要求每个约束必须符合以下形式： $a \cdot b = c$ 其中，$a$、$b$、$c$ 是线性表达式。

根据公式，我们构造以下约束：

1. $x \cdot y = w_1$
   • 转化为 R1CS 形式： $(x) \cdot (y) = w_1$
2. $w_1 + x = z$
   • 转化为 R1CS 形式： $(w_1 + x) \cdot (1) = z$

步骤 3：转化为矩阵形式

R1CS还可以用约束矩阵表示。定义：

• 变量向量：$V = [1, x, y, w_1, z]$ （包括常数1）。
• 每个约束对应三个向量 $A$、$B$、$C$，满足： $(A \cdot V) \cdot (B \cdot V) = (C \cdot V)$

第一个约束：$x \cdot y = w_1$

• $A = [0, 1, 0, 0, 0]$ （表示变量 $x$）。
• $B = [0, 0, 1, 0, 0]$ （表示变量 $y$）。
• $C = [0, 0, 0, 1, 0]$ （表示变量 $w_1$）。

第二个约束：$w_1 + x = z$

• $A = [0, 0, 0, 1, 1]$ （表示 $w_1 + z$）。
• $B = [1, 0, 0, 0, 0]$ （常数 1）。
• $C = [0, 0, 0, 0, 1]$ （表示变量 $z$）。

步骤 4：验证一个实例

假设：

• $x = 2$，$y = 3$；
• 计算结果 $z = 2 \cdot 3 + 2 = 8$。

验证步骤：

1. 计算中间变量：$w_1 = x \cdot y = 2 \cdot 3 = 6$。
2. 检查约束：
   • 第一个约束：$x \cdot y = w_1 \Rightarrow 2 \cdot 3 = 6$，成立。
   • 第二个约束：$w_1 + x = z \Rightarrow 6 + 2 = 8$，成立。

因此，约束系统验证通过，证明计算正确。