详解—从数独难题到零知识证明｜点滴资讯

该文带我们了解如何通过零知识证明拥有Sudoku的解决方案，以及如何使用纯Python构建PoC。

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

对我们来说幸运的是，对称和不对称的现代加密技术使保护我们的数据免受试图窃听我们的通信渠道的恶意对手的侵害成为可能。但是数据控制器（我们合法发送数据的人）呢？消费者如何确保自己的数据不被错误处理或滥用？确定的一种方法是首先拒绝发送数据。但是实际上，并不是那么简单。这是一种交流。我们为他们提供的某种服务交换了一些隐私权吗？但是，在很多情况下，从消费者的角度来看，这种交换还是不公平的，因为数据处理程序要求的数据方式比实际需要的更多。

同样，密码学可能对此有解决方案。如果我告诉您，毕竟可以避免共享数据怎么办。例如，与其将完整的薪水概览和工作详细信息发送给租赁机构以进行信用检查，不如仅发送证明您每年收入超过4万的证明。这正是零知识证明（ZKP）所提供的！（由于其他许多原因，它比实际中的要复杂一些。例如，我们如何信任数据的来源等……但您会明白）

尽管可以采用多种方式构造ZKP，但在本文中，我将向您提供有关如何仅使用哈希函数作为承诺的Sudoku拼图解决方案创建ZKP的演练（包含完整的代码片段）。ZKP最初很难理解，因此，我真的相信Sudoku拼图是了解ZKP如何在很高水平下工作的一个很好的例子。另外，数独是大多数人都熟悉的东西。但是，让我们开始追逐吧。

1、零知识证明

零知识协议起源于80年代，最初是由ShafiGoldwasser，SilvioMicali和CharlesRackoff在麻省理工学院提出的[2]。更准确地说，他们描述了一种交互式证明系统，其中涉及一个当事方（“证明方”）向另一方（“验证方”）证明陈述成立。

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

但是，让我们更彻底地定义“安全方式”一词的含义。通常，ZKP必须提供以下属性（至少具有很高的信心！）：

完整性：验证者必须拒绝所有无效的证明

健全性：验证人必须接受每一个有效的证明

零知识：验证程序除了断言外不学习有关该语句的任何信息。

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

2、承诺方案

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

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

隐藏：难以区分不同价值的承诺。即：

约束力：一个承诺一个人的人以后不可能宣称自己已经承诺了另一个价值：

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

为了更加清楚，让我们通过一个常见的可疑对象来举一个例子。爱丽丝和鲍勃决定以数字方式玩石头，纸，剪刀的游戏。他们都做出选择并交换意见，以便确定赢家。自然地，在数字世界中，其中一个必须首先共享他/她的选择，这使她/他处于不利的位置，因为他/她在查看其他玩家的选择后可以共享其他选择。这正是承诺计划解决的问题！

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

设置一个：

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

Bob和Alice两个随机挑选P ᴬ和Pᴮ从小号分别。现在他们计算：（|| ->表示串联）

Cᴬ =sha256（Rᴬ||Pᴬ）和 Cᴮ =sha256（Rᴮ||Pᴮ）

鲍勃股Cᴬ与Alice和Alice Cᴮ与鲍勃。请注意，到目前为止，他们都致力于这些价值观。

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

3、数独ZKP

现在是本文主要部分的时候了。数独是一个非常著名的难题，也被称为NP问题（实际上是NP-Complete[4]），并被证明对于NP中的任何问题都有ZKP[1]。SudokuZKP绝不是什么新鲜事物，但是我还没有找到带有代码示例的协议的直观，清晰的说明，因此至少这是本文旨在提供的内容。实际上，这里描述的协议是Gradwohl等人的这项非常有趣的工作的实现。[3] 因此， 有关更多正式细节，请参阅此处。有趣的是，在他们的论文中，他们还描述了一种物理协议以使用一副纸牌来执行打样，如果您想亲自演示ZPK，这很有趣，但是现在让我们继续使用数字打样。

在进入代码之前，让我们看一下协议本身的高级普通英语描述。

爱丽丝想向鲍勃证明她有数独谜题的解决方案，但鲍勃不相信她。假设她搁置以下难题和解决方案。

为避免混淆，让我们逐步遵循以下证明：

1.爱丽丝创建数独数位的排列，有效地是每个数位一对一的映射。即1->3，2->8…。

2.此外，她为每个数独单元生成一个随机字节序列（即刻）。这导致81个随机随机数。

3.她在数独解决方案的编号上应用了映射，以获取被掩盖的解决方案。请注意，通过排列值，数字是一对一的映射，因此仍然仅出现一次。

爱丽丝将屏蔽的解决方案从每个行，列，子网格和一组已知数字（首先是拼图定义的一部分）中拆分为一组数字。实际上，她最终得到27+ 1个数字集，其中从行，列，子网格派生的27个数必须满足数独要求。即1–9的所有数字仅出现一次。

然后，她通过用对应的随机数对每个单元格进行散列来创建对屏蔽解决方案的承诺，将该承诺发送给Bob，并要求Bob选择行，列，子网格或已知数字集。

鲍勃选择了一个，爱丽丝向他发送了与鲍勃的选择相对应的随机数和排列数字。

如果Bob选择了已知号码列表，则Alice还将最初生成的一对一映射发送给他。

然后，Bob验证排列的值确实只出现了一次，并使用随机数重新创建了承诺以验证Alice的承诺。

如果Bob选择了已知号码列表，他还将检查映射是否正确。例如，令M为映射，n为1–9的整数：M（n）==接收到的已知数字列表。

这9个步骤总结了证明的一个迭代！

很自然地，您已经对这些步骤提出了疑问，因此请遵循这些步骤的基本原理。

1，执行第1步，第3步，以使验证者不了解有关难题解决方法的任何信息。

步骤2，随机数用于阻止验证程序执行已知的纯文本攻击。如果没有随机数，Bob可以仅对所有数字进行散列（1–9），并将相应的摘要与承诺相匹配以显示值。

步骤5，通过创建承诺并将其发送给Bob，Alice致力于其解决方案，因此无法更改它（或映射）。

6，步骤6,7,8,9是最难理解的。通过让Bob选择那些爱丽丝中的任何一个，为验证者提供了确认解决方案正确的机会。回想一下，由于她致力于映射，因此无法更改映射。另外，您可能在想：“这证明她可能只有解决方案，而不是那个特定的解决方案”。您是100％正确的！这就是存在选择请求拼图给出的初始数字的原因。这样，爱丽丝无法作弊，因为鲍勃可随时选择索要这些号码，而且如果这是另一种解决方案，显然它们将不匹配。

更重要的是，有必要强调这种方法的可靠性误差。回想一下，稳健性是ZKPVerifier接受所有有效证明的属性。在这种情况下，由于验证者可以选择28种选择（3n+ 1），这意味着协议的声音仅为1/28％，这意味着存在1-1/28的声音错误！换句话说，在一次迭代之后，验证者仅能确保1/28是有效的证明。那不是很高，不是吗？因此，可以对上述步骤进行多次迭代，以将声音误差降低到可以忽略的值。（可以使用贝叶斯规则来推断每次迭代的健全率）

我希望这现在更有意义。让我们继续使用Python开发一个小的PoC证明。您可以在此处找到完整的代码：zkp-sudoku-pygithub.com

由于生成和解决数独问题不在本文的讨论范围之内，因此我暂时只使用一个静态数独，但可以随时将其替换为代码以每次生成一个新的数独难题：

数独谜题存储为平面python列表，以便于处理。

接下来，让我们添加代码以使用一对一映射置换数独解决方案并创建随机随机数：

在洗牌之后添加了零元素，因为我不希望它成为映射的一部分。数字索引就是从1开始的。

此外，以下是创建数独解决方案承诺的功能：

如上所示，对于承诺，使用SHA256哈希算法。此外，以下是将拼图分为行，列和子网格的代码：

最后，进行检查以确认1–9中的所有数字都存在并且仅出现一次：

现在，我们可以将所有这些功能组合在一起，以创建协议的概念证明并验证其正确性：

该代码仅用于演示目的，并且可能不是加密安全的，因此请不要在生产中按原样使用。可以添加一些优化和改进，因此，如果您有这种需求，请不要犹豫，在GitHub存储库中打开“请求”。

希望该博客文章提供了有关ZKP的一些基本知识，尤其是如何通过零知识证明来证明拥有Sudoku解决方案。在以后的文章中，我们将探索更复杂的证明，这些证明不需要证明者与验证者之间的相互作用，并且还将使用更复杂的密码原语。敬请关注！（原文地址：https://medium.com/coinmonks/walkthrough-of-an-interactive-zero-knowledge-proof-for-sudoku-puzzle-ac563588f1a8）