Mimblewimble: Private, Massively-Prunable
Blockchains
Andrew Poelstra
grindelwald@wpsoftware.net

October 8, 2016

1 / 57

History
04:30 UTC, August 2nd, 2016: “Tom Elvis Jedusor” posts a.onion link to a text file on IRC, titled MIMBLEWIMBLE anddated July 19.

2 / 57

History
04:30 UTC, August 2nd, 2016: “Tom Elvis Jedusor” posts a.onion link to a text file on IRC, titled MIMBLEWIMBLE anddated July 19.
Next morning: myself and Bryan Bishop verify it’s actuallyjust text and rehost it.

3 / 57

History
04:30 UTC, August 2nd, 2016: “Tom Elvis Jedusor” posts a.onion link to a text file on IRC, titled MIMBLEWIMBLE anddated July 19.
Next morning: myself and Bryan Bishop verify it’s actuallyjust text and rehost it.
(Previous week: I had independently found a small part ofMimblewimble which was almost supported by Elements
Alpha; starting from this I got the gist of the paper.)4 / 57

History
04:30 UTC, August 2nd, 2016: “Tom Elvis Jedusor” posts a.onion link to a text file on IRC, titled MIMBLEWIMBLE anddated July 19.
Next morning: myself and Bryan Bishop verify it’s actuallyjust text and rehost it.
(Previous week: I had independently found a small part ofMimblewimble which was almost supported by Elements
Alpha; starting from this I got the gist of the paper.)Following week: discussion on Reddit with Greg Sanders andothers leads to understanding Mimblewimble’s trust model,
and hints that the new crypto has merit.

5 / 57

History
04:30 UTC, August 2nd, 2016: “Tom Elvis Jedusor” posts a.onion link to a text file on IRC, titled MIMBLEWIMBLE anddated July 19.
Next morning: myself and Bryan Bishop verify it’s actuallyjust text and rehost it.
(Previous week: I had independently found a small part ofMimblewimble which was almost supported by Elements
Alpha; starting from this I got the gist of the paper.)Following week: discussion on Reddit with Greg Sanders andothers leads to understanding Mimblewimble’s trust model,
and hints that the new crypto has merit.
September: myself and Avi Kulkarni develop an extension,“sinking signatures”, to greatly improve its scaling properties.

6 / 57

History
04:30 UTC, August 2nd, 2016: “Tom Elvis Jedusor” posts a.onion link to a text file on IRC, titled MIMBLEWIMBLE anddated July 19.
Next morning: myself and Bryan Bishop verify it’s actuallyjust text and rehost it.
(Previous week: I had independently found a small part ofMimblewimble which was almost supported by Elements
Alpha; starting from this I got the gist of the paper.)Following week: discussion on Reddit with Greg Sanders andothers leads to understanding Mimblewimble’s trust model,and hints that the new crypto has merit.
September: myself and Avi Kulkarni develop an extension,“sinking signatures”, to greatly improve its scaling properties.
I am not Lord Voldemort.
7 / 57

What is Mimblewimble?

Mimblewimble is a design for a blockchain-based ledger that isvery different from Bitcoin.

8 / 57

What is Mimblewimble?

Mimblewimble is a design for a blockchain-based ledger that isvery different from Bitcoin.
It can be implemented as a sidechain, or softforked into
Bitcoin (with limitations).

9 / 57

What is Mimblewimble?

Mimblewimble is a design for a blockchain-based ledger that isvery different from Bitcoin.
It can be implemented as a sidechain, or softforked into
Bitcoin (with limitations).
In Bitcoin transactions, old outputs sign new outputs; outputs
have “script pubkeys” that are independent of each other. In
Mimblewimble transactions, outputs have only EC pubkeys,
and the difference between new outputs’ keys and old ones’ ismultisigned by all transacting parties.

10 / 57

What is Mimblewimble?

Mimblewimble is a design for a blockchain-based ledger that isvery different from Bitcoin.
It can be implemented as a sidechain, or softforked into
Bitcoin (with limitations).
In Bitcoin transactions, old outputs sign new outputs; outputs
have “script pubkeys” that are independent of each other. In
Mimblewimble transactions, outputs have only EC pubkeys,
and the difference between new outputs’ keys and old ones’ ismultisigned by all transacting parties.
Mimblewimble transactions are inherently scriptless.

11 / 57

Mimblewimble Transactions

A Mimblewimble transaction is the following data:
Inputs (references to old outputs).

12 / 57

Mimblewimble Transactions

A Mimblewimble transaction is the following data:
Inputs (references to old outputs).
Outputs: confidential transaction outputs (group elements,
which blind and commit to amounts), plus rangeproofs.

13 / 57

Mimblewimble Transactions

A Mimblewimble transaction is the following data:
Inputs (references to old outputs).
Outputs: confidential transaction outputs (group elements,
which blind and commit to amounts), plus rangeproofs.
Excess: difference between outputs and inputs (groupelement), plus signature (for authentication and to prove
non-infaltion)

14 / 57

Mimblewimble Transactions

15 / 57

Mimblewimble Transactions

16 / 57

Mimblewimble Transactions

17 / 57

Mimblewimble Transactions

18 / 57

Mimblewimble Transactions

19 / 57

Blocks consist of:

A merkle tree of transaction inputs.

20 / 57

Mimblewimble Transactions

21 / 57

Mimblewimble Transactions

22 / 57

Mimblewimble Transactions

23 / 57

Mimblewimble Transactions

24 / 57

Trust Model: Transactions

A transaction is valid if:
It is non-inflationary (total input amount equals total outputamount)

25 / 57

Trust Model: Transactions

A transaction is valid if:
It is non-inflationary (total input amount equals total outputamount)
The owner of the input(s) has signed off on it.

26 / 57

Trust Model: Transactions

A transaction is valid if:
It is non-inflationary (total input amount equals total outputamount)
The owner of the input(s) has signed off on it.

27 / 57

Trust Model: Blockchain
It should be verifiable that
A transaction, once committed to a block, cannot be reversed
without doing enough work to rewrite the block (and all its
descendants).

28 / 57

Trust Model: Blockchain
It should be verifiable that
A transaction, once committed to a block, cannot be reversed
without doing enough work to rewrite the block (and all itsdescendants).
The current state of all coins reflects zero net theft andinflation.

29 / 57

Trust Model: Blockchain
It should be verifiable that
A transaction, once committed to a block, cannot be reversed
without doing enough work to rewrite the block (and all itsdescendants).
The current state of all coins reflects zero net theft andinflation.
The exact historical sequence of transactions does not need tobe publicly verifable.

30 / 57

Trust Model: Blockchain
It should be verifiable that
A transaction, once committed to a block, cannot be reversed
without doing enough work to rewrite the block (and all its
descendants).
The current state of all coins reflects zero net theft andinflation.
The exact historical sequence of transactions does not need tobe publicly verifable.

31 / 57

Trust Model: Block Verification

It is possible to verify the blockchain with only the following data:
Block headers

32 / 57

Trust Model: Block Verification

It is possible to verify the blockchain with only the following data:
Block headers
Unspent outputs from each block

33 / 57

Trust Model: Block Verification

It is possible to verify the blockchain with only the following data:
Block headers
Unspent outputs from each block
Excess values and signatures.

34 / 57

Trust Model: Block Verification

It is possible to verify the blockchain with only the following data:
Block headers
Unspent outputs from each block
Excess values and signatures.
Rangeproofs for the above (witness data)

35 / 57

Trust Model: Block Verification

It is possible to verify the blockchain with only the following data:
Block headers
Unspent outputs from each block
Excess values and signatures.
Rangeproofs for the above (witness data)Full blocks near the tip should be kept to handle reorgs

36 / 57

Trust Model: Block Verification

It is possible to verify the blockchain with only the following data:
Block headers
Unspent outputs from each block
Excess values and signatures.
Rangeproofs for the above (witness data)
Full blocks near the tip should be kept to handle reorgs
In Bitcoin there are 150 million transactions and 40 million
unsigned transaction outputs: 21.6Gb of historic data, 2Gb ofUTXOs and 100Gb of UTXO rangeproofs.

37 / 57

Sinking Signatures

Open problem 2 from the Voldemort paper: can we aggregate
excess signatures?
Difficult to do without also making them negatable in later
blocks. (If you can add you can subtract.)

38 / 57

Sinking Signatures

Open problem 2 from the Voldemort paper: can we aggregate
excess signatures?
Difficult to do without also making them negatable in later
blocks. (If you can add you can subtract.)
We can by using pairings and (a variant of)
Boneh-Lynn-Shacham signatures which sign the current blockheight.

39 / 57

Sinking Signatures

Open problem 2 from the Voldemort paper: can we aggregate
excess signatures?
Difficult to do without also making them negatable in later
blocks. (If you can add you can subtract.)
We can by using pairings and (a variant of)
Boneh-Lynn-Shacham signatures which sign the current blockheight.
Now only one excess and (multi-)signature per block.

40 / 57

Sinking Signatures

Open problem 2 from the Voldemort paper: can we aggregate
excess signatures?
Difficult to do without also making them negatable in later
blocks. (If you can add you can subtract.)
We can by using pairings and (a variant of)
Boneh-Lynn-Shacham signatures which sign the current blockheight.
Now only one excess and (multi-)signature per block.
In Bitcoin there are 450000 blocks: so 22Mb of historic data(but 450k pairings to verify), 2Gb of UTXO and 100Gb ofrangeproofs.

41 / 57

Sinking Signatures
What if we could combine blocks as well?
It is possible to compress a chain of blockheaders tologarithmic size while still having a proof that takes the same
expected work as the original [Back et. al. 2014; Kiayias,Lamprou, Stouka 2016].

42 / 57

Sinking Signatures
What if we could combine blocks as well?
It is possible to compress a chain of blockheaders tologarithmic size while still having a proof that takes the same
expected work as the original [Back et. al. 2014; Kiayias,
Lamprou, Stouka 2016].
Treat the blockchain as a “skiplist” where blocks have distantparents.

43 / 57

Sinking Signatures
What if we could combine blocks as well?
It is possible to compress a chain of blockheaders tologarithmic size while still having a proof that takes the same
expected work as the original [Back et. al. 2014; Kiayias,Lamprou, Stouka 2016].
Treat the blockchain as a “skiplist” where blocks have distantparents.
If excess values signed the current height and previous
heights, the excesses and signatures can be combined forskipped blocks.

44 / 57

Sinking Signatures
What if we could combine blocks as well?
It is possible to compress a chain of blockheaders tologarithmic size while still having a proof that takes the same
expected work as the original [Back et. al. 2014; Kiayias,Lamprou, Stouka 2016].
Treat the blockchain as a “skiplist” where blocks have distantparents.
If excess values signed the current height and previous
heights, the excesses and signatures can be combined forskipped blocks.
This is a sinking signature, which can be made log-sized.
[Poelstra, Kulkarni 2016]45 / 57

Sinking Signatures
What if we could combine blocks as well?
It is possible to compress a chain of blockheaders tologarithmic size while still having a proof that takes the same
expected work as the original [Back et. al. 2014; Kiayias,
Lamprou, Stouka 2016].
Treat the blockchain as a “skiplist” where blocks have distantparents.
If excess values signed the current height and previous
heights, the excesses and signatures can be combined forskipped blocks.
This is a sinking signature, which can be made log-sized.
[Poelstra, Kulkarni 2016]
Simulations show a 500000-block chain can likely becompressed to 300 blocks. We now have 1Mb of historic data
(20 seconds on one core to verify), 2Gb of UTXO and 100Gbof rangeproofs.
46 / 57

Trust Model: Blockchain verifitation, redox
Compact chains have same expected work to produce but
much higher variance than the original chain.

47 / 57

Trust Model: Blockchain verifitation, redox
Compact chains have same expected work to produce but
much higher variance than the original chain.
With nontrivial probability a compact chain can be producedin less work than one block; thus compact chains prove nowork.

48 / 57

Trust Model: Blockchain verifitation, redox
Compact chains have same expected work to produce but
much higher variance than the original chain.
With nontrivial probability a compact chain can be producedin less work than one block; thus compact chains prove nowork.
We thus distinguish between expected work which affects
economic incentives for forgeries, and proven work whichassures a verifier an historic fact about how a chain wasproduced.

49 / 57

Trust Model: Blockchain verifitation, redox
Compact chains have same expected work to produce but
much higher variance than the original chain.
With nontrivial probability a compact chain can be producedin less work than one block; thus compact chains prove nowork.
We thus distinguish between expected work which affects
economic incentives for forgeries, and proven work whichassures a verifier an historic fact about how a chain wasproduced.
Mimblewimble verifiers should demand a month or two ofnon-compact blocks on top of a compact chain. This proves amonth or two of work, but a forger expects to do as muchwork as the entire chain. So no “incentive cliff” and verifiers
can also be assured that their chain was no accident.
50 / 57

Next Steps

Development, development, development!

51 / 57

Next Steps

Development, development, development!
Nail down chain parameters, in particular choice ofpairing-friendly curve.

52 / 57

Next StepsDevelopment, development, development!
Nail down chain parameters, in particular choice ofpairing-friendly curve.
Sidechain?

53 / 57

Open Problems

Smaller rangeproofs? Aggregation of rangeproofs?

54 / 57

Open Problems

Smaller rangeproofs? Aggregation of rangeproofs?
Peer-to-peer protocol that can handle transaction merging

55 / 57

Open Problems

Smaller rangeproofs? Aggregation of rangeproofs?
Peer-to-peer protocol that can handle transaction merging
Quantum resistance

56 / 57

Thank You
Andrew Poelstra <grindelwald@wpsoftware.net>

57 / 57