And So Satoshi Selected secp256k1 for Bitcoin, But There Are Better Curves for Smart Contracts

Meet the BN256 Curve
Photo by the blowup on Unsplash

And So Satoshi Selected secp256k1 for Bitcoin, But There Are Better Curves for Smart Contracts

Meet the BN256 Curve

Satoshi Nakamoto selected the secp256k1 curve for Bitcoin, and which was then adopted for Ethereum. The basis of this is the ECDSA signature. But, it is not that scalable for processing. For this, there are more scalable curves around, such as BN128. So, here’s DLEQ (Discrete Log Equality) using the BN256 curve and Keccak-256. These methods make it easy to implement within an Ethereum smart contract.

To implement, Peggy (the ‘Prover’) is able to prove that she still knows her secret — such as knowledge of her private key. Initially, Peggy produces where own challenge (c) and response (r) — these prove the proof of knowledge. Victor (the ‘Verifier’) can then prove this against two public key values that she has already sent to Victor. Peggy has a secret value (x) and then she creates two values xG and xH, and can check that logG(xG)==logH(xH).

Thus, Peggy has her secret (x) and then calculates xG and xH, and where G and H are two random points on an elliptic curve [1]. These are then sent to Victor. For each proof challenge, Peggy generates a random value (w) and computes wG and wH. Next, she creates a challenge (c) and which is a hash of wG,wH,xG,xH:

c=H(wG,wH,vG,vH)

Peggy then responds back with:

r=w−cx (mod o)

and where o is the order of the curve. The proof this then (c,r,vG,vH).

Victor then proves that Peggy still knows the secret with:

vG==rG+c(xG)

vH==rH+c(xH)

If both are equal, Peggy has proven that she still knows x.

This works because:

rG+c(xG)=(v−cx)G+c(xG)=vG−cxG+cxG=vG

Overall, the method is based on the technique described in “Wallet Databases with Observers — David Chaum and Torben Pryds Pedersen” and defined in this [paper].

The BN curve

Elliptic curves are used fairly extensively in public key encryption (such as in Bitcoin and Tor). A BN-curve (Barreto-Naehrig curve) [2] defines an elliptic curve which can be used for pairings that allow for a high security and efficiency level. The curve is defined by y²=x³+a.x+b (mod p), and where we have two curves defined (G_1 and G_2). They can be used to implement Bilinear groups and which are a triplet of groups (G_1, G_2 and G_T). These curves are often used in Pairing-based Cryptography. You can find out more about them here.

On the Ropsten network, there are precompiled contracts for BN256 operation, such as for one at 0x07:

Coding

The following is the code [taken from here][1][here]:

# Code extracted from https://github.com/PhilippSchindler/ethdkg
import web3
from typing import Tuple
import secrets
from py_ecc.optimized_bn128 import G1, G2
from py_ecc.optimized_bn128 import add, multiply, neg, normalize, pairing, is_on_curve
from py_ecc.optimized_bn128 import curve_order as CURVE_ORDER
from py_ecc.optimized_bn128 import field_modulus as FIELD_MODULUS
# from py_ecc.typing import Optimized_Point3D, Optimized_FQ, Optimized_FQ2
from py_ecc.typing import Optimized_Point3D
from py_ecc.fields import optimized_bn128_FQ, optimized_bn128_FQ2
keccak_256 = web3.Web3.solidityKeccak
PointG1 = Optimized_Point3D[optimized_bn128_FQ]
PointG2 = Optimized_Point3D[optimized_bn128_FQ2]
FQ = optimized_bn128_FQ
FQ2 = optimized_bn128_FQ2
H1 = (
    FQ(9727523064272218541460723335320998459488975639302513747055235660443850046724),
    FQ(5031696974169251245229961296941447383441169981934237515842977230762345915487),
    FQ(1),
)
H2 = (
    FQ2((9110522554455888802745409460679507850660709404525090688071718755658817738702, 14120302265976430476300156362541817133873389322564306174224598966336605751189)),
    FQ2((8015061597608194114184122605728732604411275728909990814600934336120589400179, 21550838471174089343030649382112381550278244756451022825185015902639198926789)),
    FQ2((1, 0))
)
def random_scalar() -> int:
    """ Returns a random exponent for the BN128 curve, i.e. a random element from Zq.
    """
    return secrets.randbelow(CURVE_ORDER)
def dleq(x1: PointG1, y1: PointG1, x2: PointG1, y2: PointG1, alpha: int) -> Tuple[int, int]:
    """ DLEQ... discrete logarithm equality
        Proofs that the caller knows alpha such that y1 = x1**alpha and y2 = x2**alpha
        without revealing alpha.
    """
    w = random_scalar()
    a1 = multiply(x1, w)
    a2 = multiply(x2, w)
    c = keccak_256(
        abi_types=["uint256"] * 12,
        values=[
            int(v)
            for v in normalize(a1)
            + normalize(a2)
            + normalize(x1)
            + normalize(y1)
            + normalize(x2)
            + normalize(y2)
        ],
    )
    c = int.from_bytes(c, "big")
    r = (w - alpha * c) % CURVE_ORDER
    return c, r

def dleq_verify(
    x1: PointG1, y1: PointG1, x2: PointG1, y2: PointG1, challenge: int, response: int) -> bool:
    a1 = add(multiply(x1, response), multiply(y1, challenge))
    a2 = add(multiply(x2, response), multiply(y2, challenge))
    c = keccak_256(  # pylint: disable=E1120
        abi_types=["uint256"] * 12,  # 12,
        values=[
            int(v)
            for v in normalize(a1)
            + normalize(a2)
            + normalize(x1)
            + normalize(y1)
            + normalize(x2)
            + normalize(y2)
        ],
    )
    c = int.from_bytes(c, "big")
    return c == challenge

x=random_scalar()
pub1=multiply(G1, x)
pub2=multiply(H1, x)
c,r = dleq(G1, pub1, H1, pub2,x)

rtn=dleq_verify(G1, pub1, H1,pub2, c, r)
print(f"Secret: {x}")
print(f"x.G: {pub1}")
print(f"x.H: {pub2}")
print (f"\nc={c}, r={r}")
print(f"Proven: {rtn}")

A sample run gives [here]:

x: 10366729598460110564106835528331459549420144661779728900553421386151727683717
x.G: (19264659997498337231621849020324059839727633018344333818406571209706203133187, 12311200540645983074100160614979827101793507198593933504549623882564840726866, 20670726114001654463056991634829687089002941232072263069935333565317103573495)
x.H: (14945644336923121346342859944168545416458423597018613969345084948695366548579, 6287194924561282354354695364050405821231283221714798271249840862954991383974, 9769023299891292075968207384775446300063615377412681646013428758993263180405)
c=51608323136266335612692795096660702882832975771701719531287921368851758992301, r=5697936578451188395987467431508950282667773400761457095498679147707605201421
Proven: True

Conclusion

NI-ZKPs are so cool and can build a whole new trusted infrastructure — without giving away secrets. Here is the demo:

https://asecuritysite.com/zero/dleq4

and BN Curves:

https://asecuritysite.com/bn

Reference

[1] Schindler, P., Judmayer, A., Stifter, N., & Weippl, E. (2019). Ethdkg: Distributed key generation with ethereum smart contracts. Cryptology ePrint Archive.

[2] Barreto, P. S., & Naehrig, M. (2005, August). Pairing-friendly elliptic curves of prime order. In International workshop on selected areas in cryptography (pp. 319–331). Springer, Berlin, Heidelberg. [paper]