Skip to content

Latest commit

 

History

History
292 lines (203 loc) · 14.2 KB

zip-0304.rst

File metadata and controls

292 lines (203 loc) · 14.2 KB
Raw
ZIP: 304
Title: Sapling Address Signatures
Owners: Jack Grigg <jack@electriccoin.co>
Credits: Daira Hopwood <daira@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 RFC 2119. [1]

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]

  • \mathsf{MerkleDepth}^\mathsf{Sapling} and \mathsf{Uncommitted}^\mathsf{Sapling} [6]
  • \mathsf{MerkleCRH}^\mathsf{Sapling} [7]
  • \mathsf{DiversifyHash}(\mathsf{d}) [8]
  • \mathsf{MixingPedersenHash}(\mathsf{cm}, position) [9]
  • \mathsf{PRF}^\mathsf{nfSapling}_\mathsf{nk}(\rho ) [10]
  • \mathsf{SpendAuthSig.RandomizePrivate}(\alpha , \mathsf{sk}), \mathsf{SpendAuthSig.RandomizePublic}(\alpha , \mathsf{vk}), \mathsf{SpendAuthSig.Sign}(\mathsf{sk}, m), and \mathsf{SpendAuthSig.Verify}(\mathsf{vk}, m, \sigma ) [11]
  • \mathsf{NoteCommit}^\mathsf{Sapling}_\mathsf{rcm}(\mathsf{g_d}, \mathsf{pk_d}, value) [12]
  • \mathsf{ValueCommit}_\mathsf{rcv}(value) [13]

We also reproduce some notation and functions here for convenience:

  • a\,||\,b means the concatenation of sequences a then b.
  • \mathsf{repr}_\mathbb{J}(P) is the representation of the Jubjub elliptic curve point P as a bit sequence, defined in [14].
  • \mathsf{BLAKE2b}\text{-}\mathsf{256}(p, x) refers to unkeyed BLAKE2b-256 in sequential mode, with an output digest length of 32 bytes, 16-byte personalization string p, and input x.

Requirements

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

  • Authentication: the signature will not verify with any other payment address.
  • Binding: the signature will not verify with any modification, extension, or truncation of the message.
  • Non-malleability: it should not be possible to obtain a second valid signature (with a different encoding) for the same payment address and message without access to the spending key for that payment address.

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:

  • A fake Sapling note with a value of 1 zatoshi and \mathsf{rcm} = 0.
  • A Sapling commitment tree that is empty except for the commitment for the fake note.

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 \alpha .
  • Let \mathsf{rk} = \mathsf{SpendAuthSig.RandomizePublic}(\alpha , \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, \alpha , \mathsf{ak}, \mathsf{nsk}). [5]
  • Let \mathsf{rsk} = \mathsf{SpendAuthSig.RandomizePrivate}(\alpha , \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 \alpha is never re-used across signatures.

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

  • \mathsf{nf} is a binary public input to zkproof.
  • \mathsf{rk} is internally bound to spendAuthSig by the design of RedJubjub.
  • RedJubjub signatures are themselves 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

zcash/librustzcash#210

References

[1]RFC 2119: Key words for use in RFCs to Indicate Requirement Levels
[2]RFC 4648: The Base16, Base32, and Base64 Data Encodings
[3]Zcash Protocol Specification, Version 2020.1.15 or later
[4](1, 2) Zcash Protocol Specification, Version 2020.1.15. Section 4.8: Merkle path validity
[5](1, 2) 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](1, 2) SLIP-0044 : Registered coin types for BIP-0044