http://www.tnmanning.com

交互式零知识证明的演练

简述

学习如何通过使用零知识证明方法解答数独,并用Python构建PoC。

毫无疑问,我们当前生活在一个数据驱动的社会中,事实上,数据已成为比黄金或石油更有价值的资源。 认真考虑一下我们每天每分钟在线共享的个人数据量。 位置,感觉,喜好,密码,消息……而且清单还在不断增长……

幸运的是,对称和非对称的加密技术使我们能够保护我们的数据免受试图窃听我们通信信道的恶意对手的攻击。但是数据控制器(我们合法发送数据的人)呢?消费者如何确保自己的数据不被错误处理或滥用?一种确定的方法是首先拒绝发送数据。但实际上,并不是那么简单。这是一次交换。我们为他们提供的某种服务交换了一些隐私权吗? 尽管如此,在很多情况下,从消费者的角度来看,这种交换并不公平,因为数据处理程序要求的数据比实际需要的要多得多。

同样,密码学可能对此有解决方案。如果我告诉您,可以避免共享您的数据怎么办。例如与其将完整的薪水概览和工作详细信息发送给租赁机构以进行信用检查,不如仅发送证明您每年收入超过4万的证明。这正是零知识证明(ZKP)所提供的!

尽管有很多方法可以构造ZKP,但在本文中,我将给出一个演练(包含完整的代码片段),说明如何为仅使用散列函数作为承诺的数独谜题解决方案创建ZKP。ZKP一开始理解起来可能会让人望而生畏,因此我真的相信数独拼图是理解ZKP如何在很高的层次上工作的一个很好的例子。另外,数独是大多数人都熟悉的东西。但让我们切入正题。

背景知识

零知识证明

零知识协议起源于80年代,最初是由Shafi Goldwasser,Silvio Micali和Charles Rackoff在麻省理工学院提出的。更准确地说,他们描述了一种交互式证明系统,其中涉及一个当事方(“证明方”)向另一方(“验证方”)证明某项陈述成立。

将此背景化为常见的Alice/Bob示例,我们可以考虑以下场景:Alice偶然发现了一个在线比赛,需要解开一个谜题,并获得100英镑的奖金。她请求Bob的帮助,如果他们中的任何一个解决了,他们同意平分奖金。不久之后,Bob声称自己已经解决了问题,Alice请他分享解决方案。然而Bob不愿意分享,因为他认为Alice可以自己提交解决方案,而不分享奖金。因此,他正在寻找一种安全的方法来向Alice证明他有解决方案,但又不直接与她分享。是的,你猜对了!ZKP正是他所追求的!

让我们更彻底地定义“安全方式”一词的含义。通常ZKP必须提供以下属性(至少具有很高的信心!):

完整性:验证者必须拒绝所有无效的证明
健全性:验证人必须接受每一个有效的证明
零知识:验证程序除了断言外,不理会其它语句的任何信息

请注意,这是交互式ZKP的非常基本的定义。有各种各样更复杂的交互式/非交互式ZKP,但是对于本演练而言,此定义就足够了。

承诺方案(Commitment Schemes)

承诺方案是ZKP的关键组成部分,总体而言,它是加密的关键部分。简而言之,它们是密码原语,它允许当事方承诺特定的价值而无需透露实际价值,同时提供一种方式来揭示价值并在以后的阶段中验证承诺。

更正式地说,让C作为承诺方案,它必须提供以下两个属性:

隐藏(Hiding):很难区分不同价值的承诺。

约束力(Binding):一个人承诺后不能再宣称自己已经承诺了另一个值:

创建承诺方案的一种方法是使用单向哈希函数和加密安全的随机字节。应该注意的是,在这种情况下,该方案的安全性由哈希函数本身的加密假设(即它是单向的)来控制。

为了更清楚地说明这一点,让我们来看一个常见嫌疑人的例子。Alice和Bob决定玩一个石头,剪刀,布的数字游戏。他们都做出选择并交换结果,以便确定赢家。在数字世界中,其中一个必须首先共享他/她的选择,这使她/他处于不利的位置,因为他/她可以在查看另一位玩家选择的结果后再共享不同的选择。这正是承诺方案要解决的问题!

另外,他们可以根据自己的选择创建承诺并共享承诺,而不是实际选择! 例如:

设置一个:

S = {“Rock”, ”Paper”,”Scissors”}

Bob和Alice都分别从S中随机选择Pᴬ和Pᴮ。现在他们计算:(||->表示串联)

Cᴬ = sha256(Rᴬ || Pᴬ) and Cᴮ = sha256(Rᴮ || Pᴮ)

Bob和Alice共同共享Cᴬ,Alice和Bob共同共享Cᴮ。请注意,到现在为止,它们都承诺了这些值。

最后它们共享原始选择和随机字节Pᴬ,Rᴬ和Pᴬ,Rᴮ。有了这些信息,各方就可以通过对P||进行散列来验证承诺。R并声明它们的等效性。根据他们的选择,可以确定获胜者,而且由于哈希值不匹配,他们都无法更改其初始选择。

数独ZKP

现在是本文的主要部分。数独是一个非常著名的难题,也被称为NP问题(实际上是NP-Complete),并被证明对于NP中的任何问题都有ZK。数独ZKP绝非什么新鲜事物,但我还没有找到一个直观和清晰的解释协议与代码示例,所以至少这是本文旨在提供的。实际上,这里描述的协议是Gradwohl等人的这项非常有趣的工作的实现。有趣的是,他们在论文中还描述了一种物理协议,可以使用一副纸牌来执行打样,如果您想亲自演示ZPK,但现在还是坚持使用数字打样,这很有趣。

Alice想向Bob证明她有一个数独谜题的解答方案,但Bob不相信她。假设她搁置以下难题和解答方案。

交互式零知识证明的演练

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。