×

LingQをより快適にするためCookieを使用しています。サイトの訪問により同意したと見なされます クッキーポリシー.

image

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

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

各位 同學 好 我 是 李永樂 老師 最近 有個 小朋友 跟 我 說 他 已經 成功 地 證明 了 哥德巴赫猜想 但是 投稿 到 專業 的 數學 期刊 沒有 人理 他 他 又 不敢 隨便 的 把 證明 過程 發給 別人 他 害怕 別人 竊取 他 的 成果 他 想問 我 有沒有 這樣 一種 方法 既 不 把 證明 過程 展示 給 大家 也 能 讓 別人 相信 他 已經 成功 證明 了 這個 猜想 呢 其實 這種 需求 在生活中 還是 挺 常見 的 比如說 有 一個 人 他融 了 一大筆錢 說 要造 汽車 結果 過了 兩年 這車 也 沒有 造出來 於是 有人 說 他 就是 個 騙子 這個 時候 他 如果 把 自己 的 技術細節 公開 的話 就 會 被 對手 竊取 自己 的 成果 但是 他 如果 不 公開 自己 的 技術細節 又 沒有 辦法 平息 這場 質疑 他 該 怎麼辦 呢 其實 這種 問題 在 數學 上 是 有 解答 的 它 的 名字 叫做 零 知識 證明 零 知識 證明 所謂 零 知識 證明 的 意思 就是 我 不 告訴 你 證明 過程 本身 但是 我 卻 能 讓 你 相信 我 已經 得到 這個 證明 了 我 不 告訴 你 技術細節 但是 我 卻 讓 你 相信 我 掌握 這個 技術細節 了 這就 叫 零 知識 證明 它 是 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 賬號 李永樂 老師 裏 訂閱 我 點擊 小 鈴鐺 可以 第一 時間 獲得 更新 信息

Learn languages from TV shows, movies, news, articles and more! Try LingQ for FREE

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

各位 同學 好 我 是 李永樂 老師 最近 有個 小朋友 跟 我 說 他 已經 成功 地 證明 了 哥德巴赫猜想 但是 投稿 到 專業 的 數學 期刊 沒有 人理 他 他 又 不敢 隨便 的 把 證明 過程 發給 別人 他 害怕 別人 竊取 他 的 成果 他 想問 我 有沒有 這樣 一種 方法 既 不 把 證明 過程 展示 給 大家 也 能 讓 別人 相信 他 已經 成功 證明 了 這個 猜想 呢 其實 這種 需求 在生活中 還是 挺 常見 的 比如說 有 一個 人 他融 了 一大筆錢 說 要造 汽車 結果 過了 兩年 這車 也 沒有 造出來 於是 有人 說 他 就是 個 騙子 這個 時候 他 如果 把 自己 的 技術細節 公開 的話 就 會 被 對手 竊取 自己 的 成果 但是 他 如果 不 公開 自己 的 技術細節 又 沒有 辦法 平息 這場 質疑 他 該 怎麼辦 呢 其實 這種 問題 在 數學 上 是 有 解答 的 它 的 名字 叫做 零 知識 證明 零 知識 證明 所謂 零 知識 證明 的 意思 就是 我 不 告訴 你 證明 過程 本身 但是 我 卻 能 讓 你 相信 我 已經 得到 這個 證明 了 我 不 告訴 你 技術細節 但是 我 卻 讓 你 相信 我 掌握 這個 技術細節 了 這就 叫 零 知識 證明 它 是 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 完全 問題 大家 聽 明白 這個 邏輯 了 嗎 就是 任何 一個 數學 命題 你 都 可以 轉換成 一個 地圖 的 形式 你 只要 能夠 把 這個 地圖 進行 成功 的 三 染色 你 就 可以 證明 這個 命題 是 真的 如果 這個 命題 是 假 的 就 說明 你 這個 地圖 是 無法 三 染色 的 是 吧 於是 這位 同 學說 我 證明 了 哥德巴赫猜想 但是 我 卻 不想 別人 知道 我 怎麼 做 第一步 把 你 這個 數學 命題 哥德巴赫猜想 轉化成 一個 地圖 的 三 染色 問題 轉化成 一張 圖 這個 圖 可能 非常 非常 龐大 可能 有 幾十 億個 區域 第二步 把 這個 地圖 進行 三 染色 你 只要 能夠 染色 成功 你 就 證明 了 你 的 結論 對 吧 當然 說 你 不 需要 告訴 我 你 怎麼 染色 的 你 只 需要 把 你 那個 顏色 代號 放在 信封 裏 然後 鋪滿 這個 地圖 讓 我 去 檢驗 每 一次 我 檢驗 之後 你 就 輪換 調換 一下 然後 你 再 讓 我 檢驗 我 檢驗 足夠 多次 之後 我 就 可以 相信 你 的確 已經 證明 了 哥德巴赫猜想 但是 我 卻 不 知道 你 是 怎麼 證明 的 從而 實現 了 什麼 實現 了 零 知識 證明 大家 聽 明白 這 過程 了 嗎 最後 給 大家 留 一個 思考題 假如 說 阿 裏 巴巴 憑 借 自己 的 機智 殺死 了 四十 大盜 並且 拿到 了 很多 的 財富 在 童話 中 阿 裏 巴巴 的 哥哥 也 非常 有錢 因為 他 娶 了 一個 有錢 的 老婆 結果 阿 裏 巴巴 和 他 哥哥 就 想 比較 一下 自己 的 財富 和 對方 的 財富 誰 多 但是 誰 也 不想 把 自己 真實 的 財富 說 出來 那麼 他們 有沒有 這樣 一種 辦法 可以 比較 自己 和 對方 的 財富 卻 不 說出 自己 到底 有 多少 財富 呢 這個 問題 其實 是 圖靈獎 獲得者 清華大學 教授 姚期智 提出 的 一個 問題 叫做 百萬富翁 問題 大家 如果 知道 這個 問題 的 答案 可以 在 評論 區裏 留言 我 也 會 在 後面 的 節目 中為 大家 做 解答 |||||||for||| 大家 如果 喜歡 我 的 視頻 可以 在 YouTube 賬號 李永樂 老師 裏 訂閱 我 點擊 小 鈴鐺 可以 第一 時間 獲得 更新 信息