Promises: fast 0conf and mempool payments for Zcash

Abstract: Zero-confirmation transactions allow for instant payment but proving time and therefore transaction generation time is a major delay for shielded zeroconf payments. This post presents a solution: promissory notes. Promissory notes are a fast way for a customer to promise funds to a merchant and prove (in zero-knowledge of course) that the promise is backed by real zec. If the customer ever tries to spend those funds to a different recipient, the merchant can block that use of funds. Moreover, promises can be made not just for spending confirmed funds, but for spending funds that are themselves unconfirmed. This removes a major obstacle to zcash usage. Because promissory notes cannot transfer value themselves, cryptographic breaks in them do not lead to inflation. As a result, faster but less safe cryptographic primitives can be used.

This protocol came out of an initial discussion between @tromer and I in the back of an Uber during RWC.

Background and motivation:
Sapling is fast, it takes about 2 seconds on a desktop to make a transaction. We could make it about 10 times faster by switching over to an algebraic hash function like MIMC or Rescue or whatever the flavor of the week is now. However, these are bleeding edge and we have no way of knowing if they are secure.

Hash functions are arguably the hardest thing to design in cryptography. Most hash functions do not have proofs of security. Worse, the history of hash functions is a graveyard of once invincible champions. And those are the ones that fared the best. MD5 and SHA1, now broken, were once the state of the art everyone agreed was secure. Far worse, those two functions were found to be flawed only because they were the de-facto standard and therefore attracted all the attention of the tiny number of researchers who analyze these things. No new hash function used in cryptocurrency will attract enough public attention anytime soon. So, using exotic hash functions is not safe. It will risk undetectable inflation. This is why sapling uses standard hash functions and Pedersen hashes which are somewhat unique in that they are provably secure. This means switching to faster hash functions for confirmed transactions is not an option.

Transaction generation time doesn’t actually matter for confirmed transactions, so the overhead of Pedersen hashes during proving is irrelevant. Transaction confirmation, especially across multiple blocks, takes well north of a minute on any reasonable blockchain. This is true even if you lower the block interval. So we don’t actually need to make proof generation faster for confirmed TXs.

However, no one tries to make fast payments with confirmed transactions. They do it with zero-confirmation (zeroconf) transactions. In a zeroconf transaction, a customer pays a merchant (e.g. for a cup of coffee) and the merchant accepts once the transaction is broadcast. Optionally the merchant can also monitor the network to detect double spends. This isn’t perfect, but people do it for small value payments. And here, sapling transaction time generation is a major problem. Zcash also faces a second major problem here: confirmation latency. In order to spend shielded money they receive, a user must wait for those funds to be confirmed for 10 blocks. Buying a cup of coffee with a paycheck you just received could take 10 minutes to see the money confirmed in your account and then another 10 minutes to see the payment for the coffee confirmed.

The idea:
Construct a version of the sapling circuit that uses fast hash functions for the merkle tree. Everything else, note structure, keys, signatures, and crucially the nullifier remains the same.

To purchase a cup of coffee, a customer constructs a promissory transaction and shows it to the merchant. Because it proves there is a sapling note with the appropriate balance in it that belongs to the customer, this is effectively proof the customer is good for the money they are promising to pay. The only risks the merchant now faces is 1) that the money will be double spent. This is the same for any zeroconf transaction and the same risk mitigations apply. Promissory notes need not address it. 2) that the customer will never broadcast the real transaction. This is new, but fixable.

If we modify the consensus protocol a little, we can penalize problem 2 very effectively. Sapling and promissory TXs have the same nullifier. We can modify consensus rules to allow a promissory note to block a real transaction that pays the funds to any other address. This would make the customer forfeit the entire balance not just that they owed the merchant, but what they’d get back in change. There are a couple of issues that need to be worked out. 1) this allows transaction revocation, though at the cost of burning the funds. We may need to limit the window in which this can be done or make it possible to opt out of it (so the recipient knows the funds are unconditionally theirs). 2) Care is needed to ensure a merchant can’t mutate the on chain transaction (that does pay them) and then use the promissory note to block it and thus deprive the customer of their change.

Extensions
Zeroconf from mempool. You can spend your money even if the transaction pays it to you is not yet confirmed. Assume the customer and merchant can agree on a set of pending mempool transactions that are reasonably likely to be included in the next few blocks. Then the promissory proof can be with respect to a merkle tree constructed over both the blockchain and this mempool list. If we change the sapling circuit so that nullifiers are not dependent on merkle tree position, then such a promissory tx would give a merchant assurance that if the transaction is included in a block, the money is either theirs or will be burned/blocked as we describ above.

Pay to merchant on dispute: With changes to the sapling circuit, we can also set this up so that if the customer tries to make a different payment with the same nullifier, the amount of the note they are spending is revealed. We do this by having the on chain tx contain a 1 of 2 secret share of the balance. The promissory tx has the other share. With the balance is revealed, the money they are owed can be paid to the merchant and the rest burned.

Security considerations
In none of these scenarios does a break in the promissory circuit lead to undetectable inflation because never create value. However, If we allow blocking/claiming behavior, then a forged proof could allow someone to, publicly, steal funds. This is potentially preventable. Early designs for sapling had the nullifier be a public key under which the transaction had to be signed. Generating a false sapling light transaction in that setting would require forging a signature. There may be other ways of accomplishing this. E.g. by constraining how spend authorization keys are randomized and allowing a dispute process.

Trusted setup. If forged and block issue can be resolved, then we do not need to worry about trusted setup, since the merchant can generate the parameters because they are the only one who is affected by falsified proofs. This has a small privacy cost. So a global set of parameters is still better. Again, however, as these are not trust critical, the setup can be smaller.

13 Likes

I’m not sure the Sapling proving time is really much of a problem even for zeroconf. Wouldn’t it be simpler just to show the real Sapling tx to the merchant? Then the merchant can verify and broadcast it themself, solving issue (2) more simply.

(I’m aware that the proving time increases if there are multiple notes.)

2 Likes

Very interesting!

I think this is still a little ambitious :stuck_out_tongue: The Pedersen hashes in the Sapling commitment tree are 1380 constraints, making up 43% of the Sapling circuit. Some example numbers:

  • IIRC in the demo Halo implementation I had the Rescue hash function with r rounds and m state size implemented in r * m * (3M + 6L) * 2; for r = 10 and m = 13 (which might be conservative for this use case) that’s 780 multiplication constraints, or 57% of the size of a Pedersen hash. This would make the current Sapling circuit around 19% smaller, but still between 216 and 217 constraints, so only a small proving speed-up.

  • If we had a very efficient hash function that required 10x fewer constraints (138 per hash), this would make the current Sapling circuit around 39% smaller. This would bring it below 216 constraints, doubling the speed of the prover.

To get anywhere near 10x faster overall proving time we’d need to replace or eliminate the BLAKE2s calls (used in the circuit for computing ivk in the key structure, and computing the nullifier). We couldn’t do that for the current circuit, given this constraint:

But let’s assume we have a new version of the Sapling circuit that replaces the BLAKE2s invocations with something (either another hash function or another circuit design that removes the need for PRF invocations) that is ~10x faster (say 2000 constraints instead of 20,500). If that were the only change, the circuit would be around 59,500 constraints (below 216, so already 2x faster than Sapling). Promissory notes for that circuit, for the two scenarios above, would be:

  • Rescue-780C: 40,300 constraints, which is between 215 and 216, so a small speed-up.
  • 10x-Pedersen-hash: ~19,800 constraints. This is below 215, so 2x faster again, and only around ~3400 constraints away from 214.

So with both a new base circuit and promissory notes, we could get in the 4x faster ballpark, and maybe into the 8x faster ballpark with some clever engineering (or if BLAKE2s could be dropped entirely without requiring any replacement constraints).

3 Likes

10 seconds on Mobile to get a cup of coffee seems less than ideal.
But, maybe its not that bad. The added benefit of this idea is “spending” from mempool.

2 Likes

BTW if you use Rescue or Poseidon for the note commitment tree, you really want to switch to a tree with arity > 2. That reduces the tree depth; I haven’t worked out the detail but it’s better than a 57% improvement for the Merkle tree part of the circuit. Agreed that you need to still need to replace the BLAKE2s calls for the circuit change to be worth it.

3 Likes

Right. This entire thing implicitly assumed we might figure out how to remove blake2. I need to start that thread too …

2 Likes

FWIW I think Ian is overly conservative here. Algebraic hash functions might be a year or two away from appearing in Zcash and by then I think we’ll be able to make decisions we’re comfortable with.

Note that the ideas here are really interesting, it’s kind of distracting to talk about hash function risk aversion in broad strokes especially when people don’t really agree on the subject.

4 Likes

A possibly circuit-efficient algebraic PRF:

Please pay attention to the disclaimer:

NB. I am making no claims here about the suitability of the BMR PRF to instantiate \mathsf{PRF^{nfSapling}} or \mathsf{CRH^{ivk}} from a security point of view.

Note that the concrete efficiency and security will depend on how large the parameter ℓ can be, which is unclear.

Obviously this is not compatible with BLAKE2s so would require a turnstile. It therefore only makes sense if we had other motivations to change the circuit.

Why not do the DY-VRF which is prf_k(x)= g^{1/(k+x)}? Seems simpler.

If I understand correctly, it’s only secure assuming ℓ-DDH when x is from a domain of size ℓ. Also there’s a security gap that depends on ℓ.

Something like that, yes. We should check that holds if we merely want unlinkability and not pseudo-random output. I believe for our purposes of anonymity, the weaker property suffices.

1 Like

Yeah, in the case of \mathsf{PRF^{nfSapling}}, the owner of the PRF key \mathsf{nk}\star only uses it on \rho\star values for notes they actually hold. It seems strange to me that security would depend on the size of the whole domain, when you’re only giving the attacker output from a small fraction of it. But I don’t know 🤷.

I suspect that both algebraists and bit-twiddlers will look askance at me for suggesting this, but how about [\mathsf{Rescue}_K(x)] H for key (K, H)? Here the scalar mul with secret base protects against cryptanalysis of Rescue, and Rescue acts as a mixing function that is heuristically at least as good for this purpose as 1/(k+x).