Mimblewimble: private, massively-prunable public blockchains

Andrew Poelstra (andytoshi)

https://twitter.com/kanzure/status/784696648597405696

slides: http://diyhpl.us/~bryan/papers2/bitcoin/mimblewimble-2016-scaling-bitcoin-slides.pdf

Hi, I am from Blockstream. I am here to talk about Mimblewimble. Mimblewimble is not mine. It's from the dark lord. I am going to start with the history of the paper. It has been in the news a little bit. I will talk about the transaction structure, the block structure, try to explain the trust model and argue that it's almost as strong as bitcoin. There's less data to verify than in bitcoin. If I have time, then I might talk about some extensions I have done to the protocol to make it extend the scaling beyond what was possible. And then next steps and open problems.

History

This started over 2 months ago, on August 2nd, when someone on IRC, someone logged on with the nickname "majorplayer" where he wrote this paper and he said here's some paper and then he signed off. Myself and Bryan Bishop, who hosts a lot of files related to bitcoin, got this file from the onion link. It was a text file, called mimblewimble.txt, signed "Tom Elvis Jedusor" which is the name of Lord Voldemort in the French Harry Potter books. It's unlikely that this is his real name. But that's the name we have.

I should mention a little bit that I was working on something similar, well not similar, somthing similar but much smaller. When I encountered this, I was surprised, it was what I was working on but much more powerful. It was exciting to me. After the next week or so, I tried to understand what I was doing compared to mimblewimble. I thought it was the same as what I was doing in Elements. I had some discussions with Greg Sanders, who broke a lot of my assumptions... I think that we have got it now.

Over the next couple of months, I spent some little while thinking about open problems posed at the end of the paper about getting further scalability. I think I have managed to get some of it, although some of the stuff I have done would be another talk.

I am not Lord Voldemort. I don't know who did it. A number of people have asked me recently who it was. I don't know.

What is mimblewimble?

It was a paper, neat name, in the Harry Potter books it's a tongue-tying curse that prevents someone from revealing secrets. So this is a fungibility spell. I don't think it was described this way in canon. It's designed for a blockchain. A separate blockchain could be made to be compatible, it could be soft-forked as an extension block or something. This could be applied to bitcoin. To any currency that you can add a mimblewimble sidechain, you get the scalability and fungibility improvements on top of that original chain.

In bitcoin, the way that bitcoin transactions work, you have a pile of inputs and a pile of outputs. Every input is an output from a previous transaction. Every input has to sign the entire transaction. This proves that the person who owns those inputs intends to send the transaction and authorizes this. In mimblewimble, rather than having a complex script system and allowing arbitrary scripts, mimblewimble just has EC keys. You can add and subtract any two EC keys and add and subtract and get another elliptic curve key. If I have some coins attached to some key, and someone wants to move the coins from my key to their key, we can take the difference between the two keys, and create a multisig of that difference, and that's almost as good as any. So we take a sum of all input keys and all output keys, and we can get a single key, and sign it with that. So it's really just operations on keys. It's bitcoin and remove script-- well no, it's designed from the ground-up to be different. I'll mention later that we can get locktime, and we can definitely get multisignatures and locktime. You can use this to get unidirectional payment channels. So in principle you can have lightning on top of mimblewimble, although not in an elegant way. I think this is very cool.

So mimblewimble transactions have inputs just like in bitcoin transactions. The inputs are confidential transactions, rather than bitcoin inputs. They are homomorphically-encrypted vaues. What you can do with confidential transactions is you can add up all the output values, subtract the input values as elliptic curve points. You can check whether they add up to zero. You can't check anything else. There's a priviledged zeropoint in elliptic curve groups. Everything else looks as a uniformly random elliptic curve points. There are no features to these. As far as fungibility is concerned, this is pretty cool that every output looks like a random number. There's an annoying feature of confidential transactions where it's in principle possible to encrypt negative values, so I can create an output with a positive million bitcoins and a negative million bitcoins... I might throw that away and have a million bitcoin. The way that confidential transactions solves this is with a range proof. In elements alpha, we use a range proof developed by Greg Maxwell, which proves that.... you can make it whatever range you wat. As long as it is much less than 2²⁵⁶, you can have any value you want, and it proves it's in the range. It's proofs of knowledge of the blinding key of the output.

Confidential transactions use homomorphic encryption. Mimblewimble uses this as a signing key and a blinding key. It uses range proofs to show that the key is known. In confidential transactions, you add up points, you show they all addu p to zero, you show that all the input values equal the output values. So you have to show that they add up to some other random curve point. That curve point has a key, it proves that it's an encrption of the value zero. We can exploit this in mimblewimble to allow handing over hte key without the recipient learning the sender's keys. We can hand-off keys by signing with their difference, and mimbewimble solves this with an ....

I am going to explain everything else from here on out with pictures. Here's two mimblewimble transactions. The way that we verify that the two transactions are legitimate is that the inputs reference old curve points. We subtract them, see if we get an excess value, we check the signature on the range proof, and then we have a valid transaction. The validity claim is not a bunch of different signatures signed data; it's rather that a bunch of things add up to another thing. A miner watching the network can combine transactions and get another valid transaction. There's a bit of an oddity here with excess values. You end up with another signature on the excess vaues. You can no longer tell which inputs and which outputs were involved. This is non-interactive coinjoin, or one-way aggregatable signatures (OWAS).

So what does this give us? There's fungibility, there's non-interactive coinjoin. Well observe this... one of these transactions spent an output of another. If I'm adding the inputs and subtracting the outputs or vie versa, if the same thing occurred on both sides, I can just drop that or not. These transactions-- one is valid if and only if the other is valid. This is called transaction cut-through which can also be done non-interactively. So I immediately get a scaling and privacy and fungibility benefit. These excess values are unrelated to.... there's no trace that this output ever existed.

Blocks are just one transaction, because of this. It's a header and a single transaction, a list of inputs, a list of outputs, a list of excess values.

Here's a picture of a bunch of mimblewimble blocks in a row. The white boxes are coinbase inputs. Assuming we don't have sidechain stuff; every block has 50 mimblewimble coins or whatever. They don't have to be written down anywhere. You just add a commitment to 50 coins. Suppose you have this mimblewimble chain and some users want to show up and know the status of the chain. In bitcoin, you have to download the entire blockchain, you have to validate everything, oyu have to replay everything to see if the current UTXO set is valid and nothing was removed or nothing invalid. What we can do here is I can send this person all the blocks, but all the transactions here I can just merge together. The blocks commit to the individual commitments. Eahc input is committed to by a different block maybe. You can see that a lot of these inputs are actually outputs of transactions. Every input except for coinbase inputs are outputs of all transactions. So I just have the coinbase inputs which don't need to be encoded; what I give the person is a list of block headers, a list of currently unspent outputs, and their range proofs, and their excess values, because if we could aggregate them in any othe rway then ... but for each transaction, that's a pubkey ad a signature that's like 100 bytes. So with the stuff in the Voldemort paper with no extensions, everything is compressed to 100 bytes. In bitcoin where we have 150 million transactions and historic blockchain data and the UTXO set and the range proofs. If we had confidential transactions in bitcoin, the CT size would exceed the entire size of the current chain, but not by much. With CT, in bitcoin, we would have 1 terabyte of blockchain data by now, if bitcoin had CT from day one. It's a lot of data for a new verifier to download. In mimblewimble you wouldn't have to do that; you only need range proofs on the unspent outputs. It means that the data scales with the number of blocks and transactions grows linearly, but it's a very small amount of data. The bulk of the data would be UTXOs, which can shrink, because you can create a transaction that shrinks the total UTXO set. So in the mimblewimble chain, in addition to whatever anti-DoS resource limits, you might want to limi the UTXO set size, and then incentivize with a fee market for transactions that shrink the UTXO set size. There's unbounded growth in the linear part, but it's very very slow unbounded growth there. So even as the chain goes on for three years and decades, it's very slow growth. It's very exciting.

Okay let's try to explain the trust model in mimblewimble. A transaction is considered valid if it's non-inflationary, you can't create or destroy coins. The outputs minus inputs equal your excess values. Also the owner of the transaction has to sign off on it, by the excess value having a signature on it. A multisig still verifies that every party signs off on this, so this would not be weakened by any extensions to the excess values. So this is almost the same as in bitcoin. In bitcoin, you have it where the owners of the inputs sign off on this specific transaction and this specific data. You can see from this picture that this is what we get here.

In the blockchain, let's considr this new verifier that downloaded the chain data. What can the verifier tell? It can tell that a transaction once it appears in a block... it can check the excess values committed in every block. It just knows the shadow and the shadow never left. So the transaction was not computed after the fact. No net inflation. If you look at the... the unspent outputs minus however much coins should exist, it should equal zero. However, you cannot tell the exact sequence of transactions. I could be giving this verifier where there was a false blockcahin and a lot of inflation in the end, or maybe I stole a bunch of coins or something--- I wouldn't gain anything from such a forgery, other than haha I did all this proof-of-work and I lied and you can't tell. It's not an attack, but it is a different trust model.

As far as fungible usable currency, it's just as strong and as usable as bitcoin's trust model. It gets you a massive scalability improvement.

Sinking signatures

Can we aggregate the excess values in a block? This is in general hard to do. You could do some trickery with a variant of BLS signatures. If you use those, then you get aggregation within a block, but it's possible for someone who has seen a transaction to reverse a transaction by swapping inputs and outputs and putting a minus sign in front of .... and if the excess value doesn't sign itself, meaning you negate it when you... that's very bad. Historic transactions can't be reversed without rewriting blocks, but this is suddenly not the case. So instead you can do tihs scheme where every transaction signs a current blockheight, and ow the transaction the reversal can only appear in the block in which they appear. So reversing it in the same block is trivial and not important. This just by itself, this makes 20 gigabyte of historic data, can be 20 megabytes. So this is 1,000x savings. But now there's a lot of pairings to verify, which is a bit slow.

You can do better than this. You can use proof-of-proof-of-work or compact SPV proofs from the sidechains whitepaper, to basically skip a whole lot of headers. You can give the verifier about 300 blocks that have enough PoW on them to have the same total difficulty as the original chain where the difficulty... in the original chain, a block count for some amount of work, and in the compact chain you can say if a block has exceeded a target, then you give it credit for all the excess it had. So using sinking signatures, allowing these excess values to sign the blockheights as well as previous blockheights, you can aggregate all the excess values on the signatures, and now those 22 megs become 1 megabyte, and you can verify that with unoptimized code in 20 seconds on my laptop. I think that's pretty good resource load for validation.

This does change the trust model a little bit. The way that it changes it is that when oyu do the compression, the compressed chain has the same expected amount of work as the original chain. The variance is much higher, though. In bitcoin, such an attacker has 0 chance of producing that. We can formalise this. If I give you 400k blocks of bitcoin, this is a proof of 395,000 blocks worth of work. If you did substantially less than the full 400k blocks of work, you have almost zero chance. In compact chains this is not the case. So you need to give the verifier about 5000 blocks with the full PoW work. This will prove that what I was giving them was no accident, it wasn't by fluke, someone gave them a lot of work to produce that. And I also give them a compact chain from genesis to that 5k block. So this incentivizes anyone who wants to produce a forgery, that such a forger would expect to do as much work as the original chain, so the Satoshi argument is that they would rather extend the main chain rathr than generate forgeries. One thing proposed every so often is to drop old blocks, then just verify the tip... the problem is that dropping the historic data is analogous to a cliff, where someone who does as much work can forge, because they can forge part of the chain. So we no longer get that here.

Where are we?

I have been working on a consensus library for mimblewimble. I have got hung up on pairing curve selection, I'm working on that now. I am going to publish the source code I've got and encourage people to contribute and do peer review. It's an exciting project. Once that is done and there's a consensus library written, then we can start doing cool stuff, we can write a p2p layer and write wallets and so on, and it will be much easier to write and more friendlier languages and you will have a lot more freedom--- there doesn't need to be consensus on that kind of source code. Right now we're still in the boring consensus part of development. I hope to get past this soon. As far as sidechains, I've been saying, ... we can actually make mimblewimble as a sidechain. If in addition to all the unspent outputs, you commit to pegs-in and pegs-out, then you can apply an excess signature on every peg-in and peg-out. And that's it. I'm over time. So I'm going to stop there. Thank you all.

Q&A

Q: What curve are you using? Could you use ed25519?

A: Good questions. When you create a transaction, the total input value has to equal the total output value. So any fee would be released as an explicit unblinded output value. As it's floating around the network, the miner would commit to that amount of fee value, so the miner would add its own output to all the aggregated transaction. On the blockchain there's an explicit fee. For a curve selection, I can't use secp256k1, can't use Ed25519. For sinking signatures, I need a pairing operation. I am using a 341-bit curve that I came up with, but I'll probably replace this as I learn more about what I should be doing.

andytoshi's mimblewimble paper http://diyhpl.us/~bryan/papers2/bitcoin/mimblewimble-andytoshi-INCOMPLETE-DRAFT-2016-10-06-001.pdf

original mimblewimble paper http://diyhpl.us/~bryan/papers2/bitcoin/mimblewimble.txt

mimblewimble podcast http://diyhpl.us/wiki/transcripts/mimblewimble-podcast/

other mimblewimble follow-up https://www.reddit.com/r/Bitcoin/comments/4vub3y/mimblewimble_noninteractive_coinjoin_and_better/ and https://www.reddit.com/r/Bitcoin/comments/4woyc0/mimblewimble_interview_with_andrew_poelstra_and/ and https://gnusha.org/url/https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-August/012927.html

and https://www.reddit.com/r/Bitcoin/comments/4xge51/mimblewimble_how_a_strippeddown_version_of/

and https://www.reddit.com/r/Bitcoin/comments/4y4ezm/mimblewimble_how_a_strippeddown_version_of/

http://gnusha.org/bitcoin-wizards/2016-08-02.log

http://gnusha.org/bitcoin-wizards/2016-08-03.log

https://www.reddit.com/r/Mimblewimble/comments/58knkc/minimal_implementation_of_the_mimblewimble/