论文笔记：P2P Mixing and Unlinkable Bitcoin Transactions

CoinShuffle：利用mixing技术混合多笔交易输入输出之间的比特币链接。
P2P Mixing：不依赖任何第三方的匿名广播混洗协议

问题：

1. 现有的混洗方案不支持可扩展性。
2. 通信代价高，最好的情况下为O(n)轮，存在f个恶意参与方时，达到O(nf)的通信轮次复杂度。
3. DC-net是一种隐私保护的分布式通信协议，通信效率高，适合用于混洗方案，但存在易破坏，要求可信第三方等问题。目前没有实用的基于DC-net的P2P Mixing方案。

P2P Mixing协议的概念化要点（特点）：

1. 对输入输出的特殊要求：
   • 输入：Fresh message
     • 要求每个参与方使用具有足够熵的新生成的位串；
     • 如果协议中有参与方被丢弃（如，下线，恶意），所有参与方的消息都要被丢弃，新一轮中使用新生成的消息。
   • 输出：额外的确认步骤
     • 要求所有参与方在混合生效前明确同意混合的输出（如，共同匿名签名）；
     • 将恶意参与方剔除。
2. 形式化接口：
   GEN()：生成fresh input message
   CONFIRM(i,P,M)：从所有未被剔除的参与方中获得对M的确认

例如：
Run 1:$GEN()\to m_1\to mix失败（参与方p主动干扰）\to 〖P_2:P{〗}_1剔除参与方p$
Run 2:$GEN()\to m_2\to mix成功\to CONFIRM(2,P_2,M_2)\to P_{(}mal,2)\ne \varnothing \to 确认失败，〖P_3:P{〗}_2剔除P_{(}mal,2)$
Run 3:$GEN()\to m_3\to mix成功\to CONFIRM(3,P_3,M_3)\to P_{(}mal,3)=\varnothing \to 确认成功，执行结束，输出混洗后的集合M_3$

3. 安全性目标：
   • Sender Anonymity：如果诚实参与方p使用消息m_p和最终参与方集合P运行一次协议成功，p^‘∈P是另一个诚实参与方，则攻击者无法区分消息m_p属于p还是属于p’。
     • 假设公告板不诚实：攻击者阻碍诚实参与方的通信，导致其被剔除。则设n为未被剔除的参与方个数，f<n-1
     • 只关注成功运行中的消息，对于失败运行中丢弃的消息，不保证匿名）
   • Termination：假设公告板是诚实的，则协议最终会为每个诚实的参与方成功结束。

关键技术：

Slot冲突：

P2P mixing的每个参与方都想要匿名发布自己的消息，他们可以运行一个DC-net的|P|个实例，每个参与方随机选择一个实例(或slot)来发布她的消息
即使所有的对等体都是诚实的，两个对等体也有很大可能选择同一个slot

冲突处理：基于Newton’s identities抽取消息的方法

1. n slots，每个参与方index i，消息$m_i$，发布$m_i^j$（ $m_i$ 的$j$次幂）。用加法代替XOR来生成DC-net 消息，每个slot冗余发布消息幂和：$S_i={\sum }_i{m}_i^j$
2. 广播后每个参与方都能计算：
   
3. 用Newton’s identities 抽取$x_1,\dots ,x_n$
   • 设多项式：$f(x)=a_n{x}^n+a_{(}n-1)x^{(}n-1)+\cdots +a_{1}x+a_0$，使得$f(x)=0$有根$x_1,\dots ,x_n$.
     $$f(x)=(x-x_1)\cdot \dots \cdot (x-x_n)=0\to a_n=1$$
   • 一般化Newton’s identities定理:
     
   • 已知所有P_i，代入能够很容易地恢复出所有的a_i，直到计算出多项式f(x)的所有系数。
4. 对f(x)进行因式分解，得到n个解（即，m_1,…,m_n）。

仍然存在的问题：

恶意参与方捣乱可能导致Newton’s identities恢复消息失败，或恢复错误的消息。
解决：在中断的情况下打破匿名。由于fresh message，这不会泄露隐私

• 由于DC-nets的发送方匿名性，行为不端的参与方不会被轻易检测到。
• 披露所有在初始密钥交换中使用的密钥
• 每个参与方可以重播其他参与方所做的步骤，剔除恶意参与方

DiceMix-基于DC-net的实用P2P Mixing协议

DiceMix协议流程：

优化通信轮次：

• 顺序执行：4+4f rounds
  
• 并行运行（两轮执行之间部分步骤可重叠）: 4+2frounds
  
  大大优化了通信性能！

CoinShuffle++：将DiceMix用于区块链混币协议

算法：

一种对其他P2P Mixing方案的攻击

DiceMix免疫此攻击

核心思想：如果一个参与方被动地离线，它将被视为恶意参与方牺牲其匿名性。问题在于：如何判断该参与方是否是真的恶意？如果它是诚实的呢？

例：Dissent方案，剩余的参与方判断p离线并将其排除；发起第二次运行，重新发送第一次运行中使用的消息M’，M^(') M={m_p}

通过延迟or隔离p的通信，实现对特定参与方的去匿名攻击！
DiceMix的fresh message机制天然地免疫这类攻击！