New Empirical Traceability Analysis of CryptoNote-Style Blockchains

发表于 | Edited on | 分类于 | 次阅读

发表于Financial Cryptography and Data Security 2019的一篇文章。
文章链接：http://fc19.ifca.ai/preproceedings/69-preproceedings.pdf

摘要

在（PETS’18）会议提出对Monero 不可追踪性的cascade effect 攻击已被开发者使用两个方法规避，其中之一是增加币环形签名(Ring Signature)中mix-ins的个数，从 0.9.0版本中的3个增加到了0.12.0版本中的7个，同时增加了ring confidential transactions(ringCTs)以提升隐私性。然而，目前并没有人对Monero当前应对的策略的匿名性进行分析。 改论文提出一种统计学分析，对所有CryptoNote类型的加密货币进行closed set attack.随后对Monero、Bytecoin以及DigitalNOte进行这种攻击，实验表明，结合了cascade attack之后的closed set attack能够识别出Monero中70.52%的input、Bytecoin中74.25%的inputs以及DigitalNote中91.56%的input。
随后对该种攻击成功的概率进行理论分析，发现成功概率为 2^19，closed set attack近似于statiscal attacks，据此，文中分析认为Monero当前的系统设置可以抵御statiscal attacks，另外文章分析说明了mix-ins不是越大越好，而是其中未被花费的input比例越高越好。

Intruductioon

目前加密货币中用户的匿名性和隐私性都逐渐受到重视，因此出现了很多致力于保护用户隐私的加密货币，例如Monero、Bytecoin、Dash、DigitalNote、Boolberry等货币，这些货币都使用了CryptoNote 协议。在这些货币中，使用了ring signature(环形签名)技术，即在一笔交易的输入中，支付方会将自己的input地址和区块链中其他output地址混合起来形成一个环，这样做的目的是不让外界知道真正的input具体是哪一个，其他没有被花费的input称之为mix-ins。

然而实际上Monero区块链中有65%的用户在花销的时候，使用的mix-ins为0，而这些交易很容易被确定真正的input，随后其他一些用户使用了这些被追踪的input作为mix-ins之后也面临着被追踪的危险，也确实有文章进行了相关分析，经过分析后发现其中87%的input都能被追踪到。随后Monero开发团队也对其进行了升级，其中引入了RingCTs技术，RingCTs技术中即使是不同数目的输入也可以作为mix-ins，同时将mix-ins的数量从2提升到了6（2019年3月29日的0.12.0版本）。但是实际上这些货币匿名性如何呢？

本文中作者引入了closed set attack方式，简而言之就是如果有X个inputs的集合，其中恰好又有X个不同的地址，那么说明在这X个inputs中，不同的X个地址都已经被花销出去，因为每个inputs至少要消费一个地址。假若其他inputs中包含了这X中的地址，那么其他inputs的匿名集就可以减小，如果减小到1，就能够追踪到其中的交易。

Preliminary

CryptoNote protocol

CryptoNote协议致力于做两件事情：

  • Untraceability： 对于任何交易，真正被花费的地址应该是在一系列outputs中匿名的作为inputs
  • Unlinkability： 对于任意两个交易，不可能证明这两笔交易是发送给同一个用户的。

为了实现unlinkability，CryptoNote中每次转账时使用一个一次性地址，而这个一次性地址来源于接受者的公钥和发送者生成的一个随机数。 为了实现untraceability，CryptoNote中使用了环形签名。

Closed Set Attack

为了说明攻击方法，用txi.in表示每笔交易的输入，假设当前有4笔交易，每笔交易中的inputs分别是：

  • tx1.in = { pk1, pk2, pk3 }
  • tx2.in = { pk2, pk3 }
  • tx3.in = { pk1, pk3 }
  • tx4.in = { pk1, pk2, pk3, pk4 }
    其中pk表示public key， 即公钥。在tx1、tx2以及tx3中分别用到了pk1、pk2和pk3，而每个tx中都会花费一个pk，因此前3个交易必然是吧pk1、pk2和pk3已经花费掉了，在tx4中，很明显可以推出pk4是真正的花费地址。
    应用理论分析应该是，在一系列交易中，所有的inputs的数量之和恰好等于这些inputs中不同地址的数目，那么其他应用这些不同地址作为mix-ins的交易，其匿名集中可以除去这些地址以减少其匿名集，如果匿名集和数量为1，那么这笔交易就成为可追踪交易了。

Definition of Cluster

那么这种攻击是如何进行的呢？文中定义一个Clus记为一个inputs的集合，Clus = { R1， R2，…, Rn }，每一个Clusetr中所有不同地址的集合，称之为PK_Clus，一个inputs我们使用R代表。假设已经存在一个Clus，那么一个inputs和Clus之间的差集定义为

  • Dist(R, Clus) = Dist(R, PK_Clus) = |R| - |PK_Clus∩R|
    举例说明之，假设Clus = { { pk1, pk2 } , { pk1, pk3 }, { pk2, pk4 } }, 那么PK_Clus = { pk1, pk2, pk3, pk4 }，假设某个R = { pk1, pk3, pk5 }, 那么Dist(R, Clus) = 3-2 =1.

closed set Attack Algorithm

为了进行closed set Attack，文中使用了一种聚类的方法，这种聚类的方法由两个算法构成，其中第二个算法调用了第1个算法。算法首先对所有的inputs应用Cascade-Effect攻击以减少其匿名集，随后对剩余的inputs集合输入到算法2中，Algorithm 2如下：

1
2
3
4
5
6
7
8
9
10
11
12
1: Let DataSet be all transaction inputs in the blockchain.
1. Cascade-Effect(Dataset)
2. Flag = true
3. while Flag == true do
4.     Flag = false
5.     for each R ∈ DataSet do
6.     Clus_Form(R) -> Clus		// 调用了Algorithm 1
7.     if Clus is a closed set then
8.        Remove(Clus) ->Flag  // 删除Dataset中的Clus集合
9.        if Flag == true then
10.           find traceable inputs
11.           check whether rings inside Clus are traceable

Algorithm 1算法如下：

1
2
3
4
5
6
1.  Start with an input R, and define the cluster as Clus = { R }
2. Let DataSet be all transaction inputs in the blockchain
3. for each R1(≠ R) 2 DataSet do
4.     if Dist(R1， Clus) ≤ 1 then
5.         Clus = Clus ∪ { R1 }
6. return Clus

对于Dataset中的所有inputs，迭代使用Algorithm 2，假设所有inputs个数为N，而每个R的长度为L，那么总的算法复杂度为θ(LN²) 。

Experiment

Dataset

本文收集了从Monero区块链创世块(2014年4月18日)到2018年3月30日的区块，总共1541236个区块，工2612070笔非coinbase 交易。

Experiment Result

将本文方法应用于Monero区块链分析，首先应用Cascade effect attack，发现其中16334967笔交易可追踪，而closed set总工追踪到了5752笔交易，因此总共追踪到70.52%的inputs。追踪结果如下表所示。总共找到3017个closed set，大小从2到55不等，总共包含了7478个public_keys，这些public keys已经被花销了，如果其他输入使用这些inputs作为mix-ins，那么是无效的。

mix-insg个数 inputs数 共可追踪inputs数 Cascade Effect Closed set 百分比
0 12209675 12209675 12209675 0 100
1 707786 625641 625264 377 88.39
2 4496490 1779134 1776192 2942 39.57
3 1486593 952855 951984 871 64.10
4 3242625 451959 451230 729 13.94
5 319352 74186 73980 206 23.23
6 432875 202360 202100 260 46.75
7 21528 4296 4282 14 19.96
8 30067 3506 3490 16 11.66
9 17724 2178 2162 16 12.29
Total ≥10 200030 29177 28856 321

最后还剩余6829778笔inputs仍然不可追踪，但是这些交易的匿名集已经大大减少，减少情况如下图所示。可以看到，很多之前inputs中地址很多，但是经过closed set分析之后币有多都可以识别，其中inputs你们集合是1的，当下有超过100万，想办法进一步进行分析，或许可以有更多收获。不过作者并没有进一步分析。

在这里插入图片描述

此外，作者分别对Bytecoin和DigitalNote进行了同样的分析，分析的结果没有过多需要介绍的，因此这里略过。

Observations and Recommendations

  • Obervation 1： 区块链中outputs的使用率是匿名性中一个非常重要的因素，因为每个outputs毕竟只能被redeem 1次，因此低的使用量能提升匿名性。
  • Obervation 2： Closed sets与intpus的匿名性息息相关，找到Closed sets有助于减少匿名集和找到real spent，虽然其数量不多，但是仍然会威胁到匿名集。
  • Recommendation 1： 为了减少outputs的使用率，应该增加更多的outputs，建议用户增加一些价值为0 的输出。(PS:输出越多，花费的交易费越多，用户愿意吗？)
  • Recommendation 2： 不用使用无效的mix-ins。PS：如果用户知道的话，用户当然不会使用了。

Thinking

这篇文章就提出了1种攻击方式，相比于其他文章来说，在内容和分析展示情况上都显示出比较单一，个人觉得提出的方法很好，但是并没有很好地挖掘这种方法之后的结果，这种方法已经将匿名集降低到1了，此时如果在坚持一下，或者在想想别的分析方法，那么就不是简单的发表在FC上了，可以冲击一下B类会议。