Math Guide
Mathematical foundations for Halo 2 and Zcash Orchard

Abstract

This volume of The Zcash Arboretum develops the mathematics underlying the cryptography of Zcash from first principles, assuming only elementary algebra and calculus. It builds a single tower: the notation of sets, functions, and relations in which every later claim is written and spoken; the integers and their remainders modulo a prime, where an extended Euclidean algorithm turns division into multiplication by an inverse; the abstract structures—groups, rings, and fields—that name the laws this arithmetic obeys; polynomials over a field, whose scarcity of roots lets two enormous polynomials be compared 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 behind short algebraic receipts for long lists of secrets; the roots of unity that furnish evaluation domains and the fast Fourier transform; elliptic curves, whose point groups have no known subexponential discrete-log attack when chosen appropriately; and finally the probability, asymptotics, and model of computation required to state—and mean—a claim of 128-bit security.

The series consumes three artefacts of this tower: the Pasta curve cycle, constructed in §10; the polynomial machinery on which Halo 2 rests, developed in §5 and §9; and the security-statement language, fixed in §11. A first reading takes the sections in order; a reader after one artefact may enter at its section and follow its backward references down the tower.