# Investigation report on the use of SIS to build fast SNARKs

## TLDR

As part of o ur work on zk-EVM and zk-Rollups, we have been investigating new ideas to build fast SNARK prover schemes and this post present an approach that retained our attention and that would like to share. We discuss the use of SIS (short integer solution problem) as a collision-resistant hash function and present an example of polynomial commitment construction based on SIS and error-correcting codes.

The construction still contains a lot of moving/undesigned parts and therefore should be seen as an example rather than as a finished product on its own. Our main takeaway (estimations, mostly), is that SIS-based hashes have competitive runtime compared to zk-friendly primitives (Elliptic Curve Operations - SNARK-friendly hash functions) and are nice to represent in an arithmetic circuits.

## Short Integer Solution

### The SIS assumption in a few words

Let $q$ be an integer (does not have to be prime) and $\Bbb{Z_q}$ be the ring of integers modulo $q$. Let $0 < \beta < q$, $n, m$ integers with $m \text{log}(\beta) > n \text{log}(q)$ and $\|\cdot\|$ be a "norm" of $\Bbb{Z}_q$ (throughout this post, we will assume $\|\cdot\|_\infty$). With the introduced parameters the SIS problem consists in:

> **SIS**
> Given a random matrix $A \in \Bbb{Z}_q^{n \times m}$, find $s \in \Bbb{Z}_q^m$ such that $As = 0_n$ and $\|s\| < \beta$.

A variant of SIS, ring-SIS, restricts the sampling domain of $A$ to a more structured of matrices for which the matrix-vector product is faster. This has the advantage of allowing to use the FFT when computing the product $As$ which yields a faster algorithm. This also allows having a more concise representation for $A$.

> **Ring-SIS**
> Given a fixed polynomial $R$ and the ring $\mathcal{R} = \frac{\Bbb{Z}_q[X]}{R[X]}$. For a random vector $a \in \mathcal{R}^{m / n}$, find a vector $s \in \mathcal{R}^{m / n}$ such all its entries viewed *as vector in coefficient representation* have norm $\leq \beta$ and such that $a . s = 0_\mathcal{R}$

In practice care must be taken when choosing the polynomial $R$ to define the ring. In practice $R(X) = X^n + 1$ with $n$ being a power of two is a common choice. Crucially, the $R(X)$ should be irreducible (for security) and sparse (for efficiency).

Even though, this is not the point of the post, it is worth mentionning that the (ring-)SIS problem is believed to be post-quantum.

### SIS Hash as a SNARK-friendly hash function

From all the above, the following procedure instantiates a collision resistant hash function (**but it should never be used to instantiate a random oracle**).

def Hash(A, x):
    s = split_in_chunks_of_small_norm(x, beta/2)
    return sis(A, s)

Indeed, if one could find two $x_0, x_1$ such that $\mathsf{Hash}(A, x_0) = \mathsf{Hash}(A, x_1)$ then they would have a solution to the (ring-)SIS problem with norm bound $\beta$. Preimage resistance can be derived from a variant (somewhat equivalent) to the SIS problem : the Inhomogeneous (ring-)SIS problem.

On the other, side using SIS as a SNARK-friendly hash function yields interesting performances. Indeed, the hashing procedure consists mainly in splitting a field into chunks of small norm, running FFTs over small ranges and other inner-product computations. All of these can be computed fairly fast compared to other SNARK-friendly hash functions.

#### Concrete algorithm for Ring-SIS

We give an efficient algorithm to perform SIS operations given a hashing key $a$ and a vector of small-norm integers $s$. The algorithm works for the ring obtained by picking $R(X) = X^n + 1$ uses FFT on-cosets

def ring_sis(precomputed_a, s):
    res = [0; n]
    for i in range(0, m / n):
        pol = s[i*n:(i+1)*n]
        pol = fft_oncoset(pol)
        pol = mul_element_wise(pol, precomputed_a)
        res = add_element_wise(res, pol)
    
    # Convert back to coefficients
    res = ifft_fromcoset(res) 
    # Reduce modulo R
    res = sub_element_wise(res[:n], res[n:])
    return res     

Putting aside all the memory costs and assuming a field addition and a field substraction have the same cost, the runtime of ring_sis is $C(q, n, m) = m\left((\frac{\log_2(n)}{2} + 1)M(q) + (\log_2(n) + 1)A(q)\right) = O(m\log_2(n))$ where $M(q)$ is the runtime of a multiplication in $\Bbb{Z}_q$ and $A(q)$ an addition (or substraction).

#### Sample parameters

The performances of the hash function are deeply tied with the parameters of the (ring-)SIS instance. The norm bound $\beta$ impacts how many chunks should be used for each entry of $x$. $n$ impacts the size of the FFTs and the size of the hash. We give below a collection of parameters for (ring-)SIS for various moduli targetting 144 bits of security against lattice reduction and combinatorial attacks.

This taken into account, one can view the following trends on how the parameters interacts (for fixed bit-security)

| Modulus (q) | Hash Size (n) | normBound ($\beta$) |
| ------- | ------------- | ------------------- |
| 2^254 | 2 | 2^2 |
| 2^254 | 4 | 2^3 |
| 2^254 | 8 | 2^4 |
| 2^254 | 16 | 2^6 |
| 2^254 | 32 | 2^10 |
| 2^254 | 64 | 2^15 |
| 2^254 | 128 | 2^22 |
| 2^254 | 256 | 2^32 |
| 2^64 | 32 | 2^4 |
| 2^64 | 64 | 2^6 |
| 2^64 | 128 | 2^10 |
| 2^64 | 256 | 2^16 |
| 2^64 | 512 | 2^22 |
| 2^64 | 1024 | 2^32 |

#### Estimation of the performances and comparison

We estimate the performances of the SIS hash with various parameters (all using the Goldilocks field) and compare them with other hash functions. To obtain these numbers, we count the number of multiplication and additions in the field. And we get a time (in ns) estimate from $0.5 N_{add} + 1.5 N_{mul}$.

We also believe it would be interesting to compare (although it is incomplete) it with other primitives that are common in the ZKP-world, purely in term of *how much they can grind* per second.

| Primitive | Speed (MBytes/sec) | ZK-friendly |
| ---------------------- | ------------------ | --- |
| RescuePrime-64bits-x12 | ~7.2 | Y |
| Poseidon-64bits-x12 | ~3 | Y |
| MSM-Bn254 1M Fe | ~8 | N |
| MiMC7-BN254 | ~3 | Y |
| RC-Concrete | ~30 | Y |
| Sha3 | ~190 | N |
| Blake2b | ~950 | N |
| SIS hash (n=32, b=2^4) | ~54 | Y |
| SIS hash (n=64, b=2^6) | ~69 | Y |
| SIS hash (n=128, b=2^10) | ~96 | Y |
| SIS hash (n=256, b=2^16) | ~153 | Y |

Ring-SIS hashes can get fairly cheaper if we consider that ~50kB is an acceptable hash size (but we need use a modulus actually compatible with the FFT). Example use-case : we want to hash 1Gbytes entries at once, then using a SIS hash + another one for full-compression would work and yield good performances.

### Expressibility in an arithmetic circuit / Composability

In order to express a (ring-)SIS Hashes in an arithmetic circuit, one need to perform:
- chunk decomposition which can be done using Plookup or bit decomposition,
- and a matrix-vector product, a no-brainer if working with R1CS and Groth16, with a modulus equal to the order of the bilinear group.
- a good candidate for custom gates if working with Plonk arithmetizations

If the modulus is different than the one of the underlying R1CS, then there are also *favorable* case. For instance, if the SIS hash is performed over 64bits but expressed on a ~256-bit field R1CS, then one can defer the modulo reduction at the end.

All of this, let us think that concrete SIS-Hash instance would have performances on-par with the popular SNARK/STARK-friendly hash functions.

## Existing protocols are not yet practical for direct deployment on Ethereum

A first and natural question one can ask about using lattice assumptions, is what type of protocol can we use to build SNARKs and get arguments of knowledge.

Creating efficient argument of knowledge for SIS is a very active area of research and is a difficult problem. Indeed, in order to do so, one need to show that they know some secret $s$ such that $As = t$ and such that $s$ is small. Doing so is not as easy as it seems. In particular, a lot of the issues stems from the fact that a linear combination $s = a s_0 + b s_2$ usually does not have a small norm. When $a$ and $b$ are small, we have that $s$ is somewhat small but larger than $s_0$ and $s_1$. In short, it's more structured than a hash (let say sha3), but there is no nice group structure.

We will not describe of all the state of the art for all the protocol that have discovers but we will give a few takeaway on the limitations of the proof system for SIS that we found.

* **Relaxation** : often, the protocol can only prove that the prover knows a witness $s$ small such that $As = ct$ where $c$ belongs in a set of small elements. It makes the soundness analysis of composite protocol including relaxed-proof of knowledge hard to analyze. It is also, unclear how hard it is for a malicious prover to pass the protocol without knowing the actual secret.
* **Slackness** : in order to a secret of small norm $\beta$, one need to use a SIS instance with norm $\beta' = \kappa \beta \land \kappa > 1$. Even though, this is not as much a theoritical issue as *relaxation*, the norm bound is a very sensible parameter in the SIS security : adapting the SIS instance to withstand a slack of 1000 will have a cost on the other parameters in practice (the hash size).
* **Soundness error** : the protocol may have a small soundness and fixing this issue implies doing many parallel repetition. This has very direct cost on every aspect of the performances of the protocol.
* **Linear verifier runtime** : the protocol may run in time linear of the verifier, which is a problem on its own.

Because of these current limitations in the lattice world, none of the schemes we found in the litterature would really be practical on Ethereum today. This will likely improve over the coming years though. But this does not prevent SIS hash functions from having interesting application as a SNARK-friendly hash function.

## An example of construction using SIS

We describe a protocol which is a variant of other protocol that have been such as Ligero, Brakedown or Orion. It also bears similarities with the protocols for data-availability based on erasure codes.

We pick $\mathcal{C}$, a linear erasure code, with rate $\rho = \frac{|\text{message}|}{|\text{codeword}|}$ and relative distance $\delta = \frac{\text{distance}}{|\text{codeword}|}$.
The erasure-code and the polynomial arithmetic must be instantied over a common field of order $p$, but it can be totally unrelated to the SIS instance modulus $q$.

### Commitment

Given a finite field $\Bbb{F}$. A prover $\mathcal{P}$ wants to commit to a polynomial $P(X) = p_0 + p_1 X + .. p_{nm-1} X^{nm-1}$. By rearranging the coefficients of $P$ in a matrix, we rewrite the equation $P(x) = y$ as follow:

$$\begin{bmatrix}1 & x^n & x^{2n} & \cdots \end{bmatrix} \begin{bmatrix} p_0 & p_1 & \cdots & p_{n-2} & p_{n-1} \\ p_n && \cdots && p_{2n - 1} \\ \cdots &&&& \cdots \\ p_{(m-2)n} && \cdots && p_{(m-1)n - 1} \\ p_{(m-1)n} && \cdots && p_{mn - 1}\end{bmatrix} \begin{bmatrix}1 \\ x \\ x^{2} \\ \cdots \end{bmatrix} = y$$

Which we conveniently rewrite as $L M R = y$

In order to commit to $P$, the prover rearranges its coefficient as in center matrix $M$ (see above). And runs the following procedure

> **SIS Hashing function**
> 1) Encode each rows of the matrix using the erasure code
> 2) Hash each column of the matrix obtained after applying the erasure code (using SIS)
> 3) Use an accumulator (Merkle-tree, whichever you like) and build an accumulator of the SIS hashes. The result is the commitment

The entire runtime is dominated by : speed of the hash, speed of the erasure code encoding, rate of the code (the higher the better).

### Interactive protocol

The protocol goes as follow, using the notations above and with $p(r) = \begin{bmatrix} 1 & r & r^2 & \cdots \end{bmatrix}$.

| | $P$ | | $V$ |
| --- | ---------------------------------------- | ----------------------------- | ------------------------------------- |
| 0 | $y_R = MR$ | | |
| 1 | | $y_R \rightarrow$ | |
| 2 | | | test $L y_R = y$ |
| 3 | | | sample $\lambda \in \Bbb{F}$ |
| 4 | | $\leftarrow \lambda$ | |
| 5 | | $u \rightarrow$ | |
| 6 | $u = p(\lambda)M$ | | |
| 7 | | | test $y_L r = L u$ |
| 8 | | | sample $q$ a subset of columns of Encoding($M$) |
| 9 | | $\leftarrow q$ | |
| 10 | $M_q$ the columns $q$ of Encoding($M$) | | |
| 11 | $\pi_H$ opening of the SIS hashes at $q$ | | |
| 12 | $H_q$ the SIS hashes at $q$ | | |
| 13 | | $M_q, \pi_H, H_q \rightarrow$ | |
| 14 | | | Test $r M_q$ consistent with Encoding($u$) |
| 15 | | | Test each $M_q$ (SIS) hash into $H_q$ |
| 16 | | | Test the accumulator proof $\pi_H$ |

We make the following observations:
* Beside (6) and (11) all prover work can be precomputed
* By taking $n = O(m)$. We have that the proof size and the verifier runtime are a $O(\sqrt{deg(P)})$.
* There is a constant number of interaction and they are public-coin, thus we can apply the FS of the protocol. It is however not clear to us what is the most efficient way to do it (8). Fortunately, we only need to open a number of column that is constant in every parameters except $\delta$)

## Feasibility of recursion

Thus, the above protocol could be described as fast prover, but slow (albeit sublinear) verifier. In practice, this protocol is not directly applicable to Ethereum. The idea now, would be to try and make it a fully-succinct SNARK using recursive composition. Intuitively, in order to so, we need proof systems able to prove:
* That some linear relation hold (14 - 15) between committed values
* That some polynomial relation hold (2 - 7 - 14)
* That some values are within a small range (15)
* That a proof of group membership hold (16)
* Sampling of $\lambda$ using FS (3)
* Sampling of a subset in a range of integers using FS (8)

Even though, we do not have at this stage, a clear idea of what is the best way to do it (many possibilities), it is clear to us that this can be done efficiently and that none of the above point is truely a blocker. Thus, we believe that working with SIS and these types of protocol for very large instances (which we encounter in zk-EVM and zk-rollups) can yield very efficient concrete protocols.