Skip to main content
Register
Springer Professional
SEARCH
MENU 1 2 3 4
main-content
Top

Hint

Swipe to navigate through the chapters of this book

Published in:
Cover of the book

2015 | OriginalPaper | Chapter

On the Malleability of Bitcoin Transactions

Authors: Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Łukasz Mazurek

Published in: Financial Cryptography and Data Security

Publisher: Springer Berlin Heidelberg

Login to get access
share
SHARE

Abstract

We study the problem of malleability of Bitcoin transactions. Our first two contributions can be summarized as follows:
(i)
we perform practical experiments on Bitcoin that show that it is very easy to maul Bitcoin transactions with high probability, and
 
(ii)
we analyze the behavior of the popular Bitcoin wallets in the situation when their transactions are mauled; we conclude that most of them are to some extend not able to handle this situation correctly.
 
The contributions in points (i) and (ii) are experimental. We also address a more theoretical problem of protecting the Bitcoin distributed contracts against the “malleability” attacks. It is well-known that malleability can pose serious problems in some of those contracts. It concerns mostly the protocols which use a “refund” transaction to withdraw a financial deposit in case the other party interrupts the protocol. Our third contribution is as follows:
(iii)
we show a general method for dealing with the transaction malleability in Bitcoin contracts. In short: this is achieved by creating a malleability-resilient “refund” transaction which does not require any modification of the Bitcoin protocol.
 
next chapter Trends, Tips, Tolls: A Longitudinal Study of Bitcoin Transaction Fees
Footnotes
1
For a short description of Bitcoin and the non-standard transactions see Sect. 2.
 
2
This is because Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) that has the property that for every signature \(\sigma = (r,s) \in \{1,\ldots ,N-1\}^2\) the value \(\sigma ' = (r,N-s)\) is also a valid signature on the same message and with respect to the same key as \(\sigma \).
 
3
An example of such a fork was experienced by the Bitcoin community in March 2013, when it was caused by a bug in a popular mining client software update [11]. Fortunately it was resolved manually, but it is still remembered as one of the moments when Bitcoin was close to collapse.
 
4
The protocol of [3] was secure only under the assumption that the Bitcoin is modified to prevent the malleability attacks.
 
5
In the original Bitcoin documentation this is called “simplified \(T_{x}\)”.
 
6
Technically in Bitcoin \([T_{x}]\) is not directly passed as an argument to \(\pi '_{i}\). We adopt this convention to make the exposition clearer.
 
7
In our experiments we used addresses 13eb7BFXgHeXfxrdDev1ehrBSGVPG6obu8 and 115g32FHp77hQpuuWpw8j8RYKPvxD1AXyP.
 
8
Typical Bitcoin client maintains about 8 connections.
 
9
More precisely it connects to the nodes maintained by mining pools GHash.IO and Eligius.
 
10
In fact, the BitGo administrators reacted to our experiments by contacting us directly.
 
11
The malleability problem occurs in Step 3 when Party \(\mathsf {A}\) generates Tx2 (the contract) which spends Tx1, and then asks \(\mathsf {B}\) to sign it and send it back. This happens before Tx1 is included in the block chain and hence if later the attacker succeeds in posting a mauled version Tx1\('\) of Tx1 on the block chain, then the transaction Tx2 becomes invalid.
 
12
The malleability problem is visible in Step 3, where the refund transaction T2 is created. This transaction depends on the transaction T1 that is not included in the block chain at the time when both parties sign it (in Steps 3 and 4).
 
13
The problem occurs in Steps 4 and 7, where the “refund_bet” and “refund_reveal” transactions are signed before theirs input transactions “bet” and “reveal” are broadcast.
 
14
The problem is visible in Step 2 of the \( Commit \) phase of this protocol (the \( Fuse ^\mathsf {A}\) and \( Fuse ^\mathsf {B}\) transactions are created before their input transaction \( Commit \) appears on the block chain).
 
15
Such transactions are called hash locked in the Bitcoin literature. Notice that having an output script, which requires only preimages and no signatures is not secure, because anyone who notices in the network a transaction trying to redeem such output script learns the preimages and can try to redeem this output script on his own. In our case the output script of the transaction \(T_0\) requires also a signature of A, but we omit it (\(\ldots \)) to simplify the exposition.
 
Literature
1.
2.
3.
Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, Ł.: Fair two-party computations via bitcoin deposits. In: Böhme, R., Brenner, M., Moore, T., Smith, M. (eds.) Financial Cryptography and Data Security. Lecture Notes in Computer Science, pp. 105–121. Springer, Berlin Heidelberg (2014)
4.
Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: 2014 IEEE Symposium on Security and Privacy (SP), May (2014)
5.
6.
Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 421–439. Springer, Heidelberg (2014)
7.
8.
9.
10.
Boldyreva, A., Cash, D., Fischlin, M., Warinschi, B.: Foundations of non-malleable hash and one-way functions. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 524–541. Springer, Heidelberg (2009) CrossRef
11.
12.
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: 34th Annual ACM Symposium on Theory of Computing, pp. 494–503. ACM Press (2002)
13.
Decker, C., Wattenhofer, R.: Bitcoin transaction malleability and mtgox. In: Kutyłowski, M., Vaidya, J. (eds.) ICAIS 2014, Part II. LNCS, vol. 8713, pp. 313–326. Springer, Heidelberg (2014)
14.
Dodis, Y., Wichs, D.: Non-malleable extractors and symmetric key cryptography from weak secrets. In: Mitzenmacher, M. (ed.) 41st Annual ACM Symposium on Theory of Computing, pp. 601–610. ACM Press (2009)
15.
16.
Dziembowski, S., Kazana, T., Obremski, M.: Non-malleable codes from two-source extractors. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 239–257. Springer, Heidelberg (2013) CrossRef
17.
Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system. Consulted 1, 28 (2008)
18.
19.
20.
21.
22.
Metadata
Title
On the Malleability of Bitcoin Transactions
Authors
Marcin Andrychowicz
Stefan Dziembowski
Daniel Malinowski
Łukasz Mazurek
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
Book
Financial Cryptography and Data Security

Print ISBN: 978-3-662-48050-2

Electronic ISBN: 978-3-662-48051-9

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-662-48051-9_1

Premium Partner

Neuer Inhalt
    Image Credits

    Version: 0.2067.0