Elliptic Curve
Cryptography

ZK Prereqs Workshop 6 of 6

Where all prerequisites converge — from curves to zero knowledge proofs

Agenda

• Elliptic curve equation & geometry
• Point addition: the "connect and flip" rule
• Why EC points form an abelian group
• Elliptic curves over finite fields
• Cyclic groups & generators on curves
• The BN128 curve (Ethereum)
• Scalar multiplication & the discrete log problem
• Building a ZK proof with py_ecc

Elliptic Curve Equation

An elliptic curve is the set of all (x, y) points satisfying this equation, plus a special "point at infinity."

• Different a, b values give different curves
• BN128 uses: y² = x³ + 3   (a=0, b=3)
• secp256k1 (Bitcoin): y² = x³ + 7   (a=0, b=7)

Point Addition: Connect and Flip

To add points P and Q on the curve:

1. Draw a line through P and Q
2. The line intersects the curve at a third point R'
3. Reflect R' over the x-axis to get R = P ⊕ Q

Vertical lines are the special case — they correspond to adding a point to its inverse, giving the point at infinity.

Point Doubling: P + P

What if both points are the same?

• Take the tangent line at P (the derivative)
• Find where it intersects the curve again
• Reflect over x-axis → result is 2P

# 1000P = 512P + 256P + 128P + 64P + 32P + 8P
# 512P = double P nine times (P → 2P → 4P → ... → 512P)
# Total: ~10 doublings + ~6 additions ≈ 16 operations
# Much better than 999 additions!

Point Addition Formula

Given P₁ = (x₁, y₁) and P₂ = (x₂, y₂):

For point doubling (P₁ = P₂):

Over finite fields, division becomes multiplication by the modular inverse. All operations stay exact!

EC Points Form an Abelian Group

1. Closed: adding two curve points gives another curve point (or point at infinity)
2. Associative: (P ⊕ Q) ⊕ R = P ⊕ (Q ⊕ R) — proven algebraically
3. Identity: the point at infinity O   (P ⊕ O = P)
4. Inverse: inverse of (x, y) is (x, -y)   (reflection over x-axis)
5. Commutative: P ⊕ Q = Q ⊕ P   (same line = same intersection)

Elliptic Curves over Finite Fields

Instead of real numbers, use arithmetic mod p:

import libnum

def generate_points(mod):
    points = []
    for x in range(mod):
        y_sq = (x**3 + 3) % mod
        if libnum.has_sqrtmod_prime_power(y_sq, mod, 1):
            for y in libnum.sqrtmod_prime_power(y_sq, mod, 1):
                points.append((x, y))
    return points

# y² = x³ + 3 (mod 11) — a small example
points = generate_points(11)
print(f"Points on y² = x³ + 3 (mod 11):")
for p in sorted(points):
    print(f"  {p}")
print(f"Total: {len(points)} points + point at infinity = {len(points)+1}")

Point Addition over Finite Fields

def ec_add(x1, y1, x2, y2, a, p):
    """Add two points on y² = x³ + ax + b (mod p)"""
    if (x1, y1) == (None, None): return (x2, y2)
    if (x2, y2) == (None, None): return (x1, y1)
    
    if x1 == x2 and y1 == y2:
        # Point doubling
        lam = ((3 * x1**2 + a) * pow(2 * y1, -1, p)) % p
    elif x1 == x2:
        # Vertical line → point at infinity
        return (None, None)
    else:
        # Regular addition
        lam = ((y2 - y1) * pow(x2 - x1, -1, p)) % p
    
    x3 = (lam**2 - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)

# Example: y² = x³ + 3 (mod 11)
print(ec_add(4, 10, 7, 7, 0, 11))  # Two points on the curve

Generating the Cyclic Group

# y² = x³ + 3 (mod 11), generator G = (4, 10)
G = (4, 10)
p = 11

point = G
print(f"1G = {point}")
for i in range(2, 14):
    point = ec_add(point[0], point[1], G[0], G[1], 0, p)
    print(f"{i}G = {point}")

# Output:
# 1G  = (4, 10)     7G  = (0, 5)
# 2G  = (7, 7)      8G  = (1, 2)
# 3G  = (1, 9)      9G  = (7, 4)
# 4G  = (0, 6)      10G = (4, 1)
# 5G  = (8, 8)      11G = (None, None) ← identity!
# 6G  = (2, 0)      12G = (4, 10) ← back to G!
# The group has order 12 (11 points + point at infinity)

Important: Order ≠ Modulus

• The modulus and order are different numbers
• Adding the modulus to a scalar gives a different point
• Adding the order to a scalar gives the same point (it wraps around)
• For BN128: modulus ≈ 2²⁵⁴, order ≈ 2²⁵⁴ (close but different!)

The BN128 Curve (Ethereum)

from py_ecc.bn128 import G1, multiply, add, eq, neg, curve_order

# The generator point
print(f"G1 = {G1}")
# (1, 2)  — a small (x,y) pair!

# But the curve operates over a HUGE field:
field_mod = 21888242871839275222246405745257275088696311157297823662689037894645226208583
print(f"Field modulus bits: {field_mod.bit_length()}")  # 254

# The curve order (number of points):
print(f"Curve order bits: {curve_order.bit_length()}")  # 254

# These are DIFFERENT numbers!
assert field_mod != curve_order

Operations with py_ecc

from py_ecc.bn128 import G1, multiply, add, eq, neg

# Scalar multiplication: nG
p1 = multiply(G1, 5)    # 5G
p2 = multiply(G1, 10)   # 10G

# Point addition
p3 = add(p1, p2)        # 5G + 10G
p4 = multiply(G1, 15)   # 15G

# The homomorphism: 5G + 10G = 15G
assert eq(p3, p4)
print("5G + 10G = 15G ✓  — Homomorphism works!")

# Point negation (inverse)
neg_p1 = neg(p1)         # -(5G)
identity = add(p1, neg_p1)  # 5G + (-5G) = O
print(f"5G + (-5G) = {identity}")  # None (point at infinity)

# Associativity
a, b, c = multiply(G1, 3), multiply(G1, 7), multiply(G1, 11)
assert eq(add(add(a, b), c), add(a, add(b, c)))
print("Associativity verified ✓")

The Discrete Logarithm Problem

from py_ecc.bn128 import G1, multiply

# EASY: compute 12345G (instant)
secret = 12345
public_point = multiply(G1, secret)
print(f"12345 × G1 = {public_point}")

# HARD: given public_point, find 12345
# The only known approach for BN128 is essentially brute force
# (or baby-step giant-step, but still infeasible for 254-bit numbers)

# With ~2^254 possible values, checking each would take
# longer than the age of the universe, even at 10^18 ops/sec

This asymmetry is the foundation of elliptic curve cryptography and ZK proofs.

Multiplication = Repeated Addition

from py_ecc.bn128 import G1, multiply, add, eq

# multiply(G1, 5) is really:
# G1 + G1 + G1 + G1 + G1

# Verify:
manual = G1
for _ in range(4):
    manual = add(manual, G1)

assert eq(manual, multiply(G1, 5))
print("5G = G+G+G+G+G ✓")

# Algebraic identity still works:
# (a+b)G = aG + bG  (because it's all addition)
a, b = 100, 200
assert eq(multiply(G1, a + b), add(multiply(G1, a), multiply(G1, b)))
print(f"({a}+{b})G = {a}G + {b}G ✓")

The Homomorphism in Practice

from py_ecc.bn128 import G1, multiply, add, eq, curve_order

# The core identity: (a + b) mod order ↔ aG + bG
# Works even with enormous numbers that overflow!

a = 2**300 + 21
b = 3**50 + 11

# Path 1: add integers, then map to curve
path1 = multiply(G1, (a + b))

# Path 2: map to curve, then add points
path2 = add(multiply(G1, a), multiply(G1, b))

assert eq(path1, path2)
print("φ(a + b) = φ(a) + φ(b) ✓")
print(f"Even with {(a+b).bit_length()}-bit numbers!")

# Also works with modular reduction
path3 = multiply(G1, (a + b) % curve_order)
assert eq(path1, path3)
print("Modular reduction gives same result ✓")

Point Inverses in Finite Fields

from py_ecc.bn128 import G1, multiply, neg, add, is_inf

field_mod = 21888242871839275222246405745257275088696311157297823662689037894645226208583

# The inverse has the same x but the y is the field inverse
for i in range(1, 4):
    point = multiply(G1, i)
    inv = neg(point)
    
    print(f"{i}G    = ({int(point[0])}, {int(point[1])})")
    print(f"-{i}G   = ({int(inv[0])}, {int(inv[1])})")
    
    # x values are the same
    assert int(point[0]) == int(inv[0])
    
    # y values are additive inverses: y + y' = field_mod
    assert int(point[1]) + int(inv[1]) == field_mod
    
    # Adding a point to its inverse gives the identity
    assert is_inf(add(point, inv))
    print(f"{i}G + (-{i}G) = point at infinity ✓\n")

Encoding Rational Numbers

from py_ecc.bn128 import G1, multiply, add, eq, curve_order

# In a finite field, 1/2 = modular inverse of 2
# This lets us encode "fractions" on the curve!

five_over_two = (5 * pow(2, -1, curve_order)) % curve_order
one_half = pow(2, -1, curve_order)

# 5/2 + 1/2 = 3 in regular math
result = add(multiply(G1, five_over_two), multiply(G1, one_half))
expected = multiply(G1, 3)

assert eq(result, expected)
print("(5/2)G + (1/2)G = 3G ✓")
print("Rational arithmetic works on the curve!")

Building a ZK Proof

from py_ecc.bn128 import G1, multiply, add, eq

# ====== PROVER ======
# "I know x and y such that x + y = 15"
secret_x = 5
secret_y = 10

# Prover computes and publishes:
A = multiply(G1, secret_x)  # xG
B = multiply(G1, secret_y)  # yG
claim = 15

proof = (A, B, claim)

# ====== VERIFIER ======
# Verifier receives (A, B, 15) but does NOT know x or y
A, B, claimed_sum = proof

# Compute claimed_sum × G
expected = multiply(G1, claimed_sum)

# Check: A + B == claimed_sum × G?
if eq(add(A, B), expected):
    print("✓ VERIFIED: prover knows x, y with x + y = 15")
else:
    print("✗ REJECTED: proof is invalid")

ZK Proof: Linear Equations

from py_ecc.bn128 import G1, multiply, add, eq

# Prove: "I know x such that 23x = 161"
# (Solution: x = 7)

# ====== PROVER ======
secret_x = 7
commitment = multiply(G1, secret_x)  # xG

# ====== VERIFIER ======
# Verifier knows the equation 23x = 161
# They check: 23 × (xG) == 161G

lhs = multiply(commitment, 23)       # 23 × (xG) = 23xG
rhs = multiply(G1, 161)              # 161G

if eq(lhs, rhs):
    print("✓ VERIFIED: prover knows x such that 23x = 161")
    print("  (Verifier doesn't know x = 7!)")

# This works because:
# 23 × (xG) = 23xG = (23x)G = 161G ← by homomorphism

Security Considerations

• True ZK requires blinding factors (random masks)
• Protocols like Groth16, PLONK add these safeguards
• But the core mechanism — homomorphic verification — is what we showed
• BN128 provides ~128 bits of security against discrete log

Treating EC as a Black Box

• ✓ Adding EC points is closed — produces another EC point
• ✓ Adding EC points is associative
• ✓ There exists an identity (point at infinity)
• ✓ Every point has an inverse
• ✓ The group is cyclic — generated from G
• ✓ Homomorphism: (a+b)G = aG + bG

This is like using a hash function — you don't need to know SHA-256's internals to use it correctly.

Workshop Series Recap

Practice Problems

1. Using py_ecc, verify that (a+b+c)G = aG + bG + cG for random a, b, c.
2. Verify associativity: (aG + bG) + cG = aG + (bG + cG) for random values.
3. Prove you know x such that 7x = 49 using EC commitments (without revealing x).
4. Generate all points on y² = x³ + 3 (mod 23). How many points are there?
5. Find a generator for the curve in problem 4 and verify it generates all points.
6. Challenge: Build a ZK proof for a system of two linear equations: 2x + 3y = 13 and x + y = 5.

What's Next?

• R1CS: Rank-1 constraint systems — encoding computations as matrices
• QAP: Quadratic arithmetic programs — polynomials from R1CS
• Groth16: The most gas-efficient ZK-SNARK for Ethereum
• PLONK: Universal trusted setup, more flexible
• STARKs: No trusted setup, quantum-resistant
• Bilinear pairings: "multiplying" EC points (bilinear maps)