×

Χρησιμοποιούμε cookies για να βελτιώσουμε τη λειτουργία του LingQ. Επισκέπτοντας τον ιστότοπο, συμφωνείς στην πολιτική για τα cookies.


image

李永乐老师 Youtube, 神奇的零知识证明!既能保守秘密,又让别人信你!

神奇 的 零 知识 证明 !既 能 保守 秘密 ,又 让 别人 信 你!

各位 同学 好 我 是 李永乐 老师 最近 有个 小朋友 跟 我 说 他 已经 成功 地 证明 了 哥德巴赫猜想 但是 投稿 到 专业 的 数学 期刊 没有 人理 他 他 又 不敢 随便 的 把 证明 过程 发给 别人 他 害怕 别人 窃取 他 的 成果 他 想 问 我 有没有 这样 一种 方法 既 不 把 证明 过程 展示 给 大家 也 能 让 别人 相信 他 已经 成功 证明 了 这个 猜想 呢 其实 这种 需求 在生活中 还是 挺 常见 的 比如说 有 一个 人 他融 了 一大笔钱 说 要造 汽车 结果 过 了 两年 这车 也 没有 造出来 于是 有人 说 他 就是 个 骗子 这个 时候 他 如果 把 自己 的 技术细节 公开 的话 就 会 被 对手 窃取 自己 的 成果 但是 他 如果 不 公开 自己 的 技术细节 又 没有 办法 平息 这场 质疑 他 该 怎么办 呢 其实 这种 问题 在 数学 上 是 有 解答 的 它 的 名字 叫做 零 知识 证明 零 知识 证明 所谓 零 知识 证明 的 意思 就是 我 不 告诉 你 证明 过程 本身 但是 我 却 能 让 你 相信 我 已经 得到 这个 证明 了 我 不 告诉 你 技术细节 但是 我 却 让 你 相信 我 掌握 这个 技术细节 了 这 就 叫 零 知识 证明 它 是 1985 年 的 时候 MIT 的 两位 科学家 还有 多伦多 大学 的 一位 科学家 一起 提出 来 的 我们 来 具体 说一说 零 知识 证明 中有 两个 人 一个 人 叫做 证明 者 证明 者 我们 用 P 来 表示 证明 者 还有 一个 叫做 验证 者 验证 者 证明 者 希望 验证 者 相信 自己 掌握 了 某种 技能 那 怎么办 呢 就是 让 验证 者 提问 验证 者 提出 一些 问题 然后 证明 者 根据 自己 掌握 的 知识 来 回答 这些 问题 在 提问 和 回答 的 过程 中 证明 者 怎么样 证明 者 P 他 不能 提供 任何 有 意义 的 信息 不能 提供 任何 有 意义 的 信息 比如说 我 证明 了 哥德巴赫猜想 你 不能 问 我 是 怎么 证 的 这个 不能 提供 有 意义 的 信息 但是 通过 这些 个 问答 这个 V 却 能够 相信 相信 这个 P 的确 是 已经 掌握 了 掌握 了 这种 信息 这个 事 就 非常 神奇 就是 我 没有 提供 任何 有 意义 的 信息 但是 你 却 相信 我 的确 掌握 了 某种 你 不 知道 的 东西 是不是 这 就 叫 零 知识 证明 一般来讲 零 知识 证明 有 三个 条件 第一个 条件 我们 称之为 完备 性 所谓 完备 性 的 意思 就是 真的假 不了 就 假如 说 证明 者 掌握 了 某种 技能 或者 能力 的话 那么 验证 者 提出 的 这些 问题 证明 者 是 很 容易 回答 的 比如说 你 掌握 了 哥德巴赫猜想 的 证明 过程 那 我 问 你 的 这些 问题 你 肯定 很 轻松 就 回答 出来 了 你 回答 出来 之后 我 这个 验证 者 也 很 容易 验证 你 回答 都 是 正确 的 对 吧 很 容易 验证 真的假 不了 叫 完备 性 第二个 叫做 合理性 合理性 的 意思 就是 假 的 真 不了 意思 是 假如 你 不 掌握 这个 能力 或者 是 技能 的话 那 我 提 的 问题 你 是 没法 回答 的 你 可以 瞎蒙 但 你 瞎蒙 的话 咱们 几轮 之后 我 就 很 容易 发现 你 的 问题 对 吧 因为 你 答案 都 是 错 的 那 就 说明 你 不 掌握 这种 知识 或者 技能 这 叫 假 的 真 不了 合理性 第三个 叫做 零 知识 虽然 我们 一个 提问 一个 回答 而且 重复 了 很 多次 但是 最后 的 结果 是 验证 者 除了 知道 证明 者 已经 掌握 了 这个 信息 这件 事 以外 别的 一无所知 我 知道 你 已经 证明 了 哥德巴赫猜想 但是 我 却 不 知道 你 怎么 证明 的 对 吧 这个 过程 就 叫做 零 知识 证明 那么 具体 是 如何 实现 的 呢 咱们 来 举个 例子 我们 把 它 带入 到 一个 童话 之中 叫做 《 阿里巴巴 与 四十 大盗 》 《 阿里巴巴 与 四十 大盗 》 这个 故事 很多 人 都 听 过 是 吧 就是 阿拉伯 的 一个 童话 我们 把 这个 故事 改编 一下 说 这个 四十 大盗 有 一天 拿到 了 一张 藏宝图 这个 藏宝图 指示 有 一大批 宝藏 藏 在 一个 地方 但是 中间 会 有 一些 关卡 这些 个 关卡 只有 特殊 技能 的 人才 能够 把 它 找到 于是 四十 大盗 就 把 阿里巴巴 给 抓住 了 说 阿里巴巴 你 得 帮 我 打开 这些 关卡 然后 找到 这个 宝藏 阿里巴巴 就 想 了 如果 我 要是 帮 四十 大盗 打开 这些 关卡 的话 那 四十 大盗 就 会 觉得 我 没用 把 我 杀 了 如果 我 不 告诉 四十 大盗 怎么 打开 这些 关卡 的话 四十 大盗 会 觉得 我 不 知道 没有 意义 也 把 我 杀 了 对 吧 我 怎么样 才能 让 四十 大盗 相信 我 确实 掌握 这个 能力 但是 我 就是 不帮 你 开 是 吧 怎么 才能 做到 这 一点 呢 这 就 需要 用到 零 知识 证明 了 那 具体 怎么 做到 呢 我们 来看 第一关 第一关 是 什么 呢 第一关 叫做 分球 就是说 在 这里 有 很多 的 球 有 的 球 是 红色 的 有 的 球 是 绿色 的 你 把 它们 分开 这一关 就 过 了 有人 说 这 不是 很 简单 的 吗 你 对于 正常人 来讲 是 很 简单 的 说 这个 阿里巴巴 他 是 一个 正常 的 青年 巴巴 他 是 一个 色觉 正常 的 青年 但是 这 四十 大盗 都 是 一个 色盲 的 妈妈 生 出来 的 对 吧 他们 都 是 色盲 大盗 他 是 什么 呢 他们 都 是 色盲 他们 没有 办法 区分 红色 和 绿色 所以 这一关 大盗 做不了 只能 阿里巴巴 做 但是 阿里巴巴 又 不 愿意 帮 四十 大盗 正式 地 分开 这些 球 他 只要 四十 大盗 相信 他 具有 这个 能力 就行了 怎么 做到 呢 其实 不难 可以 这么 做 他们 两个 首先 找 两个 颜色 不同 的 球 比如 阿里巴巴 挑出来 的 一个 是 绿色 的 球 还有 一个 球是 红色 的 球 然后 让 四十 大盗 拿 着 四十 大盗 拿 这 两个 球说 阿里巴巴 你 看吧 你 看好 了 哪个 球是 红 的 哪个 球是 绿 的 虽然 我 自己 分 不 出来 但是 你 看好 了 看好 了 之后 这 四十 大盗 就 把 这个 球 放在 身后 然后 随机 地 交换 可能 交换 可能 不 交换 然后 拿到 前面 来 再 问 说 你 看 这 两个 球是 交换 了 位置 还是 没有 交换 位置 你 告诉 我 如果 阿里巴巴 是 一个 正常 的 青年 的话 他 就 可以 很 容易 的 分辨 出来 这 两个 球 交换 了 或者 没 交换 因为 颜色 不 一样 对 不 对 如果 阿里巴巴 也 是 一个 色盲 他 只能 瞎蒙 瞎蒙 的话 只有 50% 的 可能性 可以 蒙对 然后 四十 大盗 还 可以 再 把 这 两球 放到 后面 去 再 随机 交换 或者 不 交换 拿到 前面 问 你 你 告诉 我 交换 了 还是 没 交换 如果 这个 时候 阿里巴巴 再次 蒙对 了 概率 只有 1/4 三次 蒙对 概率 1/8 四次 蒙对 概率 1/16 如果 我们 做 了 十几 二十次 这样 的 实验 你 都 一直 能 说 对 的话 那 我 估计 阿里巴巴 你 不是 蒙 的 你 真的 是 能够 分辨 红球 和 绿球 对 不 对 这 就是 一个零 知识 证明 的 过程 在 以前 我 讲 过 一个 童话 叫做 《 皇帝 的 新装 》 说 有 两个 骗子 造 了 一件 根本 不 存在 的 衣服 跟 皇帝 说 只有 聪明人 才能 看得见 那 皇帝 要 想 区分 这 两个 人 是不是 骗子 其实 很 容易 把 这 两个 骗子 分开 然后 皇帝 找 两个 侍卫 让 这个 骗子 随机 地 把 衣服 穿 到 某 一个 侍卫 的 身上 比如说 皇帝 说 了 你 穿 到 第一个 侍卫 身上 然后 皇帝 把 第二个 骗子 找 过来 说 你 告诉 我 衣服 穿 在 谁 身上 如果 你 答对 了 的话 咱们 再 来 第二轮 再 找 两个 侍卫 让 第一个 骗子 把 这个 衣服 穿 到 某 一个 人 身上 然后 再 找 第二个 骗子 问 说 你 告诉 我 衣服 在 谁 身上 来 这么 几轮 之后 就 能 区分 到底 这件 衣服 是 存在 的 还是 不 存在 的 不 存在 就 把 这 俩 骗子 拉出去 砍 了 好 这是 第一关 那么 假如 说 这一关 验证 通过 了 这个 四十 大盗 相信 阿里巴巴 是 一个 色觉 正常 的 青年 了 他们 就 来到 第二 关 这个 第二 关是 什么 呢 第二 关是 阿里巴巴 的 山洞 说 这 山洞 里边 有 一扇门 只有 你 知道 咒语 才能 让 这个 山洞 里边 的 门 打开 当然 我们 都 知道 咒语 就是 芝麻开门 但是 假如 说 四十 大盗 是 不 知道 的 是 吧 阿里巴巴 知道 但是 也 不想 告诉 他们 那 怎么办 呢 有 一种 方法 大家 看 这个 山洞 长得 比较 奇怪 是 这个 样子 的 长得 是 这个 样子 的 然后 里面 有 两条路 中间 还有 一道 门 这 道门 是 关闭 的 是 吧 好 有 两条路 一个 是 A 一个 是 B 现在 首先 阿里巴巴 先 过来 这 阿里巴巴 他 先 随机 地进 到 某 一个 地方 藏 起来 比如说 阿里巴巴 进到 A 这个 地方 藏 起来 了 藏 起来 了 之后 四十 大盗 就 过来 了 四十 大盗 没有 看到 阿里巴巴 刚才 进 了 哪个 山洞 然后 四十 大盗 就 喊一声 说 阿里巴巴 你 给 我 从 A 出来 那 阿里巴巴 本来 藏到 A 的 他 当然 可以 从 A 出来 了 对 不 对 如果 阿里巴巴 刚才 藏到 B 怎么办 如果 刚才 阿里巴巴 藏到 B 四十 大盗 让 他 从 A 出来 他 就 必须 打开 这 道门 然后 才能 从 A 出来 对 不 对 假如 说 阿里巴巴 不 知道 打开门 的 这个 密码 的话 那么 他 就 有 1/2 的 可能 能够 从 正确 的 地方 出来 是 吧 如果 两次 都 能够 正确 地 出来 的话 那么 蒙对 的 可能 只有 1/4 三次 都 能 正确 出来 的话 蒙对 的 可能 就是 1/8 对 不 对 那么 重复 个 几十次 之后 那 四十 大盗 就 会 相信 阿里巴巴 的确 知道 这个 门 的 咒语 虽然 阿里巴巴 没有 当 他 的 面 打开 这 扇门 有人 说 你 搞 这么 复杂 干什么 你 干脆 这么 办 你 让 阿里巴巴 就 直接 进到 A 里边 去 然后 你 就 跟 四十 大盗 说 你 让 他 从 B 出来 他 只要 能 从 B 出来 那 肯定 就 说明 他 打开 这个 门 了 你 这么 干 不行 吗 这么 干 不行 为什么 呢 因为 我们 要求 的 是 零 知识 证明 就是 除了 四十 大盗 你 知道 我能 打开 这 扇门 以外 其他人 都 是 不 知道 的 对 吧 如果说 我 先进 了 A 然后 你 让 我 从 B 出来 我 又 从 B 出来 了 这 你 可以 把 这个 东西 录下来 然后 给 别人 看 那 别人 也 就 知道 了 我 阿里巴巴 具有 这个 能力 了 但是 假如 说 我 开始 先 随机 进 你 看不见 然后 等 你 过来 的 时候 随机 喊 我 又 从 这个 地方 出来 就算 咱们 每 一次 都 说 对 了 你 把 这个 东西 录下来 给 别人 看 那 别人 可能 会 说 阿里巴巴 你 和 四十 大盗 串通 好 的 呀 对 不 对 所以 别人 不会 相信 阿里巴巴 知道 这个 门 的 咒语 因此 就 连 阿里巴巴 知道 门 咒语 这件 事 也 只有 四十 大盗 知道 别人 都 不 知道 因此 我们 称之为 零 知识 证明 是 吧 这 就是 特别 神奇 的 一个 地方 行 吧 这 第二 关 也 过 了 下面 是 第三关 第三关 就 更加 数学 化 了 什么 呢 叫做 数独 只有 解开 一个 数独 的 人才 能 通过 这一关 什么 叫 数独 呢 我们 来画 一下 好 数独画 完 了 这是 一个 9×9 的 格子 中间 有 一些 数字 还有 一些 空白 你 要 把 这些 空白 都 填上 1 到 9 这 九个 整数 使得 每 一行 都 是 1 到 9 这 九个 数字 每 一列 也 都 是 1 到 9 这 九个 数字 而且 这 9 个 方块 这 9 个 3×3 的 方块 1 个 2 个 3 个 4 个 5 个 6 个 7 个 8 个 9 个 这 九个 3×3 的 方块 也 必须 是 1 到 9 这 九个 数字 是 吧 行 列和块 每 一个 区域 里 都 是 1 到 9 你 把 它 填 完 了 就 说明 这个 数独 完成 了 数独 是 一个 世界 上 很 流行 的 一个 数学 游戏 好 那么 现在 阿里巴巴 就 过来 了 他 说 我 这 数独 我 能 填得 上 四十 大盗 不 信 说 你 给 我 填上 阿里巴巴 说 但是 我 不能 让 你 知道 那 阿里巴巴 怎么 做 呢 他 可以 首先 把 这个 数字 1 到 9 写到 一些 牌上 然后 把 这个 牌扣 着 放到 这些 个 格子 里 就 每个 格子 都 放牌 是 吧 每个 格子 都 放 都 放 好 了 把 这个 格子 填满 了 之后 注意 我 这些 牌 都 是 扣过去 的 我 只有 翻过来 你 才能 知道 是 什么 然后 我 让 四十 大盗 说 说 你 现在 选 吧 你 是 选行 还是 选列 还是 选格 比如说 四十 大盗 说 我 选行 那么 于是 阿里巴巴 就 会 把 每 一行 的 这些 个牌 都 收集 到 一个 袋子 里 是 吧 每 一行 的 牌 都 收集 到 一个 袋子 里 一共 收集 到 九个 袋子 里 然后 把 每 一个 袋子 里边 抖落 抖落 让 里边 的 牌 重新 洗牌 然后 把 这些 牌 拿 出来 让 你 看 每 一个 袋子 里 的 牌 都 是 1 到 9 这 就 证明 了 每 一行 都 没 问题 对 不 对 这 四十 大盗 说 巴巴 你 是 瞎蒙 的 是 吧 我 不信 除非 你 重排 让 我 重新 来 一次 于是 阿里巴巴 还 可以 把 这些 牌 再 重新 摆回去 还是 扣 着 的 让 四十 大盗 选 说 你 选行 还是 选列 这回 四十 大盗 说 我 选列 于是 他 就 会 把 每 一列 的 这些 个牌 都 收到 一个 袋子 里 收完 了 之后 把 这个 袋子 晃荡 晃荡 洗 一下 牌 拿 出来 让 你 看 你 看 还是 1 到 9 对 不 对 四十 大盗 又 说 你 这次 又 是 蒙 的 阿里巴巴 就 会 说 那 我 怎么 知道 你 这次 要选 的 是 列 而 不是 行 呢 如果 我 凑列 是 对 的 那 你 行有 可能 会 不 对 如果 行是 对 的 你 每 一个 格 可能 不 对 只要 你 每 一次 在 行 列 还有 格中 是 吧 你 要不然 选行 你 要不然 选列 你 要不然 选格 如果 每 一次 我 都 能够 向 你 展示 我 这个 行 这个 列 或者 这个 格 都 是 1 到 9 这 九个 数字 的话 就 说明 我 有 极大 的 可能 是 真的 知道 答案 所以 只要 你 多 验证 几次 这个 阿里巴巴 就 可以 证明 他 确实 知道 这个 答案 了 但 问题 是 他 没有 向 四十 大盗 透露 这个 数独 游戏 怎么 填 的 任何 的 信息 他 每 一次 都 把 牌收 起来 之后 晃荡 晃荡 所以 你 根本 不 知道 这些 个牌 都 是 数字 几 是 吧 你 没有 办法 知道 任何 的 这个 填法 好 第三关 也 通过 了 那么 第四 关 就是 什么 呢 就是 染色 问题 大家 知道 一个 四色 地图 问题 吗 说 任何 一张 世界地图 都 可以 用 四种 颜色 把 它 涂满 并且 相邻 的 国家 颜色 不 一样 这个 是 已经 被 数学家 证明 的 但是 地图 不 一定 能 用 三种 颜色 涂满 使得 相邻 的 国家 颜色 不 一样 这 是 不 一定 的 有 的 图 可以 有 的 图 不行 比如 给 你 画 一个 图 说 这 是 一张 世界地图 这个 地图 中有 很多 个 比如说 国家 是 吧 你 说 用 三种 颜色 红 黄 蓝给 我 把 它 涂满 了 其实 也 不难 比如 这涂 第一种 颜色 这涂 第二种 颜色 这涂 第三种 颜色 这涂 第一种 颜色 这涂 第二种 颜色 这涂 第三种 颜色 这 不 就是 相邻 的 国家 颜色 不 一样 的 吗 所以 这个 就是 可以 做到 的 但 也 有 一些 图是 不能 做到 的 比如说 我 给 你 画 一张 世界地图 这个 世界地图 里面 国家 是 这么 分布 的 是 这样 分布 的 这 一共 是 四个 国家 你 告诉 我 怎么 涂 吧 你 看 假如 这涂 第一种 颜色 这涂 第二种 颜色 这涂 第三种 颜色 那 你 外边 这涂 什么 颜色 你 外边 只能 涂 第四种 颜色 了 所以 说 这个 就是 三种 颜色 无法 涂满 的 一个 染色 问题 所以 有 的 地图 可以 用 三种 颜色 涂 有 的 地图 不能 用 三种 颜色 涂 这 就是 所谓 的 染色 问题 好 假如 说 到 了 这一关 是 要求 你 用 三种 颜色 把 这 张图 给 涂满 而且 相邻 的 区域 颜色 不能 一样 阿里巴巴 说 我 知道 怎么 涂 四十 大盗 说 我 不信 阿里巴巴 怎么 做 呢 阿里巴巴 可以 这么 干 把 这个 三种 不同 颜色 的 序号 比如说 一 二 三 是 吧 装 到 一个 信封 里 这装 一个 信封 这装 一个 信封 这装 一个 信封 这些 信封 都 是 扣 着 的 所以 你 根本 不 知道 里边 的 代号 是 几 是 吧 我 都 放 好 了 阿里巴巴 已经 放好 了 然后 我 告诉 四十 大盗 说 现在 你 可以 验证 了 你 可以 随机 挑选 两个 区域 我 把 这 两个 信封 打开 让 你 看 它 里面 的 数字 是 不 一样 的 就 代表 这 两个 区域 颜色 确实 不同 比如说 大盗 说 了 你 给 我 挑 这 两个 吧 打开 一看 一个 是 1 一个 是 3 说明 我 这种 方法 这 两个 区域 颜色 的确 是 不 一样 的 当然 你 只 验证 这 两个 是 不够 的 你 说 我 还 想 验证 这 两个 你 注意 你 不能 连续 的 打开 信封 否则 的话 四十 大盗 就 会 知道 这个 图上 怎么 填 的 这些 信息 了 那么 于是 你 验证 完 第一遍 之后 阿里巴巴 必须 把 这些 牌 拿 回来 让 1 2 3 这 三个 数字 轮换 一下 什么 叫 轮换 呢 你 可以 让 1 变成 2 2 变成 3 3 变成 1 你 也 可以 让 1 变成 3 3 变成 1 2 不变 你 随机 轮换 轮换 完 了 之后 重新 填上去 这个 时候 当 四十 大盗 再 问 说 你 打开 这 两个 吧 打开 的 时候 他 看到 的 这 两个 是 2 和 3 也 没有 任何 意义 因为 第一次 这 两个 是 1 和 3 和 第二次 这 两个 2 和 3 所 代表 的 颜色 不 一定 是 相同 的 大家 明白 这个 问题 了 吗 所以 说 就算 你 重复 了 很多很多 次 每 一次 验证 我 都 通过 了 你 也 只能 是 知道 我 应该 知道 这 这个 地图 怎么 填 但是 你 却 不 知道 具体 的 填法 这 就是 所谓 的 零 知识 证明 是不是 而且 还有 一位 美国 数学家 名字 叫做 威格森 他 是 今年 的 阿贝尔 奖 获得者 他 就 讲述 了 这个 例子 而且 威格森 还 说 了 这样 的 一个 问题 他 说 任何 一个 数学 的 命题 比如说 哥德巴赫猜想 或者 是 这个 什么 费马大 定理 或者 黎曼 猜想 这些 问题 任何 一个 数学 命题 你 都 可以 怎么样 你 都 可以 转化成 一个 NP 完全 问题 这个 NP 完全 问题 咱们 以后 再 去 解释 这 概念 还 挺 复杂 的 而且 所有 的 NP 完全 问题 它 的 复杂度 是 等价 的 换句话说 你 解决 了 一个 NP 完全 问题 其他 的 NP 完全 问题 也 可以 在 比较 短 的 时间 内 把 它 解决 那么 哪 一个 问题 是 NP 完全 问题 呢 这里 边 的 这个 三 染色 问题 它 就是 一个 NP 完全 问题 就是 哪 一个 地图 可以 三 染色 如何 三 染色 这 就是 一个 NP 完全 问题 大家 听 明白 这个 逻辑 了 吗 就是 任何 一个 数学 命题 你 都 可以 转换成 一个 地图 的 形式 你 只要 能够 把 这个 地图 进行 成功 的 三 染色 你 就 可以 证明 这个 命题 是 真的 如果 这个 命题 是 假 的 就 说明 你 这个 地图 是 无法 三 染色 的 是 吧 于是 这位 同学 说 我 证明 了 哥德巴赫猜想 但是 我 却 不想 别人 知道 我 怎么 做 第一步 把 你 这个 数学 命题 哥德巴赫猜想 转化成 一个 地图 的 三 染色 问题 转化成 一张 图 这个 图 可能 非常 非常 庞大 可能 有 几十亿 个 区域 第二步 把 这个 地图 进行 三 染色 你 只要 能够 染色 成功 你 就 证明 了 你 的 结论 对 吧 当然 说 你 不 需要 告诉 我 你 怎么 染色 的 你 只 需要 把 你 那个 颜色 代号 放在 信封 里 然后 铺满 这个 地图 让 我 去 检验 每 一次 我 检验 之后 你 就 轮换 调换 一下 然后 你 再 让 我 检验 我 检验 足够 多次 之后 我 就 可以 相信 你 的确 已经 证明 了 哥德巴赫猜想 但是 我 却 不 知道 你 是 怎么 证明 的 从而 实现 了 什么 实现 了 零 知识 证明 大家 听 明白 这 过程 了 吗 最后 给 大家 留 一个 思考题 假如 说 阿里巴巴 凭借 自己 的 机智 杀死 了 四十 大盗 并且 拿到 了 很多 的 财富 在 童话 中 阿里巴巴 的 哥哥 也 非常 有钱 因为 他 娶 了 一个 有钱 的 老婆 结果 阿里巴巴 和 他 哥哥 就 想 比较 一下 自己 的 财富 和 对方 的 财富 谁 多 但是 谁 也 不想 把 自己 真实 的 财富 说 出来 那么 他们 有没有 这样 一种 办法 可以 比较 自己 和 对方 的 财富 却 不 说出 自己 到底 有 多少 财富 呢 这个 问题 其实 是 图灵奖 获得者 清华大学 教授 姚期智 提出 的 一个 问题 叫做 百万富翁 问题 大家 如果 知道 这个 问题 的 答案 可以 在 评论 区里 留言 我 也 会 在 后面 的 节目 中为 大家 做 解答 大家 如果 喜欢 我 的 视频 可以 在 YouTube 账号 李永乐 老师 里 订阅 我 点击 小 铃铛 可以 第一 时间 获得 更新 信息

神奇 的 零 知识 证明 !既 能 保守 秘密 ,又 让 别人 信 你! Magical zero-knowledge proof! Keeps secrets and makes people believe you at the same time!

各位 同学 好 我 是 李永乐 老师 最近 有个 小朋友 跟 我 说 他 已经 成功 地 证明 了 哥德巴赫猜想 He has successfully proved the Goldbach conjecture 但是 投稿 到 专业 的 数学 期刊 没有 人理 他 But no one cares about him when submitting to a professional math journal 他 又 不敢 随便 的 把 证明 过程 发给 别人 他 害怕 别人 窃取 他 的 成果 他 想 问 我 有没有 这样 一种 方法 既 不 把 证明 过程 展示 给 大家 也 能 让 别人 相信 他 已经 成功 证明 了 这个 猜想 呢 其实 这种 需求 在生活中 还是 挺 常见 的 比如说 有 一个 人 他融 了 一大笔钱 说 要造 汽车 For example, there is a person who raised a large sum of money and said that he wants to build a car 结果 过 了 两年 这车 也 没有 造出来 于是 有人 说 他 就是 个 骗子 这个 时候 他 如果 把 自己 的 技术细节 公开 的话 就 会 被 对手 窃取 自己 的 成果 但是 他 如果 不 公开 自己 的 技术细节 又 没有 办法 平息 这场 质疑 他 该 怎么办 呢 其实 这种 问题 在 数学 上 是 有 解答 的 它 的 名字 叫做 零 知识 证明 Its name is zero-knowledge proof 零 知识 证明 所谓 零 知识 证明 的 意思 就是 我 不 告诉 你 证明 过程 本身 但是 我 却 能 让 你 相信 我 已经 得到 这个 证明 了 我 不 告诉 你 技术细节 但是 我 却 让 你 相信 我 掌握 这个 技术细节 了 这 就 叫 零 知识 证明 它 是 1985 年 的 时候 MIT 的 两位 科学家 还有 多伦多 大学 的 一位 科学家 一起 提出 来 的 我们 来 具体 说一说 零 知识 证明 中有 两个 人 一个 人 叫做 证明 者 证明 者 我们 用 P 来 表示 证明 者 还有 一个 叫做 验证 者 验证 者 证明 者 希望 验证 者 相信 自己 掌握 了 某种 技能 那 怎么办 呢 就是 让 验证 者 提问 验证 者 提出 一些 问题 然后 证明 者 根据 自己 掌握 的 知识 来 回答 这些 问题 在 提问 和 回答 的 过程 中 证明 者 怎么样 证明 者 P 他 不能 提供 任何 有 意义 的 信息 不能 提供 任何 有 意义 的 信息 比如说 我 证明 了 哥德巴赫猜想 你 不能 问 我 是 怎么 证 的 这个 不能 提供 有 意义 的 信息 但是 通过 这些 个 问答 这个 V 却 能够 相信 相信 这个 P 的确 是 已经 掌握 了 掌握 了 这种 信息 这个 事 就 非常 神奇 就是 我 没有 提供 任何 有 意义 的 信息 但是 你 却 相信 我 的确 掌握 了 某种 你 不 知道 的 东西 是不是 这 就 叫 零 知识 证明 一般来讲 零 知识 证明 有 三个 条件 第一个 条件 我们 称之为 完备 性 所谓 完备 性 的 意思 就是 真的假 不了 The so-called completeness means that true cannot be false 就 假如 说 证明 者 掌握 了 某种 技能 或者 能力 的话 那么 验证 者 提出 的 这些 问题 证明 者 是 很 容易 回答 的 比如说 你 掌握 了 哥德巴赫猜想 的 证明 过程 那 我 问 你 的 这些 问题 你 肯定 很 轻松 就 回答 出来 了 你 回答 出来 之后 我 这个 验证 者 也 很 容易 验证 你 回答 都 是 正确 的 对 吧 很 容易 验证 真的假 不了 叫 完备 性 It's easy to verify that it's true and it cannot be called completeness 第二个 叫做 合理性 合理性 的 意思 就是 假 的 真 不了 意思 是 假如 你 不 掌握 这个 能力 或者 是 技能 的话 那 我 提 的 问题 你 是 没法 回答 的 你 可以 瞎蒙 You can be blind 但 你 瞎蒙 的话 咱们 几轮 之后 我 就 很 容易 发现 你 的 问题 对 吧 因为 你 答案 都 是 错 的 那 就 说明 你 不 掌握 这种 知识 或者 技能 这 叫 假 的 真 不了 合理性 第三个 叫做 零 知识 虽然 我们 一个 提问 一个 回答 而且 重复 了 很 多次 但是 最后 的 结果 是 验证 者 除了 知道 证明 者 已经 掌握 了 这个 信息 这件 事 以外 别的 一无所知 我 知道 你 已经 证明 了 哥德巴赫猜想 但是 我 却 不 知道 你 怎么 证明 的 对 吧 这个 过程 就 叫做 零 知识 证明 那么 具体 是 如何 实现 的 呢 咱们 来 举个 例子 我们 把 它 带入 到 一个 童话 之中 叫做 《 阿里巴巴 与 四十 大盗 》 Called "Alibaba and the Forty Thieves" 《 阿里巴巴 与 四十 大盗 》 这个 故事 很多 人 都 听 过 是 吧 就是 阿拉伯 的 一个 童话 我们 把 这个 故事 改编 一下 说 这个 四十 大盗 有 一天 拿到 了 一张 藏宝图 这个 藏宝图 指示 有 一大批 宝藏 藏 在 一个 地方 但是 中间 会 有 一些 关卡 这些 个 关卡 只有 特殊 技能 的 人才 能够 把 它 找到 于是 四十 大盗 就 把 阿里巴巴 给 抓住 了 说 阿里巴巴 你 得 帮 我 打开 这些 关卡 然后 找到 这个 宝藏 阿里巴巴 就 想 了 如果 我 要是 帮 四十 大盗 打开 这些 关卡 的话 那 四十 大盗 就 会 觉得 我 没用 把 我 杀 了 如果 我 不 告诉 四十 大盗 怎么 打开 这些 关卡 的话 四十 大盗 会 觉得 我 不 知道 没有 意义 也 把 我 杀 了 对 吧 我 怎么样 才能 让 四十 大盗 相信 我 确实 掌握 这个 能力 但是 我 就是 不帮 你 开 是 吧 怎么 才能 做到 这 一点 呢 这 就 需要 用到 零 知识 证明 了 那 具体 怎么 做到 呢 我们 来看 第一关 Let's look at the first level 第一关 是 什么 呢 第一关 叫做 分球 The first level is called the split ball 就是说 在 这里 有 很多 的 球 有 的 球 是 红色 的 有 的 球 是 绿色 的 你 把 它们 分开 这一关 就 过 了 You just separate them 有人 说 这 不是 很 简单 的 吗 你 对于 正常人 来讲 是 很 简单 的 说 这个 阿里巴巴 他 是 一个 正常 的 青年 巴巴 他 是 一个 色觉 正常 的 青年 Babata is a youth with normal color vision 但是 这 四十 大盗 都 是 一个 色盲 的 妈妈 生 出来 的 对 吧 他们 都 是 色盲 大盗 他 是 什么 呢 他们 都 是 色盲 他们 没有 办法 区分 红色 和 绿色 所以 这一关 大盗 做不了 只能 阿里巴巴 做 但是 阿里巴巴 又 不 愿意 帮 四十 大盗 正式 地 分开 这些 球 他 只要 四十 大盗 相信 他 具有 这个 能力 就行了 怎么 做到 呢 其实 不难 可以 这么 做 他们 两个 首先 找 两个 颜色 不同 的 球 比如 阿里巴巴 挑出来 的 一个 是 绿色 的 球 还有 一个 球是 红色 的 球 然后 让 四十 大盗 拿 着 四十 大盗 拿 这 两个 球说 阿里巴巴 你 看吧 你 看好 了 哪个 球是 红 的 哪个 球是 绿 的 虽然 我 自己 分 不 出来 但是 你 看好 了 看好 了 之后 这 四十 大盗 就 把 这个 球 放在 身后 然后 随机 地 交换 可能 交换 可能 不 交换 然后 拿到 前面 来 再 问 说 你 看 这 两个 球是 交换 了 位置 还是 没有 交换 位置 你 告诉 我 如果 阿里巴巴 是 一个 正常 的 青年 的话 他 就 可以 很 容易 的 分辨 出来 这 两个 球 交换 了 或者 没 交换 因为 颜色 不 一样 对 不 对 如果 阿里巴巴 也 是 一个 色盲 他 只能 瞎蒙 瞎蒙 的话 只有 50% 的 可能性 可以 蒙对 If you are blind, there is only a 50% chance that you can be wrong 然后 四十 大盗 还 可以 再 把 这 两球 放到 后面 去 再 随机 交换 或者 不 交换 拿到 前面 问 你 你 告诉 我 交换 了 还是 没 交换 如果 这个 时候 阿里巴巴 再次 蒙对 了 概率 只有 1/4 三次 蒙对 概率 1/8 四次 蒙对 概率 1/16 如果 我们 做 了 十几 二十次 这样 的 实验 你 都 一直 能 说 对 的话 那 我 估计 阿里巴巴 你 不是 蒙 的 你 真的 是 能够 分辨 红球 和 绿球 对 不 对 这 就是 一个零 知识 证明 的 过程 在 以前 我 讲 过 一个 童话 叫做 《 皇帝 的 新装 》 说 有 两个 骗子 造 了 一件 根本 不 存在 的 衣服 跟 皇帝 说 只有 聪明人 才能 看得见 那 皇帝 要 想 区分 这 两个 人 是不是 骗子 其实 很 容易 把 这 两个 骗子 分开 然后 皇帝 找 两个 侍卫 让 这个 骗子 随机 地 把 衣服 穿 到 某 一个 侍卫 的 身上 比如说 皇帝 说 了 你 穿 到 第一个 侍卫 身上 然后 皇帝 把 第二个 骗子 找 过来 说 你 告诉 我 衣服 穿 在 谁 身上 如果 你 答对 了 的话 咱们 再 来 第二轮 再 找 两个 侍卫 让 第一个 骗子 把 这个 衣服 穿 到 某 一个 人 身上 然后 再 找 第二个 骗子 问 说 你 告诉 我 衣服 在 谁 身上 来 这么 几轮 之后 就 能 区分 到底 这件 衣服 是 存在 的 还是 不 存在 的 不 存在 就 把 这 俩 骗子 拉出去 砍 了 好 这是 第一关 那么 假如 说 这一关 验证 通过 了 这个 四十 大盗 相信 阿里巴巴 是 一个 色觉 正常 的 青年 了 他们 就 来到 第二 关 这个 第二 关是 什么 呢 第二 关是 阿里巴巴 的 山洞 说 这 山洞 里边 有 一扇门 只有 你 知道 咒语 才能 让 这个 山洞 里边 的 门 打开 当然 我们 都 知道 咒语 就是 芝麻开门 但是 假如 说 四十 大盗 是 不 知道 的 是 吧 阿里巴巴 知道 但是 也 不想 告诉 他们 那 怎么办 呢 有 一种 方法 大家 看 这个 山洞 长得 比较 奇怪 是 这个 样子 的 长得 是 这个 样子 的 然后 里面 有 两条路 中间 还有 一道 门 这 道门 是 关闭 的 是 吧 好 有 两条路 一个 是 A 一个 是 B 现在 首先 阿里巴巴 先 过来 这 阿里巴巴 他 先 随机 地进 到 某 一个 地方 藏 起来 比如说 阿里巴巴 进到 A 这个 地方 藏 起来 了 藏 起来 了 之后 四十 大盗 就 过来 了 四十 大盗 没有 看到 阿里巴巴 刚才 进 了 哪个 山洞 然后 四十 大盗 就 喊一声 说 阿里巴巴 你 给 我 从 A 出来 那 阿里巴巴 本来 藏到 A 的 他 当然 可以 从 A 出来 了 对 不 对 如果 阿里巴巴 刚才 藏到 B 怎么办 如果 刚才 阿里巴巴 藏到 B 四十 大盗 让 他 从 A 出来 他 就 必须 打开 这 道门 然后 才能 从 A 出来 对 不 对 假如 说 阿里巴巴 不 知道 打开门 的 这个 密码 的话 那么 他 就 有 1/2 的 可能 能够 从 正确 的 地方 出来 是 吧 如果 两次 都 能够 正确 地 出来 的话 那么 蒙对 的 可能 只有 1/4 三次 都 能 正确 出来 的话 蒙对 的 可能 就是 1/8 对 不 对 那么 重复 个 几十次 之后 那 四十 大盗 就 会 相信 阿里巴巴 的确 知道 这个 门 的 咒语 虽然 阿里巴巴 没有 当 他 的 面 打开 这 扇门 有人 说 你 搞 这么 复杂 干什么 你 干脆 这么 办 你 让 阿里巴巴 就 直接 进到 A 里边 去 然后 你 就 跟 四十 大盗 说 你 让 他 从 B 出来 他 只要 能 从 B 出来 那 肯定 就 说明 他 打开 这个 门 了 你 这么 干 不行 吗 这么 干 不行 为什么 呢 因为 我们 要求 的 是 零 知识 证明 就是 除了 四十 大盗 你 知道 我能 打开 这 扇门 以外 其他人 都 是 不 知道 的 对 吧 如果说 我 先进 了 A 然后 你 让 我 从 B 出来 我 又 从 B 出来 了 这 你 可以 把 这个 东西 录下来 然后 给 别人 看 那 别人 也 就 知道 了 我 阿里巴巴 具有 这个 能力 了 但是 假如 说 我 开始 先 随机 进 你 看不见 然后 等 你 过来 的 时候 随机 喊 我 又 从 这个 地方 出来 就算 咱们 每 一次 都 说 对 了 你 把 这个 东西 录下来 给 别人 看 那 别人 可能 会 说 阿里巴巴 你 和 四十 大盗 串通 好 的 呀 对 不 对 所以 别人 不会 相信 阿里巴巴 知道 这个 门 的 咒语 因此 就 连 阿里巴巴 知道 门 咒语 这件 事 也 只有 四十 大盗 知道 别人 都 不 知道 因此 我们 称之为 零 知识 证明 是 吧 这 就是 特别 神奇 的 一个 地方 行 吧 这 第二 关 也 过 了 下面 是 第三关 第三关 就 更加 数学 化 了 什么 呢 叫做 数独 只有 解开 一个 数独 的 人才 能 通过 这一关 什么 叫 数独 呢 我们 来画 一下 好 数独画 完 了 这是 一个 9×9 的 格子 中间 有 一些 数字 还有 一些 空白 你 要 把 这些 空白 都 填上 1 到 9 这 九个 整数 使得 每 一行 都 是 1 到 9 这 九个 数字 每 一列 也 都 是 1 到 9 这 九个 数字 而且 这 9 个 方块 这 9 个 3×3 的 方块 1 个 2 个 3 个 4 个 5 个 6 个 7 个 8 个 9 个 这 九个 3×3 的 方块 也 必须 是 1 到 9 这 九个 数字 是 吧 行 列和块 每 一个 区域 里 都 是 1 到 9 你 把 它 填 完 了 就 说明 这个 数独 完成 了 数独 是 一个 世界 上 很 流行 的 一个 数学 游戏 好 那么 现在 阿里巴巴 就 过来 了 他 说 我 这 数独 我 能 填得 上 四十 大盗 不 信 说 你 给 我 填上 阿里巴巴 说 但是 我 不能 让 你 知道 那 阿里巴巴 怎么 做 呢 他 可以 首先 把 这个 数字 1 到 9 写到 一些 牌上 然后 把 这个 牌扣 着 放到 这些 个 格子 里 Then buckle this card and put it in these grids 就 每个 格子 都 放牌 是 吧 每个 格子 都 放 都 放 好 了 把 这个 格子 填满 了 之后 注意 我 这些 牌 都 是 扣过去 的 Note that these cards are all deducted in the past 我 只有 翻过来 你 才能 知道 是 什么 You can only know what it is if I turn it over 然后 我 让 四十 大盗 说 说 你 现在 选 吧 你 是 选行 还是 选列 还是 选格 比如说 四十 大盗 说 我 选行 那么 于是 阿里巴巴 就 会 把 每 一行 的 这些 个牌 都 收集 到 一个 袋子 里 是 吧 每 一行 的 牌 都 收集 到 一个 袋子 里 一共 收集 到 九个 袋子 里 然后 把 每 一个 袋子 里边 抖落 抖落 让 里边 的 牌 重新 洗牌 然后 把 这些 牌 拿 出来 让 你 看 每 一个 袋子 里 的 牌 都 是 1 到 9 这 就 证明 了 每 一行 都 没 问题 对 不 对 这 四十 大盗 说 巴巴 你 是 瞎蒙 的 是 吧 我 不信 除非 你 重排 让 我 重新 来 一次 于是 阿里巴巴 还 可以 把 这些 牌 再 重新 摆回去 So Alibaba can put these cards back again 还是 扣 着 的 让 四十 大盗 选 说 你 选行 还是 选列 这回 四十 大盗 说 我 选列 于是 他 就 会 把 每 一列 的 这些 个牌 都 收到 一个 袋子 里 收完 了 之后 把 这个 袋子 晃荡 晃荡 洗 一下 牌 拿 出来 让 你 看 你 看 还是 1 到 9 对 不 对 四十 大盗 又 说 你 这次 又 是 蒙 的 阿里巴巴 就 会 说 那 我 怎么 知道 你 这次 要选 的 是 列 而 不是 行 呢 如果 我 凑列 是 对 的 If I make a list, it's right 那 你 行有 可能 会 不 对 如果 行是 对 的 你 每 一个 格 可能 不 对 只要 你 每 一次 在 行 列 还有 格中 是 吧 你 要不然 选行 你 要不然 选列 你 要不然 选格 如果 每 一次 我 都 能够 向 你 展示 我 这个 行 这个 列 或者 这个 格 都 是 1 到 9 这 九个 数字 的话 就 说明 我 有 极大 的 可能 是 真的 知道 答案 所以 只要 你 多 验证 几次 这个 阿里巴巴 就 可以 证明 他 确实 知道 这个 答案 了 但 问题 是 他 没有 向 四十 大盗 透露 这个 数独 游戏 怎么 填 的 任何 的 信息 他 每 一次 都 把 牌收 起来 之后 晃荡 晃荡 所以 你 根本 不 知道 这些 个牌 都 是 数字 几 是 吧 你 没有 办法 知道 任何 的 这个 填法 好 第三关 也 通过 了 那么 第四 关 就是 什么 呢 就是 染色 问题 大家 知道 一个 四色 地图 问题 吗 说 任何 一张 世界地图 都 可以 用 四种 颜色 把 它 涂满 并且 相邻 的 国家 颜色 不 一样 这个 是 已经 被 数学家 证明 的 但是 地图 不 一定 能 用 三种 颜色 涂满 使得 相邻 的 国家 颜色 不 一样 这 是 不 一定 的 有 的 图 可以 有 的 图 不行 比如 给 你 画 一个 图 说 这 是 一张 世界地图 这个 地图 中有 很多 个 比如说 国家 是 吧 你 说 用 三种 颜色 红 黄 蓝给 我 把 它 涂满 了 其实 也 不难 比如 这涂 第一种 颜色 这涂 第二种 颜色 这涂 第三种 颜色 这涂 第一种 颜色 这涂 第二种 颜色 这涂 第三种 颜色 这 不 就是 相邻 的 国家 颜色 不 一样 的 吗 所以 这个 就是 可以 做到 的 但 也 有 一些 图是 不能 做到 的 比如说 我 给 你 画 一张 世界地图 这个 世界地图 里面 国家 是 这么 分布 的 是 这样 分布 的 这 一共 是 四个 国家 你 告诉 我 怎么 涂 吧 你 看 假如 这涂 第一种 颜色 这涂 第二种 颜色 这涂 第三种 颜色 那 你 外边 这涂 什么 颜色 你 外边 只能 涂 第四种 颜色 了 所以 说 这个 就是 三种 颜色 无法 涂满 的 一个 染色 问题 所以 有 的 地图 可以 用 三种 颜色 涂 有 的 地图 不能 用 三种 颜色 涂 这 就是 所谓 的 染色 问题 好 假如 说 到 了 这一关 是 要求 你 用 三种 颜色 把 这 张图 给 涂满 而且 相邻 的 区域 颜色 不能 一样 阿里巴巴 说 我 知道 怎么 涂 四十 大盗 说 我 不信 阿里巴巴 怎么 做 呢 阿里巴巴 可以 这么 干 把 这个 三种 不同 颜色 的 序号 比如说 一 二 三 是 吧 装 到 一个 信封 里 这装 一个 信封 这装 一个 信封 这装 一个 信封 这些 信封 都 是 扣 着 的 所以 你 根本 不 知道 里边 的 代号 是 几 是 吧 我 都 放 好 了 阿里巴巴 已经 放好 了 然后 我 告诉 四十 大盗 说 现在 你 可以 验证 了 你 可以 随机 挑选 两个 区域 我 把 这 两个 信封 打开 让 你 看 它 里面 的 数字 是 不 一样 的 就 代表 这 两个 区域 颜色 确实 不同 比如说 大盗 说 了 你 给 我 挑 这 两个 吧 打开 一看 一个 是 1 一个 是 3 说明 我 这种 方法 这 两个 区域 颜色 的确 是 不 一样 的 当然 你 只 验证 这 两个 是 不够 的 你 说 我 还 想 验证 这 两个 你 注意 你 不能 连续 的 打开 信封 否则 的话 四十 大盗 就 会 知道 这个 图上 怎么 填 的 这些 信息 了 那么 于是 你 验证 完 第一遍 之后 阿里巴巴 必须 把 这些 牌 拿 回来 让 1 2 3 这 三个 数字 轮换 一下 什么 叫 轮换 呢 你 可以 让 1 变成 2 2 变成 3 3 变成 1 你 也 可以 让 1 变成 3 3 变成 1 2 不变 你 随机 轮换 轮换 完 了 之后 重新 填上去 这个 时候 当 四十 大盗 再 问 说 你 打开 这 两个 吧 打开 的 时候 他 看到 的 这 两个 是 2 和 3 也 没有 任何 意义 因为 第一次 这 两个 是 1 和 3 和 第二次 这 两个 2 和 3 所 代表 的 颜色 不 一定 是 相同 的 大家 明白 这个 问题 了 吗 所以 说 就算 你 重复 了 很多很多 次 每 一次 验证 我 都 通过 了 你 也 只能 是 知道 我 应该 知道 这 这个 地图 怎么 填 但是 你 却 不 知道 具体 的 填法 这 就是 所谓 的 零 知识 证明 是不是 而且 还有 一位 美国 数学家 名字 叫做 威格森 他 是 今年 的 阿贝尔 奖 获得者 他 就 讲述 了 这个 例子 而且 威格森 还 说 了 这样 的 一个 问题 他 说 任何 一个 数学 的 命题 比如说 哥德巴赫猜想 或者 是 这个 什么 费马大 定理 或者 黎曼 猜想 这些 问题 任何 一个 数学 命题 你 都 可以 怎么样 你 都 可以 转化成 一个 NP 完全 问题 这个 NP 完全 问题 咱们 以后 再 去 解释 这 概念 还 挺 复杂 的 而且 所有 的 NP 完全 问题 它 的 复杂度 是 等价 的 换句话说 你 解决 了 一个 NP 完全 问题 其他 的 NP 完全 问题 也 可以 在 比较 短 的 时间 内 把 它 解决 那么 哪 一个 问题 是 NP 完全 问题 呢 这里 边 的 这个 三 染色 问题 它 就是 一个 NP 完全 问题 就是 哪 一个 地图 可以 三 染色 如何 三 染色 这 就是 一个 NP 完全 问题 大家 听 明白 这个 逻辑 了 吗 就是 任何 一个 数学 命题 你 都 可以 转换成 一个 地图 的 形式 你 只要 能够 把 这个 地图 进行 成功 的 三 染色 你 就 可以 证明 这个 命题 是 真的 如果 这个 命题 是 假 的 就 说明 你 这个 地图 是 无法 三 染色 的 是 吧 于是 这位 同学 说 我 证明 了 哥德巴赫猜想 但是 我 却 不想 别人 知道 我 怎么 做 第一步 把 你 这个 数学 命题 哥德巴赫猜想 转化成 一个 地图 的 三 染色 问题 转化成 一张 图 这个 图 可能 非常 非常 庞大 可能 有 几十亿 个 区域 第二步 把 这个 地图 进行 三 染色 你 只要 能够 染色 成功 你 就 证明 了 你 的 结论 对 吧 当然 说 你 不 需要 告诉 我 你 怎么 染色 的 你 只 需要 把 你 那个 颜色 代号 放在 信封 里 然后 铺满 这个 地图 让 我 去 检验 每 一次 我 检验 之后 你 就 轮换 调换 一下 然后 你 再 让 我 检验 我 检验 足够 多次 之后 我 就 可以 相信 你 的确 已经 证明 了 哥德巴赫猜想 但是 我 却 不 知道 你 是 怎么 证明 的 从而 实现 了 什么 实现 了 零 知识 证明 大家 听 明白 这 过程 了 吗 最后 给 大家 留 一个 思考题 假如 说 阿里巴巴 凭借 自己 的 机智 杀死 了 四十 大盗 并且 拿到 了 很多 的 财富 在 童话 中 阿里巴巴 的 哥哥 也 非常 有钱 因为 他 娶 了 一个 有钱 的 老婆 结果 阿里巴巴 和 他 哥哥 就 想 比较 一下 自己 的 财富 和 对方 的 财富 谁 多 但是 谁 也 不想 把 自己 真实 的 财富 说 出来 那么 他们 有没有 这样 一种 办法 可以 比较 自己 和 对方 的 财富 却 不 说出 自己 到底 有 多少 财富 呢 这个 问题 其实 是 图灵奖 获得者 清华大学 教授 姚期智 提出 的 一个 问题 叫做 百万富翁 问题 大家 如果 知道 这个 问题 的 答案 可以 在 评论 区里 留言 我 也 会 在 后面 的 节目 中为 大家 做 解答 大家 如果 喜欢 我 的 视频 可以 在 YouTube 账号 李永乐 老师 里 订阅 我 点击 小 铃铛 可以 第一 时间 获得 更新 信息