3.R1CS.md

1. 基本概念

R1CS是一种特殊的约束系统，用于表示计算过程中的关系。 每个约束都是秩为1的（Rank-1），这意味着约束中只包含一个乘法项。

• 由三个向量组成：a, b, c
• 一个解向量：w（包含所有变量，称为witness）
• 约束形式：(a·w)(b·w) = (c·w) 强制要求
  • 其中 "·" 表示向量点积
  • w 包含电路中的所有变量值

2. R1CS 的组成部分

2.1. 向量组成

1. 见证向量(w)：

• 包含所有变量的值
• 第一个元素通常为1（常数项）
• 包含中间计算结果
• 包含最终输出

2. 约束向量(a,b,c)：

• 每个约束对应三个向量
• 向量长度与见证向量相同
• 大多数元素为0（稀疏向量）

2. 约束特点

• 每个约束只包含一个乘法
• 可以包含多个加法
• 所有运算都在特定有限域中进行

3. R1CS 的工作原理

3.1 基本运算转换

• 加法运算：
  • 直接在向量中表示
  • 不需要额外的约束
• 乘法运算：
  • 需要专门的约束
  • 每个乘法对应一个R1CS约束

3.2 约束满足条件

• 对每个约束i：(ai·w)(bi·w) = (ci·w)
• 所有约束必须同时满足
• 验证过程检查每个约束

4. R1CS 的应用

1. 算术电路转换：

• 将算术运算转换为R1CS约束
• 保持计算关系不变

2. 逻辑电路转换：

• 将逻辑门转换为R1CS约束
• 维护布尔运算的正确性

3. 零知识证明中的应用

• 作为中间表示形式
• 连接计算问题和证明系统
• 支持高效的证明生成

5. R1CS 的优势

• 可以表示任意计算
• 支持复杂的逻辑关系
• 适合并行处理
• 约束结构简单
• 验证计算高效
• 适合大规模系统

6. 实际使用示例

1. 简单计算示例
2. 复杂运算示例

• 将复杂运算分解为基本步骤
• 每个步骤转换为R1CS约束
• 确保中间结果正确连接

7. R1CS 的局限性

• 空间复杂度
• 转换复杂度
• R1CS只支持乘法形式的约束

8. 代码示例

https://github.com/leo-shi-dacheng/cryptography/blob/master/r1cs/r1cs.go