4 Various Papers 4.8 Sublinear Lattice ZKP for Arithmetic Circuits 4.10 Short Invertible Polynomial Ring Elements

4.9 A Non-PCP Approach to Succinct Quantum-Safe ZK

The high-level idea of [BLN+20] is twofold. On one hand, it upgrades the amortized linear-relation proof for Ajtai commitments from [BBC+18a] into a levelled SIS commitment, making the commitment object recursively compressing. On the other hand, it gives a lattice analogue of the Bulletproofs folding argument [BBB+18]. Concretely, we have:

•

levelled SIS commitments, with communication

$O\left(N^{1/(d+1)}\cdot\left(d^{3}\lambda\log^{2}N+d\lambda^{2}\right)\right)$

for $d$ levels, and hence $\mathsf{polylog}(N)$ communication on $d+1=\log N$ ;
•

a lattice analogue of the Bulletproofs folding argument [BBB+18], with smaller polylogarithmic proof size but much larger extraction slack in knowledge soundness.

$N$ is the number of committed secret values. Recall the note section 4.8 on [BBC+18a] that the one-level construction has $\tilde{O}(\sqrt{N})$ communication after balancing the number of commitments and the opening proof size after amortization. We begin by showing how [BLN+20] reduces the communication via a two-level commitment instantiation. As in the previous lattice argument note, we suppress the zero-knowledge layer: the commitment is hiding, and the proof is made zero-knowledge by Gaussian masking with rejection sampling in the Fiat-Shamir-with-aborts style.

Two-Level Commitment Map.

The levelling idea starts by committing to commitments. On message $\mathbf{S}\in\mathbb{Z}^{m_{1}m_{2}\times m_{3}}$ , commitment keys $\mathbf{A}_{1}\in\mathbb{Z}_{q_{1}}^{n\times nm_{1}}$ , $\mathbf{A}_{2}\in\mathbb{Z}_{q_{2}}^{n\times m_{2}}$ , and $q_{1}>q_{2}$ . The top commitment is

\mathbf{T}=\mathbf{A}_{1}\cdot\left(\left(\mathbf{I}_{m_{1}}\otimes\mathbf{A}_% {2}\right)\cdot\mathbf{S}\mod q_{2}\right)\mod{q_{1}}.

This is SIS-commitment-like at each level: the lower level compresses blocks of $\mathbf{S}$ , and the upper level compresses the lower-level commitments. At this point this is just the commitment map: an honest opening is a matrix $\mathbf{S}$ whose image under the above map is $\mathbf{T}$ , and $\mathbf{S}$ is short.

General Levelled Commitments.

For $d$ levels, let $N=\prod_{i\in[1,d+1]}m_{i}$ , $m_{0}=1$ , and $q_{1}>\cdots>q_{d}$ . The bottom matrix is $\mathbf{A}_{d}\in\mathbb{Z}_{q_{d}}^{n\times m_{d}}$ , and for $i<d$ , $\mathbf{A}_{i}\in\mathbb{Z}_{q_{i}}^{n\times nm_{i}}$ . Define $M_{i,j}=m_{i}\cdots m_{j}$ and $M_{i}=M_{1,i}$ , and define recursively

F_{i,j}(\mathbf{S})=\begin{cases}\mathbf{A}_{i}\mathbf{S}\mod q_{i},&i=j,\\ F_{i,j-1}\left(\left(\mathbf{I}_{M_{i,j-1}}\otimes\mathbf{A}_{j}\right)\cdot% \mathbf{S}\mod q_{j}\right),&i<j.\end{cases}

The statement is $\mathbf{T}\leftarrow F_{1,d}(\mathbf{S})$ , where $d$ is the number of levels.

Folding Operations.

Similar to the challenges in section 4.8, the challenges are matrices over the challenge set $\mathcal{C}$ the same as the one in section 4.8, with shape $\mathbf{C}_{1}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathcal{C}^{m_% {d+1}\times\lambda}$ , and $\mathbf{C}_{i}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathcal{C}^{m_% {i-1}\lambda\times\lambda}$ for $i\in[2,d]$ .

For a matrix $\mathbf{Z}$ whose rows are split into $m_{i}$ consecutive blocks $\mathbf{Z}_{1},\ldots,\mathbf{Z}_{m_{i}}$ of equal size, define the block transpose

\mathsf{BT}_{i}(\mathbf{Z})=\left[\mathbf{Z}_{1}\mid\ldots\mid\mathbf{Z}_{m_{i% }}\right].

We also use the recursive folding map $\mathsf{Fold}_{i}$ from [BLN+20]. The base case is

\mathsf{Fold}_{0}(\mathbf{U}_{1};\mathbf{C}_{1})=\mathbf{U}_{1}\mathbf{C}_{1}.

For $i>0$ , split the input tuple $(\mathbf{U}_{1},\ldots,\mathbf{U}_{M_{i}})$ into $m_{i}$ consecutive subtuples, such that for $j\in[1,m_{i}]$ ,

\bar{\mathbf{U}}_{j}=\left(\mathbf{U}_{(j-1)M_{i-1}+1},\ldots,\mathbf{U}_{jM_{% i-1}}\right).

Then

\mathsf{Fold}_{i}(\mathbf{U}_{1},\ldots,\mathbf{U}_{M_{i}};\mathbf{C}_{1},% \ldots,\mathbf{C}_{i+1})=\mathsf{BT}_{i}\begin{pmatrix}\mathsf{Fold}_{i-1}(% \bar{\mathbf{U}}_{1};\mathbf{C}_{1},\ldots,\mathbf{C}_{i})\\ \vdots\\ \mathsf{Fold}_{i-1}(\bar{\mathbf{U}}_{m_{i}};\mathbf{C}_{1},\ldots,\mathbf{C}_% {i})\end{pmatrix}\mathbf{C}_{i+1}.

Lemma 4.9.1 (Fold properties [BLN+20]).

Fix $i$ and $\{\mathbf{U}_{j}\}_{j\in[1,M_{i}]}$ with compatible dimensions. For challenges $\{\mathbf{C}_{j}\}_{j\in[1,i+1]}$ with the shapes above:

•

there exist matrices $\{\mathbf{D}_{i}\}_{i\in[1,M_{t}]}$ with $\left\|\mathbf{D}_{i}\right\|_{\infty}\leq\lambda^{i}$ such that

$\mathsf{Fold}_{i}(\mathbf{U}_{1},\ldots,\mathbf{U}_{M_{i}};\mathbf{C}_{1},% \ldots,\mathbf{C}_{i+1})=\sum_{t\in[1,M_{i}]}\mathbf{U}_{t}\mathbf{D}_{t};$
•

for every compatible matrix $\mathbf{B}$ ,

$\mathbf{B}\cdot\mathsf{Fold}_{i}(\mathbf{U}_{1},\ldots,\mathbf{U}_{M_{i}};% \mathbf{C}_{1},\ldots,\mathbf{C}_{i+1})=\mathsf{Fold}_{i}(\mathbf{B}\mathbf{U}% _{1},\ldots,\mathbf{B}\mathbf{U}_{M_{i}};\mathbf{C}_{1},\ldots,\mathbf{C}_{i+1% });$
•

if each $\mathbf{U}_{t}$ is vertically split as $\mathbf{U}_{t}=[\mathbf{U}_{t,1}^{\mathsf{T}}\mid\cdots\mid\mathbf{U}_{t,r}^{% \mathsf{T}}]^{\mathsf{T}}$ , then

$\mathsf{Fold}_{i}(\mathbf{U}_{1},\ldots,\mathbf{U}_{M_{i}};\mathbf{C}_{1},% \ldots,\mathbf{C}_{i+1})=\begin{bmatrix}\mathsf{Fold}_{i}(\mathbf{U}_{1,1},% \ldots,\mathbf{U}_{M_{i},1};\mathbf{C}_{1},\ldots,\mathbf{C}_{i+1})\\ \vdots\\ \mathsf{Fold}_{i}(\mathbf{U}_{1,r},\ldots,\mathbf{U}_{M_{i},r};\mathbf{C}_{1},% \ldots,\mathbf{C}_{i+1})\end{bmatrix}.$

Proof.

We prove all three parts by induction on $i$ . For $i=0$ , the definition gives $\mathsf{Fold}_{0}(\mathbf{U}_{1};\mathbf{C}_{1})=\mathbf{U}_{1}\mathbf{C}_{1}$ . Thus the first part holds with $\mathbf{D}_{1}=\mathbf{C}_{1}$ , and the second and third parts are immediate.

Assume the claims hold for $i-1$ . Split $(\mathbf{U}_{1},\ldots,\mathbf{U}_{M_{i}})$ into subtuples $\bar{\mathbf{U}}_{1},\ldots,\bar{\mathbf{U}}_{m_{i}}$ as was defined $\mathsf{Fold}_{i}$ , and write

\mathbf{W}_{j}=\mathsf{Fold}_{i-1}(\bar{\mathbf{U}}_{j};\mathbf{C}_{1},\ldots,% \mathbf{C}_{i}).

Also split the rows of $\mathbf{C}_{i+1}$ into $m_{i}$ blocks $\mathbf{C}_{i+1}^{(1)},\ldots,\mathbf{C}_{i+1}^{(m_{i})}$ , each of shape $\lambda\times\lambda$ . Then

\mathsf{Fold}_{i}(\mathbf{U}_{1},\ldots,\mathbf{U}_{M_{i}};\mathbf{C}_{1},% \ldots,\mathbf{C}_{i+1})=\sum_{j\in[1,m_{i}]}\mathbf{W}_{j}\mathbf{C}_{i+1}^{(% j)}.

By induction, each $\mathbf{W}_{j}$ is a bounded linear combination of the matrices in $\bar{\mathbf{U}}_{j}$ . Multiplying by $\mathbf{C}_{i+1}^{(j)}$ gives coefficient matrices whose $\ell_{\infty}$ norm grows by at most a factor $\lambda$ , since challenge entries have coefficient norm at most $1$ . Hence the new coefficients $\mathbf{D}_{t}$ satisfy $\left\|\mathbf{D}_{t}\right\|_{\infty}\leq\lambda^{i}$ , proving the first part.

For the second part, using the induction on each subtuple,

\mathbf{B}\mathbf{W}_{j}=\mathsf{Fold}_{i-1}(\mathbf{B}\bar{\mathbf{U}}_{j};% \mathbf{C}_{1},\ldots,\mathbf{C}_{i}).

Therefore multiplying $\mathsf{Fold}_{i}$ by $\mathbf{B}$ on the left is the same as replacing every input $\mathbf{U}_{t}$ by $\mathbf{B}\mathbf{U}_{t}$ before the recursive fold.

For the third part, since each $\mathbf{U}_{t}$ splits into $r$ vertical blocks, then by induction, each $\mathbf{W}_{j}$ splits into the corresponding folded block. Horizontal concatenation followed by multiplication by $\mathbf{C}_{i+1}$ preserves this vertical block decomposition, so the $a^{\mathrm{th}}$ vertical output block is

\mathsf{Fold}_{i}(\mathbf{U}_{1,a},\ldots,\mathbf{U}_{M_{i},a};\mathbf{C}_{1},% \ldots,\mathbf{C}_{i+1}).

This proves the stacking identity and completes the induction. ∎

To describe the prover’s messages that are folded, we write $\mathbf{S}$ as $\mathbf{S}_{i_{1},\ldots,i_{d-1}}$ for $(i_{1},\ldots,i_{d-1})\in[1,m_{1}]\times\ldots\times[1,m_{d-1}]$ , as a leaf of $m_{d}\times m_{d+1}$ elements. In the levelled commitment perspective, the intermediate commitments are viewed as internal nodes of the tree, and for $k\in[1,d-2]$ , define intermediate vertices recursively by

\mathbf{S}_{i_{1},\ldots,i_{k}}=\left(\mathbf{I}_{m_{k+1}}\otimes\mathbf{A}_{k% +2}\right)\begin{bmatrix}\mathbf{S}_{i_{1},\ldots,i_{k},1}\\ \vdots\\ \mathbf{S}_{i_{1},\ldots,i_{k},m_{k+1}}\end{bmatrix}\mod q_{k+2},

of shape $nm_{k+1}\times m_{d+1}$ elements. Finally,

\mathbf{S}_{\varnothing}=\left(\mathbf{I}_{m_{1}}\otimes\mathbf{A}_{2}\right)% \begin{bmatrix}\mathbf{S}_{1}\\ \vdots\\ \mathbf{S}_{m_{1}}\end{bmatrix}\mod q_{2},

with shape $nm_{1}\times m_{d+1}$ elements, so $\mathbf{A}_{1}\mathbf{S}_{\varnothing}\equiv\mathbf{T}\mod q_{1}$ . For the $i^{\mathrm{th}}$ response, the prover uses the tuple

\mathbf{V}_{i}=\begin{cases}\mathbf{S}_{\varnothing},&i=1,\\ \left(\mathbf{S}_{\boldsymbol{\alpha}}\right)_{\boldsymbol{\alpha}\in[1,m_{1}]% \times\cdots\times[1,m_{i-1}]},&i>1,\end{cases}

where $\mathbf{V}_{i}$ is ordered with the first coordinate varying fastest. This is the protocol order used by $\mathsf{Fold}_{i-1}$ ; the recursive definition of each intermediate vertex still stacks its children under a fixed prefix.

Amortized Levelled Proof.

We now show the 0-1 compression invariant $\mathbf{A}\mathbf{S}\mathbf{C}\equiv\mathbf{T}\mathbf{C}\mod q$ from [BBC+18a] in the levelled setting of [BLN+20]. The point of lemma 4.9.1 is twofold here: the vertical decomposition lets us treat a folded intermediate commitment as the stack of folded child commitments, while the left multiplication property lets us pull out the next SIS matrix $\mathbf{A}_{i+1}$ . Then $\mathsf{BT}_{i}$ only rearranges this vertical stack into the horizontal sibling blocks expected by the next challenge. With this abstraction, we show by induction over the levels of the commitment tree.

•

At the root, $\mathbf{A}_{1}\mathbf{S}_{\varnothing}\equiv\mathbf{T}\mod q_{1}$ , and therefore we have $\mathbf{A}_{1}\mathbf{Z}_{1}\equiv\mathbf{T}\mathbf{C}_{1}\mod q_{1}$ .
•

For the inductive step, write $\mathbf{V}_{i+1}=(\mathbf{V}_{i,1},\ldots,\mathbf{V}_{i,m_{i}})$ , where $\mathbf{V}_{i,j}$ is the tuple of the $j^{\mathrm{th}}$ children of the vertices in $\mathbf{V}_{i}$ . By the definition of intermediate commitments, each vertex in $\mathbf{V}_{i}$ is the vertical stack of the $\mathbf{A}_{i+1}$ -commitments to its children. Using the vertical decomposition and left multiplication properties of lemma 4.9.1, we have

$\mathbf{Z}_{i}\equiv\begin{bmatrix}\mathbf{A}_{i+1}\mathsf{Fold}_{i-1}(\mathbf% {V}_{i,1};\mathbf{C}_{1},\ldots,\mathbf{C}_{i})\\ \vdots\\ \mathbf{A}_{i+1}\mathsf{Fold}_{i-1}(\mathbf{V}_{i,m_{i}};\mathbf{C}_{1},\ldots% ,\mathbf{C}_{i})\end{bmatrix}\mod q_{i+1}.$

Applying $\mathsf{BT}_{i}$ and the next challenge gives

$\mathsf{BT}_{i}(\mathbf{Z}_{i})\mathbf{C}_{i+1}\equiv\mathbf{A}_{i+1}\mathsf{% Fold}_{i}(\mathbf{V}_{i+1};\mathbf{C}_{1},\ldots,\mathbf{C}_{i+1})=\mathbf{A}_% {i+1}\mathbf{Z}_{i+1}\mod q_{i+1}.$

The block transpose only exposes the $m_{i}$ sibling blocks of $\mathbf{Z}_{i}$ in the order needed for the next challenge matrix.

We now show an amortized opening protocol for the levelled commitment, which is public-coin, so all consistency and norm checks can be deferred to the end of the verification.

Commit.

The prover computes the levelled commitment $\mathbf{T}\leftarrow F_{1,d}(\mathbf{S})$ and sends $\mathbf{T}$ .
$i^{\mathrm{th}}$ Challenge.

The verifier samples the random challenge matrix $\mathbf{C}_{i}$ with the shape specified above.
$i^{\mathrm{th}}$ Response.

After receiving $\mathbf{C}_{i}$ , the prover sends $\mathbf{Z}_{i}\leftarrow\mathsf{Fold}_{i-1}(\mathbf{V}_{i};\mathbf{C}_{1},% \ldots,\mathbf{C}_{i})$ , of shape $nm_{i}\times\lambda$ elements.
Verify.

After receiving all responses $\mathbf{Z}_{1},\ldots,\mathbf{Z}_{d}$ , the verifier checks the response are short, and the consistency by

$\displaystyle\mathbf{A}_{1}\mathbf{Z}_{1}$ $\displaystyle\equiv\mathbf{T}\mathbf{C}_{1}\mod q_{1},$

$\displaystyle\mathbf{A}_{i+1}\mathbf{Z}_{i+1}$ $\displaystyle\equiv\mathsf{BT}_{i}(\mathbf{Z}_{i})\mathbf{C}_{i+1}\mod q_{i+1},$

where $i\in[1,d-1]$ .

Knowledge soundness and relaxed extraction.

The opening argument does not extract an exact opening to the original commitment map, and the source of this relaxation is already illustrated in the one-level vanilla construction of [BBC+18a]: special soundness subtracts two accepting responses, so the target is not scaled in the plain SIS setting, but the extracted preimage has a larger norm. If each accepted response has norm bounded by $B$ , then the extracted difference is naturally bounded by $2B$ .

In the extractor of [BBC+18a], the extracted opening is represented by bounded integers. However, in a levelled commitment, the extracted preimage is not just an opening witness; it is also meant to be an internal value produced by a lower-level commitment. The same internal value is seen in two ways: the upper-layer consumes an integer representative, as SIS is strong when the integer bound is still small, while the lower-layer only sees the corresponding residue class modulo the lower modulus. The gap between these two views is a multiple of the lower modulus, and these multiples are exactly the carry matrices in $\widetilde{F}$ .

For two levels, this definition specializes to a relaxed opening $(\bar{\mathbf{S}},\mathbf{R})$ satisfying

\mathbf{A}_{1}\cdot\left((\mathbf{I}_{m_{1}}\otimes\mathbf{A}_{2})\bar{\mathbf% {S}}\mod q_{2}+q_{2}\mathbf{R}\right)\equiv\mathbf{T}\mod q_{1}.

The extra $q_{2}\mathbf{R}$ term records the missing multiples of $q_{2}$ when the lower-level computation is viewed as an integer input to the top commitment. This relaxation is still meaningful when parameters force the extracted $(\bar{\mathbf{S}},\mathbf{R})$ to stay within SIS-binding bounds.

Although the commitment is tree shaped, extraction is better viewed depth-wise. All vertices at a same level are folded into one response, and the relaxed opening records the consistency between neighboring layers.

We now define the relaxed version of the levelled commitment map, in parallel with the exact map $F_{i,j}$ :

\widetilde{F}_{i,j}(\mathbf{S};\mathbf{R}_{i},\ldots,\mathbf{R}_{j-1})=\begin{% cases}\mathbf{A}_{i}\mathbf{S}\mod q_{i},&i=j,\\ \widetilde{F}_{i,j-1}\left(\left(\mathbf{I}_{M_{i,j-1}}\otimes\mathbf{A}_{j}% \right)\cdot\mathbf{S}\mod q_{j}+q_{j}\mathbf{R}_{j-1};\mathbf{R}_{i},\ldots,% \mathbf{R}_{j-2}\right),&i<j.\end{cases}

A bounded relaxed opening to $\mathbf{T}$ is a tuple $(\bar{\mathbf{S}},\mathbf{R}_{1},\ldots,\mathbf{R}_{d-1})$ such that every column of $\bar{\mathbf{S}}$ has norm at most $B_{S}$ , every column of $\mathbf{R}_{i}$ has $\ell_{\infty}$ norm at most $B_{R}$ , and

\widetilde{F}_{1,d}(\bar{\mathbf{S}};\mathbf{R}_{1},\ldots,\mathbf{R}_{d-1})% \equiv\mathbf{T}\mod q_{1}.

An exact opening to $\mathbf{T}$ is the case where all carry matrices $\mathbf{R}$ are zeroed out.

Similar to the theorem 4.8.7 in [BBC+18a], we define the knowledge soundness for [BLN+20].

Theorem 4.9.2.

If a prover convinces a verifier with probability $\varepsilon>2^{-\lambda+1}\cdot(4dN)^{2d}$ , there is an extractor outputs a bounded relaxed opening, where $B_{S}=2^{d}B$ and $B_{R_{k}}=2^{k}(M_{k-1}m_{d+1}\lambda^{k-1}+2)$ for $k\in[1,d-1]$ . It runs in expected $\mathsf{poly}(\lambda,1/\varepsilon)$ time.

Noticing

\mathbf{A}_{i+1}\mathbf{Z}_{i+1}\equiv\mathsf{BT}_{i}(\mathbf{Z}_{i})\mathbf{C% }_{i+1}\mod q_{i+1}

is exactly compressing $m_{i}\times\lambda$ commitments to $\lambda$ ones as in [BBC+18a], we can use the same row-local rewinding idea as theorem 4.8.7.

Fix the $\alpha^{\mathrm{th}}$ column of $\mathbf{T}$ . The desired column-wise relaxed opening has the form

\widetilde{F}_{1,d}(\bar{\mathbf{s}}_{\alpha};\mathbf{r}_{1},\ldots,\mathbf{r}% _{d-1})\equiv\mathbf{t}_{\alpha}\mod q_{1},

where $\mathbf{r}_{i}$ is the $\alpha^{\mathrm{th}}$ column of $\mathbf{R}_{i}$ for $i\in[1,d-1]$ . Iterating $\alpha$ over $[1,m_{d+1}]$ extracts the full set of relaxed opening.

For now, ignore the runtime of sampling challenges for accepting transcripts, and suppose the extractor obtains two accepting transcripts whose first challenges $\mathbf{C}_{1}$ and $\mathbf{C}_{1}^{\prime}$ differ only in the $\alpha^{\mathrm{th}}$ row. The verification equation gives

	$\displaystyle\mathbf{A}_{1}\mathbf{Z}_{1}$	$\displaystyle\equiv\mathbf{T}\mathbf{C}_{1}\mod q_{1},$
	$\displaystyle\mathbf{A}_{1}\mathbf{Z}_{1}^{\prime}$	$\displaystyle\equiv\mathbf{T}\mathbf{C}_{1}^{\prime}\mod q_{1}.$

Choose a coordinate $r$ where the two $\alpha^{\mathrm{th}}$ challenge rows differ, and orient the subtraction such that $(\mathbf{C}_{1}-\mathbf{C}_{1}^{\prime})_{\alpha,r}=1$ . Taking the $r^{\mathrm{th}}$ column after subtracting the two accepting equations gives

\mathbf{A}_{1}(\mathbf{z}_{1,r}-\mathbf{z}^{\prime}_{1,r})\equiv\mathbf{t}_{% \alpha}\mod q_{1}.

Thus the extractor obtains a bounded preimage of $\mathbf{t}_{\alpha}$ under $\mathbf{A}_{1}$ .

In a levelled commitment, this vector is only the upper-layer input; the tree construction is then used to recursively explain this extracted column by lower-level preimages.

For the next transition, write the row blocks of $\mathbf{Z}_{1}$ as $\mathbf{Z}_{1,1},\ldots,\mathbf{Z}_{1,m_{1}}$ , so that

\mathsf{BT}_{1}(\mathbf{Z}_{1})=[\mathbf{Z}_{1,1}\mid\cdots\mid\mathbf{Z}_{1,m% _{1}}].

The $r^{\mathrm{th}}$ column of $\mathbf{Z}_{1}$ is then spread across the columns $\{r_{j}=r+(j-1)\lambda\}_{j\in[1,m_{1}]}$ of $\mathsf{BT}_{1}(\mathbf{Z}_{1})$ , and the verification is

\mathbf{A}_{2}\mathbf{Z}_{2}\equiv\mathsf{BT}_{1}(\mathbf{Z}_{1})\mathbf{C}_{2% }\mod q_{2}.

To extract the $j^{\mathrm{th}}$ block of the $r^{\mathrm{th}}$ column of $\mathbf{Z}_{1}$ , the extractor therefore rewinds the $r_{j}^{\mathrm{th}}$ row of $\mathbf{C}_{2}$ . If two accepting second challenges $\mathbf{C}_{2}$ and $\mathbf{C}_{2}^{\prime}$ differ only in this row, choose a coordinate $s$ and orient such that $(\mathbf{C}_{2}-\mathbf{C}_{2}^{\prime})_{r_{j},s}=1$ . Taking the $s^{\mathrm{th}}$ column after subtracting the two level-two equations gives

\mathbf{A}_{2}(\mathbf{z}_{2,s}-\mathbf{z}^{\prime}_{2,s})\equiv\mathsf{BT}_{1% }(\mathbf{Z}_{1})_{r_{j}}\mod q_{2}.

The right hand side is the $j^{\mathrm{th}}$ block of the extracted $r^{\mathrm{th}}$ column of $\mathbf{Z}_{1}$ , which is the $r_{j}^{\mathrm{th}}$ column of $\mathsf{BT}_{1}(\mathbf{Z}_{1})$ . Iterating over $j\in[1,m_{1}]$ explains all blocks of that column; these $j$ ’s become the child slots in the transcript tree.

The heavy-row argument lemma 4.8.8 from [Dam10] is still the runtime core of the extractor.

Lemma 4.9.3 (Scaled Heavy Row Lemma).

Let $\mathbf{H}\in\{0,1\}^{n\times m}$ have density at least $\varepsilon$ . Fix $\delta\leq\varepsilon$ , and call a row $\delta$ -heavy if its row-density is at least $\delta$ . If a $1$ -entry of $\mathbf{H}$ is sampled uniformly, then its row is $\delta$ -heavy with probability at least $1-\delta/\varepsilon$ . Moreover, conditioned on a $\delta$ -heavy row, resampling a column gives another $1$ -entry with probability at least $\delta$ . If the resampled column is required to differ from the original one, this probability is at least $\delta-1/m$ .

Proof.

There are at most $\delta mn$ $1$ -entries in light rows, so at least $(\varepsilon-\delta)mn$ $1$ -entries in heavy rows, and the probability lower bound $1-\delta/\varepsilon$ holds. The rest follows the same argument in lemma 4.8.8. ∎

The 0-1 matrices are used in the runtime analysis, serving the same challenge-indexing purpose as in [BBC+18a], but now used in the extraction tree. Fix a partial transcript prefix $\boldsymbol{\pi}_{i}=\left(\mathbf{C}_{1},\mathbf{Z}_{1},\ldots,\mathbf{C}_{i}% ,\mathbf{Z}_{i}\right)$ . First define

\mathbf{H}_{i}^{(\boldsymbol{\pi}_{i})}\left[\chi,\mathbf{C}_{i+1}^{\prime}% \right]\left[\mathbf{C}_{i+2}^{\prime},\ldots,\mathbf{C}_{d}^{\prime}\right]% \in\{0,1\}.

The row is indexed by the prover randomness $\chi$ and the current challenge $\mathbf{C}_{i+1}^{\prime}$ . The column is indexed by the future challenge choice $\mathbf{C}_{i+2}^{\prime},\ldots,\mathbf{C}_{d}^{\prime}$ . The entry is $1$ iff these choices give a full accepting transcript extending $\boldsymbol{\pi}_{i}$ , such that

\mathbf{H}_{i-1}^{\boldsymbol{\pi}_{i-1}}\left[\chi,\mathbf{C}_{i}\right]\left% [\mathbf{C}_{i+1}^{\prime},\ldots,\mathbf{C}_{d}^{\prime}\right]=\mathbf{H}_{i% }^{(\boldsymbol{\pi}_{i})}\left[\chi,\mathbf{C}_{i+1}^{\prime}\right]\left[% \mathbf{C}_{i+2}^{\prime},\ldots,\mathbf{C}_{d}^{\prime}\right].

To apply the heavy-row argument to one row of the next challenge, reindex this same 0-1 matrix. Let $\rho$ be a row index in $\mathbf{C}_{i+1}^{\prime}$ . Write $\mathbf{c}_{i+1,\rho}^{\prime\mathsf{T}}$ for the $\rho^{\mathrm{th}}$ row of $\mathbf{C}_{i+1}^{\prime}$ , and $\hat{\mathbf{C}}_{i+1,\rho}^{\prime}$ for the rows obtained from $\mathbf{C}_{i+1}^{\prime}$ by deleting $\mathbf{c}_{i+1,\rho}^{\prime\mathsf{T}}$ . Define

H_{i}^{\prime(\boldsymbol{\pi}_{i},\rho)}\left[\chi,\hat{\mathbf{C}}_{i+1,\rho% }^{\prime}\right]\left[\mathbf{c}_{i+1,\rho}^{\prime\mathsf{T}},\mathbf{C}_{i+% 2}^{\prime},\ldots,\mathbf{C}_{d}^{\prime}\right]=H_{i}^{(\boldsymbol{\pi}_{i}% )}\left[\chi,\mathbf{C}_{i+1}^{\prime}\right]\left[\mathbf{C}_{i+2}^{\prime},% \ldots,\mathbf{C}_{d}^{\prime}\right].

Thus the rows of $H_{i}^{\prime(\boldsymbol{\pi}_{i},\rho)}$ fix the prover randomness and the non-interesting rows of $\mathbf{C}^{\prime}_{i+1}$ , while its columns are indexed by the $\rho^{\mathrm{th}}$ row of $\mathbf{C}^{\prime}_{i+1}$ together with all later challenges. At the root, $\boldsymbol{\pi}_{0}=\emptyset$ and the first rewinding uses the $\alpha^{\mathrm{th}}$ row of $\mathbf{C}_{1}^{\prime}$ . Beyond the root, $\mathsf{BT}$ determines how the current extraction target is seen at the next level: it becomes several target rows in $\mathbf{C}_{i+1}^{\prime}$ spaced by $\lambda$ , as was previously discussed.

The original one-level use sets $\delta=\varepsilon/2$ , and the probability is at least $1/2$ in lemma 4.8.8. For the tree extractor, the same lemma is used with a larger slack $K$ : set the heavy threshold to $\delta=\varepsilon/K$ , and an accepting entry lands in a heavy row with probability at least $1-1/K$ . After landing in such a row, resampling only the target row(s) in the challenge being rewound gives another accepting challenge with probability at least $\varepsilon/K-\left|\mathcal{C}\right|^{-\lambda}$ .

The extractor in [BLN+20] builds a tree of partial transcripts, and the leaves are accepting full transcripts. A state at depth $i$ is written as

\mathsf{TC}_{i}([j_{1},\ldots,j_{i}],\mathbf{C}_{i},\mathbf{Z}_{i},t).

Here $[j_{1},\ldots,j_{i}]$ is the address of the vertex in the tree, where each $j_{k}$ records which child slot was taken:

•

The block of the current column (because of $\mathsf{BT}$ ) being followed,
•

One of the two rewounded children, left or right.

The arguments $\mathbf{C}_{i},\mathbf{Z}_{i},t$ are the current challenge, the current response, and the column currently being extracted. Reading the challenges and responses along the addressed path gives the prefix $\boldsymbol{\pi}_{i}=(\mathbf{C}_{1},\mathbf{Z}_{1},\ldots,\mathbf{C}_{i},% \mathbf{Z}_{i})$ used when rewinding the prover.

The first step is the same operation with empty prefix and target row $\alpha$ in $\mathbf{C}_{1}$ (namely the $\alpha^{\mathrm{th}}$ column of $\mathbf{T}$ ). Sample two first challenges that differ only in this row, run the prover on both, and choose a coordinate $t$ where the two $\alpha^{\mathrm{th}}$ rows differ, oriented so the difference is $1$ . The two resulting children are depth- $1$ states storing their own $\mathbf{C}_{1},\mathbf{Z}_{1}$ , and both carry the index $t$ . Their edge already gives

\mathbf{A}_{1}(\mathbf{z}_{1,t}^{(0)}-\mathbf{z}_{1,t}^{(1)})\equiv\mathbf{t}_% {\alpha}\mod q_{1}.

Fix a non-root, non-leaf state $\mathsf{TC}_{i}([j_{1},\ldots,j_{i}],\mathbf{C}_{i},\mathbf{Z}_{i},t)$ . The first task is to determine which rows of the next challenge have to be rewound. The $t^{\mathrm{th}}$ column of $\mathbf{Z}_{i}$ is spread by $\mathsf{BT}_{i}$ across the rows

\rho_{\ell}=t+(\ell-1)\lambda,\qquad\ell\in[1,m_{i}],

of the next challenge $\mathbf{C}_{i+1}$ . For each row $\rho_{\ell}$ , the algorithm creates a pair of child candidates by sampling two challenges $\widetilde{\mathbf{C}}_{i+1}$ and $\widetilde{\mathbf{C}}_{i+1}^{\prime}$ that are equivalent except for the $\rho_{\ell}^{\mathrm{th}}$ row, and rewinding the prover from the prefix $\boldsymbol{\pi}_{i}$ to obtain the two responses $\widetilde{\mathbf{Z}}_{i+1}$ and $\widetilde{\mathbf{Z}}_{i+1}^{\prime}$ .

For $i<d-1$ , these candidates are the next partial-transcript children. For $i=d-1$ , they must be accepting leaf transcripts instead.

•

For the first child, the extractor keeps resampling the $\rho_{\ell}^{\mathrm{th}}$ row of $\widetilde{\mathbf{C}}_{i+1}$ and reruns the prover until the resulting transcript is accepting; it aborts after $\lambda K/\varepsilon$ failed attempts.
•

For the second child, it rewinds to the same prefix and repeats the same search for $\widetilde{\mathbf{C}}_{i+1}^{\prime}$ ; it aborts after $2\lambda K/\varepsilon$ failed attempts.

Choose a coordinate $s_{\ell}\in[1,\lambda]$ where the two $\rho_{\ell}^{\mathrm{th}}$ challenge rows differ,

\left(\widetilde{\mathbf{C}}_{i+1}-\widetilde{\mathbf{C}}_{i+1}^{\prime}\right% )_{\rho_{\ell},s_{\ell}}\neq 0,

and orient the pair so the difference is $1$ . The two responses become the $(\ell,0)$ and $(\ell,1)$ children, and both use $s_{\ell}$ as the next column to be extracted. The edge created by this local rewind is

\mathbf{A}_{i+1}\left(\widetilde{\mathbf{z}}_{i+1,s_{\ell}}-\widetilde{\mathbf% {z}}_{i+1,s_{\ell}}^{\prime}\right)\equiv\mathsf{BT}_{i}(\mathbf{Z}_{i})_{\rho% _{\ell}}\mod q_{i+1}.

Thus a depth $i$ state with $i\geq 1$ creates $2m_{i}$ children, and level $i>0$ has $2^{i}M_{i-1}$ vertices, as in the paper.

Now we can bound the abort probability in the same order as the paper. Let $\kappa$ denote the per-step heavy-row fraction parameter, and let the retry parameter in the tree construction be $K=\kappa^{2d}$ . Fix a level- $(d-1)$ vertex $V$ , and write

(V_{0},V_{1},\ldots,V_{d-2},V)

for the path from the root $V_{0}$ to $V$ . Let $r_{1},\ldots,r_{\gamma}$ be the indices for which $V_{r_{j}}$ is a right child. Let $\mathsf{abort}(V)$ be the event that the tree construction aborts while trying to complete this fixed leaf vertex $V$ . Write $h_{i}(\eta)$ for the event that the row selected by this path is $\eta$ -heavy in $\mathbf{H}_{i}$ , and write $h_{i}^{\prime}(\eta)$ for the corresponding event in the reindexed matrix $\mathbf{H}_{i}^{\prime}$ . The aborting probability for left and right children is derived differently: for a left child it comes directly from $\mathbf{H}_{i}$ , while for a right child it first comes through the reindexed matrix $\mathbf{H}_{i}^{\prime}$ and then through $\mathbf{H}_{i}$ .

The first step is the only boundary case. If $V_{1}$ is a right child, then the first challenge was obtained by resampling one target row while keeping the other rows fixed, so the proof first goes through $\mathbf{H}_{0}^{\prime}$ :

\Pr\left[\mathsf{abort}(V)\right]\leq\Pr\left[\mathsf{abort}(V)\mid h_{0}^{% \prime}(\varepsilon/\kappa)\right]+\Pr\left[\neg h_{0}^{\prime}(\varepsilon/% \kappa)\right]\leq\Pr\left[\mathsf{abort}(V)\mid h_{0}^{\prime}(\varepsilon/% \kappa)\right]+1/\kappa.

Here $\mathbf{H}_{0}^{\prime}$ moves the target row of $\mathbf{C}_{1}^{\prime}$ from the row index into the column index: a row of $\mathbf{H}_{0}^{\prime}$ is fixed by the non-target rows of $\mathbf{C}_{1}^{\prime}$ , and is the concatenation of the ordinary $\mathbf{H}_{0}$ rows obtained by varying that target row. Thus the heavy-row lemma applies to $\mathbf{H}_{0}^{\prime}$ after this row-column rearrangement. Conditioned on $h_{0}^{\prime}(\varepsilon/\kappa)$ , the selected row of $\mathbf{H}_{0}^{\prime}$ has density at least $\varepsilon/\kappa$ . Now split this selected row according to the value of the target row. Each piece is one ordinary row of $\mathbf{H}_{0}$ , so another application of the heavy-row lemma gives

\Pr\left[\neg h_{0}(\varepsilon/\kappa^{2})\mid h_{0}^{\prime}(\varepsilon/% \kappa)\right]\leq 1/\kappa,

thus

\Pr\left[\mathsf{abort}(V)\mid h_{0}^{\prime}(\varepsilon/\kappa)\right]\leq% \Pr\left[\mathsf{abort}(V)\mid h_{0}^{\prime}(\varepsilon/\kappa)\wedge h_{0}(% \varepsilon/\kappa^{2})\right]+1/\kappa.

If $V_{1}$ is a left child, then the first challenge is sampled as a full challenge, and the bound starts directly from $\mathbf{H}_{0}$ :

\Pr\left[\mathsf{abort}(V)\right]\leq\Pr\left[\mathsf{abort}(V)\mid h_{0}(% \varepsilon/\kappa)\right]+\Pr\left[\neg h_{0}(\varepsilon/\kappa)\right]\leq% \Pr\left[\mathsf{abort}(V)\mid h_{0}(\varepsilon/\kappa)\right]+1/\kappa.

After this boundary step, the proof continues in the same way through $h_{1},\ldots,h_{d-2}$ , inserting $h_{r_{j}-1}^{\prime}$ immediately before $h_{r_{j}-1}$ for every right child $V_{r_{j}}$ on the path. Let $E$ be the conjunction of these heavy-row events, such that the threshold divided by a factor of $\kappa$ at each peeling step. Then

\Pr\left[\neg E\right]\leq(d-1+\gamma)/\kappa\leq 2(d-1)/\kappa.

On $E$ , the event $h_{d-2}(\varepsilon/\kappa^{d-1+\gamma})$ holds. Concretely, for the prefix $\boldsymbol{\pi}_{d-2}$ on the path to $V$ , the row $\mathbf{H}_{d-2}^{(\boldsymbol{\pi}_{d-2})}[\chi,\mathbf{C}_{d-1}]$ has density at least $\varepsilon/\kappa^{d-1+\gamma}$ . The columns of this row are indexed by the remaining final challenge $\mathbf{C}_{d}$ , so this is the success probability for one attempt in the first final-challenge search. Since $\gamma\leq d-1$ and $K=\kappa^{2d}$ , this local success probability is lower-bounded by $\varepsilon/\kappa^{d-1+\gamma}\geq\varepsilon/K$ . With $\lambda K/\varepsilon$ attempts, the first leaf abort probability less than $e^{-\lambda}$ .

The paired leaf search needs one more heavy-row step. Write $\rho$ for the target row of the final challenge determined by this leaf. After the first final challenge is fixed, the extractor resamples only this row for the second final challenge, so the analysis passes to the row

\mathbf{H}_{d-1}^{\prime(\boldsymbol{\pi}_{d-1},\rho)}[\chi,\hat{\mathbf{C}}_{% d,\rho}^{\prime}]

whose columns are indexed by the resampled target row. Conditioned on $h_{d-1}^{\prime}(\varepsilon/\kappa^{d+\gamma})$ , this row has density at least $\varepsilon/\kappa^{d+\gamma}$ . This event fails with probability at most $1/\kappa$ , and, when it holds, the successful resampling probability is at least

\varepsilon/\kappa^{d+\gamma}-\left|\mathcal{C}\right|^{-\lambda},

where the subtraction excludes choosing the same target row again. By the lower bound on $\varepsilon$ in theorem 4.9.2, this is still at least $\varepsilon/(2K)$ , and the $2\lambda K/\varepsilon$ attempts make the second leaf abort probability less than $e^{-\lambda}$ .

Combining the failure of $E$ , the extra possible failure of $h_{d-1}^{\prime}(\varepsilon/\kappa^{d+\gamma})$ , and the two leaf searches, for a fixed leaf vertex we get

\Pr\left[\mathsf{abort}(V)\right]\leq 2e^{-\lambda}+2d/\kappa.

The paper sets $\kappa=4dN$ . Union bounding over all vertices at level $d-1$ , which are $2^{d-1}M_{d-2}$ of them, given that $d$ is a constant, and $2^{d-1}M_{d-2}<N$ , then the aborting probability is at most

\frac{2N}{e^{\lambda}}+\frac{2dN}{\kappa}=\frac{2N}{e^{\lambda}}+\frac{1}{2}.

Thus one run of TreeConstruct succeeds with constant probability, up to the negligible $2N/e^{\lambda}$ term. For a fixed target column $\alpha$ , running $O(\lambda)$ independent copies gives a successful tree except with negligible probability. The extractor needs this for all $m_{d+1}$ columns of $\mathbf{T}$ , so it repeats the same procedure for every $\alpha\in[1,m_{d+1}]$ . Since $m_{d+1}\leq N$ , $N=\mathsf{poly}(\lambda)$ , $d$ is constant, and $K=(4dN)^{2d}=\mathsf{poly}(\lambda)$ , the total expected running time remains $\mathsf{poly}(\lambda,1/\varepsilon)$ .

Once the tree is built, extraction is just reading off neighboring children. For a vertex whose current target is the $t^{\mathrm{th}}$ column, the two children created for the row $\rho_{\ell}$ give

\mathbf{A}_{i+1}\left(\widetilde{\mathbf{z}}_{i+1,s_{\ell}}-\widetilde{\mathbf% {z}}_{i+1,s_{\ell}}^{\prime}\right)\equiv\mathsf{BT}_{i}(\mathbf{Z}_{i})_{\rho% _{\ell}}\mod q_{i+1}.

Collecting these sibling differences over $\ell\in[1,m_{i}]$ gives the preimage block for the parent target column after the block transition. Repeating down the tree and concatenating the extracted blocks level by level produces the relaxed opening $(\bar{\mathbf{s}},\mathbf{r}_{1},\ldots,\mathbf{r}_{d-1})$ for the chosen column of $\mathbf{T}$ ; Iterating over $[1,m_{d+1}]$ columns gives the full relaxed opening.

The binding intuition is then about the relaxed relation extracted from the argument. For two levels, write the lifted inputs seen by the top matrix $\mathbf{A}_{1}$ as

	$\displaystyle\bar{\mathbf{S}}_{\varnothing}$	$\displaystyle=(\mathbf{I}_{m_{1}}\otimes\mathbf{A}_{2})\bar{\mathbf{S}}\mod q_% {2}+q_{2}\mathbf{R},$
	$\displaystyle\bar{\mathbf{S}}^{\prime}_{\varnothing}$	$\displaystyle=(\mathbf{I}_{m_{1}}\otimes\mathbf{A}_{2})\bar{\mathbf{S}}^{% \prime}\mod q_{2}+q_{2}\mathbf{R}^{\prime}.$

Both relaxed openings to the same $\mathbf{T}$ satisfy

\mathbf{A}_{1}\bar{\mathbf{S}}_{\varnothing}\equiv\mathbf{A}_{1}\bar{\mathbf{S% }}^{\prime}_{\varnothing}\equiv\mathbf{T}\mod q_{1}.

Suppose the two bounded relaxed openings $(\bar{\mathbf{S}},\mathbf{R})$ and $(\bar{\mathbf{S}}^{\prime},\mathbf{R}^{\prime})$ are distinct, and both open to the same $\mathbf{T}$ . If $\mathbf{R}\neq\mathbf{R}^{\prime}$ , then the two integer representations of the upper-layer inputs are different, and hence

\mathbf{A}_{1}(\bar{\mathbf{S}}_{\varnothing}-\bar{\mathbf{S}}^{\prime}_{% \varnothing})\equiv\boldsymbol{0}\mod q_{1}

gives a short SIS relation for $\mathbf{A}_{1}$ . If $\mathbf{R}=\mathbf{R}^{\prime}$ , then $\bar{\mathbf{S}}\neq\bar{\mathbf{S}}^{\prime}$ . In this case, either the lower-layer images of $\mathbf{I}_{m_{1}}\otimes\mathbf{A}_{2}$ differ modulo $q_{2}$ , which again makes the lifted top inputs different and gives SIS for $\mathbf{A}_{1}$ , or their equality modulo $q_{2}$ gives a short nonzero SIS solution for $\mathbf{A}_{2}$ . The separated moduli and norm bounds are chosen so that the differences stay inside the SIS-binding range.

Parameters and slack.

For constant $d$ , the parameter balancing in the paper gives communication

O\left(N^{1/(d+1)}\cdot\left(d^{3}\lambda\log^{2}N+d\lambda^{2}\right)\right).

If $d+1=\log N$ , this becomes

O(\lambda\log^{5}N+\lambda^{2}\log N).

The extractor recovers a relaxed opening: a matrix $\bar{\mathbf{S}}$ and matrices $\mathbf{R}_{1},\ldots,\mathbf{R}_{d-1}$ satisfying the relaxed recursive commitment equation. The communication saving therefore comes with knowledge slack, with parameters set so that the slack remains below the relevant SIS bounds.

Bulletproofs-style lattice folding.

The second construction asks whether the Bulletproofs [BBB+18] folding trick can be made lattice-compatible. The starting statement is the RSIS equation

\mathbf{A}\mathbf{s}=\mathbf{t},\qquad\mathbf{A}=[\mathbf{A}_{1}\mid\mathbf{A}% _{2}]\in R^{1\times k},\qquad\mathbf{s}=\begin{bmatrix}\mathbf{s}_{1}\\ \mathbf{s}_{2}\end{bmatrix}\in R^{k},

over $R=\mathbb{Z}[X]/(X^{n}+1)$ . Here the number of integer secrets is $N=kn$ . In one folding round, the prover sends

\mathbf{l}=\mathbf{A}_{1}\mathbf{s}_{2},\qquad\mathbf{r}=\mathbf{A}_{2}\mathbf% {s}_{1}.

The verifier samples a monomial challenge $c\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{X^{i}:i\in\mathbb{Z}_{2n}\}$ , and the prover responds with

\mathbf{z}=\mathbf{s}_{1}+c\mathbf{s}_{2}.

Then

(c\mathbf{A}_{1}+\mathbf{A}_{2})\mathbf{z}=c^{2}\mathbf{l}+c\mathbf{t}+\mathbf% {r},

so the verifier can replace the old statement $(\mathbf{A},\mathbf{t})$ by

\mathbf{B}=c\mathbf{A}_{1}+\mathbf{A}_{2},\qquad\mathbf{t}^{\prime}=c^{2}% \mathbf{l}+c\mathbf{t}+\mathbf{r},

with witness $\mathbf{z}$ of half the length. The verifier also checks that $\mathbf{z}$ remains short.

Repeating for $d$ rounds reduces the witness length by $2^{d}$ ; setting $d=\log k$ leaves a single ring element and gives logarithmic-length communication.

For one round, extraction rewinds to three accepting transcripts with distinct challenges $c_{1},c_{2},c_{3}$ gives

(c_{j}\mathbf{A}_{1}+\mathbf{A}_{2})\mathbf{z}_{j}=c_{j}^{2}\mathbf{l}+c_{j}% \mathbf{t}+\mathbf{r},\qquad j\in[1,3],

for the same $\mathbf{l},\mathbf{r},\mathbf{t}$ . Choose coefficients $\lambda_{1},\lambda_{2},\lambda_{3}\in R$ by solving the Vandermonde system

\begin{bmatrix}c_{1}^{2}&c_{2}^{2}&c_{3}^{2}\\ c_{1}&c_{2}&c_{3}\\ 1&1&1\end{bmatrix}\begin{bmatrix}\lambda_{1}\\ \lambda_{2}\\ \lambda_{3}\end{bmatrix}=\begin{bmatrix}0\\ 1\\ 0\end{bmatrix}.

Then the $\mathbf{l}$ and $\mathbf{r}$ terms cancel, and formally

\mathbf{A}_{1}\sum_{j=1}^{3}\lambda_{j}c_{j}\mathbf{z}_{j}+\mathbf{A}_{2}\sum_% {j=1}^{3}\lambda_{j}\mathbf{z}_{j}=\mathbf{A}\sum_{j=1}^{3}\lambda_{j}\begin{% bmatrix}c_{j}\mathbf{z}_{j}\\ \mathbf{z}_{j}\end{bmatrix}=\mathbf{t}.

The challenge set is chosen to consist of monomials $X^{i}$ . For pairwise distinct monomials, the paper uses the fact that $2/(X^{i}-X^{j})$ has coefficients in $\{-1,0,1\}$ , and obtains $\left\|8\lambda_{j}\right\|_{\infty}\leq 2n^{2}$ . After clearing this denominator, one obtains a one-round relaxed preimage

\bar{\mathbf{z}}=8\sum_{j=1}^{3}\lambda_{j}\begin{bmatrix}c_{j}\mathbf{z}_{j}% \\ \mathbf{z}_{j}\end{bmatrix},\qquad\mathbf{A}\bar{\mathbf{z}}=8\mathbf{t},

with $\left\|\bar{\mathbf{z}}\right\|_{\infty}\leq O(12n^{3}p)$ when each accepted response is bounded by $2p$ .

This is the sense in which the Bulletproofs-style extraction is approximate: the extractor does not recover a short preimage of the original target $\mathbf{t}$ , but a larger preimage of the scaled target $8\mathbf{t}$ . Recursing through $d$ folds multiplies both effects. Extraction gives a relaxed solution to

\mathbf{A}\bar{\mathbf{z}}=8^{d}\mathbf{t}

with

\left\|\bar{\mathbf{z}}\right\|_{\infty}=O(n^{3d}12^{d}p)

when $\left\|\mathbf{s}\right\|_{\infty}\leq p$ . Thus logarithmic folding buys a much smaller transcript, but pays a large slack: the target is scaled by $8^{d}$ and the extracted witness norm grows by roughly $(12n^{3})^{d}$ . With repetition to reduce soundness error, the proof size is

O\left(\frac{\lambda N\log(2^{d}p)}{2^{d}\log n}+\lambda d^{2}n\right).

Takeaway.

Both constructions are non-PCP routes to succinct, plausibly quantum-safe ZK, but neither extracts an exact original witness. Levelled commitments have larger proofs but smaller, more controllable slack. Bulletproofs folding has the better proof-size expression when slack is cheap, but the relaxed equation $\mathbf{A}\bar{\mathbf{z}}=8^{d}\mathbf{t}$ and coefficient growth can force much larger parameters in applications where the extracted witness feeds into other cryptographic components. The paper’s main open direction is to keep the algebraic folding/compression while reducing coefficient growth enough to become competitive with generic PCP/Merkle-tree based post-quantum arguments in concrete size.

	$\displaystyle\mathbf{A}_{1}\mathbf{Z}_{1}$	$\displaystyle\equiv\mathbf{T}\mathbf{C}_{1}\mod q_{1},$
	$\displaystyle\mathbf{A}_{i+1}\mathbf{Z}_{i+1}$	$\displaystyle\equiv\mathsf{BT}_{i}(\mathbf{Z}_{i})\mathbf{C}_{i+1}\mod q_{i+1},$