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.
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.
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.
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.