Is security of zk-SNARKS related to the size of the arithmetic circuit they evaluate?

Question

In the context of zk-SNARKS, we are given an arithmetic circuit $C$, public outputs $y_1, \ldots, y_n = \mathbf{y}$ and some public inputs $x_1, \ldots, x_ℓ$. The prover wants to prove knowledge of some extra secret inputs $s_1, \ldots, s_m$ such that if one were to evaluate the circuit $C$ on inputs $x_1…,x_ℓ,s_1,…,s_m$ the result would be $\mathbf{y}$.

In some application like in HALO, the recursion property depends on the size of the arithmetic circuit being evaluated. However it does not seem to be related to the security of the scheme, fixed at roughly 128bits. If so, given a certain security level $\lambda$, can one create a zk-SNARK with any circuit size? (granted that the circuit does verify the "valid assignments" we want provers to have)

Answer 1

I think there is not necessarily immediate relationship between security of zk-SNARKs and the size of the arithmetic circuit. Mostly the security of zk-SNARKs depends on your security parameter, your cryptographic assumptions and what kind of security properties you want to achieve. In contrast, the size of the arithmetic circuit is more related to the efficiency of zk-SNARKs, such as prover/verifier running time and proof size. For sure sometimes if you need some stronger security property, for example, you want to achieve universal and updatable CRS, this would lead to a larger arithmetic circuit

Answer 2

We have polynomials identity \begin{equation} A(x) \cdot B(x) - C(x) \equiv h(x) Z(x) \end{equation} with $\deg(Z(x)) = n$, $\deg(A(x)) = \deg(B(x)) = \deg(C(x)) = n-1$. It follows, there are at most $2n-2$ roots. It also follows, soundness error is at most $\frac{2n-2}{q}$, to be compared to $\frac{1}{q}$ of Schnorr protocol, for $q$ being group order.

Informally, even for real large circuits, the impact on false-positive probability is negligible: compare number of equations with a 256-bit-size group order. For a system of million constraints/equations, it would be 250 bits vs 256.