zkp

5/29 確認分工
6/5 PowerPoint要做好
6/10 上傳影片

1.第一位報告的同學要說明接下來報告的順序
2.每個報告的同學在報告前先自我介紹一下


## 小故事時間
+ 以"百萬富翁問題"做發想

在一個風和日麗的下午，兩位老朋友──亞歷克斯和鮑勃──坐在公園的長椅上。他們都是成功的商人，經常在這裡見面，談天說地。這天，話題轉向了他們各自的財富，但都不想直接透露自己的財產有多少。於是，亞歷克斯提出一個有趣的挑戰："我們來比較看看誰更富有，但我們可以不必告訴對方具體的數字，你覺得如何？"

鮑勃感到好奇，但也有些疑惑："那我們怎麼比較而不透露具體數字呢？"

亞歷克斯解釋說："這就用到一個叫做零知識證明的技術。它就像是魔術一樣，讓我們可以證明某件事情而不透露任何其他信息。"

"在 1~10 的保險箱中，A，若財富有大於該數字保險箱則在裡面放入自己的記號，反之，則不放。"
"B 則在 1~10 中選擇等同自己財富的保險箱，並將她打開，若有A的記號則B <= A，反之，B > A"

鮑勃笑了笑："這就像是我們在玩一個秘密遊戲，我贏了你也不知道我贏了多少，你贏了我也只知道你贏了而已。"

亞歷克斯點頭："正是這樣，這個方法不僅讓我們的比較變得公平，還保護了我們的隱私。"

兩位老友於是開始設置他們的零知識證明比較，一邊操作，一邊享受這場智力與技術的對決。最終，他們確定了誰的財富更豐厚，卻沒有透露任何一方的具體數字。這不僅增強了他們之間的信任，也讓他們對零知識證明的神奇之處感到驚喜和敬畏。

這個故事不僅讓鮑勃對零知識證明有了深刻的理解，也讓他深刻感受到，在這個信息洩露的時代，如何巧妙地保護個人隱私。

# 零知識證明
## 範例
### 甚麼是零知識證明？
證明者希望證明自己的年齡大於或等於18歲，但不希望透露確切的年齡。
1. **前提**：第三方機構知道證明者的確切年齡，但不會直接向其他人透露。相反，他們提供了一個經過22次哈希處理的年齡哈希代碼，這樣除非進行至少18次 Hash 處理，否則無法反推出確切的年齡。
2. **後續**：證明者只需將前4次 Hash 處理的結果提供給驗證者。驗證者將使用這些信息進行進一步的18次Hash 處理，然後將其與提供的年齡 Hash 結果進行比較。如果結果匹配，證明者成功地證明了自己的年齡大於或等於18歲，而且驗證者沒有獲得任何有關具體年齡的信息。
3. **結果**：不涉及具體的年齡信息傳遞，驗證者只能獲得關於年齡 Hash 代碼的信息，而無法推斷出證明者的確切年齡。

更簡單的例子：我要證明我知道某個人的電話號碼：
1. 我只需要能夠在眾人面前撥通那人的電話就可以證明這一事實，不需要透露那人的真實號碼。
### 三大特性
1. 完整性（Completeness）： 如果證明者的年齡確實大於或等於18歲，則證明者將能夠通過提供相應的哈希數據，使驗證者能夠完成整個證明過程。在這個例子中，證明者提供了必要的前四次哈希處理的結果，這些信息足以讓驗證者完成後續的18次哈希處理並驗證年齡哈希代碼。

2. 正確性（Soundness）： 如果證明者的年齡不符合要求，即小於18歲，則無論提供多少次哈希處理的結果，最終的年齡哈希代碼都不會匹配。這是因為第三方機構提供的年齡哈希代碼是根據真實的年齡生成的，而證明者無法篡改或虛假年齡的哈希代碼。

3. 零知識（Zero-Knowledge）： 在這個例子中，證明者成功地證明了自己的年齡大於或等於18歲，但沒有透露任何關於自己具體年齡的信息。驗證者只能通過證明者提供的哈希數據來驗證年齡哈希代碼，無法得知證明者的確切年齡。因此，證明者成功地達成了證明目標，同時保持了自己的隱私。
## 歷史
### 故事的開始
1. 零知識證明（ZKP）是在 1985 年由 Shafi Goldwasser、Silvio Micali、Chales Rackoff 合著的論文《The knowledge complexity of interactive proof systems》首次提出的數學協議，除了某一要證明的事實之外，不會透露任何其他訊息。驗證者無法獲得生成證明的秘密訊息。

2. 知識複雜度主要關注的是證明者必須擁有多少知識才能成功地欺騙驗證者。換句話說，它研究的是在證明過程中，證明者需要具備多少額外的信息才能讓驗證者相信某個陳述是真實的。如果一個交互證明系統的知識複雜度很低，意味著證明者無需擁有太多額外的信息就能成功地欺騙驗證者。這可能導致安全性問題，因為驗證者無法區分真實的證明和虛假的證明。
3. 在這種系統中，證明者和驗證者會進行多輪的交互，證明者會回答驗證者的問題，從而讓驗證者相信某個聲明的真實性。這種交互過程是概率性的，也就是說，對於一個給定的輸入，證明者可能會有不同的回答，而驗證者則會根據這些回答來決定是否接受證明。
4. **缺點**：驗證者跟證明者會進行多輪交互，就像 TCP 連線，不就代表會耗用很多網路資源，因此交互式零知識證明會導致交互時間過長。

5. **例子**：Schnorr
### 進化
1. **Fiat-Shamir**(Fiat-Shamir Heurisitc/Fiat-Shamir Paradigm)Amos Fiat和Adi Shamir兩人在1986年提出，用來解決上述交互式的缺點進而變成非交互的驗證方式。

2. **例子**：平時我們使用密碼註冊和登錄一個網站的過程可能是這樣的。我們使用用戶名和密碼註冊一個網站，網站後台收到用戶名和密碼之後，使用一個雜湊算法計算密碼的雜湊值，然後將用戶名和雜湊值存入數據庫。下次用戶登錄的時候，後台以同樣的方式計算出雜湊值，對比數據庫中的是否一樣，如果兩者的用戶名和雜湊值都一樣，登錄成功。好一點的後台可能在計算雜湊值的時候，選擇一個數字用作“鹽”，也就是加鹽雜湊。這樣攻擊者拿到加鹽的雜湊值之後，在沒有知道鹽值的情況下是無法通過暴力的方式計算出用戶的密碼的。但是，如果攻擊者知道了鹽值呢？攻擊者就能通過字典的單詞和鹽值計算出雜湊值，對比保存在數據庫中的雜湊值，來試探出用戶的密碼。總之，用戶將自己的密碼發送給後台是不安全的，因為用戶的密碼通過網絡傳播到遠方的伺服器上，會發生什麼洩露密碼的事情的不確定性太大了。所以，最安全的辦法就是用戶不用把登錄密鑰發給後台。

3. **問題**：有沒有一種辦法，讓用戶不用發密碼給後台，用戶也能註冊登入呢？

4. **解法**：

(1). 使用者透過自己的密碼生成一組數據，將這個數據而不是密碼發送給網站後台完成註冊。網站後台將這個數據保存到資料庫中。

(2). 註冊成功之後，使用者想登錄這個網站，這時候，使用者自己生成另一組數據，這個數據跟第一步的數據是不一樣的。然後將這個數據發送給網站後台。

(3). 網站後台通過第一步和第二步的兩個數據，進行一定的計算，就能夠確認現在想登錄的使用者確實是第一步所註冊的使用者。後台認證通過。

5. **結果**：就可以變成非交互式的方式去做驗證，節省網路資源

### 再進化
zk-SNARKs - 待補充

### 可以再補充一些零知識證明的技術(分析優缺點就好)
#### zk-SNARKs（零知識簡短非交互式知識的論證）
* 技術簡介：
zk-SNARKs 是目前最著名的零知識證明技術之一，廣泛用於加密貨幣如Zcash中。這種證明技術允許證明者在無需任何交互的情況下證明他們擁有某個信息，驗證者可以迅速且有效地驗證證明。

* 優點：
非交互性：一旦生成，任何人都可以驗證證明而無需證明者參與。
計算高效：證明的生成和驗證過程相對快速。
隱私保護：提供高度的隱私保護，不透露任何關於原始數據的信息。
* 缺點：
複雜的設置階段：需要一個可信的設置階段來生成公共參數，這個階段若受到妥協，整個系統的安全性可能被破壞。
證明大小和驗證時間：雖然比其他技術更有效率，但在資源受限的設備上仍可能是個挑戰。
#### zk-STARKs（零知識可擴展透明論證的知識）
* 技術簡介：
作為 zk-SNARKs 的一種替代方案，zk-STARKs 提供了無需可信設置的零知識證明，使用量子安全的加密算法。

* 優點：
無需可信設置：不需要可信的第三方來初始化參數，降低了安全風險。
量子計算安全：使用抗量子攻擊的加密技術，為未來的安全威脅做好準備。
可擴展性：對於大量數據的處理更加高效。
* 缺點：
較大的證明大小：相比於 SNARKs，STARKs 的證明大小更大，這可能影響存儲和傳輸效率。
計算需求高：生成證明的過程更加計算密集。
#### Bulletproofs
* 技術簡介：
Bulletproofs 是一種不需要可信設置的零知識證明技術，特別適合於範圍證明，如證明一個數字位於某個範圍內而不透露這個數字。

* 優點：
無需可信設置：與 zk-STARKs 一樣，無需可信第三方參與。
更短的證明：相對於其他技術，如 STARKs，證明的大小更小，更適合大規模應用。
* 缺點：
交互性：與 SNARKs 和 STARKs 的非交互性相比，Bulletproofs 需要多輪交互來完成證明。
計算成本：對計算資源的需求相對較高，尤其是在證明生成階段。
#### Ring Signatures
* 技術簡介：
雖然並非傳統意義上的零知識證明，但環簽名允許用戶在一組人中匿名地簽名消息，證明者證明其身份屬於一個特定的群組而不透露是哪一個。
* 優點：
匿名性：極高的匿名性，適合於需要保護用戶隱私的應用。
無需可信設置：不需要任何可信設置階段。
* 缺點：
有限的應用範圍：主要用於匿名身份驗證和簽名，而非通用的零知識證明。
證明大小和計算需求：相對其他零知識證明技術，環簽名可能需要更多的計算資源和存儲空間。

### 零知識證明範例故事
#### 1. 色彩識別遊戲
**故事**：
Grace 有一個由三種顏色的珠子組成的串珠，並且每種顏色都有一個特定的排列規則，但她不想公開具體的顏色排列。她可以讓 Henry 從串珠中隔著一塊布選擇兩顆珠子，然後問Grace這兩顆珠子的顏色是否相同。Grace 回答後，Henry 可以檢查布下的珠子顏色以驗證Grace的回答，但由於他不能看到整條串珠，因此無法得知整體的顏色排列。

**零知識證明的元素**：
- **完整性**：Grace 知道串珠的顏色排列。
- **正確性**：Grace 能夠正確回答 Henry 關於珠子顏色是否相同的每個問題，這證明了她確實知道整條串珠的顏色排列。Henry 通過檢查珠子的顏色來驗證 Grace 的每個回答，如果 Grace 不知道真正的顏色排列，她就無法一致且正確地回答問題。這確保了證明過程的正確性。
- **零知識**：Henry 不能得知除他所選擇的珠子之外的任何顏色信息。