Concept：zk-stark vs zk-snark\r\n谈到ZKP算法，大伙可能听过一些，比如zk-snark，zk-stark, bulletproof， aztec， plonk等等。今天，咱就给大伙聊聊这一双 名义昆季 ，zk-stark和zk-snark算法的异同之处。

不如，先让咱们从称号提及？ 毕竟，两个看起来都很利害的亚子^_^ ！

如下图所示，咱们将称号zk-stark 和 zk-snark根据功能特质分散分红四个部分，然后一一比较分析。

\r\nZk-stark => zk - s t ark\r\n\r\n\tzk：零学问，标明阴事的输入将会被袭击，除了解说者，其他任何人不会看见；\r\n\ts：可扩张的，和Replay Computation的考据耗时比较，zk-stark的解说和考据耗期间别与之呈拟线性关连和对数关连；\r\n\tt：透明的，zk-stark算法莫得CRS setup by Trusted party；\r\n\targ：学问论证，惟一清晰private input的prover，能力生成灵验的proof；\r\n\r\nZk-snark => zk - s n ark\r\n\r\n\tzk：零学问，标明阴事的输入将会被袭击，除了解说者，其他任何人不会看见；\r\n\ts：浅薄的，指的是生成的proof鼓胀小和考据期间鼓胀短；\r\n\tn：非交互式的，Prover生成解说的流程中庸verifier莫得交互；\r\n\targ：学问论证，惟一清晰private input的prover，能力生成灵验的proof；\r\n\r\nCompare\r\n\r\n\t疏浚点\r\n\r\n\r\n\t都兑现了将阴事的输入可靠袭击；\r\n\t都是基于学问论证，不清晰private input的prover生成不了灵验的proof；\r\n\t都不错兑现交互式与非交互式式的算法，只是取决于randomness是由谁来生成的；\r\n\r\n\r\n\t不同点\r\n\r\n\r\n\tzk-stark具有可扩张性，即解说和考据的耗时与原始计较的耗期间别呈拟线性关连（且线性因子为常量）和对数关连，这意味这，淌若原始输入的数据集增大1000000倍，zk-stark的解说耗时增多线性倍数的期间，但考据期间只是增多21*log1000000 =~ 420倍。解说耗时呈线性关连基本餍足通盘的ZKP算法，然而考据期间呈对数关连，仅此一家，因此在扩张性上，zk-stark要胜一筹。\r\n\tzk-stark相通具有浅薄性，然而是考据浅薄性。所谓浅薄性，持续是指即使考据圭表很大，生成的proof size也不会很大，同期又能很快的完成考据（比native computation快好多）。比较对zk-snark，zk-stark的proof size要大的多，因此在浅薄性上，zk-snark要胜一筹。\r\n\r\nALG compare\r\n前边从认识上对zk-stark 和 zk-snark算法做了比较，其异同点不错朦胧的详细为：\r\n\r\n\t都是基于学问论证的ZKP算法；\r\n\tzk-stark不需要zk-snark的Trusted party 确立CRS，因此是Transparent；\r\n\tzk-stark的考据耗时与native computation 耗时呈对数关连，因此是Scalable；\r\n\r\n底下，咱们将从算法层面，去做相对更真切一些的比较分析：\r\n\r\n\tzk-snark ALG 【4】\r\n\r\n\r\n\t算法思惟：将解说CI statement培植问题退换成解说多项式等式培植问题，退换流程用到了算术环路和QAP措施；\r\n\t多项式等式培植意味着什么？（图中黄色部分）\r\n\r\n\t等式双方不错看作两个度相等的多项式，假定为n，其交点最多有n个，假如在一个很大的域限度内赶紧选一个点，淌若的两个多项式在此点的值相等，则解说两个多项式是相等的。\r\n\t咱们不错看到，等式右边的多项式因子Z是盘算多项式，它的零点即是右边举座多项式的零点，也即是等式左边举座多项式的零点，而等式左边的多项式在这些零点的取值，就退换成了一个个的算术电路里每个乘诀窍对应的一阶线性抑遏等式（R1CS）培植，即原始计较等式培植（注：R1CS由原始计较等式领悟获得）；\r\n\r\n\r\n\t算法分为三个法子，CRS生成；解说者解说；考据者考据；\r\n\t不错看到prover生成解说流程中，莫得与考据者交互，因此是non-interative;\r\n\t若何保证prover用于生成解说的A/B/C/H是多项式且是小于某个度数呢？\r\n\r\n\t通过trusted party 来保证，因为它是确实任的，因此它生成pk,vk用到的A/B/C等细则是多项式而况是小于某个度的；\r\n\t淌若解说者作歹，那么考据者将会很概况率考据失败；\r\n\t主要用到了同态加密HH和统共学问假定KCA和椭圆弧线双线性配平等数学学问；\r\n\r\n\r\n\r\n\r\n\r\n\tzk-stark ALG  【1】【2】【3】\r\n\r\n\r\n\t算法思惟：将解说CI statement培植问题滚动成解说多项式小于某个度的问题，退换流程用到了多项式插值措施；\r\n\t多项式等式培植意味着什么？（图中黄色部分）\r\n\r\n\t思惟与zk-snark一样，T相通为盘算多项式，其零点已知且公开，亦然等式左侧多项式Q的零点，多项式Q在每一个零点的取值都对应了一个execute trace的培植（没错，在zk-stark中，原始计较语句滚动成了多个execute trace，这访佛与zk-snark中的R1CS）。因此多项式相等，意味着execute trace 正确，讲明原始CI培植。\r\n\r\n\r\n\t多项式小于某个度意味着什么？\r\n\r\n\t和zk-snark访佛的是，两者都把CI statement退换成了解说多项式等式培植的问题（？不错这样抽象的合计，zk-stark不仅要解说多项式相等，还要解说相应多项式是小于某个度的，这是zk-stark算法的中枢，是以才有了第极少的神色）。为了防护考据者作歹，必须要保证多项式是低于某个度的（？存在这样一种可能，攻击者不错成心生成餍足考据等式的一些点，这些点并不是确实的多项式上的点，然而根据这些点生成的字据也能通过考据者考据）。不同的是，zk-snark使用了trusted party机制 和 同态加密等数学措施，而zk-stark使用了低度测试等数学措施。当且仅当多项式确实的小于某个度时，多项式的相等才是真实兴味上的相等，讲明生成轨迹多项式的execute trace 是正确的，即原始CI培植。\r\n\r\n\r\n\t算法分为两大法子，算术化和低度测试；\r\n\r\n\t算术化：是把问题滚动为多项式体式\r\n\t低度测试：是解说组合多项式(图中黄色)和轨迹多项式（图中绿色）小于某个固定的度-->FRI算法\r\n\r\n\r\n\t在生成解说的流程中，有交互（图中红线所示），是以图中神色的是交互式的零学问解说算法；\r\n\r\n\r\nSummary\r\n以上分散从认识和算法上先容了zk-snark和zk-stark算法的异同之处，行动引文，后续发文将真切认真价绍zk-stark算法的旨趣。如有额外，缺乏品评指正，谢谢。\r\nAppendix\r\n\r\n\tV神三部曲，含泪拜读 https://vitalik.ca/general/2017/11/09/starks_part_1.html\r\n\tzk-stark论文 chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https://eprint.iacr.org/2018/046.pdf\r\n\tstarkware官方老师系列 https://medium.com/starkware/stark-math-the-journey-begins-51bd2b063c71\r\n\tzk-snark论文 chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https://eprint.iacr.org/2013/879.pdf