前面的文章主要讨论了STARK背后的数学原理，主要讨论了如何将计算语句转换为多项式约束，如何将检查多项式约束转换到检查多项式的低度性，同时介绍了一种有效的低度测试方式
接下来介绍如何利用概率证明和密码学Hash函数来构造STARK
Scalable Transparent Arguments
我们的目标是构建以恶搞STARk，是一个可扩展、透明的加密论证（Argument）
首先来考虑计算完整性（CI）的密码证明，这意味着对于一个程序$\boldsymbol A$，输入为$x$，输出为$y$，时间界限为$T$，我们希望生成一个证明$\boldsymbol \pi$来证明下列陈述
$\boldsymbol A(x)$在$T$个计算步骤内会输出$y$
任何（有效的）程序都无法对虚假的陈述给出一个有效的证明，这一要求对于更一般的CI也应当适用（比如某些情况下$\boldsymbol A$有一个辅助的额外输入）
回顾一下之前介绍的STARK的两个重要的性质
- Scalability：可扩展性代表生成证明的时间为$T\cdot polylog(T)$，而验证的时间仅为$polylog(T)$，且$\boldsymbol \pi$的长度为$polylog(T)$
换句话说，生成证明串$\boldsymbol \pi$的开销不应该比执行原始计算大很多，而验证的开销应当比执行原始计算快得多，证明串$\boldsymbol \pi$的长度也应当比原始计算的长度短得多
- Transparency：系统中用于生成和验证证明的全局参数妹有陷门
这个性质与需要可信方生成某些公共参数形成对比，因为可信方生成公共参数时会随机选择某些秘密参数来作为陷门，从而影响系统的安全性
和之前提到的一样，STARK只使用了轻量级对称加密（密码学hash函数），这不仅提高了系统的计算效率，且就目前而言，这个方案是后量子安全的，因为其安全性不依赖于公钥加密（公钥加密开销又大，又不能抗量子）
Roadmap for this post
对于STARK，我们需要下列两个组件
- 可通过随机的，开销小的本地检查进行验证的长证明
- 密码学Hash函数，比如SHA-256或Keccak
不严谨的说，第一个组件提供了Scalability，而第二个组件提供了Transparency，且两者不冲突，接下来的内容会逐步介绍如何利用这两个组件构建协议
- 首先描述Micali的构造，其背后利用的证明系统为PCP
- 其次分析一下Micali的构造是如何提供Scalability和Transparency的
- 第三步描述了交互式Oracle证明（IOP）的概念，这个概念是对PCP的概括，并支持涉及更高效的协议，同时还分析了之前的文章中提到的算术化和低度测试如何实现IOP的
- 最后介绍一下BCS构造，其实Micali构造的扩展，BCS构造使用了IOP更一般的概念，而不是PCP，高效的STARK都是通过BCS构造获得的
Cryptographic proof from PCP,via the Micali construction
PCP是一种证明系统，通过对长证明进行随机局部检查来确定CI Statement的正确性，具体如下
给定CI Statement：$(\boldsymbol A,x,y,T)$，PCP Prover生成一个证明串$\Psi$，该证明串是对CI Statement和执行轨迹的编码
尽管$\Psi$比需要$T$步的执行轨迹还要长（$\Psi$的长度与$T$是拟线性的），但是$\Psi$有一个特点，其可以通过概率测试，读取$\Psi$的很少一部分进行验证，也即给定相同的CI Statement：$(\boldsymbol A,x,y,T)$，PCP Verifier只需要随机检查$\Psi$的很少一部分（很少指的是一个与$T$无关的一个常量，比如3）就可以输出接受或是拒绝，Verifier的检查过程可以是本地进行且高效的，形象一点描述就是下面这个图
回想一下，我们的要求是提供的证据$\boldsymbol \pi$不仅要短，还要验证快，这与PCP有很大的区别，因为PCP的证明串$\Psi$很大，如何将$\Psi$转换到$\boldsymbol \pi$呢
有个简单的方法，我们可以让Prover先生成随机性$\rho$，并根据$\rho$选择$\Psi$中要检查的点，然后利用$\rho$和这些点生成$\boldsymbol \pi$并交给Verifier，根据PCP的特点，Verifier只需要检查$\Psi$中少数的点就可以判断是否接受，而使用的随机性也是固定长度的，因此得到的$\boldsymbol \pi$是很小的，此时Verifier再根据$\boldsymbol \pi$中的$\rho$去检查$\Psi$中的对应的点即可
但是这个方案有个缺点，如果Prover是恶意的，其生成的$\rho$很有可能不是随机的，而是其精心选择的，根据这个$\rho$在$\Psi$上找到的点可以通过验证，而$\Psi$上其余的点都无法通过验证
因此需要用到密码学Hash函数来解决这个问题，比如使用SHA-256或以上的安全Hash函数来生成随机性，从而使得Prover无法作弊，具体来看看如何完成
首先Prover利用Hash函数$H$将长证明$\Psi$承诺到一颗Merkle Tree，记该Merkle Tree的树根为$rt$，将$rt$作为$H$的输入并得到随机性$\rho$，由于$H$是安全的Hash函数，因此将$rt$作为其输入，不仅可以确保得到的值是“随机”的，还可以确保$\rho$是在Prover对$\Psi$的承诺后生成的，接下来Prover再根据$\rho$来选择$\Psi$中需要检查的点，并将这些点包含至$\boldsymbol \pi$中，最后，Prover还需要揭示这些点的承诺，也即在$\boldsymbol \pi$中包含一个所有需要检查的点的验证路径（验证路径不仅能确保整个Merkle Tree的树根被正确计算，还可以确保$\rho$是在Prover对$\Psi$的承诺后生成的）
总而言之，简洁的$\boldsymbol \pi$实际上只包含三个部分：Merkle Tree的树根$rt$，$\Psi$中需要验证的点，以及与这些点对应的验证路径，Verifier此时可以根据来检查验证路径的值，然后根据$rt$重新计算$\rho$并验证随机性是否正确
说的有点复杂，可以看下面这个图
Transparency comes from the cryptography
Micali构造中的一个重要的特征是：生成或验证简洁证明$\boldsymbol \pi$只需要唯一的一个加密Hash函数$H$，因此选择何种$H$需要作为公开的全局参数让所有参与方都知道，选择$H$的方式有很多，这也意味着Micali的方案满足Transparency
与SNARK不同，SNARK的全局参数需要由可信方来生成，且生成过程中需要秘密参数，常见的有基于群的$G$的配对
$$ (G,\alpha \cdot G,\alpha^2\cdot G,\alpha^3\cdot G,...) $$
其中$\alpha$就是秘密参数，根据SNARK基于的密码学假设（KOE），对于不知道秘密参数的参与方是无法伪造一个正确的证明的
Scalability comes from the probabilistic proof
Micali构造中的另一个重要的特征是：生成和验证简洁证明$\boldsymbol \pi$的时间接近于生成原始证明$\Psi$的时间，这是因为与PCP操作相比，生成证明过程中需要的加密开销较少，因此Micali的开销和效率实际上取决于PCP的效率
特别地，若PCP是可扩展的（生成$\Psi$的时间与$T$是拟线性的，而验证$\Psi$的时间快得多），则Micali的构造也会得到一个可扩展的密码学证明
但是很不幸，PCP的开销很高，高到不足以在实际场景中使用，因此STARK不是基于Micali的PCP构造，相反，STARK基于另一种概率性证明，不仅可以实现可扩展性，还确保了透明性
IOPs: a new notion of probabilistic proof
高效的STARK基于一种交互式的概率证明系统（Interactive Oracle Proof System，IOPs），在该系统中，Verifier发送一些随机性$\boldsymbol \sigma_i$给Prover，之后Prover返回一个长证明$\boldsymbol \Psi_i$给Verifier，在协议结束时，Verifier再随机检查所有收到的长证明$\boldsymbol \Psi_1,\boldsymbol \Psi_2,...$，如下图所示
自2015年IOPs提出以来，学界许多研究构建了高效的IOPs的设计原则，如[BCGV16]、[BCGRS16]、[BB+16]、[BBGR16]、[BCFGRS16]、[BBHR17]、[BBHR18]、[BCRSVW18]、[BKS19]、[BGKS19]，STARK中使用的IOP协议与[BBHR18]相关
Prior posts describe an efficient IOP
接下来介绍如何将算术化和低度测试转化为有效的IOPs
上图是IOPs的示意图，协议的第一阶段是算术化，将给定的CI Statement：$(\boldsymbol A,x,y,T)$转换为某个度受限的多项式问题，第二阶段是低度测试，用于测试第一阶段生成的多项式
- 算术化（图中蓝色部分）：Prover和Verifier将程序$\boldsymbol A$转换为一系列的多项式约束，然后Prover运行计算$(\boldsymbol A,x,y,T)$并得到一个$T$步的执行轨迹
然后需要将执行轨迹编码以得到一个编码轨迹$\Phi$，Prover将$\Phi$发送给Verifier（发送$\Phi$前无需从Verifier处获得任何随机性），之后Verifier返回随机性$\sigma_0$，这个随机性会使Prover和Verifier将所有的多项式约束绑定至单一的多项式约束
之后Prover将这个单一的多项式约束与编码轨迹结合在一起，得到合成多项式$\Xi$并发送给Verifier，Verifier本地检查$\Phi$和$\Xi$的相关性，当且仅当CI Statement为真时，$\Xi$和$\Phi$都是低度的，此时Verifier会以极高的概率接受
- 低度测试（图中黄色部分）：Prover利用FRI协议来使得Verifier相信$\Xi$和$\Phi$都是低度的，这个过程涉及到一个协议，协议中Verifier每轮发送一些随机性$\sigma_i$给Prover，然后Prover根据随机性返回一些辅助证据$\Psi_i$，协议结束时Verifier利用本地随机性检查$\Xi$和$\Phi$以及所有收到的$\Psi_i$，若FRI协议中Verifier以很高的概率接受，则$\Xi$和$\Phi$都具有预期的度，从而CI Statement为真
Cryptographic Proof via the BCS construction
通过BCS构造也可以获得有效的STARK，BCS将IOPs与密码学Hash函数结合在一起以获得密码学上的证明，这个构造实际上是对Micali构造的扩展，不仅保留了可扩展性和透明性，还提高了效率