BUIP135: (passed) Use OKCoin Donation to fund DoubleSpend Proofs

[theZerg]

BUIP135: Use OKCoin Donation to Fund Doublespend Proofs
Submitted by: Andrew Stone
Date: 15 Oct 2019

Recently Bitcoin Unlimited received approximately 9000USD from OKcoin to encourage BCH technological development. We want to put this generous funding to work straight away to benefit BCH and all its implementations. Voting YES for this BUIP will devote this money towards producing an implementation of DS (doublespend) proofs that:

1. Is enabled on Bitcoin Unlimited
   
   
2. Is MIT licensed and therefore available for adoption by any other full node implementation

In alignment with the BU goal to recognize and foster independent development, we propose to first offer this money to and work with the Flowee project. Flowee has implemented a GPLv3 licensed implementation of doublespend proofs, and may be willing to extract this portion of the Flowee code, offer it with an MIT license, and make some small proposed modifications (see technical details below).

If an agreement with Flowee cannot be reached, the Developer will evaluate proposals from any other applicants to find an alternative solution to providing this functionality.

Doublespend Proof Technical Details

There are currently two specifications on double spend proofs and one implementation within the larger BCH ecosystem.

Imaginary Username:
https://github.com/imaginaryusername/specs_n_stuff/blob/master/dsproof/dsproof.md

Flowee The Hub:
https://gitlab.com/snippets/1883331


Initial Considerations

One key difference in the specifications is in how the DS proofs are announced. Flowee specifies the DS proof identifier to be the double SHA256 of the entire doublespend proof. Imaginary Username specifies the DS proof identifier to be the SHA256 of the actual double spent outpoint.

Flowee’s DS proof identifier is a probabilistically unique identifier, similar to block and transaction identifiers. Imaginary Username’s identifier has an additional property, which is that different DS proofs that prove the same thing have the same hash. This is a very useful property for DS proofs to have, since nodes are only interested in what they prove, not the specifics of how (apart from verification). Imaginary Username’s formulation allows nodes to ignore DS proof messages based on the “INV” content, without actually downloading the proof.

However, we can do slightly better. The purpose of the hashing both specs propose is to create a probabilistically unique and short identifier. However, the data being hashed -- the outpoint -- consists of the double SHA256 hash of the prior input transaction and a 32bit index. This data is already probabilistically unique, so there’s no need to hash it again. Instead, let’s use the outpoint itself as the DS proof identifier. This allows more efficient handling of DS proof and DS proof INV messages (no hashing).

But probably most importantly, it allows recipients to easily determine whether the DS proof is relevant to any transactions that the recipient is interested in, when the INV is received. The recipient simply compares the announced data to the inputs of all its transactions looking for a match. If there is no match, a wallet does not need to request the full DS proof.


Secondary Considerations

Both specifications place DS proof announcements into INV messages along with any other object announcements. However, this means that the DS proof will be queued with the same priority as other transactions -- potentially waiting for the processing of the very transactions it’s trying to warn against.

Instead DS proof announcement handling should happen at higher priority than transaction announcements. While it would be possible to scan INV messages for DS proof announcements and extract them, this is inefficient and inconvenient.

A better solution is to place DS proof announcements in a separate message. These messages can then be isolated to a high priority handling queue immediately upon receipt, analogous to block and block headers message handling today.

Making a new message type is not hard. And the DS specification already requires new messages to handle transmission of DS proofs, so including another message type is a difference of degree, not kind.

 

[Tom Zander]

On the usage of the content of the double spend proof as a INV-hash:

this is useful to avoid re-downloading known invalid (previously failed) DSPs. A concept currently used in BU and others already for transactions and blocks. For instance if a BU node gets a BSV transaction, which fails due to missing outputs, then that iNV is put in the previously-failed list. This is the only place where we remember failing content in order to avoid re-download.

Similarly, there may be a valid-but-not-to-me double spend proof. For instance if an output is triple spend and thus there are two perfectly valid proofs. But only one will be accepted (first seen). And thus your change makes us promptly forget about the second and its hash. Which means that as more nodes send you that INV there is nothing that blocks you from re-downloading as you have no memory of rejecting it.

Then you continue into the suggestion to not use INV and GETDATA, which makes the previous point a little odd as your suggestion to hash stuff into a hash that can be used in INV is not needed if you make your own message to announce which output is being spent. If you want to avoid using INVs then you need not use the single hash either as a new message type can include anything.

Maybe it is indeed better to use a new message-type to announce it, but the INV system has spam protection and denial of service protection build in.

If you want to prioritize Double Spend Proofs, don't you think you'll end up reinventing the exact same rate limiting system to avoid denial of service based spamming of a node causing it to saturate the connection with only DSPs?

The system we have in place to do rate limiting of INVs does not, in actual fact, cause a problematic delay of a transaction moving though the network. Peter did the research on this and presented that in Italy. There is no difference for other types of INvs.

The maximum delay a single INV can possibly have is 5 seconds to any single peer. The probabilistic system makes the delay typically much less than that. BUT you are not connected to a single node that would propagate the proof. And you download it from the first that sends you the INV. So, the actual delay is not ranged between zero and 5 seconds. It is ranged between zero and 0.6sec (assuming 8 peers). So an average of 0.3 sec.

Next that, it is practically speaking useless to let a double spend proof outrace the transaction it is about, by introducing a new message format, as you need the transaction accepted and in your mempool to actually start to validate the DSP. So it would just end up waiting before it would get forwarded.


Too long didn't read:

* Using INV & GETDATA message types gives you the benefit of their build-in (D)DOS protection and there is no benefit to out-running a transaction as they wait at every peer anyway. So while making a new message type is possible, it doesn't have the benefit you seem to think it has.

* The usage of the hash of the content is there to avoid bandwidth waste, and its been in the client for ages. Change to a different INV-ID and you need to solve this problem again to avoid downloading the same thing from every one of your peers, only to immediately toss it again...

 

[Peter Tschipper]

"Next that, it is practically speaking useless to let a double spend proof outrace the transaction it is about, by introducing a new message format, as you need the transaction accepted and in your mempool to actually start to validate the DSP. So it would just end up waiting before it would get forwarded."

I don't think of it as being as much about racing the double spends as much as it's about getting the message sent when queue's are backed up, especially as we've seen when messages go over the GFC. So what we do in BU is to move certain p2p messages to the front of the message queue and make sure they get sent as the next message. This is beneficial for many other message types such as headers announcements and thin type blocks like graphene/xthins etc. It really helps speed up propagation and it's one of the limitation of compact blocks for instance which relies on INV/GETDATA messages.

 

[Tom Zander]

> as it's about getting the message sent when queue's are backed up

Isn't it so that if your scenario is true and there is a backlog that there is a good chance that you'll just make the double spend proof arrive before the actual transaction it is about? I'm not sure I see the benefit of that. Nodes won't process the DSP until the accompanying TX is there. It can't, it needs some info from that TX.

And while I understand you wish to somehow prioritize the double spend proof, and I agree that sounds smart, you have not addressed the core of my worry towards this suggestion.

The INV system in place today has solved several issues like avoiding denial of service attacks and the INV system managed to use the p2p system as a whisper-network (as opposed to a broadcast network).

If you want to bypass the queue and "go faster", then please do explain how we can still avoids denial of service attacks, a feature we get for free if we use INVs.

 

[solex]

As per previous discussion, this BUIP will be included in the November vote,

 

[theZerg]

Tom Zander and I have been in discussion and we have decided that the following terms are mutually satisfactory:

Tom Zander will produce a pull request into the Bitcoin Unlimited “dev” branch (https://github.com/BitcoinUnlimited/BitcoinUnlimited/tree/dev) that compiles, documents, and implements the Double Spend Proof Specification specified here: https://gitlab.com/snippets/1883331. The code in this pull request must be the integration of the new feature into the Bitcoin Unlimited full node software and include the DSP specification as an .md file.

All content in the pull request must be released under the MIT license and copyright Tom Zander <tomz@freedommail.ch>

When this work is completed and verified to accurately implement the DSP spec and have a functional client, BUIP135 will be considered fulfilled and Bitcoin Unlimited will send the equivalent of 9000USD in BCH or BTC to Tom Zander’s address specified below using the exchange rate on that day.

bitcoincash:qrzz5demzzadwd9r8zd70u6564crwvm52g8kdm9crx