通用 ZK — 电路与 R1CS

日期: 2026-11-29 方向: 零知识证明 / ZK理论 阶段: Phase 4 - ZK基础理论 (Day 209-222) 标签: #ZK #R1CS #算术电路 #AIR #约束系统

---

今日目标

---

一、算术电路 vs 布尔电路

1.1 布尔电路

变量 ∈ {0, 1}，门 ∈ {AND, OR, NOT, XOR}。GMW、Yao 协议基于布尔电路。

问题：电路规模爆炸（一次 SHA-256 ~ 24K AND gates → 24K constraint × hash overhead）。

1.2 算术电路

变量 ∈ $\mathbb{F}_p$（大素域），门 ∈ {+, ×, scalar mul}。

优势：

• 单个加/乘 = 1 门；模运算自然
• 与多项式承诺友好（Lagrange、FFT）
• 大数运算高效（128-bit 单元 vs bit-level）

SNARK 系统几乎都用算术电路。

---

二、R1CS 形式化定义

2.1 定义

R1CS 由三个 $m \times n$ 矩阵 $(A, B, C)$ 和 witness 向量 $\vec{z} = (1, x_{\text{pub}}, x_{\text{priv}}) \in \mathbb{F}_p^n$ 构成。

$\vec{z}$ 满足该 R1CS 当且仅当：

$$ \boxed{(A \vec{z}) \circ (B \vec{z}) = C \vec{z}} $$

其中 $\circ$ 是 Hadamard（逐元素）乘积。展开：

$$ \forall i \in [m]: \left(\sum_j A_{ij} z_j\right) \cdot \left(\sum_j B_{ij} z_j\right) = \sum_j C_{ij} z_j $$

每行是一个 rank-1 约束：左 = (linear)·(linear)，右 = linear。

2.2 为什么是 rank-1？

任意算术电路可以 "flatten" 成一系列形如 $a \cdot b = c$ 的 gate（每个乘法门一行）。加法不需要新约束（用 linear combination 嵌入）。

关键事实：每条 R1CS 行精确对应电路中一个乘法门。加法是"自由的"。

2.3 完整工作流

Computation
   ↓ (encode)
Arithmetic Circuit
   ↓ (flatten)
R1CS  =  (A, B, C, ⟨pub, priv⟩)
   ↓ (Lagrange)
QAP   =  (A(X), B(X), C(X), Z(X))
   ↓ (commit)
SNARK proof

---

三、例子 1：$x^2 + x = 12$（求 $x$）

3.1 数学

陈述：$\exists x$ s.t. $x^2 + x = 12$，$x = 3$ 是解。

3.2 Flatten 为 gate-by-gate

引入中间变量：

• $w_1 = x \cdot x$（乘法门）
• $\text{out} = w_1 + x$（加法，无需 R1CS 行）
• 约束 $\text{out} = 12$

实际只一个乘法门和一个最终输出约束。

3.3 Witness 向量编排

约定 $\vec{z} = (1, \text{out}, x, w_1)$，$n = 4$。

• $z_0 = 1$（约定第 0 位）
• $z_1 = \text{out}$（公开输入）
• $z_2 = x$（私有 witness）
• $z_3 = w_1$（中间变量）

代入 $x = 3$：$\vec{z} = (1, 12, 3, 9)$

3.4 R1CS 矩阵

约束 1：$x \cdot x = w_1$

$$ A_1 \vec{z} = z_2 = x \quad B_1 \vec{z} = z_2 = x \quad C_1 \vec{z} = z_3 = w_1 $$

$$ A_1 = (0, 0, 1, 0),\ B_1 = (0, 0, 1, 0),\ C_1 = (0, 0, 0, 1) $$

约束 2：$1 \cdot (w_1 + x) = \text{out}$

$$ A_2 \vec{z} = 1,\ B_2 \vec{z} = w_1 + x = z_3 + z_2,\ C_2 \vec{z} = \text{out} = z_1 $$

$$ A_2 = (1, 0, 0, 0),\ B_2 = (0, 0, 1, 1),\ C_2 = (0, 1, 0, 0) $$

3.5 矩阵汇总

$$ A = \begin{pmatrix} 0 & 0 & 1 & 0 \ 1 & 0 & 0 & 0 \end{pmatrix},
B = \begin{pmatrix} 0 & 0 & 1 & 0 \ 0 & 0 & 1 & 1 \end{pmatrix},
C = \begin{pmatrix} 0 & 0 & 0 & 1 \ 0 & 1 & 0 & 0 \end{pmatrix} $$

验证 $\vec{z} = (1, 12, 3, 9)$：

• 约束 1：$(3) \cdot (3) = 9$ ✓
• 约束 2：$(1) \cdot (9 + 3) = 12$ ✓

---

四、AIR — STARK 用的约束形式

4.1 动机

R1CS 适合 SNARK（多项式承诺），但 STARK 用 execution trace + transition constraints。

4.2 定义（简化）

• Trace：$T \times w$ 矩阵，$T$ 为时间步数，$w$ 为列数（registers）
• Boundary constraints：起始/终止约束（如 $T[0][0] = x_0$）
• Transition constraints：相邻行的多项式关系，$P(T[i], T[i+1]) = 0\ \forall i$
• Periodic constraints：周期性约束（用于 round constants）

4.3 例：Fibonacci

trace 列：$(a_i, b_i)$，转移：$a_{i+1} = b_i,\ b_{i+1} = a_i + b_i$

转移约束（多项式形式）： $$ P_1: T[i+1][0] - T[i][1] = 0 $$ $$ P_2: T[i+1][1] - T[i][0] - T[i][1] = 0 $$

边界约束：$T[0][0] = 1, T[0][1] = 1$。

4.4 R1CS vs AIR 对比

---

五、代码 — R1CS 数据结构

"""
r1cs.py — R1CS 表示与 witness 检查
"""
from typing import List
import numpy as np

class R1CS:
    def __init__(self, n_vars: int, var_names: List[str]):
        self.n = n_vars
        self.var_names = var_names
        self.A = []  # list of rows
        self.B = []
        self.C = []

    def add_constraint(self, a_row, b_row, c_row):
        assert len(a_row) == self.n
        assert len(b_row) == self.n
        assert len(c_row) == self.n
        self.A.append(a_row)
        self.B.append(b_row)
        self.C.append(c_row)

    def matrices(self):
        return np.array(self.A), np.array(self.B), np.array(self.C)

    def check(self, z: List[int], modulus: int = 0):
        """检查 (Az) ∘ (Bz) == Cz"""
        A, B, C = self.matrices()
        z_vec = np.array(z)
        Az = A @ z_vec
        Bz = B @ z_vec
        Cz = C @ z_vec
        if modulus > 0:
            Az %= modulus; Bz %= modulus; Cz %= modulus
            lhs = (Az * Bz) % modulus
            return np.array_equal(lhs, Cz)
        else:
            return np.array_equal(Az * Bz, Cz)

    def pretty(self):
        print(f"R1CS with {len(self.A)} constraints, {self.n} variables")
        print(f"Variables: {self.var_names}")
        for i, (a, b, c) in enumerate(zip(self.A, self.B, self.C)):
            la = " + ".join(f"{x}*{n}" for x, n in zip(a, self.var_names) if x)
            lb = " + ".join(f"{x}*{n}" for x, n in zip(b, self.var_names) if x)
            lc = " + ".join(f"{x}*{n}" for x, n in zip(c, self.var_names) if x)
            print(f"  C{i}: ({la or '0'}) * ({lb or '0'}) = ({lc or '0'})")

# ========== Example: x^2 + x = 12 ==========
def build_x_squared_plus_x():
    """vars: (1, out, x, w1)"""
    r = R1CS(4, ["1", "out", "x", "w1"])
    # x * x = w1
    r.add_constraint([0,0,1,0], [0,0,1,0], [0,0,0,1])
    # 1 * (w1 + x) = out
    r.add_constraint([1,0,0,0], [0,0,1,1], [0,1,0,0])
    return r

# ========== Example: SHA-256 simplified compression (3 round) ==========
def build_simple_3op():
    """证明: 知道 a, b, c 使得 (a + b) * c = 21"""
    # vars: (1, out, a, b, c, sum_ab)
    r = R1CS(6, ["1", "out", "a", "b", "c", "sum_ab"])
    # 1 * (a + b) = sum_ab
    r.add_constraint([1,0,0,0,0,0], [0,0,1,1,0,0], [0,0,0,0,0,1])
    # sum_ab * c = out
    r.add_constraint([0,0,0,0,0,1], [0,0,0,0,1,0], [0,1,0,0,0,0])
    return r

# ========== Example: Boolean check (x ∈ {0,1}) ==========
def build_boolean(x):
    """证明: x 是 0 或 1
       约束: x * (1-x) = 0  即  x*x - x = 0  →  x*x = x
       vars: (1, x, x_sq)
    """
    r = R1CS(3, ["1", "x", "x_sq"])
    # x * x = x_sq
    r.add_constraint([0,1,0], [0,1,0], [0,0,1])
    # x * 1 = x_sq  (强制 x_sq == x → x ∈ {0, 1})
    r.add_constraint([0,1,0], [1,0,0], [0,0,1])
    return r

if __name__ == "__main__":
    # Test 1: x^2 + x = 12
    print("=== x^2 + x = 12 ===")
    r1 = build_x_squared_plus_x()
    r1.pretty()
    z = [1, 12, 3, 9]
    print(f"witness {z} valid? {r1.check(z)}")
    z_bad = [1, 12, 4, 16]  # 4^2 + 4 = 20 ≠ 12
    print(f"witness {z_bad} valid? {r1.check(z_bad)}")

    print("\n=== (a+b)*c = 21 ===")
    r2 = build_simple_3op()
    r2.pretty()
    # a=2, b=5, c=3 → (2+5)*3 = 21
    print(f"witness valid? {r2.check([1, 21, 2, 5, 3, 7])}")

    print("\n=== boolean(x) ===")
    r3 = build_boolean(1)
    r3.pretty()
    print(f"x=0: {r3.check([1, 0, 0])}")
    print(f"x=1: {r3.check([1, 1, 1])}")
    print(f"x=2: {r3.check([1, 2, 4])}  (应为 False)")

预期输出：

=== x^2 + x = 12 ===
R1CS with 2 constraints, 4 variables
  C0: (1*x) * (1*x) = (1*w1)
  C1: (1*1) * (1*x + 1*w1) = (1*out)
witness [1, 12, 3, 9] valid? True
witness [1, 12, 4, 16] valid? False
...

---

六、协议关系图

  ┌────────────────────────────────────┐
  │  Front-end:                        │
  │   Circom / Halo2-DSL / Cairo / Noir│
  │   写电路 (类似 if/else/loop)       │
  └────────────────┬───────────────────┘
                   │ compile
  ┌────────────────▼───────────────────┐
  │  Mid-level:                        │
  │   R1CS  (Groth16/PlonK)            │
  │   AIR   (STARK)                    │
  │   Custom gates (Halo2/PlonK)       │
  └────────────────┬───────────────────┘
                   │ encode
  ┌────────────────▼───────────────────┐
  │  Back-end:                         │
  │   QAP → Groth16 proof              │
  │   plookup tables → PlonK           │
  │   Polynomial IOP → STARK           │
  └────────────────────────────────────┘

---

七、Witness 与 Public Inputs 的关系

z = (1 ║ x_pub ║ x_priv)
       └公开┘ └────私有────┘
verifier 知道 x_pub, 检查 proof
prover  知道 (x_pub, x_priv), 生成 proof

R1CS 把"公开 vs 私有"反映在 witness 向量的分块；verifier 只需 verify 该向量满足 $A,B,C$ 关系即可。

---

八、历史与论文

---

九、应用对应

---

十、常见陷阱

1. Under-constrained 电路：缺约束让 witness 多解，prover 可"取巧"通过（最常见漏洞，导致 ZK 协议被破）。e.g., 漏写 boolean check
2. Aliasing：变量复用导致 implicit constraint，难审计
3. 过度约束：不该有的约束让合法 witness 失效（DoS）
4. 变量数 vs 约束数：witness size = $n$（变量），proof gen 复杂度通常 $O(n \log n)$ 或 $O(n)$
5. Public inputs 顺序：prover/verifier 必须一致，否则 hash 后 challenge 不匹配

---

十一、关键速查

---

十二、面试题

Q1: R1CS 中为什么每行只有"1 个乘法"？

A1: 任何算术电路可 flatten 为 SSA-like 表示：每行 $a \cdot b = c$。加法/线性组合"免费"嵌入 $A, B, C$ 行向量。这种规范形式（rank-1 quadratic）使得后续 Lagrange 插值产生最简单的 QAP。

Q2: 把 $x^3 = 8$ 转 R1CS？

A2: 引入中间 $w = x \cdot x$（约束 1：$x \cdot x = w$），$\text{out} = w \cdot x$（约束 2：$w \cdot x = \text{out}$），再约束 $\text{out} = 8$（$1 \cdot 8 = \text{out}$）。共 3 行（其中第 3 行可以是 boundary 处理）。

Q3: 如何在 R1CS 表达 $x \in {0, 1}$？

A3: 加约束 $x \cdot (1 - x) = 0$，即 $A=(0,1,...), B=(1,-1,...), C=(0,0,...)$。这是最常用的 boolean check。

Q4: R1CS vs AIR 在 zkVM 中各自的优势？

A4: R1CS：通用，灵活；缺点是循环/重复 trace 需要 unroll，电路膨胀。AIR：天然适合 VM execution trace，转移约束高效复用，proof 时间与 trace 大小近线性，常数小；但表达不规则计算时不如 R1CS 灵活。zkSync 早期 R1CS、新版用 boojum AIR-like；StarkNet 全 AIR；Risc Zero 用 AIR。

Q5: under-constrained 漏洞为什么常见？举一例？

A5: 因为电路 DSL 让 dev 像写代码一样思考，忽略了"未约束 = 任意值"。例：写 signal x; x <-- a / b; 但忘了 x * b === a，攻击者可让 $x$ 为任意值。Tornado Cash early version 曾差点中招；Aleo 也有审计案例。修复方式：每个 <-- 都配 ===。

---

十三、明日预告

Day 213 — QAP（Quadratic Arithmetic Program）：用 Lagrange 插值把 R1CS 矩阵转多项式，每个约束变多项式根，整个 R1CS 检查变 polynomial divisibility — 这是 Groth16 的代数核心。