Skip to content

Files

Latest commit

 

History

History
78 lines (78 loc) · 2.65 KB

2.约束系统.md

File metadata and controls

78 lines (78 loc) · 2.65 KB

1. 约束

约束是一种数学表达式,用来描述变量之间必须满足的关系
可以理解为一个等式或不等式,规定了变量应该如何相互关联

1.1 约束的形式

  • 等式约束:如 a × b = c
  • 不等式约束:如 a + b ≤ c
  • 布尔约束:如 x * (1-x) = 0(确保x只能是0或1)

1.2 约束的类型

  1. 算术约束
  • 加法约束:规定变量之间的加法关系
  • 乘法约束:规定变量之间的乘法关系
  • 线性约束:只包含变量的一次方
  • 非线性约束:包含变量的高次方
  1. 布尔约束
  • 确保变量只能取0或1
  • 描述布尔运算(AND、OR、NOT、XOR等)
  • 用于表示逻辑判断

1.3 约束的作用

  • 复杂运算转换为简单的数学关系
  • 支持零知识证明的构建
  • 保证计算的可验证性

1.4 约束系统

  1. R1CS(Rank-1 Constraint System)
  • 是一种标准的约束表示系统
  • 由三个向量(a, b, c)组成
  • 约束形式:(a·w)(b·w) = (c·w)
  • w 表示所有变量的向量
  1. 约束的组合
  • 多个约束组合成约束系统
  • 所有约束必须同时满足
  • 约束之间可能存在依赖关系

1.5 约束的应用

  1. 在哈希函数中的应用
  • 将复杂的哈希运算分解为简单约束
  • 每个基本运算(如XOR、AND)转换为约束
  • 通过约束验证哈希计算的正确性
  1. 在电路中的应用
  • 描述电路的逻辑关系
  • 确保输入输出的正确性
  • 验证电路计算的完整性

1.6 总结

约束是连接实际计算问题和零知识证明的桥梁:

  • 它们将复杂的计算问题转换为标准的数学关系
  • 提供了统一的验证方式
  • 支持零知识证明的构建
  • 确保计算的正确性和可验证性

2. 约束与门电路的关系

1. 直接映射

  • 每个逻辑门对应一组数学约束
  • 电路的连线对应约束中的变量
  • 输入输出对应约束的变量值 ##2. 具体转换
  1. AND门转换:
  • 门电路:z = x AND y
  • 约束形式:
    • x(1-x) = 0 (确保x是布尔值)
    • y(1-y) = 0 (确保y是布尔值)
    • z = x y (AND运算的约束)
  1. OR门转换:
  • 门电路:z = x OR y
  • 约束形式:
    • x(1-x) = 0
    • y(1-y) = 0
    • z = x + y - xy
  1. NOT门转换:
  • 门电路:z = NOT x
  • 约束形式:
    • x(1-x) = 0
    • z = 1 - x

3. 总结

  1. 本质关系:
  • 约束是门电路的数学抽象
  • 两者在功能上完全等价
  • 约束提供了更灵活的验证方式
  1. 实际价值:
  • 支持更复杂的证明系统
  • 便于实现零知识证明
  • 提供统一的验证框架