The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

8 Digital signatures

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.

8.1 Signatures versus MACs

The message authentication codes of §6.3 prevent forgery only between parties who share a secret key: verification runs Vrfyk, 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 sk, verification a matching public key pk. Anybody can verify; only the holder of sk can sign; and because verification needs no secret, a valid signature is non-repudiable evidence that the holder of sk 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.

Conventions for this section.

Throughout, 𝔾 is a cyclic group of prime order q, written additively, with a fixed generator G; scalar multiplication is [x]P for x∈𝔽q and P∈𝔾. Concretely 𝔾 is the Pallas group of §2.6, whose order is the 255-bit prime q, so scalars are elements of the field 𝔽q. Because 𝔾 has prime order and G generates it, the map x↦[x]G is a bijection 𝔽q→𝔾: the discrete logarithm of any P∈𝔾 to base G always exists and is unique. Hardness of computing it is the DLog assumption of §2.1, transcribed additively.

8.2 Syntax and security goal

Definition 8.1 (Digital signature scheme).

A digital signature scheme is a triple of PPT algorithms Π=(KeyGen,Sign,Verify) with, for each security parameter λ, a message space ℳλ:

  • •

    KeyGen(1λ) outputs a key pair (pk,sk);

  • •

    Sign(sk,m), for m∈ℳλ, outputs a signature σ;

  • •

    Verify(pk,m,σ) is deterministic and outputs a bit.

Correctness requires that for every λ, every (pk,sk) in the support of KeyGen(1λ), and every m∈ℳλ,

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.

Definition 8.2 (Existential unforgeability under chosen-message attack).

For a signature scheme Π and adversary 𝒜, the game 𝖥𝗈𝗋𝗀𝖾Π𝒜(λ) runs as follows.

  1. 1.

    The challenger runs (pk,sk)←KeyGen(1λ).

  2. 2.

    The adversary 𝒜 runs on input pk with oracle access to Sign(sk,⋅); let Q be the set of messages it submits to the oracle, and let (m⋆,σ⋆) be its output.

  3. 3.

    The game outputs 1 iff Verify(pk,m⋆,σ⋆)=1 and m⋆∉Q.

Scheme Π is existentially unforgeable under chosen-message attack (EUF-CMA) if for every PPT 𝒜,

AdvΠforge⁢(𝒜,λ):=Pr⁡[𝖥𝗈𝗋𝗀𝖾Π𝒜⁢(λ)=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.

Definition 8.3 (Strong unforgeability).

The strong variant, sUF-CMA, replaces the winning condition m⋆∉Q by: the pair (m⋆,σ⋆) was not among the message–signature pairs returned by the oracle.

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.

8.3 The hash-and-sign paradigm

The standard schemes—RSA, Schnorr, ECDSA—sign only fixed-size inputs: an element of ℤ/Nℤ for RSA, a scalar in 𝔽q for Schnorr and ECDSA. Arbitrary messages are hashed first.

Theorem 8.4 (Hash-and-sign).

Let Π′ be a signature scheme with message space 𝒴λ, and let H:{0,1}∗→𝒴λ be drawn from a collision-resistant family (Definition 3.7). Define Π with message space {0,1}∗ by

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 𝒜 against Π there are comparably efficient ℬ1 against H and ℬ2 against Π′ with

Pr⁡[𝒜⁢ wins]≤AdvHcol⁢(ℬ1)+AdvΠ′forge⁢(ℬ2).
Proof.

Let (m⋆,σ⋆) be a valid forgery of 𝒜 on a fresh message m⋆∉Q, and distinguish two cases according to its digest. Case 1: the digest is reused, i.e. H(m⋆)=H(m) for some queried m∈Q. Then m⋆≠m but their digests agree, so the pair (m⋆,m) is a collision in H; the reduction ℬ1, which generates a key pair with KeyGen′ itself and answers 𝒜’s signing queries by signing digests under that secret key—the collision game grants no signing oracle—outputs it. Case 2: the digest is fresh, i.e. H(m⋆) differs from the digest of every queried message. Then (H(m⋆),σ⋆) is a valid forgery against Π′ on a message never submitted to its signing oracle, and ℬ2 outputs it. The two cases are exhaustive, so the union bound on the winning event gives the stated inequality. □

Remark 8.5 (Inputs of the hash in hash-and-sign).

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.

8.4 The Schnorr identification protocol

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

Rdl={(X,x)∈𝔾×𝔽q:X=[x]⁢G}:

the statement is a public point X, the witness its discrete logarithm x.

Construction 8.6 (Schnorr identification).

Fix 𝔾=⟨G⟩ of prime order q. The prover holds a secret key x∈𝔽q; both parties hold the public key X=[x]G. The protocol has three moves.

  1. 1.

    Commitment. The prover samples r←$𝔽q uniformly and sends R=[r]G. We call R the commitment (or nonce point) and r the nonce.

  2. 2.

    Challenge. The verifier samples c←$𝔽q uniformly and sends c.

  3. 3.

    Response. The prover sends s=r+cx in 𝔽q.

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.

Proposition 8.7 (Perfect completeness).

If prover and verifier are honest, the verifier accepts with probability 1.

Proof.

With R=[r]G, X=[x]G and s=r+cx, linearity of scalar multiplication gives

[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. □

Refer to caption
Figure 12: The three moves of Construction 8.6 in 𝔾=⟨G⟩ of prime order q. The prover, holding the witness x of the statement X=[x]G, commits to a fresh nonce r by sending R=[r]G; the verifier answers with a uniform challenge c; the prover responds with s=r+cx in 𝔽q. The verifier accepts iff [s]G=R+[c]X, equation (2); only the prover holds a secret (red).
Theorem 8.8 (2-special soundness).

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 c≠c′, outputs the discrete logarithm x of X.

Proof.

Both transcripts satisfy (2); subtracting the two equations in 𝔾 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 s−s′=(c−c′)x in 𝔽q. The hypothesis c≠c′ makes c−c′ a nonzero element of the field 𝔽q, hence invertible, so the extractor outputs

x=(s−s′)⁢(c−c′)−1∈𝔽q.

Verification that X=[x]G is direct, and the whole computation costs a single field inversion. □

Remark 8.9 (From special soundness to knowledge, by rewinding).

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 c≠c′; the argument is the heavy-row lemma, an instance of Markov’s inequality applied to the matrix whose rows are the prover’s random coins and whose columns are challenges (Math Guide, §“Random variables and expectation”). The two accepting transcripts share R, so the extractor of Theorem 8.8 recovers x. Making the verifier accept with non-trivial probability is therefore, up to rewinding, the same as knowing x. The same rewinding argument, sharpened into the forking lemma, carries the signature analysis of §8.6.

Theorem 8.10 (Special honest-verifier zero knowledge).

There is an efficient simulator Sim that, on input a statement X∈𝔾 and a challenge c∈𝔽q, outputs an accepting transcript (R,c,s) distributed identically to an honest execution conditioned on the challenge being c. Consequently, for a uniform challenge, the distribution of simulated transcripts coincides exactly with the distribution of real ones.

Proof.

The simulator computes the transcript in reverse: it samples s←$𝔽q uniformly, sets

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 𝔽q, R=[r]G, and s=r+cx; the map r↦r+cx is a translation of 𝔽q, hence a bijection, so s is uniform on 𝔽q, and R=[s−cx]G=[s]G−[c]X is the same deterministic function of s that the simulator uses. The real transcript is: sample s uniform, set R=[s]G−[c]X—precisely the simulated distribution. The two distributions are identical, not merely statistically close, and averaging over a uniform c preserves the identity. □

Remark 8.11 (Why honest-verifier zero knowledge suffices).

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.

8.5 From identification to signature via the Fiat–Shamir transform

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”).

Construction 8.12 (Schnorr signature).

Fix 𝔾=⟨G⟩ of prime order q and a hash function H:{0,1}∗→𝔽q. Messages are arbitrary bit strings.

  • •

    KeyGen(1λ): sample x←$𝔽q, set X=[x]G, output (pk,sk)=(X,x).

  • •

    Sign(x,m): sample r←$𝔽q, set R=[r]G, compute the challenge

    c=H⁢(R⁢‖X‖⁢m),

    set s=r+cx in 𝔽q, and output σ=(R,s).

  • •

    Verify(X,m,(R,s)): recompute c=H(R‖X‖m) and accept iff [s]G=R+[c]X.

Proposition 8.13 (Perfect correctness).

The Schnorr signature scheme is perfectly correct.

Proof.

For an honest signature (R,s) with R=[r]G, c=H(R‖X‖m) and s=r+cx, the verifier recomputes the same c—the challenge is a deterministic function of (R,X,m), all of which the verifier holds—and the check [s]G=R+[c]X holds by the completeness computation of Proposition 8.7. □

Remark 8.14 (Two conventions).

Construction 8.12 makes two presentational choices.

  1. 1.

    The signature transmits (R,s) and omits c, which the verifier recomputes. The space-saving variant transmits (c,s) instead: the verifier recovers R=[s]G−[c]X (the simulator’s equation, read as reconstruction) and checks H(R‖X‖m)=c. The two are interchangeable; the deployed schemes below use the (R,s) form.

  2. 2.

    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.

8.6 Security in the random oracle model and the forking lemma

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.

Definition 8.15 (Random oracle, general range).

The random oracle of Definition 3.13 generalises verbatim to an arbitrary finite range: a random oracle with range Y is a function 𝒪:{0,1}∗→Y drawn uniformly from the set of all such functions, realised lazily by sampling each new answer 𝒪(z)←$Y on first query. For Schnorr signatures the range is the challenge space Y=𝔽q, and the ROM for signatures models H(⋅)=𝒪(⋅), with every party—signer, verifier, forger, and reduction—sharing oracle access (Definition 1.26).

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.

Lemma 8.16 (Signature simulation).

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 qs(qs+qh)/q over an attack making qs signing and qh hash queries.

Proof.

To sign m without x: sample c←$𝔽q and s←$𝔽q uniformly, set R:=[s]G−[c]X—the HVZK simulator of Theorem 8.10—then program

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 R=[s]G−[c]X is a fixed translate of [s]G for uniform s, hence uniform over the q elements of 𝔾; at most qh+qs oracle entries exist at any point of the attack, so a given signing query collides with probability at most (qh+qs)/q, and the union bound over qs signing queries gives the stated abort probability. Conditioned on no abort, the adversary’s view is identical to the real game. □

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.

Theorem 8.17 (General forking lemma).

Fix an integer Q≥1, a finite set C with |C|=h≥2, and a randomised input generator Gen. Let B be a randomised algorithm that on input y and challenges c1,…,cQ∈C returns a pair (I,𝑜𝑢𝑡) with I∈{0,1,…,Q}, where I=0 means failure, and let

𝑎𝑐𝑐:=Pr⁡[I≥1:y←Gen;c1,…,cQ←$C;(I,𝑜𝑢𝑡)←B⁢(y,c1,…,cQ)].

Define the forking algorithm FB on input y: pick coins ρ for B and c1,…,cQ←$C; run (I,𝑜𝑢𝑡)←B(y,c1,…,cQ;ρ); if I=0, return ⊥; otherwise resample c′I,…,c′Q←$C afresh and run (I′,𝑜𝑢𝑡′)←B(y,c1,…,cI−1,c′I,…,c′Q;ρ) with the same coins ρ; if I′=I and cI≠c′I, return (I,𝑜𝑢𝑡,𝑜𝑢𝑡′), else ⊥. Then

𝑓𝑟𝑘:=Pr[FB(y)≠⊥:y←Gen]≥𝑎𝑐𝑐(𝑎𝑐𝑐Q−1h),

the probability also over the coins of FB.

Proof idea.

Condition on the coins ρ and the prefix c1,…,cI−1 up to the forking point. For each fixed prefix there is (averaging over the suffix) a set S of good values of cI on which B succeeds with index I; write p=|S|/h. The fork succeeds at this prefix iff the first draw cI and the independent re-draw c′I both land in S and differ: two independent uniform draws land in S together with probability p2, and subtracting the diagonal of equal draws costs at most p⋅1/h, so the per-prefix fork probability is at least p(p−1/h). Taking expectations over prefixes, 𝔼[p2]≥(𝔼⁢[p])2, since 𝔼[p2]−(𝔼⁢[p])2=𝔼[(p−𝔼⁢[p])2]≥0 by linearity of expectation (Math Guide, §“Random variables and expectation”); this squares the average success probability. The index I ranging over Q possible positions introduces the factor 1/Q, and collecting terms yields 𝑓𝑟𝑘≥𝑎𝑐𝑐2/Q−𝑎𝑐𝑐/h. The squaring step is where the squared probability—and hence the tightness loss examined below—enters. □

Theorem 8.18 (EUF-CMA security of Schnorr signatures in the ROM).

Model H as a random oracle with range 𝔽q. If an adversary 𝒜 runs in time t, makes at most qh hash queries and qs signing queries, and forges with probability ε, then there is an algorithm 𝒟 running in time approximately 2t that computes discrete logarithms in 𝔾 with probability

ε′≥ε2qh+qs+1−qh+qs+1q−qs⁢(qh+qs)q.

In particular, if DLog is hard in 𝔾, the Schnorr signature scheme is EUF-CMA in the ROM.

Proof structure.

Construct the algorithm B of Theorem 8.17 around 𝒜, with input y=X—the DLog challenge, so Gen outputs X=[x]G for uniform x—challenge set C=𝔽q (so h=q), and Q=qh+qs+1 prepared challenges. Algorithm B runs 𝒜 on pk=X, answering the j-th distinct hash query with cj from its challenge list and answering signing queries by the simulator of Lemma 8.16, whose programming aborts cost the qs(qh+qs)/q term.

Suppose 𝒜 outputs a valid fresh forgery (m⋆,(R⋆,s⋆)), and let c⋆=H(R⋆‖X‖m⋆). The critical hash input R⋆‖X‖m⋆ must actually have been queried during the run: otherwise c⋆ is a uniform value 𝒜 has never seen, and the verification equation [s⋆]G=R⋆+[c⋆]X then holds only with probability 1/q over the oracle’s choice—the (qh+qs+1)/q term collects these guessing events (the +1 covering the query B itself makes to verify the forgery). So B outputs the index I of the critical query together with 𝑜𝑢𝑡=(R⋆,c⋆,s⋆,m⋆), and 𝑎𝑐𝑐≥ε minus the loss terms above.

It remains to fork; Figure 13 draws the two runs. Both runs of FB share the coins ρ and the challenge prefix c1,…,cI−1, which together determine 𝒜’s behaviour up to the moment it produces the critical query; both runs therefore query the same critical input R⋆‖X‖m⋆ at index I, but receive different answers c⋆≠c′⁣⋆. Success of the fork yields two accepting transcripts (R⋆,c⋆,s⋆) and (R⋆,c′⁣⋆,s′⁣⋆) with the same commitment and distinct challenges, whereupon the extractor of Theorem 8.8 computes

x=(s⋆−s′⁣⋆)⁢(c⋆−c′⁣⋆)−1,

the discrete logarithm of X. Substituting 𝑎𝑐𝑐, h=q and Q=qh+qs+1 into 𝑓𝑟𝑘≥𝑎𝑐𝑐2/Q−𝑎𝑐𝑐/h gives the stated bound; the running time is two runs of 𝒜 plus bookkeeping. □

Refer to caption
Figure 13: The fork in the proof of Theorem 8.18, an execution of the forking algorithm FB of Theorem 8.17. Both runs of B take the same input y=X and coins ρ, and answer the first I−1 distinct hash queries with the same c1,…,cI−1 (grey band), so they coincide up to the I-th query, the critical input R⋆‖X‖m⋆. There run 1 receives cI=c⋆ (blue) and run 2 a fresh c′I=c′⁣⋆ (amber), and each continues with its own remaining challenges. When both forge with the same index I and c⋆≠c′⁣⋆, the outputs are two accepting transcripts with the common commitment R⋆ and distinct challenges, from which the extractor of Theorem 8.8 computes the discrete logarithm x of X (red).
Example 8.19 (The tightness loss, in numbers).

The dominant term of Theorem 8.18 is ε′≳ε2/qh: the reduction runs the forger twice and squares its success probability, divided by the number of hash queries. The reduction is therefore far from tight (Definition 1.22). Concretely, a forger succeeding with probability ε=2−40 after qh=260 hash queries yields a guaranteed DLog-solver advantage of only about

ε2/qh= 2−80/260= 2−140,

a factor 2100 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 𝔾 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 ℓ+1 random elements of 𝔾 and ℓ queries to a discrete-logarithm oracle, outputs all ℓ+1 logarithms), under DDH (Definition 2.5) together with key-prefixing, or in the idealised algebraic models of Remark 1.30.

Proposition 8.20 (Nonce reuse reveals the secret key).

Suppose a signer produces two Schnorr signatures (R,s) and (R,s′) on distinct messages m≠m′ with the same commitment R—a nonce r reused outright, or drawn twice from a faulty source. Then, except with probability 1/q over the challenge hash, anyone can compute the secret key from the two signatures.

Proof.

The challenges c=H(R‖X‖m) and c′=H(R‖X‖m′) differ except with probability 1/q, the chance that the random oracle answers the two distinct inputs identically. Given c≠c′, the pairs (R,c,s) and (R,c′,s′) are two accepting transcripts sharing a commitment with distinct challenges, and the extractor of Theorem 8.8—run in this case by the adversary—outputs x=(s−s′)(c−c′)−1. □

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.

8.7 RedDSA: re-randomisable Schnorr for Orchard

This subsection defines EdDSA and its generalisation RedDSA, the scheme that Orchard instantiates for both of its signatures.

Construction 8.21 (EdDSA, schematically).

EdDSA retains the Schnorr signature algebra of Construction 8.12 unchanged and hardens two implementation surfaces.

  1. 1.

    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.

  2. 2.

    Key-prefixing. The challenge hash absorbs the public key alongside R and m, as in Construction 8.12 and for the reasons of Remark 8.14.

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.

Construction 8.22 (RedDSA).

RedDSA is the Schnorr/EdDSA scheme with the base point P∈𝔾 a parameter of the scheme: different uses sign with respect to different generators.

  • •

    KeyGen: sample x←$𝔽q, output secret key x and public key X=[x]P.

  • •

    Sign(x,m): sample a fresh random byte string T and derive the nonce r=H(T‖X‖m). This is randomised, hash-based nonce generation: unlike EdDSA’s derivation, it is not deterministic from the signing key and message, so its safety rests on T being fresh and unpredictable, the hashing ensuring only that a repeated T cannot repeat a nonce across distinct messages. Set R=[r]P, c=H(R‖X‖m)∈𝔽q, s=r+cx, and output σ=(R,s).

  • •

    Verify(X,m,(R,s)): accept iff [s]P=R+[c]X with c=H(R‖X‖m).

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.

Remark 8.23 (RedDSA as deployed).

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, s<q, and, from the NU5 network upgrade onward, the encoding of R is canonical (ZIP 216); and it checks the equation multiplied by the cofactor h of the curve, [h](R+[c]X−[s]P)=𝒪, which for Pallas (h=1) is the equation of the Construction. The randomiser T is 80 uniform bytes, and both hashes are the function 𝖧⊛: BLAKE2b-512 personalised with Zcash_RedPallasH, its 64-byte output reduced to 𝔽q by wide reduction— the expand-then-reduce discipline of Construction 3.18, with the 512-bit width making the modular bias negligible. The nonce hash absorbs T‖X‖m and the challenge hash R‖X‖m, key-prefixed in both cases.

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 h=8 in the verification equation, its two base points and the 𝖧⊛ personalisation (Zcash_RedJubjubH against Zcash_RedPallasH) are all that distinguish the two.

8.8 Key re-randomisation and unlinkability

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.

Definition 8.24 (Key re-randomisation).

Fix a base point P. Given a secret key x∈𝔽q with public key X=[x]P, and a randomiser α∈𝔽q, the re-randomised signing and verification keys are

r⁢s⁢k:=x+α∈𝔽q,r⁢k:=X+[α]⁢P∈𝔾.
Proposition 8.25 (Re-randomisation consistency).

The pair (rsk,rk) is a valid RedDSA key pair: rk=[rsk]P, so a RedDSA signature under rsk verifies under rk.

Proof.

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 rk given α, while only the spender who knows x can sign under the shifted key.

Theorem 8.26 (Perfect unlinkability of re-randomised keys).

Fix a base point P. For any public key X∈𝔾, if α←$𝔽q is uniform then rk=X+[α]P is uniformly distributed over 𝔾. Consequently, in the game where an adversary—of unbounded computational power, and permitted to choose two public keys X0,X1 itself—receives rk=Xb+[α]P for a challenger’s uniform bit b and fresh uniform α, and must guess b: the distributions of rk for b=0 and b=1 are identical, and no adversary guesses b with probability better than 1/2.

Proof.

The point P generates 𝔾, which has prime order q, so α↦[α]P is a bijection 𝔽q→𝔾; for uniform α, the point [α]P is uniform over 𝔾. Translation by the fixed element X is a bijection of 𝔾 and carries the uniform distribution to itself, so rk=X+[α]P is uniform over 𝔾—for every X, hence independently of X. The two conditional distributions of rk coincide exactly, so the adversary’s view is statistically independent of b; no test distinguishes identical distributions, and the best any distinguisher can do is guess, succeeding with probability exactly 1/2. □

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 α←$𝔽q afresh for each spend and reveals it only to the proving circuit and the signer.

Remark 8.27 (Scope of unlinkability).

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 rk with each Action (the unit that spends one note and creates one) while proving, inside the Halo 2 circuit, knowledge of a witness for rk=X+[α]P with X a public key whose holder is authorised to spend the note (Orchard’s spend validating key)—the circuit constrains rk as a public input—and the network verifies the spend authorisation signature against the public rk. Signing under rk requires rsk=x+α, hence knowledge of both x and α.

Remark 8.28 (Unforgeability under re-randomised keys, and the key-prefixing subtlety).

Unforgeability must be re-established under re-randomised keys. A forgery (R,s) under rk satisfies [s]P=R+[c]rk with c=H(R‖rk‖m). Subtracting the contribution of [α]P from the verification equation gives [s−cα]P=R+[c]X, apparently a forgery under the original key X. But the identity holds with c=H(R‖rk‖m), while the base verifier recomputes H(R‖X‖m)—the plain subtraction converts forgeries only for the non-key-prefixed variant of Schnorr. For key-prefixed RedDSA one argues in the ROM by either of two routes. (i) The pair (rsk,rk)=(x+α,X+[α]P) is itself a base-scheme key pair (Proposition 8.25) whose public key is uniform (Theorem 8.26), so a forger against rk is literally a forger against the base scheme at the key rk; the reduction, which knows α, recovers x=rsk−α from the extracted rsk. (ii) When the adversary sees signatures under several randomisers αi, one re-runs the forking argument of Theorem 8.18 on the critical query H(R⋆‖rk‖m⋆), simulating signing under the remaining keys by oracle programming (Lemma 8.16). Both routes avoid a pitfall: a naive translation that programs H(R‖rk‖m):=Hbase(R‖X‖m) must be a carefully injective domain swap, and it fails outright with multiple randomisers—distinct rki-prefixed inputs would collide on a single X-prefixed point, a detectable deviation from a random oracle.

8.9 Binding signatures as a proof of knowledge of a discrete logarithm

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.

The value-commitment setup.

Shielded protocols commit to value with the homomorphic Pedersen commitment

cm⁢(v,ρ)=[v]⁢V+[ρ]⁢P,

where V and P are independent generators of 𝔾—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(viin,ρiin) and output commitments cm(vjout,ρjout), and the net commitment is

B=∑icm⁢(viin,ρiin)−∑jcm⁢(vjout,ρjout).

Orchard has no per-note value commitments: each Action—the unit that simultaneously spends a note of value vold and creates a note of value vnew—commits once to its net value change, publishing

cvnet=cm⁢(vold−vnew,ρ)=[vold−vnew]⁢V+[ρ]⁢P,

and B=∑icvnet,i over the transaction’s Actions (protocol specification § 5.4.8.3). The structure of Actions and their assembly into a transaction are treated in a later volume. In both protocols the homomorphism reduces the sum to

B=[Δv]⁢V+[ρ¯]⁢P,

where Δv is the net value— ∑iviin−∑jvjout in Sapling, ∑i(viold−vinew) in Orchard— and ρ¯ is the net blinding. The transaction balances precisely when Δv equals the public balancing value vbal; for a transaction with internal balance Δv=0, the V-component vanishes and B=[ρ¯]P. Since P generates the prime-order group 𝔾, every element of 𝔾 is some multiple of P, so what distinguishes a balanced transaction is not the existence of a representation B=[β]P but the ability to compute one. When the values balance, the signer knows the multiplier: it is the net blinding ρ¯, assembled from the individual blindings. When they do not, computing any P-multiple representation of B from the published commitments would require knowing logPV, assumed hard.

Definition 8.29 (Binding signature).

With B and ρ¯ as above and the transaction balanced, so that B=[ρ¯]P, set the binding verification key bvk:=B and the binding signing key bsk:=ρ¯. The binding signature is a RedDSA signature over the base point P, with signing key ρ¯ and verification key B, on a message that is the hash of the transaction (the sighash). The verifier recomputes B from the publicly listed value commitments and the public balancing value, then checks [s]P=R+[c]B with c=H(R‖B‖sighash).

Theorem 8.30 (The binding signature is a proof of knowledge of logPB).

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.

Proof.

Part 1: proof of knowledge. The binding signature is exactly a Fiat–Shamir Schnorr proof for the relation Rdl 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 c≠c′, from which the extractor recovers ρ¯=(s−s′)(c−c′)−1 with B=[ρ¯]P. Producing a valid binding signature is therefore equivalent, up to the standard rewinding loss, to knowing logPB.

Part 2: knowledge forces balance. Write B=[Δv]V+[ρ¯′]P for the true net value and net blinding that the commitments imply; these are well defined once the accompanying proofs fix the committed openings—in Orchard the per-Action circuit fixes vold, vnew and the opening of cvnet, in Sapling the per-note proofs fix each vi,ρi. If the signer knows ρ¯ with B=[ρ¯]P, subtracting the two expressions for B gives

[Δv]⁢V=[ρ¯−ρ¯′]⁢P,

where Δv enters as a scalar, that is, as its residue in 𝔽q. Whenever Δv≢0(modq), that residue is a nonzero element of 𝔽q, hence invertible, so

V=[(ρ¯−ρ¯′)⁢Δv−1]⁢P

—exhibiting logPV and contradicting the independence of V and P. Therefore Δv≡0(modq).

Part 3: from congruence to equality. Balance in 𝔽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 vold and vnew to {0,…,264−1} (the Action statement, protocol specification § 4.18.4), and in Sapling the per-note proofs constrain each vi likewise. A transaction with n Actions (count notes instead for Sapling) therefore has |Δv|≤n(264−1) as an integer, far below the 255-bit q for any transaction that can be serialised, and the only multiple of q in that range is 0. Hence Δv=0 over ℤ, not merely in 𝔽q. □

In deployment the transaction is not internally balanced: it declares a public balancing value vbal, and the verifier checks the signature against B−[vbal]V, folding the public value into the verification key (protocol specification § 4.14). The argument of Theorem 8.30 applies verbatim to the folded key and forces Δv≡vbal(modq); the balancing value is encoded as a signed 64-bit integer, so the range checks promote the congruence to the integer equality Δv=vbal exactly as in Part 3.

Remark 8.31 (Functions of the binding signature).

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.

Remark 8.32 (Spend authorisation and binding signatures compared).

The spend authorisation signature verifies under a re-randomised key rk=X+[α]P, chosen to hide which long-term key authorised the spend: the signing key rsk=x+α encodes authority, and α provides unlinkability (Theorem 8.26). The binding signature verifies under a key B=[ρ¯]P that the spender does not choose: the transaction’s own commitments force it, the “secret key” ρ¯ is the net blinding factor, and signing proves balance (Theorem 8.30). Both are the same Schnorr arithmetic and differ only in the meaning of the discrete logarithm: authority in one case, value conservation in the other.

8.10 The transparent layer’s schemes: ECDSA and BIP-340 over secp256k1

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 y2=x3+7 over the prime field 𝔽p with p=2256−232−977, with a fixed base point G of prime order n (a 256-bit prime) and cofactor 1; every constant is a named parameter of SEC 2. In SEC 2’s terminology it is a Koblitz curve, one with a=0, chosen for implementation speed; the choice plays no role in what follows. The group law, point encodings, and the discrete-logarithm problem on such a curve are the general machinery of the Math Guide, §“Elliptic curves” and §“The elliptic-curve discrete logarithm problem”; the hardness assumption is Definition 2.1 in the group ⟨G⟩. The primes p and n have two-adicity 1 and 6—the exponent of the largest power of 2 dividing p−1 and n−1 (Math Guide, §“Roots of unity and evaluation domains”)—against 32 for both Pasta primes (Math Guide, §“Pallas and Vesta assembled”). Power-of-two evaluation domains, on which proof systems run fast polynomial arithmetic, therefore have at most 2 and 64 points over the secp256k1 fields, against 232 over the Pasta fields.

Construction 8.33 (ECDSA over secp256k1, schematically).

Let e∈ℤ/nℤ be the integer read from the 32-byte digest of the message, and write x(R) for the x-coordinate of a point, read as an integer; the secret scalar is written d, since x is already in use.

  • •

    KeyGen: sample d←$[1,n−1], set X=[d]G, output (X,d).

  • •

    Sign(d,e): sample k←$[1,n−1], set R=[k]G and r=x(R)modn, then s=k−1(e+rd)modn; restart if r=0 or s=0; output (r,s).

  • •

    Verify(X,e,(r,s)): require r,s∈[1,n−1], compute R′=[es−1]G+[rs−1]X, and accept iff R′ is not the identity and x(R′)≡r(modn).

Correctness: R′=[s−1(e+rd)]G=[k]G=R. The nonce k must be fresh and secret, for the reason of Proposition 8.20 in different algebra: two signatures (r,s) and (r,s′) under one k on distinct digests e≠e′ give s−s′=k−1(e−e′), hence k=(e−e′)(s−s′)−1 and then d=(sk−e)r−1.

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 R↦x(R)modn—but lie outside this volume: the transparent layer relies for ECDSA’s security on its deployment record in Bitcoin rather than on a reduction.

Remark 8.34 (Deployment conventions: the sighash, DER, and low s).

Three conventions fix how the transparent layer uses Construction 8.33, which protocol specification § 4.1.7 names as the script signature scheme.

  1. 1.

    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.

  2. 2.

    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 (𝖲𝖨𝖦𝖧𝖠𝖲𝖧_𝖠𝖫𝖫 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 𝗁𝖺𝗌𝗁𝟣𝟨𝟢 commits to (§3.9).

  3. 3.

    Low-s normalisation. If (r,s) verifies then so does (r,n−s), so a third party can re-encode a valid signature and change a pre-ZIP-244 transaction id; the normalisation takes the representative s≤(n−1)/2 (BIP-62), which the deployed signer always emits (the secp256k1 crate, whose libsecp256k1 backend documents every created signature as lower-s) and which script evaluation checks only under the LowS flag, one that the consensus check of the zcash_script and zebra-script crates does not set.

Construction 8.35 (BIP-340 Schnorr over secp256k1, schematically).

Write Hτ(m)=SHA256(SHA256(τ)‖SHA256(τ)‖m) for the tagged hash with ASCII tag τ—domain separation in the sense of Definition 3.16, the doubled tag digest making the prefix a whole 64-byte SHA-256 block—and read digests as integers modulo n.

  • •

    Keys. Sample d←$[1,n−1] and set X=[d]G. The public key is the 32-byte coordinate x(X) alone (x-only): the verifier reconstructs X as the point with that abscissa and even y, and the signer replaces d by n−d when y(X) is odd, keeping the pair consistent.

  • •

    Sign(d,m): derive k=H𝙱𝙸𝙿𝟶𝟹𝟺𝟶/𝚗𝚘𝚗𝚌𝚎(t‖x(X)‖m)modn with t=d⊕H𝙱𝙸𝙿𝟶𝟹𝟺𝟶/𝚊𝚞𝚡(a) for auxiliary randomness a; set R=[k]G, negating k when y(R) is odd; compute e=H𝙱𝙸𝙿𝟶𝟹𝟺𝟶/𝚌𝚑𝚊𝚕𝚕𝚎𝚗𝚐𝚎(x(R)‖x(X)‖m)modn and s=k+edmodn; output the 64 bytes (x(R),s).

  • •

    Verify(x(X),m,(r,s)): lift x(X) to the even-y point X, recompute e, set R′=[s]G−[e]X, and accept iff R′ is not the identity, y(R′) is even, and x(R′)=r.

Remark 8.36 (BIP-340 against Construction 8.12; the ZSA consumer). #

The algebra is the Schnorr signature of Construction 8.12 in its (R,s) form with key-prefixing (Remark 8.14), under 𝔾=⟨G⟩ of order n and H=H𝙱𝙸𝙿𝟶𝟹𝟺𝟶/𝚌𝚑𝚊𝚕𝚕𝚎𝚗𝚐𝚎; the unforgeability proof of §8.6 carries over with that tagged hash modelled as the random oracle. What differs is convention: points travel by abscissa alone with parity fixed by the even-y rule, saving a byte per key and the parity of R per signature and letting the same 32 bytes serve as key encoding and as hash input; the challenge hash is domain-separated by tag; and the nonce is deterministic with optional auxiliary randomness, as in Construction 8.21. In the series, BIP-340 is the issuance authorisation signature of Zcash Shielded Assets: ZIP 227 (specified, in a draft ZIP) instantiates 𝖨𝗌𝗌𝗎𝖾𝖠𝗎𝗍𝗁𝖲𝗂𝗀 as BIP-340 over secp256k1, prefixes both the validating-key encoding and the signature with a scheme byte 𝟶𝚡𝟶𝟶, and signs the transaction’s sighash. The reference implementation, not yet deployed, is the QED-it fork of the orchard crate (commit cf801a5), which signs through the BIP-340 routine of the secp256k1 crate with zeroed auxiliary randomness. The issuance protocol itself is treated in a later volume.