Specification for Marlin

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