Day 9/100 of ZK 🔐
Continued with the group theory, bijections, rings, and then straight into polynomial territory.
Group theory deep dive:
A subgroup is simply a smaller group living inside a bigger one. A subgroup H of group G is a subset that is itself a group under the same operation: closed, has identity, inverses, associative. Conditions: non-empty, closed under operation & inverses.
Cyclic groups are generated by a single element g: G = {g^k | k ∈ ℤ} (or mod order for finite). Most ZK-friendly elliptic curves use cyclic subgroups of prime order for security (ECDLP hard).
Group homomorphism φ: G → H preserves operation (φ(a * b) = φ(a) * φ(b)). Isomorphism is a bijective homomorphism, basically a structure-preserving relabeling of elements. Bijection = one-to-one and onto (every element in target maps uniquely from source).
Rings:
A ring is a set with two operations (usually and ×): (R, ) is an abelian group, × is associative distributive over .
Types we touched: commutative rings (× commutative), rings with identity (has 1), integral domains (no zero divisors), fields (every non-zero element has × inverse). Finite fields F_p (p prime) and polynomial rings are everywhere in ZK.
Then we reached polynomials, the real workhorse
A polynomial is a sum of monomials (coefficient times variable to a power).
Univariate = one variable, e.g., f(x) = 4x³ – 2x 7.
Multivariate = several variables, e.g., f(x,y) = xy 3x 2y 5.
Multilinear polynomials are special multivariate ones where no variable appears to power higher than 1 (very useful for efficient protocols like sum-check).
Evaluation and Interpolation:
Evaluation just means “put a number in place of the variable and calculate the result.”
Example: f(x) = 2x 3
f(5) = 2×5 3 = 13
That’s it. In ZK we evaluate at hidden points to check properties without showing the whole polynomial.
Lagrange interpolation:
Imagine you have a secret curve (the polynomial) and you only know a few exact spots it passes through, like:
* At x=1, the height is 4
* At x=3, height is 10
* At x=5, height is 28
Lagrange interpolation is the clever recipe that rebuilds the exact polynomial that goes through all those spots, and it’s guaranteed to be the unique lowest-degree one that fits perfectly.
It works by creating little helper curves (basis polynomials) that are 1 at one known point and 0 at all the others, then blending them together weighted by the known heights.
This is the backbone of Shamir secret sharing and many polynomial commitment opening proofs.