跳到正文
Financial Context Wiki

密码学累加器

一份以验证为重点的密码学累加器指南，涵盖 RSA 与基于哈希的设计、成员与非成员见证、动态更新、区块链用途及运维风险。

更新于

仅供教育用途，不构成投资建议或密码学实现建议。累加器证明所认证的是相对于某一项承诺的声明，而不是底层数据、共识状态或数据可用性本身。

直接答案

密码学累加器用一个短值对集合做出承诺，并让验证者通过简洁的见证，核验某个元素是否属于所承诺的集合。有些方案还能证明非成员关系。验证者需要累加器值、元素、见证以及方案的公共参数，但不需要集合中的其他所有元素。

集合变化后必须重建的累加器称为静态累加器；能够在添加或删除元素时高效更新累加器与见证的称为动态累加器；同时支持成员证明和非成员证明的称为通用累加器。这些标签描述的是彼此独立的能力，动态方案并不会自动成为通用方案。

区块链可以对交易、未花费输出、账户、验证者或撤销记录做出承诺。较小的承诺可以减少部分参与者持有的状态，但系统仍须分发底层数据和当前见证、认证更新、处理链重组，并规定谁有权更改集合。

工作原理

  1. 精确定义集合。 定义规范的元素编码、重复项处理方式、适用时的排序规则、域分离以及承诺的确切版本。针对一种编码或状态根的证明，对另一种编码或状态根不作任何保证。

  2. 运行方案的设置过程。 基于哈希的累加器可能只使用公开的哈希参数。RSA 累加器使用未知阶群，通常由 RSA 模数 N 构造；安全性要求未获授权的一方无法利用其因数分解。其他方案可能使用配对、类群、格或额外公共参数，并各有不同的信任假设。

  3. 将元素映射到代数结构中。 在简化的 RSA 构造中，每个元素 x_i 都以确定性方式映射为互不相同的素数代表 p_i。以 g 为底，累加器为：

    A = g^(p_1 * p_2 * ... * p_n) mod N

  4. 创建成员见证。 对于以 p_i 表示的元素，从指数中略去它对应的因子：

    w_i = g^(product of p_j for all j != i) mod N

  5. 对照确切的累加器验证。 验证者检查输入是否采用规范形式，并计算：

    w_i^(p_i) mod N = A

    在方案的安全性假设下，要让集合之外的元素满足该等式，应当在计算上不可行。但这个等式并不能证明元素本身真实或已获授权。

  6. 分别处理更新和非成员关系。 动态方案规定添加和删除如何改变 A，以及如何刷新受影响的见证。通用方案另行提供非成员见证和验证算法。实现必须拒绝过期见证，以及绑定到其他状态的更新。

  7. 按照实际成本比较基于哈希的结构。 从广义上说，Merkle 树也是基于哈希的累加器：它的根很短，但成员证明包含路径上的相邻哈希，因此其大小随叶子数量呈对数增长。RSA 类方案可以提供大小恒定的单个见证，但证明生成、见证维护、设置和计算各有不同成本。

计算示例

  • Merkle 证明的大小。 一棵拥有 1,048,576 = 2^20 个叶子的平衡二叉 Merkle 树，需要 20 个相邻哈希来构成一条包含路径。若哈希为 32 字节，则在计入叶子数据、位置位和序列化开销之前，证明大小为 20 * 32 = 640 bytes。根仍为 32 字节。
  • 大小恒定不等于工作量恒定。 在简化的 RSA 构造中，集合增大时，A 和单个 w_i 仍各为一个群元素。然而，乘积指数、素数代表生成、批量更新以及刷新后见证的分发，仍可能需要大量计算或辅助数据。
  • UTXO 累加器改变了谁存储什么。 紧凑状态节点可以持有未花费输出的累加器，并且只有在收到输出及其当前成员证明时才验证一笔支出。其他参与者仍需保留足够的状态来生成这些证明；更新还必须删除已花费输出并添加新创建的输出。
  • 撤销沿用相同的边界。 凭证持有者可以证明某个标识符仍在有效成员累加器中，也可以用通用设计证明它不在撤销集合中。证明认证的是发行者所承诺的集合，而不是发行者采用了公平或正确的撤销政策。

风险

  • 使用含糊或非规范的元素编码，使同一个逻辑项目能够映射为不同值。
  • 错误地将元素映射为素数代表，或未采用方案要求的碰撞控制措施。
  • 信任其因数分解可能已被设置方或攻击者掌握的 RSA 模数。
  • 未核验记录、参与者假设和参数绑定，就认定多方设置仪式是安全的。
  • 允许管理员在没有经过认证的迁移规则时替换公共参数或累加器版本。
  • 对照过期、尚未最终确定或由攻击者选定的累加器值验证见证。
  • 采用来自错误区块、分叉、时期或集合版本的添加、删除或见证更新。
  • 误以为成员见证也能证明元素的有效性、所有权、授权或经济价值。
  • 误以为短承诺能让底层集合变得可用或可恢复。
  • 丢失构造当前见证所需的数据或服务，导致有效状态无法使用。
  • 在应用暗中依赖不存在性证明时，省略非成员支持。
  • 将 Merkle 路径、RSA 见证、多项式开启和有效性证明混为可互换的对象。
  • 忽视删除成本、见证刷新流量、证明生成延迟或拒绝服务输入。
  • 未将证明绑定到协议、链、合约、状态根、域和序列化版本。
  • 在没有独立测试向量的情况下，依赖单个未经审计的实现或自定义算术。
  • 误以为经典 RSA、配对或离散对数安全性在面对具有密码学意义的量子计算机时依然成立。

常见误解

  • 累加器包含集合的压缩副本。 它是具有绑定性的承诺，而不是可逆的存档。
  • 每种累加器都能证明不存在性。 非成员关系必须采用为这种能力而设计并经过验证的方案。
  • 见证大小恒定意味着总成本恒定。 设置、证明生成、更新、存储和见证分发仍是彼此独立的成本。
  • 无状态意味着无人存储状态。 某些参与方必须保留或重建足够的数据，才能创建元素、更新和见证。
  • 有效证明意味着所承诺的项目是真实的。 它只是在特定假设下，将该项目与一项经过认证的承诺关联起来。
  • Merkle 树与 RSA 累加器具有相同的信任和性能特征。 它们都用于集合承诺，但采用不同的假设、证明大小、更新流程和失效模式。

相关主题

来源

导航

搜索知识库...