代码实现可参见：
https://github.com/ksju6561/Transparent-SNARKs-from-DARK-Compilers 视频解说：
https://www.youtube.com/watch?v=m3Cc0kuzhfg 1）本文为单变量多项式和多变量多项式构建了新的polynomial commitment scheme——DARK polynomial commitment scheme：
该scheme的evaluation proof size为O ( log ( n ) ) O(\log(n))O(log(n))的，verification time也为O ( log ( n ) ) O(\log(n))O(log(n))，其中n nn为polynomial中系数的个数。 底层的技术称为DARK (Diophantine Argument of Knowledge)，利用的是integer representations of polynomials和groups of unknown order。 基于的安全假设是strong RSA和adaptive root assumptions。 若以class groups来实例化，则无需trusted setup。 当采用a restricted class of algebraic linear IOPs时，可称为Polynomial IOPs，可实现双倍高效的public-coin interactive arguments of knowledge for any NP relation with succinct communication。 借助linear preprocessing，online verifier’s work is logarithmic in the circuit complexity of the relation。
2）在Sonic (Maller等人2019年论文《Sonic: Zero-knowledge snarks from linear-size universal and updatable structured reference strings》) 和 PLONK (Gabizon等人2019年论文《Plonk: Permutations over lagrangebases for oecumenical noninteractive arguments of knowledge》) 的基础上，构建了SNARK算法——Supersonic：
具有quasi-linear preprocessing，quasi-linear (online) prover time, logarithmic communication, and logarithmic (online) verification time in the circuit size。 120-bit security场景下，对于具有100万个gates的circuit，Supersonic的proof size为10KB，verification time低于100ms。 Supersonic为transparent的，无需trusted setup。 通过在polynomial commitment scheme中增加hiding 变量来实现zero-knowledge evaluation。 Supersonic为第一个完整的zk-SNARK system，具有实用的prover time和近似logarithmic proof size and verification time。
interactive proofs (IPs)的源头：
1985年Goldwasser等人论文《The knowledge complexity of interactive proof-systems (extended abstract)》。 probabilistically checkable proofs (PCPs)的源头：
1991年Babai等人论文《Checking computations in polylogarithmic time》。（最早的Polynomial IOPs (PIOPs)） 1992年Arora等人论文《Proof verification and hardness of approximation problems》。 proof system的一些要素：
a prover establishes the correct performance of an arbitrary computation in a way that can be verified much more efficiently than performing the computation itself。 succinct：prover和verifier之间的communication cost应为low，如protocol transcript应小于witness size。 zero-knowledge：the computation may involve secret information and the prover demonstrates correct performance without leaking the secrets。如Ben-Or等人1988年论文《Everything provable is provable in zero-knowledge》中的ZK-IPs和Kilian 1992年论文《A note on efficient zero-knowledge proofs and arguments (extended abstract)》中的ZK-PCPs。 最近几年，有来自verifiable outsourced computation (such as trustless cloud computing) 的工业需求（如Walfish等人2015年论文《Verifying computations without reexecuting them: From theoretical possibility to near practicality》）。 在区块链中使用zero-knowledge proofs来平衡privacy 和 public-verifiable integrity（如ZCash中的anonymous transactions （参见Ben-Sasson等人2014年论文《Zerocash: Decentralized anonymous payments from bitcoin》、Hopwood等人2019年论文《Zcash Protocol Specification》）和以太坊中对smart contracts over private inputs的verify（如Zokrates）。在这些应用中，会将zero-knowledge proofs作为交易的一部分也记录在账本中，同时要求节点可在短时间内verify many proofs。因此，对succinctness和fast verification会有要求。 Vitalik Buterin 2016年提出的Zk rollup 中使用verifiable computation来实现区块链交易扩容。 O(1) Labs 2018年提出的 Coda protocol 中希望消除对历史区块链数据的维护。
SNARGs (succinct non-interactive arguments) 的要点：
succinctness (the proof size is sublinear in the original computation length T TT)。 non-interactivity (the proof is a single message)。 prover-scalability (proof generation time scales linearly or quasi-linearly in T TT)。 verifier-scalability (verification time is sublinear in T TT)。 目前来看，succinct statistically sound proofs是似乎不存在的。
构建proof system需要平衡的元素有：
proof size； proof time； verification time; 不同的trust model； 不同的cryptographic assumption。 如有些proof system可借助a one-time expensive setup procedure 的preprocessing model来生成compact verification key V K VKVK，使得Verifier在后续验证proof时的效率更高。
考虑proof size和verification time，迄今为止效率最高的proof system都需要trusted preprocessing。 基于GGPR扩展的pairing-based SNARKs有：[GGPR13, SBV+13, BCI+13, BCG+13, Gro16]
[GGPR13] Gennaro等人2012年论文《Quadratic span programs and succinct NIZKs without PCPs》 [SBV+13] Setty等人2013年论文《Resolving the conflict between generality and plausibility in verified computation》 [BCI+13] Bitansky等人2012年论文《Succinct noninteractive arguments via linear interactive proofs》 [BCG+13] Ben-Sasson等人2013年论文《SNARKs for C: Verifying program executions succinctly and in zero knowledge》 [Gro16] Groth 2016年论文《On the size of pairing-based non-interactive arguments》（在https://github.com/zkcrypto/bellman 中有相应代码实现。） 通过在a committee of parties中运行multi-party computation (MPC)，可实现相应的trusted setup——只需保证其中的一方是可信任的就足够了。在Zcash中已构建了2次这样的trusted setup仪式—— The design of the ceremony。
当proof system中不需要任何的trusted setup，则可称其为transparent的：
Ben-Sasson等人2019年论文《Scalable zero knowledge with no trusted setup》中提出的zk-STARKs 算法，其proof size 为O ( log 2 T ) O(\log^2T)O(log 2 T)，其中T TT为circuit size。 Goldwasser等人2008年论文《Delegating computation: interactive proofs for muggles》中的GKR protocol可构建interactive proof，communication cost为O ( d log T ) O(d\log T)O(dlogT)，适于low-depth circuit of total size T TT and depth d dd。 以上这些transparent proof system的性能远远低于 SNARKs based on preprocessing。以100万gate的circuit为例，zk-STARKs的proof size为600KB，而基于preprocessing的SNARKs仅需200bytes（Groth 2016年论文《On the size of pairing-based non-interactive arguments》）。Bulletproofs也是transparent proof system，Bulletproofs的proof size要小于STARK的proof size，但是Bulletproofs的verification time与circuit size呈线性关系，对于100万gate的circuit，Bulletproofs的verification time需要将近1分钟，比STARK的verification time慢1000倍。