# 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.

f\in \mathbb{F}^d[X];

6/14/20231. Notation Group elements (curve points) are capitals $K,R,P,\ldots$ Scalars (field elements) are lowercase $s,k,\ldots$ Scalar multiplication in the group is $[k]P$. Vectors are bold: $\mathbf{D}$. Tuples: $\mathcal{C}$ 2. Components 2.1 Cryptographic Primitives Curve $\mathbf{E}$ defined over field $\mathbb{F}_q$ (supposedly BN254) with group of prime order $\mathbb{F}_r$;

5/26/2023Dmitry Khovratovich Problem: whenever we implement an algorithm that works over $Z_{N}$, with $N=2^{16}$ or $N=2^{32}$, we need to reduce all computations modulo $N$ and range-check all variables against $N$. These operations are expensive. We suggest a new scheme that implements the mod-$N$ arithmetic without range checks. 1. State of the art: Simplified Plonk Notation: $N =2^n$. First recall (and simplify) how Plonk arranges its witness.

11/18/2022Zedger tokens are a class of assets that exist in the Dusk blockchain. They are specific in the privacy of transfers and ownership: regular blockchain users can't figure out the balances of other individuals. 1. Genealogy There are several versions of Zedger tokens, each with different functionality. For each asset its governance shall decide which version to use. Upgrade is possible but difficult. This document describes the following versions: Minimal, denoted by ZedMin which supports: Asset transfers between users;

8/15/2022
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up