# Circuit for Batch Verification of Falcon Signatures

## 1. Notation

* $n$ -- ring degree (512 or 1024)
* $q$ -- modulus $=12289 = 3\cdot 2^{12}+1$
* $\widehat{\beta} = \lfloor\beta^2\rfloor$ -- max norm (34 034 726 or 70 265 242)
* $\phi=X^n+1$

## 2. Single Signature Verification

Inputs:
* $r\in Z_2^{320}$
* $m$ -- bytestring
* $s$
* public key $h\in Z_q[X]/\phi$

Procedure:
1. $c\in Z_q[X]/\phi\leftarrow HashToPoint(r||m)$:
* Iterate SHAKE-256 on $r||m$;
* Extract 16 bits as $b$. If the number $b$ is $<3q$, take $b\bmod q$ as
a polynomial coefficient.
2. $s_2\in Z_q[X]/\phi\leftarrow Decompress(s)$. Reject invalid $s_2$.
3. $s_1 \in Z_q[X]/\phi\leftarrow c-s_2h$.
4. Normalize $s_1$: subtract $q$ from each coefficient that exceeds $\lfloor q/2\rfloor$.
5. Compute $A=||(s_1,s_2)||=\sum_i (s_{1,i}^2 +s_{2,i}^2)$.
6. If $A^2\leq \widehat{\beta}$
* then ACCEPT
* else REJECT.

Modified procedure:

3. Sample $z$ points $\alpha_1,\alpha_2,\ldots,\alpha_z$. Verify the statement $s_1 = c-s_2h$ on these $z$ points. If points are sampled via Fiat-Shamir, we need $z = \lambda /\log_2 \frac{q}{n}$ points, otherwise we need $n+1$ points.

## 3. Circuit for Batch Verification

### 3.1 Same $r$ and $m$ values for all signatures.

In this case Aggregator passes $r,m$ in the cleartext and both Verifier and Aggregator
can compute $c$ off-circuit.

#### Parameters
* $\ell$ --- number of signatures aggregated. The $i$-th signature is denoted as $(r,s[i])$;
* $r$ --- the scalar field $\mathbb{F}$ size of the proof system (a number of about 254 bit size).
* $w$ --- the number of points in $Z_q$ necessary to check the equality of degree $n$ polynomials with security level $\lambda$. Computed as
$$
z = \lambda /\log_2 \frac{q}{n}
$$

#### Committed Inputs

* $C$ is a commitment to $r,\{s_2[i]\}$

#### Precomputation

* Compute $\alpha_1,\alpha_2,\ldots,\alpha_s \in Z_q \leftarrow Hash(C)$.

#### Public Inputs
* Public keys $h[1],h[2],\ldots, h[\ell]\in \mathbb{F}^n$

#### Constants
* Polynomial $c(X)$.
* Evaluations of $h[i]$ at points $\alpha_j$.

#### Private Inputs
* $\{s_2[i]\}\in \mathbb{F}^n$

#### Internal variables
* $\{s_1[i]\}\in \mathbb{F}^n$
* $\{t_{i,j}\}\in \mathbb{F}$

#### Constraints
* Coefficients range check:
* $s_1[i]_j<q$. $14n$ constraints per signature
* $s_2[i]_j<q$. $14n$ constraints per signature
* Polynomial evaluation
\begin{align}
s_1[i](\alpha_j) &= w_{i,j};\;\quad z\text{ linear constraints per signature}\\
s_2[i](\alpha_j) &= w_{i,j}';\;\quad z\text{ linear constraints per signature}\\
h[i](\alpha_j) &= w_{i,j}'';\;\quad \text{ constant}\\
w_{i,j} &= c(\alpha_j)-w_{i,j}'\cdot w_{i,j}'' + q\cdot t_{i,j};\;\quad z\text{ multiplicative constraints per signature};\\
|t_{i,j}|&<nq+2n+1;\quad z(14+ \log n)\text{ multiplicative constraints per signature};\\
\end{align}
Cost is $z(15 + \log n)$ mult constraints per signature.
* Normalization:
* Sign of $s_1[i]_j$ can be obtained for free from the range check (see above);
* The rest is $1$ linear constraint per signature.
* Bounding
* Computation ($2n$ multiplicative constraints per signature)
$$
A^2 = \sum_j s_1[i]_j^2 + s_2[i]_j^2
$$
* Bound $A^2 \leq \widehat{\beta}$ -- 25 or 26 mult constraints per signature.

In total we have $30n+z(15+\log n)$ mult constraints

For Falcon-512 and 128-bit security we have $z=29$ and thus totally about 16056 mult constraints. For Falcon-1024 we get $z=37$ and thus about 31645 constraints.

### 3.2 Distinct $r$ and $m$ values for all signatures.

In this case still both Verifier and Aggregator can compute $c$ polynomials off-circuit but they are distinct. The circuit construction does not change much except that we replace $c(\alpha_j)$ with $c[i](\alpha_j)$ (both sets are constants). The number of constraints does not change then.