2
$\begingroup$

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?

Improve this question
$\endgroup$
2
3
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ the exponents are defined modulo p-1 $\endgroup$
    – Fractalice
    Sep 19 at 10:12
  • 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 at 12:08
  • $\begingroup$ Many thanks for the clarification. $\endgroup$
    – Sean
    Sep 19 at 15:55
  • 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$
    – Vadym Fedyukovych
    Sep 19 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 at 7:38
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.