Skip to content

Latest commit

 

History

History
346 lines (274 loc) · 18.8 KB

zip-0212.rst

File metadata and controls

346 lines (274 loc) · 18.8 KB
Raw
ZIP: 212
Title: Allow Recipient to Derive Ephemeral Secret from Note Plaintext
Owners: Sean Bowe <sean@electriccoin.co>
Status: Implemented (zcashd)
Category: Consensus
Created: 2019-03-31
License: MIT

Terminology

The key words "MUST", "MUST NOT", "SHOULD NOT", and "MAY" in this document are to be interpreted as described in RFC 2119.1

The following functions are defined in the Zcash Protocol Specification2 according to the type (Sapling or Orchard) of note plaintext being processed:

  • let ToScalar be ToScalarSapling defined in section 4.2.23 or ToScalarOrchard defined in section 4.2.34;
  • let DiversifyHash be DiversifyHashSapling or DiversifyHashOrchard defined in section 5.4.1.65;
  • let KA be KASapling defined in section 5.4.5.36 or KAOrchard defined in section 5.4.5.57;
  • let NoteCommit be NoteCommitSapling or NoteCommitOrchard defined in section 4.1.88.

Abstract

This ZIP proposes a new note plaintext format for Sapling Outputs (later extended to include Orchard Actions) in transactions. The new format allows recipients to verify that the sender of an Output or Action knows the private key corresponding to the ephemeral Diffie-Hellman key, in order to avoid an assumption on zk-SNARK soundness for preventing diversified address linkability.

Motivation

The Sapling and Orchard payment protocols have a feature called "diversified addresses" which allows a single incoming viewing key to receive payments on an enormous number of distinct and unlinkable payment addresses. This feature allows users to maintain many payment addresses without paying additional overhead during blockchain scanning.

The feature works by allowing payment addresses to become a tuple (pkd, d) of a public key pkd and 88-bit diversifier d such that pkd = [ivk] DiversifyHash(d) for some incoming viewing key ivk. The hash function DiversifyHash(d) maps from a diversifier to prime-order elements of the Jubjub or Pallas elliptic curve. It is possible for a user to choose many d to create several distinct and unlinkable payment addresses of this form.

In order to make a payment to a Sapling or Orchard address, an ephemeral secret esk is sampled by the sender and an ephemeral public key epk = [esk] DiversifyHash(d) is included in the Output or Action description. Then, a shared Diffie-Hellman secret is computed by the sender as KA.Agree(esk, pkd). The recipient can recover this shared secret without knowledge of the particular d by computing KA.Agree(ivk, epk). This shared secret is then used as part of note decryption.

Naïvely, the recipient cannot know which (pkd, d) was used to compute the shared secret, but the sender is asked to include the d within the note plaintext to reconstruct the note. However, if the recipient has more than one known address, an attacker could use a different payment address to perform secret exchange and, by observing the behavior of the recipient, link the two diversified addresses together. (This attacker strategy was discovered by Brian Warner earlier in the design of the Sapling protocol.)

In order to prevent this attack, before activation of this ZIP the protocol forced the sender to prove knowledge of the discrete logarithm of epk with respect to the gd = DiversifyHash(d) included within the note commitment. This gd is determined by d and recomputed during note decryption, and so either the note decryption will fail, or the sender will be unable to produce the proof that requires knowledge of the discrete logarithm.

However, the latter proof was part of the Sapling Output statement, and so relied on the soundness of the underlying Groth16 zk-SNARK — hence on relatively strong cryptographic assumptions and a trusted setup. It is preferable to force the sender to transfer sufficient information in the note plaintext to allow deriving esk, so that, during note decryption, the recipient can check that epk = [esk] gd for the expected gd, and ignore the payment as invalid otherwise. For Sapling, this forms a line of defense in the case that soundness of the zk-SNARK does not hold. For Orchard, this check is essential because (for efficiency and simplicity) epk = [esk] gd is not checked in the Action statement.

Merely sending esk to the recipient in the note plaintext would require us to enlarge the note plaintext, but also would compromise the proof of IND-CCA2 security for in-band secret distribution. We avoid both of these concerns by using a key derivation to obtain both esk and rcm.

Specification

The specification in this ZIP is intended to be aligned with version 2021.2.6 or later of the Zcash Protocol Specification9.

Pseudo random functions (PRFs) are defined in section 4.2.1 of the Zcash Protocol Specification10. We will be adapting PRFexpand for the purposes of this ZIP. This function is keyed by a 256-bit key sk and takes an arbitrary length byte sequence as input, returning a 64-byte sequence as output.

Changes to Sapling and Orchard Note plaintexts

Note plaintext encodings are specified in section 5.5 of the Zcash Protocol Specification11. Before activation of this ZIP, the encoding of a Sapling note plaintext required that the first byte take the form 0x01, indicating the version of the note plaintext. In addition, a 256-bit rcm field exists within the note plaintext and encoding.

Following the activation of this ZIP, senders of Sapling or Orchard notes MUST use the following note plaintext format:

  • The first byte of the encoding MUST take the form 0x02 (representing the new note plaintext version).
  • The field rcm of the encoding is renamed to rseed. This field rseed of the Sapling or Orchard note plaintext no longer takes the type of NoteCommit.Trapdoor (as it did for Sapling) but instead is a 32-byte sequence.

The requirement that the former rcm field be a scalar of the Jubjub elliptic curve, when interpreted as a little endian integer, is removed from descriptions of note plaintexts in the Zcash Protocol Specification.

Changes to the process of sending Sapling or Orchard notes

The process of sending notes is described in section 4.7.2 of the Zcash Protocol Specification for Sapling12 and section 4.7.3 for Orchard13. In addition, the process of encrypting a note is described (currently) in section 4.19.1 of the Zcash Protocol Specification14. Prior to activation of this ZIP, the sender sampled rcmnew and the ephemeral private key esk uniformly at random during this process.

After the activation of this ZIP, the sender MUST instead sample a uniformly random 32-byte sequence rseed. The note plaintext takes rseed in place of rcmnew.

For Sapling:

  • rcmnew MUST be computed by the sender as the output of ToScalar(PRFrseedexpand([4])).
  • esk MUST be computed by the sender as the output of ToScalar(PRFrseedexpand([5])).

For Orchard, an encoding of ρ is appended to these PRF inputs, as specified in section 4.7.3 of the Zcash Protocol Specification15.

Changes to the process of receiving Sapling or Orchard notes

The process of receiving notes in Sapling is described in sections 4.19.2 and 4.19.3 of the Zcash Protocol Specification.16 17

There is a "grace period" of 32256 blocks starting from the block at which this ZIP activates, during which note plaintexts with lead byte 0x01 MUST still be accepted.

Let ActivationHeight be the activation height of this ZIP, and let GracePeriodEndHeight be ActivationHeight + 32256.

The height of a transaction in a mined block is defined as the height of that block. An implementation MAY also decrypt mempool transactions, in which case the height used is the height of the next block at the time of the check. An implementation SHOULD NOT attempt to decrypt mempool transactions without having obtained a best-effort view of the current block chain height.

When the recipient of a note (either using an incoming viewing key or a full viewing key) is able to decrypt a note plaintext, it performs the following check on the plaintext lead byte, based on the height of the containing transaction:

  • If the height is less than ActivationHeight, then only 0x01 is accepted as the plaintext lead byte.
  • If the height is at least ActivationHeight and less than GracePeriodEndHeight, then either 0x01 or 0x02 is accepted as the plaintext lead byte.
  • If the height is at least GracePeriodEndHeight, then only 0x02 is accepted as the plaintext lead byte.

If the plaintext lead byte is not accepted then the note MUST be discarded. However, if an implementation decrypted the note from a mempool transaction and it was accepted at that time, but it is later mined in a block after the end of the grace period, then it MAY be retained.

A note plaintext with lead byte 0x02 contains a field rseed that is a 32-byte sequence rather than a scalar value rcm. The recipient, during decryption and in any later contexts, will interpret the value rcm as the output of ToScalar(PRFrseedexpand([4])) in the case of Sapling. Further, the recipient MUST compute esk as ToScalar(PRFrseedexpand([5])) in the case of Sapling, and check that epk = [esk] gd, failing decryption if this check is not satisfied. For Orchard, an encoding of ρ is appended to the PRF inputs, as for encryption.

Consensus rule change for coinbase transactions

After the activation of this ZIP, any Sapling output of a coinbase transaction that is decrypted to a note plaintext as specified in18, MUST have note plaintext lead byte equal to 0x02.

This applies even during the “grace period”, and also applies to funding stream outputs19 sent to shielded payment addresses, if there are any.

Since NU5 activates after the end of the grace period20, Orchard outputs will always require a note plaintext lead byte equal to 0x02.

Rationale

The attack that this prevents is an interactive attack that requires an adversary to be able to break critical soundness properties of the zk-SNARKs underlying Sapling. It is potentially valid to assume that this cannot occur, due to other damaging effects on the system such as undetectable counterfeiting. However, we have attempted to avoid any instance in the protocol where privacy (even against interactive attacks) depended on strong cryptographic assumptions. Acting differently here would be confusing for users that have previously been told that "privacy does not depend on zk-SNARK soundness" or similar claims.

It is possible for us to infringe on the length of the memo field and ask the sender to provide esk within the existing note plaintext without modifying the transaction format, but this would harm users who have come to expect a 512-byte memo field to be available to them. Changes to the memo field length should be considered in a broader context than changes made for cryptographic purposes.

It is possible to transmit a signature of knowledge of a correct esk rather than esk itself, but this appears to be an unnecessary complication and is likely slower than just supplying esk.

The grace period is intended to mitigate loss-of-funds risk due to non-conformant sending wallet implementations. The intention is that during the grace period (of about 4 weeks), it will be possible to identify wallets that are still sending plaintexts according to the old specification, and cajole their developers to make the required updates. For the avoidance of doubt, such wallets are non-conformant because it is a "MUST" requirement to immediately switch to sending note plaintexts with lead byte 0x02 (and the other changes in this specification) at the upgrade. Note that nodes will clear their mempools when the upgrade activates, which will clear all plaintexts with lead byte 0x01 that were sent conformantly and not mined before the upgrade.

Historical note: in practice some note plaintexts with lead byte 0x01 were non-conformantly sent even after the end of the specified grace period. ZecWallet extended its implementation of the grace period by a further 161280 blocks (approximately 20 weeks) in order to allow for recovery of these funds21.

Security and Privacy Considerations

The changes made in this proposal prevent an interactive attack that could link together diversified addresses by only breaking the knowledge soundness assumption of the zk-SNARK. It is already assumed that the adversary cannot defeat the EC-DDH assumption of the Jubjub (or Pallas) elliptic curve, for it could perform a linkability attack trivially in that case.

In the naïve case where the protocol is modified so that esk is supplied directly to the recipient (rather than derived through rseed) this would lead to an instance of key-dependent encryption, which is difficult or perhaps impossible to prove secure using existing security notions. Our approach of using a key derivation, which ultimately queries an oracle, allows a proof for IND-CCA2 security to be written by reprogramming the oracle to return bogus keys when necessary.

Deployment

This proposal will be deployed with the Canopy network upgrade.22

Reference Implementation

In zcashd:

In librustzcash:

Acknowledgements

The discovery that diversified address unlinkability depended on the zk-SNARK knowledge assumption was made by Sean Bowe and Zooko Wilcox.

References

  1. RFC 2119: Key words for use in RFCs to Indicate Requirement Levels↩

  2. Zcash Protocol Specification, Version 2021.2.6 or later↩

  3. Zcash Protocol Specification, Version 2021.2.6. Section 4.2.2: Sapling Key Components↩

  4. Zcash Protocol Specification, Version 2021.2.6. Section 4.2.3: Orchard Key Components↩

  5. Zcash Protocol Specification, Version 2021.2.6. Section 5.4.1.6: DiversifyHash^Sapling and DiversifyHash^Orchard Hash Functions↩

  6. Zcash Protocol Specification, Version 2021.2.6. Section 5.4.5.3 Sapling Key Agreement↩

  7. Zcash Protocol Specification, Version 2021.2.6. Section 5.4.5.5 Orchard Key Agreement↩

  8. Zcash Protocol Specification, Version 2021.2.6. Section 4.1.8: Commitment↩

  9. Zcash Protocol Specification, Version 2021.2.6 or later↩

  10. Zcash Protocol Specification, Version 2021.2.6. Section 4.1.2: Pseudo Random Functions↩

  11. Zcash Protocol Specification, Version 2021.2.6. Section 5.5: Encodings of Note Plaintexts and Memo Fields↩

  12. Zcash Protocol Specification, Version 2021.2.6. Section 4.7.2: Sending Notes (Sapling)↩

  13. Zcash Protocol Specification, Version 2021.2.6. Section 4.7.3: Sending Notes (Orchard)↩

  14. Zcash Protocol Specification, Version 2021.2.6. Section 4.19.1: Encryption (Sapling and Orchard)↩

  15. Zcash Protocol Specification, Version 2021.2.6. Section 4.7.3: Sending Notes (Orchard)↩

  16. Zcash Protocol Specification, Version 2021.2.6. Section 4.19.2: Decryption using an Incoming Viewing Key (Sapling and Orchard)↩

  17. Zcash Protocol Specification, Version 2021.2.6. Section 4.19.3: Decryption using a Full Viewing Key (Sapling and Orchard)↩

  18. ZIP 213: Shielded Coinbase↩

  19. ZIP 207: Split Founders' Reward↩

  20. ZIP 252: Deployment of the NU5 Network Upgrade↩

  21. Commit c31a04a in aditypk00/librustzcash: Move ZIP-212 grace period to end of April↩

  22. ZIP 251: Deployment of the Canopy Network Upgrade↩