2
$\begingroup$

Given two field elements as input of Arithmetic Circuit (consists of adding gates and multiplicating gates only), how could I output the bigger one? Or, how to place the gates in order to distinguish which one is bigger (using Arithmetic Circuit)? Could you please describe the method in picture?

In Zero-knowledge Proof, the statement to be proved would be described in a standard form first, such as Boolean Circuit / Arithmetic Circuits / R1CS. General proof schemes could deal with any kind of statement, so that any type of function could be conveyed by Arithmetic Circuit. Then, if Boolean Circuit can implement the comparison function, I think Arithmetic Circuit would definitely be able to do the same thing. A majority of online materials look like "you can compile any statement into R1CS easily". But when it comes to the specific way to implement a function (I mean, how to place the gates in a circuit), there are few discussions on the Internet. Most results from the search engine are "full-adder" "xor gate" "introduction to zk-SNARKs" "verilog" "circuit complexity" and so on, which is not helpful enough.

I know comparison can be implemented easily on Boolean Circuits, but I still need to implement it on Arithmetic Circuits, which consists of adding gates and multiplicating gates only. I used to think it is an easy target, but I discovered that I probably underestimated its difficulty. My classmate told me that "such an Arithmetic Circuit would be very complex", but even then, I am still wondering how complex (in specific) it would be. There is another Q&A on StackExchange (Boolean Circuits vs Arithmetic Circuits) that has introduced a method to emulate boolean gates on Arithmetic Circuits, which I thought would be helpful to me. However, I could not verify its validity. For example, 2 and 5 = 0010 and 0101 = 0000, but according to the QA, the result would be 2·5=10 (1010).

I want to implement a comparison function described above using Arithmetic Circuit (just ciruit, no need to be zero-knowledge), could you please teach me how to place the adding gates and multiplicating gates? If it would be a very complex circuit, how to analyze that how many gates are exactly enough?

Improve this question
$\endgroup$
2
  • $\begingroup$ I believe the question can't be answered as is because "the bigger one" is not well-defined in the context. Problem is, a field does not come with a total order or even the notion of "negative" (which perhaps would allow to define some good-enough order "A≤B" as "(-1)*A+B is non-negative"). If you can somewhat define an order, then "the bigger one of A and B" could be "(A≤B)*((-1)*A+B)+A". Update: When "the bigger one" is defined, for any fixed field, if we don't care for the circuit size, we can make a circuit as desired. $\endgroup$
    – fgrieu ♦
    Mar 10 at 8:54
  • 1
    $\begingroup$ That's true in general, but in prime order fields it is relatively common to map the field elements to integer, either in $[0, p-1]$ or in $[-p/2, p/2]$, in which case the notion of comparison can just be the standard integer comparison, which of course depends on the choice of the mapping. $\endgroup$
    – Geoffroy Couteau
    Mar 10 at 9:25

2 Answers 2

Reset to default
2
$\begingroup$

As far as I know, "the bigger one" has no canonical definition in a finite field. At least, there is no total order compatible with addition, that is such that $a\le b$ and $a'\le b'$ implies $a+a'\le b+b'$ (as we have in fields $\mathbb Q$ and $\mathbb R$).

Thus, we first need to select some ordering criteria. A most natural candidate definition uses a mapping of the field $\mathbb F_{p^k}$ to $[0,p^k)$ (the non-negative integers less than $p^k$) as follows: consider the polynomial representing a field element as with all the terms of the polynomial in $[0,p)$, and evaluate that polynomial‡ in $\mathbb N$ at point $p$. We then build a total order on the field from the canonical total order in $\mathbb N$.

Once we have defined "the bigger one" one way or another, that defines a $\max$ function from $\mathbb F_{p^k}\times\mathbb F_{p^k}$ to $\mathbb F_{p^k}$. And there is a generic method to implement any function with such domain using an arithmetic circuit, as a polynomial of the two inputs:

  • for each $J$ in the field we can build a Lagrange polynomials $P_J(X)$ with coefficients in the field evaluating to $1$ if $X=J$ and $0$ otherwise, per$$P_J(X)=-\prod_{I\ne J}(X-I)$$
  • and now $\max(X,Y)$ can be built as a polynomial, per$$\max(X,Y)=\sum_{I,J}\bigl(\max(I,J)\,P_I(X)\,P_J(Y)\bigr)$$

This polynomial can be developed into the sum of terms $U_{i,j}\,X^i\,Y^j$ with $i,j\in[0,p^k)$ where $U_{i,j}$, $X$ and $Y$ are elements of the field $\mathbb F_{p^k}$. At least $U_{0,0}$ is zero, and $U_{i,j}=U_{j,i}$.

Example: For field $\mathbb F_7$ and the above definition, $\max(x,y)$ is $(3 x^6 y^2+3 x^6 y+x^5 y^3+6 x^5 y+4 x^4 y^4+3 x^4 y^2+x^3 y^5+3 x^3 y^3+3 x^3 y+3 x^2 y^6+3 x^2 y^4+x^2 y^2+3 x y^6+6 x y^5+3 x y^3+2 x y+x+y)\bmod 7$.

I wonder if there are much simpler expressions of that polynomial, and/or if one even simpler can be made by loosening the order.

[Clarified] I'm willing to trust the other answer+comment's statement that it's provably impossible to craft an arithmetic circuit of size polynomial in $k\log p$ that implements $\max(X,Y)$ as defined above.

‡ For $k=1$, this is comparison in $[0,p)$. For $p=2$, this is unsigned binary conversion then comparison in $[0,2^k)$. More generally this is base-$p$ conversion then comparison in $[0,p^k)$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ No need to trust anyone in your last sentence: With $\le$ you can define equality, and "not equal 0" is given by the monomial $X^{p^k-1}$. Anyway, orders on finite fields that are not prime fields, look somehow arbitrary to me (the two orders on prime fields given in Geoffroy's comment feel at least halfway natural to me). $\endgroup$
    – garfunkel
    Mar 13 at 14:56
  • 1
    $\begingroup$ @garfunkel: I do not follow you. The result you state proves that $X\ne 0$ can be implemented with an arithmetic circuit of size $2k\log p$ field multipliers, when the proposition I tend to trust at face value is that $\max(X,Y)$ can't be implemented by a circuit of size polynomial in $k\log p$. What's your position on that? We agree on arbitrariness of the order I consider when when $k>1$. $\endgroup$
    – fgrieu ♦
    Mar 13 at 15:11
  • $\begingroup$ You're right, the claim is deeper. $\endgroup$
    – garfunkel
    Mar 13 at 15:51
  • $\begingroup$ Thank you very much. As a conclusion, in a Galois Field where p is extremely large (such as $\mathbb{F}_{2^{381\ }}$), the arithmetic circuit for polynomial max(x,y) (as there would be too many terms) would be too large to be applied, right? $\endgroup$
    – Yiyi
    Mar 14 at 3:16
  • 1
    $\begingroup$ @Yiyi: $\mathbb F_{2^{381}}$ is $\mathbb F_{p^k}$ with $p=2$, so $p^k$ (but not $p$) is large. As far as I can tell, yes, the arithmetic circuit for polynomial $\max(x,y)$ as I have defined it would be too large for practice. However I have no proof, I have not even tried for smaller fields like $\mathbb F_{2^4}$, and perhaps defining the order otherwise would allow a practicable construction. $\endgroup$
    – fgrieu ♦
    Mar 14 at 7:45
3
$\begingroup$

You have misread my answer here. When converting a boolean circuit into an equivalent arithmetic circuit, you need to

(1) Take your inputs over the field and convert them into bitstrings (e.g. through their integer representation if you use a prime order field)

(2) Encode each bit individually as the 0 or 1 element of the field

(3) Emulate the standard boolean basis $\{\mathsf{not}, \wedge, \oplus\}$ using arithmetic operations. Concretely:

  • $\mathsf{not}(x) = 1-x$
  • $x \wedge y = x \cdot y$
  • $x \oplus y = x + y - 2x\cdot y$,

where $-, +,\cdot$ are substraction, addition, and product over the field. Here, the operations are only performed on individual bits $x$ and $y$ (encoded as the 0-element or the 1-element of the field).

Back to your question: it is not possible to write an arithmetic circuit that will directly take as inputs two field elements and output the result of the comparison (there are impossibility results for that, though I don't have a pointer in mind right now).

EDIT: more precisely, this is possible, but only for arithmetic circuits over small fields. Concretely, the size of the circuit might blow up by a factor proportional to the field size $|\mathbb{F}|$, which becomes exponentially large as soon as we use exponential-size fields.

If you want instead the blow-up to be polynomial in $\log|\mathbb{F}|$, you need to first do the bit decomposition of the (representation of your) field elements, and input the individual bits of the representation to the arithmetic circuit. Then the arithmetic circuit can emulate an arbitrary boolean circuit of your choice, such as comparison, with only a $\mathsf{poly}(\log|\mathbb{F}|)$ slowdown.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ By a theorem of Lagrange, we can write an arithmetic circuit that implements any arbitrary function from a finite field to itself (as a polynomial of degree less than the field order). That can be extended to build any function of two variables, including whatever definition of $\max$ we select. Thus "it is not possible to write an arithmetic circuit…" is only if we want a limit to the size of the circuit when the field size grows. $\endgroup$
    – fgrieu ♦
    Mar 10 at 13:19
  • 1
    $\begingroup$ Of course, sorry. I meant polynomial-size circuits for general fields (which can be exponentially large). $\endgroup$
    – Geoffroy Couteau
    Mar 10 at 13:38
  • $\begingroup$ Thank you very much, your transformation method is correct and helpful. Here I have an additional question. The process of "converting a field element into bitstrings" cannot be conveyed by arithmetic circuits, is it? (such as 7 → 0111) Similarly, the process of "taking value from the second (large) bit of a field element" cannot be conveyed by arithmetic circuits, is it? This question matters for me, because if it cannot be conveyed by adding gates and multiplicating gates, then it means that the whole process cannot be verified using a sumcheck protocol. $\endgroup$
    – Yiyi
    Mar 14 at 2:29
  • $\begingroup$ @garfunkel yes, this is what I meant. I will edit :) $\endgroup$
    – Geoffroy Couteau
    Mar 14 at 9:45
  • 1
    $\begingroup$ @Yiyi: in general, computing the bit decomposition of a field element requires an arithmetic circuit size proportional to $|\mathbb{F}|$ at least. So, it will have exponential cost (hence be infeasible) over a large field, but can be done over a small field. As for your sumcheck protocol, it depends on how you use it, can't the witness be directly seen as the list of $0,1$ bit-encoding over the field? I.e., can't you push the conversion out of the sumcheck protocol itself? $\endgroup$
    – Geoffroy Couteau
    Mar 14 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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