密码学学习笔记——aSCV

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

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

回顾

最近 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

Cryptographic accumulator

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

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

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

1.2

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需要包含六个算法：

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

1.3

Stateless blockchain

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

图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

一些定义

：一个安全参数；

,：两个素数阶的群；

：在群 ,上的pairing e: ;：一个未知阶的群；

：单位的n次原根，即，这是为了保证互不相同;

：p是素数。 ; ; ：是一个大小为n的向量，

2.2

Lagrange 多项式插值法

给定n对，我们能够找到一个唯一的阶数小于n的多项式，任取使得。

使用 Lagrange插值法可以在的时间求出这个多项式，其实现方式如下：

观察发现。

它这篇文章中将换成了。

2.3

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

aSVC的API

Figure 3: aSVC的api

手打太累了，截图看看吧。这里比上文提到的多了三个算法，一是 VerifyUPK 用来验证更新密钥的正确性，二是 EmptyCommit 用来验证承诺是否为空，三是 AggregateProofs 用来将多个证明聚合。

3.2

From KZG to aSVC

我们现在考虑一下如何利用KZG构建一个aSVC。KZG是一个多项式承诺，所以首先我们需要根据要承诺的向量构建多项式。首先假设对于向量使用Lagrange插值法得到多项式，使得。

其中。

在得到了多项式之后我对着aSVC的API来看看如何实现各个接口。

3.2.1

承诺 & 承诺更新

对于向量生成KZG对于的承诺：，其中是一个trapdoor。设，承诺可以通过在不用算出的情况下在的时间内算出。假设为加上，我们考虑更新后的多项式，使得。更新后的承诺，更新的时间复杂度为。

3.2.2

证明的生成和验证

对于单个元素的证明的生成、验证和KZG中对于在上的证明的生成、验证相同。对于的子集合 , 对于单个元素的证明的生成、验证和KZG中对于在上的证明的生成、验证相同。对于的子集合 , 的证明的生成和证明和KZG中对于子集合上的证明和验证相同。

到现在我们有了4个函数了，接下来得看看证明的更新和聚合了。

3.3

部分因式分解

我们重写Lagrange多项式： , where

我们对求导得到（这里论文写的是，j的范围是我觉得不对应给是）。现在我们可以重写Lagrange插值法的形式（这个时候我们只有个点，所以要讨论的是这个点所在的多项式，论文里写的是我觉得有点晕）。

当时，我们有，所以我们可以将分解成为： , where 。

计算的时间复杂度为，计算的时间复杂度为，计算所有的时间复杂度为。

3.3.1

聚合证明

我们需要将一个证明的集合聚合成一个固定大小的对于集合的证明。我们回忆一下对于的证明，其中，对于集合的集合，其中，，是通过Lagrange插值法计算出来的，使得。为了聚合证明，需要找到一系列系数使得，聚合的证明。我们重写 :

将个证明 , 聚合成一个证明，计算所有的需要域运算，计算需要进行乘运算。

3.3.2

更新证明

现在要讨论当值发生改变时，如何更新证明。这里分为两种情况：

1）；

2）。

回忆一下证明是的ZKG承诺，更新后的多项式变为：。我们分情况讨论：

case i=j : 我们来看看更新后的商多项式 q'(X) :

由上式可以看出，对于证明的更新需要一个对于的KZG承诺，其实这是对的KZG证明。我们重新看，为能够更新证明，更新密钥需要饱含，新的证明。

: 我们依然来看看更新后的商多项式 q'(X) :

由上式可以看出，对于证明的更新需要一个对于的KZG承诺，为了生成这个承诺，需要一些额外的信息（关于的信息）。我们可以看到，如果要更新证明同时需要更新密钥 , ，因此我们要从 ,恢复出。首先我们重写 where ，。由于是一个常数，我们只需要生成的KZG承诺。这里的主要想法是成为更新密钥的一部分。根据部分因式分解，可以计算出，最后可以得到。