STARK – 深度解析

Step1. Build trace (fib2-example)

STARK - 深度解析

标红部分为 Public info

STARK - 深度解析

Step2. Prover for Trace

协议参数选取:

STARK - 深度解析

1.AIR 实例化

STARK - 深度解析

2.验证AIR和Trace的一致性(Debug模式)

2.1 校验基础参数

STARK - 深度解析

2.2 校验assertion有效(boundary cs)

STARK - 深度解析

2.3 校验Trace满足transition cs(Debug module)

STARK - 深度解析

Transcript

STARK - 深度解析

3.Commit for trace

域参数选取:

STARK - 深度解析

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

STARK - 深度解析

3.2 Commitment

STARK - 深度解析

Tracescript

STARK - 深度解析

4.Evaluate CS

4.1 获取线性组合系数

STARK - 深度解析

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

在本例中(fib2-example),transition cs 2 个;boundary cs 3个

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

4.2.1 t-cs

STARK - 深度解析

4.2.2 b-cs

STARK - 深度解析

4.3 Evaluate t/s-cs over ce_domain

4.3.1 定义evaluator table

STARK - 深度解析

5 Commitment to Evaluate CS

5.1 建立constraints composition polynomial

STARK - 深度解析

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

STARK - 深度解析

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

STARK - 深度解析

STARK - 深度解析

6.2.2 composition poly at z

STARK - 深度解析

6.3 建立Deep compositon polynomial

6.3.1 产生随机数

STARK - 深度解析

6.3.2 cal quotient poly

STARK - 深度解析

6.4 evaluate Deep over LDE

STARK - 深度解析

7.计算Deep 的FRI Layer num

STARK - 深度解析

STARK - 深度解析

8.确定query位置

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

STARK - 深度解析

9.构建proof对象

9.1 生成FRI proof

STARK - 深度解析

STARK - 深度解析

9.2 query trace poly at above positions

和上述类似

STARK - 深度解析

9.3 query constraint poly at above positions

和上述类似

STARK - 深度解析

9.4 构建STARK PROOF

STARK - 深度解析

Step3. Verify for proof

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

1. Ood consistency check

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

STARK - 深度解析

2. 实例化FRI-verifier对象

STARK - 深度解析

3.计算Deep poly on query positions

计算方式和章节6.4相同

4.执行FRI VERIFY过程

STARK - 深度解析

STARK - 深度解析

关于我们

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

微信公众号:Sin7Y

GitHub:Sin7Y

Twitter:@Sin7Y_Labs

Medium:Sin7Y

Mirror:Sin7Y

HackMD:Sin7Y

HackerNoon:Sin7Y

Email:contact@sin7y.org

本文由用户:麦妖榜 发布,不代表网站的立场,转转请注明出处:http://www.maiyaotop.com/hangye/126396.html

发表评论

登录后才能评论