This page is the Simplified Technical English version of section 2 of the Zcash Protocol Specification. The source specification is the normative text. Read the writing rules to understand the marked words.
2. Notation
\(\bit\) means the type of bit values, that is, \(\setof{0, 1}\). \(\byte\) means the type of byte values, that is, \(\range{0}{255}\).
\(\Nat\) means the type of nonnegative integers. \(\PosInt\) means the type of positive integers. \(\Int\) means the type of integers. \(\Rat\) means the type of rationals.
\(x \typecolon T\) is used to specify that \(x\) has type \(T\). A cartesian product type is denoted by \(S \times T\), and a function type is denoted by \(S \rightarrow T\). Other argument types or result types can depend on an argument to a function.
The type of a randomized algorithm is denoted by \(S \rightarrowR T\). The domain of a randomized algorithm can be \(()\). In that case, no arguments are necessary for the algorithm. Given \(f \typecolon S \rightarrowR T\) and \(s \typecolon S\), sampling a variable \(x \typecolon T\) from the output of \(f\) applied to \(s\) is denoted by \(x \leftarrowR f(s)\).
Initial arguments to a function or randomized algorithm can be written as subscripts. For example, if \(x \typecolon X\), \(y \typecolon Y\), and \(f \typecolon X \times Y \rightarrow Z\), then an invocation of \(f(x, y)\) can also be written \(f_x(y)\).
\(\setof{x \typecolon T \suchthat p_x}\) means the subset of \(x\) from \(T\) such that \(p_x\) (a boolean expression that depends on \(x\)) is true.
\(T \subseteq U\) means that \(T\) is an inclusive subset or subtype of \(U\).
\(S \union T\) means the set union of \(S\) and \(T\).
\(S \intersection T\) means the set intersection of \(S\) and \(T\), that is, \(\setof{x \typecolon S \suchthat x \in T}\).
\(S \setminus T\) means the set difference that results from the removal of the elements in \(T\) from \(S\), that is, \(\setof{x \typecolon S \suchthat x \notin T}\).
\(\fun{x \typecolon T}{e_x \typecolon U}\) means the function of type \(T \rightarrow U\) mapping formal parameter \(x\) to \(e_x\) (an expression that depends on \(x\)). The types \(T\) and \(U\) are always explicit.
\(\exclusivefun{x \typecolon T}{e_x \typecolon U}{V}\) means \(\fun{x \typecolon T}{e_x \typecolon U \union V}\) restricted to the domain \(\setof{x \typecolon T \suchthat e_x \not\in V}\) and range \(U\).
\(\powerset{T}\) means the powerset of \(T\).
\(\bot\) is a distinguished value. It is used to show one of these:
- unavailable information
- a failed decryption or validity check
- an exceptional case
\(\typeexp{T}{\ell}\), where \(T\) is a type and \(\ell\) is an integer, means the type of sequences of length \(\ell\) with elements in \(T\). For example, \(\bitseq{\ell}\) means the set of sequences of \(\ell\) bits, and \(\byteseq{k}\) means the set of sequences of \(k\) bytes.
\(\byteseqs\) means the type of byte sequences of arbitrary length.
\(\length(S)\) means the length of (number of elements in) \(S\).
\(\truncate{k}(S)\) means the sequence formed from the first \(k\) elements of \(S\).
\(\hexint{}\) followed by a string of \(\mathtt{monospace}\) hexadecimal digits means the corresponding integer converted from hexadecimal. \(\zerobytes{\ell}\) means the sequence of \(\ell\) zero bytes.
\(\ascii{...}\) means the given string represented as a sequence of bytes in US-ASCII. For example, \(\ascii{abc}\) means the byte sequence \(\hexarray{61,62,63}\).
\(\zeros{\ell}\) means the sequence of \(\ell\) zero bits. \(\ones{\ell}\) means the sequence of \(\ell\) one bits.
\(a..b\), used as a subscript, means the sequence of values with indices \(a\) through \(b\) inclusive. For example, \(\AuthPublicNew{\allNew}\) means the sequence \(\vphantom{\mathsf{a_a}}\smash{[\AuthPublicNew{\mathrm{1}}, \AuthPublicNew{\mathrm{2}}, ...\,\AuthPublicNew{\NNew}]}\).
(For consistency with the notation in [BCGGMTV2014] and in [BK2016], we use 1-based indexing and inclusive ranges in this specification. This is in spite of the compelling arguments to the contrary in [EWD-831].)
\(\range{a}{b}\) means the set or type of integers from \(a\) through \(b\) inclusive.
\(\listcomp{f(x) \for x \from a \upto b}\) means the sequence formed by evaluating \(f\) on each integer from \(a\) to \(b\) inclusive, in ascending order. Similarly, \(\listcomp{f(x) \for x \from a \downto b}\) means the sequence formed by evaluating \(f\) on each integer from \(a\) to \(b\) inclusive, in descending order.
\(a \bconcat b\) means the concatenation of sequences \(a\) then \(b\).
\(\concatbits(S)\) means the sequence of bits that results from the concatenation of the elements of \(S\) as bit sequences.
\(\sorted(S)\) means the sequence formed by sorting the elements of \(S\).
\(\GF{n}\) means the finite field with \(n\) elements, and \(\GFstar{n}\) means its group under multiplication (\(0\) is not in this group).
Where it is necessary to make the distinction, we denote the unique representative of \(a \typecolon \GF{n}\) in the range \(\range{0}{n-1}\) (or the unique representative of \(a \typecolon \GFstar{n}\) in the range \(\range{1}{n-1}\)) as \(a \bmod n\). Conversely, we denote the element of \(\GF{n}\) that corresponds to an integer \(k \typecolon \Int\) as \(k \pmod{n}\). We also use the latter notation in the context of an equality \(k = k' \pmod{n}\) as shorthand for \(k \bmod n = k' \bmod n\). Similarly, we use \(k \neq k' \pmod{n}\) as shorthand for \(k \bmod n \neq k' \bmod n\).
(When we refer to constants such as \(0\) and \(1\), it is usually not necessary to make the distinction between field elements and their representatives. This is because the meaning is usually clear from context.)
\(\GF{n}[z]\) means the ring of polynomials over \(z\) with coefficients in \(\GF{n}\).
\(a + b\) means the sum of \(a\) and \(b\). According to context, this can be addition of:
- integers
- rationals
- finite field elements
- group elements (refer to Represented Group)
\(-a\) means the value of the applicable integer, rational, finite field, or group type such that \((-a) + a = 0\) (or when \(a\) is an element of a group \(\GroupG{}\), \((-a) + a = \ZeroG{}\)). \(a - b\) means \(a + (-b)\).
\(a \mult b\) means the product of multiplying \(a\) and \(b\). According to context, this can be multiplication of:
- integers
- rationals
- finite field elements
This notation is not used for group elements.
\(a / b\), also written \(\hfrac{a}{b}\), means the value of the applicable integer, rational, or finite field type such that \((a / b) \mult b = a\).
\(a \bmod q\), for \(a \typecolon \Nat\) and \(q \typecolon \PosInt\), means the remainder on dividing \(a\) by \(q\). (This usage does not conflict with the notation above for the unique representative of a field element.)
\(a \xor b\) means the bitwise-exclusive-or of \(a\) and \(b\), and \(a \band b\) means the bitwise-and of \(a\) and \(b\). These are defined on integers (integers include bits and bytes), or elementwise on equal-length sequences of integers, according to context.
\(\!\vsum{i=1}{\rmN} a_i\) means the sum of \(a_{\allN{}}\). \(\vproduct{i=1}{\rmN} a_i\) means the product of \(a_{\allN{}}\). \(\vxor{i=1}{\rmN} a_i\) means the bitwise-exclusive-or of \(a_{\allN{}}\).
When \(N = 0\), the result of each of these is the applicable neutral element, that is:
- \(\ssum{i=1}{0} a_i = 0\)
- \(\sproduct{i=1}{0} a_i = 1\)
- \(\sxor{i=1}{0} a_i = 0\) or the all-zero bit sequence of length given by the type of \(a\)
\(\possqrt{a}\), where \(a \typecolon \GF{q}\), means the positive square root of \(a\) in \(\GF{q}\), that is, in the range \(\bigrange{0}{\frac{q-1}{2}}\). It is only used in cases where the square root must exist.
\(\optsqrt{a}\), where \(a \typecolon \GF{q}\), means an arbitrary square root of \(a\) in \(\GF{q}\), or \(\bot\) if no such square root exists.
\(b \bchoose x : y\) means \(x\) when \(b = 1\), or \(y\) when \(b = 0\).
\(a^b\), for \(a\) an integer or finite field element and \(b \typecolon \Int\), means the result of raising \(a\) to the exponent \(b\), that is:
\[a^b := \begin{cases} \sproduct{i=1}{b} \kern 0.15em a, &\caseif b \geq 0 \\[1.5ex] \sproduct{i=1}{-b} \kern 0.1em \hfrac{1}{a}, &\caseotherwise. \end{cases}\]
The definition of the \(\scalarmult{k}{P}\) notation for scalar multiplication in a group is in Represented Group.
The convention of affixing \(\Repr\) to a variable name is used for variables that are bit sequence representations of group elements.
The binary relations \(<\), \(\leq\), \(=\), \(\geq\), and \(>\) have their conventional meanings on integers and rationals, and are defined lexicographically on sequences of integers.
\(\floor{x}\) means the largest integer \(\leq x\). \(\ceiling{x}\) means the smallest integer \(\geq x\).
\(\bitlength(x)\), for \(x \typecolon \Nat\), means the smallest integer \(\ell\) such that \(2^\ell > x\).
The integer constants in this list will be instantiated in Constants:
- \(\MerkleDepth{Sprout}\)
- \(\MerkleDepth{Sapling}\)
- \(\MerkleDepth{Orchard}\)
- \(\MerkleHashLength{Sprout}\)
- \(\MerkleHashLength{Sapling}\)
- \(\MerkleHashLength{Orchard}\)
- \(\NOld\)
- \(\NNew\)
- \(\ValueLength\)
- \(\hSigLength\)
- \(\PRFOutputLengthSprout\)
- \(\PRFOutputLengthExpand\)
- \(\PRFOutputLengthNfSapling\)
- \(\NoteCommitRandLengthSprout\)
- \(\RandomSeedLength\)
- \(\AuthPrivateLength\)
- \(\NoteUniquePreRandLength\)
- \(\SpendingKeyLength\)
- \(\DiversifierLength\)
- \(\DiversifierKeyLength\)
- \(\QuantumSpendingKeyLength\)
- \(\QuantumIntermediateKeyLength\)
- \(\InViewingKeyLength{Sapling}\)
- \(\OutViewingKeyLength\)
- \(\ScalarLength{Sapling}\)
- \(\ScalarLength{Orchard}\)
- \(\BaseLength{Orchard}\)
- \(\MAXMONEY\)
- \(\BlossomActivationHeight\)
- \(\CanopyActivationHeight\)
- \(\ZIPTwoOneTwoGracePeriod\)
- \(\NUSevenActivationHeight\)
- \(\SlowStartInterval\)
- \(\PreBlossomHalvingInterval\)
- \(\MaxBlockSubsidy\)
- \(\NumFounderAddresses\)
- \(\PoWLimit\)
- \(\PreNUSevenPoWAveragingWindow\)
- \(\PostNUSevenPoWAveragingWindow\)
- \(\PoWMedianBlockSpan\)
- \(\PoWDampingFactor\)
- \(\PreBlossomPoWTargetSpacing\)
- \(\PostBlossomPoWTargetSpacing\)
- \(\PostNUSevenPoWTargetSpacing\)
- \(\GlobalShieldedBudget\)
- \(\OrchardProtocolBlockActionLimit\)
- \(\SaplingBlockIOLimit\)
- \(\SproutBlockJoinSplitLimit\)
- \(\LNTwoScaled\)
- \(\InitialNSMValueBalance\)
- \(\NSMReissuanceHeight\)
The constants in this list will also be defined in that section:
- the rational constants \(\FoundersFraction\), \(\PoWMaxAdjustDown\), and \(\PoWMaxAdjustUp\)
- the bit-sequence constants \(\Uncommitted{Sprout} \typecolon \bitseq{\smash{\MerkleHashLength{Sprout}}}\) and \(\Uncommitted{Sapling} \typecolon \bitseq{\smash{\MerkleHashLength{Sapling}}}\)
- the constant \(\Uncommitted{Orchard} \typecolon \MerkleHashOrchard\)
We use the abbreviation "ctEdwards" to refer to complete twisted Edwards elliptic curves and coordinates (refer to Jubjub).
References
- [BCGGMTV2014]
- Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized Anonymous Payments from Bitcoin (extended version)
- [BK2016]
- Alex Biryukov and Dmitry Khovratovich. Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem (full version)
- [EWD-831]
- Edsger W. Dijkstra. Why numbering should start at zero