This section defines digital signatures and their security against a forger: an adversary that may obtain the signer’s signature on messages of its choosing and succeeds if it then exhibits, without the secret key, a valid signature the signer never made. In Zcash a forged spend authorisation spends coins the forger does not control, and a forged balance certificate creates value. The section derives the Schnorr signature from an identification protocol, the first proof of knowledge of this volume, proves it unforgeable in the random oracle model (Theorem 8.18), and specialises it to the two RedDSA signatures of Orchard (protocol specification § 5.4.7): the spend authorisation signature, whose key pair can be re-randomised so that successive uses are unlinkable (protocol specification § 4.15), and the binding signature, which certifies the consistency of a transaction’s value commitments and proves knowledge of a discrete logarithm (protocol specification § 4.14). Signatures are the last primitive of this volume built directly on the discrete logarithm, and lead to the proof systems of Section 9.
The message authentication codes of §6.3 prevent forgery only between parties who share a secret key: verification runs Vrfy k , so whoever can check a tag can also compute one, and a tag is no evidence to a third party. A transaction’s authorisation must instead be checkable by every full node, none of whom may be able to forge it, and the check must be transferable: a block, once validated, convinces every other node. A digital signature provides this with two keys: signing uses a secret key s k , verification a matching public key p k . Anybody can verify; only the holder of s k can sign; and because verification needs no secret, a valid signature is non-repudiable evidence that the holder of s k signed. The cost is a computational assumption: the Carter–Wegman MAC of §6.3 is information-theoretically secure, whereas every signature scheme in this section rests on the hardness of the discrete logarithm.
Throughout, G is a cyclic group of prime order q , written
additively, with a fixed generator G ; scalar multiplication is
[x] P for
A digital signature scheme is a triple of PPT algorithms
KeyGen (1 λ) outputs a key pair (p k, s k) ;
Sign (s k, m) , for
Verify (p k, m, σ) is deterministic and outputs a bit.
Correctness requires that for every λ , every
(p k, s k) in the support of KeyGen (1 λ) , and
every
| Pr [Verify (p k, m, Sign (s k, m)) = 1] = 1, |
the probability over the coins of Sign . Probability- 1 correctness is called perfect; a scheme achieving only overwhelming-probability correctness tolerates a negl (λ) failure rate. Every scheme in this section is perfectly correct.
The security goal transcribes the MAC forgery game of Definition 6.8 into the public-key setting: the adversary additionally receives the verification key, and its oracle access models a signer who can be induced to sign arbitrary messages.
For a signature scheme Π and adversary A , the game Forge Π A (λ) runs as follows.
The challenger runs
The adversary A runs on input p k with oracle
access to
The game outputs 1 iff
Scheme Π is existentially unforgeable under chosen-message attack (EUF-CMA) if for every PPT A ,
| Adv Π forge (A, λ) : = Pr [Forge Π A (λ) = 1] ∈ negl (λ) . |
The oracle access is adaptive and bounded only by the adversary’s polynomial running time: the adversary may choose each query after seeing all previous signatures. The forgery is existential: the adversary wins with a valid signature on any message never submitted to the oracle, however meaningless.
The strong variant, sUF-CMA, replaces the winning condition
Plain EUF-CMA permits a scheme in which, given one valid signature, anyone can cheaply compute a second, different valid signature on the same message. Such malleability is harmless when a signature only certifies origin, but breaks any mechanism that uses a signature as a unique identifier, such as an anti-replay check that identifies a message by its signature.
The standard schemes—RSA, Schnorr, ECDSA—sign only fixed-size inputs: an element of Z / N Z for RSA, a scalar in F q for Schnorr and ECDSA. Arbitrary messages are hashed first.
Let Π ′ be a signature scheme with message space
Y λ , and let
| Sign (s k, m) := Sign ′ (s k, H (m)), Verify (p k, m, σ) := Verify ′ (p k, H (m), σ) . |
If Π ′ is EUF-CMA and H is collision resistant, then Π is EUF-CMA; concretely, for every adversary A against Π there are comparably efficient B 1 against H and B 2 against Π ′ with
| Pr [A wins] ≤ Adv H col (B 1) + Adv Π ′ forge (B 2) . |
Let (m ⋆, σ ⋆) be a valid forgery of
A on a fresh message
In all the Schnorr-type schemes below, the hash absorbs more than the message: the public key and the per-signature commitment value enter the hash alongside m . Hashing the public key prevents key-substitution (duplicate-signature) attacks, in which a signature valid under one key is exhibited as valid under another; hashing the commitment is exactly what the Fiat–Shamir transform of §8.5 requires. “Hash-and-sign” in practice thus hashes more than the message, and Theorem 8.4 captures only its message-compression part.
Every Schnorr-type scheme in the rest of this section derives from an interactive protocol in which a prover convinces a verifier that it knows the discrete logarithm of a public point without revealing anything about it. The protocol is the canonical Sigma-protocol: a three-move, public-coin, honest-verifier zero-knowledge (HVZK) proof of knowledge, a notion developed for arbitrary relations in Section 9.
The object of the protocol is the discrete-log relation
| R dl = { (X, x) ∈ G × F q : X = [x] G } : |
the statement is a public point X , the witness its discrete logarithm x .
Fix
Commitment. The prover samples
Challenge. The verifier samples
Response. The prover sends
The verifier accepts iff
| [s] G = R + [c] X . | (2) |
A triple (R, c, s) satisfying (2) is an accepting transcript for X . The verifier’s only message is a uniformly random value chosen independently of R , so the protocol is public-coin: the verifier keeps no secrets and exercises no discretion.
Figure 12 draws the three moves and the verifier’s check.
If prover and verifier are honest, the verifier accepts with probability 1 .
With
| [s] G = [r + c x] G = [r] G + [c x] G = R + [c] ([x] G) = R + [c] X, |
which is exactly (2). The computation holds identically for every choice of r and c . □
There is an efficient extractor that, given two accepting
transcripts (R, c, s) and (R, c ′, s ′) for the same statement
X with the same commitment R but distinct challenges
Both transcripts satisfy (2); subtracting the two equations in G cancels R :
| [s − s ′] G = [c − c ′] X = [(c − c ′) x] G . |
Since G generates a group of prime order q , equality of the
two multiples forces the equality of scalars
| x = (s − s ′) (c − c ′) − 1 ∈ F q . |
Verification that
Suppose a (possibly dishonest) prover makes the verifier accept with
probability ε noticeably larger than 1 / q —the
probability of guessing in advance the single challenge for which a
prepared response works. A rewinding extractor runs the prover once: it
records the commitment R , supplies a uniform challenge c , and
records whether the response is accepted. It then rewinds the
prover to the moment immediately after it sent R —restoring its
internal state, which is possible because the rewinding extractor runs
the prover as a subroutine—and supplies a fresh independent
challenge c ′ . A standard averaging argument shows that with
probability roughly ε 2 , both runs accept and
There is an efficient simulator Sim that, on input a
statement
The simulator computes the transcript in reverse: it samples
| R := [s] G − [c] X, |
and outputs (R, c, s) —accepting by construction, since (2) rearranges to exactly this definition of R .
Fix the challenge to c and compare distributions. In a real
honest transcript, r is uniform on F q ,
The simulator of Theorem 8.10 matches the real distribution only when the challenge is sampled independently of R . A cheating verifier could instead choose c as a function of R , and against such a verifier the argument for the simulator—which commits to R only after seeing c —no longer applies. For the signature schemes of this section honest-verifier zero knowledge suffices: after the Fiat–Shamir transform the challenge is a hash of R , and in the random oracle model that hash behaves like an honest, R -independent coin. The simulator also proves privacy: since anyone, without x , can produce transcripts with the true distribution, a transcript carries no information about x beyond what the statement X already reveals.
An identification protocol convinces one verifier in one interactive execution; a signature must be verifiable by any party, at any later time, without interaction. The Fiat–Shamir transform makes the prover compute the challenge itself, as a hash of everything the verifier would have seen before issuing it and of the message m . It converts any Sigma-protocol into a non-interactive proof, and, with a message in the hash, into a signature. This subsection treats the Schnorr instance; the general transform and its failure modes are treated in Section 9 (§“The Fiat–Shamir transform: from interactive to non-interactive”).
Fix
KeyGen (1 λ) : sample
Sign (x, m) : sample
| c = H (R ‖ X ‖ m), |
set
Verify (X, m, (R, s)) : recompute
The Schnorr signature scheme is perfectly correct.
For an honest signature (R, s) with
Construction 8.12 makes two presentational choices.
The signature transmits (R, s) and omits c , which the
verifier recomputes. The space-saving variant transmits
(c, s) instead: the verifier recovers
The hash takes the public key X alongside R and m —key-prefixing. The single-key unforgeability proof of §8.6 does not require it, but it forecloses attacks that relate signatures under different keys (Remark 8.5), it is standard in modern instantiations such as EdDSA, and it matters in the re-randomised setting of §8.8.
A Schnorr forgery (R ⋆, s ⋆) on a fresh message is an accepting transcript of the identification protocol whose challenge is H (R ⋆ ‖ X ‖ m ⋆) —a value the forger cannot choose freely if the hash is honest. The security argument makes “honest” precise by idealising H , then turns the rewinding of Remark 8.9 into a quantitative bound.
The random oracle of Definition 3.13 generalises
verbatim to an arbitrary finite range: a random oracle with range
Y is a function
The model remains a heuristic, with the uninstantiability caveat and the working stance of Remark 1.29: a ROM proof rules out all attacks that treat the hash as a black box—the overwhelming majority—and is the standard yardstick for Fiat–Shamir signatures. The reductions below exploit both powers of Proposition 3.14: programmability (the reduction chooses oracle answers on the fly, provided they appear uniform) and observability (the reduction sees every query the adversary makes).
The first step removes the signing oracle with the simulator of Theorem 8.10.
In the ROM there is an efficient simulator that, given only the
public key X and the ability to program H , answers signing
queries with signatures distributed identically to genuine ones,
except that it aborts with probability at most
To sign m without x : sample
| H (R ‖ X ‖ m) := c, |
and output (R, s) . The signature verifies by construction, and by Theorem 8.10 its distribution matches a real signature’s exactly: in both cases s is uniform, and c is uniform because a fresh oracle answer is.
Programming fails only if the entry H (R ‖ X ‖ m) is
already defined—by an earlier adversary hash query or an earlier
simulated signature. The point
With the EUF-CMA game simulated from X alone (Lemma 8.16), it remains to convert one forgery into two accepting transcripts on the same commitment, as Theorem 8.8 requires. The tool is the forking lemma, in the game-based form due to Bellare and Neven.
Fix an integer
| acc := Pr [I ≥ 1 : y ← Gen ; c 1, ..., c Q ← $ C ; (I, out) ← B (y, c 1, ..., c Q)] . |
Define the forking algorithm F B on input y : pick coins
ρ for B and
| frk := Pr [F B (y) ≠ ⊥ : y ← Gen] ≥ acc (acc Q − 1 h), |
the probability also over the coins of F B .
Condition on the coins ρ and the prefix
Model H as a random oracle with range F q . If an adversary A runs in time t , makes at most q h hash queries and q s signing queries, and forges with probability ε , then there is an algorithm D running in time approximately 2 t that computes discrete logarithms in G with probability
| ε ′ ≥ ε 2 q h + q s + 1 − q h + q s + 1 q − q s (q h + q s) q . |
In particular, if DLog is hard in G , the Schnorr signature scheme is EUF-CMA in the ROM.
Construct the algorithm B of
Theorem 8.17 around A , with input
Suppose A outputs a valid fresh forgery
(m ⋆, (R ⋆, s ⋆)) , and let
It remains to fork; Figure 13 draws the two runs. Both
runs of F B share the coins ρ and the challenge prefix
| x = (s ⋆ − s ′ ⋆) (c ⋆ − c ′ ⋆) − 1, |
the discrete logarithm of X . Substituting acc ,
The dominant term of Theorem 8.18 is
| ε 2 / q h = 2 − 80 / 2 60 = 2 − 140, |
a factor 2 100 weaker than ε itself. The
guarantee runs in the useful direction—any forger yields
some DLog solver, so DLog hardness still implies
security—but the quantitative content is weak. Two consequences
follow, and they must be distinguished. The first is conservative
(Remark 1.23): a designer who wants
this theorem to underwrite a target signature-security level
must provision G with roughly twice as many bits of DLog
security as the target, since the reduction hands back only the
square of the forger’s advantage; and the squaring is intrinsic to
the rewinding route—it enters at the squaring step of
Theorem 8.17, so any analysis that runs the
forger twice and extracts by special soundness incurs it. The second
is that the theorem does not establish a matching attack: the
loss belongs to the reduction, not provably to the scheme, so doubled
parameters are a cost of this proof, not a demonstrated
necessity, and parameter selection in practice weighs concrete
attack models and query bounds as well. Tighter reductions exist
once the rewinding route is abandoned—under the one-more
discrete logarithm assumption (that no efficient adversary, given
Suppose a signer produces two Schnorr signatures (R, s) and
(R, s ′) on distinct messages
The challenges
The security of the scheme therefore rests on the nonce being fresh and unpredictable for every signature. Nonce reuse is the classic operational failure of deployed Schnorr-family schemes, and motivates deriving nonces deterministically from the secret key and message, the defining idea of EdDSA.
This subsection defines EdDSA and its generalisation RedDSA, the scheme that Orchard instantiates for both of its signatures.
EdDSA retains the Schnorr signature algebra of Construction 8.12 unchanged and hardens two implementation surfaces.
Deterministic nonces. The nonce is derived as a hash of a secret prefix (part of the expanded secret key) and the message, rather than sampled fresh: no faulty random-number generator can repeat a nonce across distinct messages and trigger Proposition 8.20.
In the ROM the deterministic nonce is, to anyone ignorant of the secret prefix, a fresh uniform value per message, so the unforgeability proof of Theorem 8.18 carries over essentially unchanged.
RedDSA generalises EdDSA in two directions, both used by Orchard: the base point becomes a parameter, and the key pair can be shifted by a scalar.
RedDSA is the Schnorr/EdDSA scheme with the base point
KeyGen : sample
Sign (x, m) : sample a fresh random byte string
T and derive the nonce
Verify (X, m, (R, s)) : accept iff
For a fixed base point, RedDSA is Schnorr/EdDSA, and its EUF-CMA security in the ROM is Theorem 8.18 with G replaced by P .
The deployed scheme follows Construction 8.22
(protocol specification
§ 5.4.7),
with two additions to verification. It rejects unless R decodes to a point,
Orchard instantiates RedDSA twice, both times as RedPallas—RedDSA over the Pallas curve—and the two instantiations differ only in the base point:
the spend authorisation base point, derived by hashing to the curve with domain z.cash:Orchard and input G, for the re-randomisable signature of §8.8; and
the value-commitment randomness base point, derived with domain z.cash:Orchard-cv and input r, for the binding signature of §8.9, which relies on this base being byte-for-byte the randomness base of Orchard’s value commitment.
The curve varies only across protocol generations: Sapling’s
RedJubjub is the same scheme over the Jubjub curve;
the curve, with its cofactor
This subsection defines key re-randomisation, which Orchard uses to make spend authorisations unlinkable. Publishing the spender’s public key with each spend would link all spends by the same wallet; because a RedDSA public key is a homomorphic image of the secret, it can instead be shifted to a fresh, unlinkable key for every spend.
Fix a base point P . Given a secret key
| r s k := x + α ∈ F q, r k := X + [α] P ∈ G . |
The pair (r s k, r k) is a valid RedDSA key pair:
Linearity of scalar multiplication gives
| [r s k] P = [x + α] P = [x] P + [α] P = X + [α] P = r k . |
The pair is thus exactly KeyGen -shaped, and the correctness of signing and verification (Proposition 8.13) applies verbatim. □
Shifting the secret by α shifts the public key by [α] P , which is computable from α and P alone, without the secret key. A verifier, or a circuit, can therefore check the relationship between X and r k given α , while only the spender who knows x can sign under the shifted key.
Fix a base point P . For any public key
The point P generates G , which has prime order q , so
The guarantee is information-theoretic but holds only if α is
sampled uniformly and freshly per use and kept secret. In Orchard the
transaction builder samples
Theorem 8.26 covers only the re-randomised
key. Full unlinkability of a spend further requires that the
accompanying signature and zero-knowledge proof leak nothing beyond
their statements, that the randomiser α stays secret, and
that no other transaction field correlates two spends. In Orchard
the protocol publishes r k with each Action (the unit that
spends one note and creates one) while proving, inside the Halo 2
circuit, knowledge of a witness for
Unforgeability must be re-established under re-randomised keys. A
forgery (R, s) under r k satisfies
The second RedPallas instantiation certifies that value is conserved: the commitments hiding a shielded transaction’s amounts must balance, or the transaction creates money. The binding signature enforces this with the homomorphism of §4.6 and the fact that a Schnorr signature is a proof of knowledge of a discrete logarithm.
Shielded protocols commit to value with the homomorphic Pedersen commitment
| cm (v, ρ) = [v] V + [ρ] P, |
where V and P are independent generators of G —independent meaning that no party knows the discrete logarithm of one to the base of the other, arranged by deriving both by hashing to the curve (Construction 3.24)—and ρ is a random blinding scalar. (In the notation of Remark 4.21, the randomness base here called P is the generator R ; this section reserves R for the signature nonce point. The base P is exactly the binding base point of Remark 8.23.) By Theorem 4.20, the group sum of commitments commits to the sum of values with the sum of blindings.
Sapling commits per note: a transaction carries input commitments cm (v i in, ρ i in) and output commitments cm (v j out, ρ j out) , and the net commitment is
| B = ∑ i cm (v i in, ρ i in) − ∑ j cm (v j out, ρ j out) . |
Orchard has no per-note value commitments: each Action—the unit that simultaneously spends a note of value v old and creates a note of value v new —commits once to its net value change, publishing
| cv net = cm (v old − v new, ρ) = [v old − v new] V + [ρ] P, |
and
| B = [Δ v] V + [ρ ̄] P, |
where Δ v is the net value—
With B and ρ ̄ as above and the transaction balanced,
so that
In the ROM, a valid binding signature on a transaction is a proof of knowledge of the discrete logarithm of the net commitment B to the base P ; combined with the soundness of the accompanying zero-knowledge proofs (per Action in Orchard, per note in Sapling), which fix and range-check the committed values, it forces the transaction to balance.
Part 1: proof of knowledge. The binding signature is exactly
a Fiat–Shamir Schnorr proof for the relation R dl
with base P and statement B . By special soundness
(Theorem 8.8) together with the
forking argument of Theorem 8.18—
specialised to a single statement and no signing oracle—any
algorithm producing a valid signature under B with
non-negligible probability can be rewound to two accepting
transcripts (R, c, s) , (R, c ′, s ′) with
Part 2: knowledge forces balance. Write
| [Δ v] V = [ρ ̄ − ρ ̄ ′] P, |
where Δ v enters as a scalar, that is, as its residue in
F q . Whenever
| V = [(ρ ̄ − ρ ̄ ′) Δ v − 1] P |
—exhibiting log P V and contradicting the independence of
V and P . Therefore
Part 3: from congruence to equality. Balance in F q
alone is not yet economic balance: an integer net value equal to a
nonzero multiple of q would pass the test above while creating
q units in a single transaction. The gap is closed by the range
checks in the same accompanying proofs: in Orchard the per-Action
circuit constrains v old and v new to
In deployment the transaction is not internally balanced: it
declares a public balancing value v bal , and the
verifier checks the signature against
The single pair (R, s) accomplishes three things at once. First, it proves knowledge of ρ ̄ , certifying balance, by Theorem 8.30. Second, because the Fiat–Shamir challenge hashes the transaction sighash, the same signature authenticates the transaction: altering any signed field changes c and invalidates (R, s) , so the binding signature doubles as an integrity check binding the shielded components together—the origin of the name. Third, the construction needs no trusted setup and no separate circuit for the balance check: it is pure elliptic-curve arithmetic that anyone can verify. The homomorphism of the commitment turns the arithmetic statement “the values balance” into the algebraic statement “ B is a known multiple of P ”, and the Schnorr signature is the standard proof of knowledge for precisely that statement.
The spend authorisation signature verifies under a re-randomised key
Two signature schemes in the series live outside the Pallas group: the transparent layer authorises spends with ECDSA, and the issuance bundle of Zcash Shielded Assets is authorised with a BIP-340 Schnorr signature. Both run over secp256k1 and are recorded, not constructed from first principles, at the level their uses in the series require: syntax, deployed conventions, and the status of their security.
The curve secp256k1 is the short Weierstrass curve
Let
KeyGen : sample
Sign (d, e) : sample
Verify (X, e, (r, s)) : require
Correctness:
Where Schnorr’s challenge is a hash of R , ECDSA’s is the
coordinate r itself, so the scheme is not a Fiat–Shamir
transform and the forking-lemma route to
Theorem 8.18 does not apply.
Unforgeability analyses exist—in the generic group model, and in
the ROM under additional assumptions on the map
Three conventions fix how the transparent layer uses Construction 8.33, which protocol specification § 4.1.7 names as the script signature scheme.
The message is the sighash. The digest e is the 32 -byte SIGHASH transaction hash of protocol specification § 4.10 (ZIP 244 for version-5 transactions), so the sighash algorithm plays the role of the hash in Theorem 8.4.
DER encoding and the sighash-type byte. On the wire a signature is the DER encoding of (r, s) —an ASN.1 SEQUENCE of two minimally encoded INTEGERs—followed by one trailing byte, the sighash type, selecting which parts of the transaction the sighash commits to ( SIGHASH _ ALL for every signature the transaction builder emits; a signer working from a partially created transaction honours whichever valid type the input records). The signer appends the byte; the verifier splits it off and enforces strict DER unconditionally, the BIP-66 rule, so a malformed encoding fails script evaluation. The public key travels as its 33 -byte compressed encoding, the bytes that hash160 commits to (§3.9).
Low- s normalisation. If (r, s) verifies then so
does
Write
Keys. Sample
Sign (d, m) : derive
Verify (x (X), m, (r, s)) : lift x (X) to the
even- y point X , recompute e , set
The algebra is the Schnorr signature of
Construction 8.12 in its (R, s) form
with key-prefixing (Remark 8.14),
under