ZIP: 304
Title: Sapling Address Signatures
Owners: Jack Grigg <jack@electriccoin.co>
Credits: Daira-Emma Hopwood <daira-emma@electriccoin.co>
         Sean Bowe <sean@electriccoin.co>
Status: Draft
Category: Standards / RPC / Wallet
Created: 2020-06-01
License: MIT
Discussions-To: <https://github.com/zcash/zips/issues/345>
Pull-Request: <https://github.com/zcash/zips/pull/376>

Terminology

The key words "MUST" and "SHOULD" in this document is to be interpreted as described in BCP 14 1 when, and only when, they appear in all capitals.

Abstract

This proposal describes a mechanism for creating signatures with Sapling addresses, suitable for use by the signmessage and verifymessage RPC methods in zcashd.

Motivation

There are a variety of situations where it is useful for a user to be able to prove that they control a given payment address. For example, before a high-value transfer of funds, the sender may want to verify that the recipient will definitely be able to spend them, to ensure that the funds won't be stuck in an invalid or unusable address.

A payment address is analogous (in some cases, identical) to a public key in a signature scheme. A transaction that spends funds received by the address, is authorized by making (the equivalent of) a signature with the corresponding spending key. This authorization protocol can be repurposed to instead sign a message provided by a third party.

Bitcoin Core's bitcoind provides a signmessage RPC method that implements message signing for Bitcoin addresses, leveraging the fact that a Bitcoin private key is just a secp256k private key, and a Bitcoin transaction authorizes spends with a signature. zcashd inherited this RPC method, and it can be used to make signatures for transparent Zcash addresses.

However, support for signing messages with shielded addresses was not possible when Zcash launched, because of the design of the Sprout protocol (and the state of zero-knowledge proof R&D at the time). Shielded transactions, by design, do not expose the payment address of the sender when creating a transaction; in Sprout, this meant that the spending key was a private input to the zero-knowledge proof, and not a key that could be used to create a signature.

One of the R&D achievements behind the Sapling protocol was the ability to use elliptic curves inside a circuit. With this primitive available, Sapling keys and payment addresses could be designed such that transaction authorization involved a signature. While this was designed to enable hardware wallets (which lack the power to create zero-knowledge proofs, but can easily create signatures), it also enables the creation of a mechanism for signing arbitrary messages. That mechanism is the subject of this ZIP.

Conventions

The following constants and functions used in this ZIP are defined in the Zcash protocol specification: 3

We also reproduce some notation and functions here for convenience:

Requirements

Given a payment address, a message, and a valid signature, the following properties should hold:

Non-requirements

Multiple signatures by a single payment addresses are not required to be unlinkable.

Specification

A Sapling address signature is created by taking the process for creating a Sapling Spend description, and running it with fixed inputs:

Signature algorithm

The inputs to the signature algorithm are:

  • The payment address \((\mathsf{d}, \mathsf{pk_d})\!\) ,
  • Its corresponding expanded spending key \((\mathsf{ask}, \mathsf{nsk}, \mathsf{ovk})\!\) ,
  • The SLIP-44 15 coin type, and
  • The message \(msg\) to be signed.

The signature is created as follows:

  • Derive the full viewing key \((\mathsf{ak}, \mathsf{nk}, \mathsf{ovk})\) from the expanded spending key.
  • Let \(\mathsf{g_d} = \mathsf{DiversifyHash}(\mathsf{d})\!\) .
  • Let \(\mathsf{cm} = \mathsf{NoteCommit}^\mathsf{Sapling}_0(\mathsf{repr}_\mathbb{J}(\mathsf{g_d}), \mathsf{repr}_\mathbb{J}(\mathsf{pk_d}), 1)\!\) .
  • Let \(\mathsf{rt}\) be the root of a Merkle tree with depth \(\mathsf{MerkleDepth}^\mathsf{Sapling}\) and hashing function \(\mathsf{MerkleCRH}^\mathsf{Sapling}\!\) , containing \(\mathsf{cm}\) at position 0, and \(\mathsf{Uncommitted}^\mathsf{Sapling}\) at all other positions.
  • Let \(path\) be the Merkle path from position 0 to \(\mathsf{rt}\!\) . 4
  • Let \(\mathsf{cv} = \mathsf{ValueCommit}_0(1)\!\) .
    • This is a constant and may be pre-computed.
  • Let \(\mathsf{nf} = \mathsf{PRF}^\mathsf{nfSapling}_{\mathsf{repr}_\mathbb{J}(\mathsf{nk})}(\mathsf{repr}_\mathbb{J}(\mathsf{MixingPedersenHash}(\mathsf{cm}, 0)))\!\) .
  • Select a random \(α\!\) .
  • Let \(\mathsf{rk} = \mathsf{SpendAuthSig.RandomizePublic}(α, \mathsf{ak})\!\) .
  • Let \(zkproof\) be the byte sequence representation of a Sapling spend proof with primary input \((\mathsf{rt}, \mathsf{cv}, \mathsf{nf}, \mathsf{rk})\) and auxiliary input \((path, 0, \mathsf{g_d}, \mathsf{pk_d}, 1, 0, \mathsf{cm}, 0, α, \mathsf{ak}, \mathsf{nsk})\!\) . 5
  • Let \(\mathsf{rsk} = \mathsf{SpendAuthSig.RandomizePrivate}(α, \mathsf{ask})\!\) .
  • Let \(coinType\) be the 4-byte little-endian encoding of the coin type in its index form, not its hardened form (i.e. 133 for mainnet Zcash).
  • Let \(digest = \mathsf{BLAKE2b}\text{-}\mathsf{256}(\texttt{“ZIP304Signed”}\,||\,coinType, zkproof\,||\,msg)\!\) .
  • Let \(spendAuthSig = \mathsf{SpendAuthSig.Sign}(\mathsf{rsk}, digest)\!\) .
  • Return \((\mathsf{nf}, \mathsf{rk}, zkproof, spendAuthSig)\!\) .

Verification algorithm

The inputs to the verification algorithm are:

  • The payment address \((\mathsf{d}, \mathsf{pk_d})\!\) ,
  • The SLIP-44 15 coin type,
  • The message \(msg\) that is claimed to be signed, and
  • The ZIP 304 signature \((\mathsf{nf}, \mathsf{rk}, zkproof, spendAuthSig)\!\) .

The signature MUST be verified as follows:

  • Let \(coinType\) be the 4-byte little-endian encoding of the coin type in its index form, not its hardened form (i.e. 133 for mainnet Zcash).
  • Let \(digest = \mathsf{BLAKE2b}\text{-}\mathsf{256}(\texttt{“ZIP304Signed”}\,||\,coinType, zkproof\,||\,msg)\!\) .
  • If \(\mathsf{SpendAuthSig.Verify}(\mathsf{rk}, digest, spendAuthSig) = 0\!\) , return false.
  • Let \(\mathsf{cm} = \mathsf{NoteCommit}^\mathsf{Sapling}_0(\mathsf{repr}_\mathbb{J}(\mathsf{DiversifyHash}(\mathsf{d})), \mathsf{repr}_\mathbb{J}(\mathsf{pk_d}), 1)\!\) .
  • Let \(\mathsf{rt}\) be the root of a Merkle tree with depth \(\mathsf{MerkleDepth}^\mathsf{Sapling}\) and hashing function \(\mathsf{MerkleCRH}^\mathsf{Sapling}\!\) , containing \(\mathsf{cm}\) at position 0, and \(\mathsf{Uncommitted}^\mathsf{Sapling}\) at all other positions.
  • Let \(path\) be the Merkle path from position 0 to \(\mathsf{rt}\!\) . 4
  • Let \(\mathsf{cv} = \mathsf{ValueCommit}_0(1)\!\) .
    • This is a constant and may be pre-computed.
  • Decode and verify \(zkproof\) as a Sapling spend proof with primary input \((\mathsf{rt}, \mathsf{cv}, \mathsf{nf}, \mathsf{rk})\!\) . 5 If verification fails, return false.
  • Return true.

Signature encoding

The raw form of a ZIP 304 signature is \(\mathsf{nf}\,||\,\mathsf{LEBS2OSP}_{256}(\mathsf{repr}_{\mathbb{J}}(\mathsf{rk}))\,||\,zkproof\,||\,spendAuthSig\!\) , for a total size of 320 bytes.

When encoding a ZIP 304 signature in a human-readable format, implementations SHOULD use standard Base64 for compatibility with the signmessage and verifymessage RPC methods in zcashd. ZIP 304 signatures in this form are 428 bytes. The encoded form is the string \(\texttt{“zip304:”}\) followed by the result of Base64-encoding 2 the raw form of the signature.

Rationale

We use a fake note within the signature scheme in order to reuse the Sapling Spend circuit and its parameters. It is possible to construct a signature scheme with a smaller encoded signature, but this would require a new circuit and another parameter-generation ceremony (if Groth16 were used).

We use a note value of \(1\) zatoshi instead of zero to ensure that the payment address is fully bound to \(zkproof\!\) . Notes with zero value have certain constraints disabled inside the circuit.

We set \(\mathsf{rcm}\) and \(\mathsf{rcv}\) to zero because we do not need the hiding properties of the note commitment or value commitment schemes (as we are using a fixed-value fake note), and can thus omit both \(\mathsf{rcm}\) and \(\mathsf{rcv}\) from the signature.

Security and Privacy Considerations

A normal (and desired) property of signature schemes is that all signatures for a specific public key are linkable if the public key is known. ZIP 304 signatures have the additional property that all signatures for a specific payment address are linkable without knowing the payment address, as the first 32 bytes of each signature will be identical.

A signature is bound to a specific diversified address of the spending key. Signatures for different diversified addresses of the same spending key are unlinkable, as long as \(α\) is never re-used across signatures.

Most of the data within a ZIP 304 signature is inherently non-malleable:

The one component that is inherently malleable is \(zkproof\!\) . The zero-knowledge property of a Groth16 proof implies that anyone can take a valid proof, and re-randomize it to obtain another valid proof with a different encoding. We prevent this by binding the encoding of \(zkproof\) to \(spendAuthSig\!\) , by including \(zkproof\) in the message digest.

Reference implementation

https://github.com/zcash/librustzcash/pull/210

References

1 Information on BCP 14 — "RFC 2119: Key words for use in RFCs to Indicate Requirement Levels" and "RFC 8174: Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words"
2 RFC 4648: The Base16, Base32, and Base64 Data Encodings
3 Zcash Protocol Specification, Version 2020.1.15 or later
4 Zcash Protocol Specification, Version 2020.1.15. Section 4.8: Merkle path validity
5 Zcash Protocol Specification, Version 2020.1.15. Section 4.15.2: Spend Statement (Sapling)
6 Zcash Protocol Specification, Version 2020.1.15. Section 5.3: Constants
7 Zcash Protocol Specification, Version 2020.1.15. Section 5.4.1.3: Merkle Tree Hash Function
8 Zcash Protocol Specification, Version 2020.1.15. Section 5.4.1.6: DiversifyHash Hash Function
9 Zcash Protocol Specification, Version 2020.1.15. Section 5.4.1.8: Mixing Pedersen Hash Function
10 Zcash Protocol Specification, Version 2020.1.15. Section 5.4.2: Pseudo Random Functions
11 Zcash Protocol Specification, Version 2020.1.15. Section 5.4.6.1: Spend Authorization Signature
12 Zcash Protocol Specification, Version 2020.1.15. Section 5.4.7.2: Windowed Pedersen commitments
13 Zcash Protocol Specification, Version 2020.1.15. Section 5.4.7.3: Homomorphic Pedersen commitments
14 Zcash Protocol Specification, Version 2020.1.15. Section 5.4.8.3: Jubjub
15 SLIP-0044 : Registered coin types for BIP-0044