Layer: Relay Policy Title: Standard Priority and Doublespend Proof Author: @im_uname <imaginary.username.btc@gmail.com>, Tom Zander <flowee@libertymail.net> Created: 2018-07-16 Last updated: 2018-08-09 License: IDGAF
New relay and mining policies are specified for existing transactions that improve 0-confirmation reliability for wallets immediately and quantitatively (following miner adoption) upon deployment, without requiring change on wallet developers' part. Further improvements to 0-confirmation transactions can be achieved by wallets and merchants willing to receive doublespend-proof alerts.
Existing Bitcoin Cash transactions today are already divided into two broad categories:
"Standard priority transactions", otherwise known as "standard" transactions that pay sufficient fees today, will become more reliable for 0-confirmation, at no additional effort to wallet developers.
Nonstandard or low-fee transactions will become less reliable in 0-confirmation, until inclusion in block.
Both types of transactions can benefit in reliability if a receiving wallet adopts an optional doublespend-proof alert.
Define a respend as an unconfirmed transaction that spends one or more UTXOs also spent by another unconfirmed transaction, which differs from it even when scriptSig contents are ignored. We do not consider a malleability clone to be a respend. Two transactions can be respends to each other depending on which one a given node sees first.
Define a Standard Priority (SP) transaction as a transaction that fulfils all criteria of the IsStandard() check in most node implementations, plus fulfil the default minrelayfee most widely used, currently at 1 satoshi / byte.
Any transaction that falls outside SP is defined as an NP. They are typically not relayed by most nodes on today's Bitcoin Cash network.
There are two main cases of 0-confirmation double-spend that can be successful even when miners follow a simplistic first-seen policy. These are the fast respend and the reverse respend. This proposal improves on earlier techniques in handling each case.
In the cases below, further define a legitimate transaction to pay a recipient who is expected to provide value in exchange for payment. An economic double spend occurs when a payment recipient relies on an unconfirmed transaction that is ultimately invalidated by the confirmation of a respend of that transaction.
Assuming widespread adoption of the rules outlined in Specifications below, a merchant that receives an SP transaction payment as he does today, regardless of fee amount above minimum, and waits a short time (< 5 seconds) for a doublespend-proof alert without receiving any should be able to expect his SP transaction to be mined instead of its alternative(s). In case fraud is attempted, the merchant cannot expect his payment to be the one mined, but can expect the proof to be received shortly so appropriate actions can be taken in time.
The goal is to inform merchants and wallet-holders about double spends against them, so they can determine in time the appropriate actions against the fraudster. As long as a merchant learns of a fraud before they hand over the merchandise, they can minimize their risks beyond what is already achievable on Bitcoin Cash today.
A fast respend is transmitted simultaneously or almost simultaneously with the legitimate transaction. With a simplistic first-seen policy, miner and merchant experiences of first-seen are random if the attacker propagates at random (the attacker can improve this if she knows the network topology better), leading to probabilistic success in creating an economic double-spend.
A variant is to broadcast the respend immediately after the merchant approves payment, hoping the legitimate payment will be slowed by network randomness on its way to miners. This variant is addressed in the same way as Reverse Respends below.
Solution: The network must propagate SP transactions, and respend proofs of subsequently detected respends whether SP or NP, immediately. By monitoring for transactions and proof of their double-spends and not seeing any, recipients can quickly gain confidence that miners have seen the same transaction first.
Analysis: A merchant today generally receives SP transactions only. In order to perform a fast respend, the respend needs to propagate to a significant part of the network to have a chance of success against the merchant's version, and only SP transactions can achieve that; however, nodes receiving the respend will either:
-
If the legit payment is received significantly later, the merchant would have the "respend" already, and can reject the "legit" payment as being doublespent already.
-
If the legit payment is received at the same time its respend is broadcasted, the network will become fragmented about which tx is first seen. However, when both versions of the tx reach nodes on the other half of the network, proofs will be generated at the boundary and continue to propagate unhindered. The merchant can use a wallet that detects such a proof, and after a reasonable delay (proofs will propagate as fast as any SP tx does today, hence delay should not be longer than a few seconds), the merchant can be reasonably sure to have caught all possible fast-respends if any.
Note that today we observe some "doublespend transactions" only being detected on the network more than 10 seconds later; this is likely due to most of the network not propagating any doublespend transactions at all, hence doublespends can take significantly more hops to reach a given node if its counterpart is much better propagated. This is not expected to be a problem with double-spend proofs, which can simply propagate unhindered along all the same routes where its counterpart has gone through.
A reverse respend is a NP respend transaction placed with miners before the legitimate tx is broadcast. With a simplistic first-seen policy, miner ignores the legitimate tx and confirms the non-legitimate transaction. Since some miners have an interest to mine NP transactions and it's not against consensus to do so, we cannot stop them; however, the rest of the network not propagating NP transactions makes it difficult for a merchant to receive notification of such a respend's existence, sometimes only when a block is mined.
Solution: We recommend the following default policies for miners and other nodes: If an NP transaction is received first (by a custom adjusted node hoping to mine NP transactions) and a respend is received in the form of SP, then SP replaces NP in the mempool, but proof for the evicted NP is relayed. This proposal specifies mempool eviction of a NP transaction when a conflicting SP transaction is seen even when the SP is received later, as long as the NP is not confirmed.
Since a non-trivial percentage of hashrate on Bitcoin Cash appears to mine NP transactions today, a merchant has a probabilistic chance of having an NP respend confirmed against him all the way until the first block comes in after transaction, adding to uncertainty. If the miners adopt the recommended policy, they can still mine NP transaction as they wish; however, a malicious actor is no longer able to to take advantage of this policy, since much better propagated SP (which merchants accept) will replace NP and get mined instead, ruining the attacker's respend profits. The NP will still have its proof propagated, providing the merchant with further proof of a failed fraud attempt in case he/she wants to pursue it.
Note that this policy immediately reduces the risk of most wallets against the Reverse Respend attack without the wallets changing anything; all it takes is miners who mine NP adopting the replacement policy. The miners concerned can still mine non-respending NP transaction in peace as long as a respend is not detected. "Useful" NP transactions are not relayed very well and are typically only mined by directly transmitting to miners anyway, so they do not need 0-confirmation security of any kind and would be minimally affected.
The policy has a proportional effect the more miners adopt it, its usefulness is not limited to the scenario of universal adoption.
- Passes
IsStandardTx()in Bitcoin ABC 0.17.2, Bitcoin Cash Unlimited v1.3.0.1, and Bitcoin XT 0.11.0J - Pays a minimum fee of 1 satoshi/byte; may be adjusted further in the future
-
When a node receives an SP transaction, it is relayed per standard rules.
-
When it receives a subsequent transaction (whether SP or NP; whether it relays NP transactions) that spends the same input as a previously-seen transaction, a Double-spend Proof is generated for the conflicting inputs and relayed using a new INV type. It can be named, for example, DSPROOF. The proof should be self-contained and has relevant information from both transactions (details below), so anyone with the proof can be certain a respend has happened.
-
A node receiving a double-spend proof for an input for the first time will NOT relay nor keep it if the conflicting tx is not present in its mempool - to protect against arbitrary DoS using proofs. A node will only keep and relay proofs if a conflicting tx already exists. If it has already generated or relayed a proof for a given input, subsequent incoming proofs are ignored.
-
If a node receives a transaction that spends the same input as a transaction in its mempool while a doublespend proof already exists, the new incoming tx is ignored. A node will only keep and propagate one tx and one of its conflicting proof at most, at any given time.
-
A proof stops being valid when the relevant input is no longer spendable - for instance when a transaction containing the input is included in a block. Proofs should no longer be advertised or propagated after they stop being valid.
- Regardless of proofs propagated, nodes keep and mine the first of any conflicting SP txs seen as per existing rules.
-
If a node has first seen an NP transaction and included it in its mempool and subsequently sees an SP transaction spending one or more of the same inputs, the NP transaction is evicted, replaced by the SP. As per rule 1, a proof is generated for the respent input at the evicted NP transaction and propagated.
-
An SP transaction shall never replace another first seen SP transaction. This applies even if the later-seen SP transaction respends input from a separate NP transaction per first part of Rule 3.
In Bitcoin Cash any input is signed using the sighash algorithm. The sighash types define exactly which part of the entire transaction to use and which to ignore when creating a hash, which is then signed.
Per the BCH (aug-2017) rules of SIGHASH_FORKID the stream we hash in the hashing phase of signing is defined to be multi-stage.
Specifically, as part of the stream we hash for a specific input, we add the hash of all the inputs. This multi-stage hashing is used in proofs to avoid providing the entire transaction in order to be able to sign an input, instead we can just provide some hashes.
In order to create a signature of a single input we have a code-snippet like this to create the hash to sign;
uint256 hashPrevouts;
uint256 hashSequence;
uint256 hashOutputs;
if ((nHashType & 0x1f) != SIGHASH_SINGLE && (nHashType & 0x1f) != SIGHASH_NONE) {
hashOutputs = GetOutputsHash(txTo);
} else if ((nHashType & 0x1f) == SIGHASH_SINGLE && nIn < txTo.vout.size()) {
CHashWriter ss(SER_GETHASH, 0);
ss << txTo.vout[nIn];
hashOutputs = ss.GetHash();
}
CHashWriter ss(SER_GETHASH, 0);
ss << txTo.nVersion;
ss << hashPrevouts;
ss << hashSequence;
// separator line
ss << txTo.vin[nIn].prevout;
ss << static_cast<const CScriptBase &>(scriptCode);
ss << amount;
ss << txTo.vin[nIn].nSequence;
ss << hashOutputs;
ss << txTo.nLockTime;
ss << nHashType;
return ss.GetHash();
In effect any part of the input we are signing will be represented twice in this hash, once as part of the hashPrevouts or hashSequence and once again in the bottom part (below the separator line) where each part of an input is specifically added.
To actually create a double-spend proof we need to provide two inputs that both spend the same input (similar scriptCode), and they are both signed with the same private key. In other words, the proof is self-contained with relevant info from both transactions, anyone should be able to then take that double-spend proof and verify that the signatures (as copied from the original inputs) are correct.
We create a message that ships for each input that is double-spent the hashPrevouts, hashSequence and hashOutputs (in order to represent the irrelevant part of the transaction). Additionally the actual input itself is sent. The txid of the output it is spending, the output-index, the amount, the input-script (scriptsig), the sequence, the locktime of the transaction. Notice that the txid / output-index that is being spend is the same for all the inputs that are proven to spend those. So they only need to be supplied for the first.
The receiver of a proof will be able to validate the signature of the original transaction (repeated for each of the re-spends) by following the recipe of the sighash consensus algorithm but replacing the hashes that represent the missing part of the transaction with the hashes that the proof supplied.
Simply said, if you split the way BCH sighash validation works today as illustrated by the above script at the line of the separator, then the proof does the top part and the validation of the proof does the bottom part.
This proposal does not affect block or transaction validity consensus. The protection against Reverse-respends, mostly addressed by Rule 3, can be deployed by mining nodes immediately, and it improves 0-confirmation security of all existing wallets accepting SP transactions in a quantitative fashion as more miners (especially ones that mine NP transactions) deploy it. NP transactions are minimally affected, as they do not relay well and hence are not usually subject to 0-conf security considerations. In fact, miners adhering to Rule 3 can now mine NP transactions with the peace of mind that it no longer affects the rest of the ecosystem.
As deployment of doublespend-proofs per Rule 1 becomes more widespread, wallets are encouraged to receive proofs in addition to transactions; receiving a proof shall result in easy-to-notice alerts so merchants can take appropriate action, whether by refusing goods and services or alerting law enforcement.
Wallets adhering to existing default rules would not need to do anything immediately. They are encouraged to receive proofs, and upon receiving a proof display in unmistakable, easy to notice alerts that a fraud attempt has taken place.
If an existing wallet attaches to an NP-relaying node, unusual on the network today, the wallet should be configured to alert the merchant about incoming NP transactions, so goods and services are not given out before confirmation if an NP is used for payment.
-
If an attacker broadcasts two conflicting SP transactions at nearly the same time, one of them being a payment to merchant, the network fragments over which one is seen first, and the legitimate tx might not ultimately be mined. However, the merchant should be able to receive a proof within a short time, enabling him/her to take appropriate action whether refusing service or calling law enforcement.
-
If an attacker broadcasts a conflicting SP transaction well after the legitimate payment (SP), the merchant will not be able to refuse service in time, but the fraudulent transaction is highly unlikely to get first-seen and hence mined anywhere on the network, unless a miner conspires with him, which is beyond the scope of this proposal.
-
If an attacker attempts to broadcast a conflicting NP transaction first and the SP transaction paying merchant second (reverse-respend seen here: https://twitter.com/jasonchavannes/status/982350179079569408), per Rule 3 the NP will be replaced by miners who adopt the policy, hence the attack fails. Merchant should also be able to get a proof of the attempt in a short time.
SPV wallet can receive both tx and proofs the same way as any full node and verify that the proof is valid for a given tx (no false positives); their ability to thwart false negatives will be similar to SPV wallets today, and rely on connection to multiple nodes to improve the chances that at least one of them will relay the desired tx (and proof, if any). They do not need to do anything to benefit from the SP replacement rule.
Relaying proofs carries a DoS risk as attackers can attempt to increase bandwidth and memory consumption by broadcasting proofs in addition to fee-paying tx; however, since proofs are not relayed without an existing tx, this attack is limited to at most doubling the bandwidth and memory requirements, and can be expected to be much less depending on how many transactions the attacker can spam in the first place. As the size of a given proof cannot be bloated by adding outputs, we can also expect it to be more readily transmitted by nodes without needing as stringent a rate-limiter as a straight respend transaction relay.
The double-spend proof detection mechanism described above caters to situations where the merchant's payment is directly respent. For service providers that accept unconfirmed chains (most prominently Yours.org), it is possible for a payment to not be directly respent, but instead have its unconfirmed parent be respent. Merchants who accept chained unconfirmed transactions should configure their wallets to detect not only doublespend proof for transactions that directly pay them, but also that any of its unconfirmed parents, to take maximum advantage of relayed proofs.
In bitcoin, transaction propagation is dependent on fees. Low fees make a successful economic double-spend more likely. This proposal aims to divide existing transactions into two classes: SP transactions now enjoy higher security regardless of fee level as long as it's above minimum, especially with proofs alerting merchants of any fraud attempts.
Obviously, no rule can guarantee that any specific transaction will be mined, as transaction spikes can theoretically clog mempool no matter how high maxblocksize rises, and not all miners might adhere to the new rules. However, the rules are not binary in their benefits, and can be expected to gradually improve security as more miners and nodes adopt them. It remains the responsibility of the sender to include a fee, even beyond SP requirements, that meets current conditions of the network for the receiver to agree that it will be confirmed within reasonable time and hence has acceptable security, in the event of a small minority of uncooperative miners.
The doublespend proof part of this proposal is currently limited to simple P2PKH inputs (the most widely used format in 0-conf usecases), and does not cover multisig P2PKH or P2SH. Future extensions to these formats are possible, pending further considerations about possible attack vectors. Pubkey and signatures in input are available for proof verifications in both cases, even if the conflicting transactions are not signed by the same private key(s).
The proof could be simplified (=shrunk) enormously if we can send the intermediate state of the hash instead of the various parts that went into creating it. [TomZ]
It might be especially desirable to "bundle" relayed proof with its conflicting tx to ensure propagation, since nodes do not accept proofs if a conflicting tx is not already seen per Rule 1.3. Other more efficient relay mechanisms are suggested and up for discussion, one of which is https://gist.github.com/imaginaryusername/87af893d260afd7c60606b33403063cd .
The exact format of proof and corresponding code remains to be determined after public input.
An alternative proposal that only describes the doublespend proof can be seen here, by Chris Pacia: unlike the proof described in this document, Pacia's version requires a corresponding tx to be present to determine the proof's validity. https://github.com/cpacia/spec/blob/master/double-spend-alerts.md
We'll like to thank Tom Harding's Superstandard Immediate (SI) Transactions for providing key definitions and inspiration for this piece. A significant part of the proposal was adapted from the SI proposal at https://gist.github.com/dgenr8/173c3a3fdad1afc8a2d2c0ef676aa7ff .
This document has undergone several revisions, and we are especially grateful for the useful input and discussion from Tom Harding, Griffith, Andrew Stone, Shammah Chancellor, btcfork, Chris Pacia, freetrade68 and others, which led to significant improvements and clarifications.