📜 [專欄新文章] 瞭解神秘的 ZK-STARKs
✍️ Kimi Wu
📥 歡迎投稿： https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium

上一篇關於 zkSNARK扯到太多數學式，導致很難入手，這次介紹 STARK 會盡量減少數學式，以原理的方式跟大家介紹。

STARK 被視為新一代的 SNARK，除了速度較快之外，最重要的是有以下好處1. 不需要可信任的設置（trusted setup），以及
2. 抗量子攻擊

但 STARK 也沒這麼完美，STARK 的證明量(proof size)約 40–50KB，太佔空間，相較於 SNARK 只有288 bytes，明顯大上幾個級距。此外，這篇論文發佈約兩年的時間，就密碼學的領域來說，還需要時間的驗證。

STARK 的 S 除了簡潔（Succinct）也代表了擴展性（Scalable），而T代表了透明性（Transparency），擴展性很好理解，透明性指的是利用了公開透明的算法，可以不需要有可信任的設置來存放秘密參數。
SNARK 跟 STARK 都是基於多項式驗證的零知識技術。差別在於，如何隱藏資訊、如何簡潔地驗證跟如何達到非互動性。

快轉一下 SNARK 是如何運作的。
Alice 有多項式 P(x)、Bob有秘密 s，Alice 不知道 s、Bob 不知道 P(x)的狀況下，Bob 可以驗證P(s)。藉由同態隱藏（Homomorphic Hindings）隱藏Bob的 s → H(s)，藉由 QAP/Pinocchio 達到了簡潔地驗證，然後把 H(s) 放到CRS（Common Reference String），解決了非互動性。細節可以參考之前的文章 。

問題轉換

零知識的第一步，需要先把「問題」轉成可以運算的多項式去做運算。這一小節，只會說明怎麼把問題轉成多項式，至於如何轉換的細節，不會多琢磨。

問題 → 限制條件 → 多項式

在 SNRAK 跟 STARK 都是藉由高維度的多項式來作驗證。也就是若多項式為： x³ + 3x² + 3 = 0，多項式解容易被破解猜出，若多項式為 x^2000000 + x^1999999 + … 則難度會高非常多。

第一步，先把想驗證的問題，轉換成多項式。
這邊以Collatz Conjecture為例子，什麼是Collatz Conjecture呢？（每次都用Fibonacci做為例子有點無聊 XD）
1. 若數字為偶數，則除以2
2. 若數字為奇數，則乘以3再加1 (3n+1)

任何正整數，經由上述兩個規則，最終結果會為 1 。（目前尚未被證明這個猜想一定成立，但也還未找出不成立的數字）

52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

把每個運算過程的結果紀錄起來，這個叫做執行軌跡（Execution Trace），如上述52 -> 26 -> … -> 1。接著我們把執行軌跡轉換成多項式（由執行軌跡轉成多項式不是這裡的重點，這裡不會贅述，細節可以參考 StarkWare的文章 ）如下

https://medium.com/starkware/arithmetization-i-15c046390862

合成多項式

接著就把這四個限制條件的多項式合成為一個，這個最終的多項式就叫做合成多項式（composition polynomial），而這個合成多項式就是後面要拿來驗證的多項式。

就像一開始提的，SNARK跟STARK都是使用高維度多項式，接著，來介紹STARK是藉由哪些方式，達到零知識的交換、透明性(Transparency)跟可擴展性(Scalability)。

修改多項式維度

這一步是為了後面驗證做準備的。在驗證過程使用了一個技巧，將多項式以2的次方一直遞減為常數項（D, D/2, D/4 … 1），大幅減低了驗證的複雜度。因此，需要先將多項式修改為2^n維度

假設上述的每個限制多項式（不是合成多項式喔）為Cj(x)，維度為 Dj，D >= Dj 且 D 等於2^n，為了達到 D 維度，乘上一個維度（D -Dj）的多項式，

所以最終的合成多項式，如下

其中的αj、βj是由驗證者(verifier)所提供，所以最終的多項式是由證明方(prover)跟驗證方所共同組成。

*這小節的重點是將多項式修改成D維度，覺得多項式太煩可忽略

FRI

FRI 的全名是”Fast RS IOPP”（RS = “Reed-Solomon”, IOPP = “Interactive Oracle Proofs of Proximity”）。藉由FRI可以達到簡潔地驗證多項式。在介紹FRI 之前，先來討論要怎麼證明你知道多項式 f(x) 為何？

RS 糾刪碼：

糾刪碼的概念是把原本的資料作延伸，使得部分資料即可以做驗證與可容錯。其方式是將資料組成多項式，藉由驗證多項式來驗證資料是否正確。舉例來說，有d個點可以組成 d-1 維的多項式 y = f(x)，藉由驗證 f(z1) ?= y，來確定 z1是否是正確資料。

回到上面的問題，怎麼證明知道多項式？最直接的方式就是直接帶入點求解。藉由糾刪碼的方式，假設有d+1個點，根據Lagrange插值法，可以得到一個 d 維的多項式 h(x)，如果如果兩個多項式在（某個範圍內）任意 d 點上都相同（ f(z) = h(z), z = z1, z2…zd），即可證明我知道 f(x)。但是我們面對的是高維度的多項式，d 是1、2百萬，這樣的測試太沒效率，且不可行。FRI 解決了這個問題，驗證次數由百萬次變成數十次。

降低複雜度

假設最終的合成多項式為 f(x)，藉由將原本的1元多項式改成2元多項式，以減少多項式的維度。假設 f(x) = 1744 * x^{185423}，加入第二變數 y，使 y = x^{1000}，所以多項式可改寫為 g(x, y) = 1744*x^{423}*y^{185}。藉由這樣的方式，從本來10萬的維度變成1千，藉由這種技巧大幅降低多項式的維度。在 FRI 目前的實做，是將維度對半降低 y = x²（f(x) = g(x, x²)）。

此外，還有另一個技巧，將一個多項式拆成兩個較小的多項式，把偶數次方跟奇數次方拆開，如下：

f(x)= g(x²) + xh(x²)

假如：

f(x) = a0 + a1x + a2x² + a3x³ + a4x⁴ + a5x⁵
g(x²) = a0 + a2x² + a4x⁴, （g(x) = a0 + a2x + a4x²）
h(x²) = a1x + a3x² + a5x⁴, （h(x) = a1 + a3x + a5x² ）

藉由這兩個方法，可以將高維度的多項式拆解，重複地將維度對半再對半，以此類推到常數項。而 FRI 協議在流程上包含兩階段 — 「提交」跟「查詢」。

提交階段：提交階段就如同上述過程，將多項式拆解後，由驗證者提供一亂數，組成新的多項式，再繼續對多項式拆解，一直重複。

f(x) = f0(x) = g0(x²) + x*h0(x²)
==> f1(x) = g0(x) + α0*h0(x), ← α0（驗證者提供）
==> f2(x) = g1(x) + α1*h1(x), ← α1（驗證者提供）
==> . . .

查詢階段：這個階段要驗證證明者所提交的多項式 f0(x), f1(x), f2(x), … 是否正確，這邊運用一個技巧，帶入任意數 z 及 -z（這代表在選域的時候，需滿足 L²= {x²：x ∊ L}，這邊不多提）。所以可以得

f0(z) = g0(z²) + z*h0(z²)
f0(-z) = g0(z²) -z*h0(z²)

藉由兩者相加、相減，及可得g0(z²)、h0(z²)，則可以計算出f1(z²)，再推導出f1(x)，以此類推驗證證明者傳來的多項式。

Interactive Oracle Proofs (IOPs)

藉由FRI（RS糾刪碼、IOPs），將驗證次數由數百萬降至20–30次（log2(d)），達到了簡潔地驗證。不過，我們解決了複雜度，但還有互動性！

* 與SNARK比較 ：SNARK在驗證方面利用了QAP跟Pinocchio協定。

非互動性

藉由 Micali 建構（Micali construction）這個概念來解釋如何達到非互動的驗證。Micali 建構包括兩部分，PCPs（Probabilistically checkable proof）跟雜湊函數。PCPs 這是一個隨機抽樣檢查的證明系統。簡單來說，證明者產出一個大資料量的證明（long proof），經由隨機抽樣來驗證這個大資料量的證明。過程大約是這樣，證明者產出證明𝚿，而驗證者隨機確認 n 個點是否正確。

在STARK，我們希望達到：1.小的證明量，2.非互動。隨機抽樣可以讓達到小的證明量，那互動性呢? 想法很簡單，就是預先抽樣，把原本 PCPs 要做的事先做完，然後產出只有原本證明 𝚿 抽樣出的幾個區塊當作證明。但想也知道，一定不會是由證明者抽樣，因為這樣就可以作假。這裡是使用 Fiat-Shamir Heuristic 來作預先取樣。

首先，先把證明 𝚿組成 merkle tree，接著把 merkle root 做雜湊可得到一亂數 𝛒，而 𝛒 就是取樣的索引值。將利用𝛒取出來的區塊證明、區塊證明的 merkle tree 路徑跟 merkle root, 組一起，即為STARK 證明 𝛑。

到目前，只使用雜湊函數這個密碼學的輕量演算法。而雜湊函數的選擇是這個證明系統唯一的全域參數（大家都需要知道的），不像是 SNARK 有 KCA 使用的(α, β, 𝛾)等全域的秘密參數，再藉由 HH（同態隱藏）隱藏這些資訊來產生 CRS。因為證明的驗證是靠公開的雜湊函數，並不需要預先產生的秘密，因此 STARK 可以達到透明性，也不用可信任的設置。

接著，將FRI中需要互動的部分（驗證者提供 α 變數），使用上述的 PCP + Fiat-Shamir Heuristic， 即可達到非互動性。

* 與SNARK比較： SANRK 的非互動性是將所需的全域參數放到CRS中，因為全域參數是公開的，所以CRS裡的值使用了 HH 做隱藏。

MIMC

大部分證明系統，會使用算數電路來實作，此時，電路的複雜程度就關係到證明產生的速度。 STARK 的雜湊函數選用了電路複雜度較簡單的 MIMC，計算過程如下：

https://vitalik.ca/general/2018/07/21/starks_part_3.html

這樣的計算有另一個特性，就是無法平行運算，但卻又很好驗證，因此也很適合 VDF 的運算。Vitalik有一個使用 MIMIC 作為 VDF 的提案。

ps. 反向運算比正向慢百倍，所以會是反向計算，正向驗證

從上面的解釋，可以理解為什麼 STARK 不需要可信任設置，至於為什麼能抗量子？因為 SNARK 中使用了 HH 來隱藏秘密，而 HH 是依靠橢圓曲線的特性，但橢圓曲線沒有抗量子的特性（也就是可以從公鑰回推私鑰）。而STARK在整個過程中只使用了雜湊函數，而目前還沒有有效的演算法能破解雜湊函數，因此可以抵抗抗量子攻擊。

有錯誤或是不同看法，歡迎指教

參考：
StarkDEX Deep Dive: the STARK Core Engine
STARK 系列文：
STARK Math: The Journey Begins
Arithmetization I
Arithmetization II
Low Degree Testing
A Framework for Efficient STARKs
Vitalik 系列文：
STARKs, Part I: Proofs with Polynomials
STARKs, Part II: Thank Goodness It’s FRI-day
STARKs, Part 3: Into the Weeds
ZK-STARKs — Create Verifiable Trust, even against Quantum Computers
https://ethereum.stackexchange.com/questions/59145/zk-snarks-vs-zk-starks-vs-bulletproofs-updated

Originally published at http://kimiwublog.blogspot.com on November 12, 2019.

瞭解神秘的 ZK-STARKs was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.

👏 歡迎轉載分享鼓掌

📜 [專欄新文章] 隱私、區塊鏈與洋蔥路由
✍️ Juin Chiu
📥 歡迎投稿： https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium

隱私為何重要？區塊鏈是匿名的嗎？洋蔥路由如何改進區塊鏈？

前言

自2008年區塊鏈以比特幣的面貌問世後，它便被視為 Web 3.0，並被期許能夠進一步為人類帶來金融與治理上的大躍進。區塊鏈或許會成為如同全球資訊網一般的基礎建設，如果我們已經開始注重個人於網路上的隱私，那麼我們更應該關心這項全新的技術是否能更好地保護它。

筆者將於本文中闡述隱私的重要性，接著進一步分析區塊鏈是否能夠保護用戶隱私，最後再簡介一個知名的匿名技術 — 洋蔥路由，並列舉幾個其用於改進區塊鏈（特別是以太坊）的相關提案。

特別感謝以太坊研究員 Chih-Cheng Liang 與民間高手敖烏協助校閱並給予回饋。

隱私的重要

網際網路（Internet）無疑是 20 世紀末最偉大的發明，它催生了全新的商業模式，也使得資訊能以位元的形式進行光速傳播，更使人類得以進行前所未有的大規模協作。而自從 1990 年全球資訊網（World Wide Web）的問世以來，網路已和現代文明生活密不可分。經過近 30 年的發展，人類在網路上製造了巨量的資料，這些資料會揭露使用者的隱私。透過一個人的資料，企業或者政府能夠比你自己更了解你。這促使用戶對隱私的愈發重視 — 正如同你不會允許第三者監聽你的電話，你也不希望有第三者監看你的瀏覽器搜尋歷史。

然而，如今的網路是徹底的中心化，中心化也意謂著過大的權力，有種種跡象顯示：網路正在成為政府當局監控人民的工具。例如：中國的淨網衛士[1]、美國的稜鏡計劃[2]等。那麼，政府應該監控人民嗎？其中一派的人認為平日不做虧心事，半夜不怕鬼敲門，這也就是常見的無所隱瞞論[3]：

我不在乎隱私權，因為我沒什麼好隱瞞的。

不過持有這類論點的人通常會被下面的說法反駁：

既然沒什麼好隱瞞的，那請把你的 Email 帳號密碼給我，讓我揭露其中我認為有趣的部分。

大多數正常人應該都不會接受這個提議。

隱私應當與言論自由一樣，是公民的基本權利。事實上，隱私是一個既廣且深的題目，它涉及了心理學、社會學、倫理學、人類學、資訊科學、密碼學等領域，這裡[4]有更多關於關於隱私的討論以及網路隱私工具的整理。

隱私與區塊鏈

有了網際網路後，接下來人類或許可以透過區塊鏈來建構出一個免除人性且完全仰賴自然法則（數學）運行的去中心化系統。在中心化世界中，我們需要免於政府監控的隱私；在去中心化世界中，我們仍然需要隱私以享有真正的平等。

正如同本文的前言所述：區塊鏈也許會成為如同全球資訊網一般的基礎建設，如果我們已經開始注重網路隱私，那麼我們更應該關心區塊鏈是否能更好地保護它。

隱私與匿名

Privacy vs Anonymity [5]

當我們論及隱私時，我們通常是指廣義的隱私：別人不知道你是誰，也不知道你在做什麼。事實上，隱私包含兩個概念：狹義的隱私（Privacy）與匿名（Anonymity）。狹義的隱私就是：別人知道你是誰，但不知道你在做什麼；匿名則是：別人知道你在做什麼，但不知道你是誰。

隱私與匿名對於隱私權來說都很重要，也可以透過不同的方法達成，接下來本文將聚焦於匿名的討論。另外，筆者在接下來的文章中所提及的隱私，指的皆是狹義的隱私。

網路的匿名

以當今的網路架構（TCP/IP 協定組）來說，匿名就是請求端（Requester）向響應端（Responder）請求資源時藏匿其本身的 IP 位址 — 響應端知道請求端在做什麼（索取的資源），但不知道是誰（IP 位置）在做。

IP 位置會揭露個人資訊。在台灣，只需透過 TWNIC 資料庫就可向台灣的網路服務供應商（Internet Service Provider, ISP），例如中華電信，取得某 IP 的註冊者身份及姓名/電話/地址之類的個資。

ISP 是網路基礎建設的部署者與營運者，理論上它能知道關於你在使用網路的所有資訊，只是這些資訊被法律保護起來，並透過公權力保證：政府只在必要時能夠取得這些資訊。萬一政府本身就是資訊的監控者呢？因此，我們需要有在 ISP 能窺知一切的情形下仍能維持匿名的方法。

區塊鏈能保護隱私、維持匿名嗎？

區塊鏈除了其本身運作的上層應用協定之外，還包含了下層網路協定。因此，這個問題可以分為應用層與網路層兩個部分來看 。

應用層

應用層負責實作狀態機複製（State Machine Replication），每個節點收到由共識背書的交易後，便可將交易內容作為轉換函數（Transition Function）於本機執行狀態轉換（State Transition）。

區塊鏈上的交易內容與狀態是應當被保護的隱私，一個保護隱私的直覺是：將所有的交易（Transaction）與狀態（State）加密。然而實際上，幾乎目前所有的主流區塊鏈，包含以太坊，其鏈上的交易及狀態皆為未加密的明文，用戶不僅可以查詢任一地址的交易歷史，還能知道任一地址呼叫某智能合約的次數與參數。也就是說，當今主流區塊鏈並未保護隱私。

雖然區塊鏈上的交易使用假名（Pseudonym），即地址（Address），但由於所有交易及狀態皆為明文，因此任何人都可以對所有假名進行分析並建構出用戶輪廓（User Profile）。更有研究[6]指出有些方法可以解析出假名與 IP 的映射關係（詳見下個段落），一旦 IP 與假名產生關聯，則用戶的每個行為都如同攤在陽光下一般赤裸。

區塊鏈的隱私問題很早便引起研究員的重視，因此目前已有諸多提供隱私保護的區塊鏈被提出，例如運用零知識證明（Zero-knowledge Proof）的 Zcash、運用環簽章（Ring Signature）的 Monero、 運用同態加密（Homomorphic Encryption）的 MimbleWimble 等等。區塊鏈隱私是一個大量涉及密碼學的艱澀主題，本文礙於篇幅不再深入探討，想深入鑽研的讀者不妨造訪台北以太坊社群專欄，其中有若干優質文章討論此一主題。

網路層

節點於應用層產生的共識訊息或交易訊息需透過網路層廣播（Broadcast）到其他節點。由於當今的主流區塊鏈節點皆未採取使網路維持匿名的技術，例如代理（Proxy）、虛擬私人網路（Virtual Private Network, VPN）或下文即將介紹的洋蔥路由（Onion Routing），因此區塊鏈無法使用戶維持匿名 — 因為對收到訊息的節點來說，它既知道廣播節點在做什麼（收到的訊息），也知道廣播節點是誰（訊息的 IP 位置）。

一個常見的問題是：使用假名難道不是匿名嗎？若能找到該假名與特定 IP 的映射關係的話就不是。一般來說，要找到與某假名對應的 IP 相當困難，幾可說是大海撈針，但是至少在下列兩種情況下可以找到對應關係：1. 該假名的用戶自願揭露真實 IP，例如在社群網站公開以太坊地址；2. 區塊鏈網路遭受去匿名化攻擊（Deanonymization Attack）[6]。

洩漏假名與 IP 的關聯會有什麼問題？ 除了該 IP 的真實身份可能被揭露外，該區塊鏈節點亦可能遭受流量分析（Traffic Analysis）、服務阻斷（Denial of Service）或者審查（Censorship），可以說是有百害而無一利。

區塊鏈如何維持匿名？

其實上文已給出了能讓區塊鏈維持匿名的線索：現有匿名技術的應用。我們先來進一步理解區塊鏈網路層與深入探討網際網路協定的運作原理。

區塊鏈網路層的運作原理

P2P Overlay Network [7]

區塊鏈是一個對等網路（Peer-to-peer, P2P），而對等網路是一種覆蓋網路（Overlay Network），需建構於實體網路（Physical Network）之上。

覆蓋網路有兩種常見的通訊模式：一種是基於中繼的（Relay-based）通訊，在此通訊模式下的訊息皆有明確的接收端，因而節點會將不屬於自己的訊息中繼（Relay）給下一個可能是接收端的節點，分散式雜湊表（Distributed Hash Table, DHT）就是一種基於中繼的對等網路；另一種是基於廣播的（Broadcast-based）通訊，在此通訊模式下的訊息會被廣播給所有節點，節點會接收所有訊息，並且再度廣播至其他節點，直到網路中所有節點都收到該訊息，區塊鏈網路層就是一種基於廣播的對等網路。

覆蓋網路旨在將實體網路的通訊模式抽象化並於其上組成另一個拓墣（Topology）與路由機制（Routing Mechanism）。然而實際上，實體網路的通訊仍需遵循 TCP/IP 協定組的規範。那麼，實體網路又是如何運作的呢？

網際網路的運作原理

OSI Model vs TCP/IP Model

實體網路即是網際網路，它的發明可以追朔至 Robert Kahn 和 Vinton Cerf 於1974 年共同發表的原型[12]，該原型經過數年的迭代後演變成我們當今使用的 TCP/IP 協定組[8]。全球資訊網（WWW）的發明更進一步驅使各國的 ISP 建立基於 TCP/IP 協定組的網路基礎建設。網際網路在多個國家經過近 30 年的部署後逐漸發展成今日的規模，成為邏輯上全球最巨大的單一網路。

1984 年，國際標準化組織（ISO）也發表了 OSI 概念模型[9]，雖然較 TCP/IP 協定組晚了 10 年，但是 OSI 模型為日後可能出現的新協定提供了良好的理論框架，並且與 TCP/IP 協定組四層協定之間有映射關係，能夠很好地描述既存的 TCP/IP 協定組。

TCP/IP 協定組的各層各有不同的協定，且各層之間的運作細節是抽象的，究竟這樣一個龐大複雜的系統是如何運作的呢？

Packet Traveling [10][11]

事實上，封包的傳送正如同寄送包裹。例如筆者從台北寄一箱書到舊金山，假設每個包裹只能放若干本書，這箱書將分成多個包裹寄送，每個包裹需註明寄件地址、收件地址、收件者。寄送流程從郵局開始，一路經過台北物流中心 → 北台灣物流中心 → 基隆港 → 洛杉磯港 → 北加州物流中心 → 舊金山物流中心 → 收件者住處，最後由收件者收取。

這如同從 IP 位於台北的設備連上 IP 位於舊金山的網站，資料將被切分成多個固定大小的封包（Packet）之後個別帶上請求端 IP、響應端 IP 及其他必要資訊，接著便從最近的路由器（Router）出發，一路送至位於舊金山的伺服器（Server）。

每個包裹上的收件地址也如同 IP 位置，是全球唯一的位置識別。包裹的收件地址中除了包含收件者的所在城市、街道，還包含了門號，每個門號後都住著不同的收件者。門號正如同封包中後綴於 IP 的連接埠（Port），而住在不同門號的收件者也如同使用不同連接埠的應用程式（Application），分別在等待屬於他們的包裹。實際上，特定的連接埠會被分配給特定的應用程式，例如 Email 使用連接埠 25、HTTPS 使用連接埠 443 等等。

雖然包裹的最終目的地是收件地址，但包裹在運送途中也會有數個短程目的地 — 也就是各地的物流中心。包裹在各個物流中心之間移動，例如從北部物流中心到基隆港，再從基隆港到洛杉磯港，雖然其短程目的地會不斷改變，但其最終目的地會保持不變。

封包的最終目的地稱為端點（End），短程目的地稱為轉跳（Hop） — 也就是路由器（Router）。路由器能將封包從一個網段送至另一個網段，直到封包抵達其端點 IP 所在的網段為止。封包使用兩種定址方法：以 IP 表示端點的位置，而以 MAC 表示路由器的位置。這種從轉跳至轉跳（From Hop to Hop）的通訊是屬於 TCP/IP 協定組第一層：網路存取層（Network Access Layer）的協定。

那麼要如何決定包裹的下一個短程目的地呢？理論上，每個物流中心皆需選擇與最終目的地物理距離最短的物流中心作為下一個短期目的地。例如對寄到舊金山的包裹來說，位於基隆港的包裹下一站應該是洛杉磯港，而不是上海港。

封包則使用路由器中的路由表（Routing Table）來決定下一個轉跳位置，有數種不同的路由協定，例如 RIP / IGRP 等，可以進行路由表的更新。從端點到端點（From End to End）的通訊正是屬於 TCP/IP 協定組第二層：網際層（Internet Layer）的協定。

若一箱書需要分多次寄送，則可以採取不同的寄送策略。至於選擇何種寄送策略，則端看包裹內容物的屬性：

求穩定的策略：每個包裹都會有個序號，寄包裹前要先寫一封信通知收件者，收件者於收到信後需回信確認，寄件者收到確認信後“再”寫一次信告訴收件者「我收到了你的確認」，然後才能寄出包裹。收件者收到包裹後也需回確認信給寄件者，如果寄件者沒收到某序號包裹的回信，則會重寄該包裹。

求效率的策略：連續寄出所有的包裹，收件者不需回信確認。

橫跨多個封包的通訊是屬於 TCP/IP 協定組第三層：傳輸層（Transport Layer）的協定。這兩種策略也對應著傳輸層的兩個主要協定：TCP 與 UDP。TCP 注重穩定，它要求端點於傳送封包前必須先進行三向交握（Three-way Handshake），也就是確認彼此的確認，以建立穩固的連線，且端點在接收封包後也會回傳確認訊息，以確保沒有任何一個封包被遺失；反之，UDP 注重效率，它不要求端點在通訊前進行繁瑣的確認，而是直接傳送封包。

包裹本身亦可以裝載任何內容：這箱書可以是一套金庸全集，也可以是一年份的交換日記；同理，封包內的資料也可以是來自任何上層協定的內容，例如 HTTPS / SMTP / SSH / FTP 等等。這些上層協定都被歸類為 TCP/IP 協定組第四層：應用層（Application Layer）的協定。

維持匿名的技術

區塊鏈仰賴於實體網路傳送訊息，欲使區塊鏈網路層維持匿名，則需使實體網路維持匿名。那麼實體網路如何匿名呢？ 若以寄包裹的例子來看，維持匿名，也就是不要讓收件者知道寄件地址。

一個直覺的思路是：先將包裹寄給某個中介（Intermediary），再由中介寄給收件者。如此收件者看到的寄件地址將會是中介的地址，而非原寄件者的地址 — 這也就是代理（Proxy）以及 VPN 等匿名技術所採取的作法。

不過這個作法的風險在於：寄件者必須選擇一個守口如瓶、值得信賴的中介。由於中介同時知道寄件地址與收件地址，倘若中介將寄件地址告知收件人，則寄件者的匿名性蕩然無存。

有沒有辦法可以避免使單一中介毀壞匿名性呢？一個中介不夠，那用兩個、三個、甚至多個呢？這便是洋蔥路由的基本思路。由於沒有任何一個中介同時知道寄件地址與收件地址，因此想破壞寄件者匿名性將變得更困難。

洋蔥路由與 Tor

洋蔥路由（Onion Routing）最初是為了保護美國政府情報通訊而開發的協定，後來卻因為其能幫助平民抵抗政府監控而變得世界聞名。

1997 年，Michael G. Reed、Paul F. Syverson 和 David M. Goldschlag 於美國海軍研究實驗室首先發明了洋蔥路由[13]，而 Roger Dingledine 和 Nick Mathewson 於美國國防高等研究計劃署（DARPA）緊接著開始著手開發 Tor，第一版 Tor 於 2003 年釋出[14]。2004 年，美國海軍研究實驗室以自由軟體授權條款開放了 Tor 原始碼。此後，Tor 開始接受電子前哨基金會（Electronic Frontier Foundation）的資助；2006年，非營利組織「Tor 專案小組」（The Tor Project）成立，負責維護 Tor 直至今日。

Tor [15]是洋蔥路由的實作，它除了改進原始設計中的缺陷，例如線路（Circuit）的建立機制，也加入若干原始設計中沒有的部分，例如目錄伺服器（Directory Server）與洋蔥服務（Onion Service），使系統更強健且具有更高的匿名性。

Tor 自 2004 年上線至今已有超過 7000 個由志願者部署的節點，已然是一個強大的匿名工具。然而這也使其成為雙面刃：一方面它可以幫助吹哨者揭露不法、對抗監控；另一方面它也助長了販毒、走私等犯罪活動。但不論如何，其技術本身的精巧，才是本文所關注的重點。

Tor 的運作原理

Tor Overview [16]

Tor 是基於中繼的（Relay-based）覆蓋網路。Tor 的基本思路是：利用多個節點轉送封包，並且透過密碼學保證每個節點僅有局部資訊，沒有全局資訊，例如：每個節點皆無法同時得知請求端與響應端的 IP，也無法解析線路的完整組成。

Tor 節點也稱為洋蔥路由器（Onion Router），封包皆需透過由節點組成的線路（Circuit）傳送。要注意的是，Tor 線路僅是覆蓋網路中的路徑，並非實體網路的線路。每條線路皆由 3 個節點組成，請求端首先會與 3 個節點建立線路並分別與每個節點交換線路密鑰（Circuit Key）。

請求端會使用其擁有的 3 組線路密鑰對每個送出的封包進行 3 層加密，且最內層密文需用出口節點的密鑰、最外層密文需用入口節點的密鑰，如此才能確保線路上的節點都只能解開封包中屬於該節點的密文。被加密後的封包被稱為洋蔥，因其如洋蔥般可以被一層一層剝開，這就是洋蔥路由這個名稱的由來。

封包經過線路抵達出口節點後，便會由出口節點送往真正的響應端。同樣的線路也會被用於由響應端回傳的封包，只是這一次節點會將每個送來的封包加密後再回傳給上一個節點，如此請求端收到的封包就會仍是一顆多層加密的洋蔥。

那麼，請求端該選擇哪些節點來組成線路呢？Tor 引入了目錄伺服器（Directory Server）此一設計。目錄伺服器會列出 Tor 網路中所有可用的節點[17]，請求端可以透過目錄伺服器選擇可用的洋蔥路由器以建立線路。目前 Tor 網路中有 9 個分別由不同組織維護的目錄，中心化的程度相當高，這也成為 Tor 安全上的隱憂。

Tor 線路的建立機制

Tor Circuit Construction [18]

Tor 是如何建立線路的呢？如上圖所示，Tor 運用伸縮（Telescoping）的策略來建立線路，從第一個節點開始，逐次推進到第三個節點。首先，請求端與第一個節點進行交握（Handshake）並使用橢圓曲線迪菲 — 赫爾曼密鑰交換（Elliptic Curve Diffie–Hellman key Exchange, ECDH）協定來進行線路密鑰的交換。

為了維持匿名，請求端接著再透過第一個節點向第二個節點交握。與第二個節點交換密鑰後，請求端再透過第一、二個節點向第三個節點交握與交換密鑰，如此慢慢地延伸線路直至其完全建立。線路建立後，請求端便能透過線路與響應端進行 TCP 連線，若順利連接，便可以開始透過線路傳送封包。

洋蔥服務

Clearnet, Deepweb and Darknet [21]

洋蔥服務（Onion Service）/ 隱藏服務（Hidden Service）是暗網（Darknet）的一部分，是一種必須使用特殊軟體，例如 Tor，才能造訪的服務；與暗網相對的是明網（Clearnet），表示可以被搜尋引擎索引的各種服務；深網（Deep Web）則是指未被索引的服務，這些服務不需要特殊軟體也能造訪，與暗網不同。

當透過 Tor 使用洋蔥服務時，請求端與響應端都將不會知道彼此的 IP，只有被響應端選定的節點：介紹點（Introduction Point）會引領請求端至另一個節點：會面點（Rendezvous Point），兩端再分別與會面點建立線路以進行通訊。也就是說，請求端的封包必須經過 6 個節點的轉送才能送往響應端，而所有的資料也會採取端對端加密（End-to-end Encryption），安全強度非常高。

洋蔥服務及暗網是一個令人興奮的主題，礙於篇幅，筆者將另撰文闡述。

混合網路、大蒜路由與洋蔥路由

這裡再接著介紹兩個與洋蔥路由系出同源的匿名技術：混合網路與大蒜路由。

Mix Network Overview [22]

混合網路（Mix Network）早在 1981 年就由 David Chaum 發明出來了[23]，可以說是匿名技術的始祖。

洋蔥路由的安全性奠基於「攻擊者無法獲得全局資訊」的假設[24]，然而一旦有攻擊者具有監控多個 ISP 流量的能力，則攻擊者仍然可以獲知線路的組成，並對其進行流量分析；混合網路則不僅會混合線路節點，還會混合來自不同節點的訊息，就算攻擊者可以監控全球 ISP 的流量，混合網路也能保證維持匿名性。

然而高安全性的代價就是高延遲（Latency），這導致混合網路無法被大規模應用，或許洋蔥路由的設計是一種為了實現低延遲的妥協。

Garlic Routing Overview [25]

混合網路啟發了洋蔥路由，洋蔥路由也啟發了大蒜路由。2003年上線的 I2P（Invisible Internet Project）便是基於大蒜路由（Garlic Routing）的開源軟體，可以視為是去中心化版的 Tor。幾乎所有大蒜路由中的組件，在洋蔥路由中都有對應的概念：例如大蒜路由的隧道（Tunnel）即是洋蔥路由的線路；I2P 的網路資料庫（NetDB）即是 Tor 的目錄；I2P中的匿名服務（Eepsite）即是 Tor 的洋蔥服務。

不過，大蒜路由也有其創新之處：它允許多個封包共用隧道以節省建立隧道的成本，且其使用的網路資料庫實際上是一個分散式雜湊表（DHT），這使 I2P 的運作徹底去中心化。若想進一步理解 DHT 的運作原理，可以參考筆者之前所撰寫的文章：

連Ethereum都在用！用一個例子徹底理解DHT

I2P 最大的詬病就是連線速度太慢，一個缺乏激勵的去中心化網路恐怕很難吸引足夠的節點願意持續貢獻頻寬與電費。

區塊鏈與洋蔥路由

那麼，基於實體網路的區塊鏈能不能使用洋蔥路由或大蒜路由/混合網路/其他技術，以維持節點的匿名？答案是肯定的。事實上，目前已經出現數個專案與提案：

全新的專案

Dusk：實作大蒜路由的區塊鏈[32]，不過官方已宣布因其影響網路效能而暫停開發此功能。

cMix：透過預先計算（Precomputation）以實現低延遲的混合網路[33]，是混合網路發明者 David Chaum 近期的研究，值得期待。

Loki：結合 Monero 與 Tor/I2P 的區塊鏈 [34]，並使用代幣激勵節點貢獻頻寬與電力，由其白皮書可以看出發明者對於匿名技術的熱愛與信仰。

於主流區塊鏈的提案

比特幣：全世界第一條區塊鏈，將於其網路使用一個不同於洋蔥路由的匿名技術：Dandelion++[30][31]，該匿名技術因其訊息傳播路徑的形狀類似浦公英而得其名。

閃電網路（Lightning Network）：知名的比特幣第二層方案，將於其網路內實作洋蔥路由[27]。

Monero：使用環簽章保護用戶隱私的區塊鏈，將於其網路內實作大蒜路由，已開發出 Kovri[28] 並成為 I2P 官方認可的客戶端之一[29]。

於以太坊的提案

2018 年 12 月，Mustafa Al-Bassam 於以太坊官方研究論壇提議利用洋蔥路由改進輕節點之資料可得性（Light Client Data Availability）[36]。若讀者想了解更多關於以太坊輕節點的研究，可以參考台北以太坊社群專欄的這篇文章。資料可得性是輕節點實現的關鍵，而這之中更關鍵的是：如何向第三方證明全節點的資料可得性？由於這個提案巧妙地運用了洋蔥路由的特性，因此在今年 7 月在另一則討論中，Vitalik 亦強烈建議應儘速使洋蔥路由成為以太坊的標準[35]。

在這個提案中，輕節點需建立洋蔥路由線路，然而線路節點並非由目錄中挑選，而是由前一個節點的可驗證隨機函數（Verifiable Random Function, VRF）決定。例如線路中的第二個節點需由第一個節點的 VRF 決定。線路建立後，出口節點便可以接著向全節點請求特定的可驗證資料。由於輕節點在過程中維持匿名，因此可以防止全節點對輕節點的審查（Censoring）。取得可驗證資料後，其便與 VRF 證明沿著原線路傳回輕節點，輕節點再將可驗證資料與 VRF 證明提交至合約由第三方驗證。若第三方驗證正確，則資料可得性得證。

結語

隱私與匿名是自由的最後一道防線，我們應該盡可能地捍衛它，不論是透過本文介紹的匿名技術或者其他方式。然而，一個能保護隱私與維持匿名的區塊鏈是否能實現真正的去中心化？這是一個值得深思的問題。

本文也是筆者研究區塊鏈至今跨度最廣的一篇文章，希望讀者能如我一樣享受這段令人驚奇又興奮的探索旅程。

參考資料

[1] Jingwang Weishi, Wikipedia

[2] PRISM, Wikipedia

[3] privacytools.io

[4] Nothing-to-hide Argument, Wikipedia

[5] Anonymity vs Privacy vs Security

[6] Deanonymisation of Clients in Bitcoin P2P Network, Alex Biryukov, Dmitry Khovratovich, Ivan Pustogarov, 2014

[7] Example: P2P system topology

[8] Internet protocol suite, Wikipedia

[9] OSI model, Wikipedia

[10] Packet Traveling: OSI Model

[11] Packet Traveling — How Packets Move Through a Network

[12] A Protocol for Packet Network Intercommunication, VINTON G. CERF, ROBERT E. KAHN, 1974

[13] Anonymous Connections and Onion Routing, Michael G. Reed, Paul F. Syverson, and David M. Goldschlag, 1998

[14] Tor: The Second-Generation Onion Router, Roger Dingledine, Nick Mathewson, Paul Syverson, 2004

[15] Tor, Wikipedia

[16] What actually is the Darknet?

[17] Tor Network Status

[18] Inside Job: Applying Traffic Analysis to Measure Tor from Within, Rob Jansen, Marc Juarez, Rafa Galvez, Tariq Elahi, Claudia Diaz, 2018

[19] How Does Tor Really Work? The Definitive Visual Guide (2019)

[20] Tor Circuit Construction via Telescoping

[21] The DarkNet and its role in online piracy

[22] Mix network, Wikipedia

[23] Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms, David Chaum, 1981

[24] The differences between onion routing and mix networks

[25] Monitoring the I2P network, Juan Pablo Timpanaro, Isabelle Chrisment, Olivier Festor, 2011

[26] I2P Data Communication System, Bassam Zantout, Ramzi A. Haraty, 2002

[27] BOLT #4: Onion Routing Protocol

[28] Kovri

[29] Alternative I2P clients

[30] Bitcoin BIP-0156

[31] Dandelion++: Lightweight Cryptocurrency Networking with Formal Anonymity Guarantees, Giulia Fanti, Shaileshh Bojja Venkatakrishnan, Surya Bakshi, Bradley Denby, Shruti Bhargava, Andrew Miller, Pramod Viswanath, 2018

[32] The Dusk Network Whitepaper, Toghrul Maharramov, Dmitry Khovratovich, Emanuele Francioni, Fulvio Venturelli, 2019

[33] cMix: Mixing with Minimal Real-Time Asymmetric Cryptographic Operations, David Chaum, Debajyoti Das, Farid Javani, Aniket Kate, Anna Krasnova, Joeri De Ruiter, Alan T. Sherman, 2017

[34] Loki: Private transactions, decentralised communication, Kee Jefferys, Simon Harman, Johnathan Ross, Paul McLean, 2018

[35] Open Research Questions For Phases 0 to 2

[36] Towards on-chain non-interactive data availability proofs

隱私、區塊鏈與洋蔥路由 was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.

👏 歡迎轉載分享鼓掌