Subscribe to Hua
<100 subscribers
Subscribe to Hua
<100 subscribers
Share Dialog
Share Dialog
我在零知识证明这个领域里兜兜转转了无数圈，之所以走了很多弯路，原因在于从一开始就对零知识证明有先入为主的错误认识，这些认识是后续建造零知识证明这个房子时的框架，由于框架是错误的，那在它基础之上是无论如何也建立不起一个不会倒塌的房子的。
在这篇文章中，我将试着纠正这些错误认识，如果你正在学习零知识证明并觉得一头雾水，希望我犯过的错误能对你有所启发；如果你才刚开始去了解零知识证明，希望本文有助你搭建一个基础的框架。在我眼中，文中讨论的这些点恰是零知识证明这件事的奥妙所在，它们揭示了为何零知识证明是行得通的。
需要注意的是，下述的这些所谓纠正后的认识依然可能是不准确的认识，你只能用它做参考，并对它保持质疑。
假如我们知道宇宙演化的算法，但不知道宇宙的初始值，这时候Alice说她知道这个初始值，我们不信，于是她把一组数据作为算法的输入，一通计算，得到一个和我们所处的宇宙一模一样的宇宙，这时候我们是不是会相信Alice的那组数据就是宇宙的初始值？我们会相信。
这就是一个零知识证明，确切来讲它应该叫零知识的证明。Alice通过这种证明方法可以证明自己拥有知识（宇宙的初始值），同时又不泄漏知识。
如果观察Alice的证明过程，就会发现它只涉及三个对象：初始值，演化算法，演化结果（现状），我们可以把其抽象为：算法的输入、算法、算法的输出，而零知识证明要做到能够证明输出确实是输入通过确定的算法计算出来的。
这样一来，如果验证者看到输出是对的，同时证明显示输出是用输入计算而来的，那么验证者就可以在不知道输入的情况下相信输入。
随之而来的问题就是：如何证明输出是由输入通过某个确定的算法计算出来的？而不是其他的输入、其他的输出、或者其他的算法？这便是零知识证明协议要解决的问题。
在zk-SNARK系列的协议中，采用的方法是把输入、算法、输出转换为一个多项式，通过多项式把这三者绑定到一起。如果能够证明Alice知道这个多项式，就可以认为Alice的输出是输入通过算法计算出来的。
总而言之，因为零知识证明被广泛地用于实现隐私保护，隐私保护又意味着不泄露数据，所以我们会比较容易在一开始就围绕它是怎样隐藏数据的为方向去思考。但如果以「它是如何实现零知识的」为线索去认识它，就会一团乱麻，而如果以「它是如何实现证明的」为线索，就会一条线清晰地贯穿始终。
对于哈希函数、基于椭圆曲线的加密算法等密码学工具而言，几乎在任何情况下给出任何数据，它们都能够把这个数据隐藏起来（实践角度如果输入空间过小是无法隐藏的）；当我们知道零知识证明可以不泄露知识时，往往也会认为能够把任意的知识交给它来处理，但实际上，零知识证明只能在特定的场景下实现特定知识的「零知识」。
回到Alice的例子，在她的零知识证明过程中，至少涉及到三种可以被称为知识的东西：1.宇宙的初始值；2.宇宙的演化算法；3.宇宙的演化结果。可以通过零知识证明不泄露这些不同类型的知识吗？不能，我们甚至必须知道宇宙的演化算法和演化结果，才能证明Alice是否知道宇宙的初始值。
换言之，零知识证明只能证明但不泄漏「输入」这个位置上的知识。当在思考或使用零知识证明协议解决问题时，需要看不想泄漏的知识是否可以被放在输入的位置上，并能通过确定的算法产生一个可判断真伪的输出（更准确而言在于能否构造一个 NP-relation）。
举例来说，如果Alice在不附带任何条件的情况下声称自己知道一个数x，我们是难以用零知识证明证明她知道数x但又不泄漏x的；但如果Alice声称自己知道一个数x满足某个条件a，那就可以先有一个算法，该算法的输出一定满足条件a（可以转换为输出一定为真），然后，如果输入x能够满足这个算法，就可以相信数x满足条件a，这也意味着Alice能够在不泄漏数据的情况下使用数据。
不过这里有另一个容易混淆的地方，就是零知识证明并不能直接证明某人有解某个问题的能力，比如有解地图三染色问题的能力，它证明的是某人知道该问题的一组解。（注：可以通过让证明者解多次不同的三染色问题实例，证明证明者有计算能力可以解三染色问题。）
这与零知识证明协议的构造有关，如前所述，它证明的是一个把输入、算法、输出绑定到一起形成的多项式，而不是某个求解算法的多项式，证明这个多项式成立，实际上是在证明输入、算法、输出之间具有确定的关系，而不是在证明其他事情。
一方面，这种构造限定了零知识证明的应用，它只能在输入、算法、输出齐备的情况下实现输入的零知识证明，如果输出为真，就可以相信输入为真；但另一方面，这种构造扩展了零知识证明的其他应用，即如果输入为真，我们也可以相信输出为真。
区块链激活了零知识证明的应用，零知识证明则提供给区块链一种卓越的解决方案，两者能够彼此促进更主要的原因在于区块链的系统特点和零知识证明的证明方法特点，而不仅仅因为零知识证明能保护隐私。
回忆我们做数学的证明大题，那是一种推理式证明，有着严格的可被验证的推导过程；但还有另一种证明叫交互式证明，它不通过推导，而是借助于证明者和验证者的交互，验证者向证明者提出问题，如果证明者能给出正确的回答，就认为证明者声称的命题是对的。
举一个不算特别准确的例子：Alice声称当宇宙的输入为x时，输出为42，推理式证明是指她要代入x一步步计算，算出42，并把计算过程展示出来以供验证；交互式证明看起来则是：给验证者一台平行宇宙穿梭机，验证者随机穿梭到有输出的宇宙（输入都为x），然后根据宇宙的输出是否为42来判断Alice声称的是否可相信。
相较于推理式证明，交互式证明的验证者只需验证一个点或几个点，这是零知识证明与区块链契合的一个重要原因：区块链是一种分布式系统，每个节点都要重复完成验证的工作，受益于只需验证挑战点，简洁（Succinct）零知识证明系统可以减少验证的工作，它提供给验证者的是一个比原命题小得多的证明。
形象化而言就是：在非区块链的系统中，零知识证明减少一份验证者的工作，同时可能增加一份证明者的工作（不一定是1：1的关系），这或许就算不上好处；可在区块链系统中，零知识证明每减少一份验证者的工作，如果有100个节点，就能减少100份的总工作量，而此时增加的仍然只是一份证明者的工作，那么这种好处就很明显了。
此外，单从用零知识证明来解决问题的角度，区块链上的空间资源和时间资源都是极为稀缺的，而简洁零知识证明产生的证明小、验证时间短，适合作为区块链上的解决方案。
但需要注意，交互式证明只需验证挑战点，与之相伴的推理式证明和交互式证明的另一个区别就是：推理式证明能够证明一个命题是否成立，交互式证明却只能证明一个命题在概率上是否成立。
也就是说，假如证明者声称的命题是错的，但当验证者提出问题时证明者蒙对了答案，验证者会认为命题是对的。因此在零知识证明协议的设计中，非常重要的一部分工作就是用数学的方法让证明者几无可能蒙对答案（基于对证明者计算能力的某种假设，证明者使用虚假证明使验证者信以为真的概率是一个可忽略的函数）。
回到zk-SNARK。zk-SNARK把证明输入、算法、输出的关系转换为证明一个绑定三者关系的多项式，就能够给验证者提供一台平行宇宙穿梭机。在皮诺曹协议中（zk-SNARK的一种），交互式证明是这样的：
证明者声称自己知道一个多项式p(x)，该多项式是可以被分解成t(x)和h(x)的，即p(x)=t(x)·h(x) ；验证者随机选择一个挑战点s，通过对s加密让证明者只能算出p(s)和h(s)，而无法计算t(s)；证明者把p(s)和h(s)给验证者，验证者手中有t(s)，就可以计算t(s) ·h(s) 是否等于p(s)，如果相等，就相信证明者确实知道一个多项式。
而知道一个多项式，就意味着输入、算法、输出之间存在确定的关系，如果输出为真，我们就可以在并不知道输入的情况下相信输入为真，即实现零知识证明。那么到现在，我们就不仅知道了零知识证明是一种证明的方法，而且知道了它是如何来做证明的。
零知识证明是一种交互式的证明系统，它依赖于两个重要元素：交互、随机。
交互是指一方提出挑战，一方给出证明，如果没有这种交互，零知识证明就无法开展；随机是指挑战点必须是随机的，也就是不能被证明者预测到的，不然证明者就可以在挑战点上构建一个假证明。如果Alice事先知道验证者会去73号平行宇宙，她就可以提前把73号的答案改为42。
那为什么zk-SNARK称自己为非交互（Non-interactive）？在所谓的交互式证明中，需要先由验证者给出随机点，再由证明者构建证明；在所谓的非交互证明中，比如皮诺曹协议，它不再需要验证者给出随机点，转而由一个可信的第三方在初始化阶段给出随机点，这样一来，证明者就可以直接给出证明，验证者只需要验证证明即可，验证者和证明者之间不再需要交互。
可信第三方给出随机点就是皮诺曹协议的可信设置（Trusted-setup），相较于直接交互，可信设置在给出随机点s之外，还需多给出一个t(s)，因为验证者需要用t(s)进行验证。但问题在于t(s)不能被证明者得知，否则他可以轻易构造出一个假证明，所以需要用一个方法对t(s)做变换，使得变换后的t(s)可用于验证，但不可用于证明者的计算。皮诺曹协议选择双线性配对操作来完成这一工作。
所以无需交互更多的是一种技术上的处理，对于零知识证明而言，验证总是在随机挑战点上完成的，所不同的是这个挑战点从何而来。不同的具体协议，在用非交互取代交互时选择的方法会有比较大的区别，即便它们都叫zk-SNARK协议，这是额外需要注意的。
希望上述四点能对你理解零知识证明有所帮助，在文章的最后，是两个小的可能会出错的认识。
第一，零知识证明协议，比如zk-SNARK，并不是围绕某个确定的核心公式展开的，它是模块式的，每个模块负责完成自己的工作，然后大家组合到一起。所以如果你想通过抓住一个核心点来理解零知识证明就会比较困难，更好的方法是通过一条线索来理解它。
同时，zk-SNARK不是指某个具体的协议，它是一类方法的统称，组成它的那些模块大体不会变，但这些模块选择的具体方法是可变的。所以当你看到不同的zk-SNARK时，不用迷惑，跳出来站在模块的高度去看它，而不是陷入具体的方法。
第二，或许因为零知识证明是在与数学打交道，它常常带给人一种古老学科的感觉，但实际上零知识证明的研究还很早期，零知识证明的应用更是刚刚开始。当选择使用零知识证明时，开发者们并不是只需工程化实现一套成熟的理论，而是要一边找到/发明方法一边应用方法。
所以也许我们可以给零知识证明多一些的耐心，它可能是未来数字世界重要的组成部分，它不仅是使用构成数字世界的数据的工具，也是节省数字世界中最稀缺资源的工具。
我在零知识证明这个领域里兜兜转转了无数圈，之所以走了很多弯路，原因在于从一开始就对零知识证明有先入为主的错误认识，这些认识是后续建造零知识证明这个房子时的框架，由于框架是错误的，那在它基础之上是无论如何也建立不起一个不会倒塌的房子的。
在这篇文章中，我将试着纠正这些错误认识，如果你正在学习零知识证明并觉得一头雾水，希望我犯过的错误能对你有所启发；如果你才刚开始去了解零知识证明，希望本文有助你搭建一个基础的框架。在我眼中，文中讨论的这些点恰是零知识证明这件事的奥妙所在，它们揭示了为何零知识证明是行得通的。
需要注意的是，下述的这些所谓纠正后的认识依然可能是不准确的认识，你只能用它做参考，并对它保持质疑。
假如我们知道宇宙演化的算法，但不知道宇宙的初始值，这时候Alice说她知道这个初始值，我们不信，于是她把一组数据作为算法的输入，一通计算，得到一个和我们所处的宇宙一模一样的宇宙，这时候我们是不是会相信Alice的那组数据就是宇宙的初始值？我们会相信。
这就是一个零知识证明，确切来讲它应该叫零知识的证明。Alice通过这种证明方法可以证明自己拥有知识（宇宙的初始值），同时又不泄漏知识。
如果观察Alice的证明过程，就会发现它只涉及三个对象：初始值，演化算法，演化结果（现状），我们可以把其抽象为：算法的输入、算法、算法的输出，而零知识证明要做到能够证明输出确实是输入通过确定的算法计算出来的。
这样一来，如果验证者看到输出是对的，同时证明显示输出是用输入计算而来的，那么验证者就可以在不知道输入的情况下相信输入。
随之而来的问题就是：如何证明输出是由输入通过某个确定的算法计算出来的？而不是其他的输入、其他的输出、或者其他的算法？这便是零知识证明协议要解决的问题。
在zk-SNARK系列的协议中，采用的方法是把输入、算法、输出转换为一个多项式，通过多项式把这三者绑定到一起。如果能够证明Alice知道这个多项式，就可以认为Alice的输出是输入通过算法计算出来的。
总而言之，因为零知识证明被广泛地用于实现隐私保护，隐私保护又意味着不泄露数据，所以我们会比较容易在一开始就围绕它是怎样隐藏数据的为方向去思考。但如果以「它是如何实现零知识的」为线索去认识它，就会一团乱麻，而如果以「它是如何实现证明的」为线索，就会一条线清晰地贯穿始终。
对于哈希函数、基于椭圆曲线的加密算法等密码学工具而言，几乎在任何情况下给出任何数据，它们都能够把这个数据隐藏起来（实践角度如果输入空间过小是无法隐藏的）；当我们知道零知识证明可以不泄露知识时，往往也会认为能够把任意的知识交给它来处理，但实际上，零知识证明只能在特定的场景下实现特定知识的「零知识」。
回到Alice的例子，在她的零知识证明过程中，至少涉及到三种可以被称为知识的东西：1.宇宙的初始值；2.宇宙的演化算法；3.宇宙的演化结果。可以通过零知识证明不泄露这些不同类型的知识吗？不能，我们甚至必须知道宇宙的演化算法和演化结果，才能证明Alice是否知道宇宙的初始值。
换言之，零知识证明只能证明但不泄漏「输入」这个位置上的知识。当在思考或使用零知识证明协议解决问题时，需要看不想泄漏的知识是否可以被放在输入的位置上，并能通过确定的算法产生一个可判断真伪的输出（更准确而言在于能否构造一个 NP-relation）。
举例来说，如果Alice在不附带任何条件的情况下声称自己知道一个数x，我们是难以用零知识证明证明她知道数x但又不泄漏x的；但如果Alice声称自己知道一个数x满足某个条件a，那就可以先有一个算法，该算法的输出一定满足条件a（可以转换为输出一定为真），然后，如果输入x能够满足这个算法，就可以相信数x满足条件a，这也意味着Alice能够在不泄漏数据的情况下使用数据。
不过这里有另一个容易混淆的地方，就是零知识证明并不能直接证明某人有解某个问题的能力，比如有解地图三染色问题的能力，它证明的是某人知道该问题的一组解。（注：可以通过让证明者解多次不同的三染色问题实例，证明证明者有计算能力可以解三染色问题。）
这与零知识证明协议的构造有关，如前所述，它证明的是一个把输入、算法、输出绑定到一起形成的多项式，而不是某个求解算法的多项式，证明这个多项式成立，实际上是在证明输入、算法、输出之间具有确定的关系，而不是在证明其他事情。
一方面，这种构造限定了零知识证明的应用，它只能在输入、算法、输出齐备的情况下实现输入的零知识证明，如果输出为真，就可以相信输入为真；但另一方面，这种构造扩展了零知识证明的其他应用，即如果输入为真，我们也可以相信输出为真。
区块链激活了零知识证明的应用，零知识证明则提供给区块链一种卓越的解决方案，两者能够彼此促进更主要的原因在于区块链的系统特点和零知识证明的证明方法特点，而不仅仅因为零知识证明能保护隐私。
回忆我们做数学的证明大题，那是一种推理式证明，有着严格的可被验证的推导过程；但还有另一种证明叫交互式证明，它不通过推导，而是借助于证明者和验证者的交互，验证者向证明者提出问题，如果证明者能给出正确的回答，就认为证明者声称的命题是对的。
举一个不算特别准确的例子：Alice声称当宇宙的输入为x时，输出为42，推理式证明是指她要代入x一步步计算，算出42，并把计算过程展示出来以供验证；交互式证明看起来则是：给验证者一台平行宇宙穿梭机，验证者随机穿梭到有输出的宇宙（输入都为x），然后根据宇宙的输出是否为42来判断Alice声称的是否可相信。
相较于推理式证明，交互式证明的验证者只需验证一个点或几个点，这是零知识证明与区块链契合的一个重要原因：区块链是一种分布式系统，每个节点都要重复完成验证的工作，受益于只需验证挑战点，简洁（Succinct）零知识证明系统可以减少验证的工作，它提供给验证者的是一个比原命题小得多的证明。
形象化而言就是：在非区块链的系统中，零知识证明减少一份验证者的工作，同时可能增加一份证明者的工作（不一定是1：1的关系），这或许就算不上好处；可在区块链系统中，零知识证明每减少一份验证者的工作，如果有100个节点，就能减少100份的总工作量，而此时增加的仍然只是一份证明者的工作，那么这种好处就很明显了。
此外，单从用零知识证明来解决问题的角度，区块链上的空间资源和时间资源都是极为稀缺的，而简洁零知识证明产生的证明小、验证时间短，适合作为区块链上的解决方案。
但需要注意，交互式证明只需验证挑战点，与之相伴的推理式证明和交互式证明的另一个区别就是：推理式证明能够证明一个命题是否成立，交互式证明却只能证明一个命题在概率上是否成立。
也就是说，假如证明者声称的命题是错的，但当验证者提出问题时证明者蒙对了答案，验证者会认为命题是对的。因此在零知识证明协议的设计中，非常重要的一部分工作就是用数学的方法让证明者几无可能蒙对答案（基于对证明者计算能力的某种假设，证明者使用虚假证明使验证者信以为真的概率是一个可忽略的函数）。
回到zk-SNARK。zk-SNARK把证明输入、算法、输出的关系转换为证明一个绑定三者关系的多项式，就能够给验证者提供一台平行宇宙穿梭机。在皮诺曹协议中（zk-SNARK的一种），交互式证明是这样的：
证明者声称自己知道一个多项式p(x)，该多项式是可以被分解成t(x)和h(x)的，即p(x)=t(x)·h(x) ；验证者随机选择一个挑战点s，通过对s加密让证明者只能算出p(s)和h(s)，而无法计算t(s)；证明者把p(s)和h(s)给验证者，验证者手中有t(s)，就可以计算t(s) ·h(s) 是否等于p(s)，如果相等，就相信证明者确实知道一个多项式。
而知道一个多项式，就意味着输入、算法、输出之间存在确定的关系，如果输出为真，我们就可以在并不知道输入的情况下相信输入为真，即实现零知识证明。那么到现在，我们就不仅知道了零知识证明是一种证明的方法，而且知道了它是如何来做证明的。
零知识证明是一种交互式的证明系统，它依赖于两个重要元素：交互、随机。
交互是指一方提出挑战，一方给出证明，如果没有这种交互，零知识证明就无法开展；随机是指挑战点必须是随机的，也就是不能被证明者预测到的，不然证明者就可以在挑战点上构建一个假证明。如果Alice事先知道验证者会去73号平行宇宙，她就可以提前把73号的答案改为42。
那为什么zk-SNARK称自己为非交互（Non-interactive）？在所谓的交互式证明中，需要先由验证者给出随机点，再由证明者构建证明；在所谓的非交互证明中，比如皮诺曹协议，它不再需要验证者给出随机点，转而由一个可信的第三方在初始化阶段给出随机点，这样一来，证明者就可以直接给出证明，验证者只需要验证证明即可，验证者和证明者之间不再需要交互。
可信第三方给出随机点就是皮诺曹协议的可信设置（Trusted-setup），相较于直接交互，可信设置在给出随机点s之外，还需多给出一个t(s)，因为验证者需要用t(s)进行验证。但问题在于t(s)不能被证明者得知，否则他可以轻易构造出一个假证明，所以需要用一个方法对t(s)做变换，使得变换后的t(s)可用于验证，但不可用于证明者的计算。皮诺曹协议选择双线性配对操作来完成这一工作。
所以无需交互更多的是一种技术上的处理，对于零知识证明而言，验证总是在随机挑战点上完成的，所不同的是这个挑战点从何而来。不同的具体协议，在用非交互取代交互时选择的方法会有比较大的区别，即便它们都叫zk-SNARK协议，这是额外需要注意的。
希望上述四点能对你理解零知识证明有所帮助，在文章的最后，是两个小的可能会出错的认识。
第一，零知识证明协议，比如zk-SNARK，并不是围绕某个确定的核心公式展开的，它是模块式的，每个模块负责完成自己的工作，然后大家组合到一起。所以如果你想通过抓住一个核心点来理解零知识证明就会比较困难，更好的方法是通过一条线索来理解它。
同时，zk-SNARK不是指某个具体的协议，它是一类方法的统称，组成它的那些模块大体不会变，但这些模块选择的具体方法是可变的。所以当你看到不同的zk-SNARK时，不用迷惑，跳出来站在模块的高度去看它，而不是陷入具体的方法。
第二，或许因为零知识证明是在与数学打交道，它常常带给人一种古老学科的感觉，但实际上零知识证明的研究还很早期，零知识证明的应用更是刚刚开始。当选择使用零知识证明时，开发者们并不是只需工程化实现一套成熟的理论，而是要一边找到/发明方法一边应用方法。
所以也许我们可以给零知识证明多一些的耐心，它可能是未来数字世界重要的组成部分，它不仅是使用构成数字世界的数据的工具，也是节省数字世界中最稀缺资源的工具。
No comments yet