Double Spend Proofs: Protocol Improvements and Providing End-User Guidance

groot-verde · April 8, 2021, 8:42pm

Authors:
Andrew Groot (groot@softwareverde.com)
Josh Green (josh@softwareverde.com)

Initial Feedback From:
Calin Culianu
Tom Zander

Overview

This document’s intent is to suggest paths forward for supporting additional transaction types for generating double spend proofs, which provides coverage for double-spend attacks that may be trivially undetected. It also seeks to identify scenarios that nodes (and third-party zero-confirmation services) should identify when determining if a zero-confirmation transaction may be considered inherently untrustworthy.

The existing beta message format for double spend proofs (see dsproof-beta) allows for efficient, canonical proofs to be generated that inform recipients of the existence of additional transactions spending a particular output. It is currently in use on the Bitcoin Cash network (as a beta) and is an excellent step in the direction of safer zero-confirmation transactions. At present, however, only P2PKH (pay-to-public-key-hash) outputs are supported, allowing malicious users to side-step double-spend detection by using other types of scripts. Fortunately, the general approach to double-spend proofs used by the dsproof-beta message is sound, and a relatively small number of changes would allow for a greater range of scripts to be proven double-spent. Additionally, by introducing clear recommendations about how to interpret the safety and legitimacy of zero-confirmation transactions in a post-double-spend-proof ecosystem, middleware and wallet developers will be able to provide consistent, trustworthy information to end-users risk associated with any given transaction.

Background and Motivation

The existing approach for P2PKH outputs relies on few properties of P2PKH scripts:

there is only one signature to validate
the only difference between inputs that double-spend an output would be the signature in the unlocking script
that signature is in a predictable location

Because of these properties, it is easy for a node with the double-spend transaction to extract the signature from the offending unlocking script and directly compute the hash-prevoutputs, hash-sequence, and hash-outputs values. That signature can then be added directly to the push-data list at the end of the spender information in the double-spend proof message. Validators of the double-spend proof then have all of the values needed to create the signature preimage and verify that such a transaction would unlock the double-spent output.

In order to support P2PK (pay-to-public key), a very similar approach could be taken, but for P2SH (pay-to-script-hash) and Multisig transactions, there are additional variables that come into play. The script length is variable in these cases, but the existing dsproof-beta format already provides room for additional push-data values, which could be used to push any necessary data from each transactions unlocking script. In the worst case scenario, the entire unlocking script could be provided in the push-data for each spender (this works due to the push-only rule and minimal data requirements in BCH). This, however, is still not sufficient as P2SH and Multisig unlocking scripts are capable of requiring multiple signatures to be validated.

While a transaction having multiple signatures is not necessarily a problem for double-spend proofs, the signature preimage can vary based on the hash type designated when generating the signature. This means that the hash fields (hash-prevoutputs, hash-sequence, and hash-outputs) could have different values depending on the signature. Fortunately, hash-prevoutputs and hash-sequence only have two possible values for a given transaction, one of which is all zero (0x00) bytes, meaning there’s no need to transmit that value. However, the hash-outputs field has three possible states, two of which have non-zero values. In order to validate a double-spend proof for a transaction with two such signatures (i.e. hash types with SIGHASH_SINGLE or SIGHASH_ALL), a validator would need to have both hash-outputs values, which there is currently no way to send in the dsproof-beta message.

Independent of handling multiple signatures, however, the hash type possibilities pose an additional threat to double-spend proof. The values SIGHASH_SINGLE, SIGHASH_NONE, and SIGHASH_ANYONECANPAY all present levels of transaction malleability. A malicious sender could use combinations of these types of signatures to create double-spends whose proofs would fail to be convincing. For example, in the most extreme case of SIGHASH_NONE | SIGHASH_ANYONECANPAY, all of the other inputs and all of the outputs of the transaction can be changed without altering the signature, meaning a double-spend transaction can be trivially created by anyone but a double-spend proof would appear to represent an identical transaction (with identical push data). Extending double spend proofs to allow for duplicate proofs with identical push-data would open up denial-of-services attacks via broadcasting a double spend proof for a transaction that does not exist. This is why currently the double-spend proof beta message only supports “P2PKH outputs with all inputs signed SIGHASH_ALL without ANYONECANPAY.”

This issue is exacerbated by the fact that SPV wallets are unable to easily and definitively make such determinations in a broader set of use cases. While for P2PKH the unlocking script is structured and understandable, SPV wallets often do not have the previous output’s locking script available to guarantee that the format they see is, in fact, part of a proper P2PKH script. For P2SH scripts this is rendered even more difficult, as simply iterating through the unlocking script and redeem script looking for signature-like structures does not necessarily guarantee that a transaction is not easily double-spendable by the creator. A simple example of this is a locking script that does not execute a checksig.n this scenario it is possible the locking script still pushes what appears to be public key and a value that appears to be a signature, but ultimately are not treated as such, fooling the SPV wallet into believing the script was for a regular P2PKH script. There is therefore a class of transaction for which convincing double-spend proofs cannot be created but which are in fact easily double-spendable. This then leads to the question: what do wallets do when they receive these kinds of transactions? If a double-spend proof has not been received for a transaction does that mean it is not double-spent, or that there is no known way to create a convincing double-spend proof? Further guidance is likely needed to ensure that these cases are handled sanely by node and wallet implementations.

The above shows that while double-spend proofs are useful for what are likely the most common transactions, malicious actors still have plenty of opportunity to take advantage of the limitations. It also shows that the changes necessary to make double-spend proofs fully useful will involve both risk analysis and technical solutions. The following sections aim to address both concerns.

1: Establishing Risk Assessment Conventions: Is Double-Spend Provable

Before expanding double-spend proofs to handle more cases, it is prudent to first address how the existence of double-spend proofs affects end-user perception of zero-confirmation transactions. Presently, it’s unclear how to handle this. But as previously mentioned, not all double-spends are easily provable. A full node may be able to determine that two transactions spend the same output, but the only other parties that would be able to definitely verify the double spend would be other full nodes that also receive the full transaction. Since full nodes do not (and should not) relay double-spend transactions, nodes that are interacting with SPV nodes (or, more importantly, those supporting middleware services that provide transaction information to SPV nodes) need a method for determining how likely it is that a transaction 1) has not been double-spent, or 2) was double-spent but the proof was not relayed because a double-spend proof was not possible to create.

For the existing double-spend proof format, the rules for whether a double-spend proof is supported for a given input are very straightforward. If, and only if, the following items are true, a double-spend proof is currently supported for the input:

The spent output is in a confirmed transaction (mined in a block)
The locking script for the previous output is in the P2PKH format
The unlocking script signature has the hash type SIGHASH_ALL without SIGHASH_ANYONECANPAY

Given this, the following algorithm could be used to determine the risk level an otherwise valid zero-confirmation transaction possesses:

Are all of the transaction’s inputs spending outputs in a way that is known to allow for a double-spend proof?
If not, the transaction is not considered double-spend provable, and the risk level should be increased.
If so, for each of the parent transactions, increase the perceived risk if any of the following conditions are met:
a. The parent transaction is a zero-confirmation transaction
b. The parent transaction is a zero-confirmation transaction and is not double-spend-provable
c. The parent transaction itself spends zero-confirmation transactions.
d. (Optionally) If the transaction has a high chaining depth.

Giving concrete values to this risk level is left for each implementer to determine based on the needs of the application being supported. In the simplest case, any of the above risk increases could be seen as reason to wait for at least one block confirmation before accepting the transaction.

A less risky transaction may still be double-spent, and a more risky transaction may ultimately be mined in the next block, but this assessment provides a mechanism for utilizing the knowledge that double-spend proofs for the evaluation of transaction trustworthiness. It allows for clearer end-user guidance, which in turn theoretically leads to increased confidence in accepting BCH transactions.

2: Extending Double-Spend Proofs: Message Format Changes

The following changes to the dsproof message format would allow for support of any non-trivially double-spent transaction outputs:

Always requiring the non-empty versions of hash-prevoutputs and hash-sequence, instead of using the value actually required by the signature.
Expanding the hash-outputs field to be a list of hash-outputs values, prefixed by their determining hash type bit value (for now, always SIGHASH_ALL (0x01) followed by SIGHASH_SINGLE (0x03)).
Using the following push-data requirements by locking script type:

a. P2PKH: Include all but the last push value (the signature but not the public key)
b. P2SH: Include all but the last push value (everything except the redeem script)
c. All other scripts: Include all of the values pushed in the unlocking script

This convention reduces the amount of data contained within double spend proofs for the most common script types while still maintaining flexibility for the less-used types.

Additionally, the changes to the hash-outputs affect the canonical order of the spenders. To address this, the hash-outputs values should be compared in order, the same way the single value was previously. That is, in numerically ascending order of the hash, interpreted as 256-bit little endian integers. If those are the same, the hash-prevouts values are compared the same way.

The above changes ensure both that the unlocking script for the double-spend transaction can be fully and accurately re-created, and that the data is available to validate any signatures that might be encountered during validation of the double spend proof.

With these changes, the top-level message format would remain the same but the spender format for each transaction would become:

Field	Length	Format	Description
tx-version	4 bytes	unsigned int	Copy of the transactions version field
sequence	4 bytes	unsigned int	Copy of the sequence field of the input
locktime	4 bytes	unsigned int	Copy of the transactions locktime field
hash-prevoutputs	32 bytes	sha256	Transaction hash of prevoutputs for hash type SIGHASH_ALL \| SIGHASH_FORKID.
hash-sequence	32 bytes	sha256	Transaction hash of sequences for hash type SIGHASH_ALL \| SIGHASH_FORKID.
hash-outputs-count	variable	var-int	The number of `hash-outputs` values to follow
hash-outputs-hashes (see below)	variable	byte-array	A list of serialized `hash-outputs` values
list-size	variable	var-int	Number of items in the `push-data` list
push-data	variable	byte-array	Raw byte-array of a `push-data`. For instance a signature

For hash-output-hashes referenced above, the following format is used for each relevant hash type bit:

Field	Length	Format	Description
hash-type-byte	1 byte	byte	The hash type value the following hash corresponds to.
hash-outputs	32 bytes	sha256	The output(s) hash variant resulting from the preceding hash type.

At present this would always be the hashes for SIGHASH_ALL (0x01) and SIGHASH_SINGLE (0x03), in that order. Both are always required.

This would result in a static increase of 35 bytes per spender, for a total of 70 additional bytes per double-spend proof. These extra bits correspond to the hash-outputs-count field, hash-type-byte fields, and the extra hash-outputs field. For non-P2PKH scripts, the push-data array would also vary more in size, depending on the unlocking script of the transactions.

3: Expanding the Double-Spend Risk Assessment

With any expansion of the double-spend proof format, the risk assessment defined above should be expanded to match the new reality of double-spend proofs.

With the above expansions to the double-spend proof format, the following cases now need to be acknowledged (as they are permitted by the newly expanded script types):

Unlocking scripts that result in no signature being executed (e.g. a P2SH that acts like a password)
Unlocking scripts that contain a signature that cannot be obtained easily without execution (e.g. custom P2SH scripts)
Unlocking scripts that contain multiple signatures (e.g. raw multisig)
Non-standard scripts that could result in any of the above

These cases are likely to only be able to be handled by full nodes. As a result, the double-spend proofs are unlikely to be valuable on their own to SPV nodes, making this risk assessment even more important.

One additional scenario is when an unlocking script exclusively uses signature hash types that do not cover the whole transaction (i.e. anything other than SIGHASH_ALL without `SIGHASH_ANYONECANPAY). There may be circumstances in which a transaction with one or more such scripts would still yield a valid double-spend proof, but further analysis is required for that to be determined. Future expansions of the risk assessment may choose to address those cases, providing sufficient evidence that they are safe.

As a result, the high-level assessment algorithm can remain. The assessment of whether a double-spend proof can be generated for a particular input then becomes:

During the validation of the input, at least one signature was found

a. If no signature verifications were required to validate the input, the prevout is potentially double-spendable with the same script; this transaction is high risk
At least one signature has the hash type SIGHASH_ALL without SIGHASH_ANYONECANPAY

a. With this the script is sufficiently tied to its containing transaction. Any double-spending transaction would therefore have a different unlocking script and therefore a double-spend proof could be created.

Note that while transactions that fail the assessment are not guaranteed to have double-spend proofs (and should therefore be considered risky) a double-spend proof is still possible, if the double-spend transaction does match these rules.

Final Thoughts

With these changes, full nodes and 3rd-party zero-confirmation risk assessment services should be able to relay proofs for nearly all common double-spend attempt methods, while also being able to identify transactions that are inherently double-spendable. If these changes are accepted (in spirit) by the BCH network, then the next steps would be creating a series of test-vectors that demonstrate the various risk-states for unconfirmed transactions for nodes and services to use as implementation tests.

TierNolan · April 15, 2021, 9:17am

Isn’t there a contradiction there?

The first section requires that inputs be mined to be considered valid for double spend proofs.

The “if so” in the second quote means that they are valid for double spends. That means that the parent can’t be a zero-confirmation transaction.

groot-verde · April 15, 2021, 2:14pm

That’s a good point. Honestly, I think we really need to do those additional checks regardless.

The requirement that the previous outputs are confirmed came from existing documentation on double-spend proofs, but I think with the risk assessment we can “relax” that constraint in lieu of the risk assessment marking transactions like that as higher risk.

That would mean removing condition 1 from the double-spend-provable check and check the “If so” in part 3 of the risk assessment to “Additionally,” since we always want to include those checks. Would that fully address your concern?

TierNolan · April 15, 2021, 2:54pm

That is fair.

I think that inputs for zero-confirm should be mined transactions. It is reasonable to leave it as UI question though.

The main use cases for zero confirm is paying for the “cup of coffee” in a shop or paying for digital data online. I think in those cases, stores would be recommended to not accept transactions which spend unconfirmed inputs. There isn’t much loss of functionality. People would have coins in their wallet for a while when they go to pay.

The difficulty is that they have to wait 10 mins between payments if they only have 1 coin. Wallets should ideally pre-split the coins so there is always some confirmed funds available.

In practice, transaction that spends an unconfirmed input are likely not that much more dangerous than one that spends confirmed inputs. There isn’t much difference between double spending a transaction and double spending a parent.

A risk is that the double spend proof has already been sent. For example, an attacker sends a transaction A and then sends A’ direct to the merchant, so the merchant sees A’ first. The merchant doesn’t see A at all but sees the double spend proof for A. It ignores it since it doesn’t affect him.

The thief then pays with B’ which spends A’. Miners see A first, so that is what gets confirmed which cancels B’.

I think allowing non-confirmed inputs means that you need to check more sequences of transactions to confirm that the merchant will see a DS proof. Merchants would be recommended to keep DS proofs for a while.

groot-verde · April 15, 2021, 4:07pm

To your point, I think this proposal currently misses how risk assessment should change when a double-spend proof is known. I suppose we sort of assumed that a known double-spend proof in a transactions (unconfirmed) ancestry would obviously raise the risk level substantially, but we didn’t call that out.

The intent here though is, as you mentioned, for that risk assessment to be left to the end-user. While I agree that it would be perfectly reasonable if most users took any level of increased risk as a sign that they should wait for a confirmation, one of the primary reason we wanted to pursue these changes is to allow for a level of zero-confirmation chaining while maintaining a high level of confidence in the transactions.

Wallets pre-splitting coins will always have to be done on a heuristic basis and it’s not unreasonable for a user to want to spend money shortly after they’ve received it. So even in a world where wallets are routinely performing some level of splitting, chained zero-confirmation transactions still end up being necessary in some valid scenarios.

On top of that, given that the most common use-cases are well-covered by double-spend proofs, the point-of-sale system/wallet used by the merchant in your example should make it clear when the merchant receives B’ that it is spending a transaction, A’, that has a known double-spend proof and is therefore high risk.

For a merchant using an SPV wallet that does not rely on such a service, there’s a bit of tricky question to answer. To your point, they should ideally keep double-spend proofs until a block is mined with a transaction spending the relevant output. But what is the right way for them to get that notification? I believe the only way for them to guarantee that they’ll hear about whatever transaction ends up spending the output (even if it’s one they weren’t at all exposed to) would be to add the outpoint to their bloom filter. But doing that for every double-spend proof could end up heavily increasing traffic to SPV nodes, often for transactions they don’t care about at all. That said, wallets could just remember the output and discard the rest of the double-spend proof, which might make it practical to track them long-term. Either way, though, it’s an awkward situation.

Ultimately, this is why we’ve proposed that third-party services with full nodes perform this analysis. SPV nodes simply aren’t equipped to validate whether a given zero-confirmation transaction is even valid (given that they rarely, if ever, have all of the locking scripts), let alone whether it might be double-spent.

TierNolan · April 15, 2021, 8:31pm

This is probably an empirical question. In practice, it is possible that only a small number of DS proofs will be sent per block. An SPV client could simply keep all proofs for 1-2 blocks and they would be fine. They can check the entire transaction chain against the DS proofs stored in RAM.

If the DS proof system is effective, then nobody will bother to double spend. Having said that, with low fees, it is (relatively) inexpensive to spam the DS system. An attacker can create lots of UTXOs and then double spend all of them.

An SPV client is inherently trusting a full node. The assumption is that if you connect to multiple full nodes, then it is unlikely that they will all censor transactions. The merchant could ask all peers if they know of DS proofs for any inputs (or inputs of inputs).

The merchant’s wallet could ask the buyer’s wallet to give all unconfirmed input transactions and inclusion proofs for all confirmed inputs, since the buyer inherently has them. That may make it more efficient when communicating with the full nodes. The request for DS proofs could be more targeted.

The merchant would still need to check if any inputs have actually been spent since the inclusion proof, so maybe there is no improvement there. You have to ask the full node to check all inputs, so they can do the DS proof check then.

dgenr8 · April 16, 2021, 12:19am

Whether it is relevant that a customer just tried a double-spend, even if merchant didn’t see the tx that would have paid him, is subjective. Personally, I think it is quite relevant.

jscramer · April 16, 2021, 3:08am

Andrew, I’m new to dsproofs so sorry about maybe the ignorant question… I was surprised to read about the issue of validating scripts other than p2pkh, and this sounds like a well-known limitation.

Why doesn’t a dsproof consist of just three fields:
(1) a 36-byte outpoint id of the ds,
(2) the raw transaction containing the ds, and
(3) the scriptPubKey of the ds.

So anyone who receives that proof, regardless of script type could just validate that the scriptSig unlocks the scriptPubKey, just like how a node normally accepts a transaction. With the scriptPubKey included clients wouldn’t need any outside information or blockchain data to verify two dsproods spend the same outpoint.

I’m assuming this is not desirable because wallets would need a script vm? If this is the case, it might be not that big of a deal because the ecosystem tooling is getting pretty flexible. Bitjson has bitauth library which has a script vm. Would just need a little dsproof javascript library and maybe a couple other languages.

jscramer · April 16, 2021, 3:27am

That’s what I was thinking also. Its easy to conceptualize how to have a service allowing address subscribers, where for map of key: outpoint → list of address list subscribed is maintained. Anytime one of the outpoints is seen twice by the node an alert (with the proof) is sent to the list of address subscribers.

The down side is the third-party risk. As Josh alluded to on the dev hangout this is probably one of those things similar to SLP, can be prickly. Maybe its best to have the merchant join the p2p network, seems like they wouldn’t need to sync the chain. Is it possible to just join the network as just a listener peer, or do peers ban you for that?

freetrader · April 16, 2021, 12:46pm

If a fraudulent double spend was successful, others who received the DS proof and learn about the fraud later, could avoid being defrauded by direct future spend attempts of that output.

freetrader · April 16, 2021, 12:54pm

Why doesn’t a dsproof consist of just three fields:
(1) a 36-byte outpoint id of the ds,
(2) the raw transaction containing the ds, and
(3) the scriptPubKey of the ds.

“This gives us the opportunity to send only the intermediate hashes instead of the whole transaction while allowing receivers to still validate both signatures of the same public key.”

The reason is in order not to propagate the double spending transaction further than needed.

jscramer · April 16, 2021, 2:43pm

Thanks, Ok, understood.

Why not:
(1) 36-byte outpoint id of the ds,
(2) scriptPubKey
(3) scriptSig,
(4) array of signature digest preimages required (based on vm eval of script, 1 for p2pkh/p2pk, and N for p2sh)

freetrader · April 16, 2021, 3:59pm

Thought about it - not really sure anything speaks against doing it the way you describe.
It’s better that @tom comments on this matter of the design.

groot-verde · April 16, 2021, 5:06pm

I definitely welcome Tom to chime in as he may have additional insight but I think I can at least address what I think are the two biggest questions you’re asking with your suggestion:

Why not only send information about the double spend?

The reason for this is that nodes may not agree on which transaction is the double-spend. If two transactions, A and B, are sent to opposite ends of the network (so to speak), half of the network might receive A first and believe B to be “the double-spend transaction.” The other half that receives B first would think of A as the double-spender. When a node in the “A” part of the network creates a double-spend proof containing only information about B, nodes that have only seen B will not be convinced that there is a double-spend since the “proof” is identical to the transaction they already believe to be the proper spender.

By including the data for both A and B in the proof, all nodes will ultimately come to agreement that there is a double-spend in the network using the same, canonical, proof. Even if there is a node that received a third spender, C, it would receive the double-spend proof describing A and B and be convinced that the referenced output is indeed double-spent. So we prevent the proliferation of effectively duplicate double-spend proofs that could result from different nodes seeing different transactions first.

Why not include the locking script of the double-spent output?

Including the locking script of the output would help aid validation for nodes that don’t already have it, but could also open those nodes up to additional attacks. Since they are not able to verify that the locking script of the spent output is in fact the one present in the transaction (more on this later), false double-spend proofs could potentially be created to trick merchants into unnecessarily delaying the submitter of a valid transaction.

Suppose Bob has a grudge against Alice and wants to harass her. Alice buys a cup of coffee with BCH, spending a P2PKH output that Bob knows belongs to Alice. He immediately sends a double-spend proof to the merchant informing them that the locking script was OP_TRUE OP_DROP OP_DROP (or something along those lines) and generates two random values as the push data for the (fake) second spender. The merchant evaluates both scripts and sees that in both cases no signatures were necessary to validate the script, so the rest of the data isn’t relevant. The merchant is convinced that Alice has double-spent the output and makes her wait for a confirmation.

We could potentially prevent scenarios like this by providing proof that the locking script is indeed correct for the allegedly double-spent output. Barring changing the transaction format to allow for some sort of merkle-tree proof, that would mean including the full contents of the prior transaction so that the merchant can verify that it hashes correctly. This would make the double-spend proof potentially much larger. On top of that, an (SPV) recipient will still not necessarily know whether any of the referenced transactions are valid. If the original transaction is confirmed, a block hash could be included so the recipient could request a merkle block, and in that case the extra data should lead to increased confidence in the proof for SPV validators. So perhaps something along those lines would be possible. I suppose it’s ultimately a trade-off of extra data against the usefulness of having SPV nodes be able to sanely validate the double-spend proofs.

jscramer · April 16, 2021, 5:26pm

But the SPV client (merchant) would be able to match the double-spent outpoint with one of his unconfirmed txn’s inputs, so I’m thinking this isn’t true. Maybe context matters.

I thought the whole goal of dsproofs was for merchants to validate that there was a double spend proof. Nodes would and should still follow the first seen-rule and let the miners figure out which one to mine. We’re not doing some kind of avalanche thing where nodes need to sort it out. Am I wrong on the ultimate end-user of the dsproof? It would just be for the purposes of a single recipient of some payment, not for nodes.

Why wouldn’t nodes just forward a dsproof even if they think it’s the first seen? And let the merchant ultimately decide and let everyone be informed there’s a possible dsproof floating around. I guess this is because this would be a spam vector? Hmmmm.

In other words, if the merchant detects any dsproof that is an alternate spend of one of his payment inputs, then he cancels the order.

groot-verde · April 16, 2021, 5:28pm

I’m not sure whether we’re on the same page or not, but here are a few thoughts that might help figure out where things aren’t connecting:

To my knowledge SPV nodes are only relayed unconfirmed transactions that match their bloom filter. So in order for them to be certain that a transaction is valid, they potentially need knowledge of transactions that they don’t have.
In terms of matching the double-spend proof up to transactions that they do care about, that would be possible, but knowing how to resolve that is trickier. It doesn’t necessarily make the transaction they have invalid. It just means that they are less certain about its future.
Double-spend proofs are certainly intended to help support merchants, the question is whether or not they can reasonably do that in an SPV context. I certainly won’t rule out the possibility that it could be done, but unconfirmed transactions are already squishy territory for SPV nodes since they don’t really have an easy way to collect all of the information they would need to validate an arbitrary transaction (to my knowledge, they would have to add all the relevant outputs to their bloom filter and then potentially request merkle blocks until they found all the relevant transactions).
If nodes would forward double-spend proofs without knowledge (or proof of knowledge) of a second spending transaction, what would prevent bots from generating a double-spend proof immediately for every unconfirmed transaction? If you only have one transaction’s information it fails to be convincing and is therefore potentially just an attack.

jscramer · April 16, 2021, 5:46pm

Correct. But I thought it was established that there would be need to be some full node service that merchants subscribe to (either third-party or self-hosted). Whenever the merchant receives a payment, he would be subscribed all inputs of the received payment. I didn’t realize that being bloom filter compatible was a requirement. I’m pretty sure there are no wallets that use bloom filters anyways, Electron Cash subscribes to addresses on an individual basis.

Ok, I was thinking it would be a matter of matching dsproof up with one of the inputs they care about for are a payment they already received.

SPV context with bloom filters is hardly ever used IMO. I could be wrong, maybe we should survey what true SPV wallets are used in practice. Is EC classified as a true SPV wallet or is it a light wallet? Maybe bread wallet is true SPV? Not sure.

Right, yeah that makes sense. It makes me wonder if dsproofs can work without some kind of avalanche mechanism behind them. The avalanche wouldn’t affect the first-seen, rather it would just allow a node to decide if they should propogate the ds. I suppose no matter what you can’t prevent collusion with a miner, but this would be pretty rare and difficult to pull off.

Anyways, I’ll probably shut up now. I’m sure these are points that have already been thought through. Great work on this! It is pretty interesting to think about.

groot-verde · April 16, 2021, 6:11pm

Ah, I see the disconnect. You’re right that when I said SPV nodes I meant bloom-filter-based nodes. Given that, what we’re proposing is that those third-party services supporting the wallets perform whatever analysis/data collection is necessary and present the wallets with appropriate information to that they know how to handle the transaction. As far as I can tell, whether it’s the wallet or the third-party service is the one actually doing the double-spend proof validation is purely a matter of design/philosophy at that point.

The message format we’re proposing here would be used by the full nodes to communicate the double-spend throughout the network. Our goal with the modifications there was the keep the same general idea and expand it allow for a broader range of scripts. That plus the risk assessment for the third-party services/wallets will hopefully produce a much more secure unconfirmed transaction ecosystem, at least in the sense that merchants would get better guidance the risk associated with a given transaction, while still being able to quickly accept the most common types of transactions.

Hopefully that clears things up! Also, no worries! We wanted feedback on the idea and this was a fun conversation. I think you brought up a lot of important points that probably need better specified. Feel free to point out anything else that doesn’t make sense, it will only help improve the next version of this proposal (which will probably be a CHIP).

jscramer · April 16, 2021, 10:02pm

nodes would just ban a peer who is sending you ds proofs over a certain rate? Honest nodes would just stay under the threshold so they don’t get banned.

groot-verde · April 17, 2021, 12:54am

But why wouldn’t dishonest nodes just send you as many fake double-spend proofs as they can get away with? Maybe they’d have to be more targeted, or separate their efforts across more nodes, but they would likely still be effective at harassing others.

I actually misread your question when at first, but I think it might still bring up a good point, so apologies if the following isn’t helpful. But I am fully expecting that nodes sending invalid double-spend proofs would be banned for doing so. Fortunately, with the two spender scenario it is fairly easy to determine whether a double-spend proof is or is not valid upon receipt. If the two spender objects describe two different transactions that would allow for the referenced output to be spent, it is valid. If they don’t, it is invalid. A couple edge cases:

If the transaction is trivially double-spendable (e.g. a P2SH script that is basically just acting as a password and has no signatures), then it is would be easy to generate an alternate transaction that spends the same output. Doing so would be “wrong” in the sense that recipients would be informed of a double-spend that doesn’t exist, but theoretically a miner could swap the transaction out for one that steals the coins, so it may benefit the recipient.
In cases where a double-spend is possible because the signature hash type leaves the transaction malleable, the transaction could be double-spent without allowing for a double-spend proof. But the risk assessment we’ve described here would flag that transaction as risky for precisely that reason. Services like flipstarter, if I understand correctly, generate this type of transaction, so recipients of such multi-party transactions may end up waiting for a confirmation, but I’m guessing that’s unlikely to be a problem. And down the road we may come up with ways of forming such transactions so that they are known to be double-spend provable.

There may be some other edge-cases I’m not thinking of at the moment, but I think these are handled reasonable well. Definitely let me know if there are others that have less desirable outcomes (or if you disagree with my judgement of these cases).

However, if the double-spend proof only had a single transaction’s data in it, it would be much harder to determine whether you were sent a double-spend proof you received was invalid if you were only aware of the transaction it describes. You may learn that a double-spend transaction did exist if it’s mined in a block, but it’s impossible for you to know whether the creator of the double-spend proof actually received the other transaction first or was lying and got lucky. Similarly, if the transaction you were already aware of was mined in the next block, you have no way of knowing whether the miner (as opposed to the peer that sent the double-spend proof) happened to have the same first-seen transaction as you or if there was no double-spend and the creator was lying.

I’m interested in better understanding why you’re inclined toward double-spend proofs only specifying one transaction, but I’m not sure how you’d address the above with such a change. And if it’s not addressed I’d think I’d be hesitant to call them proofs, unless there’s something I’m missing.