[bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[rhavar]

[-- Attachment #1: Type: text/plain, Size: 5416 bytes --]

I've just finished writing an implementing of this, and extremely happy with how it turned out. So I'd like to go and try go down the path of more formally describing it and getting some comments and ultimately encourage its wide-spread use.

==Abstract==

The way bitcoin transactions are overwhelming used is known to leak more
information than desirable. This has lead to fungibility concerns in bitcoin
and a raise of unreasonably effective blockchain analysis.

Bustapay proposes a simple, practical way to bust these assumptions to immediate
benefit of the sender and recievers. Furthermore it does so in such a way that
helps recievers avoid utxo bloat, a constant problem for bitcoin merchants.

==Copyright==

This BIP is in the public domain.

==Motivation==

One of the most powerful heuristic's employed by those whose goal is to undermine
bitcoin's fungiblity has been to assume all inputs of a transaction are signed by
a single party. In the few cases this assumption does not hold, it is generally
readibly recognizable (e.g. traditional coinjoins have a very obvious structure,
or multisig outputs are most frequently validated onchain).

Bustapay requires no changes to bitcoin and creates bitcoin transactions that are
indistinguishable from normal ones.

It is worth noting that this specification has been intentionally kept as simple
as possible to encourage adoption. There are almost an endless amount of extensions
possible but the harder the implementation of clients/server the less likely it
will ever be done. Should bustapay enjoy widespread adoption, a "v2" specification
will be created with desired extensions.

==Specification==

A bustapay payment is made from a sender to a receiver.

Step 1. Sender creates a bitcoin transaction paying the receiver

This transaction must be fully valid, signed and all inputs must use segwit. This transaction is known as the "template transaction". This transaction must not be propagated on the bitcoin network.

Step 2. Sender gives the "template transaction" to the receiver

This would generally be done as an HTTP POST. The exact URL to submit it to could be specified with a bip21 encoded address. Such as bitcoin:2NABbUr9yeRCp1oUCtVmgJF8HGRCo3ifpTT?bustapay=https://bp.bustabit.com/submit and the HTTP body should be the raw transaction hex encoded as text.

Step 3. Receiver processes the transaction and returns a partially signed coinjoin

The receiver validates the transaction is valid, pays himself and is eligible for propation. The receiver then adds one of his own inputs (known as the "contributed input") and increase the output that pays himself by the contributed input amount. Doing so will invalidate the "template transaction"'s original input signatures, so the sender needs to return this "partial transaction" back to the receiver to sign. This is returned as a hex-encoded raw transaction a response to the original HTTP POST request.

Step 4. Receiver validates, re-signs, and propagates on the bitcoin network

The receiver is responsible in making sure the "partial transaction" returned by the sender was changed correctly (it should assume the connection has been MITM'd and act accordingly), resign its original inputs and propagates this transaction over the bitcoin network. The client must be aware that the server can reorder inputs and outputs.

Step 5. Receiver observes the finalized transaction on the bitcoin network

Once the receiver has seen the finalized transactions on the network (and has enough confirmations) it can process it like a normal payment for the sent amount (as opposed to the amount that it looks like on the network). If the receiver does not see the finalized transaction after a timeout will propagate the original "template transaction" to ensure the payment happens and function a strong anti-DoS mechanism.

=== Implementation Notes ===
For anyone wanting to implement bustapay payments, here are some notes for receivers:

* A transaction can easily be checked if it's suitable for the mempool with testmempoolaccept in bitcoin core 0.17
* Tracking transactions by txid is precarious. To keep your sanity make sure all inputs are segwit. But remember segwit does not prevent txid malleability unless you validate the transaction. So really make sure you're using testmempoolaccept at the very least
* Bustapay could be abused by a malicious party to query if you own a deposit address or not. So never accept a bustapay transaction that pays an already used deposit address
* You will need to keep a mapping of which utxos people have showed you and which you revealed. So if you see them again, you can reveal the same one of your own
* Check if the transaction was already sorted according to BIP69, if so ensure the result stays that way. Otherwise probably just shuffle the inputs/outpus

Notes for sending applications:

* The HTTP response must *not* be trusted. It should be fully validated that no unexpected changes have been made to the transaction.
* The sender should be aware the original "template transaction" may be propagated at any time, and in fact can intentionally be
  done so for the purpose of RBF as it should have a slightly higher fee rate.

== Credits ==
The idea is obviously based upon Dr. Maxwell's seminal CoinJoin proposal, and reduced scope inspired by a simplification of the "pay 2 endpoint" (now offline) blog post by blockstream.

-Ryan

[-- Attachment #2: Type: text/html, Size: 6789 bytes --]

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[Sjors Provoost]

[-- Attachment #1.1: Type: text/plain, Size: 5016 bytes --]


> Op 30 aug. 2018, om 22:24 heeft Ryan Havar via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> het volgende geschreven:
> 
> ==Motivation==
> 
> One of the most powerful heuristic's employed by those whose goal is to undermine
> bitcoin's fungiblity has been to assume all inputs of a transaction are signed by
> a single party. In the few cases this assumption does not hold, it is generally
> readibly recognizable (e.g. traditional coinjoins have a very obvious structure,
> or multisig outputs are most frequently validated onchain).

In addition to mixers, custodial wallets and exchanges also contribute to breaking this heuristic; even though there’s a single entity signing multiple inputs, that entity doesn’t represent a single owner of the funds. As with mixers, exchanges and custodial wallets can sometimes be spotted as well, but we don’t know what percentage is missed.

Breaking this heuristic at scale would be good, but do we know to what degree it’s already broken? Is there any empirical research measuring its accuracy and false positive rate?

> Should bustapay enjoy widespread adoption, a "v2" specification
> will be created with desired extensions.

I would not put future promises in a BIP. Rather, explain how extension might work.

> ==Specification==
> 
> A bustapay payment is made from a sender to a receiver.
> 
> Step 1. Sender creates a bitcoin transaction paying the receiver
> 
> This transaction must be fully valid, signed and all inputs must use segwit. This transaction is known as the "template transaction”.

Using PSBT?

> This transaction must not be propagated on the bitcoin network.

This can’t be guaranteed, and even after step 5 a reorg could cause it to get confirmed. It’s useful to explain why this doesn’t matter.

> 
> Step 2. Sender gives the "template transaction" to the receiver
> 
> This would generally be done as an HTTP POST.
> The exact URL to submit it to could be specified with a bip21 encoded address. Such as bitcoin:2NABbUr9yeRCp1oUCtVmgJF8HGRCo3ifpTT?bustapay=https://bp.bustabit.com/submit <https://bp.bustabit.com/submit> and the HTTP body should be the raw transaction hex encoded as text.

This seems too detailed. If you want to specify the message protocol, maybe that can have it’s own section where you list each of the messages, the URL, parameters and encoding. Then you can keep this overview section shorter.

The use of HTTPS kind of forces sender and recipient to use a 3rd party service, even though this could done bilaterally. What if the payment request contained a (single-use) Onion URL an expiration date? The recipient would have to keep a hidden service up until the expiration date, though the sender could try again if there’s temporary reachability issue.

Adding a (onion) URL to the the payment request also makes gradual adoption easier, because recipients don’t need to worry if senders support this protocol.

> Step 3. Receiver processes the transaction and returns a partially signed coinjoin
> 
> The receiver validates the transaction is valid, pays himself and is eligible for propation. The receiver then adds one of his own inputs (known as the "contributed input") and increase the output that pays himself by the contributed input amount. Doing so will invalidate the "template transaction"'s original input signatures, so the sender needs to return this "partial transaction" back to the receiver to sign. This is returned as a hex-encoded raw transaction a response to the original HTTP POST request.

> * Bustapay could be abused by a malicious party to query if you own a deposit address or not. So never accept a bustapay transaction that pays an already used deposit address


Indeed, once the recipient adds funds, they reveal more about themselves to the sender then they would otherwise. I think that needs more elaboration.

I assume the transaction in step (1) is some sort of collateral to insure they’re not just trying to extract private information from you? However if fees are low they could still double-spend it after the recipient revealed their address, especially because the recipient has no way of RBF’ing the original (though CPFP could help). Perhaps require that the original transaction pays a fee based on the expected size of the final transaction?

> 
> Notes for sending applications:
> 
> * The HTTP response must *not* be trusted. It should be fully validated that no unexpected changes have been made to the transaction.

Not trusting anything is obvious. :-) It’s better to explicitly state what exactly needs to be verified (amounts, destinations, inputs, etc), and maybe list a few obvious shenanigans to watch out for.

A more general concern is that the sender can’t know for sure the recipient really supports this protocol, so it should assume that whatever information it pings to some API could be used maliciously. In what ways could it be abused?

Sjors

[-- Attachment #1.2: Type: text/html, Size: 7305 bytes --]

[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[rhavar]

[-- Attachment #1: Type: text/plain, Size: 8136 bytes --]

Thanks Sjors,
It's nice to get hear feedback like that, it'll help make me clear some stuff up. Right now I've been working on getting a reference client for both sending and receiving, while juggling some stuff in real life.

But here is the evolving document:
https://github.com/RHavar/bips/blob/master/bip-bustapay.mediawiki

> Breaking this heuristic at scale would be good, but do we know to what degree it’s already broken? Is there any empirical research measuring its accuracy and false positive rate?

Not that I'm aware of. However from what I've seen of chainalysis, it's eerily accurate. I've seen it cluster wallets that it really shouldn't have been able to do. (address-reuse is actually the biggest culprit here, we really need to working on reducing stopping this with stuff like bip32 based address books, wallet warnings on reused addresses, etc.). As for false positives of block-chain analysis, under normal circumstances it probably shouldn't suffer any. Although it was pretty easy to confuse it with specially crafted coinjoin transactions, although a few months later seemed to realize and decluster the wallets again.

> In addition to mixers, custodial wallets and exchanges also contribute to breaking this heuristic

Well, kind of I guess. From a block-chain analysis point of view you'd be trying to figure out the transaction was to/from coinbase, rather than "coinbase on behalf of client XYZ". I guess the former is better than the later, but I think it'd be preferable if no one knew all together.

> Using PSBT?

I've got this feedback a lot, and I think it's definitely the way to go in the future. But at the moment compatibility and libraries are just not there that I'd like to stick with raw transactions for now.

> The use of HTTPS kind of forces sender and recipient to use a 3rd party service, even though this could done bilaterally.

I don't really understand this point. I just used https as an example, as I suspect that's what every merchant will want to use. I don't really mean to specify the protocol though, if the client/server support  it (e.g. onion)  then it should be fine.

> I assume the transaction in step (1) is some sort of collateral to insure they’re not just trying to extract private information from you?

It's not really designed as a sort of collateral, but as a way to prevent someone costlessly learning about one of your inputs. The cost is that of spending a utxo. An attacker can always trivially double spend the "template transaction" because from the network's point of view the "template transaction" will come after an alternate (say, non-rbf) spend.  But in practice I don't think this is a problem, because it still imposes a cost on the attacker.

> In what ways could it be abused?

I just want to make it clear that senders can't blindly sign a transaction without verifying it. The most important thing to verify is the output amounts/addresses -- but I will make it more explicit.

Thanks once again for your feedback

-Ryan

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Monday, 10 September 2018 05:30, Sjors Provoost <sjors@sprovoost.nl> wrote:

>> Op 30 aug. 2018, om 22:24 heeft Ryan Havar via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> het volgende geschreven:
>>
>> ==Motivation==
>>
>> One of the most powerful heuristic's employed by those whose goal is to undermine
>> bitcoin's fungiblity has been to assume all inputs of a transaction are signed by
>> a single party. In the few cases this assumption does not hold, it is generally
>> readibly recognizable (e.g. traditional coinjoins have a very obvious structure,
>> or multisig outputs are most frequently validated onchain).
>
> In addition to mixers, custodial wallets and exchanges also contribute to breaking this heuristic; even though there’s a single entity signing multiple inputs, that entity doesn’t represent a single owner of the funds. As with mixers, exchanges and custodial wallets can sometimes be spotted as well, but we don’t know what percentage is missed.
>
> Breaking this heuristic at scale would be good, but do we know to what degree it’s already broken? Is there any empirical research measuring its accuracy and false positive rate?
>
>> Should bustapay enjoy widespread adoption, a "v2" specification
>> will be created with desired extensions.
>
> I would not put future promises in a BIP. Rather, explain how extension might work.
>
>> ==Specification==
>>
>> A bustapay payment is made from a sender to a receiver.
>>
>> Step 1. Sender creates a bitcoin transaction paying the receiver
>>
>> This transaction must be fully valid, signed and all inputs must use segwit. This transaction is known as the "template transaction”.
>
> Using PSBT?
>
>> This transaction must not be propagated on the bitcoin network.
>
> This can’t be guaranteed, and even after step 5 a reorg could cause it to get confirmed. It’s useful to explain why this doesn’t matter.
>
>> Step 2. Sender gives the "template transaction" to the receiver
>>
>> This would generally be done as an HTTP POST.
>
>> The exact URL to submit it to could be specified with a bip21 encoded address. Such as bitcoin:2NABbUr9yeRCp1oUCtVmgJF8HGRCo3ifpTT?bustapay=https://bp.bustabit.com/submit and the HTTP body should be the raw transaction hex encoded as text.
>
> This seems too detailed. If you want to specify the message protocol, maybe that can have it’s own section where you list each of the messages, the URL, parameters and encoding. Then you can keep this overview section shorter.
>
> The use of HTTPS kind of forces sender and recipient to use a 3rd party service, even though this could done bilaterally. What if the payment request contained a (single-use) Onion URL an expiration date? The recipient would have to keep a hidden service up until the expiration date, though the sender could try again if there’s temporary reachability issue.
>
> Adding a (onion) URL to the the payment request also makes gradual adoption easier, because recipients don’t need to worry if senders support this protocol.
>
>> Step 3. Receiver processes the transaction and returns a partially signed coinjoin
>>
>> The receiver validates the transaction is valid, pays himself and is eligible for propation. The receiver then adds one of his own inputs (known as the "contributed input") and increase the output that pays himself by the contributed input amount. Doing so will invalidate the "template transaction"'s original input signatures, so the sender needs to return this "partial transaction" back to the receiver to sign. This is returned as a hex-encoded raw transaction a response to the original HTTP POST request.
>
>> * Bustapay could be abused by a malicious party to query if you own a deposit address or not. So never accept a bustapay transaction that pays an already used deposit address
>
> Indeed, once the recipient adds funds, they reveal more about themselves to the sender then they would otherwise. I think that needs more elaboration.
>
> I assume the transaction in step (1) is some sort of collateral to insure they’re not just trying to extract private information from you? However if fees are low they could still double-spend it after the recipient revealed their address, especially because the recipient has no way of RBF’ing the original (though CPFP could help). Perhaps require that the original transaction pays a fee based on the expected size of the final transaction?
>
>> Notes for sending applications:
>>
>> * The HTTP response must *not* be trusted. It should be fully validated that no unexpected changes have been made to the transaction.
>
> Not trusting anything is obvious. :-) It’s better to explicitly state what exactly needs to be verified (amounts, destinations, inputs, etc), and maybe list a few obvious shenanigans to watch out for.
>
> A more general concern is that the sender can’t know for sure the recipient really supports this protocol, so it should assume that whatever information it pings to some API could be used maliciously. In what ways could it be abused?
>
> Sjors

[-- Attachment #2: Type: text/html, Size: 10966 bytes --]

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[Adam Gibson]

Ryan and list,
I want to add some commentary to this (BIP79) to see if we can get
further in standardizing this idea.

When I first mulled it over I thought it too impractical, but its virtue
of steganographic hiding means only minimal uptake is still enormously
interesting and worth pursuing; that's my current feeling. I've offered
more detailed thoughts in my blog post[1] (def not required reading here).

Both Joinmarket and Samourai have started implementing this kind of
transaction. And while that's interesting experimentally, some kind of
cross-wallet standard would be helpful, albeit there some differences
between that and the merchant/centralized service use-case.

We might imagine as a concrete goal for this BIP to create something
that would be acceptable for inclusion into a project like BTCPayServer,
so that it could be used in a realistic use case by smaller bitcoin
accepting merchants.

Comments to the BIP[2] as follows, with generic comments first, and then
specific comments for existing points in the BIP:

[1] https://joinmarket.me/blog/blog/payjoin
[2] https://github.com/bitcoin/bips/blob/master/bip-0079.mediawiki

Generic comments
============
* Protocol versioning. Since inevitably (even if only merchants), this
must be implemented by multiple wallets to be useful, the communication
protocol will need versioning (for example i have in my
simple/experimental Joinmarket PayJoin that sender sends min and max
supported version and receiver responds with a chosen protocol version
so we can update). I do understand that as a client-server model can
apply here, we can ditch a lot of the complexities around network/p2p
interaction, but this much at least seems necessary.
* Although it has its logic, I don't think "Bustapay" is a good name for
this protocol. I prefer "PayJoin" which is neutral sounding and
self-descriptive. Needless to say this is not a hill I intend to die on.
* PSBT/BIP174. I realise this has already been discussed, but this is a
good example of what this standardisation was designed for, so I'd be
against not including it, even given the reality that, as you correctly
observe, it is not yet implemented in the majority of wallets and
libraries. One way round that is to make it optional (possibly combined
with above point about versioning). Note that for example you were
observing the necessity to check the sequence number was unchanged; that
would be encapsulated by checking equality of PSBT Input objects/fields.
While one can make such software architecture arguments, the really
fundamental point is the need for standards for x-wallet compatibility.
* Version, Locktime: Perhaps this is not needed; in a peer to peer
wallet scenario I think there might be logic in trying to get cover
traffic of (Core, Electrum, others), say, by using
last-block-locktime-mostly, as they do. Version should be 2 and sequence
is a function of your suggestion to use BIP125. Worth noting that BIP125
is *not* currently widely used on the network, though (see
https://p2sh.info/dashboard/db/replace-by-fee?orgId=1). For this reason
it should perhaps be explicitly only optional.
* Avoidance of non-payment "Unnecessary Input Heuristic" (1, 2). For
reference, see the definition here
https://gist.github.com/AdamISZ/4551b947789d3216bacfcb7af25e029e#gistcomment-2796539
and some data here
https://gist.github.com/AdamISZ/4551b947789d3216bacfcb7af25e029e#gistcomment-2800791
(whole comment thread may be of interest) - note this UIH name is afaik
Chris Belcher's invention, it seems useful as a categorisation.
 So, it seems that UIH2 is more important to avoid; while some more
sophisticated wallet coin selection algorithms *may* occasionally pick
an input set where one input is larger than any output, most won't, and
some in particular never will. So I think the text here should indicate
that *the receiver's contributed input(s) SHOULD be chosen to avoid
triggering the UIH2 heuristic where possible, so that the final payjoin
transaction is maximally plausible as an ordinary payment" or similar.
UIH1 is a nice-to-have (meaning the plausibility extends to two
different (both wrong) payment amounts, but it may not be necessary to
mention it in the BIP.


Specific comments
=================

>> ====Step 4. Receiver validates, re-signs, and propagates on the
bitcoin network====

I believe this should say "Sender" not Receiver. Also for the next
sentence, s/receiver/sender/:

>> The receiver MUST validate the ''partial transaction'' was changed
correctly and non-maliciously (to allow using potentially untrusted
communication channels), re-sign its original inputs and propagate the
final transaction over the bitcoin network.

Your very correct highlighting of the attack vector of "receiver gives
sender other inputs belonging to sender to unwittingly sign (described
below), should be highlighted here, perhaps with the phrase "re-sign its
ORIGINAL inputs" (only!)".

>> When the sender is creating a "template transaction" it is done
almost identically to creating a normal send, with the exception that
*only* segwit inputs may be used. The sender is also encouraged to use a
slightly more aggressive feerate than usual as well as BIP125 (Opt-in
Full Replace-by-Fee Signaling), but neither is strictly required.

"slightly more aggressive feerate than usual" - this I understand is to
make up for receiver contributed utxo, OK.

"*only* segwit inputs" - it certainly makes things simpler. One can work
with non-segwit inputs but especially considering (as mentioned below)
we really ought to "MUST" the part about matching input types, I tend to
agree that non-segwit should be disallowed.

>> The receiver must add at least one input to the transaction (the
"contributed inputs"). If the receiver has no inputs, it should use a
500 internal server error, so the client can send the transaction as per
normal (or try again later).

Would it not be much simpler for the server to return a different
(non-error) response indicating that it will broadcast the template tx
in this case?

>> Its generally advised to only add a single contributed input, however
they are circumstances where adding more than a single input can be useful.

I don't see a good reason to advise the use of only 1 input? (but this
will also connect with the above generic comment about "UIH"). I guess
it's because of your approach to fees. I'd prefer not to create a
limitation here.

>> To prevent an attack where a receiver is continually sent variations
of the same transaction to enumerate the receivers utxo set, it is
essential that the receiver always returns the same contributed inputs
when it's seen the same inputs.

This is an approach to avoiding this problem which has the virtue of
simplicity, but it seems a little problematic. (1) You must keep a
mapping of proposed payment utxos to one's proposed contributed input
utxos, but (2) how should this be updated if you need to spend the
contribution mentioned in (1)? Ironically use of payjoin exacerbates
this issue, because it results in a smaller number of utxos being held
by the receiver at any one time :) All this considered, I still see the
value in your approach, but it might end up with a re-attempted payment
being rejected. Certainly the more complex suggested solutions coming
out of the summer 2018 coinjoin workshop aren't as practical as this,
and may be overkill for small merchants/receivers.

>> It is strongly preferable that the receiver makes an effort to pick a
contributed input of the same type as the other transaction inputs if
possible.

I have also thought about this and you could reasonably argue this
should be a MUST section in the BIP, that is, if the receiver cannot use
inputs of the same type, he should fall back to the template
transaction. A mixed-input payjoin/coinjoin is essentially
near-perfectly identifiable as such (there is almost zero other usage of
multi-type-input transactions), which is a very different thing than a
non-identifiable payjoin transaction. That may or may not be OK to the
sender. This is debatable though, for sure.

>> After adding inputs to the transaction, the receiver generally will
want to adjust the output that pays himself by increasing it by the sum
of the contributed input amounts (minus any fees he wants to
contribute). However the only strict requirement is that the receiver
*must never* add or remove inputs, and *must not* ever decrease any
output amount.

"*must never* add or remove inputs" - did you mean "must never remove
inputs"? he surely has to add one! Or, perhaps you mean he must not
alter the list of inputs provided by the sender (in which case it should
be clarified).

"must not decrease any output amount" - I initally disagreed with this
but it is a better option than the one I currently chose in Joinmarket
payjoin (sender pays all fee as long as receiver utxos are not too
much). So this means that the receiver either consciously chooses to not
increase the fee, meaning the fee rate may be a bit low (hence your
earlier comment about being generous, got it), or contributes via the
payout amount. I guess the latter might break merchant software
expecting to have amount output fixed and fees determined by change.

Regards,
Adam Gibson/waxwing

On 30. 08. 18 22:24, Ryan Havar via bitcoin-dev wrote:
> I've just finished writing an implementing of this, and extremely happy
> with how it turned out. So I'd like to go and try go down the path of
> more formally describing it and getting some comments and ultimately
> encourage its wide-spread use.
> 
> 
> ==Abstract==
> 
> The way bitcoin transactions are overwhelming used is known to leak more
> information than desirable. This has lead to fungibility concerns in bitcoin
> and a raise of unreasonably effective blockchain analysis.
> 
> Bustapay proposes a simple, practical way to bust these assumptions to
> immediate
> benefit of the sender and recievers. Furthermore it does so in such a
> way that
> helps recievers avoid utxo bloat, a constant problem for bitcoin merchants.
> 
> ==Copyright==
> 
> This BIP is in the public domain.
> 
> ==Motivation==
> 
> One of the most powerful heuristic's employed by those whose goal is to
> undermine
> bitcoin's fungiblity has been to assume all inputs of a transaction are
> signed by
> a single party. In the few cases this assumption does not hold, it is
> generally
> readibly recognizable (e.g. traditional coinjoins have a very obvious
> structure,
> or multisig outputs are most frequently validated onchain).
> 
> Bustapay requires no changes to bitcoin and creates bitcoin transactions
> that are
> indistinguishable from normal ones.
> 
> It is worth noting that this specification has been intentionally kept
> as simple
> as possible to encourage adoption. There are almost an endless amount of
> extensions
> possible but the harder the implementation of clients/server the less
> likely it
> will ever be done. Should bustapay enjoy widespread adoption, a "v2"
> specification
> will be created with desired extensions.
> 
> ==Specification==
> 
> A bustapay payment is made from a sender to a receiver.
> 
> Step 1. Sender creates a bitcoin transaction paying the receiver
> 
> This transaction must be fully valid, signed and all inputs must use
> segwit. This transaction is known as the "template transaction". This
> transaction must not be propagated on the bitcoin network.
> 
> Step 2. Sender gives the "template transaction" to the receiver
> 
> This would generally be done as an HTTP POST. The exact URL to submit it
> to could be specified with a bip21 encoded address. Such as
> bitcoin:2NABbUr9yeRCp1oUCtVmgJF8HGRCo3ifpTT?bustapay=https://bp.bustabit.com/submit
> and the HTTP body should be the raw transaction hex encoded as text.
> 
> Step 3. Receiver processes the transaction and returns a partially
> signed coinjoin
> 
> The receiver validates the transaction is valid, pays himself and is
> eligible for propation. The receiver then adds one of his own inputs
> (known as the "contributed input") and increase the output that pays
> himself by the contributed input amount. Doing so will invalidate the
> "template transaction"'s original input signatures, so the sender needs
> to return this "partial transaction" back to the receiver to sign. This
> is returned as a hex-encoded raw transaction a response to the original
> HTTP POST request.
> 
> Step 4. Receiver validates, re-signs, and propagates on the bitcoin network
> 
> The receiver is responsible in making sure the "partial transaction"
> returned by the sender was changed correctly (it should assume the
> connection has been MITM'd and act accordingly), resign its original
> inputs and propagates this transaction over the bitcoin network. The
> client must be aware that the server can reorder inputs and outputs.
> 
> Step 5. Receiver observes the finalized transaction on the bitcoin network
> 
> Once the receiver has seen the finalized transactions on the network
> (and has enough confirmations) it can process it like a normal payment
> for the sent amount (as opposed to the amount that it looks like on the
> network). If the receiver does not see the finalized transaction after a
> timeout will propagate the original "template transaction" to ensure the
> payment happens and function a strong anti-DoS mechanism.
> 
> 
> === Implementation Notes ===
> For anyone wanting to implement bustapay payments, here are some notes
> for receivers:
> 
> * A transaction can easily be checked if it's suitable for the mempool
> with testmempoolaccept in bitcoin core 0.17
> * Tracking transactions by txid is precarious. To keep your sanity make
> sure all inputs are segwit. But remember segwit does not prevent txid
> malleability unless you validate the transaction. So really make sure
> you're using testmempoolaccept at the very least
> * Bustapay could be abused by a malicious party to query if you own a
> deposit address or not. So never accept a bustapay transaction that pays
> an already used deposit address
> * You will need to keep a mapping of which utxos people have showed you
> and which you revealed. So if you see them again, you can reveal the
> same one of your own
> * Check if the transaction was already sorted according to BIP69, if so
> ensure the result stays that way. Otherwise probably just shuffle the
> inputs/outpus
> 
> Notes for sending applications:
> 
> * The HTTP response must *not* be trusted. It should be fully validated
> that no unexpected changes have been made to the transaction.
> * The sender should be aware the original "template transaction" may be
> propagated at any time, and in fact can intentionally be
>   done so for the purpose of RBF as it should have a slightly higher fee
> rate.
> 
> == Credits ==
> The idea is obviously based upon Dr. Maxwell's seminal CoinJoin
> proposal, and reduced scope inspired by a simplification of the "pay 2
> endpoint" (now offline) blog post by blockstream.
> 
> 
> -Ryan
> 
> 
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[rhavar]

Thanks Adam,

I have fixed the mistakes you have pointed out: https://github.com/bitcoin/bips/pull/754

Thanks for the detailed look!

> but its virtue of steganographic hiding means only minimal uptake
> is still enormously interesting and worth pursuing; that's my current feeling.

I very much agree =) I really think anything that (silently) breaks the assumption of common ownership of transaction inputs offers outsized benefits for the whole ecosystem.

One other idea I have  is (way) better support for moving utxo's between wallets. The least controversial use case is moving funds between wallets you own. Like I might want to move *specific* utxo's from/to my joinmarket wallet, but not create a (privacy losing / expensive) transaction. Both core and joinmarket fail at this at a practical point of view.

Like imho it'd be pretty cool having a standardized format for (txid:vout:privatekey) with wallets showing it as "External UTXO" and preferentially spending it (and wallet not automatically importing any other utxo from that address).

Taken a bit further (this is the part which everyone hates) you could send someone money (or withdraw it from a service) by giving a person. It's not generally useful (for obvious reasons), but there's a lot of cases I think it's super cool.

---

Getting back on topic, without trying to do a point-by-point reply, I agree with pretty much everything you said but I am reluctant to make any changes.

I don't meant to be obtuse or anything, but I strongly believe the limiting factor to adoption to all these protocols is actually just getting people to implement it. I made multiple implementations of bustapay from both the sending/receiving end, so I could try develop the easiest to implement system that is still practical.

For instance I like PSBT and it's nice in theory. I actually had an original implementation using it, which is how I found some bugs in the core and golang version of PSBT). But in practice it's hugely overkill and significantly increases the implementation complexity complexity and is poorly supported. Switching to just a raw transaction actually made everything easier. (And that's not to criticise PSBT, I would definitely want to use it in other contexts).

Anyway, a big motivation for me even writing it as a BIP was to formalize my little anti-DOS trick of privately creating a "template transaction" which can just be dumped on the network as punishment. So if nothing else, hopefully I'll have demonstrated it's a pretty practical way of doing things.

--

Also your analysis on "Unnecessary Input Heuristic" is pretty cool, but I also don't like telling people to "avoid the UIH2" without providing the actual algo they should use. But really I think it's better off in a sort of article "how to pick contributed inputs" or something, as while it's nice it's not a huge deal and there's a lot of debatable tradeoffs that can/should be used. For instance the implementation I wrote for bustabit.com currently just heavily biases tainted inputs (e.g. ones associated with address reuse).



-Ryan

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Friday, January 25, 2019 6:47 AM, Adam Gibson via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

> Ryan and list,
> I want to add some commentary to this (BIP79) to see if we can get
> further in standardizing this idea.
>
> When I first mulled it over I thought it too impractical, but its virtue
> of steganographic hiding means only minimal uptake is still enormously
> interesting and worth pursuing; that's my current feeling. I've offered
> more detailed thoughts in my blog post[1] (def not required reading here).
>
> Both Joinmarket and Samourai have started implementing this kind of
> transaction. And while that's interesting experimentally, some kind of
> cross-wallet standard would be helpful, albeit there some differences
> between that and the merchant/centralized service use-case.
>
> We might imagine as a concrete goal for this BIP to create something
> that would be acceptable for inclusion into a project like BTCPayServer,
> so that it could be used in a realistic use case by smaller bitcoin
> accepting merchants.
>
> Comments to the BIP[2] as follows, with generic comments first, and then
> specific comments for existing points in the BIP:
>
> [1] https://joinmarket.me/blog/blog/payjoin
> [2] https://github.com/bitcoin/bips/blob/master/bip-0079.mediawiki
>
> Generic comments
>
> ==================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================
>
> -   Protocol versioning. Since inevitably (even if only merchants), this
>     must be implemented by multiple wallets to be useful, the communication
>     protocol will need versioning (for example i have in my
>     simple/experimental Joinmarket PayJoin that sender sends min and max
>     supported version and receiver responds with a chosen protocol version
>     so we can update). I do understand that as a client-server model can
>     apply here, we can ditch a lot of the complexities around network/p2p
>     interaction, but this much at least seems necessary.
>
> -   Although it has its logic, I don't think "Bustapay" is a good name for
>     this protocol. I prefer "PayJoin" which is neutral sounding and
>     self-descriptive. Needless to say this is not a hill I intend to die on.
>
> -   PSBT/BIP174. I realise this has already been discussed, but this is a
>     good example of what this standardisation was designed for, so I'd be
>     against not including it, even given the reality that, as you correctly
>     observe, it is not yet implemented in the majority of wallets and
>     libraries. One way round that is to make it optional (possibly combined
>     with above point about versioning). Note that for example you were
>     observing the necessity to check the sequence number was unchanged; that
>     would be encapsulated by checking equality of PSBT Input objects/fields.
>     While one can make such software architecture arguments, the really
>     fundamental point is the need for standards for x-wallet compatibility.
>
> -   Version, Locktime: Perhaps this is not needed; in a peer to peer
>     wallet scenario I think there might be logic in trying to get cover
>     traffic of (Core, Electrum, others), say, by using
>     last-block-locktime-mostly, as they do. Version should be 2 and sequence
>     is a function of your suggestion to use BIP125. Worth noting that BIP125
>     is not currently widely used on the network, though (see
>     https://p2sh.info/dashboard/db/replace-by-fee?orgId=1). For this reason
>     it should perhaps be explicitly only optional.
>
> -   Avoidance of non-payment "Unnecessary Input Heuristic" (1, 2). For
>     reference, see the definition here
>     https://gist.github.com/AdamISZ/4551b947789d3216bacfcb7af25e029e#gistcomment-2796539
>     and some data here
>     https://gist.github.com/AdamISZ/4551b947789d3216bacfcb7af25e029e#gistcomment-2800791
>     (whole comment thread may be of interest) - note this UIH name is afaik
>     Chris Belcher's invention, it seems useful as a categorisation.
>     So, it seems that UIH2 is more important to avoid; while some more
>     sophisticated wallet coin selection algorithms may occasionally pick
>     an input set where one input is larger than any output, most won't, and
>     some in particular never will. So I think the text here should indicate
>     that *the receiver's contributed input(s) SHOULD be chosen to avoid
>     triggering the UIH2 heuristic where possible, so that the final payjoin
>     transaction is maximally plausible as an ordinary payment" or similar.
>     UIH1 is a nice-to-have (meaning the plausibility extends to two
>     different (both wrong) payment amounts, but it may not be necessary to
>     mention it in the BIP.
>
>     Specific comments
>     =================
>
>
> > > ====Step 4. Receiver validates, re-signs, and propagates on the
>
> bitcoin network====
>
> I believe this should say "Sender" not Receiver. Also for the next
> sentence, s/receiver/sender/:
>
> > > The receiver MUST validate the ''partial transaction'' was changed
>
> correctly and non-maliciously (to allow using potentially untrusted
> communication channels), re-sign its original inputs and propagate the
> final transaction over the bitcoin network.
>
> Your very correct highlighting of the attack vector of "receiver gives
> sender other inputs belonging to sender to unwittingly sign (described
> below), should be highlighted here, perhaps with the phrase "re-sign its
> ORIGINAL inputs" (only!)".
>
> > > When the sender is creating a "template transaction" it is done
>
> almost identically to creating a normal send, with the exception that
> only segwit inputs may be used. The sender is also encouraged to use a
> slightly more aggressive feerate than usual as well as BIP125 (Opt-in
> Full Replace-by-Fee Signaling), but neither is strictly required.
>
> "slightly more aggressive feerate than usual" - this I understand is to
> make up for receiver contributed utxo, OK.
>
> "only segwit inputs" - it certainly makes things simpler. One can work
> with non-segwit inputs but especially considering (as mentioned below)
> we really ought to "MUST" the part about matching input types, I tend to
> agree that non-segwit should be disallowed.
>
> > > The receiver must add at least one input to the transaction (the
>
> "contributed inputs"). If the receiver has no inputs, it should use a
> 500 internal server error, so the client can send the transaction as per
> normal (or try again later).
>
> Would it not be much simpler for the server to return a different
> (non-error) response indicating that it will broadcast the template tx
> in this case?
>
> > > Its generally advised to only add a single contributed input, however
>
> they are circumstances where adding more than a single input can be useful.
>
> I don't see a good reason to advise the use of only 1 input? (but this
> will also connect with the above generic comment about "UIH"). I guess
> it's because of your approach to fees. I'd prefer not to create a
> limitation here.
>
> > > To prevent an attack where a receiver is continually sent variations
>
> of the same transaction to enumerate the receivers utxo set, it is
> essential that the receiver always returns the same contributed inputs
> when it's seen the same inputs.
>
> This is an approach to avoiding this problem which has the virtue of
> simplicity, but it seems a little problematic. (1) You must keep a
> mapping of proposed payment utxos to one's proposed contributed input
> utxos, but (2) how should this be updated if you need to spend the
> contribution mentioned in (1)? Ironically use of payjoin exacerbates
> this issue, because it results in a smaller number of utxos being held
> by the receiver at any one time :) All this considered, I still see the
> value in your approach, but it might end up with a re-attempted payment
> being rejected. Certainly the more complex suggested solutions coming
> out of the summer 2018 coinjoin workshop aren't as practical as this,
> and may be overkill for small merchants/receivers.
>
> > > It is strongly preferable that the receiver makes an effort to pick a
>
> contributed input of the same type as the other transaction inputs if
> possible.
>
> I have also thought about this and you could reasonably argue this
> should be a MUST section in the BIP, that is, if the receiver cannot use
> inputs of the same type, he should fall back to the template
> transaction. A mixed-input payjoin/coinjoin is essentially
> near-perfectly identifiable as such (there is almost zero other usage of
> multi-type-input transactions), which is a very different thing than a
> non-identifiable payjoin transaction. That may or may not be OK to the
> sender. This is debatable though, for sure.
>
> > > After adding inputs to the transaction, the receiver generally will
>
> want to adjust the output that pays himself by increasing it by the sum
> of the contributed input amounts (minus any fees he wants to
> contribute). However the only strict requirement is that the receiver
> must never add or remove inputs, and must not ever decrease any
> output amount.
>
> "must never add or remove inputs" - did you mean "must never remove
> inputs"? he surely has to add one! Or, perhaps you mean he must not
> alter the list of inputs provided by the sender (in which case it should
> be clarified).
>
> "must not decrease any output amount" - I initally disagreed with this
> but it is a better option than the one I currently chose in Joinmarket
> payjoin (sender pays all fee as long as receiver utxos are not too
> much). So this means that the receiver either consciously chooses to not
> increase the fee, meaning the fee rate may be a bit low (hence your
> earlier comment about being generous, got it), or contributes via the
> payout amount. I guess the latter might break merchant software
> expecting to have amount output fixed and fees determined by change.
>
> Regards,
> Adam Gibson/waxwing
>
> On 30. 08. 18 22:24, Ryan Havar via bitcoin-dev wrote:
>
> > I've just finished writing an implementing of this, and extremely happy
> > with how it turned out. So I'd like to go and try go down the path of
> > more formally describing it and getting some comments and ultimately
> > encourage its wide-spread use.
> > ==Abstract==
> > The way bitcoin transactions are overwhelming used is known to leak more
> > information than desirable. This has lead to fungibility concerns in bitcoin
> > and a raise of unreasonably effective blockchain analysis.
> > Bustapay proposes a simple, practical way to bust these assumptions to
> > immediate
> > benefit of the sender and recievers. Furthermore it does so in such a
> > way that
> > helps recievers avoid utxo bloat, a constant problem for bitcoin merchants.
> > ==Copyright==
> > This BIP is in the public domain.
> > ==Motivation==
> > One of the most powerful heuristic's employed by those whose goal is to
> > undermine
> > bitcoin's fungiblity has been to assume all inputs of a transaction are
> > signed by
> > a single party. In the few cases this assumption does not hold, it is
> > generally
> > readibly recognizable (e.g. traditional coinjoins have a very obvious
> > structure,
> > or multisig outputs are most frequently validated onchain).
> > Bustapay requires no changes to bitcoin and creates bitcoin transactions
> > that are
> > indistinguishable from normal ones.
> > It is worth noting that this specification has been intentionally kept
> > as simple
> > as possible to encourage adoption. There are almost an endless amount of
> > extensions
> > possible but the harder the implementation of clients/server the less
> > likely it
> > will ever be done. Should bustapay enjoy widespread adoption, a "v2"
> > specification
> > will be created with desired extensions.
> > ==Specification==
> > A bustapay payment is made from a sender to a receiver.
> > Step 1. Sender creates a bitcoin transaction paying the receiver
> > This transaction must be fully valid, signed and all inputs must use
> > segwit. This transaction is known as the "template transaction". This
> > transaction must not be propagated on the bitcoin network.
> > Step 2. Sender gives the "template transaction" to the receiver
> > This would generally be done as an HTTP POST. The exact URL to submit it
> > to could be specified with a bip21 encoded address. Such as
> > bitcoin:2NABbUr9yeRCp1oUCtVmgJF8HGRCo3ifpTT?bustapay=https://bp.bustabit.com/submit
> > and the HTTP body should be the raw transaction hex encoded as text.
> > Step 3. Receiver processes the transaction and returns a partially
> > signed coinjoin
> > The receiver validates the transaction is valid, pays himself and is
> > eligible for propation. The receiver then adds one of his own inputs
> > (known as the "contributed input") and increase the output that pays
> > himself by the contributed input amount. Doing so will invalidate the
> > "template transaction"'s original input signatures, so the sender needs
> > to return this "partial transaction" back to the receiver to sign. This
> > is returned as a hex-encoded raw transaction a response to the original
> > HTTP POST request.
> > Step 4. Receiver validates, re-signs, and propagates on the bitcoin network
> > The receiver is responsible in making sure the "partial transaction"
> > returned by the sender was changed correctly (it should assume the
> > connection has been MITM'd and act accordingly), resign its original
> > inputs and propagates this transaction over the bitcoin network. The
> > client must be aware that the server can reorder inputs and outputs.
> > Step 5. Receiver observes the finalized transaction on the bitcoin network
> > Once the receiver has seen the finalized transactions on the network
> > (and has enough confirmations) it can process it like a normal payment
> > for the sent amount (as opposed to the amount that it looks like on the
> > network). If the receiver does not see the finalized transaction after a
> > timeout will propagate the original "template transaction" to ensure the
> > payment happens and function a strong anti-DoS mechanism.
> > === Implementation Notes ===
> > For anyone wanting to implement bustapay payments, here are some notes
> > for receivers:
> >
> > -   A transaction can easily be checked if it's suitable for the mempool
> >     with testmempoolaccept in bitcoin core 0.17
> >
> > -   Tracking transactions by txid is precarious. To keep your sanity make
> >     sure all inputs are segwit. But remember segwit does not prevent txid
> >     malleability unless you validate the transaction. So really make sure
> >     you're using testmempoolaccept at the very least
> >
> > -   Bustapay could be abused by a malicious party to query if you own a
> >     deposit address or not. So never accept a bustapay transaction that pays
> >     an already used deposit address
> >
> > -   You will need to keep a mapping of which utxos people have showed you
> >     and which you revealed. So if you see them again, you can reveal the
> >     same one of your own
> >
> > -   Check if the transaction was already sorted according to BIP69, if so
> >     ensure the result stays that way. Otherwise probably just shuffle the
> >     inputs/outpus
> >
> >
> > Notes for sending applications:
> >
> > -   The HTTP response must not be trusted. It should be fully validated
> >     that no unexpected changes have been made to the transaction.
> >
> > -   The sender should be aware the original "template transaction" may be
> >     propagated at any time, and in fact can intentionally be
> >       done so for the purpose of RBF as it should have a slightly higher fee
> >     rate.
> >
> >
> > == Credits ==
> > The idea is obviously based upon Dr. Maxwell's seminal CoinJoin
> > proposal, and reduced scope inspired by a simplification of the "pay 2
> > endpoint" (now offline) blog post by blockstream.
> > -Ryan
> >
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[Adam Gibson]

On 27. 01. 19 8:36, rhavar@protonmail.com wrote:
> Thanks Adam,
> 
> I have fixed the mistakes you have pointed out: https://github.com/bitcoin/bips/pull/754
> 
> Thanks for the detailed look!
> 
>> but its virtue of steganographic hiding means only minimal uptake
>> is still enormously interesting and worth pursuing; that's my current feeling.
> 
> I very much agree =) I really think anything that (silently) breaks the assumption of common ownership of transaction inputs offers outsized benefits for the whole ecosystem.
> 
> One other idea I have  is (way) better support for moving utxo's between wallets. The least controversial use case is moving funds between wallets you own. Like I might want to move *specific* utxo's from/to my joinmarket wallet, but not create a (privacy losing / expensive) transaction. Both core and joinmarket fail at this at a practical point of view.

(tangential, but yes coin control in JM is an obviously necessary
feature and will be done, I just don't have time).

> 
> Like imho it'd be pretty cool having a standardized format for (txid:vout:privatekey) with wallets showing it as "External UTXO" and preferentially spending it (and wallet not automatically importing any other utxo from that address).
> 
> Taken a bit further (this is the part which everyone hates) you could send someone money (or withdraw it from a service) by giving a person. It's not generally useful (for obvious reasons), but there's a lot of cases I think it's super cool.

Is there a missing word. "by giving a person.."? Not actually sure what
you're getting at here but I suspect it's again tangential to this BIP
discussion.

> 
> ---
> 
> Getting back on topic, without trying to do a point-by-point reply, I agree with pretty much everything you said but I am reluctant to make any changes.
> 
> I don't meant to be obtuse or anything, but I strongly believe the limiting factor to adoption to all these protocols is actually just getting people to implement it. I made multiple implementations of bustapay from both the sending/receiving end, so I could try develop the easiest to implement system that is still practical.

You know, there's considerable evidence to the contrary, I'd argue: this
idea *has* been implemented already three times: by yourself, by myself
and by Samourai. And in fully incompatible ways :) So I think the
limiting factor is in fact creating a standard that a reasonable number
of people could agree with (and I like operational definitions, so
subjective as it is, I like the goal of "good/clear enough that it could
be incorporated into something like BtcPayServer")

> 
> For instance I like PSBT and it's nice in theory. I actually had an original implementation using it, which is how I found some bugs in the core and golang version of PSBT). But in practice it's hugely overkill and significantly increases the implementation complexity complexity and is poorly supported. Switching to just a raw transaction actually made everything easier. (And that's not to criticise PSBT, I would definitely want to use it in other contexts).

But this relates back to my first "generic" point that you haven't
addressed here - protocol versioning and the possibility of more than
one option. Perhaps more realistic (debatable): have the current version
be non-PSBT but with a plan to have a version bump with PSBT in future.
Stuff like that. It seems crazy to actually long term reject it.

> 
> Anyway, a big motivation for me even writing it as a BIP was to formalize my little anti-DOS trick of privately creating a "template transaction" which can just be dumped on the network as punishment. So if nothing else, hopefully I'll have demonstrated it's a pretty practical way of doing things.
> 

I don't want to be that guy, but this was a central part of the proposal
that came of the meetup last summer and is in Haywood's blogpost. I mean
if you came up it with separately, then cool :) But I was there, that
was established immediately as the right way of doing this to avoid a
trivial attack.
What might have confused you is all that stuff about multiple candidates
and even ZKP approaches - those were just extra ideas about making it
really secure at large scale; but those ideas don't quite meet the goal
(for various reasons); well, arguably. The basic anti-DOS of an initial
non-coinjoin was sorta central.
(Also I'm noting you didn't respond to my critique of your "always use
the same contributions" defence; I mean, probably that's fine, it was
only really saying it isn't perfect. Was just curious to hear
your/others thoughts on it).

> --
> 
> Also your analysis on "Unnecessary Input Heuristic" is pretty cool, but I also don't like telling people to "avoid the UIH2" without providing the actual algo they should use. But really I think it's better off in a sort of article "how to pick contributed inputs" or something, as while it's nice it's not a huge deal and there's a lot of debatable tradeoffs that can/should be used. For instance the implementation I wrote for bustabit.com currently just heavily biases tainted inputs (e.g. ones associated with address reuse).
> 

Good point about algo.
I wrote my best effort at a procedure here:
https://gist.github.com/AdamISZ/4551b947789d3216bacfcb7af25e029e#gistcomment-2799709

I asked for comments on it but got none back so far (gists are terrible
for this unfortunately, perhaps I'll have more luck on the list).

I would argue that this issue *should* be mentioned on the BIP. A *huge*
part of what makes PayJoin/BustaPay of interest is the steganographic
feature, if you don't pay attention to this then it doesn't look like a
payment (caveat.-->).
The counterargument is Laurent's statistics which I previously linked,
suggesting that maybe 30% of txs violate this anyway, today. I'm not
sure about that, will need more analysis; Core's SRD algo may be one
reason, but anyway ... better to make things look like payments.

It doesn't hurt to prompt an implementer to do this; whether it's
feasible in that specific wallet situation or not is up to them; whether
they want to go hog wild and control percentages of UIH1 and UIH2 and
whatnot is there business, or they can totally ignore it - but without
it being mentioned in the BIP, they may not even think of it.

A last point, you also don't see value in being more explicit about
simple things like transaction version and locktime? Even if you think
these things should *not* be controlled, e.g. the protocol should allow
either transaction version, then it'd be better to explicitly say so.
> 
> 
> -Ryan
> 
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> On Friday, January 25, 2019 6:47 AM, Adam Gibson via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
>> Ryan and list,
>> I want to add some commentary to this (BIP79) to see if we can get
>> further in standardizing this idea.
>>
>> When I first mulled it over I thought it too impractical, but its virtue
>> of steganographic hiding means only minimal uptake is still enormously
>> interesting and worth pursuing; that's my current feeling. I've offered
>> more detailed thoughts in my blog post[1] (def not required reading here).
>>
>> Both Joinmarket and Samourai have started implementing this kind of
>> transaction. And while that's interesting experimentally, some kind of
>> cross-wallet standard would be helpful, albeit there some differences
>> between that and the merchant/centralized service use-case.
>>
>> We might imagine as a concrete goal for this BIP to create something
>> that would be acceptable for inclusion into a project like BTCPayServer,
>> so that it could be used in a realistic use case by smaller bitcoin
>> accepting merchants.
>>
>> Comments to the BIP[2] as follows, with generic comments first, and then
>> specific comments for existing points in the BIP:
>>
>> [1] https://joinmarket.me/blog/blog/payjoin
>> [2] https://github.com/bitcoin/bips/blob/master/bip-0079.mediawiki
>>
>> Generic comments
>>
>> ==================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================
>>
>> -   Protocol versioning. Since inevitably (even if only merchants), this
>>     must be implemented by multiple wallets to be useful, the communication
>>     protocol will need versioning (for example i have in my
>>     simple/experimental Joinmarket PayJoin that sender sends min and max
>>     supported version and receiver responds with a chosen protocol version
>>     so we can update). I do understand that as a client-server model can
>>     apply here, we can ditch a lot of the complexities around network/p2p
>>     interaction, but this much at least seems necessary.
>>
>> -   Although it has its logic, I don't think "Bustapay" is a good name for
>>     this protocol. I prefer "PayJoin" which is neutral sounding and
>>     self-descriptive. Needless to say this is not a hill I intend to die on.
>>
>> -   PSBT/BIP174. I realise this has already been discussed, but this is a
>>     good example of what this standardisation was designed for, so I'd be
>>     against not including it, even given the reality that, as you correctly
>>     observe, it is not yet implemented in the majority of wallets and
>>     libraries. One way round that is to make it optional (possibly combined
>>     with above point about versioning). Note that for example you were
>>     observing the necessity to check the sequence number was unchanged; that
>>     would be encapsulated by checking equality of PSBT Input objects/fields.
>>     While one can make such software architecture arguments, the really
>>     fundamental point is the need for standards for x-wallet compatibility.
>>
>> -   Version, Locktime: Perhaps this is not needed; in a peer to peer
>>     wallet scenario I think there might be logic in trying to get cover
>>     traffic of (Core, Electrum, others), say, by using
>>     last-block-locktime-mostly, as they do. Version should be 2 and sequence
>>     is a function of your suggestion to use BIP125. Worth noting that BIP125
>>     is not currently widely used on the network, though (see
>>     https://p2sh.info/dashboard/db/replace-by-fee?orgId=1). For this reason
>>     it should perhaps be explicitly only optional.
>>
>> -   Avoidance of non-payment "Unnecessary Input Heuristic" (1, 2). For
>>     reference, see the definition here
>>     https://gist.github.com/AdamISZ/4551b947789d3216bacfcb7af25e029e#gistcomment-2796539
>>     and some data here
>>     https://gist.github.com/AdamISZ/4551b947789d3216bacfcb7af25e029e#gistcomment-2800791
>>     (whole comment thread may be of interest) - note this UIH name is afaik
>>     Chris Belcher's invention, it seems useful as a categorisation.
>>     So, it seems that UIH2 is more important to avoid; while some more
>>     sophisticated wallet coin selection algorithms may occasionally pick
>>     an input set where one input is larger than any output, most won't, and
>>     some in particular never will. So I think the text here should indicate
>>     that *the receiver's contributed input(s) SHOULD be chosen to avoid
>>     triggering the UIH2 heuristic where possible, so that the final payjoin
>>     transaction is maximally plausible as an ordinary payment" or similar.
>>     UIH1 is a nice-to-have (meaning the plausibility extends to two
>>     different (both wrong) payment amounts, but it may not be necessary to
>>     mention it in the BIP.
>>
>>     Specific comments
>>     =================
>>
>>
>>>> ====Step 4. Receiver validates, re-signs, and propagates on the
>>
>> bitcoin network====
>>
>> I believe this should say "Sender" not Receiver. Also for the next
>> sentence, s/receiver/sender/:
>>
>>>> The receiver MUST validate the ''partial transaction'' was changed
>>
>> correctly and non-maliciously (to allow using potentially untrusted
>> communication channels), re-sign its original inputs and propagate the
>> final transaction over the bitcoin network.
>>
>> Your very correct highlighting of the attack vector of "receiver gives
>> sender other inputs belonging to sender to unwittingly sign (described
>> below), should be highlighted here, perhaps with the phrase "re-sign its
>> ORIGINAL inputs" (only!)".
>>
>>>> When the sender is creating a "template transaction" it is done
>>
>> almost identically to creating a normal send, with the exception that
>> only segwit inputs may be used. The sender is also encouraged to use a
>> slightly more aggressive feerate than usual as well as BIP125 (Opt-in
>> Full Replace-by-Fee Signaling), but neither is strictly required.
>>
>> "slightly more aggressive feerate than usual" - this I understand is to
>> make up for receiver contributed utxo, OK.
>>
>> "only segwit inputs" - it certainly makes things simpler. One can work
>> with non-segwit inputs but especially considering (as mentioned below)
>> we really ought to "MUST" the part about matching input types, I tend to
>> agree that non-segwit should be disallowed.
>>
>>>> The receiver must add at least one input to the transaction (the
>>
>> "contributed inputs"). If the receiver has no inputs, it should use a
>> 500 internal server error, so the client can send the transaction as per
>> normal (or try again later).
>>
>> Would it not be much simpler for the server to return a different
>> (non-error) response indicating that it will broadcast the template tx
>> in this case?
>>
>>>> Its generally advised to only add a single contributed input, however
>>
>> they are circumstances where adding more than a single input can be useful.
>>
>> I don't see a good reason to advise the use of only 1 input? (but this
>> will also connect with the above generic comment about "UIH"). I guess
>> it's because of your approach to fees. I'd prefer not to create a
>> limitation here.
>>
>>>> To prevent an attack where a receiver is continually sent variations
>>
>> of the same transaction to enumerate the receivers utxo set, it is
>> essential that the receiver always returns the same contributed inputs
>> when it's seen the same inputs.
>>
>> This is an approach to avoiding this problem which has the virtue of
>> simplicity, but it seems a little problematic. (1) You must keep a
>> mapping of proposed payment utxos to one's proposed contributed input
>> utxos, but (2) how should this be updated if you need to spend the
>> contribution mentioned in (1)? Ironically use of payjoin exacerbates
>> this issue, because it results in a smaller number of utxos being held
>> by the receiver at any one time :) All this considered, I still see the
>> value in your approach, but it might end up with a re-attempted payment
>> being rejected. Certainly the more complex suggested solutions coming
>> out of the summer 2018 coinjoin workshop aren't as practical as this,
>> and may be overkill for small merchants/receivers.
>>
>>>> It is strongly preferable that the receiver makes an effort to pick a
>>
>> contributed input of the same type as the other transaction inputs if
>> possible.
>>
>> I have also thought about this and you could reasonably argue this
>> should be a MUST section in the BIP, that is, if the receiver cannot use
>> inputs of the same type, he should fall back to the template
>> transaction. A mixed-input payjoin/coinjoin is essentially
>> near-perfectly identifiable as such (there is almost zero other usage of
>> multi-type-input transactions), which is a very different thing than a
>> non-identifiable payjoin transaction. That may or may not be OK to the
>> sender. This is debatable though, for sure.
>>
>>>> After adding inputs to the transaction, the receiver generally will
>>
>> want to adjust the output that pays himself by increasing it by the sum
>> of the contributed input amounts (minus any fees he wants to
>> contribute). However the only strict requirement is that the receiver
>> must never add or remove inputs, and must not ever decrease any
>> output amount.
>>
>> "must never add or remove inputs" - did you mean "must never remove
>> inputs"? he surely has to add one! Or, perhaps you mean he must not
>> alter the list of inputs provided by the sender (in which case it should
>> be clarified).
>>
>> "must not decrease any output amount" - I initally disagreed with this
>> but it is a better option than the one I currently chose in Joinmarket
>> payjoin (sender pays all fee as long as receiver utxos are not too
>> much). So this means that the receiver either consciously chooses to not
>> increase the fee, meaning the fee rate may be a bit low (hence your
>> earlier comment about being generous, got it), or contributes via the
>> payout amount. I guess the latter might break merchant software
>> expecting to have amount output fixed and fees determined by change.
>>
>> Regards,
>> Adam Gibson/waxwing
>>
>> On 30. 08. 18 22:24, Ryan Havar via bitcoin-dev wrote:
>>
>>> I've just finished writing an implementing of this, and extremely happy
>>> with how it turned out. So I'd like to go and try go down the path of
>>> more formally describing it and getting some comments and ultimately
>>> encourage its wide-spread use.
>>> ==Abstract==
>>> The way bitcoin transactions are overwhelming used is known to leak more
>>> information than desirable. This has lead to fungibility concerns in bitcoin
>>> and a raise of unreasonably effective blockchain analysis.
>>> Bustapay proposes a simple, practical way to bust these assumptions to
>>> immediate
>>> benefit of the sender and recievers. Furthermore it does so in such a
>>> way that
>>> helps recievers avoid utxo bloat, a constant problem for bitcoin merchants.
>>> ==Copyright==
>>> This BIP is in the public domain.
>>> ==Motivation==
>>> One of the most powerful heuristic's employed by those whose goal is to
>>> undermine
>>> bitcoin's fungiblity has been to assume all inputs of a transaction are
>>> signed by
>>> a single party. In the few cases this assumption does not hold, it is
>>> generally
>>> readibly recognizable (e.g. traditional coinjoins have a very obvious
>>> structure,
>>> or multisig outputs are most frequently validated onchain).
>>> Bustapay requires no changes to bitcoin and creates bitcoin transactions
>>> that are
>>> indistinguishable from normal ones.
>>> It is worth noting that this specification has been intentionally kept
>>> as simple
>>> as possible to encourage adoption. There are almost an endless amount of
>>> extensions
>>> possible but the harder the implementation of clients/server the less
>>> likely it
>>> will ever be done. Should bustapay enjoy widespread adoption, a "v2"
>>> specification
>>> will be created with desired extensions.
>>> ==Specification==
>>> A bustapay payment is made from a sender to a receiver.
>>> Step 1. Sender creates a bitcoin transaction paying the receiver
>>> This transaction must be fully valid, signed and all inputs must use
>>> segwit. This transaction is known as the "template transaction". This
>>> transaction must not be propagated on the bitcoin network.
>>> Step 2. Sender gives the "template transaction" to the receiver
>>> This would generally be done as an HTTP POST. The exact URL to submit it
>>> to could be specified with a bip21 encoded address. Such as
>>> bitcoin:2NABbUr9yeRCp1oUCtVmgJF8HGRCo3ifpTT?bustapay=https://bp.bustabit.com/submit
>>> and the HTTP body should be the raw transaction hex encoded as text.
>>> Step 3. Receiver processes the transaction and returns a partially
>>> signed coinjoin
>>> The receiver validates the transaction is valid, pays himself and is
>>> eligible for propation. The receiver then adds one of his own inputs
>>> (known as the "contributed input") and increase the output that pays
>>> himself by the contributed input amount. Doing so will invalidate the
>>> "template transaction"'s original input signatures, so the sender needs
>>> to return this "partial transaction" back to the receiver to sign. This
>>> is returned as a hex-encoded raw transaction a response to the original
>>> HTTP POST request.
>>> Step 4. Receiver validates, re-signs, and propagates on the bitcoin network
>>> The receiver is responsible in making sure the "partial transaction"
>>> returned by the sender was changed correctly (it should assume the
>>> connection has been MITM'd and act accordingly), resign its original
>>> inputs and propagates this transaction over the bitcoin network. The
>>> client must be aware that the server can reorder inputs and outputs.
>>> Step 5. Receiver observes the finalized transaction on the bitcoin network
>>> Once the receiver has seen the finalized transactions on the network
>>> (and has enough confirmations) it can process it like a normal payment
>>> for the sent amount (as opposed to the amount that it looks like on the
>>> network). If the receiver does not see the finalized transaction after a
>>> timeout will propagate the original "template transaction" to ensure the
>>> payment happens and function a strong anti-DoS mechanism.
>>> === Implementation Notes ===
>>> For anyone wanting to implement bustapay payments, here are some notes
>>> for receivers:
>>>
>>> -   A transaction can easily be checked if it's suitable for the mempool
>>>     with testmempoolaccept in bitcoin core 0.17
>>>
>>> -   Tracking transactions by txid is precarious. To keep your sanity make
>>>     sure all inputs are segwit. But remember segwit does not prevent txid
>>>     malleability unless you validate the transaction. So really make sure
>>>     you're using testmempoolaccept at the very least
>>>
>>> -   Bustapay could be abused by a malicious party to query if you own a
>>>     deposit address or not. So never accept a bustapay transaction that pays
>>>     an already used deposit address
>>>
>>> -   You will need to keep a mapping of which utxos people have showed you
>>>     and which you revealed. So if you see them again, you can reveal the
>>>     same one of your own
>>>
>>> -   Check if the transaction was already sorted according to BIP69, if so
>>>     ensure the result stays that way. Otherwise probably just shuffle the
>>>     inputs/outpus
>>>
>>>
>>> Notes for sending applications:
>>>
>>> -   The HTTP response must not be trusted. It should be fully validated
>>>     that no unexpected changes have been made to the transaction.
>>>
>>> -   The sender should be aware the original "template transaction" may be
>>>     propagated at any time, and in fact can intentionally be
>>>       done so for the purpose of RBF as it should have a slightly higher fee
>>>     rate.
>>>
>>>
>>> == Credits ==
>>> The idea is obviously based upon Dr. Maxwell's seminal CoinJoin
>>> proposal, and reduced scope inspired by a simplification of the "pay 2
>>> endpoint" (now offline) blog post by blockstream.
>>> -Ryan
>>>
>>> bitcoin-dev mailing list
>>> bitcoin-dev@lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[rhavar]

> Is there a missing word. "by giving a person.."? Not actually sure what
> you're getting at here but I suspect it's again tangential to this BIP
> discussion.

Correct on both points. I meant to say "giving a (txid:vout:privkey)" to a person as means of payment.


> So I think the limiting factor is in fact creating a standard that a reasonable number
> of people could agree with (and I like operational definitions, so
> subjective as it is, I like the goal of "good/clear enough that it could
> be incorporated into something like BtcPayServer")


The problem with BtcPayServer (and a lot of similar software), is that it's not very unsuitable for any sender/receiver coinjoin due to it not having its own wallet. As I understand the basic architecture is just a fancy wrapper around bip32 address generation and monitoring the payment to those addresses. This means that adding support is not only a large code change, but it also entails a substantial change for merchants (you can't just have your payments flow into your trezor, but need to run a hot wallet)

But I strongly believe that bustapay is good enough _right now_ for BtcPayServer integration (which I'd happily contribute myself, if it wasn't for my unfamiliarity of the project and c#)


> But this relates back to my first "generic" point that you haven't
> addressed here - protocol versioning and the possibility of more than
> one option. Perhaps more realistic (debatable): have the current version
> be non-PSBT but with a plan to have a version bump with PSBT in future.
> Stuff like that. It seems crazy to actually long term reject it.

Adding backwards-compatible versioning at a later stage would be pretty trivial through either the URL or HTTP header (e.g  version=2)  and if breaking backwards compatible is desirable it can also easily been done (e.g. bump the bip21 or send an incompatible request/response). I don't see this as a problem at all, and I'm not rejecting it long-term, I just don't think it's particularly helpful to bikeshed now, when adoption is pretty much zero.



> I don't want to be that guy, but this was a central part of the proposal
> that came of the meetup last summer and is in Haywood's blogpost. I mean
> if you came up it with separately, then cool :) But I was there, that
> was established immediately as the right way of doing this to avoid a
> trivial attack.

Oh wow. had no idea. I saw the part about the receiver spamming the sender with a bunch of transactions, where only 1 of them are real and thought "ewww" and "came up" with the idea of a "template transaction" instead. I was always wondering why no one came up it, but now it makes sense. The transaction-spam stage was just an _additional_ layer of protection.

Ok, now I feel like an idiot =)  Thanks for letting me know.


> The counterargument is Laurent's statistics which I previously linked,
> suggesting that maybe 30% of txs violate this anyway, today. I'm not
> sure about that, will need more analysis; Core's SRD algo may be one
> reason, but anyway ... better to make things look like payments.

I think it's interesting, but I don't think it particularly matters. Avoiding UIH1 I think is pretty much irrelevant, as it'll likely just confuse any analysis into thinking the payment is the reverse of what it actually is. And wallets already don't care about violating UIH2(as a way to do implicit consolidation). If 30% of tx's are violating it, you can be pretty sure it means the _vast majority_ of wallets run coin selection in such a way that can violation UIH2.  Most wallets use a coin selection algorithm that you can approximate with:

while !enoughMoney {
    inputs += getAnotherInput();
}

and don't run a final pass that would prune superfluous inputs.  Even coinsayer (shill alert) which I believe runs the most advanced coin selection algorithms, will routinely and intentionally violate UIH2 when it's ideal (e.g. most classic case: when `consolidationFeeRate >= minFeeRate`).

I'm not trying to dismiss your analysis, as I find it interesting. I'm just against increasing the cognitive burden on implementations by mentioning all this stuff, when the truth is it (barely) matters.  If wallets routinely avoided UIH2 and making a UIH2 payment would "out" the transaction as much more likely to be a bustapay, then I'd definitely reconsider and provide a basic suggestion into how to try avoid it.

And like I said, I also think there's much more important things that go into "picking a contributed input" than just this.



> A last point, you also don't see value in being more explicit about
> simple things like transaction version and locktime? Even if you think
> these things should not be controlled, e.g. the protocol should allow
> either transaction version, then it'd be better to explicitly say so.


My intention was that wallets create a transaction exactly like they normally would do, and use that as the template transaction. The only time I wanted to be prescriptive was when it would increase the implementation complexity (e.g. being non-segwit compatible is a pain in the ass. So I'd rather just be "pure segwit only" transactions). But something like locktime makes no difference as long as the transaction is mempool eligible, so I'd rather just wallets do what they do anyway.

Although I think there should be a separate discussion on improving the uniformity of bitcoin transactions in general. The current state of affairs is really atrocious.



---


P.S. I know I come across as obstinate, but it's not really so. If you can come up with an alternative to bustapay with some traction, I'd love to get behind it and deprecate bustapay in favor of it. I just am pretty happy with the state of bustapay and it's status a sort of "MVP of pay2endpoint", and unless the argument is in the form: "We'd love to support it, but in order to do so we'd need X" I'm probably going to disagree.

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[James MacWhyte]

[-- Attachment #1: Type: text/plain, Size: 26526 bytes --]

Why does the template transaction need to be signed in step one and passed
back and forth so many times? What is wrong with:

1. Sender creates unsigned tx with their relevant inputs and outputs. This
tx is passed to receiver.

2. Receiver adds their relevant inputs and outputs and signs their portion
before returning the tx to sender.

3. Sender confirms their inputs and outputs have not been modified, and
signs the remainder of the tx before broadcasting it (or sending it to the
recipient if you want to follow the payment protocol spec).

James

On Sun, Jan 27, 2019, 08:45 Adam Gibson via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org wrote:

>
>
> On 27. 01. 19 8:36, rhavar@protonmail.com wrote:
> > Thanks Adam,
> >
> > I have fixed the mistakes you have pointed out:
> https://github.com/bitcoin/bips/pull/754
> >
> > Thanks for the detailed look!
> >
> >> but its virtue of steganographic hiding means only minimal uptake
> >> is still enormously interesting and worth pursuing; that's my current
> feeling.
> >
> > I very much agree =) I really think anything that (silently) breaks the
> assumption of common ownership of transaction inputs offers outsized
> benefits for the whole ecosystem.
> >
> > One other idea I have  is (way) better support for moving utxo's between
> wallets. The least controversial use case is moving funds between wallets
> you own. Like I might want to move *specific* utxo's from/to my joinmarket
> wallet, but not create a (privacy losing / expensive) transaction. Both
> core and joinmarket fail at this at a practical point of view.
>
> (tangential, but yes coin control in JM is an obviously necessary
> feature and will be done, I just don't have time).
>
> >
> > Like imho it'd be pretty cool having a standardized format for
> (txid:vout:privatekey) with wallets showing it as "External UTXO" and
> preferentially spending it (and wallet not automatically importing any
> other utxo from that address).
> >
> > Taken a bit further (this is the part which everyone hates) you could
> send someone money (or withdraw it from a service) by giving a person. It's
> not generally useful (for obvious reasons), but there's a lot of cases I
> think it's super cool.
>
> Is there a missing word. "by giving a person.."? Not actually sure what
> you're getting at here but I suspect it's again tangential to this BIP
> discussion.
>
> >
> > ---
> >
> > Getting back on topic, without trying to do a point-by-point reply, I
> agree with pretty much everything you said but I am reluctant to make any
> changes.
> >
> > I don't meant to be obtuse or anything, but I strongly believe the
> limiting factor to adoption to all these protocols is actually just getting
> people to implement it. I made multiple implementations of bustapay from
> both the sending/receiving end, so I could try develop the easiest to
> implement system that is still practical.
>
> You know, there's considerable evidence to the contrary, I'd argue: this
> idea *has* been implemented already three times: by yourself, by myself
> and by Samourai. And in fully incompatible ways :) So I think the
> limiting factor is in fact creating a standard that a reasonable number
> of people could agree with (and I like operational definitions, so
> subjective as it is, I like the goal of "good/clear enough that it could
> be incorporated into something like BtcPayServer")
>
> >
> > For instance I like PSBT and it's nice in theory. I actually had an
> original implementation using it, which is how I found some bugs in the
> core and golang version of PSBT). But in practice it's hugely overkill and
> significantly increases the implementation complexity complexity and is
> poorly supported. Switching to just a raw transaction actually made
> everything easier. (And that's not to criticise PSBT, I would definitely
> want to use it in other contexts).
>
> But this relates back to my first "generic" point that you haven't
> addressed here - protocol versioning and the possibility of more than
> one option. Perhaps more realistic (debatable): have the current version
> be non-PSBT but with a plan to have a version bump with PSBT in future.
> Stuff like that. It seems crazy to actually long term reject it.
>
> >
> > Anyway, a big motivation for me even writing it as a BIP was to
> formalize my little anti-DOS trick of privately creating a "template
> transaction" which can just be dumped on the network as punishment. So if
> nothing else, hopefully I'll have demonstrated it's a pretty practical way
> of doing things.
> >
>
> I don't want to be that guy, but this was a central part of the proposal
> that came of the meetup last summer and is in Haywood's blogpost. I mean
> if you came up it with separately, then cool :) But I was there, that
> was established immediately as the right way of doing this to avoid a
> trivial attack.
> What might have confused you is all that stuff about multiple candidates
> and even ZKP approaches - those were just extra ideas about making it
> really secure at large scale; but those ideas don't quite meet the goal
> (for various reasons); well, arguably. The basic anti-DOS of an initial
> non-coinjoin was sorta central.
> (Also I'm noting you didn't respond to my critique of your "always use
> the same contributions" defence; I mean, probably that's fine, it was
> only really saying it isn't perfect. Was just curious to hear
> your/others thoughts on it).
>
> > --
> >
> > Also your analysis on "Unnecessary Input Heuristic" is pretty cool, but
> I also don't like telling people to "avoid the UIH2" without providing the
> actual algo they should use. But really I think it's better off in a sort
> of article "how to pick contributed inputs" or something, as while it's
> nice it's not a huge deal and there's a lot of debatable tradeoffs that
> can/should be used. For instance the implementation I wrote for
> bustabit.com currently just heavily biases tainted inputs (e.g. ones
> associated with address reuse).
> >
>
> Good point about algo.
> I wrote my best effort at a procedure here:
>
> https://gist.github.com/AdamISZ/4551b947789d3216bacfcb7af25e029e#gistcomment-2799709
>
> I asked for comments on it but got none back so far (gists are terrible
> for this unfortunately, perhaps I'll have more luck on the list).
>
> I would argue that this issue *should* be mentioned on the BIP. A *huge*
> part of what makes PayJoin/BustaPay of interest is the steganographic
> feature, if you don't pay attention to this then it doesn't look like a
> payment (caveat.-->).
> The counterargument is Laurent's statistics which I previously linked,
> suggesting that maybe 30% of txs violate this anyway, today. I'm not
> sure about that, will need more analysis; Core's SRD algo may be one
> reason, but anyway ... better to make things look like payments.
>
> It doesn't hurt to prompt an implementer to do this; whether it's
> feasible in that specific wallet situation or not is up to them; whether
> they want to go hog wild and control percentages of UIH1 and UIH2 and
> whatnot is there business, or they can totally ignore it - but without
> it being mentioned in the BIP, they may not even think of it.
>
> A last point, you also don't see value in being more explicit about
> simple things like transaction version and locktime? Even if you think
> these things should *not* be controlled, e.g. the protocol should allow
> either transaction version, then it'd be better to explicitly say so.
> >
> >
> > -Ryan
> >
> > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> > On Friday, January 25, 2019 6:47 AM, Adam Gibson via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> >> Ryan and list,
> >> I want to add some commentary to this (BIP79) to see if we can get
> >> further in standardizing this idea.
> >>
> >> When I first mulled it over I thought it too impractical, but its virtue
> >> of steganographic hiding means only minimal uptake is still enormously
> >> interesting and worth pursuing; that's my current feeling. I've offered
> >> more detailed thoughts in my blog post[1] (def not required reading
> here).
> >>
> >> Both Joinmarket and Samourai have started implementing this kind of
> >> transaction. And while that's interesting experimentally, some kind of
> >> cross-wallet standard would be helpful, albeit there some differences
> >> between that and the merchant/centralized service use-case.
> >>
> >> We might imagine as a concrete goal for this BIP to create something
> >> that would be acceptable for inclusion into a project like BTCPayServer,
> >> so that it could be used in a realistic use case by smaller bitcoin
> >> accepting merchants.
> >>
> >> Comments to the BIP[2] as follows, with generic comments first, and then
> >> specific comments for existing points in the BIP:
> >>
> >> [1] https://joinmarket.me/blog/blog/payjoin
> >> [2] https://github.com/bitcoin/bips/blob/master/bip-0079.mediawiki
> >>
> >> Generic comments
> >>
> >>
> ==================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================
> >>
> >> -   Protocol versioning. Since inevitably (even if only merchants), this
> >>     must be implemented by multiple wallets to be useful, the
> communication
> >>     protocol will need versioning (for example i have in my
> >>     simple/experimental Joinmarket PayJoin that sender sends min and max
> >>     supported version and receiver responds with a chosen protocol
> version
> >>     so we can update). I do understand that as a client-server model can
> >>     apply here, we can ditch a lot of the complexities around
> network/p2p
> >>     interaction, but this much at least seems necessary.
> >>
> >> -   Although it has its logic, I don't think "Bustapay" is a good name
> for
> >>     this protocol. I prefer "PayJoin" which is neutral sounding and
> >>     self-descriptive. Needless to say this is not a hill I intend to
> die on.
> >>
> >> -   PSBT/BIP174. I realise this has already been discussed, but this is
> a
> >>     good example of what this standardisation was designed for, so I'd
> be
> >>     against not including it, even given the reality that, as you
> correctly
> >>     observe, it is not yet implemented in the majority of wallets and
> >>     libraries. One way round that is to make it optional (possibly
> combined
> >>     with above point about versioning). Note that for example you were
> >>     observing the necessity to check the sequence number was unchanged;
> that
> >>     would be encapsulated by checking equality of PSBT Input
> objects/fields.
> >>     While one can make such software architecture arguments, the really
> >>     fundamental point is the need for standards for x-wallet
> compatibility.
> >>
> >> -   Version, Locktime: Perhaps this is not needed; in a peer to peer
> >>     wallet scenario I think there might be logic in trying to get cover
> >>     traffic of (Core, Electrum, others), say, by using
> >>     last-block-locktime-mostly, as they do. Version should be 2 and
> sequence
> >>     is a function of your suggestion to use BIP125. Worth noting that
> BIP125
> >>     is not currently widely used on the network, though (see
> >>     https://p2sh.info/dashboard/db/replace-by-fee?orgId=1). For this
> reason
> >>     it should perhaps be explicitly only optional.
> >>
> >> -   Avoidance of non-payment "Unnecessary Input Heuristic" (1, 2). For
> >>     reference, see the definition here
> >>
> https://gist.github.com/AdamISZ/4551b947789d3216bacfcb7af25e029e#gistcomment-2796539
> >>     and some data here
> >>
> https://gist.github.com/AdamISZ/4551b947789d3216bacfcb7af25e029e#gistcomment-2800791
> >>     (whole comment thread may be of interest) - note this UIH name is
> afaik
> >>     Chris Belcher's invention, it seems useful as a categorisation.
> >>     So, it seems that UIH2 is more important to avoid; while some more
> >>     sophisticated wallet coin selection algorithms may occasionally pick
> >>     an input set where one input is larger than any output, most won't,
> and
> >>     some in particular never will. So I think the text here should
> indicate
> >>     that *the receiver's contributed input(s) SHOULD be chosen to avoid
> >>     triggering the UIH2 heuristic where possible, so that the final
> payjoin
> >>     transaction is maximally plausible as an ordinary payment" or
> similar.
> >>     UIH1 is a nice-to-have (meaning the plausibility extends to two
> >>     different (both wrong) payment amounts, but it may not be necessary
> to
> >>     mention it in the BIP.
> >>
> >>     Specific comments
> >>     =================
> >>
> >>
> >>>> ====Step 4. Receiver validates, re-signs, and propagates on the
> >>
> >> bitcoin network====
> >>
> >> I believe this should say "Sender" not Receiver. Also for the next
> >> sentence, s/receiver/sender/:
> >>
> >>>> The receiver MUST validate the ''partial transaction'' was changed
> >>
> >> correctly and non-maliciously (to allow using potentially untrusted
> >> communication channels), re-sign its original inputs and propagate the
> >> final transaction over the bitcoin network.
> >>
> >> Your very correct highlighting of the attack vector of "receiver gives
> >> sender other inputs belonging to sender to unwittingly sign (described
> >> below), should be highlighted here, perhaps with the phrase "re-sign its
> >> ORIGINAL inputs" (only!)".
> >>
> >>>> When the sender is creating a "template transaction" it is done
> >>
> >> almost identically to creating a normal send, with the exception that
> >> only segwit inputs may be used. The sender is also encouraged to use a
> >> slightly more aggressive feerate than usual as well as BIP125 (Opt-in
> >> Full Replace-by-Fee Signaling), but neither is strictly required.
> >>
> >> "slightly more aggressive feerate than usual" - this I understand is to
> >> make up for receiver contributed utxo, OK.
> >>
> >> "only segwit inputs" - it certainly makes things simpler. One can work
> >> with non-segwit inputs but especially considering (as mentioned below)
> >> we really ought to "MUST" the part about matching input types, I tend to
> >> agree that non-segwit should be disallowed.
> >>
> >>>> The receiver must add at least one input to the transaction (the
> >>
> >> "contributed inputs"). If the receiver has no inputs, it should use a
> >> 500 internal server error, so the client can send the transaction as per
> >> normal (or try again later).
> >>
> >> Would it not be much simpler for the server to return a different
> >> (non-error) response indicating that it will broadcast the template tx
> >> in this case?
> >>
> >>>> Its generally advised to only add a single contributed input, however
> >>
> >> they are circumstances where adding more than a single input can be
> useful.
> >>
> >> I don't see a good reason to advise the use of only 1 input? (but this
> >> will also connect with the above generic comment about "UIH"). I guess
> >> it's because of your approach to fees. I'd prefer not to create a
> >> limitation here.
> >>
> >>>> To prevent an attack where a receiver is continually sent variations
> >>
> >> of the same transaction to enumerate the receivers utxo set, it is
> >> essential that the receiver always returns the same contributed inputs
> >> when it's seen the same inputs.
> >>
> >> This is an approach to avoiding this problem which has the virtue of
> >> simplicity, but it seems a little problematic. (1) You must keep a
> >> mapping of proposed payment utxos to one's proposed contributed input
> >> utxos, but (2) how should this be updated if you need to spend the
> >> contribution mentioned in (1)? Ironically use of payjoin exacerbates
> >> this issue, because it results in a smaller number of utxos being held
> >> by the receiver at any one time :) All this considered, I still see the
> >> value in your approach, but it might end up with a re-attempted payment
> >> being rejected. Certainly the more complex suggested solutions coming
> >> out of the summer 2018 coinjoin workshop aren't as practical as this,
> >> and may be overkill for small merchants/receivers.
> >>
> >>>> It is strongly preferable that the receiver makes an effort to pick a
> >>
> >> contributed input of the same type as the other transaction inputs if
> >> possible.
> >>
> >> I have also thought about this and you could reasonably argue this
> >> should be a MUST section in the BIP, that is, if the receiver cannot use
> >> inputs of the same type, he should fall back to the template
> >> transaction. A mixed-input payjoin/coinjoin is essentially
> >> near-perfectly identifiable as such (there is almost zero other usage of
> >> multi-type-input transactions), which is a very different thing than a
> >> non-identifiable payjoin transaction. That may or may not be OK to the
> >> sender. This is debatable though, for sure.
> >>
> >>>> After adding inputs to the transaction, the receiver generally will
> >>
> >> want to adjust the output that pays himself by increasing it by the sum
> >> of the contributed input amounts (minus any fees he wants to
> >> contribute). However the only strict requirement is that the receiver
> >> must never add or remove inputs, and must not ever decrease any
> >> output amount.
> >>
> >> "must never add or remove inputs" - did you mean "must never remove
> >> inputs"? he surely has to add one! Or, perhaps you mean he must not
> >> alter the list of inputs provided by the sender (in which case it should
> >> be clarified).
> >>
> >> "must not decrease any output amount" - I initally disagreed with this
> >> but it is a better option than the one I currently chose in Joinmarket
> >> payjoin (sender pays all fee as long as receiver utxos are not too
> >> much). So this means that the receiver either consciously chooses to not
> >> increase the fee, meaning the fee rate may be a bit low (hence your
> >> earlier comment about being generous, got it), or contributes via the
> >> payout amount. I guess the latter might break merchant software
> >> expecting to have amount output fixed and fees determined by change.
> >>
> >> Regards,
> >> Adam Gibson/waxwing
> >>
> >> On 30. 08. 18 22:24, Ryan Havar via bitcoin-dev wrote:
> >>
> >>> I've just finished writing an implementing of this, and extremely happy
> >>> with how it turned out. So I'd like to go and try go down the path of
> >>> more formally describing it and getting some comments and ultimately
> >>> encourage its wide-spread use.
> >>> ==Abstract==
> >>> The way bitcoin transactions are overwhelming used is known to leak
> more
> >>> information than desirable. This has lead to fungibility concerns in
> bitcoin
> >>> and a raise of unreasonably effective blockchain analysis.
> >>> Bustapay proposes a simple, practical way to bust these assumptions to
> >>> immediate
> >>> benefit of the sender and recievers. Furthermore it does so in such a
> >>> way that
> >>> helps recievers avoid utxo bloat, a constant problem for bitcoin
> merchants.
> >>> ==Copyright==
> >>> This BIP is in the public domain.
> >>> ==Motivation==
> >>> One of the most powerful heuristic's employed by those whose goal is to
> >>> undermine
> >>> bitcoin's fungiblity has been to assume all inputs of a transaction are
> >>> signed by
> >>> a single party. In the few cases this assumption does not hold, it is
> >>> generally
> >>> readibly recognizable (e.g. traditional coinjoins have a very obvious
> >>> structure,
> >>> or multisig outputs are most frequently validated onchain).
> >>> Bustapay requires no changes to bitcoin and creates bitcoin
> transactions
> >>> that are
> >>> indistinguishable from normal ones.
> >>> It is worth noting that this specification has been intentionally kept
> >>> as simple
> >>> as possible to encourage adoption. There are almost an endless amount
> of
> >>> extensions
> >>> possible but the harder the implementation of clients/server the less
> >>> likely it
> >>> will ever be done. Should bustapay enjoy widespread adoption, a "v2"
> >>> specification
> >>> will be created with desired extensions.
> >>> ==Specification==
> >>> A bustapay payment is made from a sender to a receiver.
> >>> Step 1. Sender creates a bitcoin transaction paying the receiver
> >>> This transaction must be fully valid, signed and all inputs must use
> >>> segwit. This transaction is known as the "template transaction". This
> >>> transaction must not be propagated on the bitcoin network.
> >>> Step 2. Sender gives the "template transaction" to the receiver
> >>> This would generally be done as an HTTP POST. The exact URL to submit
> it
> >>> to could be specified with a bip21 encoded address. Such as
> >>> bitcoin:2NABbUr9yeRCp1oUCtVmgJF8HGRCo3ifpTT?bustapay=
> https://bp.bustabit.com/submit
> >>> and the HTTP body should be the raw transaction hex encoded as text.
> >>> Step 3. Receiver processes the transaction and returns a partially
> >>> signed coinjoin
> >>> The receiver validates the transaction is valid, pays himself and is
> >>> eligible for propation. The receiver then adds one of his own inputs
> >>> (known as the "contributed input") and increase the output that pays
> >>> himself by the contributed input amount. Doing so will invalidate the
> >>> "template transaction"'s original input signatures, so the sender needs
> >>> to return this "partial transaction" back to the receiver to sign. This
> >>> is returned as a hex-encoded raw transaction a response to the original
> >>> HTTP POST request.
> >>> Step 4. Receiver validates, re-signs, and propagates on the bitcoin
> network
> >>> The receiver is responsible in making sure the "partial transaction"
> >>> returned by the sender was changed correctly (it should assume the
> >>> connection has been MITM'd and act accordingly), resign its original
> >>> inputs and propagates this transaction over the bitcoin network. The
> >>> client must be aware that the server can reorder inputs and outputs.
> >>> Step 5. Receiver observes the finalized transaction on the bitcoin
> network
> >>> Once the receiver has seen the finalized transactions on the network
> >>> (and has enough confirmations) it can process it like a normal payment
> >>> for the sent amount (as opposed to the amount that it looks like on the
> >>> network). If the receiver does not see the finalized transaction after
> a
> >>> timeout will propagate the original "template transaction" to ensure
> the
> >>> payment happens and function a strong anti-DoS mechanism.
> >>> === Implementation Notes ===
> >>> For anyone wanting to implement bustapay payments, here are some notes
> >>> for receivers:
> >>>
> >>> -   A transaction can easily be checked if it's suitable for the
> mempool
> >>>     with testmempoolaccept in bitcoin core 0.17
> >>>
> >>> -   Tracking transactions by txid is precarious. To keep your sanity
> make
> >>>     sure all inputs are segwit. But remember segwit does not prevent
> txid
> >>>     malleability unless you validate the transaction. So really make
> sure
> >>>     you're using testmempoolaccept at the very least
> >>>
> >>> -   Bustapay could be abused by a malicious party to query if you own a
> >>>     deposit address or not. So never accept a bustapay transaction
> that pays
> >>>     an already used deposit address
> >>>
> >>> -   You will need to keep a mapping of which utxos people have showed
> you
> >>>     and which you revealed. So if you see them again, you can reveal
> the
> >>>     same one of your own
> >>>
> >>> -   Check if the transaction was already sorted according to BIP69, if
> so
> >>>     ensure the result stays that way. Otherwise probably just shuffle
> the
> >>>     inputs/outpus
> >>>
> >>>
> >>> Notes for sending applications:
> >>>
> >>> -   The HTTP response must not be trusted. It should be fully validated
> >>>     that no unexpected changes have been made to the transaction.
> >>>
> >>> -   The sender should be aware the original "template transaction" may
> be
> >>>     propagated at any time, and in fact can intentionally be
> >>>       done so for the purpose of RBF as it should have a slightly
> higher fee
> >>>     rate.
> >>>
> >>>
> >>> == Credits ==
> >>> The idea is obviously based upon Dr. Maxwell's seminal CoinJoin
> >>> proposal, and reduced scope inspired by a simplification of the "pay 2
> >>> endpoint" (now offline) blog post by blockstream.
> >>> -Ryan
> >>>
> >>> bitcoin-dev mailing list
> >>> bitcoin-dev@lists.linuxfoundation.org
> >>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >>
> >> bitcoin-dev mailing list
> >> bitcoin-dev@lists.linuxfoundation.org
> >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> >
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 32869 bytes --]

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[rhavar]

[-- Attachment #1: Type: text/plain, Size: 513 bytes --]

> Why does the template transaction need to be signed in step one and passed back and forth so many times? What is wrong with:

It isn't passed "back and forth so many times".  It works exactly as you proposed, with the only difference is in "Step 1" the sender uses a *signed* transaction instead of an unsigned one.  This is an important anti-DoS/anti-spy tactic, as it proves the sender actually owns those inputs and if the protocol is not followed to completion, the transaction can be dumped on the network.

[-- Attachment #2: Type: text/html, Size: 675 bytes --]

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[James MacWhyte]

[-- Attachment #1: Type: text/plain, Size: 1224 bytes --]

James


On Sun, Jan 27, 2019 at 2:11 PM <rhavar@protonmail.com> wrote:

>
> It isn't passed "back and forth so many times".
>

You are right, I got the wrong impression the first time I read it.


> This is an important anti-DoS/anti-spy tactic, as it proves the sender
> actually owns those inputs and if the protocol is not followed to
> completion, the transaction can be dumped on the network.
>

I'm not convinced this is a valid concern, at least not valid enough to add
extra complications to the process. The sender could still refuse to sign
the final transaction after they see the recipient's in-/outputs; "show me
yours and I'll show you mine" isn't much of a spy deterrent, and nothing
here prevents a DOS attack.

As an implementor, I would suggest keeping the protocol as simple as
possible. By dropping the signing in the first step, the recipient doesn't
need to maintain the ability to lookup and verify unspent outputs. It also
would enforce the increased privacy, which the sender obviously wants if
they are going down this path (in other words, either have the process
complete or fail -- don't give the recipient the ability to broadcast the
not-private transaction against the wishes of the sender).

[-- Attachment #2: Type: text/html, Size: 1924 bytes --]

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[rhavar]

[-- Attachment #1: Type: text/plain, Size: 2816 bytes --]

On Tuesday, January 29, 2019 6:06 PM, James MacWhyte <keatonatron@gmail.com> wrote:

> I'm not convinced this is a valid concern, at least not valid enough to add extra complications to the process.

Signing a transaction is something a wallet needs to be able to do anyway AND at the final-step. And actually a signed transaction is _simpler_ because it's more standard and way format to send and validate.

> The sender could still refuse to sign the final transaction after they see the recipient's in-/outputs; "show me yours and I'll show you mine" isn't much of a spy deterrent, and nothing here prevents a DOS attack.

If the sender refuses to sign the final transaction, the receiver just propagates the template transaction which pays the receiver! So it's a pretty weak attack.

The only real attack is that the sender could double-spend the template-transaction before it's propagated, but the cost of doing this isn't free, as at the very least you need to pay the transaction fees of creating a double spend. It's not an amazingly good defence, but it's good enough that it's unlikely to get abused (and an attacker would only learn a single utxo of the receiver) .

> As an implementor, I would suggest keeping the protocol as simple as possible. By dropping the signing in the first step, the recipient doesn't need to maintain the ability to lookup and verify unspent outputs.

Being able to verify a transaction tends to be pretty simple in practice.  (e.g. `testmempoolaccept` in bitcoin core's wallet) but if it's really hard for a receiver to do, it can easily just not do it... (and assume the template transaction is valid even if it's not).

But I suspect this actually complicates the job for the receiver, because now you have to deal with transaction malleability as they can now give you an invalid transaction, you sign it  and then they malleate into a valid transaction with a different txid. So if you're tracking the transaction by txid, you'll get really confused...).

> It also would enforce the increased privacy, which the sender obviously wants if they are going down this path

I guess that's a valid concern. A sender might want to make a payment, but *only* if it can be done via a bustapay, while the current spec doesn't support that.

But there's no way that justifies removing the protection for receivers. Without some _basic_ protection, every company that takes bustapayments will just get constantly attacked by a simple costless `wget` that leaks their wallet utxos...

The only viable way I can see, would be the sender pays the first part of his invoice in lightning. And then pays the rest with a bustapay. Now the anti-spy thing is the fact the first part of the invoice was already paid.

But with so many moving parts, no one is ever going to implement that :P

[-- Attachment #2: Type: text/html, Size: 3733 bytes --]

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[James MacWhyte]

[-- Attachment #1: Type: text/plain, Size: 994 bytes --]

On Tue, Jan 29, 2019 at 6:46 PM <rhavar@protonmail.com> wrote:

>
> If the sender refuses to sign the final transaction, the receiver just
> propagates the template transaction which pays the receiver! So it's a
> pretty weak attack.
>
> The only real attack is that the sender could double-spend the
> template-transaction before it's propagated, but the cost of doing this
> isn't free, as at the very least you need to pay the transaction fees of
> creating a double spend. It's not an amazingly good defence, but it's good
> enough that it's unlikely to get abused (and an attacker would only learn a
> single utxo of the receiver) .
>

Okay, I see what you mean. I better understand the weaknesses you've
identified, and I can't really think of a better solution than what you've
proposed. I also realized that implementors who aren't capable of
integrating signing and UTXO validation wouldn't be the ones trying to
implement this feature, so my concerns there are also moot. Carry on ;)

[-- Attachment #2: Type: text/html, Size: 1396 bytes --]

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[ZmnSCPxj]

Good morning Ryan and Adam,

> [UIH2 snipped]

Perhaps I am being naive, but I seem, the B2EP and similar do not need to worry about UIH2.

From the github discussion:

> "UIH2": one input is larger than any output.
.
I.e. there exists an input, for all outputs, input > output
To avoid this, we should ensure that, for all inputs, there exists an output, input < output.

From the proposal BIP:

> The receiver then adds one of his own inputs (known as the "contributed input") and increase the output that pays himself by the contributed input amount.

Suppose the original transaction avoids the UIH2 (i.e. for all inputs, there exists an output, input < output).
The single added input will also avoid the UIH2, since the contributed output value is added to the receiver output, thereby ensuring that contributed input < output.

Suppose the original transaction does not avoid the UIH2.
The receiver adding their own contributed input would then have a chance that the addition on the output will now cause the final transaction to avoid the UIH2, since the sum of the receiver amount and the contributed input may now exceed the largest sender input.
But since there are more transactions that avoid the UIH2 than not avoid UIH2, the increased probability of now avoiding the UIH2 will lead to a greater anonymity set (especially for the sender, whose coin selection algorithm might have a consistent bias that makes it create transactions that trigger UIH2).

So it seems to me that the simple solution, i.e. sender uses standard coin selection algorithms already in use today, and receiver does not do any UIH2 checks at all, would be an improvement in both privacy and implementation simplicity.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[Adam Gibson]

ZmnSCPxj, thanks, responses inline.

On 28. 01. 19 5:14, ZmnSCPxj wrote:
> Good morning Ryan and Adam,
> 
>> [UIH2 snipped]
> 
> Perhaps I am being naive, but I seem, the B2EP and similar do not need to worry about UIH2.
> 
> From the github discussion:
> 
>> "UIH2": one input is larger than any output.
> .
> I.e. there exists an input, for all outputs, input > output
> To avoid this, we should ensure that, for all inputs, there exists an output, input < output.
> 
> From the proposal BIP:
> 
>> The receiver then adds one of his own inputs (known as the "contributed input") and increase the output that pays himself by the contributed input amount.
> 
> Suppose the original transaction avoids the UIH2 (i.e. for all inputs, there exists an output, input < output).
> The single added input will also avoid the UIH2, since the contributed output value is added to the receiver output, thereby ensuring that contributed input < output.
> 
Yes, I had noted this (see link below).

> Suppose the original transaction does not avoid the UIH2.
> The receiver adding their own contributed input would then have a chance that the addition on the output will now cause the final transaction to avoid the UIH2, since the sum of the receiver amount and the contributed input may now exceed the largest sender input.

(Just to note (see link below) what I'm sure you're aware of but a
reader might forget: if the change output that the sender provided is
larger than the payment amount, the above won't happen).

> But since there are more transactions that avoid the UIH2 than not avoid UIH2, the increased probability of now avoiding the UIH2 will lead to a greater anonymity set (especially for the sender, whose coin selection algorithm might have a consistent bias that makes it create transactions that trigger UIH2).
> 
> So it seems to me that the simple solution, i.e. sender uses standard coin selection algorithms already in use today, and receiver does not do any UIH2 checks at all, would be an improvement in both privacy and implementation simplicity.
> 
> Regards,
> ZmnSCPxj
> 

Really good point, and I think your argument is reasonable, if not
watertight. (Just in case you missed it I tried to outline an algo to
let the receiver avoid UIH2 on best effort basis here:
https://gist.github.com/AdamISZ/4551b947789d3216bacfcb7af25e029e#gistcomment-2799709).

Although I ~ sorta agree, there is a slight counterargument: receiver is
adding utxos, so in the absence of any transaction inspection you're
creating a different distribution than one gets from existing wallet
selection algos. For example:
Note that the most likely/desirable/considered use case may be a
merchant use case (after all, who receives coins most frequently? in
theory, people selling stuff), and it is highly plausible that they
might concentrate larger and larger sums into utxo(s) via use of
PayJoin. Completely mismatched input sizes could be a problem, it's
debatable, and it's also debatable whether it can be avoided, but what I
don't quite buy is that this issue can just be ignored.

And I'm reminded that a related point is made by belcher in the gist
comment thread iirc (after we discussed it on IRC): over time a
"PayJoin-only" merchant doing the simplest thing - using a single utxo
over and over again, will concentrate more and more funds into it, and
inevitably violating UIH2 in an increasingly dramatic fashion
(contributing a 100BTC utxo to a 0.1BTC payment etc.). Suggesting it's
better if there's a mix of payjoin/non-payjoin.

Re: [bitcoin-dev] bustapay BIP :: a practical sender/receiver coinjoin protocol

[ZmnSCPxj]

Good morning Adam,

> And I'm reminded that a related point is made by belcher in the gist
> comment thread iirc (after we discussed it on IRC): over time a
> "PayJoin-only" merchant doing the simplest thing - using a single utxo
> over and over again, will concentrate more and more funds into it, and
> inevitably violating UIH2 in an increasingly dramatic fashion
> (contributing a 100BTC utxo to a 0.1BTC payment etc.). Suggesting it's
> better if there's a mix of payjoin/non-payjoin.

To be pedantic: as I understand bustapay, it would still not violate UIH2 (unless I misunderstand UIH2).

Suppose the original transaction is: (0.05 payer, 0.07 payer) -> (0.1 payee, 0.02 payer)

Then bustapay with such a PayJoin-only merchant with 100BTC UTXO would give: (100 payee, 0.05 payer, 0.07 payer) -> (100.1 payee, 0.02 payer).
As I understand it, this technically does not violate UIH2.

It would still conceivably be interpreted as a payment of 100.1 BTC, from a payer who happens to have massively lopsided UTXOs being owned, but still does not violate UIH2.

However, if that 100.1 UTXO is subsequently used to pay a 100.3 payment, then that is used to pay a 100.7 payment, that strongly suggests such a naive PayJoin-only merchant.

Perhaps a simple heuristic against this would be:

1.  For every UTXO you own, flip a coin.
    If all of them come up heads, do not payjoin; just broadcast the original transaction.
2.  Else, randomly select a UTXO (value not care?) and payjoin with that UTXO.

However, I have no proper analysis of the blockchain, so --

Regards,
ZmnSCPxj