BIP: whitlock-txid-draft
Layer: Consensus (hard fork)
Title: Mitigating transaction malleability by redefining TxId
Author: Matt Whitlock <bip@mattwhitlock.name>
Type: Standards Track
Created: 2017-04-01
License: WTFPL <http://www.wtfpl.net/>
The problem of transaction malleability can be ameliorated by redefining the transaction identifier so that it excludes the input scripts. No change to signing procedures or to any Script operations is needed.
TODO
Presently a transaction identifier ("TxId") is a double-SHA256 message digest computed over the bytes comprising a whole serialized transaction. This is problematic because the signatures checked by the OP_CHECKSIG family of Script operations cover only a subset of these bytes, meaning a pending transaction may be altered ("malleated") by a party not in possession of the signing keys, to change the transaction's identifier without invalidating the transaction. Please refer to BIP 62 for an overview of some of the real-world challenges this creates.
The primary purpose of a TxId is to act as a fixed-length identifier that uniquely identifies a transaction in a block chain or memory pool. The identity of a transaction is presently determined by the bytes of its serialized representation, but this is a needlessly strict definition. The identity of a transaction may be usefully defined by the transaction's semantics: which outputs it spends and what outputs it introduces. Crucially, the proofs given to satisfy the redemption criteria for a transaction's inputs are not meaningful components of the transaction's identity and thus need not participate in the TxId. Excluding these proofs from participating in the TxId eliminates the most troublesome class of transaction malleability, as shall be discussed further in this section.
At a high level, two classes of transaction malleations exist: those that invalidate the transaction and those that do not. Malleations that invalidate the transaction are not a concern of this proposal, as thusly malleated transactions can never be accepted into a memory pool or mined into a valid block and so do not pose significant operational challenges.
This proposal addresses the class of malleations that do not invalidate the transaction, such class further comprising a subclass of malleations that alter input scripts and a subclass of malleations that alter other parts of the transaction. By excluding input scripts from participating in the TxId, the subclass of malleations that alter input scripts is rendered inert: such malleations remain possible but have no appreciable consequences.
The remaining subclass of non-invalidating malleations comprises those that alter parts of the transaction other than the input scripts. Three such malleaction vectors exist:
-
If there exists a way to satisfy the redemption criteria for all inputs without requiring the successful verification of any signature, then any part of the transaction may potentially be altered without invalidating the transaction. This type of transaction, which redeems only "anyone-can-spend" outputs, is already assumed, by its nature, to be unreliable until it is sufficiently embedded into the block chain, so this malleation vector is inert.
-
If there exists a way to satisfy the redemption criteria for at least one input without requiring the successful verification of any signature that is of a type other than
SIGHASH_NONEand to satisfy the redemption criteria for all inputs without requiring the successful verification of any signature that is of typeSIGHASH_ALL, then any output not corresponding to an input whose redemption criteria require the successful verification of a signature that is of typeSIGHASH_SINGLEmay potentially be altered without invalidating the transaction. This type of transaction, considered a "blank check," is already assumed, as a matter of its intent, to be malleable until it is sufficiently embedded into the block chain, so this malleation vector is inert. -
If there exists a way to satisfy the redemption criteria for all inputs without requiring the successful verification of any signature that lacks the
SIGHASH_ANYONECANPAYflag, then inputs may be added to or removed from the transaction without invalidating the transaction. This type of transaction is already assumed, as a matter of its intent, to be malleable until it is sufficiently embedded into the block chain, so this malleation vector is inert.
In summary, all non-invalidating malleations that alter parts of a transaction other than its input scripts are already inert. This proposal renders inert the remaining class of malleations, thereby wholly ameliorating the problem of transaction malleability.
There exist other proposals to mitigate the problem of transaction malleability.
BIP 62 proposed to constrain the valid encodings of input scripts as a means of eliminating malleation vectors without requiring a hard fork. The proposal was withdrawn to be reintroduced later as a series of proposals.
BIP 66 mandated the encoding of signatures by the ASN.1 Distinguished Encoding Rules (DER). This new requirement eliminates one malleation vector but leaves many others unaddressed. The present proposal excludes encoded signatures from participating in the TxId, so the particulars of signature encoding are irrelevant.
BIP 140 proposed normalized transaction IDs, which are computed equivalently as in the present proposal but are never referenced in the protocol, this latter point being a necessary concession to allow deployment as a soft fork. BIP 140 also proposed to repurpose a no-op Script opcode as a new signature verification operation that checks Schnorr signatures rather than conventional ECDSA signatures. Although BIP 140 accomplishes everything that the present proposal accomplishes, it adds storage overhead, in that the database must store a normalized transaction ID for every new transaction, and it adds implementation complexity, in that it requires the implementation of Schnorr signatures. Critically, transactions using conventional ECDSA signatures do not benefit from the malleability fix. The author of the present proposal believes that BIP 140 takes "too large a bite": malleability should be fixed independently from the introduction of any new signature scheme.
BIP 141 proposed Segregated Witness ("SegWit"), a soft-fork protocol extension that would relocate the input scripts outside of the conventional transaction and therefore eliminate the same class of malleation vectors as the present proposal eliminates. However, BIP 141 is an extensive proposal that is seeing significant pushback from the community, such that it may never see activation. Again, the author of the present proposal believes that transaction malleability should be fixed independently of unrelated protocol extensions, as this will afford the greatest chance of adoption.
BIP 147 proposed a new consensus rule to require that the unused stack element in OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY operations be a null element (empty byte array). Like BIP 66, this new requirement eliminates one malleation vector but leaves many others unaddressed. The present proposal does not address this malleation vector, as it belongs to the class of malleations that invalidate signatures or to the subclass of malleations that impact "blank check" transactions, which should already be expected to be malleable.
BIP 134 proposed Flexible Transactions ("FlexTrans"), a new transaction serialization format that moves input scripts outside of the block of data over which the TxId is computed, thereby eliminating the same class of malleation vectors as the present proposal eliminates. However, like SegWit, BIP 134 is an extensive proposal that makes many other modifications to the protocol aside from fixing malleability, and it has a fatal design flaw in that the specification of a Script version in an input could alter the semantics of a previous output script. Again, this proposal is "too big a bite."