Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Offline Transactions in Mimblewimble

Offline Transactions in Mimblewimble

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.

Current Protocol

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:

  1. 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.
  2. 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.
  3. 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.

Building Non-Interactive Transactions

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.

Our Proposal

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_data containing the sender_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.

Security

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):

  1. Alice creates a transaction containing an output for Bob.
  2. Bob sends Alice the goods she purchased.
  3. Several days (or perhaps even years) pass where Bob has not yet spent his coins.
  4. 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.

Privacy

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

Payment Proofs

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.

Multisig Wallets

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.

Additional Improvements

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.

Acknowledgements

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.

@hansieodendaal

This comment has been minimized.

Copy link

@hansieodendaal hansieodendaal commented Feb 5, 2020

Hi @DavidBurkett, I would like to understand output_data a bit better. As stated, for one-sided output Pedersen commitment (vH + kG), values of v encrypted using ECDHE(sender's key, receiver's key) and k encrypted using ECDHE(sender's key, receiver's key) will be added to output_data.

  • Q1: Does this mean the shared secret S between Alice and Bob will not be used as the blinding factor as suggested earlier, but as the key to encrypt and decrypt v and k with symmetric-key encryption?
  • Q2: In order for Bob to sense a one-sided payment was made by Alice, without out of band communication by Alice, he would need to scan the blockchain and pick up any UTXO with his own pubkey in the output_data, correct?
@DavidBurkett

This comment has been minimized.

Copy link
Owner Author

@DavidBurkett DavidBurkett commented Feb 5, 2020

A1: Yes, the shared secret is not the blinding factor, it's the key to decrypt the value and blinding factor.

A2: Yes, that is correct.

@hansieodendaal

This comment has been minimized.

Copy link

@hansieodendaal hansieodendaal commented Feb 5, 2020

Thanks, understood.

Another comment then w.r.t. Signatures must be verified for all recent inputs. We recommend new nodes verify all input signatures for the most recent X blocks, where X=coinbase maturity, since the risks are similar.

Maybe it would just be more consistent to verify all (a) input signatures and (b) your newly proposed UTXO cut-through blocking, up to the pruning horizon as part of normal block validation.

@DavidBurkett

This comment has been minimized.

Copy link
Owner Author

@DavidBurkett DavidBurkett commented Feb 5, 2020

Good point. I see no reason not to verify them, since we'll have the blocks anyway. I'll make that change now.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.