Skip to content

Latest commit

 

History

History
148 lines (124 loc) · 3.82 KB

4.QAP.md

File metadata and controls

148 lines (124 loc) · 3.82 KB

1. QAP 基本概念

目标：将电路计算转换为多项式关系
QAP 包含三组多项式：

  • {uᵢ(x)}: 左输入多项式
  • {vᵢ(x)}: 右输入多项式
  • {wᵢ(x)}: 输出多项式

以及一个目标多项式：

  • t(x): "零化器"(vanishing polynomial)

2. 转换过程 从 R1CS 到 QAP

  • R1CS (Rank-1 Constraint System):
  • a · b = c // 向量点积形式
  • 转换为 QAP:
  • Σ(ai·ui(x)) · Σ(bi·vi(x)) = Σ(ci·wi(x)) + h(x)·t(x)
  • 其中 h(x) 是商多项式

2.1. R1CS 形式

R1CS 是一个向量点积形式：
a · b = c

例如一个简单的约束：
(2x + y) · (3x + z) = w

可以写成向量形式：
[2,1,0,0] · [3,0,1,0] = [0,0,0,1]
// 向量分别代表 x,y,z,w 的系数

2.2. QAP 转换

  1. 每个R1CS约束在特定点上求值
    比如选择点 r₁, r₂, r₃...

  1. 对每个变量位置，通过这些点构造多项式：
  • ui(x): 左边系数的插值多项式
  • vi(x): 右边系数的插值多项式
  • wi(x): 输出系数的插值多项式

2.3 具体例子

假设有约束：(2x + y) · (3x + z) = w

  1. R1CS 形式：
左向量 a = [2,1,0,0]  // 2x + y
右向量 b = [3,0,1,0]  // 3x + z
输出向量 c = [0,0,0,1]  // w
  1. QAP 形式：
// 在点 r₁ 上求值：
u₁(r₁) = 2  // x的系数
u₂(r₁) = 1  // y的系数
u₃(r₁) = 0  // z的系数
u₄(r₁) = 0  // w的系数

v₁(r₁) = 3  // x的系数
v₂(r₁) = 0  // y的系数
v₃(r₁) = 1  // z的系数
v₄(r₁) = 0  // w的系数

w₁(r₁) = 0  // x的系数
w₂(r₁) = 0  // y的系数
w₃(r₁) = 0  // z的系数
w₄(r₁) = 1  // w的系数
  1. 最终QAP等式：
(x·u₁(x) + y·u₂(x) + z·u₃(x) + w·u₄(x)) · 
(x·v₁(x) + y·v₂(x) + z·v₃(x) + w·v₄(x)) =
(x·w₁(x) + y·w₂(x) + z·w₃(x) + w·w₄(x)) + h(x)·t(x)

3. QAP 的特点

  1. 结构特点
  • 将约束转换为多项式关系
  • 允许批量验证多个约束
  • 支持高效的零知识证明
  1. 优势
  • 完备性：有效解必定满足多项式关系
  • 可靠性：满足多项式关系意味着原约束成立
  • 高效性：可以使用FFT加速计算

5. 示例代码

type QAP struct {
    U []Polynomial // 左输入多项式
    V []Polynomial // 右输入多项式
    W []Polynomial // 输出多项式
    T Polynomial   // 目标多项式
}

func ConvertR1CStoQAP(r1cs R1CS) QAP {
    numVars := len(r1cs.Variables)
    evaluationPoints := generateEvaluationPoints(numVars)
    
    // 为每个变量生成多项式
    U := make([]Polynomial, numVars)
    V := make([]Polynomial, numVars)
    W := make([]Polynomial, numVars)
    
    // 通过插值构造多项式
    for i := 0; i < numVars; i++ {
        U[i] = interpolate(evaluationPoints, r1cs.LeftInputs[i])
        V[i] = interpolate(evaluationPoints, r1cs.RightInputs[i])
        W[i] = interpolate(evaluationPoints, r1cs.Outputs[i])
    }
    
    // 构造目标多项式
    T := computeVanishingPolynomial(evaluationPoints)
    
    return QAP{U, V, W, T}
}

另外一个QAP Demo

5. 在 Groth16 中的应用

func GenerateProof(qap QAP, witness []Fr) Proof {
    // 1. 计算多项式组合
    A := evaluatePolynomials(qap.U, witness)
    B := evaluatePolynomials(qap.V, witness)
    C := evaluatePolynomials(qap.W, witness)
    
    // 2. 检查QAP关系
    // A * B = C + h * t
    h := computeQuotient(A, B, C, qap.T)
    
    // 3. 生成零知识证明
    proof := createZKProof(A, B, C, h)
    
    return proof
}

6. 验证过程

func VerifyQAP(qap QAP, proof Proof) bool {
    // 1. 检查多项式关系
    // e(A,B) = e(C,g) * e(T,H)
    
    lhs := pair(proof.A, proof.B)
    rhs := pair(proof.C, g) * pair(qap.T.Evaluate(), proof.H)
    
    return lhs == rhs
}