Semi-aggregation of BIP 340 signatures ``` BIP 340 签名的半聚合

<pre> Title: BIP 340 签名的一半聚合 Status: 实验性的 </pre>

== 简介 ==

=== 摘要 ===

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

=== 版权 ===

本文档采用 3-clause BSD 许可。

=== 动机 ===

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

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

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

一个例子是闪电网络路由 Gossip 协议，该协议 [https://github.com/lightning/bolts/blob/2e8f2095a36afb9de38da0f3f0051c7dc16dfc36/07-routing-gossip.md 截止撰写本文时] 涉及包含 ECDSA 签名的消息。 如果签名方案更改为 BIP 340，则一半聚合可以减少 Gossip 数据的总量。 节点可以组装一批消息，并将各个消息的签名一半聚合成批处理的单个签名，而不是发送单个 Gossip 消息。

一半聚合的另一个应用是在比特币共识协议中。 特别是，它已在[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html Graftroot 提案]的上下文中进行了讨论。 一半聚合将允许 Graftroot 花费与最佳情况 Taproot 花费一样有效，方法是聚合“替代脚本”的签名和满足该脚本的签名。 此外，一半聚合提高了提议的比特币脚本操作码的效率，这些操作码验证多个签名，例如 [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/019926.html OP_EVICT]。 我们还可以想象添加一个比特币脚本操作码来验证一半聚合签名，从而实现更有效的非交互式多重签名和阈值签名。

一半聚合也可以应用于比特币交易的输入中的签名，这一过程称为跨输入签名聚合 (CISA)。 此 [https://github.com/ElementsProject/cross-input-aggregation/blob/master/savings.org 将平均交易的大小减少] 20.6%，权重减少 7.6%。 使用一半聚合的一个已知缺点是，某些适配器签名协议的使用 [https://github.com/ElementsProject/cross-input-aggregation#half-aggregation-and-adaptor-signatures 可能不兼容]。 通常，CISA 提出使用交互式“完全”签名聚合而不是非交互式一半聚合，因为创建有效交易已经需要合作，并且完全签名聚合效率更高。 然而，一半聚合和完全聚合之间的复杂性差异非常大，以至于基于一半聚合的 CISA 是一种合理的方法。

对 Bitcoin 共识最具侵入性的应用将是全区块签名聚合。 它指的是区块生产者尽可能多地聚合交易签名的过程。 在最佳情况下，完整区块将只有一个一半聚合签名。 虽然从效率的角度来看这很有吸引力，但全区块聚合需要更多的研究（尤其需要特别注意处理 [https://github.com/ElementsProject/cross-input-aggregation#half-aggregation-and-reorgs 重组]）。

=== 设计 ===

Schnorr 签名的一半聚合的想法是在全区块签名聚合的背景下 [Tadge Dryja 在 2017 年在 Bitcoin 邮件列表中提出 https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014272.html]。 该方案存在一个安全缺陷，该缺陷 [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014306.html 被注意到] 并且 [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014308.html 在此之后不久被 Russell O'Connor 和 Andrew Poelstra 修复]。 2021 年，[https://eprint.iacr.org/2021/350 Chalkias, Garillot, Kondi 和 Nikolaenko] 在随机预言模型 (ROM) 中发布了一项安全证明，该证明将一半聚合的安全性降低到 Schnorr 签名的安全性。 [https://eprint.iacr.org/2022/222.pdf Chen 和 Zhao] 在第二年能够产生 ROM 和代数群模型中的严格证明。 此外，他们提出了一种优雅的增量聚合方法，该方法已用于本文档中。

• 增量聚合允许将额外的 BIP 340 签名非交互式地聚合到现有的“一半聚合”签名中。
• u 个 BIP 340 输入签名的“一半聚合”签名序列化为 （u+1）⋅32 字节数组 r₁ || ... || r_u || bytes(s)，其中 r_i 是来自输入签名 i 的 32 字节数组，而 s 是标量聚合（有关详细信息，请参见下文）。
• 本文档 不 指定多个聚合签名的聚合（尚未）。这是可能的，但需要更改聚合签名的编码。由于无法撤消 s 值的聚合，因此在验证此类聚合签名时，随机数生成器需要与验证各个聚合签名时相同。因此，聚合签名需要对一棵树进行编码，该树揭示了各个签名是如何聚合的以及如何重新聚合生成的聚合签名。
• 第一个随机数生成器 z₀ 固定为常量 1，这加快了验证速度，因为 z₀⋅R₀ = R₀。 [https://eprint.iacr.org/2022/222.pdf Chen 和 Zhao] 已经建议并证明了这种优化的安全性。
• 可以聚合的签名最大数目为 2¹⁶ - 1。具有最大值是为了防止整数溢出。此特定值是一个保守的选择，将来可能会提高（TODO）。

== 描述 ==

=== 规范 ===

该规范以 [https://github.com/hacspec/hacspec hacspec] 编写，这是一种用于正式规范的语言，也是 rust 的子集。 它可以在 [[hacspec-halfagg/src/halfagg.rs|hacspec-halfagg directory]] 中找到。 请注意，该规范依赖于 hacspec 库和 [https://github.com/hacspec/hacspec/pull/244 BIP 340 的 hacspec 实现]。

=== 测试向量 ===

初步测试向量在 [[hacspec-halfagg/tests/tests.rs|tests.rs]] 中提供。 可以通过在 [[hacspec-halfagg|hacspec-halfagg directory]] 中运行 <code>cargo test</code> 来使用测试向量执行规范 (<code>cargo</code> 是 [https://doc.rust-lang.org/stable/cargo/ rust 包管理器])。

=== 伪代码 ===

以下伪代码 不是 规范，仅旨在补充实际的 hacspec [[#specification|specification]]。

==== 符号 ====

使用以下约定，常量定义为 [https://www.secg.org/sec2-v2.pdf secp256k1]。我们注意到，将此规范调整为其他椭圆曲线并非易事，并且可能导致不安全的方案<ref>在其他缺陷中，将规范与阶数不接近 nonce 派生函数范围大小的曲线一起使用是不安全的。</ref>。

• 小写变量表示整数或字节数组。 常量 p 指的是字段大小，0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F。 常量 n 指的是曲线阶数，0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141。
• 大写变量指的是在整数模 p 上具有方程 y² = x³ + 7 的曲线上点。 is_infinite(P) 返回 P 是否为无穷远点。 x(P) 和 y(P) 是范围 0..p-1 中的整数，指的是点 P 的 X 和 Y 坐标（假设它不是无穷远）。 常量 G 指的是基点，对于该基点，x(G) = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 并且 y(G) = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8。 点的加法指的是通常的 [https://en.wikipedia.org/wiki/Elliptic_curve#The_group_law 椭圆曲线群运算]。 ** 整数和点的 [https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication 乘法 (⋅)] 指的是群运算的重复应用。
• 函数和运算： || 指的是字节数组的连接。 函数 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 字节数组，返回最高有效字节优先编码为 x 的 256 位无符号整数。 函数 has_even_y(P)，其中 P 是一个点，其中 not is_infinite(P)，返回 y(P) mod 2 = 0。 函数 lift_x(x)，其中 x 是一个 256 位无符号整数，返回点 P，其中 x(P) = x<ref> 给定范围 0..p-1 中的候选 X 坐标 x，存在恰好两个或零个有效的 Y 坐标。如果不存在有效的 Y 坐标，则 x 也不是有效的 X 坐标，即不存在点 P，其中 x(P) = x。给定候选坐标 x 的有效 Y 坐标是 c = x³ + 7 mod p 的平方根，它们可以计算为 y = ±c^(p+1)/4 mod p （参见 [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus 二次余数]），如果存在，可以通过平方并与 c 进行比较来检查。</ref> 并且 has_even_y(P)，或者如果 x 大于 p-1 或者不存在这样的点，则失败。函数 lift_x(x) 等效于以下伪代码： 如果 x ≥ p，则失败。 令 c = x³ + 7 mod p。 令 y = c^(p+1)/4 mod p。 如果 c ≠ y² mod p，则失败。 * 如果 y mod 2 = 0，则返回唯一一个点 P，使得 x(P) = x 并且 y(P) = y，否则返回 y(P) = p-y。 函数 hash_tag(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。 （但是，逆命题不成立：给定合适有效的元组，可以构造一个输入到“Aggregate”的数组，该数组包含无效的元组，但是 “VerifyAggregate” 将接受 “Aggregate” 返回的聚合签名。如果不需要这样，应先单独验证输入的元组，然后再将其传递给“Aggregate”。）

输入：

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

'''Aggregate(pms<sub>0..u-1</sub>)'''':

• 令 aggsig = bytes(0)
• 令 pm_aggd 为空数组
• 返回 IncAggregate(aggsig, pm_aggd, pms<sub>0..u-1</sub>); 如果失败则返回失败。

==== IncAggregate ====

“IncAggregate” 接受一个聚合签名，一个对应于聚合签名的公钥和消息元组数组，以及另一个公钥、消息和签名三元组数组。 它将额外的三元组数组聚合到现有的聚合签名中，并返回生成的新聚合签名。 换句话说，如果 VerifyAggregate(aggsig, pm_aggd) 通过并且 pms_to_agg 中的每个三元组 (p, m, s) 都是有效的（即 BIP 340 中定义的 Verify(p, m, s) 返回 true），则返回的聚合签名以及 pm_aggd 和 pms_to_agg 的 (p, m) 元组数组通过 VerifyAggregate。 (但是，逆命题不成立：给定一个合适有效的聚合签名和合适有效的元组，可以构造 “IncAggregate” 的输入，其中包含无效的聚合签名或无效的元组，但是 “VerifyAggregate” 将接受 “IncAggregate” 返回的聚合签名。如果不需要这样，应先单独验证输入的三元组和输入的聚合签名，然后再将它们传递给 “IncAggregate”。)

输入：

• aggsig：一个字节数组
• pm_aggd<sub>0..v-1</sub>：一个由 v 个元组组成的数组，其中每个元组的第一个元素是一个 32 字节的公钥，第二个元素是一个 32 字节的消息
• pms_to_agg<sub>0..u-1</sub>：一个由 u 个三元组组成的数组，其中每个三元组的第一个元素是一个 32 字节的公钥，第二个元素是一个 32 字节的消息，第三个元素是一个 64 字节的 BIP 340 签名

'''IncAggregate(aggsig, pm_aggd<sub>0..v-1</sub>, pms_to_agg<sub>0..u-1</sub>)'''':

• 如果 v + u ≥ 2<sup>16</sup>，则失败
• 如果 len(aggsig) ≠ 32 * (v + 1)，则失败
• 对于 i = 0 .. v-1： 令 (pk<sub>i</sub>, m<sub>i</sub>) = pm_aggd<sub>i</sub> 令 r<sub>i</sub> = aggsig[i⋅32:(i+1)⋅32]
• 对于 i = v .. v+u-1： 令 (pk<sub>i</sub>, m<sub>i</sub>, sig<sub>i</sub>) = pms_to_agg<sub>i-v</sub> 令 r<sub>i</sub> = sig<sub>i</sub>[0:32] 令 s<sub>i</sub> = int(sig<sub>i</sub>[32:64]) 如果 i = 0： * 令 z<sub>i</sub> = 1 * 否则： 令 z<sub>i</sub> = int(hash<sub>HalfAgg/randomizer</sub>(r<sub>0</sub> || pk<sub>0</sub> || m<sub>0</sub> || ... || r<sub>i</sub> || pk<sub>i</sub> || m<sub>i</sub>)) mod n
• 令 s = int(aggsig[(v⋅32:(v+1)⋅32]) + z<sub>v</sub>⋅s<sub>v</sub> + ... + z<sub>v+u-1</sub>⋅s<sub>v+u-1</sub> mod n
• 返回 r<sub>0</sub> || ... || r<sub>v+u-1</sub> || bytes(s)

==== 验证聚合 ====

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

输入：

• aggsig：一个字节数组
• pm_aggd<sub>0..u-1</sub>：一个由 u 个元组组成的数组，其中每个元组的第一个元素是一个 32 字节的公钥，第二个元素是一个 32 字节的消息

'''VerifyAggregate(aggsig, pm_aggd<sub>0..u-1</sub>)'''': 算法 VerifyAggregate(aggsig, pm_aggd<sub>0..u-1</sub>) 定义为：

• 如果 u ≥ 2<sup>16</sup>，则失败
• 如果 len(aggsig) ≠ 32 * (u + 1)，则失败
• 对于 i = 0 .. u-1： 令 (pk<sub>i</sub>, m<sub>i</sub>) = pm_aggd<sub>i</sub> 令 P<sub>i</sub> = lift_x(int(pk<sub>i</sub>)); 如果失败则返回失败 令 r<sub>i</sub> = aggsig[i⋅32:(i+1)⋅32] 令 R<sub>i</sub> = lift_x(int(r<sub>i</sub>)); 如果失败则返回失败 令 e<sub>i</sub> = int(hash<sub>BIP0340/challenge</sub>(bytes(r<sub>i</sub>) || pk<sub>i</sub> || m<sub>i</sub>)) mod n 如果 i = 0： * 令 z<sub>i</sub> = 1 * 否则： 令 z<sub>i</sub> = int(hash<sub>HalfAgg/randomizer</sub>(r<sub>0</sub> || pk<sub>0</sub> || m<sub>0</sub> || ... || r<sub>i</sub> || pk<sub>i</sub> || m<sub>i</sub>)) mod n
• 令 s = int(aggsig[u⋅32:(u+1)⋅32]); 如果 s ≥ n 则失败
• 如果 s⋅G ≠ z<sub>0</sub>⋅(R<sub>0</sub> + e<sub>0</sub>⋅P<sub>0</sub>) + ... + z<sub>u-1</sub>⋅(R<sub>u-1</sub> + e<sub>u-1</sub>⋅P<sub>u-1</sub>)，则失败
• 当且仅当在到达此点之前没有发生任何失败时，才返回成功。

验证算法类似于 [https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#batch-verification BIP340 批量验证]。与 BIP340 中一样，使用 [https://bitcoin.stackexchange.com/a/80702/109853 用于计算多个 EC 乘法之和的高效算法] 可以显着加快验证速度。

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