BLS聚合重数问题

在 SBC Ethereum/ZK 工作坊上，与 Mary Maller、Dan Boneh 教授、Andrew He、Scott Wu、George (asn)、Carl、Dankrad、Pop 和许多其他人讨论的关于 BLS 聚合多重性问题的一些笔记。

BLS - 常用方案

首先，快速介绍一下 BLS 签名方案。BLS 是一种基于配对的优雅签名方案：

密钥

生成一个私钥

sk 和一个对应的公钥

pk=[sk]G1，其中

G1 是生成元。注意

sk 受

DLOG 难题保护。

签名

要对消息

M 进行签名，计算

sig=[sk]H(M)，其中

H 是一个哈希函数。

验证

要验证

sig，只需检查

e(H(m),pk)=e(sig,G1)。

聚合

给定两个签名和密钥，

pk1,sk1,sig1 和

pk2,sk2,sig2 且消息相同

M，注意

e(H(M),pk1+pk2)=e(sig1+sig2,G1)。因此，令

sigagg=sig1+sig2 且

pkagg=pk1+pk2。然后，验证聚合与验证针对

pkagg,sigagg 的签名相同：

e(H(m),pkagg)=e(sigagg,G1)。正确性遵循标准配对性质。

注意，这可以直接扩展到聚合 2 个以上的签名。

设置

注意：N = 4096，M = 16，t = 4 秒（目前）？

目前，有

N 个验证者对一个区块进行 BLS 签名，并将他们的签名提交给

M 个选定的聚合器。然后，这些

M 方将他们收到的所有签名聚合成一个聚合 BLS 签名，然后重复聚合所有这些聚合签名，并将总聚合发布到链上，以证明区块的有效性。理想情况下，每个

N 验证者都希望他们的签名出现在区块上（为了安全，甚至可能在未来获得经济奖励）。因此，

N 验证者通常会将他们的签名提交给许多

M 个聚合器，希望至少其中一个聚合器能够诚实地将其包含在完整的聚合中。

此外，我们希望在分布式网络环境中，在两个 t 秒的回合内完成此操作，第一回合，验证者将签名发送给聚合器，第二回合，生成完整聚合。引入更多回合或联网是可能的，但不在本文档的讨论范围之内。

对于第一层聚合，单个聚合器只需监听来自多个验证者的签名，上述 章节 中描述的聚合设置运作良好。聚合器可以通过提交一个

N 位字符串来允许其他人验证聚合，其中如果索引为

i 的验证者的签名包含在聚合中，则第

i 位为 ON，并且验证者可以使用该位字符串来组装匹配的

pkagg。因此，传递此聚合的成本非常低，只需要传递

N 位和一个

sigagg（由

⌈log2⁡(|field size

|)⌉ 位组成）。

但是，当我们尝试在下一层聚合签名时，此通信成本会增加。由于所有聚合器都将独立组装聚合，因此它们的聚合之间将存在重叠的签名，因此仅传递位字符串是不够的。

作为一个具体的例子，对于

N=3 和

M=2，一个聚合器看到了来自第一个和第三个验证者的签名，而另一个聚合器看到了来自第一个和第二个验证者的签名，因此对应于其各个聚合的位字符串是

(1,0,1) 和

(1,1,0)。简单地遵循先前描述的 聚合方案，我们将最终得到

pkagg=2pk1+pk2+pk3 和

sigagg=2sig1+sig2+sig3。请注意，每个单独的

sig/

pk 的贡献不再受

1 限制，因此我们需要传递验证的完整系数（天真地需要

⌈log2⁡(|field size

|)⌉⋅N 位用于通信）。

简而言之，我们正在寻找一种支持聚合的签名方案，使得同一个密钥对可以多次贡献签名，但可以以最小的性能/网络开销进行验证。

因此，我们建议使用一种简单快速的辅助方案，该方案可以与 BLS 签名一起使用以支持这种结构。此外，我们证明了可以通过包装在 bulletproof 中来使该方案简洁。

建议的简单方案

请注意，来自每个密钥对的签名在最终聚合中最多可以重复

M 次（因为每个聚合器最多可以贡献一次）。对于

pkagg=v1pk1+v2pk2+⋯=<v,pk>，

vi∈[0,M]∀i。因此，向量

v 可以在

N⋅⌈log2⁡(M)⌉ 位中传递，这已经比以前的方法好得多。

Bulletproofing

首先，我们为解决一个非常具体的问题构建一个 bulletproof：给定一个 BLS 公钥向量

pk→，一个位字符串

b→ 和一个聚合公钥

pkagg，证明存在一些见证向量

v→ 使得

<v→,pk→>=pkagg 并且如果

bi=1， 那么

vi≠0。稍后，我们将展示此 bulletproof 足以满足我们的用例。

构造

输入：聚合公钥

pkagg、位字符串

b→、BLS 公钥向量

pk→。

见证：公钥的系数向量

pk→ 的系数向量

v→。

证明：

• <v→,pk→>=pkagg：这是一个内积参数，并且在 原始 bulletproof 论文 中直接表明可在

log2⁡N 轮内完成 =

2log2⁡N 个字段元素通信，其中

N =

v→ 的大小 = 验证者的数量。

• v→⋅v→−1=b→⟹v→⋅v→p−2=b→，其中

p 是域（质数）的阶。这约束了如果

bi=1，那么

vi≠0。

通过在链上包含此证明及其输入，我们能够在不包含

v→ 本身的情况下显示

pkagg 和

b→ 的有效性，然后可以使用它来验证来自

pkagg 的相应 BLS 签名。此 bulletproof 非常简洁，仅需

O(logN) 个字段元素进行通信和

O(N) 验证时间（在这种情况下，对于 N 的大小应该足够快）。因此，仅需

O(logN) 通信/区块大小开销，我们就解决了原始问题。一些粗略的计算表明，在

N=1000 左右时，这在通信方面比 上面的简单方案 更有效。（TODO：对传输的比特数进行精确计算，并确定何时比上面提到的更简单的解决方案更好）

但是请注意，我们没有约束

b→ 上的另一个方向，如果

vi≠0，那么

bi=1（即，即使聚合器实际上在其

pkagg 中包含了来自相应验证者的签名，它也可能已将

bi=0）。这可能不是必需的，因为它似乎没有创建新的攻击面。特别是，创建此证明的聚合器可能只是创建了一个备用聚合

sigagg/pkagg，排除了验证者，所以忽略这一点可能没有问题？（TODO 确认？）

Dankrad 的问题扩展

在提出此解决方案时，Dankrad 指出了此问题的扩展版本，其中拥有此方案的可递归验证版本可能很有用。此问题的详细信息对我来说还不完全清楚（TODO，请他详细说明？），但这似乎表明如下：在稍后的时间，你希望能够证明某个验证者已（或未）签署特定的历史区块，并在当前区块中拥有一个可以打开的单一承诺，以证明此多重证明。本质上，我们之前解决了一个两层树的问题，并在第二层解决该问题，但是 Dankrad 希望找到一个三层树的解决方案（同时适用于Layer2和第 3 层）。如果此扩展问题是首要任务，一种解决方法是在聚合到区块的层（即Layer2）使用 简单方案，然后在证明削减的层（第 3 层）使用 bulletproof 构造。

一个明显的解决方案是在 SNARK 中验证 bulletproof，或者使用另一个高效的 SNARK 递归证明系统，例如 Plonky 2 或 Nova，但这通常效率低下，并且安全证明需要做更多的工作。

进一步思考，我不清楚为什么我们不能在区块中维护这些（签名，位字符串）的某种滑动窗口 Merkle 树，然后使用 Merkle 证明 + BLS 验证来打开它们。（我可能遗漏了一些有关扩展的信息？）

asn 提到 Vitalik 的另一个相关问题/扩展：https://ethresear.ch/t/request-for-cryptographic-primitive-vector-commitment-for-elliptic-curve-points-with-algebraic-properties/9080

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