Content pfp
Content
@
0 reply
0 recast
0 reaction
Zk pfp
Zk
@risotto
ZK Scholars Assembly Revision 3 - More Elliptic Curves, Parings and KGZ Other than Weierstrass form of elliptic curve that is used in Bitcoin & Ethereum (secp256k1) and TEE & Secure Enclave (secp256r1), there are also other forms of elliptic curves such as Montgomery Curves, Edwards Curves and Twisted Edwards Curves. Montgomery curves have no point at infinity, they can also do arithmetic operations that are more computational efficient such as differential addition and Montgomery ladder. For example scalar multiplication kP where k is a large integer. In the Weierstrass form, this involves numerous point additions and doublings, each requiring multiple field inversions. In the Montgomery form, the Montgomery ladder performs this operation using only field multiplications and squaring, significantly reducing the computational overhead.
1 reply
0 recast
0 reaction
Zk pfp
Zk
@risotto
This not only improved efficiency of computation but also provide better security against side-channel attack such as timing attacks where an attacker infers k bits by measuring time taken for each operations as repeatedly adding a point P is based on bits of scalar k. A Montgomery curve can transform into and from Edwards curve (x^2 + y2 = 1 + d(x^2)(y^2)) with a projection function Z. For example Curve25519 (Montgomery curve) can transform into Ed25519 (twisted Edwards curve). Twisted Edwards curve is formed by adding extra coefficient a, ax^2 + y2 = 1 + d(x^2)(y^2). Thanks to geometrical symmetry (circle-like graph), one standout feature of Edwards curves is unified addition formula, this means the same formula can be used for both point addition and point doubling operations. Unlike Weierstrass form required different formulas. Twisted Edwards curves can achieve higher performance for cryptographic operations by adding flexibility with additional parameter a.
1 reply
0 recast
0 reaction
Zk pfp
Zk
@risotto
By having simplified, standard operations, eliminating exceptional cases (no point of infinity), Edwards curves provides better security than Weierstrass curves. This is also why EdDSA has better security and performance than ECDSA. What is KGZ? KGZ is a polynomial commitment scheme that is widely used in ZK protocols. What it does is essentially allows a party to commit to a polynomial and later prove to any verifier that an evaluation of the polynomial at specific point is correct. A prover wants to prove that he has a polynomial f(x) ∈ F[X]<d and f(x1) = y1. The verifier then picks a random r and compute set of powers of r on elliptic curve point groups {g, gr, gr^2, gr^3, …, gr^(d - 1)}. Then verifier request prover to compute g^f(r) using the set of points and also request a quotient polynomial g^q(x) s.t. f(x) - y1 = (x - x1) * q(x) The verifier then verifies by checking: f(r) - y1 = (r - x1) * q(r) g^f(r) / g^(y1) = g^(r - x1) * g^q(r)
1 reply
0 recast
0 reaction
Zk pfp
Zk
@risotto
To complete this, we need pairing function e to check bilinearity: e(g^f(r) / g^(y1), g) = e(g^(r - x1), g^q(r)) A pairing function e is a function that maps two points from elliptic curves to another finite field element (or target group point) G X G -> Gt. The two points can be of the same group (symmetric pairing) or from different groups (asymmetric pairing). Bilinearity property means that for all P, Q, R ∈ G and scalars a, b: e(aP + bQ, R) = e(P, R)^a ⋅ e(Q, R)^b e(P, aQ + bR) = e(P, Q)^a ⋅ e(P, R)^b Notice how the scalars in original groups are related to exponents in target groups! This is exactly how the verifier verifies in the last step of KGZ.
1 reply
0 recast
0 reaction