题目链接：Chaos Theory 1. 问题描述 Bob designed a new one time scheme, that’s based on the tried and true method of encrypt + sign. He combined ElGamal encryption with BLS signatures in a clever way, such that you use pairings to verify the encrypted message was not tampered with. Alice, then, figured out a way to reveal the plaintexts… Bob 设计了一个新的一次性方案，这是基于加密+签名的久经考验的方法。他用一个聪明的方法将ElGamal加密算法和BLS签名结合，使得你可以使用pairings来验证加密信息未被篡改。然后 Alice 发现了一个方法能够揭示出明文… Bob 把ElGamal加密算法和BLS签名结合起来，设计了一套新方案，但是Alice可以从中破解出被加密的数据。我们接下来要做的就是找到Alice获取加密原象的方法。 2. 代码原理分析 2.1 ElGamal加密算法 In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange.

题目链接：Supervillain 1. 问题描述 首先看一下问题描述： Bob has been designing a new optimized signature scheme for his L1 based on BLS signatures. Specifically, he wanted to be able to use the most efficient form of BLS signature aggregation, where you just add the signatures together rather than having to delinearize them. In order to do that, he designed a proof-of-possession scheme based on the B-KEA assumption he found in the the Sapling security analysis paper by Mary Maller.

题目链接：Gamma Ray 1. 问题描述 首先来看一下问题描述： Bob was deeply inspired by the Zcash design for private transactions and had some pretty cool ideas on how to adapt it for his requirements. He was also inspired by the Mina design for the lightest blockchain and wanted to combine the two. In order to achieve that, Bob used the MNT7653 cycle of curves to enable efficient infinite recursion, and used elliptic curve public keys to authorize spends.

论文链接：sangira 在Nova 论文中定义了一种基于Committed Relaxed R1CS的折叠方案，用来实现零知识的IVC（incrementally-verifiable computation）。这边方案可以用于折叠R1CS结构的instance-witness来做证明，参考文章。 Sangira是基于Plonk的电路结构 Plonkish 的变种实现的折叠方案。 1. Plonk 和 Relaxed Plonk 1.1 Plonk 电路结构 Plonk 的电路的结构为： $C_{\mathcal{Q},i}(a, b, c) = (q_L)_i a_i + (q_R)_i b_i + (q_O)_i c_i + (q_M)_i a_i b_i + (q_C)_i$ 其中$(q_L)_i, (q_R)_i, (q_O)_i, (q_M)_i, (q_C)_i$ 表示第i行的 selector 向量，我们用$\mathcal{Q} = (\mathbf{q}_L, \mathbf{q}_R, \mathbf{q}_O, \mathbf{q}_M, \mathbf{q}_C )$ 来表示所有的selector取值。 其中 $a_i, b_i, c_i$ 为第 i 行的左边，右边和输出值，这三行$(\mathbf{a}, \mathbf{b}, \mathbf{c})$ 都是 instance-witness $(\mathbf{X}, \mathbf{W})$（假设plonk电路的前n行为public input，后面s行的是witness）。 另外我们用 $\mathcal{S}$ 表示 copy constraint。

论文链接：Nove （第三章） 本文介绍一种折叠方案（folding scheme），Nova 协议中利用它的非交互性质和零知识性质去实现零知识的IVC（incrementally-verifiable computation）。 1. R1CS 和 Relaxed R1CS 1.1 R1CS Consider a finite field $\mathbb{F}$. Let the public parameters consists of size bounds $m, n, l \in \mathbb{N}$ where $m > l$. The R1CS structure consists of sparse matrices $A, B, C \in \mathbb{F}^{m \times m}$ with at most $n = \Omega(m)$ non-zero entries in each matrix. An instance $x \in \mathbb{F}^l$ consists of public inputs and outputs and is satisfied by a witness $W \in \mathbb{F}^{m - l - 1}$ if $(A \cdot Z) \circ (B \cdot Z) = (C \cdot Z)$, where $Z = (W, x, 1)$

论文地址：Aggregatable Subvector Commitments aSVC(aggregatable subvector commitment) 是向量承诺（vector commitment）的一种，它可以用来将多个证明聚合成一个小的 subvector 证明。由于aSVC非常低的通信量和计算量，以及它的聚合验证能力，可以使用它来做 payments-only stateless cryptocurrenc。 1. 前提知识 aSVC也是基于KZG10实现的，KZG10的优势在于constant-sized，它的证明的大小和证明的验证时间都是常数规模的。 1.1 KZG10 步骤（单点） 首先，证明者（prover）和验证者（verifier）获得一组安全的 SRS 公开参数 $(g^{\tau^i})_{i \in [0, n]}$ 证明者（prover）使用 SRS 参数生成 C(x) 的承诺（commitment）, 并公开承诺值 $C = \prod_{i=0}^d (g^{\tau^i})^{c_i} = g^{\phi(\tau)}$ 验证者（verifier）生成随机数 $a$ 并发送给证明者（prover） 证明者（prover）计算多项式 C(x) 在$a$ 处的取值 $y = C(a)$，并生成证明 $\pi$，将 $(y, \pi)$ 发送给验证者（verifier）。 $\frac{C(\tau)-y}{\tau-a} = q(\tau), \pi = [q(\tau)]_1$， 验证者（verifier）执行验证 $e(C-[y]_1, [1]_2) = e(\pi, [\tau]_2 - [a]_2)$ 1.2 KZG10 步骤（多点） 首先，证明者（prover）和验证者（verifier）获得一组安全的 SRS 公开参数 $(g^{\tau^i})_{i \in [0, n]}$ 证明者（prover）使用 SRS 参数生成 C(x) 的承诺（commitment）, 并公开承诺值 $C = \prod_{i=0}^d (g^{\tau^i})^{c_i} = g^{\phi(\tau)}$ 验证者（verifier）生成一组挑战数集合 $I$ 并发送给证明者（prover） 证明者（prover）计算多项式： $a(x) = \prod_{i \in I} (x-i)$ $r(x) = \sum_{i=1}^m y_i \tau_i(x)$，其中 $y_i = \phi(i), i \in l$, $r(i) = y_i$ 证明者（prover）继续计算证明 $q(x) = \frac{\phi(x) - r(x)}{a(x)}$, $\pi = [q(\tau)]_1$ 证明者（prover）发送 ${ \pi, r(x)}$ 给验证者（verifier） 验证者（verifier）执行验证： $e(C-[r(\tau)]_1, [1]_2) = e(\pi, [a(\tau)]_2)$ 2.

1 多项式求和验证 假设在有限域 $\mathbb{F}$ 上定义一个有 l 项输入的多项式 f，当变量的取值都为0或者1时，共有$2^l$ 组输入的取值。若有一个求和的就算，即将这$2^l$ 组取值带入多项式 f 计算，并将结果相加： $H = \sum_{b_1,b_2,…,b_l\in{0,1}}f(b_1,b_2,…,b_l)$， 若要直接完成这个求和计算，就需要先算出多项式 f 在这 $2^l$ 组输入上的结果，然后再进行求和计算。这里需要的时间复杂度为 l 的指数时间 $O(2^l)$。但是当计算条件有限无法进行这个复杂度计算的时候该怎么办呢？这里引入一个委托计算的概念，verifier不需要进行计算，计算被委托给了prover去完成，verifier只需要通过很低的消耗去验证计算结果的正确性就可以了。这里所说的委托证明可以通过 Sumcheck 来完成的，在Sumcheck协议中，verifier 的验证时间复杂度仅为 O(dl)（d为多项式 f 的阶数）。 我们先来看一个最简单的例子， 一元多项式 假设多项式 f 只有一个输入项，即 f(x)，那么 $H = \sum_{b_1\in{0,1}}f(b_1) = f(0)+f(1)$， 这里只有两项， verifier 可以直接带入多项式 f 计算 $f(0),f(1)$，再验证 $H = f(0)+f(1)$ 。 二元多项式 当 f 被扩展到有两项输入变量时，即$f(x_1,x_2)$，那么 $H = \sum_{b_1,b_2\in{0,1}}f(b_1,b_2)$， 我们可以将它变换为 $H=\sum_{b_1 \in {0,1}}(\sum_{b_2 \in {0,1}}f(b_1,b_2)) = \sum_{b_1 \in {0,1}}f_1(b_1)$，其中 $f_1(x) = \sum_{b_2 \in {0,1}}f(x,b_2)$。 也就是说如果我们知道多项式 $f_1(x)$，我们就可以用验证一元多项式的方式去验证H了。 那么把验证变换成两步： （1）验证 $H=f_1(0)+f_1(1)$了； （2）验证多项式 $f_1(x)$。

论文地址：https://eprint.iacr.org/2023/033.pdf 1. 托普利茨矩阵和循环矩阵 1.1 托普利茨矩阵 In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant. A Toeplitz matrix is not necessarily square. 在线性代数中，以 Otto Toeplitz 命名的 Toeplitz 矩阵或对角线常数矩阵是一个矩阵，其中从左到右的每个下降对角线都是常数。Toeplitz 矩阵不一定是正方形的。 1.2 循环矩阵 In linear algebra, a circulant matrix is a square matrix in which all rows are composed of the same elements and each row is rotated one element to the right relative to the preceding row.

本文为hackerhouse 期间阅读论文的学习笔记，如有笔误，欢迎指正。 Caulk 是一种向量承诺方案，可以零知识的证明一个或多个值都属于一个向量，并且不泄露这一个或者多个值的位置。Caulk可以用来做Membership证明，也可以作为Lookup Argument，并且比先前的方案在生成证明的效率上更有优势。 Caulk+ 是Caulk的优化版本方案，它用了一个被称为「polynomial divisibility check」的方法来替换原本的子协议，以提升Caulk生成证明的效率，使得证明复杂度仅与子集的大小有关，而与原向量的大小无关。 1. 前提知识 1.1 Commitment Schemes 承诺方案（Commitment schemes）是一种很重要的密码学原语。它允许承诺的一方公开一个被称为承诺（commitment）的值，承诺的值与某个消息绑定（binding），同时又不泄露消息的具体内容（hiding）。 向量承诺（Vector Commitments） 向量承诺（Vector Commitments，简称 VCs）允许通过某种方式去承诺一组有顺序的值（或者称为向量），并且在后面可以在某个特定的位置打开（open）它。 多项式承诺（Polynomial Commitments） 多项式承诺（Polynomial Commitments）允许去承诺一个多项式，并且验证者可以用它来验证承诺多项式所声明的值的计算。可以用来验证多项式在某个点处的取值。 KZG10 做向量承诺 KZG10 承诺方案原本是一种多项式承诺方案，它同样也可以用来做向量承诺，并证明某个值（$c_i$）等于被承诺的向量在某个特定位置（$i$）的值。 假设有一个向量 $\vec{c_i}$，长度为N。我们可以用它生成一个多项式 $C(x) = \sum_{i}^N c_i \cdot \lambda_i(x)$，其中 $\lambda_i(x)$ 是拉格朗日插值多项式，满足$C(\omega^i) = c_i$。 ${ \omega^i }$ 是一组单位根 $\mathbb{H} = {1, \omega, …, \omega^{N-1} }$，满足 $\omega^N = 1$。当且仅当证明者（prover）知道向量 $\vec{c_i}$的所有值，才能构造多项式 $C(x)$ 。那么就可以通过对多项式 $C(x)$ 做多项式承诺并验证，来代替直接对向量 $\vec{c_i}$的承诺和验证。 Caulk, Caulk+（以及很多其他的Lookup Argument ，如Baloo，CQ，CQLin等）就是基于 KZG10 设计的方案，所以在讨论 Caulk, Caulk+ 之前，先来看看 KZG10方案的步骤。

在Plonk协议中，多项式承诺是非常重要的一个环节，协议中的多项式承诺实现了多个多项式在两个点上的open。但是在实际的应用场景下，有可能会出现需要多个多项式在多个不同点处open的场景，如果能通过改进多项式承诺协议来使得plonk支持多个多项式在不同的子集点处的open。 若 $ z \in S $，那么 $Z_S(x) = \prod_{z \in S} (X-z)$。 假设有一个数据集$T = {z_1, z_2, …, z_t}$，并且它的子集$S_1,S_2,…,S_k \subset T$。如果有k个多项式$f_1(x), f_2(x),…,f_k(x)$，它们的承诺分别为$cm_1, cm_2,…,cm_k$，要分别在$S_1,S_2,…,S_k $上open。 首先若要使用KZG10对一个多项式做验证的话，那么 prover计算多项式 $$ h(x) = \frac{f_i(x) - r_i(x)}{Z_{S_i}(x)} $$ 其中$r_i(x)$ 是一个$|s_i|$ 阶的多项式，且满足再$f_i(x) = r_i(x), x \in S_i$。 再使用srs参数计算证明$W =[h(x)]_1 = g^{h(x)}$，发送给verifier。 Verifier 拿到证明W后进行验证，这里需要两次pairing运算。 $$ e(cm_i - [r_i(x)]_1, g_2) = e(W,g_2 ^ {k}) $$ 其中 $k = Z_{S_i}(x)$ 如果要一次性得对这k个多项式进行验证，只需要引入一个随机数 verifier 生成一个随机数$\gamma$，并发送给prover prover 拿着随机数将k组多项式的证明计算 $$ h_i(x) = \frac{f_i(x) - r_i(x)}{Z_{S_i}(x)} $$