This is the accepted version of the journal article: Pérez-Solà, Cristina; Delgado-Segura, Sergi; Navarro-Arribas, Guillermo; [et al.]. «Double-spending prevention for Bitcoin zero-confirmation transactions». International Journal of Information Security, Vol. 18, Issue 4 (August 2019), p. 451-463. DOI 10.1007/s10207-018-0422-4 This version is available at https://ddd.uab.cat/record/280632 under the terms of the license International Journal of Information Security manuscript No. (will be inserted by the editor) Double-Spending Prevention for Bitcoin Zero-Confirmation Transactions Cristina Pérez-Solà B · Sergi Delgado-Segura · Guillermo Navarro-Arribas · Jordi Herrera-Joancomartı́ Received: date / Accepted: date Abstract Zero-confirmation transactions, i.e., trans- spent it passes effectively to the recipients’ hands, dig- actions that have been broadcast but are still pending ital currency tokens can be easily copied and double to be included in the blockchain, have gained attention spent if security mechanisms are not correctly applied. in order to enable fast payments in Bitcoin, shorten- Bitcoin deals with this double spending problem by ing the time for performing payments. Fast payments building an append-only ledger, the blockchain, that is are desirable in certain scenarios, for instance, when replicated in every single Bitcoin full node. The block- buying in vending machines, fast food restaurants, or chain is made of blocks that are stacked on top of withdrawing from an ATM. Despite being quickly prop- each other. Blocks are made of entries, which contain agated through the network, zero-confirmation trans- some source (inputs) and destination (outputs). En- actions are not protected against double-spending at- tries in the blockchain are called transactions, and they tacks, since the double spending protection Bitcoin of- are used to transfer bitcoins between different users, fers relies on the blockchain and, by definition, such typically identified by their Bitcoin addresses. Bitcoin transactions are not yet included in it. In this paper, we transfer is performed by using an unspent output of propose a double-spending prevention mechanism for a previous transaction (UTXO) as the input of a new Bitcoin zero-confirmation transactions. Our proposal is one. Therefore, Bitcoin transactions consume previous based on exploiting the flexibility of the Bitcoin script- outputs and generate new ones. ing language together with a well-known vulnerability Transactions are broadcast over the Bitcoin P2P of the ECDSA signature scheme to discourage attackers network aiming to reach every single node. Nodes will from performing such an attack. validate the correctness of the received transactions and include the correct ones in their mempool. Such vali- Keywords double-spending · Bitcoin · cryptocur- dation includes, among others checks, that the trans- rency · blockchain · ECDSA. action does not claim any spent funds. Finally, every Mathematics Subject Classification (2010) 68M14 valid transaction should be eventually included in a new block. Hence, double spending is prevented once a transaction is part of the blockchain, since it has been proven that no previous transaction spends from the 1 Introduction same outputs, and future transactions will be prevented to do so.1 Double spending, or spending a currency token more However, transactions are not automatically included than once, is the main security issue that digital cur- in blocks. In the time between transaction broadcast- rencies have to deal with. Unlike physical money, where ing and its inclusion, transactions are known as zero- the physical token is hard to copy, and once it has been confirmation transactions, and they are just stored in Department of Information Engineering and Communica- 1 Although it can be argued that Bitcoin transactions are tions, Universitat Autònoma de Barcelona, not final since blockchain forks may always occur, throughout CYBERCAT-Center for Cybersecurity Research of Catalonia this paper, to simplify the discussion, we assume that once a E-mail: {cperez, sdelgado, gnavarro, jherrera}@deic.uab.cat transaction appears in the blockchain it is final. 2 Cristina Pérez-Solà B et al. the mempool of the nodes that have received them. the conclusions and provides guidelines for further re- Therefore, during this time window, different transac- search. tions spending the same outputs can be spread through the Bitcoin P2P network. Having received a transaction spending an unspent 2 State of the art output, the default behaviour of a node will be to store the transaction in his local mempool and drop any other Double spending attacks on zero-confirmation transac- incoming transactions trying to spend from the same tions in Bitcoin were first analyzed by Karame et al. [1, source. However, different nodes could receive different 2]. The authors showed how, with some reasonable as- transactions spending from the same source, and double sumptions and without the need of special computa- spending could be attempted. For instance, suppose two tion nor much network overhead, an attacker has a transactions (tx1 and tx2 ) that spend the same output great probability of succeeding with a double spend- from a previous transaction (tx0 ) are created by an at- ing attack. Moreover, the authors also showed how ba- tacker A. tx1 is used to pay for some goods to B, while sic countermeasures such as waiting a few seconds be- tx2 is used to return the funds to the attacker. In this fore accepting the payment or adding observers that scenario, if A can make B believe that tx1 is the only report back to the payee are not enough on their own transaction spending from tx0 ’s output, but tx2 finally to avoid these type of attacks. Additionally, the authors becomes included in a block, the attack is successful. proposed to modify the Bitcoin protocol rules so that Figure 1 depicts the aforementioned example. nodes forward double spending transactions instead of dropping them. By doing so all nodes may be notified of Notice that only one of the double-spending trans- double spending attempts. However, such a mechanism actions will be included in a block due to the double eases denial of service attacks. Moreover, nodes receiv- spending protection that Bitcoin achieves by design. ing both transactions will not be able to distinguish However, in case tx2 is included in a block, tx1 will be between the original and the double spending one. discarded and the double-spending attack will succeed. The approach of monitoring observers has been im- In this paper, we propose a solution to mitigate the plemented by companies such as GAP600 [3] in order to double spending problem for Bitcoin zero-confirmation provide risk evaluation for accepting zero-confirmation transactions. In our proposal, any single observer who transactions. Nevertheless, the company does not pro- identifies a double spending attempt may take part and vide details regarding the technique used to perform punish the attacker. Moreover, our solution discourages the analysis nor the evaluation. the attacker even to attempt the double-spending, be- Regarding mitigation of double spending attacks, cause doing so makes him risk losing an amount of bit- Decker et al. [4] proposed some other countermeasures coins bigger than the double-spent amount. Our solu- that can reduce the merchant’s likelihood of being de- tion benefits fast-payment scenarios, like in-shop pur- ceived by an attacker: requiring the merchant to be con- chases or trading platforms, where the transfer bitcoin- nected to a large random sample of nodes of the network product/service cannot wait until the transaction is and not accepting incoming connections. By applying confirmed in the blockchain. Finally, although this pa- such countermeasures the merchant ensures that the at- per is focused in Bitcoin transactions for conciseness, a tacker cannot send the transaction directly to him nor similar construction can be developed for other cryp- should be able to identify his neighbours. tocurrencies with zero-confirmation transactions and Other research studies have proven that this kind of based on ECDSA signatures, for instance, Litecoin or attacks was actually possible, and not only was the at- Dogecoin. tacker able to identify the merchant’s neighbours, but The paper is structured as follows. First, Section 2 also to make the merchant connect only to nodes con- reviews the state of the art in double-spending pro- trolled by the attacker [5–7]. tection for fast payment transactions within Bitcoin. Ultimately, none of the proposed countermeasures Then, Section 3 introduces the most important con- forces attackers to stop trying, nor punishes them by cepts about Bitcoin transactions, needed to understand not doing so. However, if some penalty could be applied our contribution. Next, Section 4 explains our proposed to anyone who tries to perform such an attack, and mechanism for discouraging double spending attempts. this penalty could be implemented by any node which Section 5 provides implementation details and Bitcoin detects it (instead of just dropping the transactions), scripts to deploy the proposed scheme. After that, Sec- attackers may be discouraged even to try it. tion 6 analyses the benefits each party obtains when ap- The idea of using penalties to discourage misbe- plying the proposed protocol. Finally, Section 7 presents haviour in protocols on top of cryptocurrencies is not Double-Spending Prevention for Bitcoin Zero-Confirmation Transactions 3 From: A 1 BTC Signed: From: Someone 1 BTC Attacker m Signed: To: B 1 BTC Someone Required to unlock: B’s signature To: A 1 BTC Required to unlock: tx1 A’s signature From: A 1 BTC tx0 Signed: Attacker m To: A 1 BTC Required to unlock: A’s signature tx2 Fig. 1 Double-spending transactions. new [8]. However, recent proposals, such as the Light- The output of a Bitcoin transaction includes two ning network [9], have popularized this approach, that fields. The first one represents the value (in satoshis) is now used in many other systems (e.g. mental poker that the output is holding.2 The second field, named playing [10, 11] or proof-of-space schemes [12]). In such scriptPubKey, defines the conditions to be fulfilled to a way, and alternatively to other works [4], we address spend output. the double spending problem in fast payments by in- Even though transactions within Bitcoin are, in most troducing a penalty for the attacker. cases, bound to Bitcoin addresses (locking conditions) This penalty involves the disclosure of a private key. and redeemed providing digital signatures (unlocking A similar penalty mechanism has also been proposed conditions), the Bitcoin scripting language is flexible in [13] as a generic penalty for parties issuing contra- enough to allow the definition of many other scripts dictory statements. Our proposal presents a simpler so- that encode different conditions under which the out- lution, which does not require the use of additional pro- puts may be spent, as we describe in the next section. tocols other than Bitcoin. 3 Background on Bitcoin transactions 3.1 The Bitcoin scripting language As we have already stated, Bitcoin transactions are the In order to spend a UTXO, the locking conditions spec- tool for value transfer in the Bitcoin protocol. Bitcoin ified by the script in its scriptPubkey field have to be transfer is performed by using an unspent output of met. The fulfilment of these conditions is provided by a previous transaction (UTXO) as the input of a new the values included in the scriptSig field of the in- one. Therefore, Bitcoin transactions consume previous put that spends the UTXO. To evaluate if an input can outputs and generate new ones. spend a corresponding output, the code included in the The input of a Bitcoin transaction is formed, mainly, scriptPubKey is appended to the values included in the by three fields. The two first ones, namely previous scriptSig, and the complete set of instructions is exe- transaction id and previous output index, uniquely iden- cuted. Only if the execution evaluates to true, the input tify the UTXO that is being claimed by the input. The is able to spend the UTXO. Notice that this general ap- third field, identified as scriptSig, provides the condi- proach allows not only to spend UTXO based on digital tions to be met by the transaction to be valid and the signatures but also to create much richer constructions, payment be correctly performed. Such conditions were the so-called smart contracts. defined in the transaction output that is going to be 2 spent. Both conditions, the specification in the output Notice inputs does not contain any value. The whole value of an output is consumed when it is used as an input of a new and the fulfillment in the input, are codified using the transaction. The difference between the amount claimed by Bitcoin scripting language [14], a stack-based language the inputs and the ones specified in the new outputs is the defined in the Bitcoin protocol. fee collected by the miner. 4 Cristina Pérez-Solà B et al. Smart contracts can indeed specify complex condi- Indeed, given two ECDSA signatures that have been tions.3 For instance, besides the popular Pay-to-Public- created using the same k and the same private key, Key-Hash (P2PKH) and the Pay-to-Public-Key (P2PK) sig1 = sig(m1 ) = (r, s1 ) and sig2 = sig(m2 ) = (r, s2 ) outputs where a standard digital signature must be pro- with m1 ̸= m2 , an attacker that obtains m1 , sig1 and vided to spend the UTXO, there exist multi-signature m2 , sig2 may derive the private key d: constructions, where a UTXO is locked under n public keys, and at least m matching signatures must be pro- 1. Recall that, by definition of the signature scheme: vided. Furthermore, even more, general constructions s1 = k −1 (m1 + rd) mod q ⇒ can be deployed using Pay-to-Script-Hash (P2SH) out- ks1 = m1 + rd mod q puts. P2SH outputs encode an ad-hoc set of instructions s2 = k −1 (m2 + rd) mod q ⇒ in the form of a script. The hash of such script is set ks2 = m2 + rd mod q as locking conditions in the scriptPubKey field of an Note that, since r is deterministically created from k output. An input spending such an output must con- and the fixed parameters of the scheme, the r values tain the corresponding script, along with any necessary of both signatures will be the same. data to make the whole script evaluate to true. 2. The attacker learns k by computing k = ms22 −m −s1 . 1 3. The attacker learns the private key d by computing 3.2 Digital signatures on Bitcoin d = s1 k−m r 1 or d = s2 k−m r 2 . Moreover, the leakage of private key information is Digital signatures in Bitcoin are performed with the not only restricted to the case where the exact same k Elliptic Curve Digital Signature Algorithm (ECDSA). values are used, but also to situations when similar k ECDSA has a set of system parameters: an elliptic values are generated [18, 19]. curve field and equation C, a generator G of the elliptic Some Bitcoin wallets adopted deterministic ECDSA curve C, and a prime q which corresponds to the order after this vulnerability was found to affect some Bitcoin of G. The values for these parameters are defined to be transactions [20–22]. In deterministic ECDSA [23] the secp256k1 [15] for Bitcoin. determinism in the algorithm comes precisely from the Let ∗ be the operation of multiplying an elliptic selection of k, which is derived from the message to curve point by a scalar. Given a specific configuration of sign and the private key using an HMAC construction. the parameters and a private key d, the ECDSA signa- In this way, for a fixed message and private key, the ture algorithm over the message m is defined as follows: value k is always the same. The HMAC construction 1. Randomly choose an integer k in [1, q − 1] ensures that the mapping between the message and k 2. (x, y) = k ∗ G appears random from the point of view of an observer 3. r = x mod q that does not know the private key. Key generation and 4. s = k −1 (m + rd) mod q signature validation algorithms remain the same as in 5. If either s or r are 0, go back to step 1. the non-deterministic version of ECDSA. As we will see, 6. Output: sig(m) = (r, s) our proposal can be used both with deterministic and non-deterministic ECDSA. The ECDSA signature scheme is therefore proba- Taking advantage of this vulnerability to perform bilistic, that is, there exist many different valid signa- a private key disclosure in Bitcoin has been previously tures made with the same private key for the same mes- used for timestamping in data commitment schemes by sage. The selection of a specific signature from the set Clark and Essex [24]. of valid ones is determined by the election of the integer k. There exists a well known ECDSA signature vulner- 3.3 Bitcoin transactions propagation ability (also present in the non-elliptic curve signature scheme of ElGamal and its popular variant, DSA [16, As we already pointed out, Bitcoin transactions are 17]) by which an attacker that observes two signatures propagated through a peer to peer network. Every node of different messages made with the same private key is of the network broadcasts the transactions he gener- able to extract the private key if the signer reuses the ates and propagates transactions received from other same k selected on step 1. Therefore, the selection of k network peers. As a protection against denial of ser- is critical to the security of the system. vice attacks, every peer performs different validations on every received transaction before its propagation,4 3 An interested reader could refer to [14] for additional in- 4 formation about Bitcoin smart contracts and script types. See [14] for all the validation details. Double-Spending Prevention for Bitcoin Zero-Confirmation Transactions 5 like data format validation, digital signature verifica- actions (if they know the private key needed to generate tion, or correctness checks over the values involved in a signature). the transaction. Besides such validations, the node also In order to discourage double-spending attacks, we validates that the received transaction does not spend propose a mechanism to construct special transaction an already spent output, either by a transaction already outputs. Such outputs can be spent with a single sig- in the blockchain or by a transaction included in the nature but have the property that if two different sig- node’s mempool. In case that some validation fails, the natures for the same output are disclosed (for instance, node drops the transaction and, therefore, the transac- in two different transactions spending the same output tion is not propagated any further. as a double-spending attack), the private key used to However, since Bitcoin Core 0.12, Bitcoin includes sign the transaction is revealed. This mechanism allows a replace-by-fee mechanism (RBF) that allows trans- any observer to generate a third transaction spending actions to signal replaceability. This mechanism was the same output and sending the amount to an address introduced to allow to increase the fee of an already controlled by himself. broadcast transaction to boost its odds of inclusion in To allow such a construction, we propose a new Bit- the blockchain. Therefore, if a transaction is flagged coin script that we call fixed-r pay-to-pubkey script as replaceable with RBF, it can be replaced from the (FR-P2PK). This script is a variant of the standard node’s mempool by a newer transaction that spends pay-to-pubkey (P2PK) script where a signature is re- the same outputs but includes a higher fee.5 Moreover, quired to redeem, but a FR-P2PK script adds an addi- this new transaction will also be further propagated tional condition to be able to spend the output: the sig- throughout the network, since it is considered a valid nature must be made with a specific r value. Then, due transaction that replaces the previous one. This feature to the ECDSA vulnerability described in Section 3.2, ensures that when a transaction is flagged as a RBF, a this particular condition discourages double-spending double spending transaction of the same UTXO will be of that output. Indeed, if the sender generates another propagated further than a double spending of a regular transaction that spends the same output and propa- (non-RBF) transaction. gates it through the P2P network, the sender risks los- ing all the funds deposited in the address, because any peer that captures both transactions will be able to de- 4 Double-spending prevention mechanism rive the private key. Recall that the value r is computed from the value k as described in Section 3.2, giving a Our proposed scheme discourages signers from perform- one to one correspondence between them. ing double spending attacks in zero-confirmation trans- actions used in fast payment scenarios. Fast payment 4.1 Basic prevention mechanism scenarios are those where the merchant delivers the goods or services when seeing the payment transaction Let Alice be a user that wants to take advantage of the in the Bitcoin network, without waiting for the transac- proposed double-spending prevention mechanism and tion to be confirmed. Examples of such scenarios are on- let {P Ka , SKa } be an ECDSA key pair belonging to site shopping where the buyer cannot wait 10 minutes Alice. to leave the shop after purchase or in trading platforms The double spending prevention mechanism is made where a timely transaction can save/earn you money. of two phases: initialization, that is performed before In our scenario, we assume that the adversary is the the payment is made, and fast-payment, where the pay- buyer that pays for some goods to a merchant, and that ment is executed. may have incentives to try to double-spend the payment in order to finish the interaction with both the goods 4.1.1 Initialization and the payment amount. We assume that he can perform a double-spending The initialization phase is performed beforehand. Dur- attack by generating multiple transactions that spend ing this phase, Alice generates a funding transaction from the same output and broadcast them selectively in that transfers some funds from an output in her con- the Bitcoin P2P network. Additionally, we also assume trol to a FR-P2PK output also under her control. In all peers of the network have the same capabilities, that order to do so, Alice chooses a random integer k and is, they can generate and broadcast double spend trans- a public key P Ka (for which she knows the associated 5 secret key SKa ), constructs the FR-P2PK output, and Notice that this only affects transactions in the mempool, since transactions included in the blockchain are final and sends some funds to an output in her control (see Figure thus not replaceable. 2). 6 Cristina Pérez-Solà B et al. Alice broadcasts the funding transaction and waits for the transaction to be confirmed, upon which the From: Alice σ BTC From: Alice σ BTC Signed: Signed: initialization phase is considered terminated. Alice Alice A single funding transaction may include multiple To: Alice σ BTC (fixed ) Required to unlock: FR-P2PK outputs (with different public keys) in order Alice’s signature To: Bob Required to unlock: σ BTC to allow Alice to use the proposed prevention mecha- (fixed ) Bob’s signature nism multiple times. Therefore, there is no need to per- funding tx fast payment tx form the initialization phase before every fast-payment, as long as Alice has enough funds stored in FR-P2PK Fig. 3 Fast payment transaction. outputs. Alice may repeat the initialization phase if she runs out of unspent FR-P2PK outputs. Additionally, spend the transaction she takes the risk of losing the notice that Alice remains in control of all the funds de- Bitcoins of that output. posited by the funding transaction, and she is able to transfer them back to a standard output whenever she If Alice decides to try to double spend the fast- wants. payment transaction (see Figure 4, double-spending at- tempt), she needs to create a double spending trans- action that also spends the FR-P2PK output of the funding transaction. This double spending transaction From: Alice σ BTC has to be valid, so it needs to include a (second) signa- From: Someone σ BTC Signed: Signed: Alice ture made with SKa and the k value chosen on the ini- Someone To: Alice σ BTC tialization phase. Hence the moment the double spend To: Alice σ BTC Required to unlock: Required to unlock: Alice’s signature transaction is created, there exist two different signa- Alice’s signature (fixed ) tures made with the same private key SKa using the funding tx same r. The signatures will be indeed different since the signed content (i.e. the transactions) will also be Fig. 2 Creation of the funding transaction. different. Recall that, because of the ECDSA vulner- ability mentioned above, knowing two different signa- tures made by the same private key with the same k At some point in the future, Alice wants to send value is enough to derive the private key used to sign. some amount of bitcoins to another user Bob. Alice does As a consequence, if Alice broadcasts the double not want to wait for the confirmation of the transaction spend transaction, she risks losing her funds. This hap- and Bob is not willing to accept the transaction pens because any observer that receives both trans- without confirmation. So they decide to use the pro- actions (the fast-payment transaction and the double- posed double-spending prevention mechanism, execut- spending transaction) will be able to derive Alice’s se- ing the fast-payment phase. cret key SKa and, as a consequence, create a third transaction, the penalty transaction that also spends 4.1.2 Fast payment the FR-P2PK output of the funding transaction but that sends the bitcoins to the observer. Note that this Alice creates a fast-payment transaction that pays to strategy may be performed simultaneously by any ob- Bob spending from the FR-P2PK output of the funding server, ending with multiple penalty transactions, as it transaction. The input script in the fast-payment trans- is depicted in Figure 4. action forces Alice (the redeemer) not only to prove she has the private key SKa associated with the given pub- lic key P Ka by creating a valid signature, but also to 4.2 Disincentive-based prevention mechanism deliver a signature that has been made using the spe- cific k value that Alice chose during the initialization The basic prevention method described in the previ- phase (see Figure 3). Alice broadcasts the fast-payment ous section has a clear drawback. Suppose that Alice transaction to the Bitcoin P2P network. performs a purchase to Bob’s shop and Bob accepts Then, when Bob sees the fast-payment transaction a fast transaction from Alice. When such transaction in his mempool, he can validate that the output script is received, Bob delivers the goods to Alice. However, of the funding transaction spent by the fast payment once Alice has the goods, she may try to perform a transaction is indeed a FR-P2PK script. If the valida- double-spending attack. In case an observer sees both tion is correct, Bob knows that if Alice tries to double the fast-payment transaction and the double-spending Double-Spending Prevention for Bitcoin Zero-Confirmation Transactions 7 From: Alice σ BTC Signed: Alice (fixed ) To: Bob σ BTC Required to unlock: Bob’s signature fast payment tx Double-spending From: Alice σ BTC Signed: From: Alice σ BTC attempt Signed: Alice To: Alice σ BTC Alice Required to unlock: (fixed ) Alice’s signature To: Alice' σ BTC (fixed ) Required to unlock: Alice' ‘s signature funding tx double-spending tx From: Alice (σ * γ) BTC From: Alice σ BTC From: Alice Signed: σ BTC Signed: From: Alice σ BTC Signed: Signed: Alice Alice Alice (fixed ) (fixed Alice ) (fixed ) To: Observer (fixed1 ) (σ * γ) BTC To: Observer 1 (σ * γ) BTC To: Required Observer to unlock: (σ * γ) BTC Required to unlock: 1 To: Observer Required Observer to unlock: 1 σ BTC ’s signature Observer1’s1 signature Required to unlock: Observer ’s signature Observer1’s1 signature penalty txj Fig. 4 Transactions involved in the scheme. transaction, he constructs the penalty transaction, and payment and Alice gets her change back. However, be- manages to get it accepted in the blockchain, Alice loses cause the whole FR-P2PK output is spent, if Alice tries her funds but Bob does not receive the payment. In to double-spend the fast payment she risks losing the that case, Bob may have complied with his part of entire amount of the FR-P2PK output, and not only the agreement (e.g. delivered the bought goods) but the amount paid to Bob. will not receive the agreed amount of bitcoins in ex- As we will discuss in Section 6, by adjusting the λ change. Alice would have paid the agreed amount of factor Alice’s penalty for double-spending can also be bitcoins to a third party (the observer) instead of pay- adjusted (and thus Bob’s confidence on the fast pay- ing them to Bob, but she would remain in possession of ment). the goods. The observer would obtain the total amount Moreover, note that the fast-payment transaction of the transaction. As a consequence, Alice will not lose may also have multiple inputs spending different FR- anything by trying the double-spend (just the amount P2PK outputs which in turn allows Alice to perform she is already willing to pay for it), and thus the pro- payments of different amounts and with varying levels posed method may not be discouraging enough to pre- of penalty without having to freeze a high quantity of vent double spending attempts. bitcoins into FR-P2PK outputs. However, a minor modification to the method may Notice that Bob does not get refunded in case of be enough to discourage Alice from attempting any fraud. The objective of this work to counteract poten- double-spend: enforcing that the amount deposited to tial frauds by penalizing Alice. An alternative approach the FR-P2PK output of the funding transaction is higher to refund Bob could be designed but remains out of the than the paid amount by a certain factor λ. Recall that scope of the current proposal. a Bitcoin UTXO must be spent in its totality (i.e. it is not possible to spend a part of a UTXO). Therefore, if 4.2.1 The role of the observers the FR-P2PK output has an amount bigger than what Alice must pay to Bob, Alice proceeds to create the The funding transaction is confirmed before starting fast-payment transaction including two different out- the fast-payment phase, so any full node of the net- puts: one that pays to Bob the agreed amount, and work is aware of its existence. Moreover, because it has the other that pays back to her the change. This has an output with an easily identifiable script, the FR- no consequences on the normal operation of the proto- P2PK script, any observer aware of the specification of col, that is, if Alice well-behaves, Bob ends up with his our proposed mechanism is able to identify the trans- 8 Cristina Pérez-Solà B et al. action as a funding transaction belonging to our proto- after one of the transactions spending the encapsulated col. Therefore, such an observer will be able to monitor FR-P2PK is seen in the network. This transaction will his mempool, looking for transactions that spend the include the FR-P2PK script in the scriptSig (input FR-P2PK output. Once a transaction spending from script). The moment the observer processes this script, the FR-P2PK output is seen, the observer is able to he can start the active listening period in which he looks actively listen to the network, searching for any other for other transactions spending from the same funding transaction spending the same output. If the observer is transaction output. Because timing is critical in our sce- able to catch a double-spending transaction, he should nario, we argue that using directly a FR-P2PK output be able to construct a penalty transaction, moving the in the funding transaction is the best alternative. funds to an address controlled by himself. If the ob- In a Bitcoin transaction, signatures are represented server does not capture a double spending transaction, by a single hexadecimal value, which corresponds to the he may stop this active listening period and return to DER encoding of the two-element sequence of the r and its normal behaviour when a transaction spending the s integers that make up an ECDSA signature. Figure 5 FR-P2PK output is included in the blockchain. describes the format of a Bitcoin signature. Each inte- To achieve the maximum level of propagation, and ger r and s (see Section 3.2 regarding the notation) is thus to spread awareness of the double-spending at- encoded with three different fields: a 1-byte field with tempt, fast-payment transactions are flagged with replace- the 0x02 flag denoting the integer type, a 1-byte field by-fee (RFB). By forcing a customer to flag a transac- with the size l of the integer (in bytes), and an l-byte tion in such a way a merchant enables the forwarding of field with the integer value itself. Then, the signature future double-spending transactions, that could be de- includes a 1-byte field with a flag denoting a sequence tected by a higher number of nodes, increasing the odds (0x30), a 1-byte field with the length of the sequence, of an observer receiving two instances of the transaction the sequence of the two integers, and finally a 1-byte and, therefore, publishing a punishment transaction. field with the hash type, a flag that indicates the parts Note that even though transactions are flagged with of the transaction that are hashed and signed. RBF, some actors may not have incentives to propagate duplicate transactions. This is the case, for instance, of 30 len(z) 02 len(r) r 02 len(s) s ht hex value miners that are aware of the protocol, that may prefer 1 1 1 1 32-33 1 1 32-33 1 byte length to mine their own penalty transaction instead of prop- Fig. 5 Bitcoin signature format. agating a third-party penalty transaction (after hav- ing sent any of the other transactions). However, many other actors would indeed propagate penalty transac- Both r and s are 32 byte integers. However, when tions, for instance: non-miner observers, that need to the first bit of any of the values is set (that is, the first send their penalty transaction to a miner for inclusion byte is > 0x7f), an additional byte (0x00) is added in in a block; nodes not participating in the protocol (e.g. front of the value, thus making it 33 byte long. The nodes running the standard bitcoin client), that propa- reason is that DER rules interpret this first bit as a gate RBF transactions by default; or nodes just aware sign, and therefore not adding 0x00 would cause the of one of the transactions, that would not even be aware value to be interpreted as negative. Therefore, Bitcoin of which of the transactions it is. signatures range from 71 to 73 bytes. For the sake of simplicity, let us assume that we are dealing with 71- 5 Implementation details byte signatures, that is, signatures where both r and s are 32 byte long (Figure 6a). In this Section, we describe how to construct the FR- Taking into account the format of signatures in Bit- P2PK output of the funding transaction as well as the coin, the script of a FR-P2PK output is defined as fol- inputs of the transactions that spend it, taking into lows: account Bitcoin’s signature format and scripting lan- guage. ScriptPubKey: First of all, notice that it would be possible to en- OP DUP OP CHECKSIGVERIFY capsulate the proposed FR-P2PK script into a standard OP SIZE <0x47> OP EQUALVERIFY P2SH output. However, doing so makes the funding OP AND OP EQUAL transaction no longer recognizable as belonging to our ScriptSig: protocol by external observers. Therefore, an observer that is aware of the existence of our protocol would be able to detect that the mechanism is being used only where Double-Spending Prevention for Bitcoin Zero-Confirmation Transactions 9 – is the public key that will be used to val- terminates with a False value on the stack, making it idate the signature, fail. – is a 71-byte array that has ones in the Note that the only way to ensure that the script positions where r and ht are specified and zeros in succeeds is by providing a valid signature that matches the rest of positions, and the specified . Therefore, two different transactions – is the 71-byte array that represents the integer spending the same FR-P2PK output would include two r in DER format in the positions where it is found different signatures made with the same private key and in a signature, 0x01 in the ht field, and zeros in the the same k, and thus by obtaining the two transactions, rest of positions. one is able to infer the private key that was used to Figures 6b-c show the construction of create the signatures. and , respectively. Regarding the construction of the We have created a funding transaction in the Bit- byte array , on the one hand the integer r is derived coin testnet that exemplifies the proposed prevention uniquely from the randomly chosen k value (recall Step mechanism. Following the transaction naming used in 3 of the ECDSA signature generation algorithm in Sec- Figures 2, 3, and 4, the funding transaction6 contains tion 3.2). Note that any value of k may be used by the output with a FR-P2PK script. The output of the the protocol, what matters is that it is fixed before- funding transaction is currently unspendable due to the hand (that is, before the signature is made). On the fact that it uses an OP AND opcode that is disabled in other hand, the hash flag tag ht is set to 0x01, which the standard Bitcoin software. corresponds to SIGHASH ALL. This flag signals that the signed content corresponds to the entire transaction (except the signature scripts themselves). By enforcing 6 Proposal analysis that signatures cover the entire transaction, we ensure that a double spending attempt will include a signa- In this section, we provide an analysis of the possible ture different from the one found in the fast-payment outcomes of performing a payment with the proposed transaction, and thus that observing both transactions mechanism. The analysis measures the benefits of each indeed allows deriving the private key. party taking part in the system to show how it discour- ages double-spending attacks. Table 1 summarizes the 30 44 02 20 r 02 20 s ht hex value notation used in this section. a) 1 1 1 1 32 1 1 32 1 byte length 00 00 ff ff f · · ·f 00 00 0· · ·0 ff hex value b) 1 1 1 1 32 1 1 32 1 byte length Table 1 Notation summary 00 00 02 20 r 00 00 0· · ·0 01 hex value c) 1 1 1 1 32 1 1 32 1 byte length Symbol Meaning Fig. 6 Values used in the proposed script. τf Fast-payment transaction τd Double-spending transaction τpj Penalty transaction j P r[τx ∈ B] Probability that transaction τx is In order to redeem a FR-P2PK output, the input’s included in the blockchain scriptSig only needs to include a single signature. The σ Payment amount signature must be correct when validated with the spec- λ·σ Funding transaction output amount ified public key and must be performed with a specific γ Value of goods r value. Otherwise, the validation will fail. Let’s analyse how does the script perform these val- idations. First, the script duplicates the signature (with Our analysis makes the follow assumptions. First OP DUP). This is needed in order to be able to per- of all, we assume that Alice always generates the fast form different validations over the same signature value. payment transaction since it is the triggering action for Then, the signature is validated against the specified the payment. Once the fast payment has been gener- public key using the check signature operand ( ated, we assume that Bob sees the payment and, at OP CHECKSIGVERIFY). After that, the length of the sig- that time and acting honestly, he delivers the goods to nature is checked (OP SIZE <0x47> OP EQUALVERIFY). Alice. Furthermore, to focus the analysis in the pro- Finally, a bitwise AND operation between the signature posed mechanism, we assume that at least one of the and is computed (with OP AND), transactions of the system τf , τd , or τpj will be con- and the result is compared with ( OP EQUAL). If firmed. Although transactions do include fees, fees are both values are equal (that is, the signature was made using the specified r and with a hash flag of 0x01), 6 https://www.blocktrail.com/tBTC/tx/8e27cae62d1d the script terminates successfully; otherwise, the script f357b65b634a8482672d85f71804a5c7fc392050517a5bfeb04f 10 Cristina Pérez-Solà B et al. intentionally excluded from the computation of the pay- equilibrium, since Alice pays the specified price for some offs, since they do not directly affect the result of our goods and obtains the goods in exchange; Bob delivers evaluation. The usage of the replace-by-fee mechanism, the goods and gets paid for them, and the observers that will allow the propagation of multiple instances of do not intervene. On the contrary, if Alice tries to dou- the transaction, forces double-spending transactions to ble spend the payment, the equilibrium may be altered include a higher fee than the original transaction. How- and the payoff will reflect the gains or losses each party ever, it could be argued that a higher fee will incentive assumes. miners to mine a double-spending transaction instead Then, Bob’s payoff function PB is given by the fol- of a fast-payment transaction, affecting not only the lowing expression: payoff but also the odds of either succeed or fail in the attack. Nonetheless, if a miner sees two instances of PB = P r[τf ∈ B] · (σ − γ)− the transaction (fast-payment and double-spending) he − P r[τd ∈ B] · γ− would maximize his payoff as an observer by generating − P r[τpj ∈ B] · γ = a third transaction (penalty) that pays all the amount = P r[τf ∈ B] · σ − γ to himself (instead of choosing to include any of the previous ones depending on the fees). Moreover, notice Note that, for fixed σ and γ, Bob’s payoff only de- that our analysis can be seen as an upper-bound on the pends on P r[τf ∈ B]. Recall that our mechanism tries to attacker’s gains since including fees in the computation disincentivize Alice from double-spending the payment only lowers the attacker’s payoff, but never increases it. transaction, but does not directly benefit the merchant Of course, due to the double-spending protection of (regardless of the λ value used by the protocol).8 Bitcoin for on-chain transactions, at most one of these In a similar way, Alice’s payoff PA is given by: transactions gets into the blockchain, that is, the events τf ∈ B, τd ∈ B, and τpj ∈ B are mutually exclusive. Fi- PA = P r[τf ∈ B] · (γ − σ)+ P nally, notice that P r[τf ∈ B]+P r[τd ∈ B]+ j P r[τpj ∈ + P r[τd ∈ B] · (γ)+ B] = 1, since such probabilities depend on the distri- + P r[τpj ∈ B] · (γ − σλ) bution hash rate devoted to the interests of every set of users (Alice, Bob and the rest of the network, acting Alice’s maximum payoff is, therefore, γ, and is ob- as observers) and we can assume that such sets will be tained when Alice’s successfully double spends the trans- disjunct. action, thus keeping the goods γ without paying any- Taking into account these assumptions, in Figure 7 thing. However, Alice’s minimum payoff (that is, max- we have represented how the possible final three states imum losses) depends on λ, a parameter that can be of the protocol we propose may be reached. If the fast adjusted in our protocol. Therefore, by adjusting λ, the payment transaction τf gets confirmed, then Bob re- protocol allows to tune Alice’s losses, and so the risks ceives the payment for the goods, Alice receives the she assumes by trying to perform a double spending change (the amount deposited to the funding transac- attack. The bigger the λ is, the higher the risks Alice’s tion minus the payment) and the goods, and the ob- faces on a double spend attempt. server does not intervene. If the double spending trans- Finally, an observer’s j payoff is given by the ex- action τd is confirmed, then Alice gets everything (the pression: full amount deposited in the funding transaction and the goods) and therefore both Bob and the observers POj = P r[τpj ∈ B] · (σλ) do not obtain anything. Finally, if one of the penalty Figure 8 shows the evolution of the parties payoffs transactions τpj is confirmed, then Alice obtains the as a function of P r[τf ∈ B] and P r[τd ∈ B]9 for the case goods but loses the full deposited amount that goes to where σ = γ (the value of goods is equal to the price it the observer. Figure 7 also describes the possible paths is paid for them), for different values of the parameter that end up in each of the states. λ. The payoff dimension is measured based on the value We define the payoff P of any party participating in the protocol as the gains (or losses) obtained by deviat- B’s payoff is positive and reflects the benefit obtained from the sale. ing from the correct operation of the protocol. That is, the payoff of all parties (Alice, Bob, and the observers) 8 Note, however, that Bob may also act as an observer him- will be 0 when no double spending is attempted (left- self, being able to create a penalty transaction and trying to most box in Figure 7).7 In that case, there will be an gain the observer’s payoff. 9 P Since P r[τf ∈ B] + P r[τd ∈ B] + j P r[τpj ∈ B] = 1, 7 Here we assume that the price of the goods is equal to the fixing the first two probabilities uniquely determines the third value of the goods. If the price paid is higher than the cost, operand. Double-Spending Prevention for Bitcoin Zero-Confirmation Transactions 11 Fig. 7 Diagram showing the protocol’s final states and the paths leading to them. Fig. 8 Parties payoffs for σ = γ. σ. That means that a payoff of 3 implies a benefit of 3 that, as λ increases, Bob’s payoff (first three graphics) times the value of σ while a payoff of −3 implies a lost remains exactly the same since his payoff is indepen- of 3 times the value of σ. The payoff results are thus dent of the parameter λ. On the contrary, Alice’s pay- proportional to σ. off (next three graphics) depends on λ. With λ = 1, The graphics show that, as expected, when there is Alice’s payoff is always positive or zero: Alice does not no double spending attempt (P r[τf ∈ B] = 1) there is lose anything by trying to double spend and may even an equilibrium in the parties’ payoffs, and in all graph- gain something if the attack is successful. That situa- ics we obtain PB = PA = POj = 0 (green zone). Note tion is the basic prevention mechanism described in Sec- 12 Cristina Pérez-Solà B et al. tion 4.1. However, by increasing λ the scenario changes minutes. In order to provide fast payments, one of the radically for Alice: the probabilities range at which Al- alternatives used in these scenarios is to rely on zero- ice gains something from the attack decrease fast and, confirmation transactions, i.e., transactions that have at the same time, for some probability values she even been seen on the network but have not yet been in- starts to get a negative payoff (that is, she has to as- cluded in the blockchain. Experimental analysis have sume losses). Finally, notice that the observer’s payoff shown that, in Bitcoin, most of the transactions prop- (last three graphics) is never negative, and his gains agated through the network reach 75% of the nodes in increase with λ. less than 8 seconds [25], which is two orders of mag- Notice that our analysis does not assume any spe- nitude faster than the block production interval. How- cific values on the probabilities P r[τf ∈ B], P r[τd ∈ B], ever, zero-confirmation transactions are not secured by and P r[τpj ∈ B]. However, as we have already indi- the standard Bitcoin double-spending protection mech- cated, such probabilities depend on the hash distribu- anism, since this mechanism is applied to transactions tion of the Bitcoin network among mining the trans- included in the blockchain and zero-confirmation trans- actions, τf , τd , and τpj . For that reason, in case the actions are not yet in blocks by definition. hash rate devoted to τd with respect the rest is low, In this paper, we have presented a mechanism to the graphics show that Alice’s payoff, for values λ > 1, secure fast payments within Bitcoin by reducing the is moving in the red zone thus being negative (Alice is risk of double-spending attacks in transactions with losing money). The greater the λ value the bigger the zero confirmations. The proposed mechanism discour- red zone. ages double spending attempts by creating a special Providing values for the exact probabilities that pa- type of outputs that enforce private key disclosure in rameterise our analysis is far from trivial because these case of a double-spending attempt. Any Bitcoin net- probabilities are affected by the personal decisions of work user may act as an observer and obtain a reward nodes that participate in the network. These personal by detecting double-spending attempts. The reward the decisions may not even attend to economical incentives observer receives is equal to the price the attacker pays only, but also political or even non-rational ones. That as punishment for having tried to double spend a trans- being said, we can, of course, imagine a specific scenario action and may be fixed by the receiver beforehand. with rational actors and estimate the probabilities for Nevertheless, the attacker may have enough incentive that individual case. For instance, we can assume that to double-spend even when that will likely result in a all miners are aware of the protocol and try to opti- loss for her, but pursuing Bob’s lost, that could be more mize their immediate profit (that is, they would try to damaging. Such scenario may appear when the wealthy obtain the reward of a penalty transaction if they are of the attacker is much higher than the receiver. How- able to do so). Additionally, we can also assume both ever, since our proposal is an optional alternative to the fast payment and the double-spending transactions accept fast payments, Bob may opt-out of using our are propagated to all miners of the network. Then, an system in case his possible loss would be more than he attacker that controls the currently largest mining pool can afford. will have P r[τd ∈ B] = 0.24 (BTC.com has 24.6% of the Further research will be focused on experimentally hash-rate as of today).10 On the other hand, P r[τf ∈ B] testing the proposed approach in a Bitcoin-like P2P will be 0, since no miner would mine the fast-payment network, in order to quantify the probabilities of each transaction (each miner would mine their own penalty transaction entering the blockchain depending on the transaction). For λ = 3, this scenario results in an at- exact capabilities of the attacker (both in terms of net- tacker’s payoff of PA = −1.28σ, while the sum of the work connectivity and hash power) and the percentage of nodes of the network that are aware of the existence P observers payoffs will be ∀j POj = 2.28σ. The second largest pool will be the best observer, with a payoff of of the prevention mechanism. In turn, this would al- PO0 = 0.51σ. low us to better evaluate the risks the merchant is fac- ing with each transaction and to study the overhead of transactions relayed through the network by the usage 7 Conclusions of our protocol. The speed at which payments in blockchain based cryp- tocurrencies can be performed is lower bounded by the block generation interval, which in Bitcoin is fixed to 10 10 https://web.archive.org/web/20180522080137/https: //blockchain.info/pools Double-Spending Prevention for Bitcoin Zero-Confirmation Transactions 13 Compliance with Ethical Standards 17. C. Paar, J. Pelzl, Understanding cryptography: a text- book for students and practitioners (Springer Science & Business Media, 2009) Funding: This work is partially supported by the Span- 18. P.Q. Nguyen, I.E. Shparlinski, Journal of Cryptology ish ministry under grant number TIN2014-55243-P and 15(3), 151 (2002) the Catalan Agència de Gestió d’Ajuts Universitaris i 19. M. Bellare, S. Goldwasser, D. Micciancio, in Annual In- de Recerca (AGAUR) grant 2014SGR-691. ternational Cryptology Conference (Springer, 1997), pp. 277–291 Conflict of Interest: The authors declare that they 20. N. Schneider. Recovering Bitcoin private keys using weak have no conflict of interest. signatures from the blockchain (2013) Ethical approval: This article does not contain any 21. F. Valsorda. Exploiting ECDSA failures in the Bitcoin studies with human participants or animals performed blockchain (2014) 22. Bitcoin.org. Android security vulnerability (2013). URL by any of the authors. https://bitcoin.org/en/alert/2013-08-11-android 23. T. Pornin. Deterministic usage of the digital signature algorithm (DSA) and elliptic curve digital signature algo- rithm (ECDSA). RFC 6979, Internet Request for Com- References ments, The Internet Society (2013) 24. J. Clark, A. Essex, in Financial Cryptography and Data 1. G.O. Karame, E. Androulaki, S. Capkun, in Proceedings Security, Lecture Notes in Computer Science, vol. 7397, of the 2012 ACM conference on Computer and commu- ed. by A.D. Keromytis (Springer Berlin Heidelberg, nications security (ACM, 2012), pp. 906–917 2012), pp. 390–398. URL http://dx.doi.org/10.1007/ 2. G.O. Karame, E. Androulaki, M. Roeschlin, A. Ger- 978-3-642-32946-3_28 vais, S. Čapkun, ACM Trans. Inf. Syst. Secur. 18(1), 2:1 25. C. Decker. Data propagation: How fast does information (2015). DOI 10.1145/2732196. URL http://doi.acm.or move in the network? http://bitcoinstats.com/netwo g/10.1145/2732196 rk/propagation/ (2017) 3. GAP600. Gap600 bitcoin transactions guaranteed. http: //gap600.com/ (2017) 4. T. Bamert, C. Decker, L. Elsen, R. Wattenhofer, S. Wel- ten, in Proceedings of the IEEE Internation Conference on Peer-to-Peer Computing (P2P) (Trento, Italy, 2013., 2013) 5. A. Biryukov, D. Khovratovich, I. Pustogarov, in Proceed- ings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (ACM, 2014), pp. 15–29 6. A. Biryukov, I. Pustogarov, in Security and Privacy (SP), 2015 IEEE Symposium on (IEEE, 2015), pp. 122– 134 7. J.A. Kroll, I.C. Davey, E.W. Felten, in The Twelfth Workshop on the Economics of Information Security (WEIS 2013) (2013) 8. I. Bentov, R. Kumaresan, in International Cryptology Conference (Springer, 2014), pp. 421–439 9. J. Poon, T. Dryja, The Bitcoin lightning network: Scal- able off-chain instant payments. Tech. rep. (2015). https://lightning.network 10. I. Bentov, R. Kumaresan, A. Miller, in International Conference on the Theory and Application of Cryptology and Information Security (Springer, 2017), pp. 410–440 11. B. David, R. Dowsley, M. Larangeira, in Proceedings of the 2018 International Conference on Financial Cryp- tography and Data Security (2018) 12. S. Park, A. Kwon, G. Fuchsbauer, P. Gazi, J. Alwen, K. Pietrzak, in Proceedings of the 2018 International Conference on Financial Cryptography and Data Secu- rity (2018) 13. T. Ruffing, A. Kate, D. Schröder, in Proceedings of the 22Nd ACM SIGSAC Conference on Computer and Com- munications Security (ACM, 2015), CCS ’15, pp. 219– 230 14. A.M. Antonopoulos, in Mastering Bitcoin: unlocking dig- ital cryptocurrencies (O’Reilly Media, Inc., 2014), chap. 5 15. Certicom Research, Sec 2: Recommended elliptic curve domain parameters. Tech. rep., Certicom Corp. (2010) 16. A.J. Menezes, P.C. Van Oorschot, S.A. Vanstone, Hand- book of applied cryptography (CRC press, 1996)