关于succinctness我说几句：
- 任何证明系统中，Verifier的时间上限是多项式时间；Prover的时间上限要么不限制(Prove)，要么也是多项式时间(Argument)。在传统的ZKP中，可以证明的语言类远远超过了NP，达到了PSPACE（要假设OWF存在）；假设P不等于NP（其实是更强的指数时间假设ETH），对于NPC语言的ZKP系统Prover的运行时间都必须达到输入的指数。在这种证明极为困难判定问题（hard-relation）的场景中，一个多项式大小的证明，一个依然是多项式运行时间的Verifier，验证速度相比于原始计算快多了，那么这种时候算不算已经达到了succinctness？我觉得算。
- 当然，在zk-SNARKs场景下，Prover的运行时间也是多项式时间，证明的语言不超过NP(对于NPC语言witness要通过辅助输入)，甚至在很多情况下只是在证明「Verifier如果加钱买机器也能自己运算」的BPP类问题。那么在这种情况下仅仅延续使用多项式时间就不足以去描述Verifier相对于Prover计算的加速了（二者现在都是多项式时间），需要更精细的描述。
- Prover哪怕是读完输入都要|x|+|w|的时间（顺便说一句这也是Prover时间优化的下界），而Verifier可以比这个更快，所以很自然的产生了sublinear,polylog,O(1)这些更精细的描述。另一方面，证明大小也需要更精细的sublinear,polylog,O(1)这样的描述（对于NP语言的witness大小为polynomial）。上述的这几个描述是按照从弱到强的顺序。而且证明大小和验证时间在这种精细化的意义上没有必然约束关系。
- 于是组合起来就出现了9种succinctness的可能定义：证明sublinear(就是上面有人引用的[GGPR13])的定义，按照这个定义Bulletproof属于SNARK，slightly succinct)；polylog（STARK的证明大小是O(log^2(|C|)，所以如果定义succinctness是log的话STARK就不是SNARK)；O(1)。验证sublinear（比如Kilian94,Micali00等基于PCP的证明系统）；polylog；O(1)。还有证明大小+验证时间同时满足这几个条件的定义（其中双O(1)的就是Groth16/Plonk等，fully succinctness）。