Math Guide
Abstract
This volume of The Zcash Arboretum develops the mathematics underlying the cryptography of Zcash from first principles, assuming only elementary algebra and calculus. Its subjects, in order, are the notation of sets, functions, and relations in which every later claim is stated; the integers and their remainders modulo a prime, where the extended Euclidean algorithm computes inverses and so reduces division to multiplication by an inverse; the abstract structures—groups, rings, and fields—that axiomatise the laws this arithmetic obeys; polynomials over a field, whose bounded number of roots allows two polynomials of large degree to be compared by evaluation at a single random point; the finite fields, their possible sizes, and their cyclic multiplicative structure; the number theory of squares, square roots, and the discrete logarithm; linear algebra and the inner products underlying short commitments to long vectors; the roots of unity that supply evaluation domains and the fast Fourier transform; elliptic curves, whose point groups, when chosen appropriately, admit no known subexponential discrete-logarithm attack; and the probability, asymptotics, and model of computation required to state a claim of 128-bit security with a precise meaning.
Later volumes of the series depend on three parts of this volume: the Pasta curve cycle, constructed in §10; the polynomial machinery on which Halo 2 rests, developed in §5 and §9; and the language of security statements, fixed in §11. A first reading should take the sections in order; a reader who needs one of these parts may begin at its section and follow its references back to the earlier sections on which it depends.
Contents
- 1 Notation: sets, functions, and relations
-
2 The integers and modular arithmetic
- 2.1 Well-ordering and the integers
- 2.2 Divisibility
- 2.3 The division algorithm
- 2.4 The greatest common divisor and the Euclidean algorithm
- 2.5 The Bézout identity and the extended Euclidean algorithm
- 2.6 Primes and the fundamental theorem of arithmetic
- 2.7 Congruences and residue classes
- 2.8 Units modulo n and modular inverses
- 3 Groups
- 4 Rings and fields
- 5 Polynomials over a field
- 6 Finite fields
- 7 Number theory for cryptography
- 8 Linear algebra over a field
-
9 Roots of unity and evaluation domains
- 9.1 Roots of unity
- 9.2 Existence over finite fields: the condition
n ∣ q − 1 - 9.3 The evaluation domain H and its vanishing polynomial
- 9.4 The Lagrange basis on H
- 9.5 Evaluation and interpolation as mutually inverse linear maps
- 9.6 The number-theoretic transform and convolution
- 9.7 The fast Fourier transform
- 9.8 The role of smooth multiplicative domains in polynomial proof systems
-
10 Elliptic curves
- 10.1 Weierstrass equations
- 10.2 The point at infinity, geometrically
- 10.3 The chord-and-tangent group law: geometry
- 10.4 Explicit affine formulas
- 10.5 Identity, inverses, commutativity, and associativity
- 10.6 Projective and Jacobian coordinates
- 10.7 Scalar multiplication and double-and-add
- 10.8 The group structure of E (F p)
- 10.9 Torsion, the cofactor, and prime-order subgroups
- 10.10 Base fields, scalar fields, and the Pasta cycle
- 10.11 The elliptic-curve discrete logarithm problem
- 10.12 The j -invariant and the GLV endomorphism
- 10.13 A worked toy example
- 10.14 Pallas and Vesta assembled
-
11 Probability, asymptotics, and computation
- 11.1 Finite probability spaces and events
- 11.2 Conditional probability and independence
- 11.3 Random variables and expectation
- 11.4 The union bound and a birthday calculation
- 11.5 Statistical distance
- 11.6 Uniform sampling and the bias of modular reduction
- 11.7 Beyond finite spaces: countable additivity, limits, and densities
- 11.8 Asymptotic notation
- 11.9 Polynomial, exponential, and negligible functions
- 11.10 Algorithms, running time, and PPT
- 11.11 The security parameter