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 from byte strings to -byte strings
with the notation of the expansion function (§2.3) and the -byte personalisation Zcash_RedPallasH. Its reduction to scalars is
(protocol specification, §“RedDSA, RedJubjub, and RedPallas” and §“BLAKE2 Hash Functions”). The symbol 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 of a point.
In security arguments the RedPallas hash is modelled as a random oracle with output length , that is, with range the -byte strings, queried by every party (Crypto Guide, §“The random oracle model”, Definition “Random oracle”). Consequently is a random function into : its values at distinct inputs are independent, and each is distributed as for uniform on the -byte strings. That distribution is at statistical distance at most
from the uniform distribution on (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
, of prime order , with both hashes
and with a base point
Keys. A signing key is a scalar
Signing a message under : draw uniformly from the
-byte strings, where
and output the -byte signature
Validation of a -byte string under a point on
: let be the first bytes of and the
last ; let
| (4) |
(Protocol specification, §“RedDSA, RedJubjub, and RedPallas”; its validation equation carries the cofactor, which is on Pallas.)
The partial inverse returns on every -bit
string that is not the star encoding of a point (§2.1);
validation therefore rejects a non-canonical , and an accepted
signature has
The volume uses two instances of RedPallas, which share the signing and validation algorithms and differ in the base 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
the binding-signature instance, without re-randomisation, used in “The binding signature” (§8.3), with base the value-commitment randomness base
Both bases are rows of Table 3 (§2.2); the specification takes each as the generator parameter of RedDSA.
The randomiser generator draws uniformly from
the -byte strings and returns
Let be valid under on , with decoded components and
and challenge
For each Action the spender draws a spend-authorisation randomiser
with the sign-normalised spend authorising key of the spending key of
the consumed note and its spend validating key
(§3.1). Since
Under Assumption 7.3, let an algorithm, the observer, make at
most queries to and, at one point, choose a byte string
and receive
| (5) |
of the pair obtained when is replaced by a uniform element of
independent of all else. A randomiser from
is the case
Let be the event that the observer queries at
. In a second experiment, is replaced,
in the computation of only, by a uniform -byte string
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 are independent of , so the
two experiments are identical until occurs; has the same probability
in both, and their outputs are within statistical distance
(Crypto Guide, §“Security as a game”, Remark “Game-hopping”). In
the second experiment the observer’s view is independent of , so each
query agrees with in its first bytes with probability at
most , and
Two consensus rules of the protocol specification, §“Action Descriptions”, concern spend authorisation:
the randomised validating key of an Action must not be the identity ;
the spend-authorisation signature of the Action must be valid under 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
equals only if
Let
If each is uniform on , the tuple
is uniform on , whatever
the points , and hence independent of them. For each
and the scalar with
If each is drawn by , then under Assumption 7.3, for an observer that receives the tuple and makes at most queries to , the pair of its view and the tuple is within statistical distance
of the pair obtained from a uniform tuple independent of ; the
pairs arising from two assignments of the points are therefore within
statistical distance
(i) For each this is the Crypto Guide’s Theorem “Perfect
unlinkability of re-randomised keys” (§“Key re-randomisation and
unlinkability”). The base generates the Pallas
group, of prime order (§7.1), so
(ii) The randomisers are replaced by independent uniform scalars one at a
time, for
After the last step the are uniform, independent and independent of , so by (i) the tuple is uniform and independent of , for every assignment of the points. The triangle inequality through that common distribution gives the factor for two assignments. □
The proposition concerns 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 adds no information about
: under Assumption 7.3 it is simulated from
and the message alone by programming (Crypto
Guide, §“Security in the random oracle model and the forking lemma”,
Lemma “Signature simulation”). The simulator draws uniform on the
-byte strings and uniform on , sets
Assume that discrete logarithms on Pallas are hard
(Assumption 2.22) and that is a random oracle
(Assumption 7.3). Let be uniform on and
Extraction. There is an algorithm that
receives but not , runs twice on shared coins,
answers its signing queries without , and outputs a scalar
with
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 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
(Construction “RedDSA”). The Orchard steps are made in place; write
(1) Idealisation. First, the nonce of each oracle answer is
replaced by a uniform scalar. By the lemma on the distance of
from uniform, with
(2) Embedding. The reduction receives a discrete-logarithm challenge
(3) Signing. It answers the -th query without
, under
(4) Critical query. Let be a forgery,
with
(5) Fork. The reduction wraps 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
, prepared challenges
(6) Extraction. The transcripts and
are accepting for with
the discrete logarithm of , which is (i). For (ii) the reduction
outputs
with at least