Mimblewimble is a blockchain protocol that improves on bitcoin's privacy and scalability by using pedersen commitments, schnorr signatures, and a novel technique called 'cut-through'. These benefits have come at a steep cost. Building transactions have thus far required interaction between the sender and receiver to create the outputs and collectively sign the transaction. We present here a method of achieving one-sided transactions while minimizing the impact on the scalability and privacy of mimblewimble.
Like bitcoin, Grin uses a UTXO model. Transactions are created by including inputs to spend, creating new outputs of equal or lesser value, and signing and building rangeproofs to verify ownership of the inputs.
Unlike bitcoin, Grin uses confidential transactions, so the inputs and outputs are pedersen commitments (r*G + v*H). Instead of the signatures being added to the inputs, there is only one signature per transaction, which is part of the transaction kernel. This signature proves knowledge of the blinding factors (and therefore, ownership) of the inputs, and collective knowledge of the blinding factors of the outputs.
In order for a transaction to be valid, the following must be true (ignoring fees and transaction offsets, for simplicity):
- The sum of the output commitments minus the sum of the input commitments must equal the kernel commitment. ie.
(r_out1..n*G +v_out1..n*H) - (r_in1..n*G +v_in1..n*H) = r_kern*G - A signature of the kernel excess value
(rk = sum(ro1..n) - sum(ri1..n))to the base point G of some known message. - A rangeproof proving none of the output values are negative.
The combination of these 3 things proves that the sender is the owner of the inputs, and that no new coins are created in the transaction.
This protocol requires the sender (Alice) to interact with the receiver (Bob) to build the transaction, in order to avoid revealing the blinding factors for each other's inputs and outputs. This is a 3 step process:
- Alice creates an unsigned transaction with her inputs, change output & rangeproof, an intermediary kernel containing the difference in her output and input blinding factors, and commits to a nonce for the schnorr signature.
- Bob creates his output & rangeproof, adds his share of the kernel commitment to generate the actual transaction kernel, commits to his nonce, and provides a partial signature of the transaction kernel.
- Alice signs her portion of the kernel signature, and aggregates the 2 signatures.
While this protocol works, and allows Alice to immutably transfer funds to Bob, the interactive portion presents some security, usability, and privacy challenges. Building transactions either requires a user to keep their keys online, or requires some form of out-of-band communication which could result in privacy leaks and MITM attacks.
It's long been the belief of most that non-interactive transactions were not possible in mimblewimble, since knowledge of an output's blinding factor is necessary to create rangeproofs, and to build the schnorr signature.
To solve this, we must first find a way for both the sender and the receiver to know the blinding factor, but nobody else. Diffie-Hellman is perfect for this. The sender simply generates a keypair, performs ECDH with the receiver's pubkey, and generates a shared secret, which can be used as the blinding factor. The sender can then generate the receiver's outputs, blinding factors, and signature to create a valid transaction. But this presents 2 obvious problems.
The first problem is the sender still has to communicate their public key and the value to the receiver, so we need to somehow include that as part of the output without affecting privacy. But there's no obvious way to commit to the data. We can't include it as part of the kernel, since it would link kernels to outputs, removing privacy benefits.
The second problem is both Alice and Bob end up with the keys to the funds, which means Bob doesn't become exclusive owner of the funds, and it's impossible to resolve disputes. We need a way to verify that only Bob can spend the output.
As it turns out, it's possible to encrypt nearly 32 bytes of data in the rangeproof. If we use a known key, blake2b(output_commitment) for example, we could then publicly commit to some additional data. And if the data we "encrypt" in the rangeproof is a hash, we can actually publicly commit to as much data as we need. This allows us to include a new block of data (output_data) containing:
- sender's ephemeral pubkey
- receiver's pubkey
- value of the output (encrypted using
ECDHE(sender's key, receiver's key)) - output's blinding factor (encrypted using
ECDHE(sender's key, receiver's key))
Then, we can add the following consensus rules for verifying outputs:
- Every rangeproof must be rewindable using
blake2b(output_commitment) - Every output must contain
output_datacontaining thesender_pubkey,receiver_pubkey, and some additional encrypted data - The
ripemd160(blake2b(output_data))must match the first 20 bytes of the rewound rangeproof data
Nodes must store this output_data for all UTXOs, so when they are later spent, we can also require 1 new consensus rule for verifying inputs:
- Every input must contain a valid signature:
sig(receiver_pubkey, input_commitment)
Inputs and outputs can continue to be pruned as usual, and we've now provided a means of sending funds to a receiver, and guaranteeing the sender can not respend those funds.
Because both the sender and receiver know the blinding factor of an output, it's no longer enough to just verify the current UTXO set against the kernels. Signatures must be verified for all recent inputs. We recommend new nodes verify all input signatures for the most recent blocks up to the cut-through horizon, since all full nodes should already have access to those blocks.
This still leaves one attack that isn't possible today. The attack works as follows (assume input signatures verified for the past day):
- Alice creates a transaction containing an output for Bob.
- Bob sends Alice the goods she purchased.
- Several days (or perhaps even years) pass where Bob has not yet spent his coins.
- Alice forces a large reorg beyond the horizon. She can then send Bob's output back to herself, since she knows the blinding factor, and signatures aren't validated for transactions in blocks beyond the horizon.
While this attack theoretically allows you to spend coins of any age, they have to be coins the attacker previously sent, and have not yet been spent by the receiver. However, the financial incentives provided by this attack are unlikely to be larger than those of much shorter reorgs today. For the extra cautious though, simply self-spending coins when you receive large amounts would prevent this attack, at the minimal cost of an additional kernel.
The described scheme does not leak any additional privacy as long as keypairs are not reused. To ensure this, we recommend making a fairly trivial modification to the output_data to support some form of stealth addresses (either ISAP or DKSAP).
Payments can now be proven fairly easily. All that's required to prove a payment was made is the original output, rangeproof, output_data, and a merkle proof that shows membership to the rangeproof MMR.
Currently, securely sending to a multisig wallet involves the sender needing to interact with all of the receiving parties. This removes that need, at the cost of a loss of privacy for the multisig wallet.
Since we now have a way to commit to additional data as part of the outputs, we can move fee, and perhaps other data out of the kernel and into the output_data struct, which will allow pruning, and therefore reduce the size of the chain.
Thanks to John Tromp for detailing the reorg attack, Jasper van der Maarel for his input on bulletproofs and multisig wallets, Phyro for suggesting the idea of moving kernel details into the output_data struct. Also, a huge thanks to Daniel Lehnberg, Antioch Peverell, Phyro, and Vladislav Gelfer for their valuable feedback on the design.
I see a potential problem here.
Both Alice and Bob know the output blinding factor, so they are both able to create a transaction that balances out. You make the assumption that this is OK because only Bob can sign with
receiver_pubkey. However, imagine the following scenario:This could be fixed by binding the input signature to the kernel or the outputs, but that's hard to do without introducing linkability issues.