BIP协调：bips/bip-reconcil.mediawiki，来自naumenkogs/bips

该文档描述了一种P2P协议扩展，用于在两个节点之间协调交易广播，这是高效交易中继协议（例如Erlay）的基础。该协议通过使用集合协调技术，旨在降低交易广播的带宽成本，提高网络连接的鲁棒性，并改进隐私。

markdown 跳到内容

naumenkogs/ bips 公开

从 bitcoin/bips fork

折叠文件树

文件

bip-reconcil

搜索此仓库

/

bip-reconcil.mediawiki

复制路径

Blame更多文件操作

Blame更多文件操作

最近提交

naumenkogsnaumenkogs

bip for erlay messages

2019年9月25日

311c085 · 2019年9月25日

历史

历史

打开提交详情

查看此文件的提交历史。

296 行 (207 loc) · 19.6 KB

/

bip-reconcil.mediawiki

顶部

文件元数据和控制

  • 预览

  • 代码

  • Blame

296 行 (207 loc) · 19.6 KB

Raw

复制原始文件

下载原始文件

大纲

编辑和原始操作

  BIP: ???
  Layer: Peer Services
  Title: Transaction announcements reconciliation
  Author: Gleb Naumenko <naumenko.gs@gmail.com>, Pieter Wuille <pieter.wuille@gmail.com>
  Comments-Summary: ???
  Comments-URI: ???
  Status: Draft
  Type: Standards Track
  Created: 2010-00-00
  License: PD
## 目录<br>Permalink: 目录<br>- 摘要<br>- 动机 <br> - Erlay<br>- 规范 <br> - 新的数据结构 <br> - 32位短交易ID<br> - 短交易ID草图<br> - 截断的交易ID<br> - 预期协议流程 <br> - 二分<br> - 新消息 <br> - sendrecon<br> - reqreconcil<br> - sketch<br> - reqbisec<br> - reconcildiff<br> - invtx<br> - gettx<br>- 本地状态 <br> <br> - 协调集<br> - 协调集快照<br> - q系数<br>- 向后兼容性<br>- 原理 <br> <br> - 为什么使用PinSketch进行集合协调？<br> - 为什么使用32位短交易ID？<br> - 为什么使用128位短ID？<br> - 为什么使用二分法而不是扩展草图？<br>- 实现<br>- 致谢<br>- 版权

摘要

Permalink: 摘要

本文档指定了一个用于2个节点之间的交易公告协调的P2P协议扩展，这是高效交易中继协议（例如，Erlay）的构建块。这是朝着以几乎零带宽成本增加网络连接性迈出的一步。

动机

Permalink: 动机

目前在比特币网络中，每个32字节的交易ID都通过INV消息在每对连接的对等方之间以至少一个方向进行广播。这导致了广播交易的高成本：O(节点 * 每个节点的连接数)。

一个基于协调的协议，它使用本文档中建议的技术，可以比基于INV的泛洪具有更好的扩展属性。

增加网络的连接性使网络更能抵抗分区攻击；因此，改进交易中继的带宽扩展到 O(节点)（并且没有很高的恒定开销）将使我们能够通过增加连接性来提高网络的安全性。它还将减少运行比特币节点所需的带宽，并可能使更多用户能够运行完整节点。

Erlay

Permalink: Erlay

Erlay 是一个高级交易中继协议的示例，该协议采用集合协调来实现带宽效率。

Erlay 使用泛洪（使用 INV 消息广播到所有对等节点）和协调来广播交易。 泛洪的成本很高，因此 Erlay 试图谨慎地在战略位置使用它 - 只有良好连接的公共可访问节点才通过出站连接将交易泛洪到其他公共可访问的节点。 由于每个无法访问的节点都直接连接到多个可访问的节点，因此该策略可确保快速传播交易，使其位于网络中大多数节点的一跳范围内。

所有未通过泛洪传播的交易都通过有效的集合协调传播。 为此，每个节点都为每个对等节点维护一个协调集，其中放置了如果不存在此协议，将使用 INV 消息广播的交易。每隔 2 秒，每个节点都以预定的顺序从其出站连接中选择一个对等节点进行协调，从而导致双方都了解另一方已知的交易。在每一轮协调之后，相应的协调集将被清除。 有关集合协调轮次和其他实现细节的更详细描述，请参见论文。

Erlay 允许我们：

  • 节省节点消耗的 40% 的带宽，假设截至 2019 年 7 月的典型网络连接
  • 实现类似的延迟
  • 以几乎零带宽或延迟成本增加网络连接性
  • 改善隐私作为副作用

本文档提出了一种 P2P 层扩展，该扩展是启用基于有效协调的交易中继协议（如 Erlay）所必需的。

规范

Permalink: 规范

新的数据结构

Permalink: 新的数据结构

首先将几种新的数据结构引入 P2P 协议，以帮助实现有效的交易中继。

32位短交易ID

Permalink: 32位短交易ID

在协调期间，使用大小仅为 32 位的显著缩写的交易ID。为了防止攻击者构建导致全网冲突的交易集合，短ID计算在每个链接的基础上使用由两个通信伙伴贡献的64位熵进行加盐。

短ID的计算方式如下：

  • 令 salt1 和 salt2 为双方贡献的熵；有关如何交换它们的详细信息，请参阅后面的“sendrecon”消息。
  • 对两个盐进行排序，使 salt1 ≤ salt2（哪一方发送什么并不重要）。
  • 计算 h = SHA256("Tx Relay Salting" || salt1 || salt2)，其中两个盐以64位小端字节顺序编码。
  • 令 k0 为通过以小端字节顺序解释 h 的前 8 个字节获得的 64 位整数。
  • 令 k1 为通过以小端字节顺序解释 h 的第二个 8 个字节获得的 64 位整数。
  • 令 s = SipHash-2-4((k0,k1),wtxid)，其中 wtxid 是由 BIP141 定义的包含见证数据的交易哈希。
  • 短ID等于 1 + (s mod 0xFFFFFFFF)。

这导致范围 [1..0xFFFFFFFF] 中近似均匀分布的ID，这是将它们用作 32 位草图中的元素的要求。有关详细信息，请参见下一段。

短交易ID草图

Permalink: 短交易ID草图

基于协调的中继使用 PinSketch 基于BCH的安全草图，如 Fuzzy Extractors paper 中引入的那样。它们是一种集合校验和形式，具有以下属性：

  • 草图具有预定的容量，并且当集合中的元素数量不超过容量时，始终可以通过解码草图来从草图中恢复整个集合。容量为c的非零b位元素的草图可以存储在bc位中。
  • 可以通过组合这些集合的草图来获得两个集合之间 对称差 的草图（即，仅在一个输入集合中出现的所以元素）。

此处使用的草图由 有限域 GF(232) 的元素组成。具体来说，我们将有限域元素表示为 GF(2) 上以 x 为变量，模 x32+ x7 + x3 + x2 + 1 的多项式。要将整数映射到有限域元素，只需将整数中的每个位 i（值为 2i）视为多项式表示中 xi 的系数。例如，整数 101 = 26 + 25 + 22 + 1 映射到域元素 x6 + x5 + x2 + 1。这些域元素可以相加和相乘，但这不在本文档的讨论范围内。

容量为 c 的短 ID 草图由 c 个域元素序列组成。第一个是集合中所有短 ID 的总和，第二个是所有短 ID 的 3 次方之和，第三个是 5 次方之和，依此类推，直到最后一个元素是 (2c-1) 次方之和。然后，这些元素以小端字节顺序编码为 32 位整数，从而产生 4c 字节的序列化。

以下 Python 3.2+ 代码实现了草图的创建：

FIELD_BITS = 32
FIELD_MODULUS = (1 &lt;&lt; FIELD_BITS) + 0b10001101

def mul2(x):
    """Compute 2*x in GF(2^FIELD_BITS)"""  # 计算 GF(2^FIELD_BITS) 中的 2*x
    return (x &lt;&lt; 1) ^ (FIELD_MODULUS if x.bit_length() >= FIELD_BITS else 0)

def mul(x, y):
    """Compute x*y in GF(2^FIELD_BITS)"""  # 计算 GF(2^FIELD_BITS) 中的 x*y
    ret = 0
    for bit in [(x >> i) & 1 for i in range(x.bit_length())]:
        ret, y = ret ^ bit * y, mul2(y)
    return ret

def create_sketch(shortids, capacity):
    """Compute the bytes of a sketch for given shortids and given capacity."""  # 计算给定 shortid 和给定容量的草图的字节
    odd_sums = [0 for _ in range(capacity)]
    for shortid in shortids:
        squared = mul(shortid, shortid)
        for i in range(capacity):
            odd_sums[i] ^= shortid
            shortid = mul(shortid, squared)
    return b''.join(elem.to_bytes(4, 'little') for elem in odd_sums)

minisketch 库有效地实现了这些草图的构造、合并和解码。

截断的交易ID

Permalink: 截断的交易ID

为了在协调之外广播和中继交易，我们需要一种明确的、未加盐的方式来引用交易，以消除交易请求的重复数据。由于我们无论如何都要引入一种新方案，因此这是一个切换到基于 wtxid 的请求而不是基于 txid 的请求的好机会。虽然使用完整的 256 位 wtxid 是可能的，但这有点过头了，因为它们也对总带宽做出了重大贡献。相反，我们将 wtxid 截断为仅其前 128 位。这些被称为截断的 ID。

预期的协议流程

Permalink: 预期的协议流程

集合协调主要包括请求后传输和解码协调集草图。

集合协调协议流程

二分

Permalink: 二分

如果节点无法从接收到的草图中重建集合差异，则该节点会发出额外的协调请求，类似于初始请求，但此请求仅应用于可能交易的一小部分（例如，在 0x0–0x8 范围内）。由于草图的线性，交易子集的草图将允许节点计算剩余部分的草图，从而节省带宽。

二分

新消息

Permalink: 新消息

添加了几个新的协议消息：sendrecon、reqreconcil、sketch、reqbisec、reconcildiff、invtx、gettx。本节介绍它们的序列化、内容和语义。

在下文中，所有整数都以小端字节顺序序列化。布尔值编码为单个字节，该字节必须恰好为 0 或 1。数组使用 CompactSize 前缀序列化，该前缀编码它们的长度，这在其他 P2P 消息中很常见。

sendrecon

Permalink: sendrecon

sendrecon 消息声明支持协调协议。预计只会发送一次，并且会被不支持它的节点忽略。

它的有效负载包括：

数据类型 名称 描述
bool sender 指示发送方是否将发送“reqreconcil”消息
bool responder 指示发送方是否将响应“reqreconcil”消息。
uint32 version 目前必须恰好为 1。
uint64 salt 短交易 ID 计算中使用的 salt。

只有在发送方发送了 sender=true 的“sendrecon”消息，并且接收方发送了 responder=true 的“sendrecon”消息时，才能发送“reqreconcil”消息。

reqreconcil

Permalink: reqreconcil

reqreconcil 消息启动一轮协调。

数据类型 名称 描述
uint16 set_size 发送方的协调集的大小，用于估计集合差异。
uint8 q 用于估计集合差异的系数。

收到“reqreconcil”消息后，接收方：

  • 构造并发送“sketch”消息（见下文），其草图容量计算为 ``|set_size - local_set_size| + q * (set_size + local_set_size) + c ，其中 local_set_size 表示接收方的协调集的大小。
  • 创建其当前协调集的快照，并清除该集合本身。快照将保留到节点收到“reconcildiff”消息为止。

建议使用 c=1 以避免发送空草图并减少因低估而造成的开销。

直观上，q 表示集合的差异：集合越接近，最佳 q 越低。 正如 Erlay 建议的那样，q 应被导出为给定对等方的先前协调的最佳 q 值，一旦实际集合大小和集合差异已知。或者，q=0.1 应作为默认值使用。 例如，如果在前一轮中 set_size=30 且 local_set_size=20，并且*实际*差异为 4，则节点应计算q，如下所示： q=(|30-20| - 1) / (30+20)=0.18 q 的推导可以根据协议的版本而改变。

在发送“reconcildiff”消息之前，不能发送新的“reqreconcil”消息。

sketch

Permalink: sketch

草图消息用于传递执行集合协调所需的草图。

数据类型 名称 描述
byte[] skdata 发送方的协调快照的草图

收到“sketch”消息后，节点通过将接收方草图与在本地为相应协调集计算的草图组合来计算集合差异。如果这是此轮第二次收到“sketch”消息，则使用二分法，并且通过将新草图与前一个草图组合，获得两个差异草图，一个用于短 id 范围的前半部分，一个用于后半部分。然后，接收节点尝试解码此草图（或草图），并根据结果：

  • 如果解码失败，则发送设置了失败标志（success=false）的“reconcildiff”消息。如果这是本轮的第一个“sketch”，则可以改为发送“reqbisec”消息。
  • 如果解码成功，则发送“reconcildiff”消息，其中包含所有本地已知事务的截断 ID，这些事务出现在解码结果中，以及无法识别事务的短 ID。

接收方还会创建其当前协调集的快照，并清除该集合本身。快照将保留到节点发送“reconcildiff”消息为止。

reqbisec

Permalink: reqbisec

reqbisec 消息用于表示集合协调已失败，并且需要额外的草图来查找集合差异。

它有一个空的有效负载。

收到“reqbisec”消息后，节点使用“sketch”消息对其进行响应，该消息包含相应协调集快照的子集的草图（在处理当前轮的“reqreconcil”消息时存储）（范围 [0..(2^31)] 中的值）。

reconcildiff

Permalink: reconcildiff

reconcildiff 消息用于广播在发送方集合协调期间发现丢失的交易。

数据类型 名称 描述
uint8 success 指示消息的发送方是否成功解码集合差异。
uint32[] ask_shortids 发送方没有的短 ID。

收到 success=1 的“reconcildiff”消息后，节点会发送“invtx”消息，用于请求 32 位 ID（第一个向量）请求的交易，其中包含其 128 位截断 ID（父交易在其依赖项之前出现），并且可以通过“gettx”消息请求其没有的已广播交易（第二个向量）。 否则，如果 success=0，接收方应通过 reqbisec 请求二分（如果第一次发生故障）。 如果第二次发生故障，接收方应通过“invtx”消息广播协调集中的交易，但不包括发送方广播的交易。

消息的发送方和接收方都会清除相应协调集的 快照。

发送方还应发送自己的“invtx”消息以及 reconcildiff 消息，以广播接收方丢失的交易。

invtx

Permalink: invtx

invtx 消息用于广播交易（既随 reconcildiff 消息一起发送，又作为对 reconcildiff 消息的响应）。它是“inv”（由于它具有 256 位元素而无法使用）的截断 ID 类似物。

数据类型 名称 描述
uint128[] inv_truncids 发送方认为接收方没有的交易的截断 ID。

收到“invtx”消息后，节点会请求其不拥有的已广播交易。 消息的发送方会清除相应协调集的 快照。

gettx

Permalink: gettx

gettx 消息用于按 128 位截断 ID 请求交易。它是“getdata”的截断 ID 类似物。

数据类型 名称 描述
uint128[] ask_truncids 发送方希望获得完整交易数据的交易的截断 ID。

收到“gettx”消息后，节点会为请求的交易发送“tx”消息。

本地状态

Permalink: 本地状态

此 BIP 建议使用有状态协议，并且需要在每个节点存储几个变量才能正常运行。

协调集

Permalink: 协调集

每个节点为每个对等节点存储 128 位截断 ID 的集合，表示根据常规泛洪协议本应发送的交易。 当收到这些交易时，会将传入的交易添加到集合中（如果它们满足对等节点设置的最低费用等策略）。 在传输初始草图后，会将协调集移动到相应的集合快照。

协调集快照

Permalink: 协调集快照

在传输初始草图（发送或接收 reconcildiff 消息）之后，每个节点都应存储当前协调集的快照，并清除该集合。 这对于在协调轮次期间使二分更加稳定非常重要（二分应应用于快照）。 快照还用于有效地查找通过短 ID 请求的交易。 快照在协调轮次结束时（发送或接收 reconcildiff 消息）被清除。

q系数

Permalink: q系数

应存储 q 值以进行有效的差异估计。它在对等节点之间共享，并在每次协调后更改。 q 系数表示集合的差异：集合越接近，最佳 q 越低。 在将来的实现中，q 可能会因不同的对等节点而异或变为静态。

向后兼容性

Permalink: 向后兼容性

在此更改之后，旧客户端仍保持完全兼容和可互操作。

由于交易广播协调仅用于协商支持的对等节点，因此不实现此协议的客户端在使用现有协议进行此更改后仍保持完全兼容。

原理

Permalink: 原理

为什么使用 PinSketch 进行集合协调？

Permalink: 为什么使用 PinSketch 进行集合协调？

据我们所知，PinSketch 比 IBLT 具有更高的带宽效率，尤其是对于我们期望运行的集合中的小差异。 PinSketch 与 CPISync 的带宽效率一样高，但 PinSketch 具有二次解码复杂度，而 CPISync 具有三次解码复杂度。这使得 PinSketch 快得多。

为什么使用 32 位短交易 ID？

Permalink: 为什么使用 32 位短交易 ID？

为了在实践中使用 Minisketch，应缩短交易 ID（理想情况下，每个元素不超过 64 位）。 每个交易的小位数还可以节省额外的带宽并使草图上的操作更快。 根据我们的估计，32 位提供了非对抗模型中的低冲突率（通过使用每个链接的独立盐来实现）。

为什么使用 128 位短 ID？

Permalink: 为什么使用 128 位短 ID？

为了避免由网络延迟引起的问题，我们的协议需要额外一轮广播未加盐的交易 ID。Erlay 基于此工作的协议也需要广播未加盐的交易 ID 以进行泛洪。 这两种措施都允许消除跨对等节点交易广播的重复数据。 但是，使用完整的 256 位 ID 来唯一标识交易似乎有点过头了。 128 是 2 的最高幂，可以在对抗模型中提供足够好的抗冲突性，并且可以轻松节省与这些广播相关的大部分带宽。

为什么使用二分而不是扩展草图？


与扩展草图不同，二分法不需要在高阶草图上操作。
这允许避免由二次解码复杂度引起的高计算成本。

### 实现

[永久链接：实现](https://github.com/naumenkogs/bips/blob/bip-reconcil/bip-reconcil.mediawiki#implementation)

待办事项

### 致谢

[永久链接：致谢](https://github.com/naumenkogs/bips/blob/bip-reconcil/bip-reconcil.mediawiki#acknowledgments)

这个提案的大部分是在与 Gregory Maxwell、Sasha Fedorova 和 Ivan Beschastnikh 一起设计 Erlay 时完成的。
我们要感谢 Ben Woosley 对这个想法的高级描述所做的贡献。

### 版权

[永久链接：版权](https://github.com/naumenkogs/bips/blob/bip-reconcil/bip-reconcil.mediawiki#copyright)

本文档置于公共领域。

>- 原文链接： [github.com/naumenkogs/bi...](https://github.com/naumenkogs/bips/blob/bip-reconcil/bip-reconcil.mediawiki)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～
点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
naumenkogs
naumenkogs
江湖只有他的大名，没有他的介绍。

naumenkogs

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！