3. 通用的计算过程证明

问题：创建程序 POC_PROVE(P,I) -> (O, Q) 以及 POC_VERIFY(P,O,Q) -> {0, 1} ，使得 POC_PROVE 以 I 为输入运行程序 P ，可以返回程序输出 O 以及一段计算过程证明 Q ；当 POC_VERIFY 以 P 、O 、Q 为输入时，可输出结果，表明 Q 和 O 是不是 POC_PROVE 算法使用程序 P 生成出来的。

现状：大量理论进展和实际进展。

这个基本上就是说，要构建一个 SNARK（或者 STARK 或 SHARK，等等）。而且我们已经做到了！SNARKs 越来越被充分理解了，甚至已经被用在多条区块链中（包括以太坊上的 tornado.cash 项目）。而且 SNARKs 是非常有用的，无论是作为隐私保护技术（Zcash 和 tornado.cash），还是作为可扩展性技术（例如 ZK Rollup、STARKDEX 以及 STARK 化的纠删编码数据根）。

不过还是有些效率上的问题，创造一种算术友好型的哈希函数是一个（看 此处 和 此处 了解那些突破性的候选方案）；高效证明随机内存存取是另一个。进一步来说，还有一个未解决的问题是，是不是此类方案的证明时间都遵循 O(n * log(n)) 的限制，还是说，有某种办法可以构建一个简洁的证明，开销仅呈线性增长，就像 bulletproofs 一样（但它的验证时间也会呈线性增长）。此外，这些现有方案有 bug 的风险也是一直存在的。总而言之，问题都是细节上的，在问题的基本层面已经没有疑问了。

4. 代码混淆

密码学难题的圣杯是创造一个混淆器 O：对给定的任意程序 P，该混淆器能产生一个次级的程序 O(P) = Q，只要给出相同的输入，P 与 Q 会返回相同的输出，并且更重要的是，Q 不会暴露 P 的任何信息。这样话，人们就可以在 Q 中隐藏口令、秘密的加密密钥，或者仅仅是用 Q 来隐藏算法本身的工作方式。

现状：进展缓慢。

翻译成大白话，这个问题就是说，我们想要一种方式来 “加密” 一个程序，使得加密后的程序能对同样的输入给出相同的输出，但原程序内部的机理又是完全隐藏起来的。这种技术的一种用场是一段包含一把私钥的程序，仅允许这把密钥对特定消息签名。

代码混淆方案对区块链协议来说是非常有用的，虽然用起来会比较微妙，因为我们必须面对这样的可能性：一个在链上的混淆过的程序可能会被复制并用在一个完全不同的环境中，由此产生许多不同的结果。让我很感兴趣的点在这里：我们可以用包含一些工作量证明的、混淆后的程序来代替运营者，从而能在抗串谋工具中移除中心化的运营者，因为在确定单个参与者的行动时，使用多个输入、运行多次程序的开销会非常大。

不幸的是，到目前为止，这还是一个难题。在这个问题上不断有人付出努力，一方面是创造一些建构（例如这个），尝试减少对那些我们不知道其实用性的数学对象（例如通用性密码学多重线性映射）的假设，另一方面是尝试做出有用数学对象的有用实现。不过，所有这些路径距离我们的目的——创建出可行且在已知条件下安全的代码混淆器——非常遥远。请看 https://eprint.iacr.org/2019/463.pdf 以了解对该问题的更一般化的概述。

5. 基于哈希的密码学

问题：创造一种签名算法，除了依靠哈希函数的随机特性以外没有别的安全假设；哈希函数对古典计算机保持 160 比特的安全性（即，根据 Grover 算法，对量子计算机保持 80 比特的安全性），并且具有最优大小及其他属性。

现状：有一些进展。

自 2014 年以来，这个题目下出现了两项进展：

1.SPHINCS，一种 “无状态” 的签名方案（“无状态” 的意思是，即使多次使用，也无需保存像 nonce 那样的计数信息）。该方案在《难题》一文出版后不久就出现了，提供了一种仅基于哈希函数的签名方案，签名大小在 41 kB 左右；

2.STARKs 也已经被开发出来了，所以人们可以基于 STARK 技术实现相近大小的签名。不仅是签名方案，连通用型零知识证明技术，都可以仅用哈希函数实现出来，这是我在 5 年前完全没有料到的事，我很高兴能见识到这一切。虽然说，签名的大小仍然是一个问题，但人们也在不断付出努力减少证明的大小（例如最近的 DEEP FRI），而且看起来进一步的进展效果会越来越强。

基于哈希函数的密码学中尚未解决的主要问题是签名聚合，就是类似于 BLS 签名方案所提供的功能。已知的是我们可以对许多 Lamport 签名方案生成 STARK，所以一个更有效率的签名方案可能就快出来了。（如果你还在思考基于哈希函数的公钥加密方案是否可能，答案是，不行，因为攻击者只需付出诚实用户平方级的成本就可以攻破这样的方案。）

点击关注币海启行微信公众号，了解更多