2
$\begingroup$

I am following Vitalik Buterin's article to study zk-SNARKs recently.

I can understand the main procedure of zk-SNARKs when given example equation x**3 + x + 5 == 35. However, in cryptography, most equations contain exponents. For example, the prover may want to prove the knowledge of $a$ in $g^a=A$. In this case, an arithmetic circuit seems hard to be built by multiplication gates (since the number of multiplication gates is not fixed).

Then I think of elliptic curve, which can transform $g^a=A$ into $a\cdot g=A$ where $g$ is an elliptic curve point. By doing so, it suits the *form of multiplication gate. But this brings up another problem: the multiplication is actually an elliptic curve operation instead of basic arithmetic.

Therefore, I wonder how exponents and group operations can be transformed into arithmetic circuits.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Does this answer your question? Zero knowledge proof for a discrete logarithm $\endgroup$
    – Gareth Ma
    Commented Aug 9, 2023 at 5:53
  • $\begingroup$ @GarethMa Thanks. But that is not exactly what I am looking for. I know there are simple ZKPs for a discrete logarithm. My question is: if I want to prove the knowledge of discrete logarithm using zkSNARKs, I have to convert it into an arithmetic circuit at the setup phase. So, how can I convert the exponent (or logarithm) to an arithmetic circuit with only addition and multiplication gates? $\endgroup$
    – Z. Chen
    Commented Aug 10, 2023 at 8:02
  • $\begingroup$ AFAIK you can't? $\endgroup$
    – Gareth Ma
    Commented Aug 10, 2023 at 11:15

1 Answer 1

Reset to default
1
$\begingroup$

$1)$ Why no exponentiation provided?

$A)$ Exponentiation is multiplication.

$5^4 = 5\star5\star5\star5$ (4 times)

So any exponentiation can be done using the multiplication gate

$2)$ How do scalar multiplication in elliptic curves using the addition & multiplication gates?

$A)$ First of all, there is no multiplication operation in the Elliptic Curve Group - the Elliptic Curve group supports only the addition operation. Scalar multiplication is actually addition. Elliptic Curve Group has formulas for addition of two points & also point doubling (doubling is addition of a point to itself).

Assuming $P=(x_1,y_1)$, $Q=(x_2, y_2)$, then you can compute

  1. Addition ($P \ne Q$)

$R= (x_3, y_3) = P + Q$

  1. Doubling (Addition where $P = Q$)

$R = 2P = 2Q = P + Q$

There are formulas for this

enter image description here

If you check the formulas it involves numerical addition & subtraction (which can be done with the addition gate of a circuit.

The division is actually multiplication by the inverse. So you have first calculate the inverse of $(x_2 - x_1)$ or $2y_1$ first in the finite field which again needs to be broken into basic operations (numerical addition/multiplication). And then the whole formula becomes something which can be just done using addition & multiplication gates.

So the addition, scalar multiplication etc are all notational operations which have to be broken down to basic arithmetic operations & then are done using circuit gates.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 1) Why no exponentiation provided? Indeed exponentiation can be done using the multiplication gate. But things are different when using zkSNARKs. In zkSNARKs, the witness (hidden information) should be the input of a circuit. E.g. $5^4=625$ where 4 is the witness. And the circuit itself is public. Then obviously, if I give a circuit containing 4 multiplication gates of the same input 5, anyone would know my witness. 2) The formulas solve my second question. I can see basic arithmetic operations can be used to do scalar multiplication. $\endgroup$
    – Z. Chen
    Commented Aug 10, 2023 at 12:10
  • $\begingroup$ And may I ask a little additional question: Changing the exponent operations in $Z_p$ to scalar multiplications of elliptic curve group for the purpose of using zkSNARKs is just my idea. Does it really work like this in reality? $\endgroup$
    – Z. Chen
    Commented Aug 10, 2023 at 12:20
  • $\begingroup$ In group theory, the multiplication & additional operations are actually notational - they may not actually mean addition or multiplication. As you see in Elliptic curve groups, addition is actually some other formula & not arithmetic addition. Even there some choose to write the scalar multiplication $nG$ as $G^n$ - you will find lots of cryptographic documents which use $G^n$ for scalar multiplication even though there is no actual exponentiation (there is even no notational exponentiation in a additive group). In group theory all operations are notational. $\endgroup$
    – user93353
    Commented Aug 10, 2023 at 12:25

Your Answer

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

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