Step1. Build trace （fib2-example）

标红部分为 Public info

Step2. Prover for Trace

协议参数选取：

1.AIR 实例化

2.验证AIR和Trace的一致性（Debug模式）

2.1 校验基础参数

2.2 校验assertion有效(boundary cs)

2.3 校验Trace满足transition cs（Debug module）

Transcript

3.Commit for trace

域参数选取：

3.1 Interpolate -> LDE -> evaluate over LDE-domain

3.2 Commitment

Tracescript

4.Evaluate CS

4.1 获取线性组合系数

系数个数和约束的个数一致

在本例中（fib2-example），transition cs 2 个；boundary cs 3个

4.2 为t-cs和b-cs构建evaluator

4.2.1 t-cs

4.2.2 b-cs

4.3 Evaluate t/s-cs over ce_domain

4.3.1 定义evaluator table

5 Commitment to Evaluate CS

5.1 建立constraints composition polynomial

5.2 commitment to composition poly

Example:

Compose_poly = a * x^3 + b * x^2 + c * x + d = (a * x^2 + c) * x^ + (b * x^2 + d)

(a * x^2 + c), (b *x^2 +d) 分别对应两个column

6.建立DEEP composition多项式

The general formal: f(x) = q(x)* t(x)

Need check at random z

1. f(z) = q(z) * t(z)

2. f(x),q(x),t(x) indeed equal respectively f(z), q(z), t(z)

3. calculate Deep_composition = (q(x) - q(z)) / (x - z)

4. Check LDT for q_q(x)

6.1 select z which out of domain(ood)

draw an out-of-domain point z. Depending on the type of E, the point is drawn either from the base field or from an extension field defined by E.

The purpose of sampling from the extension field here (instead of the base field) is to increase security.

6.2 evaluate trace and constraint polynomials at the OOD point z

6.2.1 trace_poly at z & z * g

6.2.2 composition poly at z

6.3 建立Deep compositon polynomial

6.3.1 产生随机数

6.3.2 cal quotient poly

6.4 evaluate Deep over LDE

7.计算Deep 的FRI Layer num

8.确定query位置

从lde_domain中选取多个query的位置。

9.构建proof对象

9.1 生成FRI proof

9.2 query trace poly at above positions

和上述类似

9.3 query constraint poly at above positions

和上述类似

9.4 构建STARK PROOF

Step3. Verify for proof

从  transcript中读取pub-info，用来获取相关的数据，以执行验证过程。

1. Ood consistency check

验证章节5.2描述的数学关系的一致性。

2. 实例化FRI-verifier对象

3.计算Deep poly on query positions

计算方式和章节6.4相同

4.执行FRI VERIFY过程

关于我们

Sin7y成立于2021年，由顶尖的区块链开发者组成。我们既是项目孵化器也是区块链技术研究团队，探索EVM、Layer2、跨链、隐私计算、自主支付解决方案等最重要和最前沿的技术。

微信公众号：Sin7Y

GitHub | Twitter | Telegram | Medium| Mirror | HackMD | HackerNoon