主分支cross-input-aggregation/half-aggregation.mediawiki的交叉输入聚合

跳转到内容

BlockstreamResearch/ cross-input-aggregation Public

• 通知 你必须登录才能更改通知设置
• Fork\ 10
• Star\ 65

折叠文件树

文件

master

搜索此仓库

/

half-aggregation.mediawiki

复制路径

BlameMore file actions

BlameMore file actions

最近提交

jonasnick

halfagg: mention multi/threshold sig opcode use case

2024年2月22日

ce8c2f9 · 2024年2月22日

历史

历史

打开提交详情

查看此文件的提交历史。

185 行 (147 loc) · 17 KB

/

half-aggregation.mediawiki

顶部

文件元数据和控件

• 预览

• 代码

• Blame

185 行 (147 loc) · 17 KB

Raw

复制原始文件

下载原始文件

轮廓

编辑和原始操作

  Title: BIP 340 签名的一半聚合
  Status: 实验性的

简介

永久链接：简介

摘要

永久链接：摘要

本文档描述了 BIP 340 签名的一半聚合。 一半聚合是一种非交互式过程，用于将一组签名聚合为单个聚合签名。 生成的聚合签名的大小大约是原始签名组合大小的一半。

版权

永久链接：版权

本文档基于 3-clause BSD 许可。

动机

永久链接：动机

如果存在需要验证多个签名的验证者，则一半聚合适用。 签名可以压缩为单个聚合签名并发送给验证者，而不是将单个签名发送给验证者。 如果验证者可以成功验证聚合签名，则验证者可以确保单个签名可以通过验证。

一半聚合的目的是减小发送给验证者的数据的大小。 虽然 n 个 BIP 340 签名是 64*n 字节，但相同签名的一半聚合是 32*n + 32 个字节。 一半聚合的过程非常简单：它是输入签名、公钥和消息的纯函数。 它是非交互式的，不 需要其他方的合作，包括签名者或验证者。

在各种情况下，BIP-340 签名的一半聚合都很有用。 为了使本节简短并避免快速过时，我们专注于列出示例应用程序，并将特定于应用程序的权衡的详细讨论推迟到其他地方。

一个例子是闪电网络路由 gossip 协议，该协议截至撰写本文时 涉及包含 ECDSA 签名的消息。 如果签名方案更改为 BIP 340，则一半聚合可以减少 gossip 数据的总量。 节点可以组装一批消息，并将各个消息的签名一半聚合到批处理的单个签名中，而不是发送单个 gossip 消息。

一半聚合的另一个应用是在比特币共识协议中。 特别是，它已在 Graftroot 提案 的上下文中进行了讨论。 通过聚合替身脚本的签名和满足此脚本的签名，一半聚合将允许 Graftroot 花费与最佳情况 Taproot 花费一样有效。 此外，一半聚合提高了提议的比特币脚本操作码的效率，这些操作码验证多个签名，例如 OP_EVICT。 我们还可以想象添加一个比特币脚本操作码来验证一半聚合签名，从而实现更高效的非交互式多重签名和阈值签名。

一半聚合也可以应用于比特币交易输入中的签名，这个过程称为跨输入签名聚合 (CISA)。 这 将平均交易的大小减少了 20.6%，权重减少了 7.6%。 使用一半聚合的一个众所周知的缺点是，某些适配器签名协议的使用 可能不兼容。 通常，CISA 建议使用交互式完整签名聚合而不是非交互式一半聚合，因为创建有效交易已经需要合作，并且完整签名聚合效率更高。 但是，一半聚合和完整聚合之间的复杂性差异非常显着，因此基于一半聚合的 CISA 是一种合理的方法。

对比特币共识最具侵入性的应用将是全区块签名聚合。 它指的是区块生产者尽可能多地聚合交易签名的过程。 在最佳情况下，整个区块将只有一个一半聚合签名。 虽然从效率的角度来看这很有吸引力，但全区块聚合需要更多的研究（特别是，要特别注意处理 reorgs）。

设计

永久链接：设计

Schnorr 签名一半聚合的想法是在全区块签名聚合的背景下，由 Tadge Dryja 于 2017 年在 比特币邮件列表中提出的。 该方案存在一个安全漏洞，该漏洞在不久之后由 Russell O'Connor 和 Andrew Poelstra 注意到 并进行了 修复。 2021 年，Chalkias、Garillot、Kondi 和 Nikolaenko 在随机预言机模型 (ROM) 中发布了一个安全证明，该证明将一半聚合的安全性降低到 Schnorr 签名的安全性。 Chen 和 Zhao 在第二年能够在 ROM 和代数组模型中生成一个严格的证明。 此外，他们提出了一种优雅的增量聚合方法，本文档中使用了该方法。

• 增量聚合允许将额外的 BIP 340 签名非交互式地聚合到现有的一半聚合签名中。
• u BIP 340 输入签名的一半聚合签名序列化为 (u+1)⋅32 字节数组 r1 || ... || ru || bytes(s)，其中 ri 是来自输入签名 i 的 32 字节数组，s 是标量聚合（有关详细信息，请参见下文）。
• 本文档（尚未）指定多个聚合签名的聚合。 这是可能的，但需要更改聚合签名的编码。 由于无法撤消 s 值的聚合，因此在验证此类聚合签名时，随机数需要与验证各个聚合签名时相同。 因此，聚合签名需要编码一棵树，该树揭示了如何聚合各个签名以及如何重新聚合生成的聚合签名。
• 第一个随机数 z0 固定为常量 1，这加快了验证速度，因为 z0⋅R0 = R0。 Chen 和 Zhao 提出了这种优化方法并证明了其安全性。
• 可以聚合的最大签名为 216 - 1。 具有最大值是为了防止整数溢出。 这个特定值是一个保守的选择，将来可能会提高（TODO）。

描述

永久链接：描述

规范

永久链接：规范

该规范是用 hacspec 编写的，hacspec 是一种用于形式规范的语言，也是 rust 的一个子集。 它可以在 hacspec-halfagg 目录 中找到。 请注意，该规范依赖于 hacspec 库和 BIP 340 的 hacspec 实现。

测试向量

永久链接：测试向量

初步的测试向量在 tests.rs 中提供。 可以使用测试向量执行该规范，方法是在 hacspec-halfagg 目录 中运行 cargo test （cargo 是 rust 包管理器）。

伪代码

永久链接：伪代码

以下伪代码_不是_规范，仅旨在补充实际的 hacspec 规范。

符号

永久链接：符号

使用以下约定，常量定义为 secp256k1。 我们注意到，将此规范调整为其他椭圆曲线并非易事，并且可能导致不安全的方案 [1]。

• 小写变量表示整数或字节数组。
  • 常量 p 指的是字段大小，0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F。
  • 常量 n 指的是曲线阶数，0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141。
• 大写变量指的是曲线上方程 y2 = x3 + 7 (mod p) 的点。
  • is_infinite(P) 返回 P 是否为无穷远点。
  • x(P) 和 y(P) 是范围 0..p-1 中的整数，指的是点 P 的 X 和 Y 坐标（假设它不是无穷远点）。
  • 常量 G 指的是基点，其中 x(G) = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 并且 y(G) = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8。
  • 点的加法指的是通常的 椭圆曲线群运算。
  • 整数和点的乘法 (⋅) 指的是群运算的重复应用。
• 函数和操作：
  • || 指的是字节数组串联。
  • 函数 x[i:j]，其中 x 是一个字节数组，i, j ≥ 0，返回一个 (j - i) 字节数组，其中包含 x 的第 i 个字节（包括）到第 j 个字节（不包括）的副本。
  • 函数 bytes(x)，其中 x 是一个整数，返回 x 的 32 字节编码，最高有效字节在前。
  • 函数 bytes(P)，其中 P 是一个点，返回 bytes(x(P))。
  • 函数 len(x)，其中 x 是一个字节数组，返回数组的长度。
  • 函数 int(x)，其中 x 是一个 32 字节数组，返回 256 位无符号整数，其最高有效字节在前的编码为 x。
  • 函数 has_even_y(P)，其中 P 是一个点，其中 not is_infinite(P)，返回 y(P) mod 2 = 0。
  • 函数 lift_x(x)，其中 x 是一个 256 位无符号整数，返回点 P，其中 x(P) = x [2] 并且 has_even_y(P)，如果 x 大于 p-1 或者不存在这样的点，则失败。 函数 lift_x(x) 等效于以下伪代码：
  • 如果 x ≥ p，则失败。
  • 令 c = x3 + 7 mod p。
  • 令 y = c(p+1)/4 mod p。
  • 如果 c ≠ y2 mod p，则失败。
  • 返回唯一的点 P，使得 x(P) = x 并且 y(P) = y (如果 y mod 2 = 0) 或 y(P) = p-y (否则)。
  • 函数 hashtag(x)，其中 tag 是 UTF-8 编码的标签名称，x 是一个字节数组，返回 32 字节哈希 SHA256(SHA256(tag) || SHA256(tag) || x)。
• 其他：
  • 元组通过列出括号内的元素并用逗号分隔来书写。 例如，(2, 3, 1) 是一个元组。

聚合

永久链接：聚合

Aggregate 接受公钥、消息和签名三元组的数组，并返回一个聚合签名。 如果每个三元组 (p, m, s) 都有效（即，BIP 340 中定义的 Verify(p, m, s) 返回 true），则返回的聚合签名和 (p, m) 元组数组将通过 VerifyAggregate。 （但是，逆不成立：给定合适 Valid 三元组，可以构造 Aggregate 的输入数组，该数组包含无效的三元组，但 VerifyAggregate 将接受 Aggregate 返回的聚合签名。 如果不希望这样做，应在将输入三元组传递给 Aggregate 之前单独验证它们。）

输入：

• pms0..u-1: 一个 u 三元组的数组，其中每个三元组的第一个元素是 32 字节的公钥，第二个元素是 32 字节的消息，第三个元素是 64 字节的 BIP 340 签名

Aggregate(pms0..u-1):

• 令 aggsig = bytes(0)
• 令 pm_aggd 为一个空数组
• 返回 IncAggregate(aggsig, pm_aggd, pms0..u-1); 如果失败则失败。

增量聚合

永久链接：增量聚合

IncAggregate 接受一个聚合签名，一个与聚合签名相对应的公钥和消息元组数组，以及一个额外的公钥、消息和签名三元组数组。 它将额外的三元组数组聚合到现有的聚合签名中，并返回生成的新聚合签名。 换句话说，如果 VerifyAggregate(aggsig, pm_aggd) 通过，并且 pms_to_agg 中的每个三元组 (p, m, s) 都有效（即，BIP 340 中定义的 Verify(p, m, s) 返回 true），那么返回的聚合签名以及 pm_aggd 的 (p, m) 元组和 pms_to_agg 的数组将通过 VerifyAggregate。 （但是，逆不成立：给定一个合适的有效聚合签名和合适 Valid 三元组，可以构造 IncAggregate 的输入，该输入包含无效的聚合签名或无效的三元组，但 VerifyAggregate 将接受 IncAggregate 返回的聚合签名。 如果不希望这样做，则应在将输入三元组和输入聚合签名传递给 IncAggregate 之前单独验证它们。）

输入：

• aggsig : 一个字节数组
• pm_aggd0..v-1: 一个 v 元组的数组，其中每个元组的第一个元素是 32 字节的公钥，第二个元素是 32 字节的消息
• pms_to_agg0..u-1: 一个 u 三元组的数组，其中每个三元组的第一个元素是 32 字节的公钥，第二个元素是 32 字节的消息，第三个元素是 64 字节的 BIP 340 签名

IncAggregate(aggsig, pm_aggd0..v-1, pms_to_agg0..u-1):

• 如果 v + u ≥ 216，则失败
• 如果 len(aggsig) ≠ 32 * (v + 1)，则失败
• 对于 i = 0 .. v-1:
  • 令 (pki, mi) = pm_aggdi
  • 令 ri = aggsig[i⋅32:(i+1)⋅32]
• 对于 i = v .. v+u-1:
  • 令 (pki, mi, sigi) = pms_to_aggi-v
  • 令 ri = sigi[0:32]
  • 令 si = int(sigi[32:64])
  • 如果 i = 0:
  • 令 zi = 1
  • 否则:
  • 令 zi = int(hashHalfAgg/randomizer(r0 || pk0 || m0 || ... || ri || pki || mi)) mod n
• 令 s = int(aggsig[(v⋅32:(v+1)⋅32]) + zv⋅sv + ... + zv+u-1⋅sv+u-1 mod n
• 返回 r0 || ... || rv+u-1 || bytes(s)

验证聚合

永久链接：验证聚合

VerifyAggregate 针对公钥和消息元组数组验证给定的聚合签名。

输入：

• aggsig : 一个字节数组
• pm_aggd0..u-1: 一个 u 元组的数组，其中每个元组的第一个元素是 32 字节的公钥，第二个元素是 32 字节的消息

VerifyAggregate(aggsig, pm_aggd0..u-1): 算法 VerifyAggregate(aggsig, pm_aggd0..u-1) 定义为：

• 如果 u ≥ 216，则失败
• 如果 len(aggsig) ≠ 32 * (u + 1)，则失败
• 对于 i = 0 .. u-1:
  • 令 (pki, mi) = pm_aggdi
  • 令 Pi = lift_x(int(pki)); 如果失败则失败
  • 令 ri = aggsig[i⋅32:(i+1)⋅32]
  • 令 Ri = lift_x(int(ri)); 如果失败则失败
  • 令 ei = int(hashBIP0340/challenge(bytes(ri) || pki || mi)) mod n
  • 如果 i = 0:
  • 令 zi = 1
  • 否则:
  • 令 zi = int(hashHalfAgg/randomizer(r0 || pk0 || m0 || ... || ri || pki || mi)) mod n
• 令 s = int(aggsig[u⋅32:(u+1)⋅32]); 如果 s ≥ n 则失败
• 如果 s⋅G ≠ z0⋅(R0 + e0⋅P0) + ... + zu-1⋅(Ru-1 + eu-1⋅Pu-1)，则失败
• 仅当在到达此点之前没有发生任何故障时，才返回成功。

验证算法与 BIP340 批量验证 相似。 与 BIP340 中一样，使用 用于计算多个 EC 乘积之和的有效算法 可以大大加快验证速度。

• 原文链接： github.com/ElementsProje...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～