密码学累加器：第一部分

照片由 Gayatri Malhotra 拍摄，来源于 Unsplash

本文介绍了密码累加器的基本概念及其基于未知阶RSA群的构建。我决定在阅读了这篇 论文 后撰写这篇文章。如果你想深入了解，这篇论文非常值得一读。

密码累加器是对一组元素的短期 绑定 承诺，并允许对集合中任一元素进行短期成员证明和/或对不在集合中的元素进行非成员证明。这些证明，也称为证人（证人证明元素已被添加到累加器中），可以与承诺相比进行验证。它们通常用作远程数据库的通信高效认证数据结构，通过单个元素及其证明可以快速检索并有效验证数据库的完整性。

累加器可以分为 静态 和 动态。与静态变体不同，动态累加器允许在不依赖已累加集大小的情况下添加/删除元素。如果一个动态累加器支持成员证明和非成员证明，则称之为 通用。

Merkle树也是一个 累加器 的例子，它是对一组的绑定承诺。成员证明和非成员证明的大小与集合的规模呈对数关系。此外，Merkle树是 向量承诺，它们是位置绑定承诺，即向量中的每个位置都与一个唯一值绑定。

基于RSA的 动态累加器 首次在 [CL02] 中引入，应用于高效撤销匿名凭证。[ LLX07] 提出了 通用累加器 的定义以及在通过添加/删除更新累加器时高效更新成员/非成员证人的算法。

基于RSA的累加器基本构建

假设一个RSA群，其模数为 N，随机生成器为 g。让 S 为要累加的整数集。Hprime 为哈希函数，将整数哈希为唯一的奇质数。Sp 为从哈希 S 中元素得到的质数集合。令 p_s 为 Sp 中所有质数的乘积。那么累加器的值为 A = g^(p_s) mod N，这是一个单一的RSA群元素。这个值可以当作对集合 S 的承诺传递。对于 S 中的任意元素 x，令 p_x 为 Sp 中相应的元素，使得

p_x = Hprime(x) x 的成员证明 或证人 wx，验证与承诺 A 相关的累加集合包含 x，由以下公式给出：

wx = g^(p_s/p_x) mod N 可以使用证人 wx 验证 x 的成员资格，相对于承诺 A，如下所示：

wx^p_x mod N = (g^(p_s/p_x))^p_x mod N = g^p_s mod N = A

要求累加值为质数是为了高效生成非成员证明而不需要任何陷门信息。陷门信息是RSA群的阶，即 N = p*q 中 (p-1)*(q-1)。

不属于集合 S 的 y 的非成员证明可以如下生成：

1. 计算 Bezout 系数 a,b，使得 a*p_y + b*p_s = 1。这样的系数存在，因为 p_y 和 p_s 是互质的。
2. y 的非成员证人 u_y 为对 (g^a, b)。
3. 为了证明 y 不属于累加集合，通过 u_y = (d, b) 进行检查，

(d^p_y)*(A^b) = (g^(a*p_y))*(g^(b*p_s))

= g^(a*p_y+b*p_s) = g

// RSA 累加器
type rsaAccumulator struct {
    g *big.Int // 群的生成元
    N *big.Int // RSA 模数
    val *big.Int // 累加器的值
}

// 集合类型
type Set = map[int]bool

type MemWitness = big.Int

type NonMemWitness struct {
    d *big.Int
    b *big.Int
}

// Add 将 x 添加到 A，并返回带有成员证书的更新累加器
func Add(A *rsaAccumulator, S Set, x int) (*rsaAccumulator, *MemWitness, error) {
    if present, ok := S[x]; ok && present {
        return A, nil, errors.New("添加错误：%v, 已存在\\n", x)
    }
    wx := &MemWitness{new(big.Int).Set(A.val)}
    S[x] = true
    A.val = new(big.Int).Exp(A.val, Hprime(x), A.N)
    return A, wx, nil
}

// Del 从 A 中删除 x，并返回更新的累加器和非成员证书
func Del(A *rsaAccumulator, S Set, x int) (*rsaAccumulator, *NonMemWitness, error) {
    if present, ok := S[x]; !ok || !present {
        return A, nil, errors.New("删除错误： %v, 不在集合中\\n", x)
    }
    delete(S, x)
    // 返回所有质数的乘积，Hprime(x)，针对 S 中所有 x
    xX := productOfPrimes(S)
    A.val = new(big.Int).Exp(A.g, xX, A.N)
    a, b := Bezout(Hprime(x), xX)
    d := new(big.Int).Exp(A.g, a, A.N)
    // 非成员证人
    ux := &NonMemWitness{d, b}
    return A, ux, nil
}

以上是一个在 go 中实现函数 Add 和 Del 更新累加器状态并生成证人的示例。如果证人被存储，在每次更新（添加/删除）时需要更新它们。更新成员/非成员证人以适应添加/删除元素的高效算法如 [ LLX07] (第4.2节)中所提议的。

例如，如果元素 x 被添加到累加器 A，则当前所有 y != x 在 S 中的成员证人为 wy。更新后的新累加器值和证人为 A_new 和 wy_new 为

A_new = A^(p_x) mod N

wy_new = wy^(p_x) mod N 使得 wy_new^p_y mod N = (wy^p_y)^(p_x) mod N

= A^(p_x) mod N = A_new

累加器的批处理和聚合技术

本节简要描述了 批处理 和 聚合 技术，这些技术由 论文 提供（第4节）。这项工作旨在使累加器可以用于实际应用。

批处理 是指对 n 项目应用一次操作，而不是对每个项目逐次应用操作。将 n 项结合在一起，而不是一一添加的例子就是批处理。

聚合 是指将 n 项组合为一个单独的项目。聚合的一个例子是将 n 个成员证人合并为一个证人，以验证所有 n 项的成员资格。

由于 Wes18 的最新工作，以下函数将在上述批处理和聚合技术中作为黑盒使用：

这些函数的伪代码可以在 论文 图1中找到。

1. NI-PoE (非交互式指数证明)： 给定 u, x 和 w，使得 u^x = w, NI-PoE 生成一个简洁的证明，可用于验证 u^x = w，而无需计算 u^x。
2. NI-PoKE2 ( 非交互式指数知识证明)： 给定 u, x 和 w，使得 u^x = w, NI-PoKE2 生成一个简洁的证明，

可用于验证证明者知道 x，使得 u^x = w，而不向验证者透露 x。

一些其他辅助函数将被使用：

1. ShamirTrick: 给定群元素 g 的 x 次和 y 次根，其中 x 和 y 互质，它返回 xy 次根的 A。

ShamirTrick(x,y, g^(1/x), g^(1/y)) = g^(1/(x*y))

2. RootFactor: 给定 y=g^x 及 x = x1*x2…xn 的分解，返回所有 xi 次根的 y 即 y^(1/x1), y^(1/x2)…y^(1/xn)。该算法的运行时间为 O(nlogn)。该算法可用于一次生成集合 S 的所有成员证人。

累加器更新的批处理

BatchAdd: 一次性将多个元素 {x1, x2, … , xn} 添加到累加器 A，而不是逐个添加。这种效率的提升是由于只需进行一次群的指数运算，且只需 O(n) 次乘法，而不是 O(n) 次群的指数运算。生成和分发简洁的证明，使用 NI-PoE 以验证累加器更新是正确的。

x_p_batched = Hprime(x1)*Hprime(x2)…*Hprime(xn)

A_new = A^(x_p_batched)

NI-PoE(x_p_batched, A, A_new) : 确保累加器更新正确的简洁证明

BatchDel: 从累加器 A 删除元素 {x1, x2, …, xn} 不是那么简单。一种低效的方式是从头创建不包含已删除元素的累加器。如果我们有要删除的元素的成员证人 {(x1, wx1), (x2, wx2),…(xn,wxn)}，可以稍微改善操作：

1. 删除 x1，更新后的累加器值为 A_new = wx1
2. 更新所有其他证人。
3. 对其余元素重复步骤1。

给定证人的更高效的删除方式是通过反复使用 ShamirTrick 来计算 A^(1/x_p_batched)，其中

x_p_batched = Hprime(x1)*Hprime(x2)…*Hprime(xn) 我们生成一个通过 NI-PoE 产生的有效更新简洁证明，即，

NI-PoE(x_p_batched, A_new, A)。

聚合成员证人

给定元素及其成员证人 {(x1, wx1), (x2, wx2),…(xn,wxn)}，可以生成聚合证人 wx_p_batched，针对

x_p_batched = Hprime(x1)*Hprime(x2)…*Hprime(xn)，如果你拥有整个累加器集 S 或者证人 wx1, wx2, … wxn。在后一种情况下，只需 A^(1/x_p_batched)，可以使用在 BatchDel 中提到的 ShamirTrick 计算。前者的情况是琐碎的，可以通过计算 g^(x_p_others) 来完成，其中

x_p_other = Hprime(y1)*Hprime(y2)*…Hprime(ym)

对于 S 中但不包含 {x1, x2…xn} 的所有 yi。

批量非成员证人

可以通过以下方式为元素 {x1,x2,…xn} 创建单个非成员证人：

1. 计算 s_p = Hprime(y1)*Hprime(y2)*…Hprime(ym)，针对 S 中所有 yi。
2. 计算 x_p_batched = Hprime(x1)*Hprime(x2)…*Hprime(xn)。
3. 计算 a,b = Bezout(x_p_batched, s_p)。
4. 计算 v = A^b, d = g^a。
5. 生成 proofD = NI-PoKE2(b, A, v) 和

proofG = NI-PoE(x_p_batched, d, g*(v^(-1))。

6. 非成员证人为 {d,v, proofD, proofG}。

如果你注意到，上述过程与生成单个非成员证明非常相似，直到步骤3。步骤4、5、6 对于批处理效率提升至关重要。我们本可以保持相同的过程，仅发送 {d, b} 作为证人，但 b 的大小将与 x_p_batched 的大小相同。因此，与分别发送 n 个证明相比，没有显著的收益。

总结

本文简要描述了基于RSA的累加器及其批处理和聚合技术，以摊销累加器操作的成本。

下一篇关于同一主题的文章将介绍如何在区块链背景下利用累加器。

参考文献

1. 适用于IOPs和无状态区块链的累加器批处理技术 [ 链接 ]
2. 具有高效非成员证明的通用累加器 [ 链接 ]
3. 高效可验证延迟函数 [ 链接 ]

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