Transaction malleability in cryptocurrencies

In this article I'm going to provide a brief review of protection methods against replay attacks, arising from signature malleability of elliptic curve cryptography.

Thus everyone can verify that the sender wants to send her coins to the recipient, but a problem arises - how to prevent the inclusion of transactin Tx in the blockchain twice? Without such a protection an unscrupulous recipient may repeat Tx as long as the sender has enough coins at his balance, making it impossible to reuse the same address for more then 1 transaction. In particular the adversary can withdraw some coins from an exchange and repeat this transaction until there are no coins left on exchange (such attacks have already been executed in practice, e.g. for

The simplest way to keep all the included transactions and compare the new one to them doesn't work because of the elliplic curve signature malleability - it is possible to change a signature but keep it valid at the same time (see

Scala code that changes signature like that is very simple:

    def forgeSignature25519(signature: Array[Byte]): Array[Byte] = {  
        val modificator: BigInt = BigInt("7237005577332262213973186563042994240857116359379907606001950938285454250989")  
        signature.take(32) ++ (BigInt(signature.takeRight(32).reverse) + modificator).toByteArray.reverse  
    }

Thus, now we have a sequence of transactions Tx1, ..., TxN with the same fields, but different signatures, and there's a challenge to determine whether they are all generated by the sender or some of them are generated by the adversary.

For example, if you need your transaction to be included in block as soon as possible, you may rebroadcast your transaction with the same nonce, but increased fee and be sure, that only one of your transactions will pass all checks. Nonce provides additional benefits for transactional layer, but not for free - every transaction should contain nonce, so transaction size become bigger. On the other size nonce should be big enough, because it's not clear how to handle a situation when nonce limit has been reached. To mitigiate this it's possible to reuse a transaction field as nonce, for example use timestamp as a nonce.

In such an approach it's not possible to require to increase nonce by 1, so rule Tx.timestamp > account.timestamp should be used. This leads to another attack: if someone broadcasted sequence of transactions Tx1, ...,TxN with increasing timestamp, "evil" miner may only include TxN making transactionsTx1, ..., TxN-1 invalid.