你怎么证明你知道——零知识证明

45934

一、问题定义
       零知识证明主要解决的问题是，让一方像另一方证明他知道某个问题的答案但却不想透露该问题的具体答案。具体来说，对一个可清晰描述的论断，一个证明方（Prover）能通过与验证方（Verifier）的交互使其确信论断是正确的，但除此之外验证方一无所知。所谓的零知识，就是指验证方除了对论断判断的结果（错或对）之外，无法获取任何额外信息。
例如，我知道你在学院里银行里存了多少英镑，但不能直接说出来，那么我要怎么向你证明我确实知道。

二、特点

• 完备性（Completeness）：若一个证明方确实掌握了某论断的答案，则他肯定能找到方法向验证方证明他手中掌握的数据的正确性，即真的假不了。（对应上面英镑的例子，我是证明方，我肯定能够想办法说服验证方，我真的知道你存了多少英镑）
• 可靠性（Soundness）：若一证明方根本不掌握某论断的答案，则他无法（或只能以极低概率）说服验证方他手中所谓答案的准确性，即假的真不了。（对应上面英镑的例子，我如果不知道，那么也没办法蒙混过关让验证方误以为我知道）
• 零知识性（Zero-knowledgeness）：验证方除了知道证明的结果外，对其他信息一无所知。
  

三、如何构造零知识证明
      零知识证明要求，证明方不直接回答本问题的具体答案，而是通过证明自己知道其他问题的答案来说服验证方。什么样的”其他问题的答案“能够间接判断本问题的答案？就是与本问题答案具有强相关性的其他答案。
      也就是让验证方知道一些，只有知道本问题答案后才能知道或做到的事情。验证方通过这些事情，来判断出证明方确实知道答案。
       以上述例子为例，我要怎么向你证明我知道你存了多少英镑。
      比如，我向你列出了你，以往每次的存入和取出操作的日期。那么很大概率也是知道你的存储的总金额的。
      或是，你想我多次验证，某天存入或取出了多少英镑，我给出了确切的答案，那么我也是有很大概率知道你存储总额的。

      零知识证明不像其他数学证明一样，具有明确的推论逻辑和确切的结果。它偏向于概率论证，验证后是让你大概率的相信，如果能够完全确信，那么其实答案也就是出来了，此时就不是零知识了。

四、案例
交互式零知识证明——色盲游戏
       A是色盲，B不是色盲。B手上有两个大小，形状完全一样的球，但两个球颜色不一样，一个红色，一个蓝色。由于A是色盲，无法分边两个球是否一样，所以B要向A证明两个球是不一样的。这里的A就是验证者，B是证明者。
      B需要在A不能获得两个球的颜色的情况下，向A证明这两个球的颜色是不一样的这个事实，这与零知识证明的定义是相符合的。具体证明方法为：
A当B的面拿起两个球，左手拿蓝球，右手拿红球，然后将双手放到背后，这样B就看不到A手上的球了，A在背后随机交换左右手上的球，交换完成后A将手伸出，并询问B两个球是否交换过位置，如果B能看到球上的颜色，那么每次A换过球的位置后，B都能正确回答出A的问题。
      了解概率论的同学应该知道，随着实验次数增加，两个球不一样的概率越大。当然有极小概率，B每次都蒙对。
非交互零知识证明——数独游戏
        A为了向B证明他解决一个数独难题，但不能告诉B具体的答案。A想到了一个办法，对于9乘9数独题，A制作了81张卡片，包括了9套1-9的数字，然后将题面的数字用卡片正面表示，答案数据用卡面背面表示，摆放过程中B禁止观看。摆放完，B可以任意选择一行一列或每个九宫格内的卡片取出，然后打乱后翻开，看看数值是否在1-9之间。可以多次重复改过程，如果A是真的解决了，那么无论重复多少次和选择哪一行一列一宫，都能看到1-9九张数字牌。
      当然，还有极小的概率，A知道B会选择哪一行一列一宫，只保证那一块的卡片不重复。

204094

"我知道你有多少英镑!"
"啊，你是怎么知道的!?!?!?"
"害嗨害，我看的你主页!!!"

（哈哈哈开个玩笑，帖很有用，感谢分享~

169280

帖很有用，先赞在看！！！

188423

感谢分享！

177252

感谢分享

189915

“你是不是外面有人了？我们分手吧！”
“你怎么知？不对，我没有啊！”
“给你看病把脉的老中医是我爸爸！不信吗？我还能拿出给你开的方子！还不信吗？我能说出你是哪天开始去看的中医，还不信吗？你看的中医的姓没发现和我一个姓吗？还有，你手机里2022年10月31日23点36分和小樱桃的对话为什么要亲？”

195208

感谢分享

204207

感谢分享

156723

谢谢分享

196169

感谢分享~