-
Notifications
You must be signed in to change notification settings - Fork 9
/
poelstra mimwim paper
860 lines (859 loc) · 47.6 KB
/
poelstra mimwim paper
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
http://mimblewimble.cash/20161006-WhitePaperUpdate-e9f45ec.pdf
Mimblewimble
Andrew Poelstra∗
2016-10-06 (commit e9f45ec)
Abstract
At about 04:30 UTC on the morning of August 2nd, 2016, an anonymous person using the
name Tom Elvis Jedusor signed onto a Bitcoin research IRC channel, dropped a document hosted
on a Tor hidden service[Jed16], then signed out. The document, titled Mimblewimble, described
a blockchain with a radically different approach to transaction construction from Bitcoin, supporting
noninteractive merging and cut-through of transactions, confidential transactions, and
full verification of the current chainstate without requiring new users to verify the full history of
any coins.
Unfortunately, while the paper was detailed enough to comminicate its main idea, it contained
no arguments for security, and even one mistake1
. The purpose of this paper is to make
precise the original idea, and add further scaling improvements developed by the author.
In particular, Mimblewimble shrinks the transaction history such that a chain with Bitcoin’s
history would need 15Gb of data to record every transaction (not including the UTXO set, which
including rangeproofs, would take over 100Gb). Jedusor left open a problem of how to reduce
this; we solve this, and combine it with existing research for compressing proof-of-work
blockchains, to reduce the 15Gb to less than a megabyte.
License. This work is released into the public domain.
1https://www.reddit.com/r/Bitcoin/comments/4vub3y/mimblewimble_noninteractive_coinjoin_
and_better/d61n7yd
1
Contents
1 Introduction 2
1.1 Overview and Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Trust Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Preliminaries 5
2.1 Cryptographic Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Standard Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Sinking Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Mimblewimble Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 The Mimblewimble Payment System 9
3.1 Fundamental Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 The Blockchain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3.1 Block Headers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3.2 Proven and Expected Work . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3.3 Sinking Signatures and Compact Chains . . . . . . . . . . . . . . . . . . . 14
4 Extensions and Future Research 16
5 Acknowledgements 17
1 Introduction
In 2009, Satoshi Nakamoto introduced the Bitcoin cryptocurrency[Nak09], an online currency system
to allow peer-to-peer transfer of digital tokens. These tokens’ ownership is ascertained by the
use of public keys, and transfer is accomplished by means of a public ledger, a globally replicated
list of transactions which destroy unspent transaction outputs (UTXOs) and create new ones of
equal value but different keys.
All Bitcoin coins originate in coinbase transactions, transactions which create new outputs without
destroying any old ones, and which are limited in value to maintain a fixed inflation schedule.
Once created, they change hands by means of ordinary transactions. This means that new users, in
10 order to fully verify that their view of the system is uncompromised (absent theft or illegal inflation),
must download and validate the entire history from the system’s genesis in 2009 until today.
In other words, they must download and “replay” every transaction that has ever occurred.
Today the Bitcoin blockchain sits just shy of 100Gb on the author’s disk. Had Bitcoin used Con-
fidential Transactions[Max15] (CT), each of the approximately 430 million outputs would consume
2.5Kb each, totalling over a terabyte of historical data2
.
In this paper, we describe a research project to design a Bitcoin-like cryptocurrency, which
achieves dramatically better scaling and privacy properties than Bitcoin. In particular, it allows
2The author is aware of unpublished research that would reduce this quantity by about 25%; the total is still formidable.
2
removal of most historic blockchain data, including spent transaction outputs, rangeproofs and all,
while still allowing users to fully verify the chain. Indeed, it is possible for the system to function
20 even if no users retain the vast majority of historic blockchain data.
Further, this currency allows transactions to be noninteractively combined (a la Coinjoin[Max13a])
and cut-through[Max13b], eliminating much of the topological structure of the transaction graph. If
this is done without publishing the original component transactions, the result is an enormous boon
to user privacy, amplified by CT.
Unfortunately, it accomplishes these goals at cost of sacrificing functionality.
1.1 Overview and Goals
Mimblewimble is a design for a cryptocurrency whose history can be compacted and quickly veri-
fied with trivial computing hardware even after many years of chain operation. As a secondary goal,
it should support strong user privacy by means of confidential transactions and an obfuscated trans-
30 action graph. However, to achieve these goals, Mimblewimble cannot support a general-purpose
scripting system such as that in Bitcoin. This precludes such functionality as zero-knowledge contingent
payments[Max16], cross-chain atomic swaps[Nol13] and micropayment channels[PD16].
Further research is needed to emulate these functionalities on top of Mimblewimble, and is discussed
in Section 4.
More precisely,
• Direct transfer of value between parti(es) to other parti(es) should be possible on the system.
• All transactions should use confidential transactions to blind their output amounts.
• Transactions should be noninteractively aggregable[Mou13], i.e. support a noninteractive
variant of CoinJoin[Max13a, Max13b], such that parties not privy to the original transactions
40 are unable to separate them. This can improve censorship resistance and privacy, though it is
unclear how to design a safe peer-to-peer network capable of exploiting this ability.
• For a new participant, the amount of bandwidth and processing power needed to catch up
with the system should be proportional to the current state of the system, i.e. the size of the
UTXO set plus rangeproofs, rather than the total size of all historical transactions.
As described in the next section, and more thoroughly in Section 3.3, Mimblewimble has
a scheme for compressing blockchain history to a size polylog in the original size, which in
practice for a system with Bitcoin’s scale should allow a decade or more of transaction history
to be verified in several seconds using a couple megabytes of data3
.
3Experiments with the compact chains described in this paper suggest that a 500000 block chain may have a compact
length of around 300 blocks (though with high variance across multiple experiments), each containing sinking signatures
which average ten 96-byte elliptic curve points, merkle commitments to previous blocks consisting of forty 40-byte (blockhash,
difficulty) pairs, and some extra block header data, totalling less than 3Kb of data. Across 300 blocks this is 900Kb
total of compact chain data. Verification time is dominated by pairing computations, of which there are on average ten per
block, or 3000. On the author’s laptop using Ben Lynn’s libpbc library, these can be done in under 20 seconds using a
single core. By more careful choice of elliptic curve, and focused optimization work, this number can surely be improved.
3
On the other hand, Bitcoin’s current state of 40 million unspent outputs would grow to 100Gb
50 and a few days of verification on a modern CPU, thanks to Mimblewimble’s use of confidential
transitions. It is an open problem how to improve this. We observe that even without
cryptographic improvements, it would go a long way to simply cap the UTXO set size as a
function of blockheight and let the transaction-fee market take care of it.
1.2 Trust Model
Like Bitcoin, Mimblewimble is a blockchain-based cryptocurrency intended to be instantiated in
a decentralized manner in which users may join or leave the system at any time. Further, upon
(re)joining the network, users should be able to determine the network state, at least up to some
recent time, and verify that this state was obtained by a series of valid state transitions, without
trusting the honesty of any third parties.
60 However, there are two points of departure from Bitcoin’s trust model:
1. Unlike Bitcoin, whose blockchain describes every transaction in its entirety, and therefore
allows all users to agree on and verify the precise series of transactions that led to the current
chainstate, Mimblewimble only allows users to verify the essential features:
• A transaction, once committed to the block, cannot be reversed without rewriting the
block (or by the owner(s) of its outputs explicitly undoing it).
• The current state of all coins was obtained by zero net theft or inflation: there are exactly
as many coins in circulation as there should be, and there for each unspent output there
exists a path of transactions leading to it, all of which are committed in the chain and
authorized.
70 Note that there may be other paths which have also been committed in the chain, during
which some transactions may have been invalid or unauthorized or inflationary, but
since a legitimate path exists, all these things must have netted out to zero.
2. Like Bitcoin, verifiers may see multiple differing blockchains, and select the valid one as the
one with the greatest total work. This is detailed in Section 3.3.2.
However, in Bitcoin the total work represents both the expected work to produce such a
blockchain as well as the proven work of the chain, in the sense that any party who expends
significantly less than this much work will be unable to produce such a chain except with
negligible probability.
Mimblewimble, on the other hand, separates these. The total work still represents the ex-
80 pected work to produce the blockchain, and therefore incentivizes rational actors to contribute
to the most-work chain rather than rewriting it. The proven work, on the other hand, is
capped at some fixed value independent of the length of the chain, and serves to make forgery
by irrational lucky actors prohibitively expensive.
4
2 Preliminaries
2.1 Cryptographic Primitives
Groups. Throughout, G1, G2 will denote elliptic curve groups adorned with an efficiently computable
bilinear pairing ˆe : G1 ×G2 → GT , with GT equal to the multiplicative group of Fq
k for some
prime q, small positive integer k. We further require both G1 and G2 to have prime order r. Let G, H
be fixed generators of G1 whose discrete logarithms relative to each other are unknown (i.e. they are
90 nothing-up-my-sleeve (NUMS) points; G2 does not need any canonical generators. We will make
computational hardness assumptions about these groups as needed. We write Zr for the integers
modulo r, and write + for the group operation in all groups.
All cryptographic schemes will have an implicit GenParams(1
λ
) phase which generates r, G1,
G2, GT , G and H uniformly randomly given a security parameter λ.
2.1.1 Standard Primitives
Definition 1. A commitment scheme is a pair of algorithms Commit(v,r) → G , Open(v,r,C) →
{true,false} such that Open(v,r,Commit(v,r)) accepts for all (v,r) in the domain of Commit. It
must satisfy the following security properties.
• Binding. The scheme is binding if for all (v,r) in the domain of Commit, there is no (v
0
,r
0
) 6=
(v,r) such that Open(v
0
,r
0
100 ,Commit(v,r)) accepts. It is computationally binding if no PPT
algorithm can produce such a (v
0
,r
0
) with nonneglible probability.
• Hiding. The scheme is (perfectly, computationally) hiding if the distribution of Commit(v,r)
for uniformly random r is (equal, computationally indistinguishable) for different values of v.
Definition 2. We define a homomorphic commitment scheme as one for which there is a group
operations on commitments and Commit is homomorphic in its value parameter. That is, one where
commitments to v, v0
can be added to obtain a commitment to v + v
0 having the same security
properties.
Example 1. Define a Pedersen commitment as the following scheme: Commit : Z
2
r → G maps (v,r)
to vH +rG, and Open : Z
2
r ×G → {true,false} checks that Commit(v,r) equals vH +rG.
110 If the discrete logarithm problem in G is hard, then this is a computationally binding, perfectly
hiding homomorphic commitment scheme[Ped01].
Definition 3. Given a homomorphic encryption C, we define a rangeproof on C as a cryptographic
proof that the committed value of C lies in some given range [a,b]. We further require that rangeproofs
are zero-knowledge proofs of knowledge (zkPoK) of the opening information of the commitments.
Unless otherwise stated, rangeproofs will commit to the range [0,2
n
] where n is small enough
that no practical amount of commitments can be summed to produce an overflow.
We may use, for example, the rangeproofs described in [Max15] for Pedersen commitments,
which satisfy these criteria.
5
120 2.1.2 Sinking Signatures
This brings us to the first new primitive needed for Mimblewimble.
Definition 4. We define a sinking signature as the following collection of algorithms:
• Setup(1
λ
) outputs a keypair (sk,pk);
• Sign(sk,h) takes a secret key sk and nonnegative integer “height” h which is polynomial in
λ, and outputs a signature s.
• Verify(pk,h,s) takes a public key pk and signature s and outputs from {true,false}.
satisfying the following security and correctness properties:
• Correctness. For all polynomial h, (sk,pk) ← Setup(1
λ
), s ← Sign(sk,h), we have that
Verify(pk,h,s) accepts.
• Security. Let (·,pk) ← Setup(1
λ
130 ). Then given pk and an oracle H which given h returns
Sign(sk,h), no PPT algorithm A can produce a pair (s,h
0
) with h0 > h for all h given to the
oracle, and Verify(pk,h
0
,s) accepts. (Except with negligible probability.)
The name “sinking signature” is motivated by the fact that given a signature s on height h, it
may be possible for a forger to create a signature s
0 on height h
0 with the same public key and h
0 ≤ h,
thus “decreasing the height” of the signature. We will use this feature later to aid scalability for a
Mimblewimble chain.
Definition 5. We say a sinking signature is aggregatable or summable if given a a linear combination
pk of pki
values computed from Setup(1
λ
), the same linear combination of si ← Sign(ski
,h)
(for fixed h) it is possible to compute a signature s such that Verify(pk,h,s) accepts.
140 For a summable sinking signature, we generalize the above security game to allow the adversary
A to play polynomially many times in parallel and win with an arbitrary linear combination of its
received public keys. (It must also provide the coefficients of the linear combination.)
Definition 6. We propose the following summable sinking signature (Poelstra, Kulkarni). Let H2
be a random oracle hash with values in G2.
• Setup(1
λ
) chooses a uniformly random sk ← Zr and sets pk = sk ·G.
• Sign(sk, x) first computes the sequence {x0,..., xn} where x0 = x and xi+1 is obtained by
subtracting from xi
the largest power of 2 that divides it (i.e., by clearing its least significant
1 bit). We observe that xn = 0 and that n is one plus the number of one bits in x and is
therefore O(log2
x).
Finally, it outputs s = {sk ·H2(xi}
n
i=0
150 .
• Verify(pk, x,{si}) computes S as the sum of all si
, computes H = ∑
n
i=0H2(xi), and checks
that e(G,S) = e(pk,H).
6
Observe that the verification step uses only the sum S of the elements of the signature. However,
the extra data will be useful later, so we state it here so we can prove the scheme is secure with it.
Correctness and summability of the scheme are immediate.
Theorem 1. This is a secure summable sinking signature, in the following sense: if an adversary
A exists which wins the game described in Definition 5, a simulator B exists which can solve the
computational co-Diffie-Hellman (co-CDH) problem for (G2,G1), given oracle access to A .
Proof. B answers random oracle queries to H and works in the following way. (Recall that the
160 game in Definition 5 is the game from Definition 4 played in parallel.)
We suppose without loss that before making signature queries on any height x, the adversary first
all random oracle queries needed to verify such a signature; similarly before producing a forgery on
height x
∗
it makes the required queries. We then suppose that in total it requests at most qp public
keys and makes at most qh random oracle queries.
1. B receives a co-CDH challenge (G,P,Q) from its challenger, where G,P ∈ G1, Q ∈ G2, and
the goal is to produce R ∈ G2 such that ˆe(P,Q) = eˆ(G,R).
2. B responds to the ith public key request by generating a uniformly random keypair (xi
,Pi)
and replies with Pi +P.
3. B responds to the jth random oracle query by generating a uniformly random keypair (y j
,Hj)
except that Hj
∗ = Q for j
∗
$←− {1,...,qh}, and replying with Hi
170 .
4. B responds to the kth signature query on height h
k
and pubkey P
k
as follows: it computes
the sequence {h
k
n} and checks if any of the H(h
k
n
) values is Q; if so, it aborts.
Otherwise, for each i{0,...,n} it knows a zi such that H(h
k
i
) = ziG and produces s = {ziP}i
.
5. Finally, A wins by producing a forgery consisting of coefficients {ci}
m
i=1 with not all ci zero,
a pubkey P
∗ = ∑
m
i=1
ci(Pi+P), a height h
∗ greater than any h
∗
thus queried on, and a signature
s
∗ = {Si} such that ∑
n
∗
i=0
e(G,Si) = ∑
n
∗
i=0
e(P
∗
,H(h
∗
i
)).
6. If some H(h
∗
i
∗ ) = Q, then for the above sum to hold, writing x
∗
for P
∗ = x
∗G, we must have
n
∗
∑
i=0
Si =
n
∗
∑
i=0
y
∗
i P
∗
for y
∗
i
such that H(h
∗
i
) = y
∗
i G
=
n
∗
∑
i=0
m
∑
j=1
[cjxjy
∗
i G+cjy
∗
i P]
=
n
∗
∑
i=0
m
∑
j=1
[cjxjH(h
∗
i
) +cjy
∗
i P]
=
m
∑
j=1
cjR+
n
∗
∑
i=0
i6=i
∗
m
∑
j=1
[cjxjH(h
∗
i
) +cjy
∗
i P]
where R is the solution to B’s CDH challenge, and every other term is computable by B.
7
To complete the proof, we must show that we abort with probability bounded away from 1,
and that our win condition occurs with nonneglible probability. We observe that we only abort if
180 the attacker asks for a signature that requires Q be used, and we win if Q is used in the attacker’s
forgery.
Both occur if H(h
∗
) = Q, which has probability 1/qh, which completes the proof.
2.2 Mimblewimble Primitives
Definition 7. A Mimblewimble transaction is the following data:
• A list of homomorphic commitments termed the inputs, with attached rangeproofs. Alternately,
inputs may be given as explicit amounts, in which case they are treated as homomorphic
commitments to the given amount with zero blinding factor.
• A list of homomorphic commitments termed the outputs, with attached rangeproofs.
• A blockheight x.
190 • An excess commitment to zero, with a summable sinking signature on blockheight x with this
as pubkey.
We make the further restriction on transactions that every input within a transaction be unique.
Definition 8. We define the sum of a transaction to be its outputs minus its inputs, plus its excess.
If
• the sum is zero4
, and
• the rangeproofs and sinking signature are valid
then we say the transaction is valid.
Definition 9. We define the canonical form of a transaction T as the transaction equal to T except
if any input is equal to an output, both are removed.
200 Notice that the canonical form of any transaction has equal sum to the original transaction; in
particular a transaction is valid if and only if its canonical form is valid.
We observe that all valid transactions are noninflationary; the total output value must be equal
to the total input value.
Definition 10. Given a finite set of transactions {Ti} with pairwise disjoint input sets, we define the
cut-through of {Ti} as the canonical form of the union of all Ti’s.
Next, we define some terms that will allow us to treat Mimblewimble transactions as mechanisms
for the transfer of value within a blockchain.
Definition 11. (Ownership.) We say that a party S owns a set of transaction outputs if she knows
the opening of the sum of the outputs.
4By zero we mean the homomorphic commitment which commits to zero with zero blinding factor.
8
210 Definition 12. (Sending n coins.) To send n coins from S to R, S produces a transaction: chooses
inputs, creates uniformly random change output(s) and a uniformly random excess, whose sum is a
commitment to n. S sends this to R along with the opening information of the sum.
Definition 13. (Receiving n coins.) To receive n coins, R receives a transaction T0 which sums to a
commitment of m ≥ n coins, along with opening information of this sum, and completes it to a valid
transaction T by the following process:
1. R first produces uniformly random outputs whose total committed value is n, and adds these
to the transaction.
2. If m = n, R negates the sum of this transaction and adds it to the excess of the transaction, so
that the total sum is now zero. (It also computes a summable sinking signature for the amount
220 added, and adds this to the original signature, so that the final excess has a valid signature
on it.)
Otherwise the transaction now has sum committing to m−n, so R adds a uniformly random
value to excess, updates the signature, and gives the opening information of the new sum to
another recipient who can take the remaining value.
When we define a blockchain and require transaction inputs to be outputs of earlier transactions,
we will show that after this process, R is the only party who owns any of the outputs that he added.
3 The Mimblewimble Payment System
3.1 Fundamental Theorem
Theorem 2. (Fundamental Theorem of Mimblewimble) Suppose we have a binding, hiding ho-
230 momorphic commitment scheme. Then no algorithm A can win at the following game against a
challenger C except with negligible probability:
1. (Setup.) C computes a finite list L of uniformly random homomorphic commitments. C sends
L to A .
2. (Challenge.) At most polynomially many times, A selects some (integer) linear combination
Ti of L and requests the opening of this combination from C . C obliges.
3. (Forgery.) A then chooses a new linear combination T which is not a linear combination of
{Ti} and reveals the opening information of T .
Proof. Consider the lattice Λ of formal linear combinations generated by L, that is, the set {∑A∈L bAA :
bA ∈ Z}. Consider the quotient lattice Λ/Γ where Γ is the sublattice of Λ generated by the queries
240 {Ti}. We may consider every element of Λ/Γ to be a homomorphic commitment by using some
canonical representative. In particular, every element of Λ/Γ is a homomorphic commitment which
satisfies the same hiding/blinding properties that the original scheme did.
9
Then the projection of every {Ti} into Λ/Γ is zero, and the projection of T is nonzero. Therefore
A has learned no information about the projection of T from its queries; however, if A knows the
opening of T then it also knows the opening of the projection of T, contradicting the hiding property
of the homomorphic commitment scheme.
3.2 The Blockchain
Mimblewimble consists of a blockchain, which is a weighted-vertex directed rooted tree of blocks
(defined below) for which the highest-weighted path is termed the consensus history.
250 Definition 14. We define a Mimblewimble block as the following data:
• A canonical transaction, whose inputs are of one of the two forms:
– A reference to an output of the transaction in an earlier block; or
– An explicit (i.e. with zero blinding factor) input restricted by rules above those given in
this paper5
.
• A block header, which has a binding commitment to earlier blocks in the chain, termed backlinks;
a commitment to the current UTXO set after this block’s transaction has taken effect;
and the transaction included in this block.
If the block’s transaction is valid, we say the block is valid.
In Section 3.3, we will describe how blocks are weighted, and which previous blocks specifically
260 should be linked to. For now we may use Definition 14 as our definition of validity, though note
that there will be additional requirements on the commitments.
Definition 15. We define the consensus chain state of a Mimblewimble blockchain as the cutthrough
of all transactions on the consensus history.
If the consensus chain state is valid, we call the blockchain valid.
Note that for a blockchain to be valid, it is not required that all blocks be valid, only that the
entire chain sum to a valid transaction.
Next, we prove that Mimblewimble is a sound payment system, in the sense of the following
two theorems.
Theorem 3. (No inflation.) The total value committed by the outputs of the consensus chainstate of
270 a valid blockchain is equal to the value of the explicit inputs in each block.
Proof. By hypothesis the consensus chain state, which is the canonical form of the cut-through of
all transactions, is valid. Since every non-explicit input of every block is the output of a previous
transaction, it does not appear in this canonical form. Therefore the only inputs of the chain state
are the explicit ones.
5A typical rule would be that each block can have only a single coinbase input of fixed value.
10
Lemma 1. (Unique ownership.) Suppose that all outputs of a transaction were created by receiving
coins as in Definition 13 or sending as in Definition 12, so that all blinding factors are kept secret.
Then for every subset of outputs in which not all have not been sent, the only owner of that subset
is the person who created all its outputs. (In particular, if the subset contains outputs created by
different parties, then that subset has no owner.)
280 Proof. Let O be an output in the subset which has not been sent. Then the only combination of
outputs containing O whose commitment included O that may have been revealed also included
some uniformly random excess E which was chosen when O was created.
Further no other sum containing E was ever revealed, so that any combination including O but
not E is not a linear combination of combinations whose opening information has been revealed.
The subset in question does not contain E, since E is an excess not an output. Therefore by Theorem
2 nobody knows the opening information of the subset except the person who created O.
Theorem 4. (No theft.) Consider a valid blockchain. An output x created as in Definition 13
cannot be removed from the consensus chain state without replacing the block in which it appeared,
i.e., forming a higher-weighted valid blockchain not containing this block, except by parties who
290 (collectively) own a set U of outputs containing x.
Proof. Suppose otherwise; then there exists a higher-weighted chain containing the block B in
which x appeared, but for which the consensus chain state does not contain x.
Consider the transaction T which is the canonical form of the cut-through of the first block after
B to the tip of the chain. (Note that T may not be valid; we know only that the full chain states are
valid.)
Then the outputs of T are a subset of the outputs of the new chain state; in particular they contain
rangeproofs which are proofs of knowledge of the openings of the outputs. Similarly, the excess
value is also known. We conclude that the parties who created these blocks (and therefore T) know
the openings of all outputs and sum of the excess value, and therefore own the set of all inputs of T.
300 However, the inputs of T form a set of outputs containing x, completing the proof.
3.3 Consensus
Mimblewimble uses a hashcash[Bac02] style blockchain in which every block in a blockchain is
labelled by a weight called its difficulty. A blockchain is valid if every block of difficulty D has a
header which hashes into a range of size 1/D of the total space of hashes. We define a directed edge
from block A to B iff A commits to B in its header, and require each block commit to its unique
parent.
We can then refine our definition in Section 3.2 of consensus history as the highest-weighted
path terminating at the root. This is the same as Bitcoin’s design.
3.3.1 Block Headers
310 However, in we also define a second graph structure on blocks as vertices, called the compact
blockchain. We define the compact blockchain iteratively as follows.
11
1. The genesis block is in the compact blockchain.
2. The first block after the genesis is added to the compact blockchain, and is assigned effective
difficulty equal to its difficulty.
3. Each new block is added to the tip of the compact blockchain, and may cause blocks to be
removed from the compact chain as follows:
(a) First, its effective difficulty is calculated as follows. Consider the “maximum possible
difficulty” M of the block, which is the size of the hash space divided by the hash of the
block. (This may be larger than the actual difficulty.)
320 The effective difficulty is determined by starting with the block’s difficulty, then adding
the effective difficulties of as many consecutive blocks as possible, starting from the tip,
so that the total is less than or equal to M.
(b) All blocks whose effective difficulty was used in the above calculation, except the new
block itself, are dropped from the compact chain.
The compact blockchain is encoded in the real blockchain by having every block commit to a merkle
sum tree (with effective difficulty the quantity being summed) of all blocks in the current compact
chain.
We next prove several theorems to give an intuition of the properties of the compact blockchain.
Lemma 2. The expected work required to produce a block with effective difficulty D is equivalent to
computing D hashes; similarly to produce several blocks with total effective difficulty D0
330 one must
do expected work of computing D0 hashes.
Proof. This is immediate in the random oracle model.
Theorem 5. The expected amount of work to replace a block B in the compact chain (i.e. produce
a blockchain of greater or equal total difficulty whose compact chain does not contain B) is greater
than or equal to the work needed to replace B, its parent in the non-compact chain, its parent, and
so on, up to but not including B’s parent in the compact chain.
Proof. This follows immediately from Lemma 2 and the fact that the effective difficulty of every
block is defined to be greater than or equal to the sum of the difficulty of the skipped blocks.
Corallary 1. The expected work required to produce a compact blockchain is at least as large as
340 the expected work required to produce a full chain containing the same blocks.
Theorem 6. Assuming constant difficulty, given a blockchain of length N, the expected length of
the compact chain will be O(logN).
Proof. The compact chain has been defined such that the proof in [BCD+14, Appendix A] still
holds. We summarize it here:
12
1. First, consider starting from the tip and scanning backward until we find a block that can skip
all remaining blocks back to the genesis. By construction this block will be in the compact
chain. The probability that such a block exists within the first x blocks we check is
1−
x
∏
i=1
N −i
N −i+1
= 1−
N −x
N
=
x
N
and the expectation of this over all 1 ≤ x ≤ N is N+1
2
, i.e. we expect the chain length to be
halved by this one skip.
350 2. Inductively, we can scan back from the tip until we find a block that skips back to the block
in the previous step. This halves (in expectation) the remaining chain, and so on.
The number of times we repeat this process until we have no more blocks to skip is the length of
the compact chain, since each step added one more block to the compact chain, and since each step
halved the number of remaining blocks, we see that there are only logarithmically many steps.
We observe that small variations in difficulty do not affect the character of this proof, and therefore
the constant-difficulty case can be considered a good approximation to the real-world situation.
Theorem 7. Given a blockchain B (for the purpose of this theorem, we considering B to be only the
most-work path), there is exactly one compact chain C ⊆ B. Further, verifiers can determine that
that C is the compact chain given only the blocks of C and the opening of each block’s commitment
360 to the previous in the compact chain. Finally, no blocks in B\C will appear in the compact chain
of any extension of B (i.e. once a block is dropped it may be forgotten forever).
Proof. By construction, a compact chain C exists which is a subset of B. Suppose that some other
compact chain C
0 6= C of B also exists. Let C← be the longest path from the tip contained in both
C
0
and C (since the tip itself is in both C
0
and C by construction, this is nonempty), and let β be the
deepest block of C←.
Now, the block preceding β must differ in C and C; however, this is impossible since β commits
to an ordered Merkle sum tree of previous blocks in the compact chain, the “preceding block” must
be the first one that β’s hash is not small enough to skip, and this is uniquely specified by the shape
of the Merkle sum tree. We conclude that C
0 = C.
370 Next, we argue that when B is extended, no blocks of B\C are added to the compact chain. But
this is immediate, since by construction only new blocks are ever added to a compact chain.
3.3.2 Proven and Expected Work
However, while the expected work can be computed to be the same, the the compact chain does not,
in general, prove as much work as the full chain. Here by “proving an amount of work” we mean
that a prover who does less than this amount of work has negligible chance of producing the chain.
For example, consider a blockchain of total difficulty D across n blocks, whose compact chain has
logn blocks.
Suppose an attacker attempts to produce this chain in εD work, where 0 < ε < 1. Then this
requires, on average, that each individual block be produced in ε the expected time. Each block’s
13
380 production time is an independent variable, so the Chernoff bound lets us approximate this more
precisely: if ε < 1 then the probability decays exponentially with the number of blocks in the chain.
For the full chain this means probability O(exp[(1 − ε)n]) (exponential in n); for the compact
chain O(exp[(1−ε)logn]) or O(n
1−ε
) (sublinear in n). In fact, the extreme case is even worse: a
compact chain may consist of only a single block which has difficulty D, in which case the probability
is simply O(exp(1−ε)). This means an attacker willing to expend some fixed percentage of
the total chain work has the same probability of successfully rewriting the chain regardless of the
length of the chain.
To be conservative, we conclude that compact chains, as described in this paper, prove no
work.6
.
390 So what good are they? In Mimblewimble, we expect verifiers of a chain to demand all blocks
from the most recent two months, say, and a compact chain from there to the start (in Section 3.3.3
we will see how full verification can proceed using only a compact chain). The resulting composite
will:
• be forgeable with expected work equal to the entire chain’s work; but
• only prove the most recent two months of work
Unlike Bitcoin, where the expected work to forge a blockchain is the same (asymptotically) to its
proven work, in Mimblewimble these quantities are different. The expected work affects incentives:
rational actors will choose to extend the most-work chain rather than attempting forgeries, just as in
Bitcoin; on the other hand, the proven work affects verifiers’ certainty about the state of the world:
400 they know at least two months worth of work has been done to produce the chain they see, that it
was not an accident, and that if it is a forgery it was a very expensive one that cannot be reliably
repeated.
3.3.3 Sinking Signatures and Compact Chains
In this section, we describe how sinking signatures interact with compact chains, and in particular
we find that it is possible to do a full Mimblewimble verification with only a compact chain. We
introduce a notion of compact validity of blocks which which is weaker than validity as described
in in Definition 14. Nonetheless, we preserve the trust model of Section 1.2.
To do this, we modify the Merkle sum tree of previous blocks and their effective difficulty to
sum not only difficulty, but (a) the excess of the blocks’ transactions (Definition 7), (b) the sinking
410 signatures on this excess. The excess values are summed in the obvious way, added as points, but
the sinking signatures are more complicated.
Rather than directly adding the signatures, we combine sets of signatures from each child at
every node of the Merkle tree, in the following fashion: for any blockheight x, let {xn} denote the
decreasing sequence defined in Definition 6. Then the signature set on a node is the union of the
signature set of its children, except that whenever two heights x < y appear in the set such that
6This says nothing about the compact SPV proofs described in, e.g. [KLS16], which put lower bounds on the length of
compact proofs in order to upper-bound the probability a less-than-expected-work attacker can succeed. We cannot take this
approach because we are using these proofs in consensus code and therefore need Theorem 7.
14
{xn} ⊆ {yn}, then both signatures are dropped and replaced by the signature on {xn} obtained by
adding the corresponding components of the original signature.
Therefore for a block at height h, the root of the Merkle sum tree committing to its ancestor
blocks will have O(logh) sinking signatures, one for every power of 2 between 0 and h.
420 With this structure in place, we are able to define validity of a block.
Definition 16. A block is compact valid if
• It is valid in the sense of Definition 14.
• Its Merkle sum tree commits to the deepest block allowable under the rules of Section 3.3.1.
• This commitment is valid, in the sense that all the summing rules are obeyed.
• The above commitment will be a Merkle proof consisting of a path from the commitment to
the Merkle root of the form {ci
, c
0
i
} where c0 is a direct commitment to the block; for all i c0
i
is the sibling in the Merkle tree of ci; and ci+1 is a commitment to {ci
, c
0
i
}.
We require the first c0
i
that is a right sibling in the tree to have a valid set of sinking signatures
on it. (If there is no such c0
i
then this block is skipping back to the genesis, so we instead
430 require that all the signatures at the root of the tree are correct.)
Definition 17. A block is fully valid if it is compact valid and
• It commits to its immediate predecessor in the full chain (and the excess/signature committed
to in the tree match the previous block).
• It has a valid commitment to the current UTXO set at the time of its creation.
(The latter condition allows the UTXO set to be verified using only the compact chain; it also
prevents consensus attacks whereby users are given the same chain but differing UTXO sets that
it commits to. The former condition ensures that compact blocks’ contents don’t differ from full
blocks’ contents, as long as full verifiers are watching.) (And if nobody is watching, it’s a moot
point anyway.)
440 The conditions of Definition 16 are very technical. We can summarize them simply as follows:
whenever a block at height h skips back to h0
, we sink the signatures of every intervening block to
the lowest height greater than h0 possible, then aggregate all the signatures that wound up on the
same height. This mess of Merkle sum trees is only to show how this condition can be checked by
a verifier given only polylogarithmically much data.
We argue that this design preserves the trust model. In particular:
Theorem 8. No transaction can be removed without (doing as much work as) rewriting the block
it appeared in.
Proof. Every transaction has a sinking signature on the height h of the block it appears in. When a
block is removed from the compact chain, the above construction may cause this signature to only
be verified after being sunk to some lower height h
0
450 .
15
However, since h
0
is always guaranteed to lay between the same two blocks in the compact
chain that h does, this signature cannot be removed except be rewriting the more recent of these
two blocks. However, by construction, this has expected work greater than or equal to rewriting the
block that the transaction originally appeared in.
Theorem 9. The commitments required by Definition 16 take O(log3
) space in the height of the full
chain.
Proof. The commitment contains logarithmically many nodes from the Merkle tree, each of which
contain logarithmically many sinking signatures, each of them are logarithmic in size.
4 Extensions and Future Research
460 Multisignature Outputs. We observe that CT rangeproofs can be produced interactively in the
same ways that Schnorr signatures can to produce multisignature outputs. Similarly the sinking
signatures can be trivially produced in a multiparty way. So support for multiparty signatures, while
not addressed in this article, is simply a matter of wallet support and requires no further changes to
the system.
Payment channels. Bitcoin’s script system supports off-chain payment channels, which are used
by the Lightning network[PD16] to support unlimited transaction capacity in constant blockchain
space. A scaling-focused blockchain design such as Mimblewimble ought to support such a scheme.
It is an open problem to produce payment channels that are as ergonomic and flexible as those in
Bitcoin, but to show that this ought to be possible, here is an example of a primitive Mimblewimble
470 payment channel. Suppose that a party A wants to send a series of payments to party B of maximum
value V.
1. First A creates a spend of V coins to a multisignature output requiring both A’s and B’s
signature to sign. A “timelocks” this by taking the highest 0 bit i in the current blockheight
h, then asking B to sign a transaction with height h+2
i
returning the coins to A. Only after
receiving this signature, A publishes the spend.
The signing signature construction ensures that such a refund transaction cannot be spent in
any block between h and h+2
i
. On the other hand, this means that if A wants a locktime of
2
i blocks he must wait for a blockheight that is a multiple of 2i+1
to create it.
2. Now that all V coins are in a multisignature output requiring both A’s and B’s signatures to
spend (with the coins going back to A after 2i
480 blocks in case of stall), A can send an amount
v to B by signing a transaction from this output sending v to B and (V −n) to A.
3. To increase the value v, A simply signs a new transaction with the new value v. B will not
sign and publish until the channel is near-closing, at which point B can publish one transaction
taking the whole value v, even if it was actually produced over the course of many
interactions.
16
Sidechain support. If Mimblewimble blocks commit to a structure containing all peg-in transactions
and all peg-out transactions (in the same way they commit to the UTXO set, except these
structures will never shrink), then it is possible for Mimblewimble to be implemented as a pegged
sidechain. This would provide a tremendous scaling benefit to its parent chain, since most blockchain
490 transactions are of the simple transfer-of-value sort that Mimblewimble supports, and also reduce
the risk to users of Mimblewimble from quantum computers, since it is easy to move coins off of a
sidechain.
On a technical level, both peg-ins and peg-outs may look like transaction excess values which,
instead of signing blockheights, sign an output on the destination chain. Then verifiers add this
excess plus as ±vH to the total utxoset value (where v is the value of the output).
Working out the details of this, and arguing security, is left as future research, but it appears on
a high-level that there are no open problems.
Quantum resistance. Since Mimblewimble depends on the discrete logarithm problem for security
against theft and inflation, it is highly susceptible to attacks by quantum computers. Find-
500 ing quantum-secure analogues to the primitives used in this paper would allow a quantum-secure
Mimblewimble with the same asymptotic scaling properties of the original. Some research in this
direction includes:
• Pedersen commitments can be replaced by a quantum analogue such as [CDG+15]. Note that
these commitments are not homomorphic in the strong sense of allowing arbitrarily many
commitments to be added, since after a fixed noise threshold the commitments will no longer
open — however, this is not a problem since Mimblewimble only requires that (unmerged)
transactions sum to (a non-hiding) commitment to zero.
• Sinking signatures can likely be replaced by a LWE-based candidate, or a variation of the
NIZK proof-of-openings given in the above paper. The only interesting property required of
510 these is that signatures on same value can be added to form multisignatures, which should be
algebraically easy to obtain.
• The author is unaware of any quantum-secure rangeproofs.
• The blockchain commitments, being based on hashes, are already quantum secure, and the
compact chain arguments go through unchanged.
5 Acknowledgements
The author would like to thank
• Avi Kulkarni for developing the sinking signature construction described in the paper (and
breaking the author’s original construction).
• Gregory Sanders for asking probing questions about Mimblewimble’s guarantees until a clear
520 picture of its consensus structure appeared.
17
References
[Bac02] A. Back, Hashcash — a denial of service counter-measure, 2002, http://hashcash.
org/papers/hashcash.pdf.
[BCD+14] A. Back, M. Corallo, L. Dashjr, M. Friedenbach, G. Maxwell, A. Miller, A. Poelstra,
J. Timon, and P. Wuille, ´ Enabling blockchain innovations with pegged sidechains,
2014, https://www.blockstream.com/sidechains.pdf.
[CDG+15] D. Cabarcas, D. Demirel, F. Gopfert, J. Lancrenon, and T. Wunderer, ¨ An unconditionally
hiding and long-term binding post-quantum commitment scheme, Cryptology
ePrint Archive, Report 2015/628, 2015, http://eprint.iacr.org/2015/628.
[Jed16] T.E. Jedusor, Mimblewimble, 2016, Defunct hidden service, http:
//5pdcbgndmprm4wud.onion/mimblewimble.txt. Reddit discussion at
https://www.reddit.com/r/Bitcoin/comments/4vub3y/mimblewimble_
noninteractive_coinjoin_and_better/.
[KLS16] A. Kiayias, N. Lamprou, and A.-P. Stouka, Proofs of proofs of work with sublinear
complexity, Financial Cryptography and Data Security: FC 2016 International Workshops,
BITCOIN, VOTING, and WAHC, Christ Church, Barbados, February 26, 2016,
Revised Selected Papers (Berlin, Heidelberg) (J. Clark, S. Meiklejohn, Y.A.P. Ryan,
D. Wallach, M. Brenner, and K. Rohloff, eds.), Springer Berlin Heidelberg, 2016,
pp. 61–78.
[Max13a] G. Maxwell, CoinJoin: Bitcoin privacy for the real world, 2013, BitcoinTalk post,
https://bitcointalk.org/index.php?topic=279249.0.
[Max13b] , Transaction cut-through, 2013, BitcoinTalk post, https://bitcointalk.
org/index.php?topic=281848.0.
[Max15] , Confidential transactions, 2015, Plain text, https://people.xiph.org/
~greg/confidential_values.txt.
[Max16] , The first successful zero-knowledge contingent payment,
2016, Blog post, https://bitcoincore.org/en/2016/02/26/
zero-knowledge-contingent-payments-announcement/.
[Mou13] Y. M. Mouton, Increasing anonymity in Bitcoin ... (possible alternative to Zerocoin?),
2013, BitcoinTalk post, https://bitcointalk.org/index.php?topic=290971.
[Nak09] S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, 2009, https://www.
bitcoin.org/bitcoin.pdf.
[Nol13] T. Nolan, Re: Alt chains and atomic transfers, https://bitcointalk.org/index.
php?topic=193281.msg2224949#msg2224949, 2013.
18
[PD16] J. Poon and T. Dryja, The bitcoin lightning network, 2016, https://lightning.
network/lightning-network-paper.pdf.
[Ped01] T. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing,
Lecture Notes in Computer Science 576 (2001), 129–140.
19