零知识证明：一个基于zk-SNARKs的Mastermind棋盘游戏

一、关于Mastermind棋盘游戏

wiki: https://en.wikipedia.org/wiki/Mastermind_(board_game)
mastermind （益智棋盘游戏） 编辑 讨论 上传视频
参考URL: https://baike.baidu.com/item/mastermind/3579377

Mastermind（珠玑妙算）是一种可供两名玩家使用的密码破译棋盘游戏。

在1970年由Mordecai Meirowitz发明，他是一位以色列邮政和电信专家。 但游戏类似早期一种利用铅笔和纸进行的游戏，游戏名为“公牛和母牛”，可能追溯到一个世纪或更长时间。

Mastermind Game，就是一个博弈游戏，靠猜测来取胜的娱乐游戏。

二、一个零知识证明游戏

https://github.com/weijiekoh/zkmm

1. readme

这是Mastermind棋盘游戏的实现，该游戏使用zk-SNARK而不是受信任的第三方来执行游戏规则。

它使用来自iden3的snarkjs和circom JavaScript库。

关于zk-SNARKS

zk-SNARK允许您以密码方式证明某些秘密数据的知识，而无需透露这些数据。 有关zk-SNARK的简单说明，请阅读Christian Lundkvist的这篇博客文章。

Mastermind规则

There are two players: the codebreaker and the codemaster.

有两个参与者：密码破解者和密码管理员。

The codemaster creates a secret four-digit sequence of coloured pegs, limited to red, blue, green, and yellow.

编码管理员会创建一个秘密的四位数彩色钉子序列，仅限于红色，蓝色，绿色和黄色。

To win, the codebreaker must guess the secret sequence of pegs within a set number of attempts. After each guess, if the codebreaker does not yet have the correct solution, the codemaster must tell the codebreaker the following clue:

为了赢得胜利，密码破解者必须在一定次数的尝试中猜出钉子的秘密序列。 每次猜测之后，如果密码破解者还没有正确的解决方案，则密码管理员必须告诉密码破解者以下线索：

1. How many exact matches of colour and position there are — these are are black pegs

   颜色和位置有多少个精确匹配-这些是黑色钉子

2. How many pegs have matching colours, but are in the wrong position — these are white pegs.

   多少个钉子的颜色匹配，但位置错误–这些是白色钉子。

For example, if the solution is R R B Y, and the guess is Y R B G, the codemaster must provide this clue: 2 black pegs and 1 white peg.

例如，如果解决方案是R R B Y，而猜测是Y R B G，则代码管理员必须提供以下线索：2个黑色钉和1个白色钉。

Solution       : Y R B G
Guess          : R R B YExact matches  : 0 1 1 0 -> 2 black pegs
Inexact matches: 0 0 0 1 -> 1 white peg

Inexact matches do not overlap; for instance:

不精确的匹配不会重叠； 例如：

Solution       : R R Y B
Guess          : G G R BExact matches  : 0 0 0 1 -> 1 black peg
Inexact matches: 0 0 1 0 -> 1 white peg (not two, even though there are two red pegs in the solution)

An illustrated example:
插图示例：

协议

1.准备电路 Prepare the circuit

创建一个本质上是此功能的算术电路C：

C (pubGuess, pubClue, pubSolutionHash, privSolution):hash(privSolution) === pubSolutionHashgenClue(pubGuess, privSolution) === pubClue

That is, given the secret sequence privSolution, the guess pubGuess, the clue pubClue, and a cryptographic hash of the secret sequence, the circuit:

也就是说，给定秘密序列privSolution，猜测pubGuess，线索pubClue和秘密序列的密码哈希，电路：

a) calculates the correct clue and the cryptographic hash of the secret sequence, and
计算出秘密序列的正确线索和加密哈希，并且

b) declares two constraints: that the cryptographic hash is correct and that the clue is correct.
声明2个约束：加密哈希是正确的，提醒是正确的。

In a later step, the codebreaker can cryptographically verify that (a) and/or (b) does not hold; more on that later.

在随后的步骤中，密码破解者可以通过密码验证（a）和/或（b）不成立； 稍后再讨论。

2.可信设置 Trusted setup

Generate the proving key, verifiying key, and toxic waste. Discard the toxic waste. Make the proving key and verifying key public. For simplicity, we assume that whoever did so can be trusted.

生成证明密钥，验证密钥和有毒废物。 丢弃有毒废物。 公开证明密钥和验证密钥。 为简单起见，我们假设这样做的人都是可以信任的。

3.生产随机盐 Generate a random salt

Using a commit-reveal scheme, the codemaster and codebreaker should arrive at a random salt. This is not part of the zk-SNARK, but helps to prevent a rainbow attack on the solution by the codebreaker.

使用提交发布方案，代码管理员和代码破解者应随机应变。 这不是zk-SNARK的一部分，但有助于防止密码破解程序对解决方案产生彩虹攻击。

4.开始游戏

Before each game, the codemaster should generate the following:

在每个游戏之前，代码管理员应生成以下内容：

a) the secret solution to the puzzle — e.g. G R Y B

b) the SHA256 hash of the solution and the salt

5. 猜一猜 Make a guess

For each turn, the codebreaker should send their guess to the codemaster, who should then generate the following:

对于每一回合，代码破解者都应将其猜测发送给代码管理员，然后由代码管理员生成以下内容：

a) the clue which corresponds to the secret solution and the guess;
与秘密解决方案和猜测相对应的线索；

b) a proof that the clue is correct, which is the result of computing:
提示是正确的证明，这是通过计算得出的：

proof = Prover(provingKey, pubGuess, pubClue, pubSolutionHash, privSolution)

The codemaster must then send the clue and the proof back to the codemaster, who can verify that the clue is valid by computing:

然后，代码管理员必须将线索和证据发送回代码管理员，后者可以通过计算来验证线索是否有效：

Verify(verifyingKey, pubGuess, pubClue, pubSolutionHash, proof)

6. 重复 Repeat

Perform step 5 until the codebreaker guesses the correct solution. Note that this implementation of Mastermind lets you make as many guesses as you want, and even after you reach the correct solution.

执行步骤5，直到密码破解者猜出正确的解决方案为止。 请注意，即使您已经找到正确的解决方案，Mastermind的这种实现也可以让您做出任意数量的猜测。

运行游戏

You need the TypeScript compiler tsc v2.7.2 or higher, and Node v10 or higher.

您需要TypeScript编译器tsc v2.7.2或更高版本，以及Node v10或更高版本。

You may use yarn or npm as your package manager, but the following instructions will use yarn.

您可以使用yarn或npm作为程序包管理器，但是以下说明将使用yarn。

PS:

NPM 安装 TypeScript
如果你的本地环境已经安装了 npm 工具，可以使用以下命令来安装。使用国内镜像：npm config set registry https://registry.npm.taobao.org
安装 typescript：npm install -g typescript
安装完成后我们可以使用 tsc 命令来执行 TypeScript 的相关代码，以下是查看版本号：$ tsc -v
Version 3.2.2

配置电路

1. Install dependencies

cd mastermind && \
yarn install && \
tsc

2. Compile the circuit

node build/mastermind/src/compile.js -i mastermind/circuits/mastermind.circom  -o mastermind/circuits/mastermind.json -r

3. Perform the trusted setup

This takes about 30 seconds if you use Node 10 or greater. Note that it will take about ten times longer to complete if you use Node 9, as Node 10 has more optimised BigInt support.

如果使用Node 10或更高版本，则大约需要30秒。 请注意，如果您使用Node 9，则完成所需的时间大约是原来的十倍，因为Node 10具有更优化的BigInt支持。

mkdir -p mastermind/setup && node build/mastermind/src/trustedsetup.js   -i mastermind/circuits/mastermind.json  -pk mastermind/setup/mastermind.pk.json   -vk mastermind/setup/mastermind.vk.json -r

4. Generate a sample proof and public signals in JS

Generate the proof and public signals for a sample input:
为样本输入生成证明和公共信号：

mkdir -p mastermind/proofs 
mkdir -p mastermind/signals

node build/mastermind/src/generateproof.js  -c mastermind/circuits/mastermind.json -vk mastermind/setup/mastermind.vk.json -pk mastermind/setup/mastermind.pk.json -po mastermind/proofs/mastermind.proof.json -so mastermind/signals/testsignals.json

5. Verify a sample proof in JS

To verify it, run:

node build/mastermind/src/test_js_verification.js  -c mastermind/circuits/mastermind.json   -vk mastermind/setup/mastermind.vk.json   -p mastermind/proofs/mastermind.proof.json   -s mastermind/signals/testsignals.json

在浏览器中运行游戏

首先，建立前端

cd frontend && \
yarn install && \
yarn build:prod

You may also run the frontend development server using yarn dev.

您也可以使用yarn dev运行前端开发服务器。

In a different terminal, set up virtualenv:

在另一个终端中，设置virtualenv：

cd backend && \
virtualenv -p python3 venv && \
source venv/bin/activate && \
pip3 install -r requirements.txt

Next, run the backend server in a separate terminal. Note that you have to set the NODE_PATH environment variable to a Node binary of version 10 or above.

接下来，在单独的终端中运行后端服务器。 请注意，您必须将NODE_PATH环境变量设置为版本10或更高版本的Node二进制文件。

export NODE_PATH='/path/to/node/10+' 

cd zkmm/backend && \
source venv/bin/activate && \
python3 manage.py migrate && \
python3 manage.py collectstatic -c --noinput && \
python3 manage.py runserver

Launch http://localhost:9000 for the development frontend environment, or http://localhost:8000 for the production frontend environment.

Make a guess and click on the Verify button to have the backend generate a proof, so that the frontend can verify the clue in the browse

为开发前端环境启动http：// localhost：9000，为生产前端环境启动http：// localhost：8000。

进行猜测，然后单击“验证”按钮以使后端生成证明，以便前端可以在浏览器中验证线索

三、Zero-knowledge proofs, a board game, and leaky abstractions: how I learned to write zk-SNARKs

原文（强烈推荐阅读，需翻墙）： https://weijiek.medium.com/how-i-learned-zk-snarks-from-scratch-177a01c5514e
参考URL: https://www.tuoluocaijing.cn/article/detail-49313.html

Zero-knowledge proofs, a board game, and leaky abstractions: how I learned zk-SNARKs from scratch

「A great way to learn a new skill is to build something with it.」

学一个技术的最好的办法是用它来做点什么事。作者讲了一个故事，当然很少有技术文章以故事的方式展开。他从一开始对零知识证明感兴趣，经过一番努力，把一个桌游游戏搬到了区块链上，这个游戏叫「MasterMind」。

这是一个古老的猜数字游戏。这个游戏需要两个人玩，一个出题者与一个解题者。出题者随机选四个数字，按顺序放好，然后解题者直接裸猜。假设有 N 个数字猜中，出题者则出示 N 个黑球，如果解题者猜中了 M 个数字，但是位置不对，出题者会出示 M 个白球。然后根据黑白球数量的提示，解题者再猜，如果解题者三次提示后仍然猜不对，则解题者输。否则，出题者输。

游戏搬到区块链上后，一个核心问题就是出题者不能作弊。这里零知识证明技术就派上了用场，出题者可以向解题者证明，他的「黑白球提示」是完全正确的，没有作弊。

但是作者实现好最初版本后，发现性能差的无法忍受，用户体验很差。接下来他在各种尝试之后，发现了 ZCash 用 Pedersen Hash 替换掉了 SHA256。

从传统上看，Pedersen Hash 是一个存在了很多很多年的古老算法，一直被认为非常低效而已经被人遗忘。但是在 零知识证明技术 zkSNARK 中，Pedersen Hash 的构造电路却可以非常精简，性能居然出奇地好。电路规模大概只有 SHA256 的 三十分之一。（插一句：技术永远不会过时，过时的永远是观念）

于是作者选用了这个古老的算法之后，把这个游戏的性能足足提升了 6 倍。下面是这个游戏代码的链接：https://github.com/weijiekoh/zkmm

区块链技术发展目不暇接，不知道大家有没有跟我一样有点焦虑，「Jumping straight into building」，做点东西，这是迅速提高技术能力的秘诀。