[Sapling] Disunify Mint and Pour

[daira]

One of the protocol differences between Zerocash and Zcash is that the former has separate Mint and Pour operations, while the latter unifies these into JoinSplit operations. A JoinSplit is like a Zerocash Pour, except that it takes a transparent input and therefore subsumes the functionality of a Zerocash Mint. However, it has the performance characteristics of a Pour even in the case where there are only transparent inputs.

This was a performance vs simplicity+privacy trade-off that we took in favour of simplicity+privacy. I think it was a perfectly reasonable decision at the time; it did simplify the code, the protocol design, and the user-visible concepts significantly. In particular it simplified the solution to the Faerie Gold attack (see sections 7.3 and 7.4 of the protocol specification). It also improves privacy slightly by reducing the distinguishability of some operations. (This is quite subtle because JoinSplits that take a transparent input are still distinguishable; the improvement is that those JoinSplits can be operating on shielded notes at the same time.)

However, given the expense of generating zk-SNARK proofs (currently ~42 seconds and ~3.1GB on our benchmark server), we should consider whether to disunify these operations in order to allow faster creation of shielded notes from transparent inputs. While there is plenty of scope for reducing proving time and/or memory (#647, #2064, #750, #1966, #2005, #43, #40, #2171, #2173, #2230, #2233, #2234, #2235), those options can't compete on performance with eliminating the proof entirely for some cases.

An obvious difficulty is how to support compatibility with existing notes. When we fixed the InternalH bug (see section 7.5 of the protocol spec), we changed the note commitment from the two-level structure used in Zerocash, to a one-level structure (#704, #738). The purpose of the two-level structure was to allow Mint operations to reveal the opening of the outer commitment (v, k, s), which is necessary to prove that the Mint is creating a coin of the right value v. It is highly desirable, when changing the circuit, to maintain a single note anonymity set, so that new transactions can spend old notes without loss of privacy. On the other hand, we may want to change the commitment in any case in order to allow for User-Issued Tokens (#830) or other extensions (#344, #608, #716, #718, #782, #794, #829). Also see #790 about note commitment extensibility.

I believe it should be relatively straightforward to support a new commitment structure in parallel with the old one. Minted notes would always use the new structure, as would output notes from JoinSplits. The input side of the JoinSplit circuit would accept either the old or new structure; it can potentially do so without any performance cost (i.e. still with only two SHA256Compress evaluations per input), if the new format is arranged carefully.

For the protocol integration, I suggest adding a vector of Mint operations to a transaction, in the same way as we currently have a vector of JoinSplits. All of the Mints would take effect (adding to the note commitment tree) before any of the JoinSplits. This is sufficient because the Mints do not require any of the notes output by the JoinSplits. We can continue to have a v^pub_old input to a JoinSplit; it is low-cost to support, and simplifies maintaining backward compatibility.

To fix the Faerie Gold attack for Mints, we can specify that ρ is derived from r and hSig via a collision-resistant PRF; this allows the recipient of a coin to check that ρ is not repeated without needing to keep track of all seen ρ values. The reason we didn't do it that way originally is that only the note recipient can do this check; generation of notes with repeated ρ is not prevented by public verification, as it is for notes that are JoinSplit outputs. However, I believe this doesn't actually cause any security problem.

[Aside: before we decided to unify the operations, we had renamed "Mint" to "Protect". However given our current terminology, I'd suggest calling this operation "Shield".]

[zookozcash]

This seems to have similar tradeoffs to #647. Is it related to #647?

[daira]

@zookozcash It's independent; you can do either or both, and the effect on privacy is different.

My current inclination is to do #647 and #2230, and change the structure of new commitments so that a secure mint operation would be possible without changing them again. (For the Pedersen commitments this is low cost because you don't need to pad hash inputs to SHA256Compress' input block size, so the extra cost of a multi-level hash is only in rehashing the previous hash output.) Notes with SHA256Compress commitments would be spendable by a separate circuit. Then we can look at the resulting performance and either make this change as well or (I suspect more likely) reject it as unnecessary for Sapling. In the case where we reject it for Sapling, it would then not require another commitment change to do it later.

[nathan-at-least]

Note: doing this would support a major use case that would be beneficial for systemic security; thus I am inclined to prioritize this as a protocol change (although I haven't done careful prioritization of potential Sapling upgrades).

Currently one or more mining pool operators have reported that they cannot do shielded payouts, even when they or their miners would prefer to.

We should verify with pool operator use case that this would allow payouts to arrive at z-addresses. IIUC, this would look like a single transaction with an aggregation of coinbase mining rewards with a very large Shield/Mint vector, with individual public values as payouts. This means the distribution of values would be non-private. The benefit however is that recipients would receive payouts to a z-address, and if any of them postpone the time until they deshield or they send those through subsequent shielded transfers, they would be improving system-wide privacy.

[nathan-at-least]

Requested constraint: ensure that coinbase miner or founders' rewards still must be shielded as their first transition, whether via a v^pub_old or a Shield/Mint transparent input.

Requested constraint: retain the v^pub_old transparent input to JoinSplit (or its Sapling equivalent). This may still be useful for other use cases and as Daira suggests should be relatively small cost overhead.

[daira]

The chosen design for Sapling has a Spend description per shielded input, and an Output description per shielded output, and these are separate. Balance is ensured by summing value commitments. However Output descriptions still have zk-SNARK proofs –albeit of a much smaller circuit– so this is not like a Zerocash "Mint". We don't use a layered note commitment.

If we revisit this design for a future upgrade then we should open another ticket. Closing this one.