密码学学习笔记——aSCV

潘业达 安比技术社区 2020-06-29 13:39

本文作者潘业达，安比技术社区小伙伴，来自富士通研发中心。

回顾


密码学学习笔记——Sigma Protocol


最近 Ethereum 分片分的如火如荼，stateless blockchain 是以太坊分片可能需要走的必经之路，而 vector commitment 是一种实现 stateless blockchain 很好的方式。最近看了一篇 vector commitment 的文章，试着跟大家分享一下。原文链接如下： 

Aggregatable Subvector Commitments for Stateless Cryptocurrencies



https://eprint.iacr.org/2020/527.pdf

1. Vector commitment & stateless blockchain

1.1

Image

Cryptographic accumulator

在介绍Vector commitment之前，让我们先讨论一个名为accumulator 的密码学原语，它生成一个绑定在一组元素上的长度很短的承诺，以及对该组中任何元素是否属于该集合的一个长度很短的证明。这些证明可以根据承诺公开核实。最简单的累加器是Merkle树。

Image

图Figure1: 8个叶子结点的Merkle tree。

Merkle树中非叶子节点的值是子节点连接的哈希值。例如，在上图中，A1=hash（k | | k1）、B1=hash（A1 | | A2）和root=hash（B1 | | B2）。

Merke tree 的根结点 是绑定在叶子结点集合上的短承诺。我们说一个结点 k 到根结点到根结点  路径上所有结点的有序结合叫做 path(k) , path(k) 上结点到兄弟结点构成的有序集合我们称之为 sib(k) 。sib(k) 就是 k 存在于这棵Merkle tree的证明。在图1中，绿色的方块构成了 sib(k) ，证明过程就是根据 sib(k) 从 k 重新计算到根节点 ，看是 。

1.2

Image

Vector commitment

Vector commitment  （VC）是一个和accumulator很相似的密码学原语。它提供了和accumulator类似的功能，但是VC除了能够证明一个元素在一个集合中，而且能够证明该元素在集合中的位置。更准确地说，VC是一个和位置绑定的承诺，它能够用一个长度很短的证明（vector长度sub-linear）在vector的任意位子打开一个唯一的值。Sub-vector commitment 指的是那些可以在一个短证明中打开多个位置的VC。一种典型的VC或者accumulator的使用方式是为远端数据库构造一种可验证数据结构（authenticated data structure aka. ADS）。一般情况下，一个VC需要包含六个算法：

  1. ：给定一个安全参数 λ 以及vector的长度 n ，输出公共参数 pp 。
  2. ：给定向量 ，输出 的承诺 C 。
  3. ：给定位置 ，值以及 ，输出证明 。
  4. : 给定承诺 ，置 ，值 以及对应的证明 ,输出为接受或者拒绝。
  5. ：给定更新信息 以及承诺 ，输出新的承诺 。
  6. ：给定更新信息 以及证明 ，输出新的证明 。

1.3

Image

Stateless blockchain

Stateless blockchain 的一般形式是矿工只保存所有账户的VC，一个用户发送一笔交易的时候需要将其账户余额以及账户余额的证明提供给矿工，矿工根据本地的承诺验证余额正确性，执行交易、更新承诺，相关用户在收到了新的区块后更新证明。

Image

图Figure 2: Stateless blockchain 一般过程

2. 预备知识

我们现在来说说aSCV吧。首先它由一下几个特点：

1）产生n个长度为 O(1) 的证明的时间复杂度为 ；
2）更新证明的时间复杂度为 O(1) ；
3）将b个证明聚合成 O(1) 大小的subvector证明的时间复杂度为 ；
4）证明密钥的长度为 O (n) ，验证密钥的长度为 O(1) ，更新密钥的长度为 O(1) ；

2.1

Image

一些定义

：一个安全参数；
,：两个素数阶的群；
：在群 ,上的pairing e: ;：一个未知阶的群；
：单位的n次原根，即 ，这是为了保证 互不相同;
：p是素数。 ; ; ：是一个大小为n的向量，

2.2

Image

Lagrange 多项式插值法

给定n对 ，我们能够找到一个唯一的阶数小于n的多项式 ，任取 使得 。
使用 Lagrange插值法 可以在  的时间求出这个多项式，其实现方式如下：
观察发现 。
它这篇文章中将 换成了 。

2.3

Image

KZG 多项式承诺

这里介绍一个基于n-S(B)DH假设的多项式承诺——KZG 。它能对一个多项式生成一个固定长度的承诺，并且每一个元素的证明的大小以及验证的时间复杂度都是常数。KZG需要一个的公共参数 ，其中 是一个trapdoor（这个需要使用trustred-setup 来生成）。

  • Committing.

    表示一个阶为d的多项式，其中 ，其各次项的系数为 。一个对于多项式的KZG承诺是一个群中的元素： 。生成 C 的时间复杂度为 。

  • Proving One Evaluation.

    这里我们需要证明的事情是 。KZG利用了剩余多项式理论： 。那么对于 的证明也是一个群元素： 。生成这个证明的时间复杂度为 。
    对于 的验证过程为判断下列等式是否成立：

  • Proving Multiple Evaluations.

    这里我们要证明，集合 I 中元素对应的值为 。这里使用的方式是对于这 对关系生成一个证明而不是对 中元素一个个生成证明。

    证明者首先计算 ，其时间复杂度是 。然后计算 ，其时间复杂度为 ，得到关系： 。生成的证明为 。

    其验证过程为：验证者首先根据 生成 ，然后利用插值法计算出 使得 ，有 。

    （ps：因为 的阶小于 的阶 ，并且有 其中 ，所以可以通过Lagrange插值法算出 ）。

    然后计算 以及 ，验证等式 是否成立。


3. 如何构建一个aSVC的协议

3.1

Image

aSVC的API