Score:2

Crypto

A field element as the exponent of a group element

Sean

1/19/23, 1:23 AM

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?

171

0 + 0

finite-field

snarks

fgrieu

1/19/23, 9:26 AM

R1CS stands for Rank 1 Constraint System. I had to google that.

Peter Mortensen

1/19/23, 2:14 PM

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](https://github.com/scipr-lab/libsnark)"*

Score:3

Crypto

kodlu

1/19/23, 8:53 AM

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

0 + 0

Fractalice

1/19/23, 10:12 AM

the exponents are defined modulo p-1

fgrieu

1/19/23, 12:08 PM

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

Sean

1/19/23, 3:55 PM

Many thanks for the clarification.

Sean

1/19/23, 3:59 PM

Just out of curiosity. Since $F_p$ could be defined over other domain, e.g., finite fields over polynomials, which is homomorphic to its counter part in the integer domain. But then, given an element in such a field, I guess it's hard to "map" it back to its integer counter-part. In this case, when people define R1CS, why not directly say that the domain is field of integers like $Z_p^*$?

Vadym Fedyukovych

1/19/23, 4:07 PM

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.

fgrieu

1/20/23, 7:38 AM

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

Score:1

Crypto

Vadym Fedyukovych

1/19/23, 4:01 PM

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.

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: A field element as the exponent of a group element

TH: องค์ประกอบฟิลด์เป็นเลขชี้กำลังขององค์ประกอบกลุ่ม

RO: Un element câmp ca exponent al unui element de grup

RU: Элемент поля как показатель группового элемента

VI: Phần tử trường là số mũ của phần tử nhóm

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.