V Ironwood Guide: The Zcash Orchard protocol and its Ironwood pool 1 Introduction 3 Keys and addresses

2 Notation and primitive instances

This section fixes the encodings and the primitive instances on which the later constructions rest, each with its Orchard parameters and domain separators. The underlying constructions belong to the Math Guide and the Crypto Guide and are cited, not re-derived; each named assumption is stated at the first construction whose security needs it.

2.1 Fields, groups, and encodings

The Pallas group $\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ is the group of points of the curve $y^{2}=x^{3}+5$ over the prime field $\mathbb{F}_{p_{\mathsf{Pallas}}}$ , with identity $\mathcal{O}$ . It has prime order $p_{\mathsf{Vesta}}$ and cofactor $1$ , and $\mathbb{F}_{p_{\mathsf{Vesta}}}$ is both its scalar field and the base field of the Vesta curve (Math Guide, §“Base fields, scalar fields, and the Pasta cycle” and §“Pallas and Vesta assembled”, Example “The Pasta curves”; Crypto Guide, §“Instantiation on elliptic curves; the Pasta curves”, Definition “The Pasta curves”). The group, its order and the cycle with Vesta are cited, not re-derived; the moduli are those of the protocol specification, §“Pallas and Vesta”. Table 1 maps this notation, once, to the names used by the specification and by the lower volumes. Those names appear in the table only; later text writes only the column headed “This volume”. Maps defined on the Pallas group carry the specification’s subscript $\mathbb{P}$ , as in $\mathsf{Extract}_{\mathbb{P}}$ .

Object	This volume	Specification	Lower volumes
Pallas base-field modulus	$p_{\mathsf{Pallas}}$	$q_{\mathbb{P}}$	$p$
Pallas scalar-field modulus, Vesta base-field modulus, order of the Pallas group	$p_{\mathsf{Vesta}}$	$r_{\mathbb{P}}$	$q$
Pallas base field and scalar field	$\mathbb{F}_{p_{\mathsf{Pallas}}}$ , $\mathbb{F}_{p_{\mathsf{Vesta}}}$	$\mathbb{F}_{q_{\mathbb{P}}}$ , $\mathbb{F}_{r_{\mathbb{P}}}$	$\mathbb{F}_{p}$ , $\mathbb{F}_{q}$
Pallas group	$\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$	$\mathbb{P}$	$E_{p}(\mathbb{F}_{p})$
$k$ -bit little-endian encoding of an integer	$\mathrm{LE}_{k}$	$\mathsf{I2LE{}BSP}_{k}$	—
Encoding of a point $P$	$P^{\star}$	$\mathsf{repr}_{\mathbb{P}}(P)$	—
Sinsemilla short commitment	$\mathsf{ShortCommit}$	$\mathsf{Sinsemilla{}ShortCommit}$	—
Spend validating key, as a point and as its $x$ -coordinate	$\mathsf{ak}^{\mathbb{P}}$ , $\mathsf{ak}$	$\mathsf{ak}^{\mathbb{P}}$ , $\mathsf{ak}$	—

Table 1: Notation for the fields, the Pallas group and the encodings, with the names of the protocol specification and of the Math and Crypto Guides. The spend validating key is constructed in §3.1; the point

\mathsf{ak}^{\mathbb{P}}

and the field element

\mathsf{ak}=\mathsf{Extract}_{\mathbb{P}}(\mathsf{ak}^{\mathbb{P}})

are kept apart throughout.

Scalar multiplication is written $[k]P$ , for $k\in\mathbb{F}_{p_{\mathsf{Vesta}}}$ or an integer read modulo $p_{\mathsf{Vesta}}$ . The symbol $\|$ denotes concatenation of bit strings or of byte strings, and $\varepsilon$ the empty string. Byte-string literals and tags are set in monospace, as in z.cash:Orchard, and single bytes as $\mathtt{0x..}$ . The symbol $\bot$ is the failure value of a partial map; a map that may fail takes values in $X\cup\{\bot\}$ for its codomain $X$ .

Both moduli have bit length $255$ , and $p_{\mathsf{Pallas}}<p_{\mathsf{Vesta}}$ :

2^{254}<p_{\mathsf{Pallas}}<p_{\mathsf{Vesta}}<2^{255}.

Two consequences are used later. First, the integer representative of an element of either field lies in $\{0,\dots,2^{255}-1\}$ and has a $255$ -bit encoding, which leaves the top bit of a $256$ -bit string free. Second, the integer representative of an element of $\mathbb{F}_{p_{\mathsf{Pallas}}}$ lies in $\{0,\dots,p_{\mathsf{Vesta}}-1\}$ ; reading it as a Pallas scalar is therefore an injective, not a surjective, map $\mathbb{F}_{p_{\mathsf{Pallas}}}\to\mathbb{F}_{p_{\mathsf{Vesta}}}$ . This map is used wherever a base-field element multiplies a point (§3.3, §6.1).

Definition 2.1 (Integer and byte encodings).

For $k\geq 0$ and an integer $m\in\{0,\dots,2^{k}-1\}$ , the $k$ -bit little-endian encoding $\mathrm{LE}_{k}(m)\in\{0,1\}^{k}$ is the bit sequence $b_{0}b_{1}\cdots b_{k-1}$ with $m=\sum_{i=0}^{k-1}b_{i}2^{i}$ . The map $\mathrm{LE}_{k}\colon\{0,\dots,2^{k}-1\}\to\{0,1\}^{k}$ is a bijection with inverse $\mathrm{LE}_{k}^{-1}$ . A field element is encoded through its integer representative in $\{0,\dots,p-1\}$ , for $p$ the modulus. In the conversion names below, $\mathsf{I}$ stands for integer, $\mathsf{LE}$ for little-endian, $\mathsf{BS}$ for bit string, and $\mathsf{OS}$ for octet string (a sequence of eight-bit bytes). The digit $2$ is read “to”, and $\mathsf{P}$ stands for primitive, a basic conversion operation. The subscript $k$ counts bits, not bytes. Three maps relate integers, bit strings and byte strings:

•

the map $\mathsf{I2LEOSP}_{k}$ sends $m\in\{0,\dots,2^{k}-1\}$ to its $\lceil k/8\rceil$ -byte little-endian encoding;
•

for $k$ a multiple of $8$ , the map $\mathsf{LEOS2IP}_{k}$ sends a $k/8$ -byte string $(s_{0},\dots,s_{k/8-1})$ to the integer $\sum_{i}s_{i}\,256^{i}\in\{0,\dots,2^{k}-1\}$ ;
•

the map $\mathsf{LEBS2OSP}_{k}\colon\{0,1\}^{k}\to\{0,\dots,255\}^{\lceil k/8\rceil}$ pads its input on the right with zero bits to a multiple of $8$ bits, packs each group of $8$ bits into a byte, least significant bit first, and keeps the order of the groups.

Hence $\mathsf{LEBS2OSP}_{k}(\mathrm{LE}_{k}(m))=\mathsf{I2LEOSP}_{k}(m)$ . The byte form is needed wherever a bit string enters BLAKE2b or $\mathsf{GroupHash}$ (protocol specification, §“Integers, Bit Sequences, and Endianness”).

The widths used later are $\mathrm{LE}_{10}$ (the Merkle layer tag, §5.1), $\mathrm{LE}_{64}$ (the note value, §4.2), $\mathrm{LE}_{88}$ (the diversifier index, §3.3), $\mathrm{LE}_{255}$ (field elements) and $\mathrm{LE}_{256}$ (the star encoding below; the key encoding of $\mathsf{r_{ivk}}$ , §3.2).

Definition 2.2 (Coordinate extraction).

The map $\mathsf{Extract}_{\mathbb{P}}\colon\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}% })\to\mathbb{F}_{p_{\mathsf{Pallas}}}$ is

\mathsf{Extract}_{\mathbb{P}}(\mathcal{O}):=0,\qquad\mathsf{Extract}_{\mathbb{% P}}\bigl{(}(x,y)\bigr{)}:=x.

Its lifting $\mathsf{Extract}_{\mathbb{P}}^{\bot}\colon\mathcal{E}(\mathbb{F}_{p_{\mathsf{% Pallas}}})\cup\{\bot\}\to\mathbb{F}_{p_{\mathsf{Pallas}}}\cup\{\bot\}$ maps $\bot$ to $\bot$ and agrees with $\mathsf{Extract}_{\mathbb{P}}$ on points (protocol specification, §“Coordinate Extractor for Pallas”).

The map $\mathsf{Extract}_{\mathbb{P}}$ supplies a field element wherever a later construction needs one in place of a point: the field element $\mathsf{ak}$ (§3.1), the extracted note commitment $\mathsf{cmx}$ (§4.2), the node values of the note commitment tree (§5.1) and the nullifier $\mathsf{nf}$ (§6.1). It is two-to-one on non-identity points, by Lemma 2.4 and because $P\neq-P$ for $P\neq\mathcal{O}$ in a group of odd order; every binding argument over an extracted coordinate treats the opposite point explicitly.

Lemma 2.3 (Extract vanishes only at the identity).

For $P\in\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ , $\mathsf{Extract}_{\mathbb{P}}(P)=0$ if and only if $P=\mathcal{O}$ .

Proof.

If $P=\mathcal{O}$ , then $\mathsf{Extract}_{\mathbb{P}}(P)=0$ by definition. A point $(0,y)$ would satisfy $y^{2}=5$ in $\mathbb{F}_{p_{\mathsf{Pallas}}}$ , but $5$ is a quadratic non-residue modulo $p_{\mathsf{Pallas}}$ (Math Guide, §“Quadratic residues and the Euler criterion”, Example “ $5$ is a non-square in the Pallas base field”). Hence no point other than $\mathcal{O}$ has extracted coordinate $0$ . □

Lemma 2.4 (Coordinate extraction identifies opposite points).

For $P,P^{\prime}\in\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ , $\mathsf{Extract}_{\mathbb{P}}(P)=\mathsf{Extract}_{\mathbb{P}}(P^{\prime})$ if and only if $P^{\prime}=P$ or $P^{\prime}=-P$ .

Proof.

Negation is $-\mathcal{O}=\mathcal{O}$ and $-(x,y)=(x,-y)$ (Math Guide, §“Explicit affine formulas”, Definition “Negation”), so $\mathsf{Extract}_{\mathbb{P}}(-P)=\mathsf{Extract}_{\mathbb{P}}(P)$ for every $P$ , which is the reverse implication. For the forward implication let $\mathsf{Extract}_{\mathbb{P}}(P)=\mathsf{Extract}_{\mathbb{P}}(P^{\prime})$ . If $P=\mathcal{O}$ , then $\mathsf{Extract}_{\mathbb{P}}(P^{\prime})=0$ , and Lemma 2.3 gives $P^{\prime}=\mathcal{O}=-P$ . If $P=(x,y)$ , then $x\neq 0$ by Lemma 2.3, so $P^{\prime}\neq\mathcal{O}$ and $P^{\prime}=(x,y^{\prime})$ with $y^{\prime 2}=x^{3}+5=y^{2}$ ; hence $y^{\prime}=\pm y$ and $P^{\prime}=\pm P$ . □

Definition 2.5 (Star encoding).

For $P\in\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ the star encoding $P^{\star}\in\{0,1\}^{256}$ is

\mathcal{O}^{\star}:=\mathrm{LE}_{256}(0),\qquad(x,y)^{\star}:=\mathrm{LE}_{25% 6}\bigl{(}x+2^{255}(y\bmod 2)\bigr{)},

with $x$ and $y$ read as integer representatives: the $255$ -bit $x$ -coordinate fills the low bits and the parity of $y$ the top bit. The partial inverse $\mathsf{abst}_{\mathbb{P}}\colon\{0,1\}^{256}\to\mathcal{E}(\mathbb{F}_{p_{% \mathsf{Pallas}}})\cup\{\bot\}$ reads the first $255$ bits of $s$ as $\tilde{x}:=\mathrm{LE}_{255}^{-1}(s_{0}\cdots s_{254})$ and the last bit as the sign bit $\tilde{y}:=s_{255}$ , and returns

1.

the failure value $\bot$ if $\tilde{x}\geq p_{\mathsf{Pallas}}$ ; otherwise let $x:=\tilde{x}\in\mathbb{F}_{p_{\mathsf{Pallas}}}$ ;
2.

the identity $\mathcal{O}$ if $x=0$ and $\tilde{y}=0$ ;
3.

the failure value $\bot$ if $x^{3}+5$ is not a square in $\mathbb{F}_{p_{\mathsf{Pallas}}}$ ;
4.

otherwise the point $(x,y)$ with $y^{2}=x^{3}+5$ and $y\bmod 2=\tilde{y}$

(protocol specification, §“Pallas and Vesta”).

The encoding is canonical: $\mathsf{abst}_{\mathbb{P}}(P^{\star})=P$ for every point $P$ , and $\mathsf{abst}_{\mathbb{P}}(s)\neq\bot$ implies $\mathsf{abst}_{\mathbb{P}}(s)^{\star}=s$ . For the first claim, $\mathcal{O}^{\star}$ decodes to $\mathcal{O}$ at step 2. A point $(x,y)$ has $x\neq 0$ (Lemma 2.3), and $y\neq 0$ because a point with $y=0$ has order $2$ , which a group of odd order does not contain (Math Guide, §“Torsion, the cofactor, and prime-order subgroups”, Remark “No two-torsion on the Pasta curves”). The two square roots $\pm y$ are therefore non-zero and, $p_{\mathsf{Pallas}}$ being odd, of opposite parities, so step 4 returns $(x,y)$ . For the second claim, a string decoded at step 2 is $\mathrm{LE}_{256}(0)=\mathcal{O}^{\star}$ , and a string decoded at step 4 to $(x,y)$ has low bits $\mathrm{LE}_{255}(x)$ and top bit $y\bmod 2$ , so it equals $(x,y)^{\star}$ . Consequently $P\mapsto P^{\star}$ is injective, each point has exactly one valid encoding, and every other string decodes to $\bot$ , among them $\mathrm{LE}_{256}(2^{255})$ (whose $x$ -part is $0$ and sign bit $1$ ) and every string whose $x$ -part is at least $p_{\mathsf{Pallas}}$ . The star encoding is the form in which a point enters a hash or a commitment as a bit string.

2.2 GroupHash, domain separation, and nothing-up-my-sleeve generators

Construction 2.6 (GroupHash on Pallas).

For byte strings $D$ (the domain separator) and $M$ (the message), the point $\mathsf{GroupHash}(D,M)\in\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ is computed as follows.

1.

Let

$\mathsf{DST}:=D\,\|\,\texttt{-}\,\|\,\texttt{pallas}\,\|\,\texttt{\_XMD:BLAKE2% b\_SSWU\_RO\_};$

the map is defined when $\mathsf{DST}$ has at most $255$ bytes, which holds for every domain separator of Table 2.
2.

The map $\mathsf{hash\_to\_field}$ expands $(M,\mathsf{DST})$ by $\mathsf{expand\_message\_xmd}$ over BLAKE2b-512 into two $64$ -byte strings. BLAKE2b runs with zero personalisation; the string $\mathsf{DST}$ , followed by a byte carrying its length, is part of the hashed input. Each string is read as a big-endian integer and reduced modulo $p_{\mathsf{Pallas}}$ , giving $u_{0},u_{1}\in\mathbb{F}_{p_{\mathsf{Pallas}}}$ .
3.

The simplified Shallue–van de Woestijne–Ulas map sends each $u_{i}$ to a point $Q_{i}$ of a curve $3$ -isogenous to Pallas.
4.

The output is the image of $Q_{0}+Q_{1}$ under the $3$ -isogeny onto Pallas.

No cofactor is cleared, since the Pallas group has prime order. The isogenous curve, the isogeny coefficients and the constant of the map are those of the protocol specification, §“Group Hash into Pallas and Vesta”, and are not reproduced. The map is deterministic, public and efficiently computable (Crypto Guide, §“Hashing to a field element”, Construction “Expand-then-reduce”; §“Hashing to a curve point”, Constructions “Simplified Shallue–van de Woestijne–Ulas map” and “The hash-to-curve pipeline”, Remark “The isogeny detour forced by $j$ -invariant $0$ ”).

Definition 2.7 (Domain separator and fixed generator).

A domain separator is a fixed ASCII byte string naming a use site; it is the first argument of $\mathsf{GroupHash}$ , so that distinct uses draw distinct generators. A fixed generator is the value of $\mathsf{GroupHash}$ on a public, fixed pair $(D,M)$ . It is nothing-up-my-sleeve: the public pair determines it, and no party chose it (Crypto Guide, §“Hashing to a curve point”, Construction “Nothing-up-my-sleeve generators”). The strings are fixed by the protocol specification.

Assumption 2.8 (GroupHash as a random oracle).

In security arguments $\mathsf{GroupHash}$ is modelled as a random oracle on pairs $(D,M)$ with values in $\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ (Crypto Guide, §“The random oracle model”, Definition “Random oracle”, with the group in place of bit strings): distinct pairs receive independent uniform points. In particular the fixed generators of Table 2 are, in the model, independent uniform points. The assumption is a heuristic about the concrete map, supported by its design for indifferentiability from a random oracle (protocol specification, §“Group Hash into Pallas and Vesta”, note); it is not a theorem. Every later binding, collision, uniqueness or unlinkability result that needs it names it.

Table 2 lists every $\mathsf{GroupHash}$ input of the Orchard protocol, with the object it defines and the section that uses it. The messages G, K, v and r are one-byte ASCII strings, and the Sinsemilla messages are the ASCII strings shown. The rows are those of the protocol specification, §“Spend Authorization Signature (Sapling and Orchard)”, §“Computing $\rho$ values and Nullifiers”, §“ $\mathsf{DiversifyHash}^{\mathsf{Sapling}}$ and $\mathsf{DiversifyHash}^{\mathsf{Orchard}}$ Hash Functions”, §“Sinsemilla Hash Function”, §“Sinsemilla commitments”, §“ $\mathsf{MerkleCRH}^{\mathsf{Orchard}}$ Hash Function” and §“Homomorphic Pedersen commitments (Sapling and Orchard)”.

Domain separator $D$	Message $M$	Object	Used in
z.cash:Orchard	G	$G^{\mathsf{SpendAuth}}$ , spend-authorisation base	§3.1, §7.1
z.cash:Orchard	K	$K^{\mathsf{Orchard}}$ , nullifier base	§6.1
z.cash:Orchard-gd	$\mathsf{LEBS2OSP}_{88}(d)$	$\mathsf{g_{d}}$ for a diversifier $d$	§3.3
z.cash:Orchard-gd	$\varepsilon$	$\mathsf{g_{d}}$ if the row above gives $\mathcal{O}$	§3.3
z.cash:SinsemillaQ	z.cash:Orchard-NoteCommit-M	hash base of $\mathsf{NoteCommit}$	§4.2
z.cash:Orchard-NoteCommit-r	$\varepsilon$	blinding base of $\mathsf{NoteCommit}$	§4.2
z.cash:SinsemillaQ	z.cash:Orchard-CommitIvk-M	hash base of $\mathsf{Commit}^{\mathsf{ivk}}$	§2.4
z.cash:Orchard-CommitIvk-r	$\varepsilon$	blinding base of $\mathsf{Commit}^{\mathsf{ivk}}$	§2.4
z.cash:SinsemillaQ	z.cash:Orchard-MerkleCRH	hash base of $\mathsf{MerkleCRH}$	§5.1
z.cash:Orchard-cv	v	$V^{\mathsf{Orchard}}$ , value base	§8.1
z.cash:Orchard-cv	r	$R^{\mathsf{Orchard}}$ , randomness base	§8.1
z.cash:SinsemillaS	$\mathsf{I2LEOSP}_{32}(j)$	table entry $S(j)$ , $0\leq j<2^{10}$	§2.4

Table 2: Every input of

\mathsf{GroupHash}

in the Orchard protocol. The hash base of

\mathsf{MerkleCRH}

is derived from its domain without the suffix -M, and

\mathsf{MerkleCRH}

has no blinding base. The table entries

S(j)

are shared by every Sinsemilla domain.

Remark 2.9 (Domain separation).

The pairs of Table 2 are pairwise distinct, and the map from $(D,M)$ to the input hashed by $\mathsf{hash\_to\_field}$ is injective, because $\mathsf{DST}$ is closed by a byte carrying its length. Under Assumption 2.8 the table’s generators are therefore independent, and a relation found in one context transfers to no other (Crypto Guide, §“Domain separation and personalisation”, Proposition “Domain separation yields independent oracles”). The Crypto Guide’s inventory of Orchard tags and personalisations in the same section is cited, not repeated.

2.3 Pseudorandom functions and field reductions

Definition 2.10 (Pseudorandom function).

A keyed family $(F_{k})_{k}$ of functions is a pseudorandom function (PRF) if no efficient adversary with adaptive oracle access distinguishes $F_{k}$ , for a secret uniform key $k$ , from a uniformly random function with the same domain and range, except with negligible advantage (Crypto Guide, §“Pseudorandom functions and permutations”, Definition “Pseudorandom function”).

Construction 2.11 (Expansion function).

For a key $k\in\{0,1\}^{256}$ and a byte string $t$ ,

	$\displaystyle\mathsf{PRFexpand}_{k}(t):=\mathrm{BLAKE2b\text{-}512}\bigl{(}$	$\displaystyle\texttt{Zcash\_ExpandSeed},$
		$\displaystyle\mathsf{LEBS2OSP}_{256}(k)\,\\|\,t\bigr{)},$

a $64$ -byte string, identified with $\{0,1\}^{512}$ ; here $\mathrm{BLAKE2b\text{-}512}(P,x)$ is unkeyed BLAKE2b with a $64$ -byte output, the $16$ -byte personalisation $P$ and the input $x$ . A key given as a $32$ -byte string enters as is. The key is thus carried in the message, not in BLAKE2b’s native keyed mode (protocol specification, §“Pseudo Random Functions”), so the Crypto Guide’s PRF argument for native keying (§“PRFs from hash functions: length extension and keyed BLAKE2”) does not cover this construction; Assumption 2.12 states the property directly. The key is written as a subscript; the leading byte of $t$ names the derived quantity (protocol specification, §“Pseudo Random Functions”).

Assumption 2.12 (Pseudorandomness of PRF expansion).

For $k$ uniform on $\{0,1\}^{256}$ , the function $t\mapsto\mathsf{PRFexpand}_{k}(t)$ from byte strings to $\{0,1\}^{512}$ is a PRF in the sense of the preceding definition. This is the security requirement that the protocol specification, §“Pseudo Random Functions”, places on $\mathsf{PRFexpand}$ .

Definition 2.13 (Field reductions).

For $x\in\{0,1\}^{512}$ , read as $64$ bytes,

	$\displaystyle\mathrm{ToBase}(x)$	$\displaystyle:=\mathsf{LEOS2IP}_{512}(x)\bmod p_{\mathsf{Pallas}}\in\mathbb{F}% _{p_{\mathsf{Pallas}}},$
	$\displaystyle\mathrm{ToScalar}(x)$	$\displaystyle:=\mathsf{LEOS2IP}_{512}(x)\bmod p_{\mathsf{Vesta}}\in\mathbb{F}_% {p_{\mathsf{Vesta}}}$

(protocol specification, §“Orchard Key Components”).

For $x$ uniform on $\{0,1\}^{512}$ , the statistical distance of $\mathrm{ToBase}(x)$ from the uniform distribution on $\mathbb{F}_{p_{\mathsf{Pallas}}}$ is at most $p_{\mathsf{Pallas}}/2^{512}$ , and that of $\mathrm{ToScalar}(x)$ from the uniform distribution on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ at most $p_{\mathsf{Vesta}}/2^{512}$ (Math Guide, §“Uniform sampling and the bias of modular reduction”, Proposition “Bias of modular reduction”, with $L=512$ ). Both bounds are below $2^{-257}$ .

Construction 2.14 (Domain bytes of PRF expansion).

Every later use of $\mathsf{PRFexpand}$ derives one quantity as

y:=f\bigl{(}\mathsf{PRFexpand}_{\kappa}(b\,\|\,t^{\prime})\bigr{)},

where the lead byte $b$ , the key $\kappa$ , the remainder $t^{\prime}$ of the input and the reduction $f\in\{\mathrm{ToBase},\mathrm{ToScalar}\}$ , or no reduction, form one row of Table 3. Each row’s objects are defined in the section it names (protocol specification, §“Orchard Key Components” for $\mathtt{0x06}$ , $\mathtt{0x07}$ , $\mathtt{0x08}$ and $\mathtt{0x82}$ ; §“Sending Notes (Orchard)” for $\mathtt{0x04}$ , $\mathtt{0x09}$ and $\mathtt{0x0B}$ ).

$b$	Key $\kappa$	Remainder $t^{\prime}$	$f$	Output	Section
$\mathtt{0x06}$	$\mathsf{sk}$	$\varepsilon$	$\mathrm{ToScalar}$	$\mathsf{ask}$	§3.1
$\mathtt{0x07}$	$\mathsf{sk}$	$\varepsilon$	$\mathrm{ToBase}$	$\mathsf{nk}$	§3.1
$\mathtt{0x08}$	$\mathsf{sk}$	$\varepsilon$	$\mathrm{ToScalar}$	$\mathsf{r_{ivk}}$	§3.1
$\mathtt{0x82}$	$\mathrm{LE}_{256}(\mathsf{r_{ivk}})$	$\mathsf{I2LEOSP}_{256}(\mathsf{ak})\,\\|\,\mathsf{I2LEOSP}_{256}(\mathsf{nk})$	none	$\mathsf{dk}\,\\|\,\mathsf{ovk}$	§3.2
$\mathtt{0x04}$	$\mathsf{rseed}$	$\mathsf{I2LEOSP}_{256}(\rho)$	$\mathrm{ToScalar}$	$\mathsf{esk}$	§4.3
$\mathtt{0x09}$	$\mathsf{rseed}$	$\mathsf{I2LEOSP}_{256}(\rho)$	$\mathrm{ToBase}$	$\psi$	§4.3
$\mathtt{0x0B}$	$\mathsf{rseed}$	$\mathsf{LEBS2OSP}_{256}(\mathsf{g_{d}}^{\star})\,\\|\,\allowbreak\mathsf{LEBS2% OSP}_{256}(\mathsf{pk_{d}}^{\star})\,\\|\,\allowbreak\mathsf{I2LEOSP}_{64}(v)\,% \\|\,\allowbreak\mathsf{I2LEOSP}_{256}(\rho)\,\\|\,\allowbreak\mathsf{I2LEOSP}_{% 256}(\psi)$	$\mathrm{ToScalar}$	$\mathsf{rcm}$	§4.3

Table 3: Every lead byte of

\mathsf{PRFexpand}

used in this volume. The row

\mathtt{0x82}

applies no reduction: its

64

-byte output splits into

\mathsf{dk}

, the first

32

bytes, and

\mathsf{ovk}

, the last

32

bytes.

Lemma 2.15 (Independence of domain-separated expansions).

Let $k$ be uniform on $\{0,1\}^{256}$ and used only as a $\mathsf{PRFexpand}$ key. Let an efficient algorithm choose, possibly adaptively, pairwise distinct inputs $t_{1},\dots,t_{n}$ , in particular inputs with pairwise distinct leading bytes, and receive the answers. Under Assumption 2.12, the answers $(\mathsf{PRFexpand}_{k}(t_{1}),\dots,\mathsf{PRFexpand}_{k}(t_{n}))$ are computationally indistinguishable from $n$ independent uniform elements of $\{0,1\}^{512}$ . Consequently, for reductions $f_{i}\in\{\mathrm{ToBase},\mathrm{ToScalar}\}$ , the answers $(f_{i}(\mathsf{PRFexpand}_{k}(t_{i})))_{i}$ are computationally indistinguishable from independent uniform elements of the target fields, up to an additional statistical distance of at most the sum of the reduction distances. For a key within statistical distance $\delta$ of uniform, both conclusions hold with $\delta$ added.

Proof.

One hybrid replaces $\mathsf{PRFexpand}_{k}$ by a uniformly random function; the distinguishing advantage changes by at most the PRF advantage of the algorithm that runs the given one and forwards its queries to its own oracle (Assumption 2.12; adaptive queries are within the definition, Crypto Guide, §“Pseudorandom functions and permutations”, Remark “Necessity of adaptivity”). A random function, sampled lazily, answers each new input with a fresh uniform value, so its answers on pairwise distinct inputs are independent and uniform, also when each input depends on earlier answers. For the reduced answers, replacing each $f_{i}$ of a fresh uniform string by a fresh uniform field element changes the distribution of the whole interaction by at most the reduction distance of $f_{i}$ ; summing over $i$ bounds the total by the triangle inequality, and the post-processing by the algorithm does not increase it (Math Guide, §“Statistical distance”, Theorem “Properties of statistical distance”). A key within statistical distance $\delta$ of uniform changes the interaction, a function of the key and the algorithm’s coins, by at most $\delta$ , by the same theorem. □

The hypothesis of Lemma 2.15 holds for the spending key $\mathsf{sk}$ , and for $\mathsf{rseed}$ towards an adversary that sees $\mathsf{rseed}$ only through $\mathsf{PRFexpand}$ outputs; the note plaintext, which contains $\mathsf{rseed}$ , is treated in §10.2. It does not hold for the row $\mathtt{0x82}$ , whose key encodes the trapdoor $\mathsf{r_{ivk}}$ , which is also used in $\mathsf{Commit}^{\mathsf{ivk}}$ ; that row is covered by Assumption 3.13 in §3.2. The lemma is used in §3.1, in Lemma “Rejection in key generation” (§3.2), in Propositions 3.18, 3.17, 4.8, 6.10 and 10.6, in Proposition “Confidentiality of the outgoing ciphertext” (§10.3), in Theorems 12.9 and 12.12, and in Remark “Hypothesis (H) for honest keys” (§11.3).

Remark 2.16 (Hash roles).

Each hash is defined at its construction site. BLAKE2b-512 with personalisation Zcash_ExpandSeed serves $\mathsf{PRFexpand}$ (this subsection); BLAKE2b-512 without personalisation serves $\mathsf{hash\_to\_field}$ inside $\mathsf{GroupHash}$ (§2.2); personalised BLAKE2b-512 serves the RedPallas hash $\mathsf{H}$ (§7.1); BLAKE2b-256 serves the note-encryption key derivation and the outgoing cipher key (§10.2, §10.3); BLAKE2b serves the transaction and signature digests (§11.3); Sinsemilla serves $\mathsf{MerkleCRH}$ , $\mathsf{NoteCommit}$ and $\mathsf{Commit}^{\mathsf{ivk}}$ (§2.4); Poseidon serves the nullifier PRF, constructed with the nullifier (§6.1). The personalisations of $\mathsf{PRFexpand}$ , the note-encryption key derivation and the outgoing cipher key are those of the Crypto Guide’s inventory (§“PRFs from hash functions: length extension and keyed BLAKE2”, Remark “Zcash’s use of keyed and personalised BLAKE2”); every personalisation is stated at its construction.

2.4 Sinsemilla: hash, commitment, and short forms

Construction 2.17 (Sinsemilla hash on Pallas).

The Crypto Guide, §“Sinsemilla: an algebraic hash-based commitment”, Construction “Sinsemilla hash”, fixes the chunk width $k=10$ (written $w$ there, where $k$ counts the pieces), the table and the domain base

	$\displaystyle S(j)$	$\displaystyle:=\mathsf{GroupHash}\bigl{(}\texttt{z.cash:SinsemillaS},\,\mathsf% {I2LEOSP}_{32}(j)\bigr{)}\qquad(0\leq j<2^{k}),$
	$\displaystyle Q(D)$	$\displaystyle:=\mathsf{GroupHash}(\texttt{z.cash:SinsemillaQ},\,D)$

for a byte string $D$ , and the accumulator; it writes $\mathrm{LE}_{32}(j)$ for the four-byte encoding $\mathsf{I2LEOSP}_{32}(j)$ . The Orchard instance adds the following (protocol specification, §“Sinsemilla Hash Function”).

1.

The chunk bound $c$ is the largest integer with $2^{c}\leq(p_{\mathsf{Vesta}}-1)/2$ ; thus $c=253$ , and a message has at most $kc=2530$ bits.
2.

Incomplete addition $\dotplus$ on $\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})\cup\{\bot\}$ returns $\bot$ if either operand is $\bot$ ; for points it returns $\bot$ in an exceptional case, when an operand is $\mathcal{O}$ or the operands have equal $x$ -coordinates (equal or opposite points), and their group sum otherwise (Math Guide, §“Explicit affine formulas”, Remark “Complete versus incomplete addition”).
3.

For a byte string $D$ and a bit string $M$ of length at most $k c$ , let $n:=\lceil|M|/k\rceil\leq c$ , pad $M$ with zero bits to $n k$ bits, split the result into $k$ -bit pieces, and let $m_{i}$ be $\mathrm{LE}_{k}^{-1}$ of the $i$ -th piece, $1\leq i\leq n$ . Then

$\mathsf{Acc}_{0}:=Q(D),\qquad\mathsf{Acc}_{i}:=(\mathsf{Acc}_{i-1}\dotplus S(m% _{i}))\dotplus\mathsf{Acc}_{i-1}\quad(1\leq i\leq n),$

and $\mathsf{SinsemillaHashToPoint}(D,M):=\mathsf{Acc}_{n}$ . The output is $\bot$ exactly when some incomplete addition meets an exceptional case.

The extracted hash is

\mathsf{SinsemillaHash}(D,M):=\mathsf{Extract}_{\mathbb{P}}^{\bot}\bigl{(}% \mathsf{SinsemillaHashToPoint}(D,M)\bigr{)}\in\mathbb{F}_{p_{\mathsf{Pallas}}}% \cup\{\bot\}.

Construction 2.18 (Sinsemilla commitment and short commitment).

For a byte string $D$ , a bit string $M$ of length at most $k c$ and a trapdoor $r\in\mathbb{F}_{p_{\mathsf{Vesta}}}$ , let

\hat{M}:=\mathsf{SinsemillaHashToPoint}(D\,\|\,\texttt{-M},\,M),\qquad H_{D}:=% \mathsf{GroupHash}(D\,\|\,\texttt{-r},\,\varepsilon).

Then, with complete group addition,

	$\displaystyle\mathsf{SinsemillaCommit}_{r}(D,M)$	$\displaystyle:=\begin{cases}\hat{M}+[r]H_{D}&\text{if }\hat{M}\neq\bot,\\ \bot&\text{otherwise},\end{cases}$
	$\displaystyle\mathsf{ShortCommit}_{r}(D,M)$	$\displaystyle:=\mathsf{Extract}_{\mathbb{P}}^{\bot}\bigl{(}\mathsf{% SinsemillaCommit}_{r}(D,M)\bigr{)}\in\mathbb{F}_{p_{\mathsf{Pallas}}}\cup\{\bot\}$

(protocol specification, §“Sinsemilla commitments”). The domain $D$ is routed to the hash as $D\,\|\,\texttt{-M}$ and to the blinding base as $D\,\|\,\texttt{-r}$ with the empty message. The Crypto Guide constructs the commitment with a generic independent blinding generator (§“Sinsemilla: an algebraic hash-based commitment”, Construction “SinsemillaCommit”); the routing and the $\bot$ case are the Orchard additions.

The unblinded $\mathsf{SinsemillaHash}$ is deterministic and therefore not hiding; $\mathsf{ShortCommit}$ is its blinded counterpart. Proposition 2.24 and Lemma 2.26 state the security of both.

Construction 2.19 (Orchard instances).

The Orchard protocol uses three Sinsemilla instances, each with one fixed message length per domain, all within $c$ chunks (Table 4): $\mathsf{MerkleCRH}$ , a $\mathsf{SinsemillaHash}$ instance whose layout is given in §5.1; $\mathsf{NoteCommit}$ , a $\mathsf{SinsemillaCommit}$ instance whose layout is given in Definition 4.4; and $\mathsf{Commit}^{\mathsf{ivk}}$ , a $\mathsf{ShortCommit}$ instance defined next.

Instance	Form	Domain	Message bits	Chunks
$\mathsf{MerkleCRH}$	$\mathsf{SinsemillaHash}$	z.cash:Orchard-MerkleCRH	$10+2\cdot 255=520$	$52$
$\mathsf{NoteCommit}$	$\mathsf{SinsemillaCommit}$	z.cash:Orchard-NoteCommit	$2\cdot 256+64+2\cdot 255=1086$	$109$
$\mathsf{Commit}^{\mathsf{ivk}}$	$\mathsf{ShortCommit}$	z.cash:Orchard-CommitIvk	$2\cdot 255=510$	$51$

Table 4: The Orchard Sinsemilla instances. Each domain hashes messages of the single length shown, of at most

c=253

chunks of

k=10

bits.

Definition 2.20 (The key commitment).

For $x,y\in\mathbb{F}_{p_{\mathsf{Pallas}}}$ and $\mathsf{r_{ivk}}\in\mathbb{F}_{p_{\mathsf{Vesta}}}$ ,

\mathsf{Commit}^{\mathsf{ivk}}_{\mathsf{r_{ivk}}}(x,y):=\mathsf{ShortCommit}_{% \mathsf{r_{ivk}}}\bigl{(}\texttt{z.cash:Orchard-CommitIvk},\ \mathrm{LE}_{255}% (x)\,\|\,\mathrm{LE}_{255}(y)\bigr{)},

a $510$ -bit message (protocol specification, §“Sinsemilla commitments”). Its output is $\bot$ exactly when $\mathsf{SinsemillaHashToPoint}(\texttt{z.cash:Orchard-CommitIvk-M},\cdot)$ returns $\bot$ ; it is $0$ exactly when the commitment point is $\mathcal{O}$ (Lemma 2.3); otherwise it is the $x$ -coordinate of a non-identity point, an element of $\{1,\dots,p_{\mathsf{Pallas}}-1\}$ and hence, since $p_{\mathsf{Pallas}}<p_{\mathsf{Vesta}}$ , a non-zero Pallas scalar. The $x$ -coordinates of non-identity points form a set of $(p_{\mathsf{Vesta}}-1)/2$ elements, by Lemma 2.4 and because a group of odd prime order has no point with $y=0$ . The incoming viewing key of §3.2 is this instance applied to $(\mathsf{ak},\mathsf{nk})$ with trapdoor $\mathsf{r_{ivk}}$ ; the exclusion of the outputs $0$ and $\bot$ by key generation is stated there.

Remark 2.21 (Cost inside a proof).

Sinsemilla is used for its cost inside an arithmetic circuit with lookups, one table lookup and two incomplete additions over $\mathbb{F}_{p_{\mathsf{Pallas}}}$ per $k$ -bit chunk (Crypto Guide, §“Sinsemilla: an algebraic hash-based commitment”, Remark “Why Sinsemilla exists: cost inside a proof”; Halo 2 Guide, §“The lookup argument” and §“From statement to circuit: arithmetisation in practice”), and its collision resistance reduces to discrete logarithms on Pallas together with $\mathsf{GroupHash}$ modelled as a random oracle, not to discrete logarithms alone.

Assumption 2.22 (Discrete logarithms on Pallas).

For every classical probabilistic polynomial-time algorithm, given a generator $G$ of $\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ and $[s]G$ for $s$ uniform in $\mathbb{F}_{p_{\mathsf{Vesta}}}$ , the probability of outputting $s$ is negligible (Crypto Guide, §“The discrete logarithm problem”, Definition “Discrete logarithm problem, DLP”, instantiated on Pallas; Math Guide, §“The elliptic-curve discrete logarithm problem”). Concretely, the best known classical attack costs about $2^{126}$ group operations (Crypto Guide, §“Instantiation on elliptic curves; the Pasta curves”, Proposition “The Pasta curves against the criteria”); the level is cited, not recomputed.

Lemma 2.23 (Relations among fixed generators).

Under Assumptions 2.8 and 2.22, no efficient algorithm outputs, except with negligible probability, distinct inputs of $\mathsf{GroupHash}$ with values $P_{1},\dots,P_{t}$ and coefficients $a_{1},\dots,a_{t}\in\mathbb{F}_{p_{\mathsf{Vesta}}}$ , not all zero, with $\sum_{i}[a_{i}]P_{i}=\mathcal{O}$ .

Proof.

In the model of Assumption 2.8 a reduction receiving a challenge $Y=[s]G$ answers each new $\mathsf{GroupHash}$ input with $[u]G+[w]Y$ for fresh uniform $u,w\in\mathbb{F}_{p_{\mathsf{Vesta}}}$ , a uniform point and hence distributed as the oracle’s answer. For every value of $w$ exactly one $u$ is consistent with the answer, so the $w$ remain uniform and independent of the algorithm’s view. A relation $\sum_{i}[a_{i}]P_{i}=\mathcal{O}$ gives $c_{0}+c_{1}s=0$ with $c_{1}=\sum_{i}a_{i}w_{i}$ , which is non-zero except with probability $1/p_{\mathsf{Vesta}}$ , and then $s=-c_{0}c_{1}^{-1}$ (Crypto Guide, §“Pedersen vector commitments”, Theorem “Properties of the vector commitment”, proof; §“Hashing to a curve point”, Remark “Why NUMS generators are binding-safe”). □

Every later argument that ends in a non-trivial discrete-logarithm relation among values of $\mathsf{GroupHash}$ ends in this lemma.

Proposition 2.24 (Collision resistance of the Sinsemilla instances).

Consider an Orchard instance of Table 4 with message length $l$ , hash domain $D^{\prime}$ (z.cash:Orchard-MerkleCRH for $\mathsf{MerkleCRH}$ ; $D\,\|\,\texttt{-M}$ for a commitment instance with domain $D$ ) and, for a commitment instance, blinding base $H_{D}$ . Under Assumptions 2.22 and 2.8, no efficient algorithm outputs, except with negligible probability:

(i)

messages $M,M^{\prime}\in\{0,1\}^{l}$ whose hash points $P:=\mathsf{SinsemillaHashToPoint}(D^{\prime},M)$ and $P^{\prime}:=\mathsf{SinsemillaHashToPoint}(D^{\prime},M^{\prime})$ are not $\bot$ and satisfy $P=P^{\prime}$ with $M\neq M^{\prime}$ , or $P=-P^{\prime}$ ; hence, by Lemma 2.4, no $M\neq M^{\prime}$ with equal values of the extracted form $\mathsf{SinsemillaHash}$ other than $\bot$ ;
(ii)

for a commitment instance, openings $(M,r)$ and $(M^{\prime},r^{\prime})$ in $\{0,1\}^{l}\times\mathbb{F}_{p_{\mathsf{Vesta}}}$ whose commitments $C:=\mathsf{SinsemillaCommit}_{r}(D,M)$ and $C^{\prime}:=\mathsf{SinsemillaCommit}_{r^{\prime}}(D,M^{\prime})$ are not $\bot$ and satisfy $C=C^{\prime}$ with $M\neq M^{\prime}$ , or $C=-C^{\prime}$ ; hence no $M\neq M^{\prime}$ with equal values of $\mathsf{ShortCommit}$ other than $\bot$ ;
(iii)

a message in $\{0,1\}^{l}$ on which $\mathsf{SinsemillaHashToPoint}(D^{\prime},\cdot)$ returns $\bot$ , equivalently on which the $\mathsf{SinsemillaHash}$ or commitment form returns $\bot$ for every trapdoor.

Each such output yields efficiently a non-trivial discrete-logarithm relation among $Q(D^{\prime})$ , $S(0)$ , …, $S(2^{k}-1)$ and, in (ii), $H_{D}$ .

Proof.

The proof is by citation, with the Orchard steps made in place. The cited arguments are, in the Crypto Guide, §“Sinsemilla: an algebraic hash-based commitment”, Proposition “Collision resistance of Sinsemilla”, with the paragraph after it on the extracted coordinate and the fixed length, and Construction “SinsemillaCommit”; and the Security argument of the protocol specification, §“Sinsemilla Hash Function”: Lemma “An injectivity property for Sinsemilla”, the theorem “Collision resistance of SinsemillaHash and SinsemillaHashToPoint” with its note extending it to added terms with independent bases, which covers $\mathsf{SinsemillaCommit}$ and $\mathsf{ShortCommit}$ , and the theorem that a $\bot$ output of $\mathsf{SinsemillaHashToPoint}$ yields a non-trivial discrete-logarithm relation. These arguments write a non- $\bot$ output on the pieces $m=(m_{1},\dots,m_{n})$ as

\mathsf{SinsemillaHashToPoint}(D^{\prime},M)=[2^{n}]Q(D^{\prime})+\sum_{j=0}^{% 2^{k}-1}[\chi_{j}(m)]S(j),

(1)

where $\chi_{j}(m):=\sum_{i=1}^{n}2^{n-i}\delta_{m_{i},j}$ with $\delta$ the Kronecker delta, and with $[r]H_{D}$ added for a commitment. Equal outputs on distinct messages give

\textstyle\sum_{j}[\chi_{j}(m)-\chi_{j}(m^{\prime})]S(j)+[r-r^{\prime}]H_{D}=% \mathcal{O},

non-trivial because $m\mapsto\chi(m)$ is injective. Opposite outputs give

\textstyle[2^{n+1}]Q(D^{\prime})+\sum_{j}[\chi_{j}(m)+\chi_{j}(m^{\prime})]S(j% )+[r+r^{\prime}]H_{D}=\mathcal{O},

non-trivial because its coefficient on $Q(D^{\prime})$ is non-zero. An exceptional case at step $i$ has the form $[\alpha]\mathsf{Acc}_{i-1}+S(m_{i})=\mathcal{O}$ with $\alpha\in\{-1,1,2\}$ ; substituting (1) for $\mathsf{Acc}_{i-1}$ gives a relation with coefficient $\alpha\,2^{i-1}$ on $Q(D^{\prime})$ . For the hash forms the terms in $H_{D}$ are absent.

Three steps are made in place. (1) Each instance hashes one fixed length $l$ per domain, and $l$ is admissible: $n\leq c$ , with $n=52$ , $109$ and $51$ (Table 4). Admissibility is exactly the hypothesis under which no coefficient wraps modulo $p_{\mathsf{Vesta}}$ . Because $2^{n}\leq 2^{c}\leq(p_{\mathsf{Vesta}}-1)/2$ , each difference $\chi_{j}(m)-\chi_{j}(m^{\prime})$ has absolute value below $2^{n}<p_{\mathsf{Vesta}}$ and vanishes modulo $p_{\mathsf{Vesta}}$ only if it vanishes as an integer, so uniqueness of binary expansions makes $\chi$ injective; and $0<2^{n+1}\leq p_{\mathsf{Vesta}}-1$ and $0<|\alpha\,2^{i-1}|\leq 2^{n}$ keep the coefficient on $Q(D^{\prime})$ non-zero. Padding to $n k$ bits is injective on messages of the fixed length $l$ , so $M\neq M^{\prime}$ gives $m\neq m^{\prime}$ . (2) By the definition of incomplete addition, an instance returns $\bot$ exactly when some incomplete addition meets an exceptional case, the case the cited $\bot$ theorem treats. An operand $\mathcal{O}$ arises only if $Q(D^{\prime})$ or some $S(j)$ is $\mathcal{O}$ , itself a non-trivial relation, because an incomplete addition that meets no exceptional case never returns $\mathcal{O}$ . The commitment forms return $\bot$ exactly when the point hash does, for every trapdoor, since the blinding addition is complete. (3) The generators $Q(D^{\prime}),S(0),\dots,S(2^{k}-1)$ and $H_{D}$ are values of $\mathsf{GroupHash}$ on pairwise distinct inputs (Table 2), so the lemma on relations among fixed generators excludes each relation except with negligible probability. The consequences for the extracted forms follow from Lemma 2.4: equal extracted values other than $\bot$ come from equal or opposite points, which are the cases of (i) and (ii). □

Remark 2.25 (Fixed length).

The fixed-length hypothesis cannot be dropped. The point hash $\mathsf{SinsemillaHashToPoint}$ zero-pads its input to a multiple of $k$ bits, so for a message $M$ whose length is not a multiple of $k$ the messages $M$ and $M\,\|\,0$ collide with no discrete-logarithm relation. The specification requires collision resistance only between inputs of one fixed length for a given domain (protocol specification, §“Sinsemilla Hash Function”), and every Orchard domain hashes a single length.

Lemma 2.26 (Hiding and binding of SinsemillaCommit).

Let $D$ be a byte string and $l\leq kc$ a message length.

(i)

Perfect hiding: if $H_{D}\neq\mathcal{O}$ , then for every $M\in\{0,1\}^{l}$ with hash point $\hat{M}\neq\bot$ and $r$ uniform on $\mathbb{F}_{p_{\mathsf{Vesta}}}$ and independent of $M$ , the commitment $\mathsf{SinsemillaCommit}_{r}(D,M)$ is uniform on $\mathcal{E}(\mathbb{F}_{p_{\mathsf{Pallas}}})$ ; hence the distribution of neither it nor $\mathsf{ShortCommit}_{r}(D,M)$ , a fixed function of it, depends on $M$ .
(ii)

Computational binding: under Assumptions 2.22 and 2.8, no efficient algorithm outputs, except with negligible probability, openings $(M,r)$ and $(M^{\prime},r^{\prime})$ with $M\neq M^{\prime}$ in $\{0,1\}^{l}$ whose commitments $\mathsf{SinsemillaCommit}_{r}(D,M)$ and $\mathsf{SinsemillaCommit}_{r^{\prime}}(D,M^{\prime})$ are equal and not $\bot$ .

Proof.

The lemma is the Crypto Guide’s Construction “SinsemillaCommit” (§“Sinsemilla: an algebraic hash-based commitment”) for the Orchard blinding base. (i) Since $H_{D}\neq\mathcal{O}$ and the group has prime order $p_{\mathsf{Vesta}}$ , the map $r\mapsto[r]H_{D}$ is a bijection from $\mathbb{F}_{p_{\mathsf{Vesta}}}$ onto the group, so $[r]H_{D}$ is uniform, and so is its translate by the fixed point $\hat{M}$ (Crypto Guide, §“The Pedersen commitment”, Theorem “Perfect hiding”). (ii) Two such openings give the first relation in the proof of Proposition 2.24, whose coefficient vector on the $S(j)$ is non-zero for $n=\lceil l/k\rceil\leq c$ by step (1) of that proof. The only Orchard addition is the blinding base $H_{D}=\mathsf{GroupHash}(D\,\|\,\texttt{-r},\varepsilon)$ , whose input differs from those of $Q(D\,\|\,\texttt{-M})$ and of every $S(j)$ , since its domain separator ends in -r; the lemma on relations among fixed generators excludes the relation. The specification states the same properties, with hiding conditional on no $\bot$ output (protocol specification, §“Sinsemilla commitments”). □