1# Notes on Labrador, a lattice-based SNARK scheme
  2*2026-06-11*
  3
  4I was curious on how (post-quantum) lattice-based SNARKs would work, and since I had a bit of time these past days, I've been reading the [LaBRADOR paper](https://eprint.iacr.org/2022/1341.pdf), by Ward Beullens and Gregor Seiler. This post tries to explain the intuition and steps not explicitly shown in the paper, which helped me understanding it.
  5
  6The structure of this post is the following:
  7
  8<div id="toc"></div>
  9
 10## Notation
 11
 12The paper uses $\vec{z} \in R^n$ to indicate a vector of length $n$; for simplicity, in this post I'll use $z \in R^n$, since it is already clear that we're working with a vector since we use $\in R^n$.
 13
 14Also, will use $i \in [n]$ to indicate $i = 1, \ldots, n$. And $(a_{ij})$ denotes the matrix with all the $a_{ij}$ values as entries.
 15
 16## A bit of background on lattices
 17
 18
 19### Lattices intro
 20
 21Intuitively, think of lattices as a discrete version of finite-dimensional vector spaces. In the same way that vector spaces span over some basis vectors $\{ b_i ~|~ i \in [n] \}$ in a field, lattices span over the basis in a ring:
 22
 23$$\mathcal{L} = \mathcal{L}(B) := B \cdot \mathbb{Z}^k = \{ \sum_{i=1}^k z_i \cdot b_i ~|~ z_i \in \mathbb{Z} \}$$
 24
 25for a basis $B = \{ b_1, \ldots, b_k \}$ (which since they are a basis, they are linearly independent). $k$ is the rank of the basis, and we restrict our attention to *full-rank* lattices where $k=n$.
 26
 27Since we're at the lattices realm, we work with the polynomial ring $R_q = \mathbb{Z}_q[X]/(X^d + 1)$, and particularly in Labrador we pick $q$ and $d$ such that $X^d + 1$ splits in two irreducible factors $\pmod q$.
 28
 29<br>
 30
 31To provide a bit of more intuition, we can relate it to the *algebraic coding theory* concept of *sphere packing problem*, where in lattices we use short vectors and in coding theory we're interested into low weighted codewords. Both in lattices and coding theory we have q-ary {lattices/matrices} respectively and also parity check {lattices/matrices} respectively.
 32
 33<div style="text-align:center;">
 34<img style="width:70%"
 35src="img/posts/labrador/lattice-spherepackingproblem.png"></img>
 36<br>
 37<i></i>
 38</div>
 39
 40### MSIS problem
 41*MSIS* problem stands for *Module Short Integer Solution* problem, and it is as follows:
 42
 43Given a uniformly random matrix $A \in^R R_q^{n \times m}$, with columns $a_i \in R_q^n$, find a non-zero integer vector $z \in R^m$ of norm $||z|| \leq \beta$ such that
 44
 45$$A \cdot z = \sum_i a_i \cdot z_i = 0 \in R_q^n$$
 46
 47> *Remarks:*
 48>
 49> - without $||z|| \leq \beta$, it is easy to find a solution via [Gaussian elimination](https://math.libretexts.org/Courses/Palo_Alto_College/College_Algebra/05:_Systems_of_Equations_and_Inequalities/5.04:_Solving_Systems_with_Gaussian_Elimination).
 50> - $\beta < q$, because otherwise $z=(q, 0, \ldots, 0) \in R^m$ would always be a valid solution.
 51> - $\beta$ and $m$ must be large enough so that a solution is guaranteed to exist, usually $\beta \geq \sqrt{\hat{m}}$ and $m \geq \hat{m}$ where $\hat{m}$ is the smallest integer greater than $n \log q$.
 52
 53So overall when doing lattice-based cryptography, we will be interested into keeping the values *short*, aka. of small norm.
 54
 55Specifically, Labrador relies on the hardness of finding short solutions to linear equations over polynomial rings.
 56
 57<br>
 58
 59With this in mind, usually a common trick used when doing operations is to decompose the values with small bases, so that we can represent them while keeping the norm low. We will also use this in Labrador.
 60
 61
 62### Ajtai commitments
 63
 64We use a variant of the Ajtai commitments, where the messages are ring elements with small norms.
 65
 66For a sampled random matrix $A \in^R R_q^{n \times m}$, and given $x \in R^m$ as input, where $||x|| \leq \beta$, the Ajtai commitment is defined as $cm := A \cdot x \in R_q^n$.
 67
 68In other words, Ajtai commitments are essentially MSIS instances.
 69
 70Notice that this is binding but it is not hiding, but we could make it hiding by appending a small random veector to $x$.
 71
 72## Labrador constraints
 73
 74As usual in SNARK schemes, we have the witness, denoted $s= s_1, \ldots, s_r$, where each $s_i \in R_q^n$, ie. the witness is a vector of $r$ vectors of ring elements.
 75
 76And since we're at the lattices world and we're using the assumptions of SIS and Module-SIS, the witness values are "short", that is, their norm is bounded by some parameter: $\sum_{i=1}^r || s_i ||_2^2 \leq \beta^2$.
 77
 78
 79While in other SNARK systems we worked with constraints in the shape of R1CS or Plonkish, LaBRADOR defines its constraints as
 80
 81$$\boxed{
 82f(s) = \sum_{i, j}^r a_{ij} \langle s_i, s_j \rangle + \sum_{i=1}^r \langle \phi_i, s_i \rangle + b = 0
 83}
 84$$
 85
 86where $s_i, \phi_i \in R_q^n$, and $a_{ij}, b \in R_q$.
 87
 88There are two different families of constraints, which are evaluated differently:
 89
 90- $\mathcal{F}$ family, which are those constraints where the entire polynomial must evaluate to zero, ie. $f(s) = 0$
 91- $\mathcal{F}~'$ family, which are those constraints where we're only interested in their constant term being zero, ie. $ct( f'(s) ) = 0$
 92
 93To avoid future doubts, let's write down what are some constant values:
 94
 95- $r$: amount of witness vectors $s_1, \ldots, s_r$
 96- $K = |\mathcal{F}|$: amount of original constraints of fully vanishing dot products
 97- $L = |\mathcal{F}~'|$: amount of original constraints where the constant term is zero
 98
 99
100<!--
101(HIDDEN)
102> *Side derailed observation*: since Labrador works with $\mathbb{Z}_q[X]/(X^d + 1)$, where $q, d$ are such that $X^d + 1$ splits in two irreducible factors $\pmod q$, this is a ring, the polynomial ring $R_q$.
103> 
104> But imagine for a moment (only imagine, since in many lattice-based cryptography this is not the case) that we pick $q, d$ parameters such that $X^d+1$ is irreducible, then we would have $\mathbb{Z}_q[X]/(X^d+1)$ being a finite field, $\mathbb{F}_{q^d}$; and then, the set of solutions satisfying the family $\mathcal{F}$ would be an *algebraic variety*, which is an interesting algebraic object, although not so useful in the context where we're now. But this is not the case, and in our case the $X^d+1$ that splits into two irreducible factors so that it ensures that through the protocol we can find challenges that are both computationally *short* and invertible when subtracted ([iacr:2017-523](https://eprint.iacr.org/2017/523)).
105-->
106
107
108## Protocol
109For the rest of this post, I'll use colours to easily identify the different concepts across the various equations of the protocol.
110
111We start from the *original* constraints. Those are both, the fully vanishing constraints of the family $\mathcal{F}$ and the constraints where the constant term is zero of the family $\mathcal{F}~'$:
112
113$$
114f(s) = \sum_{i, j}^r \textcolor{magenta}{a_{ij}} \langle s_i, s_j \rangle + \sum_{i=1}^r \langle \textcolor{blue}{\phi_i}, s_i \rangle - \textcolor{orange}{b} = 0
115$$
116
117$$
118f'(s) = \sum_{i, j}^r \textcolor{magenta}{a'_{ij}} \langle s_i, s_j \rangle + \sum_{i=1}^r \langle \textcolor{blue}{\phi'_i}, s_i \rangle - \textcolor{orange}{b'} ~~such~that~~ ct(f'(s))=0
119$$
120
121In this blog post we will not cover how do we get from the R1CS constraints into the Labrador constraints shape, it can be found in the section 6 of the paper, but the main idea you need to have is that for different kinds of R1CS constraints (binary and non-binary constraints) we can obtain the $f(s)$ and $f'(s)$ Labrador constraints.
122
123Once we have the original constraints, the idea is to do some reductions adding some more constraints, and then do multiple aggregation steps in order to end up having fewer constraints.
124
125
126<div style="text-align:center;">
127<img style="width:60%"
128src="img/posts/labrador/constraint-polynomials-evolution.jpg"></img>
129<br>
130<i style="color:#374072">$f(s), f'(s)$ are original polynomials, from the mentioned families $\mathcal{F}$ and $\mathcal{F}~'$ respectively,<br>
131$f_{proj}(s), f''(s)$, $F(s)$ are polynomials that we will describe in the following sections.</i>
132</div>
133
134
135<br>
136Labrador reduces proof size through four transformations unfolded over the next sections:
137
1381. Commit to the witness
1392. Reduce norm checking with Johnson-Lindenstrauss projections
1403. Aggregate many constraints into one
1414. Amortize openings
1425. Recurse
143
144
145### 1. Committing to the witness
146We name *inner commitments* the commitments to the original witness. Those commitments are
147
148$$cm(s_i) = t_i = A \cdot s_i \in R_q^k ~~ \forall i \in [r]$$
149
150But beware, sending all those $r$ commitments would be too costly, so what the protocol does is it commits to them. The issue then is that $t_i$ (the inner commitments) have coefficients that are $\pmod q$, whose norm would be too big. The trick that the protocol uses, is the one we mentioned at the [*'a bit of background on lattices'* section](#a-bit%20of%20background%20on%20lattices), this is, to decompose them into $t_1 \geq 2$ parts with small base $b_1$ before committing, ie.
151
152$$t_i = t_i^{(0)} + t_i^{(1)} b_1 + \ldots + t_i^{(t_1-1)} \cdot b_1^{t_1 -1}$$
153with $|| t_i^{(k)} ||_{\infty} \leq b_1/2$.
154
155Now, let $t \in R_q^{r \cdot t_1 \cdot k}$ be the concatenation of all decomposition parts of $t_i^{(k)}$.
156
157The commitment to the original commitment, is named *outer commitment*, and it is computed as
158
159$$u_1 = B \cdot t$$
160
161that is
162
163$$u_1 = \sum_{i=1}^r \sum_{k=0}^{t_1-1} B_{ik} \cdot t_i^{(k)}$$
164
165with $||t|| \leq \gamma_1$ for a fixed norm parameter $\gamma_1$.
166
167
168Now, we want to show that $s=(s_1, \ldots, s_r)$ satisfies the norm bound that we mentioned at the [setup](#setup) section. But sending $r$ witness to the verifier would be again too costly, so the protocol reduces it through a projection.
169
170### The σ₋₁ trick
171
172Before going forward with the protocol, we will overview a trick that Labrador uses in order to compute inner products within the polynomial ring realm.
173
174$\sigma_{-1}(\pi_i)$ allows us to convert the coefficient-wise vector inner product into a polynomial multiplication relation.
175
176Within the protocol, we want to compute $p_j = \sum_{i=1}^r \langle \pi_i^{(j)}, s_i \rangle$, but we want to compute it using ring operations, concretely using polynomial multiplication.
177
178Notice that in Labrador, vectors are encoded as polynomials in $R_q$, ie
179
180$$a=(a_1, \ldots, a_{n}) ~\longleftrightarrow~ a(x) = \sum_{k=1}^n a_k X^k \in R_q$$
181
182Let $a(x) = \sum_k a_k X^k,~~ b(x) = \sum_k b_k X^k$, then when computing $a(x) \cdot b(x)$
183
184$$a(x) b(x) = (\sum_k a_k X^k) \cdot (\sum_k b_k X^k) = \sum_{i,j} a_i b_j X^{i+j}$$
185
186which is different from the dot product that we're interested in.
187
188We want to only multiply together the coefficients of the equal-index terms, ie. $a_0 b_0 + a_1 b_1 + \ldots + a_{n-1} b_{n-1}$. Thus we need some trick to force getting only the values when $i=j$.
189
190The trick is with $\sigma_{-1}$ and getting the constant term of the result of multiplying $\sigma_{-1}(a) \cdot b$.
191
192Define the automorphism $\sigma_{-1}$ as $\sigma_{-1}(X) = X^{-1}$, so that $\sigma_{-1}(a(X)) = a(X^{-1}) = \sum_i a_i X^{-i}$.
193
194Then, when multiplying
195
196$$\sigma_{-1}(a(X)) \cdot b(X) = \sum_{i,j} a_i b_j X^{j-i}$$
197
198So, when $j=i$, $X$ will be $0$; hence the result we're interested in, the dot product result, will be contained in the constant terms of the result of that multiplication, where the $X^{j-i}=X^0$.
199
200In other words, $\langle a, b \rangle = ct(\sigma_{-1}(a(X)) \cdot b(X))$, where $ct$ denotes getting the constant term. That is, applied to the projection case, $\langle \pi_i^{(j)}, s_i \rangle= ct(\sigma_{-1}(\pi_i^{(j)}) \cdot s_i)$.
201
202
203### 2. Johnson-Lindenstrauss projection
204
205The main idea here, is that we will use random linear projections that almost preserve the $l_2$-norm while allowing us to reduce the amount of equations to check, while keeping the bounds in place.
206
207This relies on the Johnson-Lindenstrauss Lemma, which basically is used as instead of revealing all the witnes values $s_1, \ldots, s_r$, the verifier samples a random linear map $\Pi: \mathbb{Z}_q^{nd} \longrightarrow \mathbb{Z}_q^{256}$, and then the prover reveals only $\Pi \cdot s$, which has many less elements than the original $s$ vector.
208
209And the Johnson-Lindenstrauss Lemma guarantees that $||\Pi s||$ contains almost the same norm information as $||s||$ with very high probability.
210
211In practice, verifier samples $\Pi_i = (\pi_i^{(j)})_j \in \chi^{256 \times nd}$, the prover computes $p_j = \sum_{i=1}^r \langle \pi_i^{(j)}, s_i \rangle$, and the verifier checks that $||p|| \leq \sqrt{128} \beta$.
212
213
214So at this point, in the family $\mathcal{F}~'$, we have the original constraints, without any projection related stuff:
215
216$$
217f'(s) = \sum_{i, j}^r \textcolor{magenta}{a'_{ij}} \langle s_i, s_j \rangle + \sum_{i=1}^r \langle \textcolor{blue}{\phi'_i}, s_i \rangle + \textcolor{orange}{b'} = 0
218$$
219
220And the projection constraints, which encode the check for the J-L projection in the Labrador constraints shape:
221
222Notice that the projection equation, $p_j = \sum_{i=1}^r \langle \sigma_{-1}(\pi_i^{(j)}), s_i \rangle$ is also
223
224$$\sum_{i=1}^r \langle \sigma_{-1}(\pi_i^{(j)}), s_i \rangle - p_j = 0$$
225
226which looks almost like the Labrador canonical constraints, we just need to add the $a_{ij}$ part. We do it by setting $a_{ij}=0$:
227
228$$
229f_{proj}(s) = \sum_{i, j}^r \textcolor{magenta}{0} \cdot \langle s_i, s_j \rangle + \sum_{i=1}^r \langle \textcolor{blue}{\sigma_{-1}(\pi_i^{(j)})}, s_i \rangle - \textcolor{orange}{p_j} = 0
230$$
231
232this is, we set $\textcolor{magenta}{a_{proj,ij}=0}$, $\textcolor{blue}{\phi_{proj,~i}=\sigma_{-1}(\pi_i^{(j)})}$ and $\textcolor{orange}{b_{proj} = -p_j}$. In this way we have the projection constraints encoded as Labrador constraints.
233
234Recall that both the original $f'(s)$ constraints, and the projection constraints $f_{proj}(s)$ are in the family $\mathcal{F}~'$, so that we care about their constant term being zero, not the full polynomial vanishing.
235
236
237### 3. Aggregation steps
238At this point of the protocol, in the family $\mathcal{F}~'$, we have $L$ original constraints $f'(s)$ and $256$ projection constraints $f_{proj}(s)$. The idea now is to linearly combine them into fewer constraints.
239
240The verifier sends the challenges $\psi^{(k)} \in^R (\mathbb{Z}_q)^L$ and $w^{(k)} \in^R (\mathbb{Z}_q)^{256}$, which the prover will use to compute the random linear combinations of the constraints we have so far, which preserves the validity while reducing the number of constraints.
241
242#### 3.1. 1st aggregation
243
244The prover linearly combines
245
246- the $L$ original constraints from $f'(s)$
247- the $256$ constraints that prove the Johnson-Lindenstrauss projection, $f_{proj}(s)$
248
249as follows
250
251$$
252f''^{(k)}(s) =
253\sum_{l=1}^L \psi_l^{(k)} \cdot f'^{(l)}(s)
254+
255\sum_{j=1}^{256} w_j^{(k)} \cdot f_{proj}(s)
256=
257\\
258= \underbrace{ \sum_{l=1}^L \psi_l^{(k)} \cdot f'^{(l)}(s) }_{(i.)~ \text{lin.comb. of the original constraints}}
259+
260\underbrace{ \sum_{j=1}^{256} w_j^{(k)} \cdot ( \langle \sigma_{-1}(\pi_i^{(j)}), s_i \rangle -p_j) }_{(ii.)~ \text{lin.comb. of the 256 projection constraints}}
261$$
262
263First we will tackle $(i.)$. Recall that $f'(s) = \sum_{i, j}^r a_{ij}' \cdot \langle s_i, s_j \rangle + \sum_{i=1}^r \langle \phi_i', s_i \rangle + b'$, so by distributing the challenge $\psi_l^{(k)}$,
264
265$$
266(i.):~
267\sum_l \psi_l^{(k)} \cdot f'^{(l)}(s) =
268\sum_l \psi_l^{(k)} \cdot \left(
269  \sum_{i,j} a_{ij}^{'(l)} \cdot \langle s_i, s_j \rangle
270  + \sum_i \langle \phi_i^{'(l)}, s_i \rangle - b_0^{'(k)}
271\right)\\
272=
273\underbrace{
274\sum_{i,j} \left( \sum_l \psi_l^{(k)} \cdot a_{ij}^{'(l)} \right) \cdot \langle s_i, s_j \rangle
275}_{(i.A)}
276\underbrace{
277+ \sum_i \left( \sum_l \psi_l^{(k)} \cdot \phi_i^{'(l)} \right) \cdot s_i
278- \sum_l \psi_l^{(k)} \cdot b_0^{'(l)}
279}_{(i.B)}
280$$
281
282For the $(i.A)$ part, we can set
283
284$$\textcolor{magenta}{a_{ij}^{''(k)}} = \sum_{l=1}^L \psi_l^{(k)} \cdot a_{ij}^{'(l)}$$
285
286so that:
287
288$$
289(i.A):~
290 \sum_{i,j} \left( \sum_l \psi_l^{(k)} \cdot a_{ij}^{'(l)} \right) \cdot \langle s_i, s_j \rangle ~=~ \sum_{i,j} \textcolor{magenta}{a''^{(k)}_{ij}} \cdot \langle s_i, s_j \rangle
291$$
292
293
294Now tackle $(ii.)$:
295
296$$
297(ii.):~ \sum_{j=1}^{256} w_j^{(k)} \cdot \big( \langle \sigma_{-1}(\pi_i^{(j)}), s_i \rangle - p_j \big) = \sum_i \langle \sum_j w_j^{(k)} \sigma_{-1}(\pi_i^{(j)}),~ s_i \rangle
298- \sum_j w_j^{(k)} \cdot p_j
299$$
300
301Now let's put together $(i.B)$ and $(ii)$:
302
303$$
304\overbrace{
305  \textcolor{green}{
306    \sum_i ( \sum_l \psi_l^{(k)} \cdot \phi_i^{'(l)} ) \cdot s_i
307  }
308  \textcolor{blue}{
309    - \sum_l \psi_l^{(k)} \cdot b_0^{'(l)}
310  }
311}^{(i.B)}
312+ 
313\overbrace{
314  \textcolor{orange}{
315    \sum_i \langle \sum_j w_j^{(k)} \sigma_{-1}(\pi_i^{(j)}),~ s_i \rangle
316  }
317  \textcolor{red}{
318    - \sum_j w_j^{(k)} \cdot p_j
319  }
320}^{(ii.)}
321=\\~\\
322=
323  \sum_i
324\textcolor{green}{
325    \big\langle 
326    \sum_l \psi_l^{(k)} \cdot \phi_i^{'(l)}
327  }
328  +
329  \textcolor{orange}{
330    \sum_l w_j^{(k)} \cdot \sigma_{-1}(\pi_i^{(j)}), s_i
331    \big\rangle
332  }
333  +
334  \textcolor{blue}{
335    \sum_l \psi_l^{(k)} \cdot b_0^{'(l)}
336  }
337  +
338  \textcolor{red}{
339    \sum_j w_j^{(k)} \cdot p_j
340  }
341$$
342
343without colors:
344
345$$
346=
347\sum_i
348  \big\langle 
349  \underbrace{
350    \sum_l \psi_l^{(k)} \cdot \phi_i^{'(l)}
351    +
352    \sum_l w_j^{(k)} \cdot \sigma_{-1}(\pi_i^{(j)})
353    }_{\phi_i^{''(k)}},
354    s_i
355  \big\rangle
356  +
357  \underbrace{
358    \sum_l \psi_l^{(k)} \cdot b_0^{'(l)}
359    +
360    \sum_j w_j^{(k)} \cdot p_j
361  }_{b_0^{''(k)} ~\text{(constant term)}}
362  \\
363  =
364  \sum_{i=1}^r \langle \textcolor{blue}{\phi_i^{''(k)}}, s_i \rangle - \textcolor{orange}{b_0^{''(k)}}
365$$
366
367So by putting it together with the $(i.A)$ part, we get the full $f''^{(k)}(s)$ aggregated constraint:
368
369$$
370\boxed{
371f''^{(k)}(s) =
372\overbrace{
373\sum_{i,j=1}^r \textcolor{magenta}{a_{ij}^{''(k)}} \cdot \langle s_i, s_j \rangle
374}^{(i.A)}
375+
376\overbrace{
377\sum_{i=1}^r \langle \textcolor{blue}{\phi_i^{''(k)}}, s_i \rangle - \textcolor{orange}{b_0^{''(k)}}
378}^{(i.B) + (ii.)}
379}
380$$
381
382such that $ct(f''^{(k)}(s)) = 0$.
383
384
385<br>
386
387Right now, $f''^{(k)}(s)$ is a constraint where only the constant term evaluates to zero (ie. it is a constraint from the $\mathcal{F}'$ family). However, for the next aggregation step, we need it to be a *completely vanishing* polynomial, that is, a function from the $\mathcal{F}$ family. 
388
389To do so, the prover takes the integer constant $\textcolor{orange}{b_0^{''(k)}}$ and extends it into a full polynomial $\textcolor{orange}{b''^{(k)}}$ so that the newly formed function $f''^{(k)}(s)$ evaluates exactly to zero. The prover then sends these full $b''^{(k)}$ polynomials to the verifier. 
390
391To ensure that the prover isn't cheating by just making up a polynomial that matches the equation, the verifier will check that the constant coefficient of the prover's $b''^{(k)}$ corresponds to the $b_0^{''(k)}$ value that the verifier computes from the public values and challenges, that is $b_0^{''(k)} \stackrel{?}{=} \langle w^{(k)}, p \rangle + \sum_{l=1}^L \psi_l^{(k)} b_0^{'(l)}$.
392
393<br>
394
395Recall that along these past steps, we've defined the new $a_{ij}^{''(k)},~ \phi_i^{''(k)},~ b''$ as
396
397$$\textcolor{magenta}{a_{ij}^{''(k)}} = \sum_{l=1}^L \psi_l^{(k)} \cdot \textcolor{magenta}{a_{ij}^{'(l)}}$$
398
399$$\textcolor{blue}{\phi_i^{''(k)}} = \sum_{l=1}^L \psi_l^{(k)} \textcolor{blue}{\phi_i^{'(l)}} + \sum_{j=1}^{256} w_j^{(k)} \cdot \sigma_{-1}(\textcolor{blue}{\pi_i^{(j)}})$$
400
401$$\textcolor{orange}{b''} = \sum_{i,j=1}^r \textcolor{magenta}{a_{ij}^{''(k)}} \cdot \langle s_i, s_j \rangle + \sum_{i=1}^r \langle \textcolor{blue}{\phi_i^{''(k)}}, s_i \rangle$$
402
403
404#### 3.2. 2nd aggregation
405Till here, the 1st aggregation step has taken a random linear combination of the original constant-vanishing constraints and the projection constraints, and linearly combined them into Labrador-shaped constraints.
406
407Now the idea is to random linearly combine the original fully vanishing constraints $f(s)$, and separately the aggregated $f''(s)$ constraints that come from the original constant-vanishing constraints ($f'(s)$) and projection constraints ($f_{proj}(s)$).
408
409The verifier sends the challenges $\alpha \in^R R_q^K,~ \beta \in^R R_q^{\lceil 128/\log{q} \rceil}$.
410
411Then the prover will compute
412
413$$
414F(s) = \sum_{k=1}^K \alpha_k \cdot f^{(k)}(s) + \sum_{k=1}^{\lceil 128/ \log q \rceil} \beta_k \cdot f''^{(k)}\\
415=
416\sum_{k=1}^K \alpha_k \cdot \left( \sum_{i, j}^r a_{ij} \langle s_i, s_j \rangle + \sum_{i=1}^r \langle \phi_i, s_i \rangle + b \right)
417+
418\sum_{k=1}^{\lceil 128/ \log q \rceil} \beta_k \cdot
419\left(
420  \sum_{i,j}^r a_{ij}^{''(k)} \langle s_i, s_j \rangle + \sum_i^r \langle \phi_i^{''(k)}, s_i \rangle - b_0^{''(k)}
421\right)
422$$
423
424distribute $\alpha_k$ and $\beta_k$ while keeping the witness values separated
425
426$$
427= \sum_{i,j=1}^r
428\underbrace{
429  \left( \sum_{k=1}^K \alpha_k a_{ij}^{(k)}
430  +
431  \sum_{k=1}^{\lceil 128/\log q \rceil} \beta_k a_{ij}''^{(k)}
432  \right)
433}_{a_{ij}}
434\langle s_i, s_j \rangle + \sum_{i=1}^r \langle \underbrace{ \left( \sum_{k=1}^K \alpha_k \phi_i^{(k)} + \sum_{k=1}^{\lceil 128/\log q \rceil} \beta_k \phi_i''^{(k)} \right) }_{\phi_i}, s_i \rangle
435\\
436- \underbrace{ \left( \sum_{k=1}^K \alpha_k b^{(k)} + \sum_{k=1}^{\lceil 128/\log q \rceil} \beta_k b''^{(k)} \right) }_{b}
437$$
438
439$$
440\boxed{
441  F(s) = \sum_{i,j} a_{ij} \langle s_i, s_j \rangle + \sum_i \langle \phi_i, s_i \rangle - b
442}
443$$
444
445again, a Labrador-shaped constraint, which in this case encodes the linear combinations of the original $f^{(k)}(s)$ constraints and the $f''^{(k)}(s)$ aggregated constraints, which for a valid witness it satisfies $F(s)=0$.
446
447
448### 4. Amortization
449
450Now, at this point we have $r$ witness vectors, which in practice it is too much to deal with. Thus, instead of opening the individual inner commitments $t_i$ by sending all the $s_i$ and then checking the constraint $F(s)$, the prover opens a random linear combination
451
452$$z = \sum_{i=1}^r c_i \cdot s_i$$
453
454and its respective committed version
455
456$$\overline{z} = \sum_{i=1}^r c_i \cdot t_i$$
457
458
459with challenge polynomials $c_i \in R_q$.
460
461Then the verifier checks
462
463$$A \cdot z = \sum_{i=1}^r c_i \cdot t_i$$
464
465which should match since $t_i$ are the commitments to $s_i$ such that $t_i = A s_i$, so that
466
467$$A \cdot z = A \cdot \sum_i^r c_i s_i = \sum_i c_i \cdot (A s_i) = \sum_i c_i t_i$$
468
469
470And also checks that $||z|| \leq \gamma$ which comes from the instantiation parameters, to ensure small norm.
471
472<br>
473
474The following step is verifying that $F(s)=0$, but recall that $F(s) = \sum_{i,j} a_{ij} \langle s_i, s_j \rangle + \sum_i \langle \phi_i, s_i \rangle - b$, and the verifier does not know the values of $s_i$ hence can not compute it.
475
476To do the check, both prover and verifier use what the paper calls *garbage polynomials*, but intuitively we can think about them as some auxiliary polynomials to do this final check.
477
478Let the *garbage polynomials* be
479
480$$g_{ij}= \langle s_i, s_j \rangle,~~~~ h_{ij} = \frac{1}{2} ( \langle \phi_i, s_j \rangle + \langle \phi_j, s_i \rangle )$$
481
482for $i,j \in [r]$.
483
484
485The prover will commit to those polynomials early on, before the challenges $c_i$ are generated, so that the prover is not able to select the garbage polynomials based on knowledge of the challenges, which would allow the prover to cheat.
486
487> Observation: the paper does the commitment to the "garbage" polynomials $g$ and $h$ differently at the protocol conceptual explanation of page 14 and at the protocol description of Figure 2 at page 17.
488> 
489> The conceptual explanation describes the second outer commitment $u_2$ as
490> 
491> $$u_2 = C g + D h$$
492> 
493> but later at the protocol description, the commitment to $g$ is moved to the outer commitment $u_1$, leaving only the commitment to $h$ at $u_2$. So the outer commitments end up being
494> 
495> $$u_1 = B \cdot t + C \cdot g = \sum_{i=1}^r \sum_{k=0}^{t_1-1} B_{ik} t_i^{(k)} + \sum_{i \leq j} \sum_{k=0}^{t_2-1} C_{ijk} g_{ij}^{(k)}$$
496> 
497> $$u_2 = D \cdot h = \sum_{i \leq j} \sum_{k=0}^{t_1-1} D_{ijk} h_{ij}^{(k)}$$
498>
499> This is done because the $g_{ij}$ polynomials are independent of all challenges, thus they can be computed at the very beginning of the protocol and included in $u_1$, allowing a slightly better security proof.
500
501Then, the verifier will do the following checks:
502
503$$(i.)~~~ <z, z> = \sum_{i,j=1}^r g_{ij} c_i c_j$$
504
505$$(ii.)~~~ \sum_{i=1}^r \langle \phi_i, z \rangle \cdot c_i = \sum_{i,j=1}^r h_{ij} c_i c_j$$
506
507$$(iii.)~~~ \sum_{i,j=1}^r a_{ij} g_{ij} + \sum_{i=1}^r h_{ii} -b = 0$$
508
509Where $(i.)$ and $(ii.)$ are to check the correctness of $g_{ij}$ and $h_{ij}$ respectively, and $(iii.)$ is checking the $F(s)=0$ equality through the garbage polynomials $g_{ij}, h_{ij}$.
510
511
512
513### 5. Recursion
514
515At this point, the prover has sent the *proof* which consists of $(z, t, h, g)$, and the norm checks get grouped into a single norm check $||z||^2 + ||t||^2 + ||g||^2 + ||h||^2 \leq \gamma^2 + \gamma_1^2 + \gamma_2^2$.
516
517
518The idea now, is to recurse, encoding the protocol checks into new Labrador constraints, and then performing again the protocol.
519
520First, we simplify the target relation, let $v = t || g || h \in R_q^m$, so that the norm check becomes
521
522$$||z||^2 + ||v||^2 \leq \gamma^2 + \gamma_1^2 + \gamma_2^2$$
523
524
525Now we decompose the witness $z = z^{(0)} + b \cdot z^{(1)}$, with $z^{(0)}, z^{(1)} \in R_q^n$, to keep the coefficients with small norm.
526
527Then, the quadratic dot product becomes
528
529$$\langle z, z \rangle = \langle z^{(0)}, z^{(0)} \rangle + 2b \langle z^{(0)}, z^{(1)} \rangle + b^2 \langle z^{(1)}, z^{(1)} \rangle$$
530
531and we can do the norm check as $||z^{(0)}||^2 + ||z^{(1)}||^2 + ||v||^2 \leq \frac{2}{b^2} \gamma^2 + \gamma_1^2 + \gamma_2^2 = (\beta')^2$, which implies $||z|| = ||z^{(0)} + b z^{(1)} || \leq (1+b)\beta'$.
532
533
534Write the vectors $z^{(0)}, z^{(1)}, v$ as concatenations of vectors:
535
536$$
537z^{(0)} = s_1 || s_2 || \ldots || s_{\nu}\\
538z^{(1)} = s_{\nu+1} || \ldots || s_{2\nu}\\
539v = s_{2\nu+1} || \ldots || s_{2\nu+ \mu}
540$$
541
542that is $r' = 2 \nu + \mu$ vectors in total.
543
544
545Observe that the final verifications from the previous section, the checks $(i.),~ (ii.),~ (iii.)$ can be done as dot product constraints (ie. Labrador constraints):
546
547#### encoding check (i.)
548
549from the check $(i.)$, $\langle z, z \rangle = \sum_{i,j=1}^r g_{ij} \cdot c_i \cdot c_j$, since we've decomposed $z = z^{(0)} + b z^{(1)}$ then we have
550
551$$
552\langle z, z \rangle = \langle z^{(0)} + b z^{(1)}, z^{(0)} + b z^{(1)} \rangle\\
553= \langle z^{(0)}, z^{(0)} \rangle + 2b \langle z^{(0)}, z^{(1)} \rangle + b^2 \langle z^{(1)}, z^{(1)} \rangle
554$$
555
556that is, three separate dot products. Then we place
557
558$$
559z^{(0)} ~\text{into}~ s_1', \ldots, s'_{\nu}\\
560z^{(1)} ~\text{into}~ s_{\nu+1}', \ldots, s'_{2\nu}
561$$
562
563so that
564
565$$\langle z^{(0)}, z^{(0)} \rangle = \langle s_1', s_1' \rangle + \langle s_2', s_2' \rangle + \ldots + \langle s_{\nu}', s_{\nu}' \rangle$$
566
567and similarly with $\langle z^{(1)}, z^{(1)} \rangle$
568
569$$\langle z^{(1)}, z^{(1)} \rangle = \langle s_{\nu+1}', s_{\nu+1}' \rangle + \ldots + \langle s_{2\nu}', s_{2\nu}' \rangle$$
570
571and
572
573$$\langle z^{(0)}, z^{(1)} \rangle = \langle s_1', s_{\nu+1}' \rangle + \langle s_2', s_{\nu+2}' \rangle + \ldots + \langle s_{\nu}', s_{2\nu}' \rangle$$
574
575
576So that now, it is a matter of setting appropriate $a_{ij}$ values to reshape the original check into a Labrador-shaped constraint:
577
578- from $1$ to $\nu$: if $i=j$, set $a_{ij}=1,~ 0$ otherwise,
579- from $\nu+1$ to $2\nu$: if $i=j$, set $a_{ij}=b^2,~ 0$ otherwise,
580- from $2\nu$ to $2\nu+\mu$: if $j=i+\nu$, set $a_{ij}=b$. And since the $(a_{ij})$ matrix is symmetric, then $a_{ji}=b$, which implies that when both combined we get $2b$.
581
582Therefore, we can perform the $\langle z, z \rangle$ with the decompositions $z^{(0)},~ z^{(1)}$.
583
584
585#### encoding check (ii.)
586
587The next check is $(ii.)$, $\sum_{i=1}^r \langle \phi_i, z \rangle \cdot c_i = \sum_{i, j = 1}^r h_{ij} c_i c_j$. Reshape it into
588
589$$\sum_{i=1}^r \langle \phi_i \cdot c_i, z \rangle - \sum_{i, j = 1}^r (c_i c_j)\cdot h_{ij} = 0$$
590
591and, recall that we set
592
593$$
594z^{(0)} = s_1 || s_2 || \ldots || s_{\nu}\\
595z^{(1)} = s_{\nu+1} || \ldots || s_{2\nu}\\
596v = s_{2\nu+1} || \ldots || s_{2\nu+ \mu}
597$$
598
599also recall that $v=t || g || h$. Thus, similarly as for the check $(i.)$,
600
601- from $1$ to $\nu$: $\phi_i^{(k)} = \sum \phi_i c_i$,
602- from $\nu+1$ to $2\nu$: $\phi_i^{(k)} = \sum \phi_i c_i \cdot b$,
603- from $2\nu$ to $2\nu+\mu$: $\phi_i^{(k)} = - (c_i c_j)$.
604
605
606#### encoding check (iii.)
607
608For the check $(iii.)$, $\sum a_{ij} g_{ij} + \sum h_{ii} - b =0$, recall again that $g_{ij}, h_{ij}$ are inside $v$, so it is just a matter of setting $a_{ij}=a_{ij}$ and $a_{ij}=1$ at their corresponding positions, and $b^{(k)}=b$.
609
610With this, we can encode the checks $(i.),~ (ii.),~ (iii.)$ into the Labraddor constraint shape
611
612$$g^{(k)}(s') = \sum_{i,j=1}^{r'} a_{ij}^{(k)} \langle s_i', s_j' \rangle + \sum_i^{r'} \langle \phi_i^{(k)}, s_i' \rangle - b^{(k)} = 0$$
613
614with $s' := z^{(0)} || z^{(1)} || v$, where $v=t ||g||h$.
615
616
617#### encoding commitments checks
618
619Similarly we encode he commitments checks. We had $Az = \sum c_i t_i$, which we can do in a dot product constraint as
620
621$$\langle A_{row}, z \rangle - \sum c_i \cdot ~ (t_i)_{row} = 0$$
622
623which in a similar fashion as the checks $(i.), (ii.), (iii.)$, we can reshape it into a Labrador constraint, since the inner commitments $t_i$ are placed inside $v$.
624
625<br>
626
627And for the outer commitments $u_1,~ u_2$, as we saw in the section [[4. Amortization](#4.-amortization)] we want
628
629$$
630u_1 = B \cdot t + C \cdot g\\
631u_2 = D \cdot h
632$$
633
634which we can encode as
635
636$$
637\langle B_{row}, t \rangle + \langle C_{row}, g \rangle = (u_1)_{row}\\
638\langle D_{row}, h \rangle = (u_2)_{row}
639$$
640
641which, as before, we can also reshape into the dot product Labrador constraints.
642
643<br>
644
645The paper mentions that [6 or 7](https://giphy.com/gifs/67-six-seven-john-chungus-08uBcURaMq6vA93TGc) iterations of the recursive protocol give the best results, where at each recursion the witness shrinks down from $|s^{(i)}|$ into $|s^{(i)}|^{2/3}$.
646
647
648## Conclusions
649
650It has been very interesting to see how a lattice-based SNARK works, its machinery and tricks.
651Also, Labrador is of special interest because it was a big step forward on lattice-based SNARKs since it has good proof sizes; asymptotically of $\mathcal{O}(\log n)$, and for $2^{16}$ R1CS constraints, the paper reports proof sizes of 54 kbytes.
652
653<div style="text-align:center;">
654<a target="_blank" href="img/posts/labrador/proof-sizes-table.png">
655  <img style="width:80%"
656  src="img/posts/labrador/proof-sizes-table.png"></img>
657</a>
658<br>
659<i style="color:#374072">table from the Labrador paper</i>
660</div>
661
662<br>
663
664An interesting thing in Labrador is the capacity to mix binary and non-binary R1CS constraints, which get reshaped into the $f(s)$ and $f'(s)$ Labrador constraints. This is nice, because for many zk-circuits we want to prove binary-based operations (such as traditional hashes), while doing arithmetic logic, and in Labrador we can mix both in parallel.
665
666Other post-quantum safe SNARK schemes are based on hashes (eg. STARKs), widely used in the industry; but what seems interesting of the lattice-based cryptography is that lattices have more algebraic structure, and while a bit less developed in production than hash based proofs, they have interesting potential.
667
668I've enjoyed studying Labrador, and definitely I'll keep exploring other lattice-based schemes while also going a bit down to the math behind them.
669
670