The R1CS constraints are expressed over finite fields. Many proofing systems, such as zk-SNARK, use prover keys such as $g^{\alpha^0}, g^{\alpha^1}, ..., g^{\alpha^n}$ where $\alpha$ is a field element. Are these field elements actually integers?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ R1CS stands for Rank 1 Constraint System. I had to google that. $\endgroup$– fgrieu ♦Sep 19, 2021 at 9:26
-
$\begingroup$ A language? What kind of language? "A preprocessing zk-SNARK for the NP-complete language "R1CS" (Rank-1 Constraint Systems), which is a language that is similar to arithmetic circuit satisfiability ...The NP-complete language R1CS" $\endgroup$– Peter MortensenSep 19, 2021 at 14:14
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
If $\alpha \in \mathbb{F}_p$ i.e., the field is a prime field then the exponents are integers modulo $p-1$ since a primitive element $\alpha$ generates the multiplicative group $\mathbb{F}_p^{\ast}$ of order $p-1$.
-
2
-
1$\begingroup$ Subtitle for the answer and above comment [revised and expanded]: yes the $\alpha^i$ are integers. We can equivalently consider them as in $\mathbb Z$, or as integers in range $[0,p)$ where $p$ is the order (number of elements) of the group of powers of $g$ , or when/since $p$ is prime as elements of the finite field $\mathbb F_p$, also noted $\operatorname{GF}(p)$ or $\mathbb Z/p\mathbb Z$. The exponent $i$ itself is an integer defined modulo $p-1$, that is in $\mathbb Z/(p-1)\mathbb Z$, since $p-1$ is the order of the multiplicative group $\mathbb F_p^*$. $\endgroup$– fgrieu ♦Sep 19, 2021 at 12:08
-
-
1$\begingroup$ The only known implementation known is prime order fields, no field extensions (polynomials). The reason is, pairing operation on elliptic curves is required for the main verification equation with popular Groth 2016 sytsem. $\endgroup$ Sep 19, 2021 at 16:07
-
1$\begingroup$ @Sean: as far as I know, if we want to keep that$$g^{\left(\alpha^{i+j}\right)}=\left(g^{\left(\alpha^i\right)}\right)^{\left(\alpha^j\right)}$$and $\alpha$ in a finite field, then $\mathbb F_p$ with $g$ of prime order $p$ is the only option for said field. $\endgroup$– fgrieu ♦Sep 20, 2021 at 7:38
$\begingroup$
$\endgroup$
Group element like $g^{\alpha^k}$ where $g$ is a subgroup generator and field element $\alpha$ is comparable to the challenge of Verifier of Schnorr protocol are used to evaluate polynomials. In particular, $g$ would be an elliptic curve point of a primer order $q$, and $\alpha \in \mathbb{F}_q$ would be a residue modulo $q$. Well, a residue could be considered quite an integer in all practical aspects.
I was pushing this idea even further with an elementary school -level "multiplication by 3" example of an R1CS system without reminding of residues, just to keep it extremely easy and friendly. One could see it at section C "Sudoku" paper followed by entry-level c++/libsnark code, useful for someone new to SNARKs. This paper is about my re-implementation of a private verification of a secret Sudoku solution originally presented at Financial Cryptography 2016, starting from Naor verification method and polynomial set representation.
answered Sep 19, 2021 at 16:01