Randomizable Signatures

Penumbra’s signatures are provided by decaf377-rdsa, a variant of the Zcash RedDSA construction instantiated using the decaf377 group. These are Schnorr signatures, with two additional properties relevant to Penumbra:

They support randomization of signing and verification keys. Spending a note requires use of the signing key that controls its spend authorization, but if the same spend verification key were included in multiple transactions, they would be linkable. Instead, both the signing and verification keys are kept secret¹, and each spend description includes a randomization of the verification key, together with a proof that the randomized verification key was derived from the correct spend verification key.
They support addition and subtraction of signing and verification keys. This property is used for binding signatures, which bind zero-knowledge proofs to the transaction they were intended for and enforce conservation of value.

`decaf377-rdsa`

Let $G$ be the decaf377 group of prime order $r$ . Keys and signatures are parameterized by a domain $D$ . Each domain has an associated generator $B_{D}$ . Currently, there are two defined domains: $D = SpendAuth$ and $D = Binding$ . The hash function $H^{⋆} : {0, 1}^{*} \to F_{r}$ is instantiated by using blake2b with the personalization string decaf377-rdsa---, treating the 64-byte output as the little-endian encoding of an integer, and reducing that integer modulo $r$ .

A signing key is a scalar $a \in F_{r}$ . The corresponding verification key is the group element $A = [a] B_{D}$ .

`Sign`

On input message m with signing key $a$ , verification key $A$ , and domain $D$ :

Generate 80 random bytes.
Compute the nonce as $r \leftarrow H^{⋆} (random_bytes ∣∣ A_bytes ∣∣ m)$ .
Commit to the nonce as $R \leftarrow [r] B_{D}$ .
Compute the challenge as $c \leftarrow H^{⋆} (R_bytes ∣∣ A_bytes ∣∣ m)$ .
Compute the response as $s \leftarrow r + a c$ .
Output the signature R_bytes || s_bytes.

`Verify`

On input message m, verification key A_bytes, and signature sig_bytes:

Parse $A$ from A_bytes, or fail if A_bytes is not a valid (hence canonical) decaf377 encoding.
Parse sig_bytes as R_bytes || s_bytes and the components as $R$ and $s$ , or fail if they are not valid (hence canonical) encodings.
Recompute the challenge as $c \leftarrow H^{⋆} (R_bytes ∣∣ A_bytes ∣∣ m)$ .
Check the verification equation $R = [s] B - [c] A$ , rejecting the signature if it is not satisfied.

`SpendAuth` signatures

The first signature domain used in Penumbra is for spend authorization signatures. The basepoint $B_{SpendAuth}$ is the conventional decaf377 basepoint 0x0800000....

Spend authorization signatures support randomization:

`Randomize.SigningKey`

Given a randomizer $r $ F_{r}$ , the randomized signing key is $r a$ .

`Randomize.VerificationKey`

Given a randomizer $r $ F_{r}$ , the randomized verification key is $[r] A$ .

Randomizing a signing key and then deriving the verification key associated to the randomized signing key gives the same result as randomizing the original verification key (with the same randomizer).

`Binding` signatures

The second signature domain used in Penumbra is for binding signatures. The basepoint $B_{Binding}$ is the result of converting blake2b(b"decaf377-rdsa-binding") to an $F_{r}$ element and applying decaf377’s CDH encode-to-curve method.

Since the verification key corresponding to the signing key $a \in F_{r}$ is $A = [a] B_{D}$ , adding and subtracting signing and verification keys commutes with derivation of the verification key, as desired.

This situation is a good example of why it’s better to avoid the terms “public key” and “private key”, and prefer more precise terminology that names keys according to the cryptographic capability they represent, rather than an attribute of how they’re commonly used. In this example, the verification key should not be public, since it could link different transactions.

Simple example: Binding signature

Let’s say we have two actions in a transaction: one spend (indicated with subscript $s$ ) and one output (indicated with subscript $o$ ).

The balance commitments for those actions are:

$c v_{o} = [v_{o}] G_{v} + [rc v_{o}] G_{rc v}$

$c v_{s} = [v_{s}] G_{v} + [rc v_{s}] G_{rc v}$

where $G_{v}$ and $G_{rc v}$ are generators, $rc v_{i}$ are the blinding factors, and $v_{i}$ are the values.

When the signer is computing the binding signature, they have the blinding factors for all commitments.

They derive the signing key $b s k$ by adding up the blinding factors based on that action’s contribution to the balance:

$b s k = rc v_{s} - rc v_{o}$

The signer compute the binding signature using this key $b s k$ .

When the verifier is checking the signature, they add up the balance commitments to derive the verification key $b v k$ based on their contribution to the balance:

$b v k = c v_{s} - c v_{o} = [v_{s} - v_{o}] G_{v} + [rc v_{s} - rc v_{o}] G_{rc v}$

If the transaction is valid, then the first term on the LHS ( $[v_{s} - v_{o}] G_{v}$ ) is zero since for Penumbra all transactions should have zero value balance.

This leaves the verifier with the verification key:

$b v k = [rc v_{s} - rc v_{o}] G_{rc v}$

If the value balance is not zero, the verifier will not be able to compute the verification key with the data in the transaction.

The Penumbra Protocol