交易中继协议Erlay

目前，当节点获得新交易时，它会向连接的所有节点广播该交易（除了之前发送该交易的节点）。这是一个非常简单有效的策略，但效率不高 - 节点收到的大多数交易都是已经从不同节点收到的交易，这种冗余浪费了大约44％的节点带宽（根据论文）。

本文试图使用Erlay协议来减少冗余，该协议将中继分为两个阶段：扇出阶段和协调阶段。

• 在扇出阶段，节点将仅从节点的出站节点中选择部分节点广播新交易，而不是向所有节点广播交易。

• 在协调阶段，节点将周期性地从每个出站节点请求所有新交易的短交易标识符（txid前8字节）的草图。草图使用minisketch算法创建，该算法实现了高效的集合协调算法。收到请求的草图后，节点本身还会生成所有新交易的草图。节点将本地草图与接收到的草图组合在一起，生成草图之间差异的列表。然后，节点可以请求缺少的任何交易，并继续查询该节点下一个节点的草图。每隔时间T重复一次，从而允许节点快速接收通过扇出通知未收到的任何交易。

集合协调算法

erlay使用的集合协调算法为Minisketch,使用该算法生成的集合草图具有以下特性:
•草图具有预定容量，当集合中的元素数量不超过容量时，始终可以通过解码草图从草图中恢复整个集合。 具有容量c的b位元素的草图可以以bc位存储。
•通过对这些集的草图的位表示进行异或运算，可以获得两个集之间的对称差异草图（即，出现在一个但不是两个集合中的所有元素）。

节点间协调流程
（1）Alice和Bob节点计算本地交易草图。
（2）Alice将草图发送给Bob。
（3）Bob计算两个草图的对称差异。
（4）Bob 获取自己缺少的交易。
（5）Bob向Alice发送alice缺少的交易。
对草图进行解码在计算上是昂贵的，并且计算量是差异的二次方。 因此，准确估计差异的大小并在集合差异变得过大之前进行协调是协议的重要目标。
重要的参数
D – 草图真正的差异大小。
d – D的估计值。
q – 计算d的参数。
准确估计D对于协调的成功至关重要。论文采用了一种简约的方法，根据当前的集合大小和之前的对帐轮次中观察到的差异来估计集合差异的大小。

d = abs(|A| − |B|) + q · min(|A|, |B|) + c

其中q是表征先前对帐的浮点系数（在下面导出），c是用于处理特殊情况的参数。

q=(D − abs(|A| − |B|)) / (min(|A|, |B|))

此更新的q将用于下一轮对帐。 我们以这种方式计算q，因为我们假设网络中的每个节点都具有一致的最优q。
协议具体流程

Minisketch 数学原理

集合草图

出于本说明的目的，草图可以被视为具有两个特殊属性的“集合校验和”：

• 草图具有预定的容量，并且当集合中的元素数量不高于容量时，minisketch将始终能从草图恢复整个集合。具有容量c的b位元素的草图可以以bc位存储。

• 可以通过（XOR）组合两组的草图以获得两组之间的对称差异（即，在一个但不是两个输入组中出现的所有元素）。

此概述说明了如何将集合转换为草图以及如何从草图中恢复集合。

从字段元素到草图

数据条目作为字段元素

范围 [1…2^b-1] 中的每个整数（具有字段大小b的Minisketch草图的可接受数据元素）可以映射到有限域 GF(2^b) 的非零字段元素。在这个有限域中，我们可以添加和相乘元素，并为这些操作提供自定义。字段元素的加法（和减法）对应于它们对应的整数的XOR运算，但乘法复杂一些。

集合幂级数

我们定义了一个函数S，它将元素m映射到下面形式的幂级数：

• S(m) = 1 + mx + m²x² + m³x³ + ….
  然后，我们通过将集合元素的函数结果相加来扩展此函数以对字段元素集进行操作。如果M={m1，m2，…}：
• S(M) = S({m₁,m₂,…}) = S(m₁) + S(m₂) + … = (1 + 1 + …) + (m₁ + m₂ + …)x + (m₁² + m₂² + …)x² + (m₁³ + …
  因为在我们的有限域,加法对应于XOR，所以对于每一个a是a + a = 0。如果把这个规则引入S函数，意味着对于每个a，S（a）+ S（a）= 0。这意味着这些幂级数的系数具有我们希望的草图的第二个属性，即存在组合两个草图的有效操作，使得结果是集合的对称差异的草图。它认为 S({m₁,m₂}) + S({m₂,m₃}) = S(m₁) + (S(m₂) + S(m₂)) + S(m₃) = S(m₁) + S(m₃) = S({m₁,m₃}}).

问题是我们是否也可以从其幂级数系数中有效地恢复元素。

无穷大的系数近似

为了更容易理解这些幂级数，请注意单个元素的系列实际上是几何级数。如果我们正在研究实数而不是有限域并且 |mx| < 1，它会收敛到 (1 - mx)^-1。

• (1 - mx) S(m) = 1
  这可以推广到多个集合元素的运算。对于我们有两个要素：

• (1 - m₁x) (1 - m₂x) S({m₁,m₂}) = (1 - m₁x) (1 - m₂x) (S(m₁) + S(m₂)) = (1 - m₂x) + (1 - m₁x)
  对于三个：

• (1 - m₁x) (1 - m₂x) (1 - m₃x) S({m₁,m₂,m₃}) = (1 - m₁x) (1 - m₂x) (1 - m₃x) (S(m₁) + S(m₂) + S(m₃)) = (1 - m₂x)(1 - m₃x) + (1 - m₁x)(1 - m₃x) + (1 - m₁x)(1 - m₂x)
  在每一种情况下，我们注意到，S(M)(1 - m_ix) 其中mi是集合M元素，得到一个n-1阶多项式。

解析集合元素

上面的函数让我们可以构建了一个求解器，它从幂级数的系数中提取集合元素。如果我们能找到一个多项式L由N个不同 (1 - m_ix) 因子组成，对于不同的m_i，使得 P = S(M)L 为 n-1 阶多项式，然后这些值mi是M的元素。

P的系数是集合元素本身的非平凡表达式。然而，我们可以只关注P中的n阶或更高阶的系数，其它系数都是0.让si做S（m）系数 ，Ii做L的系数，S(M) = s₀ + s₁x + s₂x² + s₃x³ + … 并且 L = l₀ + l₁x + l₂x² + l₃x³ + … + l_nxⁿ。注意 l₀ = 1，它是 (1 - m_ix) 因子中所有单一项的乘积。

以下是n+1到2n阶的 S(M)L 系数的等式：

• s_n+1 + s_n+0l₁ + s_n-1l₂ + s_n-2l₃ + … + s₁l_n = 0
• s_n+2 + s_n+1l₁ + s_n+0l₂ + s_n-1l₃ + … + s₂l_n = 0
• s_n+3 + s_n+2l₁ + s_n+1l₂ + s_n+0l₃ + … + s₃l_n = 0
• …
• s_2n + s_2n-1l₁ + s_2n-2l₂ + s_2n-3l₃ + … + s_nl_n = 0

这些是具有n个未知数n个线性方程，可以使用高斯消元法求解。在这样做之后，我们得到L的系数，然后可以将其分解为一阶因子 (1 - m_ix)。得到的m值是我们的集合元素。

算法结论

有趣的是，解决上述方程组只需要2n个S（M）系数。这意味着我们得到答案：1至2N的S(M)系数，或列表 [m₁ + m₂ + …, m₁² + m₂² + …, …, m₁²ⁿ + m₂²ⁿ + …] 用作草图，满足我们想要的两个属性：

• 通过简单地将列表元素相加组成的草图，可以用来计算其对称差异的草图。
• 使用2n个列表元素，我们可以有效地从草图中恢复n个元素。

结论

在描述了Erlay协议之后，使用60,000个节点的模拟网络（数量与当前比特币网络相似）和100个节点的实时集合分析了其性能，这些节点遍布多个数据中心。最值得注意的结果是，Erlay将用于宣布新交易存在的带宽量减少了84％。 但是，传输到网络中所有节点的交易确实需要大约80％（2.6秒）的时间。比特币交易仍然只能平均每十分钟确认一次，因此三秒减速似乎是一个合理的价格，可以为带宽的大幅减少付出代价。

考虑到比特币中继策略未来可能发生的变化，文中指出出站节点数量从8个增加到32个，广播新交易带宽使用Erlay协议增加了32%，而使用目前的广播协议需要增加300%。正如上面关于Erlay两个阶段的段落中所描述的那样，新的交易仍然只能通过直接传达给8个对等点，但是节点会与所有32个对等点进行集合协调。中继连接性能提高了四倍，提高了像LN这样的协议的时间敏感交易能够快速进入矿工节点的机会。