Skip to content

Latest commit

 

History

History
163 lines (146 loc) · 4.56 KB

6.线约束.md

File metadata and controls

163 lines (146 loc) · 4.56 KB

1. 线约束的基本概念

  • 线约束的目的：证明不同门之间连线上的信号值相等
  • 例如：门A的输出 = 门B的输入

例如电路：

  • 门1: a + b = c (加法门)
  • 门2: c * d = e (乘法门) 其中门1的输出c与门2的输入c必须相等

2. 置换映射原理

2.1 信号编号

给每个信号位置分配唯一编号：

  • left[i]: 第i个门的左输入 (编号范围: 0 ~ n-1)
  • right[i]: 第i个门的右输入 (编号范围: n ~ 2n-1)
  • out[i]: 第i个门的输出 (编号范围: 2n ~ 3n-1)

例如 n=4 的电路：

  • left: [0,1,2,3]
  • right: [4,5,6,7]
  • out: [8,9,10,11]

2.2 编号规则

对于第i个门:

  • 左输入编号 = i
  • 右输入编号 = i + 4
  • 输出编号 = i + 8

2.3 置换表示

如果门1的输出(编号8)连接到门2的左输入(编号1)：

  • 原始序列: [0,1,2,3, 4,5,6,7, 8,9,10,11]
  • 置换后: [0,8,2,3, 4,5,6,7, 1,9,10,11]
# 1. 每个门的编号是固定的
门1 = {
    "左输入": 0,  # 第1个门的左输入固定为0
    "右输入": 4,  # 第1个门的右输入固定为4
    "输出": 8     # 第1个门的输出固定为8
}

门2 = {
    "左输入": 1,  # 第2个门的左输入固定为1
    "右输入": 5,  # 第2个门的右输入固定为5
    "输出": 9     # 第2个门的输出固定为9
}

# 2. 当我们说"8连接到1"时，实际上是在说：
# - 门1的输出值(编号8)
# - 要传递给门2的左输入位置(编号1)
  • 置换σ表示了这种连接关系：σ(8)=1, σ(1)=8

3. 累加器多项式

目标：证明不同位置的信号值相等，同时保持零知识性 方法：使用随机数构造累加器，使得相等的信号产生相等的累加值

3.1 基本原理

  1. 选择随机数β,γ
  2. 为每个位置i计算: acc[i] = (index[i] + β * value[i] + γ)
  3. 构造累加器多项式: P(X) = ∏(acc[i])
  4. 如果两个位置的信号相等，则它们的acc值也相等

3.2 示例计算

假设有两个相等的信号：

  • 位置i: index=8, value=5
  • 位置j: index=1, value=5

  • acc[i] = 8 + β*5 + γ
  • acc[j] = 1 + β*5 + γ

如果这两个信号确实相等，则:

  • P(X) = P'(X) (P'是置换后的累加器多项式)

3.3 安全性保证

  1. 随机数β,γ确保:
  • 攻击者无法预测acc值
  • 不同位置的不相等信号几乎不可能产生相同的acc值
  1. 位置编号index确保:
  • 即使信号值相等，不同位置也会产生不同的acc值
  • 除非这确实是一个有效的连接

3.4 完整的验证流程

# 1. 原始序列的累加器多项式
P(X) = (index[0] + β*value[0] + γ) * 
       (index[1] + β*value[1] + γ) * 
       ... * 
       (index[n] + β*value[n] + γ)

# 2. 置换后序列的累加器多项式
P'(X) = (index[σ(0)] + β*value[0] + γ) * 
        (index[σ(1)] + β*value[1] + γ) * 
        ... * 
        (index[σ(n)] + β*value[n] + γ)

# 3. 验证
如果所有连接都正确，则 P(X) = P'(X)

3.5 关键特性

  1. 零知识性：
  • β,γ的随机性保护了具体的信号值
  1. 绑定性：
  • 不同的信号值几乎不可能产生相同的acc值
  1. 完备性：
  • 正确的连接一定会通过验证
  1. 可靠性：
  • 错误的连接通过验证的概率可忽略

4. 具体实现

type PermutationArgument struct {
    // 1. 置换映射
    Sigma []int   // σ(i) 表示位置i连接到的位置
    
    // 2. 置换多项式
    S1 *Polynomial // 左输入置换
    S2 *Polynomial // 右输入置换  
    S3 *Polynomial // 输出置换
    
    // 3. 累加器多项式
    Z *Polynomial  // 累积乘积多项式
}

// 4. 构造累加器
func BuildAccumulator(
    indices []int,
    values []Fr,
    beta Fr,
    gamma Fr,
) *Polynomial {
    acc := make([]Fr, len(indices))
    for i := 0; i < len(indices); i++ {
        // acc[i] = index[i] + β*value[i] + γ
        acc[i].Mul(&values[i], &beta)
        acc[i].Add(&acc[i], &indices[i])
        acc[i].Add(&acc[i], &gamma)
    }
    return NewPolynomial(acc)
}

5. 验证过程

5.1 证明者

  1. 计算原始累加器多项式 P(X)
  2. 计算置换后的累加器多项式 P'(X)
  3. 证明 P(X) = P'(X)

5.2 验证者

  1. 检查累加器多项式承诺
  2. 验证评估点处 P(z) = P'(z)
  3. 验证除法证明

6. 特殊情况处理

6.1 公开输入

公开输入的线约束需要特殊处理：

  1. 分配固定的编号
  2. 在累加器中使用特殊的系数

6.2 常量门

常量门的线约束：

  1. 不参与置换
  2. 使用特殊的累加器计算方式

6.3 未使用的线

某些门的输入/输出未连接：

  1. 自循环置换(σ(i)=i)
  2. 使用特殊值填充