This section instantiates RedDSA, the re-randomisable Schnorr signature scheme of the Crypto Guide, on the Pallas group; constructs the randomised validating key and the spend-authorisation signature of an Action; and proves two properties of them: the published key is, with the signature scheme’s hash modelled as a random oracle, within negligible statistical distance of a key independent of the spend validating key; and a new valid signature under a randomised key yields the key’s discrete logarithm. The signed message is a parameter throughout; “Transaction digests and signatures” (§11.3) fixes it.
Requirement R5 of “Requirements on a shielded payment”
(§1.4) admits only the holder of a note’s spending authority
as a party that consumes the note. For keys generated with
The RedPallas hash is the map H from byte strings to 64 -byte strings
| H (z) := BLAKE2b - 512 (Zcash_RedPallasH, z), |
with the notation of the expansion function (§2.3) and the 16 -byte personalisation Zcash_RedPallasH. Its reduction to scalars is
| H ⊛ (z) := LEOS2IP 512 (H (z)) mod p Vesta = ToScalar (H (z)) ∈ F p Vesta |
(protocol specification, §“RedDSA, RedJubjub, and RedPallas” and §“BLAKE2 Hash Functions”). The symbol H ⊛ is that of the specification and of the Crypto Guide’s Remark “RedDSA as deployed” (§“RedDSA: re-randomisable Schnorr for Orchard”); it is distinct from the star encoding P ⋆ of a point.
In security arguments the RedPallas hash H is modelled as a random oracle with output length 512 , that is, with range the 64 -byte strings, queried by every party (Crypto Guide, §“The random oracle model”, Definition “Random oracle”). Consequently H ⊛ is a random function into F p Vesta : its values at distinct inputs are independent, and each is distributed as ToScalar (U) for U uniform on the 64 -byte strings. That distribution is at statistical distance at most
| δ 512 := p Vesta / 2 512 < 2 − 257 |
from the uniform distribution on F p Vesta (Math Guide,
§“Uniform sampling and the bias of modular reduction”, Proposition “Bias
of modular reduction”, with
RedPallas is the Crypto Guide’s Construction “RedDSA”
(§“RedDSA: re-randomisable Schnorr for Orchard”) on the Pallas group
E (F p Pallas) , of prime order p Vesta , with both hashes
H ⊛ and with a base point
Keys. A signing key is a scalar
Signing a message M under x : draw T uniformly from the
80 -byte strings, where
| r | := H ⊛ (T ‖ X ̄ ‖ M), | R | := [r] B, | ||
| c | := H ⊛ (R ̄ ‖ X ̄ ‖ M), | S | := r + c ⋅ x ∈ F p Vesta, |
and output the 64 -byte signature
Validation of a 64 -byte string σ under a point X on
M : let R ̄ be the first 32 bytes of σ and S ̄ the
last 32 ; let
| [S] B = R + [c] X . | (4) |
(Protocol specification, §“RedDSA, RedJubjub, and RedPallas”; its validation equation carries the cofactor, which is 1 on Pallas.)
The partial inverse abst P returns ⊥ on every 256 -bit
string that is not the star encoding of a point (§2.1);
validation therefore rejects a non-canonical R ̄ , and an accepted
signature has
The volume uses two instances of RedPallas, which share the signing and validation algorithms and differ in the base B and in the use of key re-randomisation (protocol specification, §“Spend Authorization Signature (Sapling and Orchard)” and §“Binding Signature (Sapling and Orchard)”):
the spend-authorisation instance, with key re-randomisation (§7.2) and base
| B = G SpendAuth = GroupHash (z.cash:Orchard, G) ; |
the binding-signature instance, without re-randomisation, used in “The binding signature” (§8.3), with base the value-commitment randomness base
| B = R Orchard = GroupHash (z.cash:Orchard-cv, r) . |
Both bases are rows of Table 3 (§2.2); the specification takes each as the generator parameter of RedDSA.
The randomiser generator GenRandom draws T uniformly from
the 80 -byte strings and returns
Let σ be valid under X on M , with decoded components R and S
and challenge
For each Action the spender draws a spend-authorisation randomiser
| rsk := ask + α ∈ F p Vesta, rk := ak P + [α] G SpendAuth ∈ E (F p Pallas), |
with ask the sign-normalised spend authorising key of the spending key of
the consumed note and ak P its spend validating key
(§3.1). Since
Under Assumption 7.3, let an algorithm, the observer, make at
most q h queries to H and, at one point, choose a byte string
w and receive
| δ 512 + q h ⋅ 2 − 640 | (5) |
of the pair obtained when α is replaced by a uniform element of
F p Vesta independent of all else. A randomiser from
GenRandom is the case
Let E be the event that the observer queries H at
T ∥ w . In a second experiment, H (T ∥ w) is replaced,
in the computation of α only, by a uniform 64 -byte string U
independent of all else. In the lazy realisation of the random oracle
(Crypto Guide, §“The random oracle model”, Definition “Random
oracle”) the answers at inputs
other than T ∥ w are independent of H (T ∥ w) , so the
two experiments are identical until E occurs; E has the same probability
in both, and their outputs are within statistical distance Pr [E]
(Crypto Guide, §“Security as a game”, Remark “Game-hopping”). In
the second experiment the observer’s view is independent of T , so each
query agrees with T ∥ w in its first 80 bytes with probability at
most 2 − 640 , and
Two consensus rules of the protocol specification, §“Action Descriptions”, concern spend authorisation:
the randomised validating key rk of an Action must not be the identity O ;
the spend-authorisation signature of the Action must be valid under rk on the signature digest of “Transaction digests and signatures” (§11.3).
Validation rejects a non-canonical encoding of the signature’s point
component (§7.1). An honestly computed rk
equals O only if
Let
If each α i is uniform on F p Vesta , the tuple
(rk 1, ..., rk n) is uniform on E (F p Pallas) n , whatever
the points ak i P , and hence independent of them. For each i
and the scalar ask i with
If each α i is drawn by GenRandom , then under Assumption 7.3, for an observer that receives the tuple and makes at most q h queries to H , the pair of its view and the tuple is within statistical distance
| n (δ 512 + (q h + n) ⋅ 2 − 640) |
of the pair obtained from a uniform tuple independent of H ; the
pairs arising from two assignments of the points are therefore within
statistical distance
(i) For each i this is the Crypto Guide’s Theorem “Perfect
unlinkability of re-randomised keys” (§“Key re-randomisation and
unlinkability”). The base G SpendAuth generates the Pallas
group, of prime order p Vesta (§7.1), so
(ii) The randomisers are replaced by independent uniform scalars one at a
time, for
| n δ 512 + (n q h + n (n − 1) 2) 2 − 640 ≤ n (δ 512 + (q h + n) ⋅ 2 − 640) . |
After the last step the α i are uniform, independent and independent of H , so by (i) the tuple is uniform and independent of H , for every assignment of the points. The triangle inequality through that common distribution gives the factor 2 for two assignments. □
The proposition concerns rk alone, for randomisers drawn by the honest
spender; a randomiser chosen by an adversary is the subject of
Proposition 7.12 (§7.3). The
spend-authorisation signature published with rk adds no information about
ak P : under Assumption 7.3 it is simulated from
rk and the message M alone by programming H (Crypto
Guide, §“Security in the random oracle model and the forking lemma”,
Lemma “Signature simulation”). The simulator draws u uniform on the
64 -byte strings and S uniform on F p Vesta , sets
Assume that discrete logarithms on Pallas are hard
(Assumption 2.22) and that H is a random oracle
(Assumption 7.3). Let x be uniform on F p Vesta and
| η := Q δ 512 + q s (q h + 2 q s) ⋅ 2 − 640 . |
Extraction. There is an algorithm D that
receives ak P but not x , runs A twice on shared coins,
answers its signing queries without x , and outputs a scalar rsk ∗
with
| (ε − η) 2 Q − Q p Vesta − q s (q h + q s) p Vesta (ε ≥ η), |
the bound of the Crypto Guide’s Theorem “EUF-CMA security of
Schnorr signatures in the ROM” (§“Security in the random oracle model
and the forking lemma”) with ε replaced by
Unforgeability under re-randomisation. If A also
outputs
With every randomiser zero, part (ii) is the existential unforgeability of RedPallas under chosen-message attack (Crypto Guide, §“Syntax and security goal”, Definition “Existential unforgeability under chosen-message attack”) in its strong form (Definition “Strong unforgeability” there), since freshness is required of the triple rather than of the message. Part (ii) implies the SURK-CMA requirement of the protocol specification, §“Signature with Re-Randomizable Keys”, whose forgery is a message–signature pair not returned by the oracle, hence a triple not returned by it.
The argument is route (ii) of the Crypto Guide’s Remark
“Unforgeability under re-randomised keys, and the key-prefixing subtlety”
(§“Key re-randomisation and unlinkability”), with the bound of its
Theorem “EUF-CMA security of Schnorr signatures in the ROM” (§“Security
in the random oracle model and the forking lemma”), which applies to
RedPallas with the generator replaced by the base G SpendAuth
(Construction “RedDSA”). The Orchard steps are made in place; write
(1) Idealisation. First, the nonce r i of each oracle answer is
replaced by a uniform scalar. By the lemma on the distance of
GenRandom from uniform, with
(2) Embedding. The reduction receives a discrete-logarithm challenge
(3) Signing. It answers the i -th query (α i, M i) without
x , under
(4) Critical query. Let (rk ∗, M ∗, σ ∗) be a forgery,
with
(5) Fork. The reduction wraps A as the algorithm of the
Crypto Guide’s Theorem “General forking lemma” (§“Security in the
random oracle model and the forking lemma”), with challenge set
F p Vesta , Q prepared challenges
(6) Extraction. The transcripts (R ∗, c, S ∗) and
(R ∗, c ′, S ′ ∗) are accepting for rk ∗ with
| rsk ∗ = (S ∗ − S ′ ∗) (c − c ′) − 1, |
the discrete logarithm of rk ∗ , which is (i). For (ii) the reduction
outputs
| frk ≥ acc (acc Q − 1 p Vesta), |
with acc at least