On the Malleability of Bitcoin Transactions

We study the problem of malleability of Bitcoin transactions. Our first two contributions can be summarized as follows:

1. (i)

   we perform practical experiments on Bitcoin that show that it is very easy to maul Bitcoin transactions with high probability, and

2. (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:

1. (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.

1. 1.

   For a short description of Bitcoin and the non-standard transactions see Sect. 2.

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

   The protocol of [3] was secure only under the assumption that the Bitcoin is modified to prevent the malleability attacks.

5. 5.

   In the original Bitcoin documentation this is called “simplified \(T_{x}\)”.

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

   In our experiments we used addresses 13eb7BFXgHeXfxrdDev1ehrBSGVPG6obu8 and 115g32FHp77hQpuuWpw8j8RYKPvxD1AXyP.

8. 8.

   Typical Bitcoin client maintains about 8 connections.

9. 9.

   More precisely it connects to the nodes maintained by mining pools GHash.IO and Eligius.

10. 10.

    In fact, the BitGo administrators reacted to our experiments by contacting us directly.

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

Authors and Affiliations

1. University of Warsaw, Warsaw, Poland

   Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski & Łukasz Mazurek

Corresponding author

Correspondence to Łukasz Mazurek .

Editors and Affiliations

1. Leibniz Universität, Hannover, Germany

   Michael Brenner

2. Carnegie Mellon University, Pittsburgh, Pennsylvania, USA

   Nicolas Christin

3. Carnegie Mellon University, Pittsburgh, Pennsylvania, USA

   Benjamin Johnson

4. New Jersey Institute of Technology, Newark, New Jersey, USA

   Kurt Rohloff

Reprints and permissions

© 2015 International Financial Cryptography Association

Policies and ethics