给出一个问题,“找出这个问题的答案”和“验证一个答案的正确性”是不同的事情。例如大数的质因数分解问题,分解出质因数很难,验证答案很容易。对数组进行排序也是一个例子。
计算理论里面对这种分离有一个更加普遍的分类叫IP,这是 Shafi Goldwasser, Silvio Micali, 和 Charles Rackoff 在1985年的开创性论文中提出的一个复杂性分类。IP指的是可以被这样一种计算模型解决的一类问题(例如SAT问题):给两台计算机 P(prover) 和 V(verifier),一个输入X(e.g. X是一个boolean formula),P可以有无限计算能力和存储,而V只有合理的计算能力和存储以及一定的随机性(随机性很重要)。P和V在有限的时间内交换一系列的消息,最终V可以通过和P的交互判定输入是否是问题的解(例如X是否是SAT)。
如果把layer1看作verifier, layer2看作prover,我们会发现layer1/2的架构和IP其实是完全一致的。layer1只有有限的计算能力,而layer2是可以无限扩展的,layer2通过消息与layer1交互,layer1通过交互验证layer2上发生的计算是正确的。数学上已经证明IP = PSPACE,而 PSPACE 是比 NP 还要大的一类问题,换句话说,数学上证明了分层架构基本可以解决我们实际应用中会遇到所有问题。
GMR的论文同时也是零知识证明协议(ZKP)的开端,这一领域在近年尤其是区块链时代得到了极大的发展,理论和可以实际应用的成果都不少。因为zkp是IP的一个子问题,所以zkp的方案用在layer1/2上也非常合适(e.g. zk rollup)。但是zero-knowledge在layer1/2的应用里面其实是多余的,这里只需要soundness/completeness,不需要zero-knowledge。
所以从研究上来说,除了ZKP,IP和可验证计算(Verifiable Computing)也是我们非常关注的,我相信后两个领域的研究也可以推动layer1/2的发展,不过我还没有发现这两个领域的比较合适的可以应用到layer2上的成果,希望有朋友可以不吝赐教。