如何利用聚類破壞 CoinJoin 匿名性
匿名是研究隱私的最終目標，思考以下幾點很有用：de-匿名化就像一場遊戲。
我們設想一個對手擁有一些信息，它試圖從一組候選者中正確猜測出系統中某個事件的責任人。 為了防止對手獲勝，我們需要讓它不斷猜測，這意味著要么限制它獲取信息的渠道，要么利用隨機性來增加它獲勝所需的信息量。
許多讀者可能都熟悉“猜猜我是誰？”遊戲。 這款遊戲可以理解為更通用的遊戲“猜猜我是誰？”的兩個實例的回合製組合。 在“二十個問題”遊戲中，玩家需要從給定集合中秘密選擇一個元素，而對手則通過向玩家提出最多 20 個是非問題來嘗試猜出該元素。 在“猜猜我是誰？”遊戲中，雙方輪流對戰，最先猜對的一方獲勝。 “猜猜我是誰？”遊戲中的元素集合是固定的，由 24 個卡通人物組成，每個人物都有各自的顯著特徵，例如髮色或髮型。 每個人物都有一個獨特的名稱，可以明確地識別他們。
是或否問題的答案可以表示為——或者二十位二進制數可以表示 0 到 1,048,575（即 2²⁰-1）範圍內的任何整數。 如果一個集合可以完全排序，則集合中的每個元素都可以通過其在排序中的編號位置進行索引，從而唯一地標識它。 因此，20 位可以唯一地尋址一百萬個元素中的一個。
雖然僅使用 20 個是非題的答案就能唯一識別集合中元素的最大數量是 2²⁰，但在現實世界中，20 個答案通常包含的信息量小於這個數字。 對於大多數集合和問題組合而言，情況幾乎肯定不會完美地排列，而且並非每個問題都能獨立地將候選元素一分為二。 有些問題的答案可能存在偏差；有些問題的答案可能與其他問題的答案相關。
假設你不再問“你的角色戴眼鏡嗎？”這樣的問題，而是問“按字母順序，你的角色的名字是否出現在 [剩餘角色名字的中位數] 之前？”。 這是一個 ，它將最大限度地提高每個問題的答案的信息量：在每一步中，中位數名字都會分割剩餘角色的集合，而這個問題會消除兩半中的一個。 反復將剩餘的候選者減半將以“是”或“否”答案所能達到的最快速度縮小搜索範圍；只需要對數級的步驟，這比線性掃描（即逐個檢查：“是愛麗絲嗎？不是嗎？鮑勃呢？……”）要快得多。
請記住，如果你是為了贏而玩遊戲，那麼遊戲的目的並非從對手那裡獲取最多的信息，而是成為第一個猜對的人。 事實證明，最大化每個答案的信息量才是關鍵——至少在遊戲公平進行的情況下是如此。 同樣，在使用遊戲來研究隱私時，必須假設對手根據其偏好是理性的；由於對手是為了贏而玩遊戲，因此很容易意外地優化出一個略顯錯誤的結果。
最後，假設玩家不再被認為是誠實的。 顯然，作弊者可以不被發現；與其一開始就選擇集合中的一個元素，然後誠實地回答每個問題，不如始終給出一個能留下最多候選答案的答案。 因此，自適應選擇的答案可以最大限度地減少對手獲取有用信息以贏得比賽的速度。 在這種情況下，最優策略不再與玩家誠實時相同。 在這種情況下，對手的最佳應對策略是堅持使用二分搜索，這會限制自適應策略的優勢。
自適應的“猜猜我是誰？”遊戲相當無聊，就像井字棋一樣，如果你專心致志，它總是會以平局結束。 準確地說，正如我們將在下一節中看到的那樣，你可以從你最具對抗性的對手那裡提取4.58比特的信息，而遊戲規則可以用來迫使對手接受這些信息。 這意味著這類游戲中的答案記錄應該始終由均勻隨機的比特組成，因為任何其他比特都會給對手帶來優勢。 遺憾的是，使用這種自適應性或附加隨機性的隱私保護機制難以構建和理解，因此實際的隱私軟件通常比這些玩具示例更難分析。
測量匿名性：香農熵
“猜猜我是誰？”中答案的熵——也稱為香農熵——量化了學習結果的意外程度。 例如，如果你已經發現對手的角色是禿頭，那麼當你得知他們沒有黑頭髮時，你就不會感到驚訝；這個答案不包含任何額外的信息。 這並不令人驚訝，因為在被告知之前，你可以推斷出擁有黑頭髮的概率為零。
假設從候選集合中剩下兩個選項；這基本上就是拋硬幣，兩個選項中的任何一個都應該有同等的可能性，因此也同樣令人驚訝。 得知是選項 A 就告訴你它不是選項 B——等價地，得知它是不是 B 告訴你它一定是 A ——因此只需要一個是或否的問題、一點信息，就可以消除所有不確定性。
該值可以根據概率分佈計算出來，在這個二進制例子中，概率分佈為 p=1/2。
首先，計算每種情況的概率的以 2 為底的對數的否定，或者等效地先反轉概率並跳過否定：
首先，計算每種情況的概率的以 2 為底的對數的否定，或者等效地先反轉概率並跳過否定：
在這兩種情況下：
然後，將這些值乘以其對應的概率（某種加權平均值）進行縮放，最終得到兩種情況下的貢獻均為½位。 這些項之和（在本例中為1）即為分佈的香農熵。
這也適用於兩個以上的結果。 如果你一開始就問：“是[一個隨機角色的名字]嗎？”你很可能只會知道
如果答案是“否”，則提供一些信息。
那時log₂（23）≈4.52位量化了你對剩餘 23 種等概率概率的不確定性。 另一方面，如果你運氣好猜對了，你就能知道完整的log₂（24）≈4.58信息位，因為不會留下任何不確定性。
只需不到 5 位就能縮小到 24 個字符中的一個。 10 位可以識別 1,024 個字符中的一個；20 位則可以識別大約百萬分之一的字符。
足夠通用，可以量化非均勻分佈。 並非所有名字都同樣流行，所以一個有趣的問題是，““？ 鏈接的帖子估計美國姓氏的編碼大約需要15位。 根據文獻，美國名字大約包含10-11位。 這些估計意味著每個全名的上限為26位，但請記住，像John Smith這樣的常見名字所包含的信息量要比不常見名字少。 （唯一地表示整個美國人口的信息量需要29位。）
截至撰寫本文時，世界人口正緩慢但穩步地接近85億，即2³³人。 33並不是一個很大的數字：生日包含多少位？ 僅僅是年齡？ 某人的？ IP地址？ 瀏覽器？ 郵遞區號? 他們的詞彙量，還是標點符號的習慣？
這些問題很棘手。 與這些遊戲和現代密碼學不同，這些遊戲中的秘密是隨機的，而且往往是短暫的，而我們無法隨機化、過期或輪換我們現實生活中的身份識別屬性。
此外，這些個人身份信息在我們的生活中經常洩露，有時是出於必要，有時是無意和不必要。 我們常常不得不相信與我們互動的人不會洩露這些信息，無論是與第三方共享還是意外洩露。 這或許與我們必須將生命託付給別人（例如醫生或職業司機和飛行員）並無二致。 然而，就我們個人數據而言，信任的必要性顯然是不可比擬的。
熵主義視角下的匿名性
允許用戶例如，如果您觀察到一個從 Tor 出口節點到您服務器的連接，那麼據您所知，它可能是由數千個 Tor 用戶之一建立的。 通俗地說，假設去匿名化對手觀察到了某個事件（可能是通過攔截網絡中兩個節點之間傳輸的消息），那麼特定用戶的匿名集就是指可能將該事件歸因於的潛在用戶集合。
如果這個假設的系統是完全匿名的，那麼除了接收者之外，任何用戶都有同等的可能性發送了該消息。
兩篇頗具影響力的論文同時發表，提出用匿名集的熵來衡量匿名性：一篇由 Claudia Díaz、Stefaan Seys、Joris Claessens 和 Bart Preneel 撰寫的《匿名集熵》，另一篇由 Andrei Serjantov 和 George Danezis 撰寫的《匿名集熵》。 這兩篇論文從攻擊者能夠從匿名集中準確猜出用戶的概率不及隨機概率的假設，推廣到能夠考慮該匿名集上非均勻概率分佈的模型。 兩篇論文都提出用熵的比特數來量化匿名集的大小。
當匿名集完全對稱時，只有均勻分佈才有意義，因此將匿名集大小轉換為比特數只需計算 log₂(n)，其中 n 是集合的大小。 例如，集合中 1024 個等概率元素的分佈熵為 10 比特。
當分佈不均勻時，分佈的熵會降低。 例如，如果硬幣正面或反面都有可能，但正面的概率為四分之一，反面的概率為四分之三，則該分佈的總熵只有
位而不是完整的位。 這量化了概率分佈中所表示的不確定性；拋擲這枚彎曲硬幣的結果比拋擲一枚公平硬幣的結果不確定性較小。
香農熵是整體的一個特例。 它表徵了一條消息（或者更廣義地說，是或否答案）的平均信息量，該信息量是根據可能消息的概率分佈得出的。 更保守的估計方法可能是只考慮概率最高的元素，而不是計算算術平均值，從而量化最壞情況。 在本文中，我們將主要討論香農熵。 如果想更深入地探討和解讀熵主義的觀點，保羅·西弗森的《》值得一讀。
匿名交叉口
在 Latanya SWeeney 的論文中，她回顧了之前的一些研究成果——結果證明了“匿名”數據的重新識別。 單獨來看，數據集中與條目相關的每個屬性（例如出生日期）似乎都無法揭示該條目的主題。 但就像遊戲中的是非題一樣，只需要對數級的信息量；換句話說，令人驚訝的是，:
例如，該研究發現，87%（2.48億人口中的2.16億）的美國人口僅根據{5位數郵政編碼、性別、出生日期}就可能擁有獨特的特徵。 顯然，包含此類個人信息的發布數據不應被視為匿名。
粗略估計，一串 5 位數字將有log₂(10⁵)≈ 16.6 位最大熵，但郵政編碼的數量比這要少，log₂（4.3 x 10⁴）≈ 15.4 — 請記住，人口在郵政編碼上的分佈並不均勻，因此 13.8 將是 。 性別字段在大多數情況下通常包含略多於 1 位的信息，因為即使存在非二元性別，大多數條目仍是男性或女性。 也就是說，具有非二元值的條目會揭示關於該條目主題的遠多於 1 位的信息。 如果不考慮年齡分佈，出生日期也很難估算。
忽略 2 月 29 日，假設生日均勻分佈且出生年份為 2 位數，則熵為log₂(365 x 10²)≈ 15.1. 再次，還有更多內容，綜合起來，較為保守的估計大約為 29.7 位。 相比之下，當時美國人口均勻分佈的熵為log₂（248 x 10⁶）≈ 27.9 位，或log₂（342 x 10⁶）≈ 28.4，具有最新內容。
對於那些花了一些時間學習 SQL 中“內連接”的人來說，下面的論文圖表可能看起來很熟悉。 它展示了一個不同的例子，Sweeney 使用相同的字段將醫療記錄與選民登記名單關聯起來，並在一個“匿名”醫療數據集中識別出了時任馬薩諸塞州州長 William Weld 的具體記錄：
這種韋恩圖用兩個重疊的圓圈表示兩個集合，重疊部分突出顯示，通常表示兩個集合之間的交集。 集合是元素的無序集合，例如數據庫中的行、數字或任何其他可以用數學定義的元素。 兩個集合的交集是同時存在於兩個集合中的元素的集合。 例如，在選民登記名單中，我們可能會討論郵政編碼為 12345 的所有條目的子集，以及出生日期為 1970 年 1 月 1 日的所有條目的集合。 這兩個子集的交集是郵政編碼為 12345 的條目的子集。 和其出生日期為 1970 年 1 月 1 日。 就州長而言，在條目子集中只有一個條目的屬性值與選民登記名單中的屬性相匹配。
對於結構不同的數據集，存在一個小問題：如果我們將它們視為行的集合，那麼它們的交集將始終為空，因為行的形狀會有所不同。 在計算兩個數據庫表的內連接時，只有存在於在某種意義上，通過指定類似的東西來相交連接 a.zip = b.zip 和 a.dob = a.dob或不太便攜USING(郵政編碼，出生日期)語法，但這些相交的值與它們來自的行相關，因此鏈接兩個數據集的整體結構更加複雜。
請注意，Sweeney 的圖表描繪了數據集列的交集，強調了更主要的問題，即“匿名”數據集中包含的屬性無意中與其他公開數據集的屬性具有非空交集。
在k匿名模型的應用方面，由於後續工作中發現的一些缺陷（Aloni Cohen的“”），本文中描述的數據集匿名化程序已不再受歡迎。 k匿名的核心思想是確保對於所有可能的屬性組合，至少存在k包含數據中所有特定組合的行，這意味著需要 log₂(k) 個額外的信息位才能從其一致的條目中識別出一個條目。 為確保這一點，建議的去識別程序是以數據相關的方式進行編輯或概括，例如，從出生日期中刪除日期，保留年份和月份，如果這還不夠，甚至可以只保留年份。 Cohen 的研究表明因為即使丟棄信息直到k每種組合，以及編輯過程本身對未編輯數據集統計數據的掌握。 此類洩露，即使非常細微，也不僅會隨著時間的推移而累積，而且通常會加劇。 使用對數尺度的比特來計算隱私損失，或許有助於更好地理解隱私通常呈指數級衰減的現象。
比特幣 CoinJoins 中的匿名性：交叉攻擊
Steven Goldfeder、HARry Kalodner、Dillon Reisman 和 Arvind Narayanan 在他們的論文《隱私洩露：兩種攻擊模式》中描述了兩種獨立但相關的攻擊。 或許更重要的是，他們清晰地展示了隱私洩露如何加劇，從而為更廣泛的攻擊提供了極具說服力的論據。
在比特幣中，一種貨幣的匿名集的自然定義是該貨幣可能被合併到的集合。 如果存在多個候選簇，則匿名集並非平凡，在這種情況下，合併將取決於獲取更多信息。 新交易可能會引入不確定性，因此需要為無法合併到任何現有簇中的輸出創建新的簇。 另一方面，新交易和帶外信息也可以消除不確定性，促進簇的合併。 最常見的情況是，如果多輸入啟發式方法被認為對此類新交易有效，那麼輸入貨幣的簇將被合併。 然而，正如我們之前所見，存在許多啟發式方法，其中一些的準確性令人震驚。
假設 Alice 收到了一些比特幣，這些比特幣被存入了她控制的錢包。 其中一些可能是從交易所提取的（可能帶有 KYC 信息）。 也許是朋友付了她的午餐錢。 也許她賣掉了自己的車。 在進行了幾次交易後，Alice 意識到她的交易記錄對所有人都可見，而且很容易解讀，但很快她就需要進行不止一次交易，而是……二單獨的交易，並且隱私保證比她迄今為止所依賴的更強。
在了解了一些隱私知識後，Alice 決定使用支持 CoINJoin 的錢包。 在幾筆 CoinJoin 交易中，她用掉現有的幣，換取了顯然設置了匿名性的替代幣。 在 CoinJoin 之前，她的錢包很可能是可聚類的。 CoinJoin 之後，她現在擁有的每個 UTXO 都無法分配給任何特定的聚類，因為其他用戶的錢包聚類也隱含在各個 CoinJoin 交易中。
，任何輸出都不能與特定的輸入關聯。 這有點類似於混合網絡 (mixnet)，其中每筆 Coinjoin 交易都是一次中繼，而混合的“消息”就是代幣本身。 這個比喻過於簡單，在實現 CoinJoin 時會遇到許多導致其崩潰的複雜因素，但在本文中我們將忽略這些細微差別，並假設 Alice 選擇的 CoinJoin 錢包始終能夠成功地在每個 CoinJoin 中只使用一個輸入，從而實現其資金與 CoinJoin 其他參與方資金的完美混合。 在這些假設下，如果有kCoinJoin 交易中的等效輸出，以及k為輸入設置單獨的集群，那麼在創建此交易時，每個輸出的匿名集應該具有 log₂(k) 位熵。
CoinJoin 後聚類
現在，論文中描述的第一次攻擊已準備就緒。 此次攻擊是通過引入第三方資源（例如商家網站上支付處理器的 JavaScript）實現的。 假設用於交易的支付地址被洩露給第三方，這將導致 Alice 的網絡會話與她的鏈上交易關聯起來。 這篇論文發表於 2017 年，因此與網絡相關的洩密細節如今已有些過時，但其背後的原理依然重要。
Alice 使用她的一個 CoinJoin UTXO 完成了第一筆需要隱私保護的交易。 假設沒有語義洩露（例如與購買相關的賬單地址）或元數據洩露（例如她本人），這筆交易應該能夠保留 Alice 從之前的 CoinJoin 交易中獲得的隱私。 如圖所示，這筆交易相當於 1 位。 輸入或輸出的顏色表示它們已被分配到的集群。 Alice 的幣為紅色，漸變表示模糊性：
雖然第一筆交易本身並不能揭示太多信息，但假設 Alice 進行了另一筆交易。 假設這筆交易是與另一個商家進行的，但該商家與第一筆商家使用相同的支付處理器。 簡單來說，下圖似乎代表了 Alice 支付交易的隱私性，而攻擊者需要 2 位額外信息（每筆交易 1 位）才能將這兩筆交易歸因於 Alice 的集群：
儘管 Alice 有意將其與第一筆交易斷開關聯，但她可能並未意識到自己的網頁瀏覽活動正在被追踪。 論文表明，這種追踪不僅可行，而且切實可行，甚至可以向第三方揭示這兩筆交易可以聚類，即使它們在鏈上看起來毫無關聯。 我們可以用其他顏色來直觀地表示這種聚類：
正如論文中所討論的，網絡追踪只是促成集群信息洩露的眾多途徑之一。 例如，網站入侵可能導致購買記錄被公開，即使是在事發多年之後。 至少在 年間，本應保護受害者的法律訴訟，卻因不恰當地刪除交易金額而無謂地洩露了客戶的鏈上交易信息，最終使受害者遭受了更大的傷害。 之前關於錢包集群歷史的文章提供了幾個額外的例子。
具體來說，在 CoinJoin 的背景下，這種關聯發生的典型方式是，混合後支付交易的找零輸出隨後被 CoinJoin，並通過對輸入進行聚類使其可關聯。 這也被稱為“毒性找零問題”，如下圖所示。 請注意，本例中的白色區域並不代表單個聚類，只是缺少聚類信息。
如果所謂的“無需信任”的 CoinJoin 協議的協調者是惡意的，那麼即使這在鏈上不明顯，也可能鏈接交易。 其後果與論文中描述的攻擊相同，只是 CoinJoin 協調者還可以假裝某些參與者未能及時提交簽名，主動但隱蔽地進行，或者至少可以否認地干擾輪次以獲取更多聚類信息。
交叉前導簇
不幸的是，Alice 的故事並沒有就此結束。 論文接下來指出，鑑於 CoinJoin 後交易之間存在這種關聯，無論這種聚類是如何學習的，對 CoinJoin 交易本身的隱私進行交叉攻擊也是可能的。
這就像對手在玩“猜猜我是誰？”遊戲，並收到一筆支付交易，然後試圖猜測資金的來源。 考慮每筆 CoinJoin 交易的輸入集。 每一枚花費的幣都被分配到某個集群。 Alice 參與的每一筆 CoinJoin 交易都有一個輸入，可以鏈接到以下某個集群：她集群。 此類交易的隱私性源於與大量原本不相關的集群相鏈接。隨機個人用戶參與的頻率是多少每一個Alice 進行過哪些交易？ 如果不止一筆呢？ 這種情況並不常見。 假設交集包含一個唯一的集群，這種情況最終可能會經常發生。 在這種情況下，攻擊者將能夠將 Alice 的交易彼此關聯，並將其與 CoinJoin 之前的交易歷史記錄關聯起來，從而有效地撤銷混合。
從視覺上看，這結合了之前圖表的推論。 對於後兩張圖中紫色簇中的每枚硬幣，我們可以將其與前一張圖中描繪的漸變顏色集相交：
只有 Alice 的紅色集群位於交集處，因此紫色集群可以合併到紅色集群中。 由於本例中只有兩筆用戶 CoinJoin 交易，因此不僅 Alice 的集群會合併，其餘集群也可以通過排除法與其祖先集群合併。 因此，在這種特殊情況下，Alice 的可鏈接支付也有可能使假設的 Bob 和 Carol 去匿名化：
這表明，即使 CoinJoins 的功能像完美混合一樣（但事實並非如此），混合後交易隱私不足也會進一步損害先前 CoinJoin 交易的隱私，而且速度比直覺上要快得多。 連接比特幣交易的圖結構包含大量可供去匿名化攻擊者利用的信息。
鑑於防止甚至控制隱私洩露的挑戰，隱私問題常常被淡化。 希望人們的意識能夠提高，事情能夠像過去幾十年的密碼學那樣發展——無論是不再使用弱密鑰，還是最初大多被忽視，但現在人們普遍認為它們實際上可以被利用，而沒有考慮到它們的實現被認為是不安全的。 話雖如此，它總是更具挑戰性：在密碼學中，我們有更多機會通過優先使用臨時密鑰而不是長期密鑰，或者至少定期輪換長期密鑰來限制意外洩露的危害。 遺憾的是，我能想到的隱私領域最接近輪換密鑰的方案是證人保護計劃——這是一種相當極端且成本高昂的措施，而且遠非完美有效。
對於現實世界中的隱私，CoinJoin 隱私的挑戰依然存在。
這是 這篇文章由 撰寫，發佈於 6 月 11 日。
骨髓 每週都會發布一些與比特幣和比特幣愛好者相關的熱門話題的深度文章。 如果 如果您有符合該模型的投稿，請隨時聯繫 editor[at]Bitcoinmagazine.com。
