Math for ZK

ECDSA Signatures

Elliptic Curve Digital Signature Algorithm is a signature algorithm based on elliptic curve cryptography. It can generate key pairs, create signatures, and verify them. These use asymmetric keys to perform secure transactions, and when coming to Ethereum, it uses the last 20 bytes of the Keccak-256 hash of the public key as identification (Ethereum address)

This ECDSA signature contains three integers derived from points on the elliptic curve. These values are mathematically linked to the private key and the curve parameters, but cannot be reversed to recover the private key

1. r – x-coordinate of a curve point, reduced modulo n
   • r = (x coordinate of (k · G)) mod n
2. s – proof that the signer knows the private key
   • s = k⁻¹ (hash(msg) + r · privKey) mod n
3. v – recovery identifier (used to reconstruct the public key)
   • v = 27 or 28 (legacy Ethereum convention indicating which curve solution to use)

In normal arithmetic, we could just divide by G to get the private key from the public key, but elliptic curves do not support division
Instead, ECDSA relies on scalar multiplication, which means repeatedly adding a point to itself p times. This operation is easy to compute forward but computationally infeasible to reverse (Elliptic Curve Discrete Logarithm Problem), so we cannot compute the private key from the public key

When we verify the message, we perform the following operations:
s1 = s⁻¹ mod n
R’ = (hash(msg) · s1) · G + (r · s1) · pubKey
R’ = (x, y)
r’ = x mod n
r’ == r ?
If r' == r, the signature is valid

ECDSA uses the secp256k1 curve. This curve is used due to its interoperability with Bitcoin and its efficiency. This curve has two important constants:

1. G – generator point on the curve
2. n – order of the subgroup generated by G
   • n is a large prime number
   • it defines the valid range of private keys (1 ≤ privKey < n)

Replay Attacks in Ethereum

A replay attack occurs when a valid signed transaction from one context is reused in another context without the signer’s intent
In Ethereum, replay attacks became a real concern during chain splits (e.g., Ethereum ↔ Ethereum Classic)

How replay attacks work:

• A user signs a transaction on Chain A
• The same transaction data is valid on Chain B
• An attacker replays the signed transaction on Chain B
• Funds are moved again without the user explicitly approving it

Why this happens:

• ECDSA signatures are valid as long as:
  • the signature (r, s, v) is valid
  • the transaction data is identical
• Without domain separation, signatures are chain-agnostic

Replay Protection using chainId (EIP-155) - Ethereum solved this using EIP-155, which adds the chainId into the signed transaction payload
v = {27, 28} + chainId * 2 + 8
This ensures:

• A transaction signed for one chain cannot be replayed on another chain
• The signature becomes domain-specific

Set Theory

• It’s a collection of distinct elements, may be numbers, letters or elements
• The number of elements in the set is called cardinality
• We have two types of sets
  • Finite Sets - Has countable number of elements
  • Infinite Sets
    • Countably Infinite Sets - Each element can be placed in one-to-one correspondence with natural numbers - {0, 1, 2,…}
    • Uncountably Infinite Sets - This cannot be placed in one-to-one correspondence with natural numbers, it means there are “more” elements that there are natural numbers - {0.01, 0.001, 0.0001,…}

Modular Arithmetic

It’s simply using ”%” which gives remainder
There is no modulus where we’ve division in numerator,
here we’ve Multiplicative Inverse - a number that, when multiplied by a given non-zero number, yields a product of 1. for example “x” and “1/x”
We also have a concept of Congruent - two integers a, b are congruent modulo n, if they’ve the same remainder when divided by “n” - a = b * mod(n). for example, 12-7=5, it means 2 = 7 * mod(5) = 12 * mod(5) = 17 * mod(5)

Group Theory

A group is a set of elements equipped with a binary operator that satisfies following properties:

1. closure - the operation must be closed, it means when the operator is applied to any two elements in the set the result should also be in the set
2. identity - there must exist an identity element “I” in the set such that for every element “a” in the set - a * I = I * a = a - the identity element should be unique and only one should be present in the set
3. inverse - every element in the set must have an inverse, for each element a in the set, there must exist an element a_inv, such that - a * a_inv = a_inv * a = I
4. associativity - this ensures that the result of applying the operation does “not” depend on how the elements are parenthesized - (a * b) * c = a * (b * c)

Fermat’s Little Theorem

If p is prime and a is an integer not divisible by p (i.e., a ≢ 0 (mod p) since 0 does not have a multiplicative inverse), then: a^(p−1) ≡ 1 (mod p)

Multiplying both sides by a⁻¹ gives: a^(p−2) ≡ a⁻¹ (mod p)

This proves that in a finite field ℤ_p, we should not include 0 when talking about multiplicative inverses, to make sure the set forms a group under multiplication, and that p must be prime

Modular Inverses

Group theory applies to both infinite and finite sets, but for modular arithmetic we focus on finite sets of integers modulo n
Inverses in modular arithmetic for finite set integers:

• Identity elements:

  • Additive identity → 0
  • Multiplicative identity → 1

• Additive Inverse in Modular Arithmetic - a + a_inv ≡ 0 (mod n)

  • From modular arithmetic (congruence), we can rewrite: a_inv ≡ −a (mod n)
  • Further simplifying: a_inv ≡ −a + k·n (mod n), for some integer k
  • In practice, we usually take:
    • a_inv = n − a, if a ≠ 0
    • a_inv = 0, if a = 0
  • for example: n = 7, a = 3 → a_inv = 7 − 3 = 4 → 3 + 4 ≡ 0 (mod 7)

• Multiplicative Inverse in Modular Arithmetic - a · a_inv ≡ 1 (mod p)

  • A multiplicative inverse exists if and only if: gcd(a, p) = 1
  • For prime p, this means: a ≢ 0 (mod p)
  • Using Fermat’s Little Theorem: a^(p−1) ≡ 1 (mod p)
  • Multiply both sides by a⁻¹: a^(p−2) ≡ a⁻¹ (mod p), So: a_inv = a^(p−2) (mod p)
  • For example: p = 7, a = 3 → a_inv = 3^(7−2) = 3^5 = 243 → 243 mod 7 = 5
  • checking: 3 · 5 = 15 ≡ 1 (mod 7)

• Additive inverses exist for all elements in ℤ_n

• Multiplicative inverses exist only for elements co-prime with n

• When n is prime, all non-zero elements have a multiplicative inverse

• This is why cryptography works in finite fields (ℤ_p), not just any modular set

Abelian Group

It’s a commutative group, set plus a binary operator that satisfies - closure, identity, inverse and associativity
An abelian group is a group PLUS the group operation is commutative, the result of applying the group operation to two elements a and b doesn’t depend on the order in which they are written: a * b = b * a, for all a, b ∈ G

Ring

A ring is a set equipped with two binary operators (say +, *) that satisfy the following properties:

• Addition: The set must form an abelian group: closure, Identity element, Inverse, Associative, Commutative
• Multiplication: the set must satisfy: Closure and Associativity
• Distributive laws: multiplication must distribute over addition
  • Left distributive: for a, b, c ∈ R - a * (b + c) = (a * b) + (a * c)
  • Right distributive: (a + b) * c = (a * c) + (b * c)
• If there exists a multiplicative identity 1, it is a ring with unity (or unital ring)
• If multiplication is commutative: a * b = b * a, for all a, b ∈ R, then it is a commutative ring

Field

A field is a ring with unity plus additional properties under multiplication

• Addition: The set must form an abelian group: Closure, Identity element, Inverse, Associative, Commutative
• Multiplication: the set must satisfy: Closure, Identity element(1), Inverse(for all a ≠ 0), Associative, Commutative
• Distributive laws: multiplication must distribute over addition
  • Left distributive: for a, b, c ∈ F - a * (b + c) = (a * b) + (a * c)
  • Right distributive: (a + b) * c = (a * c) + (b * c)