R1CS

零知識證明算法Marlin是基於R1CS的證明系統，給定係數矩陣參I=(F,n,m,A,B,C)和一組有效賦值z=(x,w)∈ ，其中x為公開的信息，即Instance； w為私有的信息，即，witness。如果有： Az∘Bz=Cz成立，則說明R1CS成立。

Transition into Polynomial (efficiency）

Prepare

Define polynomial

1.為向量定義多項式（LDE） ，滿足在群H上值與向量一致，其中群H的階和向量長度相等(假設都為n )，即有：

增加了b 個冗餘點，不暴露w 的任何信息。

2. 為向量z = (x, w) 定義多項式（LDE）

3. 為矩陣A, B, C 定義多項式（Holographic）
為了減小verifier計算的複雜度（見paper5.2.1 ），這裡用了一個特殊的形式來表示矩陣，以上述示例的矩陣A 為例：

定義：

其中是矩陣的第k個非零值在矩陣中的行索引， ϕ−1(tk)：[|H|]→H">： 把索引映射到計算域上， 是矩陣第k個非零值，被整除。

Linearity check

現在，我們為在H上的每一個元素乘一個因子r(α,X) ，那為了保證平衡，我們應當為項乘一個因子r(α,X) ，如下圖所示：

可以看出，當多項式t(X)取遍H值時，滿足：

同樣，也可以從公式推導：

即，如果能證明，多項式在群的累積為0，則說明之間的Linearity關係成立

AHP for R1CS

Common

給定多項式：

計算多項式滿足：

生成隨機多項式：

Prover

=>Prover

=>Oracle

=>Prover - sumcheck-1

=> Oracle

=> Prover - sumcheck-1

=> Prover - sumcheck-2

=> Oracle

=> Prover - sumcheck-2

=> Prover - sumcheck-3

=> Oracle

=> Prover - sumcheck-3

Verifier

=> Verifier- sumcheck-3

=> Verifier- sumcheck-2

Recall the equality

=> Verifier- sumcheck-1

Recall the equality

=> Verifier

Polynomial commitment

協議總共進行了三輪交互，每輪交互承諾的多項式，以及query的點如下：

Optimization

Sum(s(X)) = 0

生成隨機多項式：

Reduce sumcheck

根據COS20. Claim6.7 （Fractal）論⽂提到的優化，我們令：

Common

Prover

Verifier

Reduce polynomial numbers for Sumcheck - 2

對三個矩陣的現行校驗，壓縮成對一個矩陣的校驗，即：

對這個多項式進行稀疏矩陣的表示。

矩陣多項式，從9個縮減為3個。

Set b = 1

令b = 1

Final Procotol

Marlin in arkworks

引用

關於我們

Sin7Y成立於2021年，由頂尖的區塊鏈開發者和密碼學工程師組成。我們既是項目孵化器也是區塊鏈技術研究團隊，探索EVM、Layer2、跨鏈、隱私計算、自主支付解決方案等最重要和最前沿的技術。

微信公眾號：Sin7Y

GitHub：Sin7Y

Twitter：@Sin7Y_Labs

Medium：Sin7Y

Mirror：Sin7Y

HackMD：Sin7Y

HackerNoon：Sin7Y

Email：contact@sin7y.org