Blockchain Cryptography: Elliptic Curves, ZK Proofs & Threshold Signatures - Blockchain Development Hub

Elliptic Curve Cryptography Curve Parameters # Short Weierstrass form: y² = x³ + ax + b (mod p) # secp256k1 (Bitcoin, Ethereum) p = 2²⁵⁶ - 2³² - 977 a = 0 b = 7 G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8) n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # order h = 1 # cofactor # Ed25519 (EdDSA, Solana, newer chains) # Twisted Edwards: -x² + y² = 1 + dx²y² p = 2²⁵⁵ - 19 d = -121665/121666 G = (x, y) # base point n = 2²⁵² + 27742317777372353535851937790883648493 # order h = 8 # cofactor Group Operations # Point addition (affine coordinates) # P = (x1, y1), Q = (x2, y2) # if P == Q: point doubling # λ = (3x1² + a) / (2y1) mod p # else: # λ = (y2 - y1) / (x2 - x1) mod p # x3 = λ² - x1 - x2 mod p # y3 = λ(x1 - x3) - y1 mod p # Point doubling (projective coordinates for speed) # Jacobian: (X, Y, Z) represents (X/Z², Y/Z³) # No inversion needed until final conversion # Scalar multiplication: k * P # Double-and-add (binary) or windowed NAF # Constant-time for side-channel resistance ECDSA (secp256k1) # Signing k = random_scalar(1, n-1) # MUST be random! RFC 6979 deterministic R = k * G = (r_x, r_y) r = r_x mod n s = k⁻¹ * (hash(m) + r * private_key) mod n signature = (r, s) # Verification u1 = hash(m) * s⁻¹ mod n u2 = r * s⁻¹ mod n R = u1 * G + u2 * public_key valid = (R.x mod n) == r # Critical: nonce reuse → private key recovery # If (r, s1) and (r, s2) for different messages: # k = (hash(m1) - hash(m2)) * (s1 - s2)⁻¹ mod n # private_key = (s1 * k - hash(m1)) * r⁻¹ mod n # Solution: RFC 6979 deterministic nonces k = HMAC-DRBG(private_key, hash(m)) EdDSA (Ed25519) # Deterministic, no per-signature randomness # Private key: 32-byte seed → (private_scalar, prefix) # Public key: prefix + encode(private_scalar * G) # Signing r = hash(prefix || message) # 64 bytes → scalar mod n R = r * G k = hash(encode(R) || public_key || message) # scalar mod n s = r + k * private_scalar mod n signature = encode(R) || encode(s) # Verification R = s * G - k * public_key check hash(encode(R) || public_key || message) == k # Advantages: no RNG needed, faster verification, batch verification Hash Functions & Commitments SHA-256 / Keccak-256 # SHA-256 (Bitcoin) # Merkle-Damgård construction, 512-bit blocks, 64 rounds # Initialization constants: fractional parts of sqrt(2..19) # Round constants: fractional parts of cube root(2..311) # Keccak-256 (Ethereum) # Sponge construction: absorb → squeeze # State: 5×5×64 = 1600 bits # Rate: 1088 bits, Capacity: 512 bits # 24 rounds of θ, ρ, π, χ, ι # Domain separation: # Ethereum: keccak256(abi.encodePacked(...)) # Solidity: keccak256(bytes(data)) BLAKE3 # BLAKE3: fast, parallelizable, based on BLAKE2 + Chacha # Merkle tree structure: each chunk → leaf, parent = hash(left || right) # SIMD-friendly (AVX2, NEON), ~5x faster than SHA-256 # Use cases: file integrity, content addressing, keyed hashing (MAC) # Bao: verified streaming hash (BLAKE3 + Merkle proofs) # Seekable, verifiable streaming for large files Poseidon (ZK-Friendly Hash) # Designed for arithmetic circuits (R1CS/Plonkish) # Based on Hades permutation: full rounds + partial rounds # S-box: x → x^α (α=3 or 5, usually 5 for security) # MDS matrix for diffusion # Parameters (BN254): # t = 3 (state width), Rf = 8 (full rounds), Rp = 56 (partial rounds) # ~400 constraints vs ~25,000 for SHA-256 in R1CS # Poseidon2: improved MDS, fewer rounds, better performance Pedersen Commitments # Commit(value, randomness) = value * G + randomness * H # G, H = generators, log_G(H) unknown (nothing-up-my-sleeve) # Properties: # - Perfectly hiding: randomness hides value # - Computationally binding: can't open to different value (DL assumption) # - Additively homomorphic: Com(a) + Com(b) = Com(a+b) # Used in: confidential transactions, ZK proofs, VSS Digital Signatures Schnorr Signatures # Simpler than ECDSA, linear in private key # Signing: k = random_scalar() R = k * G e = hash(R || public_key || message) s = k + e * private_key mod n signature = (R, s) # Verification: s * G = R + hash(R || public_key || message) * public_key # Advantages: # - Linear: enables key aggregation, threshold signatures # - Batch verification: sum(s_i) * G = sum(R_i) + sum(e_i * P_i) # - Native multisig: MuSig (key aggregation) # Taproot (Bitcoin): Schnorr + MAST (Merkelized Abstract Syntax Trees) # Single public key for all spending conditions MuSig2 (Multisignature) # Key aggregation: single public key = sum(P_i) # 2-round signing: # Round 1: each party → random nonce R_i # Round 2: each party → partial signature s_i # Aggregated: R = sum(R_i), s = sum(s_i) # Security: prevents rogue key attack (pre-session nonces) # MuSig-DN: deterministic nonces for hardware wallets Threshold Signatures (TSS) GG18 / GG20 (ECDSA Threshold) # t-of-n ECDSA signing without reconstructing private key # Based on Paillier encryption + zero-knowledge proofs # Setup: distributed key generation (DKG) # Each party gets share x_i, public key = sum(x_i) * G # Signing (GG20 - 3 rounds): # 1. Each party: commit to random k_i, prove knowledge (ZK) # 2. Reveal k_i, compute R = sum(k_i) * G, r = R.x # 3. Each party: compute partial sig s_i = k_i⁻¹ * (hash(m) + r * x_i) # with Paillier encryption for multiplication # 4. Combine: s = sum(s_i) mod n # signature = (r, s) # Used by: Fireblocks, Sepior, Coinbase, Binance custody FROST (Flexible Round-Optimized Schnorr Threshold) # Threshold Schnorr signatures (t-of-n) # 1 round of communication (vs 3 for GG20) # DKG: Pedersen VSS → each party gets share x_i # Public key = sum(x_i) * G # Signing (single round): # 1. Each party: generate nonce commitment (t-1 degree polynomial) # 2. Broadcast commitments # 3. Each party: compute binding factor, partial signature # 4. Aggregate: verify Lagrange interpolation, combine s_i # Advantages: fewer rounds, identifiable abort (detect malicious parties) # Used by: Zcash, Penumbra, various threshold wallets DKG (Distributed Key Generation) # Generate shared secret without trusted dealer # Pedersen VSS: # Dealer picks polynomial f(x) = a_0 + a_1*x + ... + a_{t-1}*x^{t-1} # a_0 = secret, shares = f(i) for i=1..n # Commitments: C_j = a_j * G (public verification) # Each party verifies: f(i) * G = sum(C_j * i^j) # Complaints if invalid → dealer reveals share or disqualified # Joint-Feldman DKG: all parties contribute polynomials # Final secret = sum of all a_0 from each party # Robust: tolerates up to t-1 malicious parties BLS Signatures & Aggregation BLS Basics (BLS12-381) # Pairing-based: e: G1 × G2 → GT # G1 = E(F_p)[r], G2 = E'(F_{p²})[r], GT = F_{p¹²}[r] # BLS12-381: p ≈ 2³⁸¹, embedding degree 12 # KeyGen: sk ∈ F_r, pk = sk * G2 # Sign: σ = sk * H(message) ∈ G1 (H: hash_to_curve) # Verify: e(σ, G2) == e(H(m), pk) # Aggregation: # Multiple signatures on same message: # σ_agg = σ_1 + σ_2 + ... + σ_n ∈ G1 # pk_agg = pk_1 + pk_2 + ... + pk_n ∈ G2 # Verify: e(σ_agg, G2) == e(H(m), pk_agg) # Multiple messages: # σ_agg = σ_1 + σ_2 + ... + σ_n # Verify: e(σ_agg, G2) == ∏ e(H(m_i), pk_i) # Used by: Ethereum 2.0 (attestations), Chia, Dfinity, Algorand BLS in Ethereum 2.0 # Attestation aggregation # Committee of 128 validators # Each signs attestation data (slot, shard, beacon_block_root, etc.) # Aggregator collects signatures, verifies, combines # Single aggregated signature verified by beacon chain # Sync committee (512 validators): # Aggregate signature for light client proofs # Light client verifies 1 pairing instead of 512 # Signature domains (domain separation): # DOMAIN_BEACON_ATTESTER = 0x01 # DOMAIN_BEACON_PROPOSER = 0x02 # DOMAIN_SYNC_COMMITTEE = 0x07 # ... prevents cross-domain replay Threshold BLS # BLS is linear → threshold via Shamir secret sharing # DKG: share sk using Shamir (t-of-n) # Each party: sk_i = f(i), pk_i = sk_i * G2 # Reconstruct: sk = sum(sk_i * L_i(0)) where L_i = Lagrange basis # Distributed signing: # Each party: σ_i = sk_i * H(m) # Combine: σ = sum(σ_i * L_i(0)) = sk * H(m) # No interaction needed! (non-interactive aggregation) # Caveat: rogue key attack if pk not verified # Solution: proof of possession (sign own pk) or MuSig-style aggregation Verifiable Random Functions (VRF) ECVRF (Elliptic Curve VRF) # VRF: pseudorandom output + proof of correctness # KeyGen: sk, pk = sk * G # Evaluate(sk, input): # h = hash_to_curve(input) # Γ = sk * h (VRF output) # Prove: π = (c, s) where c = hash(Γ, h, pk), s = k - c*sk # Return (Γ, π) # Verify(pk, input, Γ, π): # h = hash_to_curve(input) # c' = hash(Γ, h, pk) # Check: s*G + c'*pk == k*G (recomputed from π) # Properties: # - Uniqueness: for fixed (pk, input), only one valid Γ # - Pseudorandomness: Γ indistinguishable from random without sk # - Verifiability: anyone can check π # Used by: Algorand (sortition), Cardano (leader selection), # Polkadot (BABE), Chainlink VRF, Ethereum 2.0 (RANDAO alternative) Applications # 1. Leader election: VRF(output) < threshold → elected # Proportional to stake, verifiable by all # 2. Random beacon: chain VRF outputs # VRF(sk, prev_output) → next_output # Unbiasable, unpredictable # 3. Sharding: VRF determines shard assignment # Verifiable, no central coordinator # 4. Fair ordering: VRF-based transaction ordering # Prevents front-running by sequencer Zero-Knowledge Proofs SNARKs (Groth16, PLONK, Marlin) # Succinct Non-interactive ARgument of Knowledge # Trusted setup (per circuit for Groth16, universal for PLONK) # Proof size: ~200 bytes (Groth16), ~1-2 KB (PLONK) # Verification: ~200k gas (pairing check) # Arithmetization: R1CS (Rank-1 Constraint System) # A * w ∘ B * w = C * w (∘ = Hadamard product) # w = witness (public inputs + private inputs) # Groth16: circuit-specific setup, 3 group elements # PLONK: universal setup, permutation argument for wiring # Marlin: universal, sparse polynomial commitment (KZG) # Halo2: no trusted setup (IPA commitment), recursive # Used by: zkSync, Scroll, Electric Coin Co. STARKs (Scalable Transparent ARguments of Knowledge) # No trusted setup (transparent), quantum-resistant # Based on FRI (Fast Reed-Solomon IOP) # Proof size: ~50-100 KB (larger than SNARKs) # Verification: more expensive (hash-based) # Prover: faster for large computations # Arithmetization: AIR (Algebraic Intermediate Representation) # Execution trace → polynomial constraints # FRI: prove polynomial is low-degree # Used by: Starknet, Polygon Miden, RISC Zero, Winterfell # Recursive STARKs: prove verification of another STARK # Enables incremental verification (validiums, L3s) Bulletproofs # No trusted setup, short proofs for range proofs # Inner product argument: prove = c # Range proof: prove v ∈ [0, 2ⁿ] without revealing v # Proof size: 2 log₂(n) + 9 group elements (~672 bytes for 64-bit) # Used by: Monero (confidential transactions), # Mimblewimble (Grin, Beam), Solana (token confidential transfers) # Aggregation: combine m range proofs → O(log m) size Nova / SuperNova (Incrementally Verifiable Computation) # IVC: prove correct execution of each step # Folding scheme: combine two instances into one # No trusted setup, O(1) verification per step # Nova: R1CS folding, ~10k constraints per step # SuperNova: customizable constraint system, non-uniform IVC # Sangria: PLONK folding # Applications: # - Incremental blockchain sync (light clients) # - Recursive ZK-VM (RISC Zero, SP1) # - Streaming proofs Commitment Schemes Polynomial Commitments (KZG) # Kate-Zaverucha-Goldberg (KZG) commitments # Trusted setup: [1]₁, [s]₁, [s²]₁, ..., [s^d]₁, [s]₂ # Commit(f) = f(s) * G₁ # Open(f, z): prove f(z) = y # π = (f(s) - y) / (s - z) * G₁ # Verify: e(commit - y*G₁, G₂) == e(π, s*G₂ - z*G₂) # Used by: PLONK, Marlin, DANKSHARDING (Ethereum), # zkSync, Scroll, many ZK rollups # Multipoint opening: prove f(z_i) = y_i for multiple points # Batch opening: random linear combination FRI (Fast Reed-Solomon IOP) # No trusted setup, hash-based # Commit: Merkle root of Reed-Solomon codeword # f: F → F, deg(f) < d # Evaluate on domain L (|L| = 2^k ≥ 4d) # Commitment: Merkle root of [f(x) for x in L] # FRI protocol: prove codeword is close to low-degree polynomial # 1. Prover sends f₀ = f # 2. Verifier sends random α # 3. Prover computes f₁(x) = (f₀(x) + f₀(-x))/2 + α*(f₀(x) - f₀(-x))/(2x) # (folding: reduces degree by 2) # 4. Repeat until constant polynomial # 5. Verifier queries Merkle paths at each round # Used by: STARKs, Winterfell, RISC Zero, Polygon Miden Vector Commitments # Commit to vector [v₁, ..., v_n], open individual positions # Use cases: stateless clients, light clients, Verkle trees # KZG-based: each position = evaluation at distinct point # Verkle trees: KZG commitments at each node # - Wider branching factor (256 vs 16 for Merkle Patricia) # - Shorter proofs: 1 KZG proof per level vs 16 siblings # - Ethereum Verkle tree transition (post-Verkle) # Lagrange-based: commit to polynomial f(i) = v_i # Opening at i: quotient proof (f(x) - v_i)/(x - i) Conclusion Cryptography is the backbone of blockchain systems. The transition from ECDSA to Schnorr/BLS enables signature aggregation and threshold schemes. ZK proofs (SNARKs/STARKs) are scaling Ethereum and enabling privacy. VRFs provide verifiable randomness for consensus. Polynomial commitments (KZG, FRI) underpin modern ZK systems and future Ethereum upgrades (Verkle trees, danksharding). For developers, the key decision is choosing the right primitive: ECDSA/EdDSA for simple signatures; BLS for aggregation; TSS/FROST for custody; Groth16/PLONK for small circuits; STARKs for large computations; FRI for transparency. Libraries like arkworks, halo2, gnark, and circom make these accessible without implementing crypto from scratch.