如何利用聚类破坏 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. 再次，还有更多内容，14.9 位。综合起来，较为保守的估计大约为 29.7 位。相比之下，当时美国人口均匀分布的熵为log₂（248 x 10⁶）≈ 27.9 位，或log₂（342 x 10⁶）≈ 28.4，具有**内容。
对于那些花了一些时间学习 SQL 中“内连接”的人来说，下面的论文图表可能看起来很熟悉。它展示了一个不同的例子，Sweeney 使用相同的字段将医疗记录与选民登记名单关联起来，并在一个“匿名”医疗数据集中识别出了时任马萨诸塞州州长 William Weld 的具体记录：
来源：k-匿名：一种保护隐私的模型这种韦恩图用两个重叠的圆圈表示两个集合，重叠部分突出显示，通常表示两个集合之间的交集。集合是元素的无序集合，例如数据库中的行、数字或**其他可以用数学定义的元素。两个集合的交集是同时存在于两个集合中的元素的集合。例如，在选民登记名单中，我们可能会讨论邮政编码为 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 Rei**an 和 Arvind Narayanan 在他们的论文《隐私泄露：两种攻击模式》中描述了两种独立但相关的攻击。或许更重要的是，他们清晰地展示了隐私泄露如何加剧，从而为更广泛的攻击提供了极具说服力的论据。
在比特币中，一种货币的匿名集的自然定义是该货币可能被合并到的集合。如果存在多个候选簇，则匿名集并非平凡，在这种情况下，合并将取决于获取更多信息。新交易可能会引入不确定性，因此需要为无法合并到**现有簇中的输出创建新的簇。另一方面，新交易和带外信息也可以**不确定性，促进簇的合并。最常见的情况是，如果多输入启发式方法被认为对此类新交易有效，那么输入货币的簇将被合并。然而，正如我们之前所见，存在许多启发式方法，其中一些的准确性令人震惊。
假设 Alice 收到了一些比特币，这些比特币被存入了她控制的钱包。其中一些可能是从交易所提取的（可能带有 KYC 信息）。也许是朋友付了她的午餐钱。也许她卖掉了自己的车。在进行了几次交易后，Alice 意识到她的交易记录对所有人都可见，而且很容易解读，但很快她就需要进行不止一次交易，而是……二单独的交易，并且隐私保证比她迄今为止所依赖的更强。
在了解了一些隐私知识后，Alice 决定使用支持 CoinJoin 的钱包。在几笔 CoinJoin 交易中，她用掉现有的币，换取了显然设置了匿名性的替**。在 CoinJoin 之前，她的钱包很可能是可聚类的。CoinJoin 之后，她现在拥有的每个 UTXO 都无法分配给**特定的聚类，因为其他用户的钱包聚类也隐含在各个 CoinJoin 交易中。
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 交易都有一个输入，可以链接到以下某个集群：她集群。此类交易的隐私性源于与大量原本不相关的集群相链接。对手知道 CoinJoin 后交易将多个 CoinJoin 输出链接在一起，因此可以计算相关集群集的交集。随机个人用户参与的**是多少每一个Alice 进行过哪些交易？如果不止一笔呢？这种情况并不常见。假设交集包含一个**的集群，这种情况**可能会经常发生。在这种情况下，攻击者将能够将 Alice 的交易彼此关联，并将其与 CoinJoin 之前的交易历史记录关联起来，从而有效地撤销混合。
从视觉上看，这结合了之前图表的推论。对于后两张图中紫色簇中的每枚硬币，我们可以将其与前一张图中描绘的渐变颜色集相交：
只有 Alice 的红色集群位于交集处，因此紫色集群可以合并到红色集群中。由于本例中只有两笔用户 CoinJoin 交易，因此不仅 Alice 的集群会合并，其余集群也可以通过排除法与其祖先集群合并。因此，在这种特殊情况下，Alice 的可链接支付也有可能使假设的 Bob 和 Carol 去匿名化：
这表明，即使 CoinJoins 的功能像**混合一样（但事实并非如此），混合后交易隐私不足也会进一步损害先前 CoinJoin 交易的隐私，而且速度比直觉上要快得多。连接比特币交易的图结构包含大量可供去匿名化攻击者利用的信息。
鉴于防止甚至控制隐私泄露的挑战，隐私问题常常被淡化。希望人们的意识能够提高，事情能够像过去几十年的密码学那样发展——无论是不再使用弱密钥，还是最初大多被忽视，但现在人们普遍认为它们实际上可以被利用，而没有考虑到它们的实现被认为是不安全的。话虽如此，它总是更具挑战性：在密码学中，我们有更多机会通过优先使用临时密钥而不是长期密钥，或者至少定期轮换长期密钥来限制意外泄露的危害。遗憾的是，我能想到的隐私领域最接近轮换密钥的方案是证人保护计划——这是一种相当极端且成本高昂的措施，而且远非**有效。
对于现实世界中的隐私，CoinJoin 隐私的挑战依然存在。
这是 这篇文章由 撰写，发布于 6 月 11 日。
骨髓 每周都会发布一些与比特币和比特币爱好者相关的热门话题的深度文章。如果 如果您有符合该模型的投稿，请随时联系 editor[at]bitcoinmagazine.com。