Vector Commitments with Efficient Proofs学习笔记

1. 背景知识

Markulf Kohlweiss和Alfredo Rial 2012年文章《Vector Commitments with Efficient Proofs》和相应的ppt《Vector Commitments with Efficient Proofs》
初始motivation为 2010年《Privacy-Preserving Smart Metering》提到的智能计量的隐私保护。在该智能计量场景中，存在：计量meter方$M$M，服务提供provider方$P$P，*机构government agency $A$A，以及用户user $U$U。

• $M$M 测量 $U$U 的消费（如水或电），将测得的值前面后发送给$U$U【基本格式为： a consumption value, a consumption time interval and a signature on both the consumption and the time.】。
  
• $P$P 将已签名的收费政策发送给$U$U【含：the price per unit of consumption for each time interval.】。
  
• $A$A 将另一份的已签名的收费政策发送给$U$U【该收费政策可对每个用户都不一样，签名时包含了特定用户$U$U的身份信息】。
  
• 在计算费用的时候，用户$U$U会从$A$A和$P$P给的收费政策中选择每个时间段更低的收费标准，从而形成用户$U$U专属的收费中间表：
  
• 目标：
  用户$U$U需要证明其缴纳的费用是正确计算的，但是同时要保护其专属的收费中间表不对外公布。该证明过程包含一个OR statement where $U$U proves that, for each interval, the employed rate was signed either by $P$P or by $A$A。传统的OR argument生成的proof size grows with the number of tariff policies involved。

本文采用vector commitment机制来commit to a vector $(x_1,\cdots,x_n)$(x1​,⋯,xn​) and open it to $x_i(i\in [1,n])$xi​(i∈[1,n]) with cost independent of $n$n。

$U$U commit to the vector of其专属的收费中间表，并提供相应的证明，如：for each vector component, $U$U proves that it was signed either by $P$P or by $A$A。
为了证明费用计算的正确性，$U$U 需证明其采用的rate was committed in the correct vector component。

2. 基于accumulator构建的vector commitment

---

可参见博客 Vector Commitments and their Applications学习笔记 中第2.2节内容“基于RSA的Vector Commitment实现”。

---

3. 基于SDH assumption的vector commitment

将[kzg10]2010年论文《Polynomial Commitments*》【精简版本为《Constant-Size Commitments to Polynomials and Their Applications*》】中实现的polynomial commitment【基于SDH assumption】扩展为vector commitment。扩展方式为，对于vector $(x_1,\cdots,x_n)$(x1​,⋯,xn​)，基于Lagrange插值$\{(1,x_1),\cdots,(n,x_n)\}${(1,x1​),⋯,(n,xn​)}构建polynomial，对position $i$i进行polynomial evaluation返回的值即为$x_i$xi​。
对[kzg10]论文polynomial commitment的代码实现可参见博客：

• Polynomial Commitments代码实现【1】——scipr-lab/poly-commit（含不同曲线性能对比）
• Polynomial Commitments代码实现【2】——lovesh/kzg-poly-commit

polynomial commitment转vector commitment的详细思路可参见2015年论文《Composable & Modular Anonymous Credentials:Definitions and Practical Constructions》中第三节内容：【博客 vector commitment 中有提及。】

4. 基于DHE assumption的vector commitment

2010年Benoît Libert和Moti Yung 的论文《Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs》中基于DHE assumption构建的vector commitment。

详情参见博客 Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs 学习笔记

5. 基于CDH assumption的vector commitment

Catalano和Fiore 2011年论文《Concise vector commitments and their applications to zero-knowledge elementary databases》【又名《Vector Commitments and their Applications》】中提出了基于CDH assumption的vector commitment实现。详情参见博客 Vector Commitments and their Applications学习笔记 中第2.1节内容“基于CDH的Vector Commitment实现”。