The Zcash ArboretumI Math Guide
Contents
PDF
Theme

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.