[bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[German Luna]

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

Hello All,

## Objective
* Make atomic swaps within the same chain possible in a traceless way
* Achieving traceless same-chain atomic-swaps effectively turns an entire
chain into a  (P2PKH) mixer by default

## Proposed solution
Similar to the way that atomic swaps would work with schnorr signatures
(i.e. leveraging adaptor signatures), the proposed solution is to use - in
place of the secret 't' - a suitably chosen schnorr signature. The end
result being that when one counterparty claims their side of the funds, the
party can obtain the signature they're missing to claim the funds in the
(schnorr) multisig that pays them.
On-chain, this would appear like two independent transactions, even though
effectively the two parties have “exchanged” the history attached to the
UTXOs. Unlike a mixing service, in which all of the histories get merged,
with this protocol histories can be pairwise swapped without anybody’s
knowledge.

## Protocol description
* Alice and Bob, holding funds at UTXO1 (controlled by Alice) and UTXO2
(controlled by Bob) wish to swap them.
* Alice provides Bob with a single public key P_A
* Bob provides Alice two pubkeys P_B1, P_B2.
* Bob and Alice construct the P2PKH addresses Addr1 = Hash(P_A+P_B1) [where
the UTXO1 funds will be sent to eventually] and Addr2  = Hash(P_A+P_B2)
[where the UTXO2 funds will be sent to eventually]
* Bob and Alice exchange time-locked refund transactions for the funding
transactions sending the funds to Addr1 and Addr2.
* Bob and Alice submit the funding transactions (Alice pays to Addr1 from
UTXO1; Bob pays to Addr2 from UTXO2)
* Alice sends Bob an adaptor signature: r1 + H(r1 | m)*x_a + r2 + H( r2 |
m')*x_a
* Bob verifies the adaptor signature Alice sent contains a valid signature
for spending from Addr1 AND another valid signature for spending from
Addr2. Both signatures from Alice. Bob cannot separate out the two
signatures and hence cannot claim any of the funds, provided H( r1 | m) !=
H( r2 | m') in the signature commitment.
* Bob now sends Alice the valid signature: r2 + H( r2 | m' )*x_b2
* Alice can now add her signature to Bob's and get: r2 + H( r2| m'
)*(x_b2 + x_a) which is a valid signature to spend the funding transaction
sent to Addr2.
* Finally, Bob sees Alice claims the fund sent to Addr2 and uses that
signature to subtract his own: r2 + H( r2 | m' )*(x_b2 + x_a) - (r2 + H( r2
| m' )*x_b2) = H( r2 | m ')*x_a
* Bob takes the original adaptor signature and subtracts the known quantity
r2+ H( r2 | m' )*x_a, to get a valid signature: r1 + H( r1 | m )*x_a
* Bob can now add to that valid signature, his own signature and retrieve
the funds.
## Notes
* It is possible for the counterparty to store copies of the signatures as
proof that such a join has taken place. But plausible deniability is
available upon discarding signatures since the joint private keys (x_a +
x_b*) are unavailable.

I'm interested in hearing feedback on this idea if possible, and deemed
interesting enough.

Best regards,
-- 
Germán
Mathematician

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

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[ZmnSCPxj]

Good morning Germán,

It looks to me like this is CoinSwap with Schnorr Scriptless Scripts.

* https://joinmarket.me/blog/blog/coinswaps/
* https://joinmarket.me/blog/blog/flipping-the-scriptless-script-on-schnorr/

I also recently put up an article on extending such a protocol across 3 or more participants:

* https://zmnscpxj.github.io/bitcoin/multiswap.html

Regards,
ZmnSCPxj

> ## Objective
> * Make atomic swaps within the same chain possible in a traceless way
> * Achieving traceless same-chain atomic-swaps effectively turns an entire chain into a  (P2PKH) mixer by default
>
> ## Proposed solution
> Similar to the way that atomic swaps would work with schnorr signatures (i.e. leveraging adaptor signatures), the proposed solution is to use - in place of the secret 't' - a suitably chosen schnorr signature. The end result being that when one counterparty claims their side of the funds, the party can obtain the signature they're missing to claim the funds in the (schnorr) multisig that pays them.
> On-chain, this would appear like two independent transactions, even though effectively the two parties have “exchanged” the history attached to the UTXOs. Unlike a mixing service, in which all of the histories get merged, with this protocol histories can be pairwise swapped without anybody’s knowledge.
>
> ## Protocol description
> * Alice and Bob, holding funds at UTXO1 (controlled by Alice) and UTXO2 (controlled by Bob) wish to swap them. 
> * Alice provides Bob with a single public key P_A
> * Bob provides Alice two pubkeys P_B1, P_B2.
> * Bob and Alice construct the P2PKH addresses Addr1 = Hash(P_A+P_B1) [where the UTXO1 funds will be sent to eventually] and Addr2  = Hash(P_A+P_B2) [where the UTXO2 funds will be sent to eventually]
> * Bob and Alice exchange time-locked refund transactions for the funding transactions sending the funds to Addr1 and Addr2.
> * Bob and Alice submit the funding transactions (Alice pays to Addr1 from UTXO1; Bob pays to Addr2 from UTXO2)
> * Alice sends Bob an adaptor signature: r1 + H(r1 | m)*x_a + r2 + H( r2 | m')*x_a
> * Bob verifies the adaptor signature Alice sent contains a valid signature for spending from Addr1 AND another valid signature for spending from Addr2. Both signatures from Alice. Bob cannot separate out the two signatures and hence cannot claim any of the funds, provided H( r1 | m) != H( r2 | m') in the signature commitment. 
> * Bob now sends Alice the valid signature: r2 + H( r2 | m' )*x_b2
> * Alice can now add her signature to Bob's and get: r2 + H( r2| m' )*(x_b2 + x_a) which is a valid signature to spend the funding transaction sent to Addr2.
> * Finally, Bob sees Alice claims the fund sent to Addr2 and uses that signature to subtract his own: r2 + H( r2 | m' )*(x_b2 + x_a) - (r2 + H( r2 | m' )*x_b2) = H( r2 | m ')*x_a
> * Bob takes the original adaptor signature and subtracts the known quantity r2+ H( r2 | m' )*x_a, to get a valid signature: r1 + H( r1 | m )*x_a
> * Bob can now add to that valid signature, his own signature and retrieve the funds.
> ## Notes
> * It is possible for the counterparty to store copies of the signatures as proof that such a join has taken place. But plausible deniability is available upon discarding signatures since the joint private keys (x_a + x_b*) are unavailable.
>
> I'm interested in hearing feedback on this idea if possible, and deemed interesting enough.
>
> Best regards,
> --
> Germán
> Mathematician

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[German Luna]

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

Good morning  ZmnSCPxj,

Thank you for your excellent feedback!

Indeed, with a little protocol-level sugar so that the coins being swapped
get paid out of different pubkeys.
I read your article. Excellent idea on the randomized locktimes! I've still
to read the details of what S6 amounts to but I'm excited to.

With regards to trying to tackle the problem of value-based correlations,
wouldn't it be possible to try to model the solution after the
equal-sum-subset problem (np complete problem)(
https://www.cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subsetSumNPCompleteness.pdf
)?
That is, a pair of individuals with a set of UTXOs that both add up to
similar if not equal value perform a swap of similar-(total)value sets. In
this way the values of the UTXOs can be broken up essentially at random
(following some nominal distribution so that it doesn't stand out; e.g.
https://en.wikipedia.org/wiki/Benford%27s_law), but swapped in conjunction
and decorrelated by using different keys + randomized locktimes.


Regards,
Germán

On Thu, Apr 23, 2020 at 11:56 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Germán,
>
> It looks to me like this is CoinSwap with Schnorr Scriptless Scripts.
>
> * https://joinmarket.me/blog/blog/coinswaps/
> *
> https://joinmarket.me/blog/blog/flipping-the-scriptless-script-on-schnorr/
>
> I also recently put up an article on extending such a protocol across 3 or
> more participants:
>
> * https://zmnscpxj.github.io/bitcoin/multiswap.html
>
> Regards,
> ZmnSCPxj
>
> > ## Objective
> > * Make atomic swaps within the same chain possible in a traceless way
> > * Achieving traceless same-chain atomic-swaps effectively turns an
> entire chain into a  (P2PKH) mixer by default
> >
> > ## Proposed solution
> > Similar to the way that atomic swaps would work with schnorr signatures
> (i.e. leveraging adaptor signatures), the proposed solution is to use - in
> place of the secret 't' - a suitably chosen schnorr signature. The end
> result being that when one counterparty claims their side of the funds, the
> party can obtain the signature they're missing to claim the funds in the
> (schnorr) multisig that pays them.
> > On-chain, this would appear like two independent transactions, even
> though effectively the two parties have “exchanged” the history attached to
> the UTXOs. Unlike a mixing service, in which all of the histories get
> merged, with this protocol histories can be pairwise swapped without
> anybody’s knowledge.
> >
> > ## Protocol description
> > * Alice and Bob, holding funds at UTXO1 (controlled by Alice) and UTXO2
> (controlled by Bob) wish to swap them.
> > * Alice provides Bob with a single public key P_A
> > * Bob provides Alice two pubkeys P_B1, P_B2.
> > * Bob and Alice construct the P2PKH addresses Addr1 = Hash(P_A+P_B1)
> [where the UTXO1 funds will be sent to eventually] and Addr2  =
> Hash(P_A+P_B2) [where the UTXO2 funds will be sent to eventually]
> > * Bob and Alice exchange time-locked refund transactions for the funding
> transactions sending the funds to Addr1 and Addr2.
> > * Bob and Alice submit the funding transactions (Alice pays to Addr1
> from UTXO1; Bob pays to Addr2 from UTXO2)
> > * Alice sends Bob an adaptor signature: r1 + H(r1 | m)*x_a + r2 + H( r2
> | m')*x_a
> > * Bob verifies the adaptor signature Alice sent contains a valid
> signature for spending from Addr1 AND another valid signature for spending
> from Addr2. Both signatures from Alice. Bob cannot separate out the two
> signatures and hence cannot claim any of the funds, provided H( r1 | m) !=
> H( r2 | m') in the signature commitment.
> > * Bob now sends Alice the valid signature: r2 + H( r2 | m' )*x_b2
> > * Alice can now add her signature to Bob's and get: r2 + H( r2| m'
> )*(x_b2 + x_a) which is a valid signature to spend the funding transaction
> sent to Addr2.
> > * Finally, Bob sees Alice claims the fund sent to Addr2 and uses that
> signature to subtract his own: r2 + H( r2 | m' )*(x_b2 + x_a) - (r2 + H( r2
> | m' )*x_b2) = H( r2 | m ')*x_a
> > * Bob takes the original adaptor signature and subtracts the known
> quantity r2+ H( r2 | m' )*x_a, to get a valid signature: r1 + H( r1 | m
> )*x_a
> > * Bob can now add to that valid signature, his own signature and
> retrieve the funds.
> > ## Notes
> > * It is possible for the counterparty to store copies of the signatures
> as proof that such a join has taken place. But plausible deniability is
> available upon discarding signatures since the joint private keys (x_a +
> x_b*) are unavailable.
> >
> > I'm interested in hearing feedback on this idea if possible, and deemed
> interesting enough.
> >
> > Best regards,
> > --
> > Germán
> > Mathematician
>
>
>

-- 
Germán
Mathematician

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

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[ZmnSCPxj]

Good morning Germán,


> With regards to trying to tackle the problem of value-based correlations, wouldn't it be possible to try to model the solution after the equal-sum-subset problem (np complete problem)( https://www.cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subsetSumNPCompleteness.pdf  )? 
> That is, a pair of individuals with a set of UTXOs that both add up to similar if not equal value perform a swap of similar-(total)value sets. In this way the values of the UTXOs can be broken up essentially at random (following some nominal distribution so that it doesn't stand out; e.g. https://en.wikipedia.org/wiki/Benford%27s_law), but swapped in conjunction and decorrelated by using different keys + randomized locktimes.

There are a number of issues to simply modeling this to the subset-sum problem.

* There is a practical limit to the number of UTXOs you would be willing to receive in the swap.
  * Every UTXO you receive increases the potential fee you have to pay to spend them, meaning you would strongly dislike receiving 100 UTXOs that sum up to 1mBTC.
  * Thus, a practical blockchain analyst can bound the size of the sets involved, and the problem becomes less than NP in practice.
* If you have a single UTXO and split it, then swap, anyone looking at the history can conjecture that the split involved is part of a CoinSwap.
  * The split is now a hint on how the subset sums can be tried.
* If after the CoinSwap you spend the UTXOs you received in a single transaction, then you just published the solution to the subset sum for your adversary.
  * This ties in even further to the "practical limit on the number of UTXOs".
    * Because it is not safe to spend the UTXOs from a single CoinSwap together, you want to have fewer, larger UTXOs for more flexibility in spending later.

I believe belcher and waxwing and nopara73 have been working far longer on privacy tech, and you should try to get in contact with them as well, they may know of other issues (or solutions to the above problems).

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[German Luna]

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

Good morning ZmnSCPxj,

The issues you point out are indeed important to note. Thank you for your
wonderful feedback!

* There is a practical limit to the number of UTXOs you would be willing to
> receive in the swap.
>   * Every UTXO you receive increases the potential fee you have to pay to
> spend them, meaning you would strongly dislike receiving 100 UTXOs that sum
> up to 1mBTC.
>
Absolutely agree. It wouldn't be particularly nice to have to manage that.

  * Thus, a practical blockchain analyst can bound the size of the sets
> involved, and the problem becomes less than NP in practice.
>
Definitely, though they first have to consider all subsets of a fixed size
with values bounded above by the value of the unknown sum. So the analyst
has to search through all fixed size sets (up to the practical bound) whose
elements are less than a maximum sum. This is a number of choices that is
(in a crude estimation) exponential (in the size of the UTXO set), and
polynomial in the number UTXOs below that maximum sum value on-chain which
can be pretty big at sufficiently large value-transfers.

* If you have a single UTXO and split it, then swap, anyone looking at the
> history can conjecture that the split involved is part of a CoinSwap.
>   * The split is now a hint on how the subset sums can be tried.
>
You're right that anybody could conjecture that it is involved in a
CoinSwap, however in my proposed protocol the swap would like a (schnorr)
P2PKH to the chain so you'd have to make that conjecture for every UTXO, so
it's not much of a hint. Especially so noting that one, both or none of the
outputs could be part of a swap.

* If after the CoinSwap you spend the UTXOs you received in a single
> transaction, then you just published the solution to the subset sum for
> your adversary.
>   * This ties in even further to the "practical limit on the number of
> UTXOs".
>     * Because it is not safe to spend the UTXOs from a single CoinSwap
> together, you want to have fewer, larger UTXOs for more flexibility in
> spending later.
>
Yes, this is definitely a weakness and some over-the-top UTXO management
techniques (e.g. try to avoid combining different UTXOs in a known set into
the same transaction by default, where possible) would be needed or like
you say fewer larger UTXOs.

It's interesting to note one can pick some subset of recent UTXOs and add
up their output values, and select that as the amount of value transfer to
exchange in a given operation. Resulting in a bit of added obfuscation as
there are now seemingly (at least) 3 utxo sets that add up to similar or
identical values, but only two of which are really participating in the
swap.

I believe belcher and waxwing and nopara73 have been working far longer on
> privacy tech, and you should try to get in contact with them as well, they
> may know of other issues (or solutions to the above problems).
>
Thank you for your input and suggestions! I will reach out to them.

-- 
Germán
Mathematician

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

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[Chris Belcher]

On 24/04/2020 02:34, ZmnSCPxj via bitcoin-dev wrote:
> Good morning Germán,
> 
> 
>> With regards to trying to tackle the problem of value-based correlations, wouldn't it be possible to try to model the solution after the equal-sum-subset problem (np complete problem)( https://www.cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subsetSumNPCompleteness.pdf  )? 
>> That is, a pair of individuals with a set of UTXOs that both add up to similar if not equal value perform a swap of similar-(total)value sets. In this way the values of the UTXOs can be broken up essentially at random (following some nominal distribution so that it doesn't stand out; e.g. https://en.wikipedia.org/wiki/Benford%27s_law), but swapped in conjunction and decorrelated by using different keys + randomized locktimes.
> 
> There are a number of issues to simply modeling this to the subset-sum problem.
> 
> * There is a practical limit to the number of UTXOs you would be willing to receive in the swap.
>   * Every UTXO you receive increases the potential fee you have to pay to spend them, meaning you would strongly dislike receiving 100 UTXOs that sum up to 1mBTC.
>   * Thus, a practical blockchain analyst can bound the size of the sets involved, and the problem becomes less than NP in practice.
> * If you have a single UTXO and split it, then swap, anyone looking at the history can conjecture that the split involved is part of a CoinSwap.
>   * The split is now a hint on how the subset sums can be tried.
> * If after the CoinSwap you spend the UTXOs you received in a single transaction, then you just published the solution to the subset sum for your adversary.
>   * This ties in even further to the "practical limit on the number of UTXOs".
>     * Because it is not safe to spend the UTXOs from a single CoinSwap together, you want to have fewer, larger UTXOs for more flexibility in spending later.
> 
> I believe belcher and waxwing and nopara73 have been working far longer on privacy tech, and you should try to get in contact with them as well, they may know of other issues (or solutions to the above problems).
> 
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

Hello list,

A couple of thoughts on multi-transaction coinswaps:

* Users should never split up a single UTXO before doing a coinswap,
instead they should send the one UTXO to a coinswap address and get back
multiple UTXOs.

For example, this 1-to-3 TXO coinswap (The symbol ----> means bitcoin
transaction).

    AliceA (10 BTC) ----> CoinSwap AddressA ----> BobA (10 BTC)

    BobB (3 BTC) ----> CoinSwap AddressB ----> AliceB (6 BTC)
    BobC (2 BTC) ----> CoinSwap AddressC ----> AliceC (3 BTC)
    BobD (5 BTC) ----> CoinSwap AddressD ----> AliceD (1 BTC)


Note that the Bob-to-Alice set of transactions add up to 10 BTC, the
entire CoinSwap is swapping the same amount.

Or written another way:

    Alice TXO (10 BTC) ----> Coinswap Protocol ----> Alice TXO1 (6 BTC)
                                               ----> Alice TXO2 (3 BTC)
                                               ----> Alice TXO3 (1 BTC)

This kind of thing could also be used for consolidation of many UTXOs
without necessarily leaking information that the same person owns them.
For example, if Alice owns 5 UTXOs:

    Alice TXO1 ----> Coinswap Protocol ----> Alice TXO
    Alice TXO2 ---->
    Alice TXO3 ---->
    Alice TXO4 ---->
    Alice TXO5 ---->


* It's helpful if any CoinSwap app is actually used for spending rather
than just mixing back to yourself. That will help avoid the problem of
users inadvertently co-spending all their coinswap outputs in the same
transaction.
An example of Alice paying for a VPN anonymously:

    Alice TXO (10 BTC) ---> Coinswap Protocol ---> VPN Payment (0.1 BTC)
                                              ---> Change1 (6 BTC)
                                              ---> Change2 (3 BTC)
                                              ---> Change3 (0.9 BTC)

In this case Alice will never accidentally merge all her TXOs together,
because the VPN Payment TXO doesn't belong to her. Also this could
improve privacy because unlike in normal transaction the VPN provider
might not be able to figure out the lower bound of Alice's balance (10
BTC in this case).


* Multi-transaction CoinSwaps aren't truly an example of a subset-sum
problem, but "sparse subset sum", a related and easier problem.

The way its normally formulated, subset sum is about finding a subset
that adds up to a target value. But in multi-transaction coinswap
there'd only be three or four CoinSwap outputs, so the problem is
finding just three or four integers in a big set that add up to the target.

You could think of it mathematically that the n-choose-k function is
near-polynomial when k is near 0 or near n, and the function is
exponential when k is near n/2.

A more promising way to build privacy is to create a situation where an
adversary would find a huge amount of false positives which are very
close the amount being sent. So even if the adversary has enough
computational power to iterate all the amounts it won't help them much
due to the huge number of false positives.


Regards
CB

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[ZmnSCPxj]

Good morning CB,

I have been thinking about CoinSwap for a good while as well.

Here are some very unorganized thoughts.

It wold be nice to interoperate with JoinMarket, i.e. have a JoinMarket maker that also provides CoinSwap services using the same UTXOs.
However, this requires us to retain compatibility with the JoinMarket wallet structure, which is divided into mixdepths, with the rule that UTXOs in different mixdepths cannot be spent together in the same onchain UTXO (to move across mixdepths you have to do a send, and sending out is always done by a single CoinJoin round with multiple makers).

I am uncertain what is the best way to handle multitransaction when considering the mixdepth system.
My instinct is that if you are doing multitransaction (whether as taker or maker) then each transaction in the swap *has to* come from a different mixdepth.
The issue here is:

* If all the UTXOs in the multitransaction swap come from the same mixdepth, then a surveillor who is monitoring that mixdepth gets a good hint in solving the sparse subset sum problem.
* On the other hand, if all the UTXOs in the multitransaction swap come from different mixdepths, then a surveillor who has solved the sparse subset sum problem now has the hint that the different mixdepths are really owned by the same JoinMarket user.

I am uncertain which tradeoff is better here, though I am inclined to think the latter is better.


Attempting to completely detach a market-for-CoinSwap from JoinMarket seems to be impossible to my mind: the protocols are known, implementations open, and someone will inevitably write code for a single piece of software that can operate as both a JoinMarket maker *and* a maker for a market-for-CoinSwap (to increase their market, so to speak), so it might be better to just add CoinSwap to JoinMarket in the first place.


> A couple of thoughts on multi-transaction coinswaps:
>
> -   Users should never split up a single UTXO before doing a coinswap,
>     instead they should send the one UTXO to a coinswap address and get back
>     multiple UTXOs.
>
>     For example, this 1-to-3 TXO coinswap (The symbol ----> means bitcoin
>
>
> transaction).
>
> AliceA (10 BTC) ----> CoinSwap AddressA ----> BobA (10 BTC)
>
> BobB (3 BTC) ----> CoinSwap AddressB ----> AliceB (6 BTC)
>
>     BobC (2 BTC) ----> CoinSwap AddressC ----> AliceC (3 BTC)
>
>     BobD (5 BTC) ----> CoinSwap AddressD ----> AliceD (1 BTC)
>
>
> Note that the Bob-to-Alice set of transactions add up to 10 BTC, the
> entire CoinSwap is swapping the same amount.
>
> Or written another way:
>
> Alice TXO (10 BTC) ----> Coinswap Protocol ----> Alice TXO1 (6 BTC)
>
>                                                ----> Alice TXO2 (3 BTC)
>
>                                                ----> Alice TXO3 (1 BTC)
>

Assuming Alice is the taker, and Bob is the maker, then Alice might want a specific coin value (or set of such) that Bob does not have.
In that case, Bob will have to split a UTXO it owns.

We could constrain it so that Bob at least is not allowed to use the change from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC and 1 BTC coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cannot split its own 9 BTC coin then swap.
Or in terms of mixdepths, Bob can split within a mixdepth but each outgoing UTXO in the same swap should be from different mixdepths.



> -   It's helpful if any CoinSwap app is actually used for spending rather
>     than just mixing back to yourself. That will help avoid the problem of
>     users inadvertently co-spending all their coinswap outputs in the same
>     transaction.
>     An example of Alice paying for a VPN anonymously:
>
>     Alice TXO (10 BTC) ---> Coinswap Protocol ---> VPN Payment (0.1 BTC)
>
>                                                 ---> Change1 (6 BTC)
>
>                                                 ---> Change2 (3 BTC)
>
>                                                 ---> Change3 (0.9 BTC)
>
>
>
> In this case Alice will never accidentally merge all her TXOs together,
> because the VPN Payment TXO doesn't belong to her. Also this could
> improve privacy because unlike in normal transaction the VPN provider
> might not be able to figure out the lower bound of Alice's balance (10
> BTC in this case).

This is a good idea, akin to the rule in JoinMarket that all outgoing spends are done through a CoinJoin.

Of course, if a surveillor ***does*** solve the sparse subset sum, then the CoinSwap Protocol part looks exactly like a Bitcoin transaction, with a "main" paying output and a "change" output, and the same techniques that work with current Bitcoin txes work with "CoinSwap Protocol" virtual transactions.

It seems to me that, in a system of makers and takers, even if the maker is really just paying the taker(s) to do CoinSwaps to mix back to itself, it should still "require" some output amount that really goes to itself, so that the maker at least does not differentiate between the case that the taker is paying to itself vs the case that the taker is paying someone else via a CoinSwap.
That is, the protocol should still require that the taker specify *some* target desired amount, regardless of whether the taker wants to pay a specific value, or the taker wants to just mix its coins.


> -   Multi-transaction CoinSwaps aren't truly an example of a subset-sum
>     problem, but "sparse subset sum", a related and easier problem.
>
>     The way its normally formulated, subset sum is about finding a subset
>     that adds up to a target value. But in multi-transaction coinswap
>     there'd only be three or four CoinSwap outputs, so the problem is
>     finding just three or four integers in a big set that add up to the target.
>
>     You could think of it mathematically that the n-choose-k function is
>     near-polynomial when k is near 0 or near n, and the function is
>     exponential when k is near n/2.
>
>     A more promising way to build privacy is to create a situation where an
>     adversary would find a huge amount of false positives which are very
>     close the amount being sent. So even if the adversary has enough
>     computational power to iterate all the amounts it won't help them much
>     due to the huge number of false positives.

What are your thoughts on creating such possible situations?

An idea is to require standard swap amounts, i.e. similar to the standard 100mBTC mixing bin of Wasabi.

As well, one could randomly select some existing 1-input 1-output txes in the mempool and/or recent blocks, sum them, and swap for the same sum, to force at least one false positive, but the surveillor could protect against this by removing the earliest match (the one it saw in the mempool first, or onchain).

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[Chris Belcher]

Hello ZmnSCPxj,


On 29/04/2020 08:56, ZmnSCPxj wrote:
> It wold be nice to interoperate with JoinMarket, i.e. have a JoinMarket maker that also provides CoinSwap services using the same UTXOs.

A great benefit of a CoinSwap system is that the transactions are
steganographic. If equal-output-coinjoins were involved that benefit
would be lost. So it would be better if it didn't happen.

> However, this requires us to retain compatibility with the JoinMarket wallet structure, which is divided into mixdepths, with the rule that UTXOs in different mixdepths cannot be spent together in the same onchain UTXO (to move across mixdepths you have to do a send, and sending out is always done by a single CoinJoin round with multiple makers).
> I am uncertain what is the best way to handle multitransaction when considering the mixdepth system.
> My instinct is that if you are doing multitransaction (whether as taker or maker) then each transaction in the swap *has to* come from a different mixdepth.
> The issue here is:
> 
> * If all the UTXOs in the multitransaction swap come from the same mixdepth, then a surveillor who is monitoring that mixdepth gets a good hint in solving the sparse subset sum problem.
> * On the other hand, if all the UTXOs in the multitransaction swap come from different mixdepths, then a surveillor who has solved the sparse subset sum problem now has the hint that the different mixdepths are really owned by the same JoinMarket user.
> 
> I am uncertain which tradeoff is better here, though I am inclined to think the latter is better.

JoinMarket has many mixdepths (5 by default) because it's
equal-output-coinjoins easily leak change addresses. CoinSwap
transactions don't have this flaw because they're steganographic. Such a
system could also be coded to intentionally break the weaker change
output heuristics
(https://en.bitcoin.it/wiki/Privacy#Change_address_detection).

Equal-output-coinjoins and JoinMarket also have a version of the
common-input-ownership-heuristic (CIOH), because its often possible to
separate the inputs into sets of their owners of a equal-output-coinjoin
using the input amounts. CoinSwap can be combined with something like
PayJoin or CoinJoinXT, which would genuinely break the CIOH, so such a
system wouldn't have this flaw either.

For those reasons I've been thinking a CoinSwap system wouldn't need as
many mixdepths, maybe it could use two or even just one.

If so, then it follows that multi-transaction CoinSwaps can be done by
having UTXOs come from the same mixdepth, as long as the inputs that
should be separate are not co-spent in the same transaction.

Remember that a passive surveillor of the blockchain doesn't see
mixdepths at all, they see addresses and transactions, and must use
heuristics to try to cluster them together. We can break these heuristics.


> Attempting to completely detach a market-for-CoinSwap from JoinMarket seems to be impossible to my mind: the protocols are known, implementations open, and someone will inevitably write code for a single piece of software that can operate as both a JoinMarket maker *and* a maker for a market-for-CoinSwap (to increase their market, so to speak), so it might be better to just add CoinSwap to JoinMarket in the first place.

Someone who has the ability to write such code should also have the
awareness to realize that mixing equal-output-coinjoins with coinswaps
damages the privacy because it breaks the steganography of coinswaps.

Also, because CoinSwap is better than equal-output CoinJoin in almost
every way, we can expect users (who are takers) to stop using JoinMarket
and switch over to CoinSwap if the software becomes mature. So such a
JoinMarket maker won't get many customers, and so there wouldn't be much
point writing such maker code.

But for sure it would be good to reuse code in any eventual
implementation. Indeed Waxwing's implementation did:
https://github.com/AdamISZ/CoinSwapCS

> Assuming Alice is the taker, and Bob is the maker, then Alice might want a specific coin value (or set of such) that Bob does not have.
> In that case, Bob will have to split a UTXO it owns.
> 
> We could constrain it so that Bob at least is not allowed to use the change from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC and 1 BTC coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cannot split its own 9 BTC coin then swap.
> Or in terms of mixdepths, Bob can split within a mixdepth but each outgoing UTXO in the same swap should be from different mixdepths.

A good way to do it could be for Alice to tell Bob that she wants 10 BTC
and let Bob figure out on his own how to get that amount, based on the
amounts he already has. If Alice is making a payment she can provide
that amount too, but all the other output amounts can be up to Bob.

Bob would often still have to split a UTXO he owns, but see below about
breaking change address heuristics.

> Of course, if a surveillor ***does*** solve the sparse subset sum, then the CoinSwap Protocol part looks exactly like a Bitcoin transaction, with a "main" paying output and a "change" output, and the same techniques that work with current Bitcoin txes work with "CoinSwap Protocol" virtual transactions.
> 
> It seems to me that, in a system of makers and takers, even if the maker is really just paying the taker(s) to do CoinSwaps to mix back to itself, it should still "require" some output amount that really goes to itself, so that the maker at least does not differentiate between the case that the taker is paying to itself vs the case that the taker is paying someone else via a CoinSwap.
> That is, the protocol should still require that the taker specify *some* target desired amount, regardless of whether the taker wants to pay a specific value, or the taker wants to just mix its coins.

If Bob needs to split a UTXO he'd do that with a change output. And
because we understand change detection heuristics we can intentionally
break them, for example if Bob's UTXO is on a p2sh-p2wpkh address and
the CoinSwap address is of that type too (because ECDSA-2P is being
used) then Bob could make his change output p2wpkh or p2pkh. Then anyone
using the script-type-heuristic would think that the CoinSwap address is
actually change and still belongs to Bob, and that the real change
address is actually the payment or CoinSwap address. i.e. the adversary
would assume that wallet software only uses one script type, in this
case it assumes that Bob's wallet is exclusively p2sh-p2wpkh.

> 
>> -   Multi-transaction CoinSwaps aren't truly an example of a subset-sum
>>     problem, but "sparse subset sum", a related and easier problem.
>>
>>     The way its normally formulated, subset sum is about finding a subset
>>     that adds up to a target value. But in multi-transaction coinswap
>>     there'd only be three or four CoinSwap outputs, so the problem is
>>     finding just three or four integers in a big set that add up to the target.
>>
>>     You could think of it mathematically that the n-choose-k function is
>>     near-polynomial when k is near 0 or near n, and the function is
>>     exponential when k is near n/2.
>>
>>     A more promising way to build privacy is to create a situation where an
>>     adversary would find a huge amount of false positives which are very
>>     close the amount being sent. So even if the adversary has enough
>>     computational power to iterate all the amounts it won't help them much
>>     due to the huge number of false positives.
> 
> What are your thoughts on creating such possible situations?
> 
> An idea is to require standard swap amounts, i.e. similar to the standard 100mBTC mixing bin of Wasabi.
> 
> As well, one could randomly select some existing 1-input 1-output txes in the mempool and/or recent blocks, sum them, and swap for the same sum, to force at least one false positive, but the surveillor could protect against this by removing the earliest match (the one it saw in the mempool first, or onchain).

I think we can get the false positive count up because the n-choose-k
function still gets quite large as k increases.

We can make a simplified reasonable assumption that outputs on the
blockchain follow a lognormal distribution. An adversary trying to unmix
a 3-transaction CoinSwap would have to find the sum of every
3-combination of the relevant outputs. For our case, the sum of three
lognormal distributions is another lognormal distribution with different
parameters, it's corresponding frequency distribution would get scaled
by n-choose-3. This frequency distribution is what the adversary would
find when searching, and that distribution would be quite tall because
of the scaling by n-choose-k. Suppose our CoinSwap is for 4 BTC then the
adversary would look at their frequency distribution at 4 BTC and find a
pretty big number, i.e. many other combinations of 3 outputs would add
up to 4 BTC just by chance. That is the false positive rate, and is our
anonymity set with respect to this attack.

To work this out precisely we'd need to study the distribution of output
values on the blockchain today, and see how it behaves when summed
together. But the lognormal distribution assumption is probably not too
far from the truth, as it appears all the time in economics and finance,
and there is a clear justification for why. And the scaling by
n-choose-k would still hold.

Along with that, some output amounts have very few significant figures
(e.g. 1 BTC, 0.1 BTC, 0.01 BTC), presumably because the user types just
one number on their keyboard when creating a transaction. We can use
that fact to add a bit of privacy by occasionally making one of our
outputs also be rounded like that.

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[ZmnSCPxj]

Good morning CB,


> Equal-output-coinjoins and JoinMarket also have a version of the
> common-input-ownership-heuristic (CIOH), because its often possible to
> separate the inputs into sets of their owners of a equal-output-coinjoin
> using the input amounts. CoinSwap can be combined with something like
> PayJoin or CoinJoinXT, which would genuinely break the CIOH, so such a
> system wouldn't have this flaw either.
>
> For those reasons I've been thinking a CoinSwap system wouldn't need as
> many mixdepths, maybe it could use two or even just one.

Would the ZeroLink proposal of separating a receiving (pre-mix) wallet from a sending (post-mix) wallet apply, thus having two implicit mixdepths (the receiving mixdepth and the sending mixdepth)?
Or would imposing the rule "all sends must be via CoinSwap" be sufficient (and follow the ZeroLink rule in spirit)?

> If so, then it follows that multi-transaction CoinSwaps can be done by
> having UTXOs come from the same mixdepth, as long as the inputs that
> should be separate are not co-spent in the same transaction.

This "as long as the inputs that should be separate are not co-spent" is precisely what mixdepths protect against, which is why I think *some* kind of mixdepth facility will still matter in CoinSwap.

Still, you have convinced me that, for the purpose of multi-transaction CoinSwap where you do not merge any of your coins, it is immaterial if the sub-transactions come from the same mixdepth or not.
And if you have to merge your coins (for instance, if you are a maker and your customer wants to get a UTXO that is larger than any you have on hand, you have to merge your coins), you just have to ensure they are in the same mixdepth.

Of course, you *could* be proposing some other construct --- perhaps you have some relational entry which says "you cannot merge coin A and coin B" which allows you to merge A C D or B C E, but not A B?
(I imagine this would make coin selection even harder, but I am not a mathematician and there may be some trivial solution to this.)

Now --- if you have two coins that cannot be merged in the same onchain tx, what happens when you swap them in a multi-tx CoinSwap with somebody else?
That somebody else does not know that information.
Instead, that somebody else must always assume that any coins it got from the same CoinSwap operation must not be safely mergeable (though they can still be used in the same swap together).

Coins received via receive addresses would also not be mergeable with any other coins, except coins to the same address (because coins in the same address already leak that they are owned by the same owner).

>
> Remember that a passive surveillor of the blockchain doesn't see
> mixdepths at all, they see addresses and transactions, and must use
> heuristics to try to cluster them together. We can break these heuristics.
>
> > Attempting to completely detach a market-for-CoinSwap from JoinMarket seems to be impossible to my mind: the protocols are known, implementations open, and someone will inevitably write code for a single piece of software that can operate as both a JoinMarket maker and a maker for a market-for-CoinSwap (to increase their market, so to speak), so it might be better to just add CoinSwap to JoinMarket in the first place.
>
> Someone who has the ability to write such code should also have the
> awareness to realize that mixing equal-output-coinjoins with coinswaps
> damages the privacy because it breaks the steganography of coinswaps.
>
> Also, because CoinSwap is better than equal-output CoinJoin in almost
> every way, we can expect users (who are takers) to stop using JoinMarket
> and switch over to CoinSwap if the software becomes mature. So such a
> JoinMarket maker won't get many customers, and so there wouldn't be much
> point writing such maker code.

An unscrupulous possible maker might not value the privacy of its customers (indeed makers are a privacy attack vector, which requires something like fidelity bonds like you suggested before to protect against), and takers might not want to do possibly-computationally-expensive blockchain analysis to evaluate whether a particular maker values privacy.
An unscrupulous maker might thus earn more than a more scrupulous maker can, at least during the transition from JoinMarket to SwapMarket, and get a greater share of the future SwapMarket available liquidity due to their increased earnings during the transition.

Against this we should remember that software that does two things is four times as complicated as software that does one thing, so hopefully your projected transition from JoinMarket to SwapMarket will be fast enough that such a combined Join/SwapMarket maker software does not arise fast enough to matter.


> But for sure it would be good to reuse code in any eventual
> implementation. Indeed Waxwing's implementation did:
> https://github.com/AdamISZ/CoinSwapCS
>
> > Assuming Alice is the taker, and Bob is the maker, then Alice might want a specific coin value (or set of such) that Bob does not have.
> > In that case, Bob will have to split a UTXO it owns.
> > We could constrain it so that Bob at least is not allowed to use the change from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC and 1 BTC coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cannot split its own 9 BTC coin then swap.
> > Or in terms of mixdepths, Bob can split within a mixdepth but each outgoing UTXO in the same swap should be from different mixdepths.
>
> A good way to do it could be for Alice to tell Bob that she wants 10 BTC
> and let Bob figure out on his own how to get that amount, based on the
> amounts he already has. If Alice is making a payment she can provide
> that amount too, but all the other output amounts can be up to Bob.

This leaks to Bob whether Alice is making a payment or not; it would be better for the privacy of Alice for Alice to *always* mention *some* "payment amount", even if this is not actually a payment and Alice is just mixing for herself prior to storing in cold storage.
And if Alice wants to use a single swap to pay to multiple targets at once, that implies Alice has to have the ability to indicate the outputs it wants to Bob, and it would imply as well that Alice has to obfuscate which of those outputs have amounts that actually *matter* (by always insisting on what the output amounts must be, rather than insisting on N output amounts and letting Bob handle the rest).
(We *could* constrain it such that Alice can make only one payment per CoinSwap, so that Alice only gives one "target" amount and one "total" amount, but that implies even bigger blockspace utilization, sigh.)

Otherwise, Bob can get information:

* "Oh, Alice did not specify any of the outputs, just the total amount, all of my old coins are owned by Alice now."
* "Oh, Alice specified an exact value for one of the outputs, that one is no longer owned by Alice but the rest are owned by Alice."
* "Oh, Alice specified exact values for two of the outputs, those two are definitely no longer owned by Alice but the rest are owned by Alice."

The conclusion here is either Alice never specifies any of the outputs --- in which case Alice cannot use a CoinSwap to pay directly to somebody else --- or Alice specifies all of them.

Again, the maker might be an active surveillor, thus we should reduce information leaks to the maker as much as we can.

>
> Bob would often still have to split a UTXO he owns, but see below about
> breaking change address heuristics.
>
> > Of course, if a surveillor does solve the sparse subset sum, then the CoinSwap Protocol part looks exactly like a Bitcoin transaction, with a "main" paying output and a "change" output, and the same techniques that work with current Bitcoin txes work with "CoinSwap Protocol" virtual transactions.
> > It seems to me that, in a system of makers and takers, even if the maker is really just paying the taker(s) to do CoinSwaps to mix back to itself, it should still "require" some output amount that really goes to itself, so that the maker at least does not differentiate between the case that the taker is paying to itself vs the case that the taker is paying someone else via a CoinSwap.
> > That is, the protocol should still require that the taker specify some target desired amount, regardless of whether the taker wants to pay a specific value, or the taker wants to just mix its coins.
>
> If Bob needs to split a UTXO he'd do that with a change output. And
> because we understand change detection heuristics we can intentionally
> break them, for example if Bob's UTXO is on a p2sh-p2wpkh address and
> the CoinSwap address is of that type too (because ECDSA-2P is being
> used) then Bob could make his change output p2wpkh or p2pkh. Then anyone
> using the script-type-heuristic would think that the CoinSwap address is
> actually change and still belongs to Bob, and that the real change
> address is actually the payment or CoinSwap address. i.e. the adversary
> would assume that wallet software only uses one script type, in this
> case it assumes that Bob's wallet is exclusively p2sh-p2wpkh.
>
> > > -   Multi-transaction CoinSwaps aren't truly an example of a subset-sum
> > >     problem, but "sparse subset sum", a related and easier problem.
> > >     The way its normally formulated, subset sum is about finding a subset
> > >     that adds up to a target value. But in multi-transaction coinswap
> > >     there'd only be three or four CoinSwap outputs, so the problem is
> > >     finding just three or four integers in a big set that add up to the target.
> > >     You could think of it mathematically that the n-choose-k function is
> > >     near-polynomial when k is near 0 or near n, and the function is
> > >     exponential when k is near n/2.
> > >     A more promising way to build privacy is to create a situation where an
> > >     adversary would find a huge amount of false positives which are very
> > >     close the amount being sent. So even if the adversary has enough
> > >     computational power to iterate all the amounts it won't help them much
> > >     due to the huge number of false positives.
> > >
> >
> > What are your thoughts on creating such possible situations?
> > An idea is to require standard swap amounts, i.e. similar to the standard 100mBTC mixing bin of Wasabi.
> > As well, one could randomly select some existing 1-input 1-output txes in the mempool and/or recent blocks, sum them, and swap for the same sum, to force at least one false positive, but the surveillor could protect against this by removing the earliest match (the one it saw in the mempool first, or onchain).
>
> I think we can get the false positive count up because the n-choose-k
> function still gets quite large as k increases.
>
> We can make a simplified reasonable assumption that outputs on the
> blockchain follow a lognormal distribution. An adversary trying to unmix
> a 3-transaction CoinSwap would have to find the sum of every
> 3-combination of the relevant outputs. For our case, the sum of three
> lognormal distributions is another lognormal distribution with different
> parameters, it's corresponding frequency distribution would get scaled
> by n-choose-3. This frequency distribution is what the adversary would
> find when searching, and that distribution would be quite tall because
> of the scaling by n-choose-k. Suppose our CoinSwap is for 4 BTC then the
> adversary would look at their frequency distribution at 4 BTC and find a
> pretty big number, i.e. many other combinations of 3 outputs would add
> up to 4 BTC just by chance. That is the false positive rate, and is our
> anonymity set with respect to this attack.
>
> To work this out precisely we'd need to study the distribution of output
> values on the blockchain today, and see how it behaves when summed
> together. But the lognormal distribution assumption is probably not too
> far from the truth, as it appears all the time in economics and finance,
> and there is a clear justification for why. And the scaling by
> n-choose-k would still hold.

Okay, from what little I understand it seems that "even if sparse subset sum is easier than subset sum, it is still hard, so it probably will not matter in practice", would that be a fair takeaway?

>
> Along with that, some output amounts have very few significant figures
> (e.g. 1 BTC, 0.1 BTC, 0.01 BTC), presumably because the user types just
> one number on their keyboard when creating a transaction. We can use
> that fact to add a bit of privacy by occasionally making one of our
> outputs also be rounded like that.

I agree.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[Chris Belcher]

Hello ZmnSCPxj,

On 30/04/2020 09:54, ZmnSCPxj wrote:
> Good morning CB,
> 
> 
>> Equal-output-coinjoins and JoinMarket also have a version of the
>> common-input-ownership-heuristic (CIOH), because its often possible to
>> separate the inputs into sets of their owners of a equal-output-coinjoin
>> using the input amounts. CoinSwap can be combined with something like
>> PayJoin or CoinJoinXT, which would genuinely break the CIOH, so such a
>> system wouldn't have this flaw either.
>>
>> For those reasons I've been thinking a CoinSwap system wouldn't need as
>> many mixdepths, maybe it could use two or even just one.
> 
> Would the ZeroLink proposal of separating a receiving (pre-mix) wallet from a sending (post-mix) wallet apply, thus having two implicit mixdepths (the receiving mixdepth and the sending mixdepth)?
> Or would imposing the rule "all sends must be via CoinSwap" be sufficient (and follow the ZeroLink rule in spirit)?
> 
>> If so, then it follows that multi-transaction CoinSwaps can be done by
>> having UTXOs come from the same mixdepth, as long as the inputs that
>> should be separate are not co-spent in the same transaction.
> 
> This "as long as the inputs that should be separate are not co-spent" is precisely what mixdepths protect against, which is why I think *some* kind of mixdepth facility will still matter in CoinSwap.
> 
> Still, you have convinced me that, for the purpose of multi-transaction CoinSwap where you do not merge any of your coins, it is immaterial if the sub-transactions come from the same mixdepth or not.
> And if you have to merge your coins (for instance, if you are a maker and your customer wants to get a UTXO that is larger than any you have on hand, you have to merge your coins), you just have to ensure they are in the same mixdepth.
> 
> Of course, you *could* be proposing some other construct --- perhaps you have some relational entry which says "you cannot merge coin A and coin B" which allows you to merge A C D or B C E, but not A B?
> (I imagine this would make coin selection even harder, but I am not a mathematician and there may be some trivial solution to this.)
> 
> Now --- if you have two coins that cannot be merged in the same onchain tx, what happens when you swap them in a multi-tx CoinSwap with somebody else?
> That somebody else does not know that information.
> Instead, that somebody else must always assume that any coins it got from the same CoinSwap operation must not be safely mergeable (though they can still be used in the same swap together).
> 
> Coins received via receive addresses would also not be mergeable with any other coins, except coins to the same address (because coins in the same address already leak that they are owned by the same owner).

Yes I guess you're right. This part about mixdepths requires further
thought.

CoinSwap can be combined with some kind of CoinJoin (most likely
something similar to PayJoin or CoinJoinXT). That should help with the
reasoning about co-spending inputs and mixdepths, because other inputs
that are not owned by the taker will often be co-spent anyway.

Regarding coins which mustn't be co-spent being coinswapped to somebody
else, ideally that coinswap maker will receive coins from unrelated
takers too, so will merge their coins along with those as well. Also the
fact that a coinswap happened means there are two transactions between
the taker's-inputs-which-mustnt-be-merged and them actually being merged.

Great point on the receive addresses coins. Another use case of
mixdepths is to stop incoming payments from two different sources being
linked together.

>>> Assuming Alice is the taker, and Bob is the maker, then Alice might want a specific coin value (or set of such) that Bob does not have.
>>> In that case, Bob will have to split a UTXO it owns.
>>> We could constrain it so that Bob at least is not allowed to use the change from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC and 1 BTC coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cannot split its own 9 BTC coin then swap.
>>> Or in terms of mixdepths, Bob can split within a mixdepth but each outgoing UTXO in the same swap should be from different mixdepths.
>>
>> A good way to do it could be for Alice to tell Bob that she wants 10 BTC
>> and let Bob figure out on his own how to get that amount, based on the
>> amounts he already has. If Alice is making a payment she can provide
>> that amount too, but all the other output amounts can be up to Bob.
> 
> This leaks to Bob whether Alice is making a payment or not; it would be better for the privacy of Alice for Alice to *always* mention *some* "payment amount", even if this is not actually a payment and Alice is just mixing for herself prior to storing in cold storage.
> And if Alice wants to use a single swap to pay to multiple targets at once, that implies Alice has to have the ability to indicate the outputs it wants to Bob, and it would imply as well that Alice has to obfuscate which of those outputs have amounts that actually *matter* (by always insisting on what the output amounts must be, rather than insisting on N output amounts and letting Bob handle the rest).
> (We *could* constrain it such that Alice can make only one payment per CoinSwap, so that Alice only gives one "target" amount and one "total" amount, but that implies even bigger blockspace utilization, sigh.)
> 
> Otherwise, Bob can get information:
> 
> * "Oh, Alice did not specify any of the outputs, just the total amount, all of my old coins are owned by Alice now."
> * "Oh, Alice specified an exact value for one of the outputs, that one is no longer owned by Alice but the rest are owned by Alice."
> * "Oh, Alice specified exact values for two of the outputs, those two are definitely no longer owned by Alice but the rest are owned by Alice."
> 
> The conclusion here is either Alice never specifies any of the outputs --- in which case Alice cannot use a CoinSwap to pay directly to somebody else --- or Alice specifies all of them.
> 
> Again, the maker might be an active surveillor, thus we should reduce information leaks to the maker as much as we can.

Yep great point.

A benefit of Alice not specifying any amounts is that Bob is able to
improve privacy and reduce costs by creating fewer change outputs. A
downside is that this leaks Alice's intentions (self-mix vs payment) to Bob.

A solution could be to add randomness. Have Alice randomly specify
payment amounts with some probability even if she is only self-mixing.

Although this doesn't solve everything, because Alice not specifying any
amounts implies self-mixing. But at least specifying some amounts
doesn't imply a payment.

>>
>> Bob would often still have to split a UTXO he owns, but see below about
>> breaking change address heuristics.
>>
>>> Of course, if a surveillor does solve the sparse subset sum, then the CoinSwap Protocol part looks exactly like a Bitcoin transaction, with a "main" paying output and a "change" output, and the same techniques that work with current Bitcoin txes work with "CoinSwap Protocol" virtual transactions.
>>> It seems to me that, in a system of makers and takers, even if the maker is really just paying the taker(s) to do CoinSwaps to mix back to itself, it should still "require" some output amount that really goes to itself, so that the maker at least does not differentiate between the case that the taker is paying to itself vs the case that the taker is paying someone else via a CoinSwap.
>>> That is, the protocol should still require that the taker specify some target desired amount, regardless of whether the taker wants to pay a specific value, or the taker wants to just mix its coins.
>>
>> If Bob needs to split a UTXO he'd do that with a change output. And
>> because we understand change detection heuristics we can intentionally
>> break them, for example if Bob's UTXO is on a p2sh-p2wpkh address and
>> the CoinSwap address is of that type too (because ECDSA-2P is being
>> used) then Bob could make his change output p2wpkh or p2pkh. Then anyone
>> using the script-type-heuristic would think that the CoinSwap address is
>> actually change and still belongs to Bob, and that the real change
>> address is actually the payment or CoinSwap address. i.e. the adversary
>> would assume that wallet software only uses one script type, in this
>> case it assumes that Bob's wallet is exclusively p2sh-p2wpkh.
>>
>>>> -   Multi-transaction CoinSwaps aren't truly an example of a subset-sum
>>>>     problem, but "sparse subset sum", a related and easier problem.
>>>>     The way its normally formulated, subset sum is about finding a subset
>>>>     that adds up to a target value. But in multi-transaction coinswap
>>>>     there'd only be three or four CoinSwap outputs, so the problem is
>>>>     finding just three or four integers in a big set that add up to the target.
>>>>     You could think of it mathematically that the n-choose-k function is
>>>>     near-polynomial when k is near 0 or near n, and the function is
>>>>     exponential when k is near n/2.
>>>>     A more promising way to build privacy is to create a situation where an
>>>>     adversary would find a huge amount of false positives which are very
>>>>     close the amount being sent. So even if the adversary has enough
>>>>     computational power to iterate all the amounts it won't help them much
>>>>     due to the huge number of false positives.
>>>>
>>>
>>> What are your thoughts on creating such possible situations?
>>> An idea is to require standard swap amounts, i.e. similar to the standard 100mBTC mixing bin of Wasabi.
>>> As well, one could randomly select some existing 1-input 1-output txes in the mempool and/or recent blocks, sum them, and swap for the same sum, to force at least one false positive, but the surveillor could protect against this by removing the earliest match (the one it saw in the mempool first, or onchain).
>>
>> I think we can get the false positive count up because the n-choose-k
>> function still gets quite large as k increases.
>>
>> We can make a simplified reasonable assumption that outputs on the
>> blockchain follow a lognormal distribution. An adversary trying to unmix
>> a 3-transaction CoinSwap would have to find the sum of every
>> 3-combination of the relevant outputs. For our case, the sum of three
>> lognormal distributions is another lognormal distribution with different
>> parameters, it's corresponding frequency distribution would get scaled
>> by n-choose-3. This frequency distribution is what the adversary would
>> find when searching, and that distribution would be quite tall because
>> of the scaling by n-choose-k. Suppose our CoinSwap is for 4 BTC then the
>> adversary would look at their frequency distribution at 4 BTC and find a
>> pretty big number, i.e. many other combinations of 3 outputs would add
>> up to 4 BTC just by chance. That is the false positive rate, and is our
>> anonymity set with respect to this attack.
>>
>> To work this out precisely we'd need to study the distribution of output
>> values on the blockchain today, and see how it behaves when summed
>> together. But the lognormal distribution assumption is probably not too
>> far from the truth, as it appears all the time in economics and finance,
>> and there is a clear justification for why. And the scaling by
>> n-choose-k would still hold.
> 
> Okay, from what little I understand it seems that "even if sparse subset sum is easier than subset sum, it is still hard, so it probably will not matter in practice", would that be a fair takeaway?

Not exactly. Here's another summary:

Suppose Alice has V bitcoins and mixes them with multi-transaction
CoinSwap, she receives transactions with amounts (w_0, w_1, w_2....)
which add up to V.

Privacy relying on the (sparse) subset sum problem works by making it
_computationally infeasible_ for an adversary to search the entire
blockchain for sets of transactions (w_0, w_1, w_2....) which add up to
V. I believe aiming for this kind of privacy isn't practical due to
block space considerations and others.

Privacy relying on false positives does not make any search
computationally infeasible, it works by having a large number of other
sets of transactions (w_0, w_1, w_2....) which add up to V just by
chance. Then the transactions received by Alice's will have a big crowd
to hide in. I believe this is practical because the numbers are
proportional to the n-choose-k function which can still be very large.


Regards
CB

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[ZmnSCPxj]

Good morning CB,

> > This "as long as the inputs that should be separate are not co-spent" is precisely what mixdepths protect against, which is why I think some kind of mixdepth facility will still matter in CoinSwap.
> > Still, you have convinced me that, for the purpose of multi-transaction CoinSwap where you do not merge any of your coins, it is immaterial if the sub-transactions come from the same mixdepth or not.
> > And if you have to merge your coins (for instance, if you are a maker and your customer wants to get a UTXO that is larger than any you have on hand, you have to merge your coins), you just have to ensure they are in the same mixdepth.
> > Of course, you could be proposing some other construct --- perhaps you have some relational entry which says "you cannot merge coin A and coin B" which allows you to merge A C D or B C E, but not A B?
> > (I imagine this would make coin selection even harder, but I am not a mathematician and there may be some trivial solution to this.)
> > Now --- if you have two coins that cannot be merged in the same onchain tx, what happens when you swap them in a multi-tx CoinSwap with somebody else?
> > That somebody else does not know that information.
> > Instead, that somebody else must always assume that any coins it got from the same CoinSwap operation must not be safely mergeable (though they can still be used in the same swap together).
> > Coins received via receive addresses would also not be mergeable with any other coins, except coins to the same address (because coins in the same address already leak that they are owned by the same owner).
>
> Yes I guess you're right. This part about mixdepths requires further
> thought.
>
> CoinSwap can be combined with some kind of CoinJoin (most likely
> something similar to PayJoin or CoinJoinXT). That should help with the
> reasoning about co-spending inputs and mixdepths, because other inputs
> that are not owned by the taker will often be co-spent anyway.
>
> Regarding coins which mustn't be co-spent being coinswapped to somebody
> else, ideally that coinswap maker will receive coins from unrelated
> takers too, so will merge their coins along with those as well. Also the
> fact that a coinswap happened means there are two transactions between
> the taker's-inputs-which-mustnt-be-merged and them actually being merged.

One of those transactions (the second one) will be a 1-input 1-output tx (it moves the coin from bilateral control to unilateral control of Bob), which chain analysis already knows to be a self-transfer.
The first transaction will also usually be a 1-input 1-output tx as well (it moves the coin from unilateral of Alice to bilateral control) if you did not do any splitting or merging before providing the coin into the swap (for example if this comes from the taker, and the taker knows all the coins it wants to swap cannot be safely merged together).

If chain analysis keeps the heuristic "1-input 1-output is a self-payment because srsly who has an exact amount for a payment Bitcoin is volatile lol", then the resulting coins still are not safe to merge, because chain analysis will "pass through" the swap operation and if the two coins are later merged then they still end up *correctly* concluding the original coins were owned by the same owner.

Using a PayJoin construction for the second tx would help, but if the receiving end does not have a spare UTXO it can merge with (e.g. all its liquidity got tied up in the swap) then there might not be an opportunity to PayJoin.

There is also little that can be done about the first transaction, in case it ends up being a 1-input 1-output.

Suppose Alice the taker has a 1 BTC output and a 1 BTC output *and no other coins*, both of which it cannot safely merge, and it has to pay 1.2 BTC to Carol.
Alice then has to CoinSwap them to Bob the maker, requesting a 1.2 BTC output going to Carol and the rest in whatever loose change Bob has.
Alice then has to use two 1-input 1-output txes for each of its 1 BTC outputs (because it cannot merge them together) to put them into bilateral control.
Then Bob claims them from bilateral control with 1-input 1-output txes as well (it cannot merge them together, because that might break Alice privacy, and Bob might not have any other spare coins it can merge with the incoming funds).

Now, even if Bob PayJoins the second tx for both 1 BTC outputs, it still cannot merge the resulting joined coins together, because the "spent-together" analysis would still tie those coins as being owned by the same owner, it is simply that the surveillor will think the owner owns more coins than it actually does, but the two 1 BTC TXOs that Alice used to own are still analyzed as being owned by the same owner if they are ever merged.

What Alice could do, to "merge" its 1BTC coins together, would be to swap only one of the 1BTC coins first, for a single 1BTC coin as well.
Then presumably the incoming 1BTC coin has no linkage with the coin Alice swapped out (Alice hopes), then Alice could spend that new 1BTC coin with the old one it could not merge with the coin it swapped out.
(Actually Alice does not need to do that as it is the customer after all, but maybe Bob the maker has to do that sometimes, in case it finds there are too many cannot-spend-together constraints in its pool of UTXOs and it is getting harder to select coins --- but if so, who does Bob the maker swap *with*?
If Bob can encounter that problem, then maybe other makers will also have that problem as well!)

(the above can be done by PayJoining with the unswapped coin on either the first or second transaction in the swap as well; the idea is more general.)

>
> Great point on the receive addresses coins. Another use case of
> mixdepths is to stop incoming payments from two different sources being
> linked together.

We could eliminate mixdepths entirely and just use "cannot merge with X" constraints.

When the wallet sees an incoming payment, it just marks it as "cannot merge with" all other coins it owns, unless they have the same address.
This prevents any linkage at all and is maximally private.

On a CoinSwap, the incoming coins are marked as "cannot merge with" to each other in the same CoinSwap operation, but not with any other coins it owns.

Maybe?

It might be easier for the user to understand as well, and reduces scope for mistakes in using mixdepths.
For example, I might have a sensitive source of funds (e.g. from all the ransomware I have been writing) and put them in one mixdepth, then after a few months I forgot which mixdepth I put those in and accidentally use it for my on-the-books salary.


> > > > Assuming Alice is the taker, and Bob is the maker, then Alice might want a specific coin value (or set of such) that Bob does not have.
> > > > In that case, Bob will have to split a UTXO it owns.
> > > > We could constrain it so that Bob at least is not allowed to use the change from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC and 1 BTC coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cannot split its own 9 BTC coin then swap.
> > > > Or in terms of mixdepths, Bob can split within a mixdepth but each outgoing UTXO in the same swap should be from different mixdepths.
> > >
> > > A good way to do it could be for Alice to tell Bob that she wants 10 BTC
> > > and let Bob figure out on his own how to get that amount, based on the
> > > amounts he already has. If Alice is making a payment she can provide
> > > that amount too, but all the other output amounts can be up to Bob.
> >
> > This leaks to Bob whether Alice is making a payment or not; it would be better for the privacy of Alice for Alice to always mention some "payment amount", even if this is not actually a payment and Alice is just mixing for herself prior to storing in cold storage.
> > And if Alice wants to use a single swap to pay to multiple targets at once, that implies Alice has to have the ability to indicate the outputs it wants to Bob, and it would imply as well that Alice has to obfuscate which of those outputs have amounts that actually matter (by always insisting on what the output amounts must be, rather than insisting on N output amounts and letting Bob handle the rest).
> > (We could constrain it such that Alice can make only one payment per CoinSwap, so that Alice only gives one "target" amount and one "total" amount, but that implies even bigger blockspace utilization, sigh.)
> > Otherwise, Bob can get information:
> >
> > -   "Oh, Alice did not specify any of the outputs, just the total amount, all of my old coins are owned by Alice now."
> > -   "Oh, Alice specified an exact value for one of the outputs, that one is no longer owned by Alice but the rest are owned by Alice."
> > -   "Oh, Alice specified exact values for two of the outputs, those two are definitely no longer owned by Alice but the rest are owned by Alice."
> >
> > The conclusion here is either Alice never specifies any of the outputs --- in which case Alice cannot use a CoinSwap to pay directly to somebody else --- or Alice specifies all of them.
> > Again, the maker might be an active surveillor, thus we should reduce information leaks to the maker as much as we can.
>
> Yep great point.
>
> A benefit of Alice not specifying any amounts is that Bob is able to
> improve privacy and reduce costs by creating fewer change outputs. A
> downside is that this leaks Alice's intentions (self-mix vs payment) to Bob.
>
> A solution could be to add randomness. Have Alice randomly specify
> payment amounts with some probability even if she is only self-mixing.
>
> Although this doesn't solve everything, because Alice not specifying any
> amounts implies self-mixing. But at least specifying some amounts
> doesn't imply a payment.

I think that maybe it would be a better policy for Alice to always just give a specified payment amount at all times.
Of course, a sufficiently motivated Bob could always just do statistical analysis on the payment amount (e.g. if it is not equivalent to some round number of United States Green Historical Commemoration Papers, it is unlikely to be a payment but instead a random amount that Alice had to provide on a self-payment).
So .....


Anyway, slightly unrelated, maybe we can simply have Alice specify a single payment amount always, as an unremovable part of the protocol.

I proposed "private key turnover" here: https://github.com/AdamISZ/CoinSwapCS/issues/53
Basically, after exchanging the swap secret, it is now safe to give your share of bilateral control to your swap partner, so you can just turn over that private key to the swap partner.
For clarity:

* Alice owns a 1 BTC coin it wants to swap with a 1 BTC coin from Bob.
* Alice sends its 1 BTC coin to bilateral control (Alice temporary key and Bob temporary key).
  * Backoffs and confirmations and etc etc are needed, we all know how to do CoinSwap safely, I elide those details here.
* Bob sends its 1 BTC to bilateral control (Alice 2nd temporary key and Bob 2nd temporary key).
* Alice and Bob complete the CoinSwap protocol and now both know the swap secret X, and have to claim the bilateral control before some future blockheight L.
* Alice can send its Alice temporary key to Bob, so that Bob can change the second transaction as it likes.
  * Bob can merge it with a coin it happens to have, without having to coordinate signing with Alice (i.e. it gets PayJoin on the second tx for free).
  * If Bob the maker gets another swap request, it can spend directly from the bilateral control address to another bilateral control address with a different taker, reducing blockchain footprint.
  * Bob can fee bump using RBF instead of CPFP.
* Bob can also now send its Bob 2nd temporary key to Alice, for similar advantages for Alice.

It does require that both Alice and Bob respect the timeout --- the bilateral outputs have to be spent before the timeout, else the timelock branches come into play.
But Alice and Bob, after private key turnover, need not *immediately* broadcast the claiming transactions --- they can wait a little time for opportunities to change the claiming transaction, for example if they get an incoming payment they could assume that the recently-concluded swap is safe to merge with the new incoming coin and they can CPFP the incoming payment on the mempool with their existing coin, or Bob the maker might get another customer and Bob can cut-through from one swap to the next, reducing 4 transactions for 2 swaps to just 3 transactions (and if it can continuously chain customers that way, in the long run Bob on average has 1 transaction per swap, halving the block space usage needed for CoinSwap).

This increases complication of the implementation, but you potentially get an improvement in blockchain space for popular makers, with an asymptote of 50% reduction, so it is probably worth implementing.


Thus, if Alice wants to multipay, she could just sum up all the outgoing values, then specify the sum to Bob.
Then it can modify the second transaction to pay multiple destinations (since it has the private keys to remake that).
Of course, all the outgoing payments are now linked together.... but I suppose you can warn the user of Alice of such.

It would probably be best for both Alice and Bob to always change the destination address as well after private key turnover.


> > Okay, from what little I understand it seems that "even if sparse subset sum is easier than subset sum, it is still hard, so it probably will not matter in practice", would that be a fair takeaway?
>
> Not exactly. Here's another summary:
>
> Suppose Alice has V bitcoins and mixes them with multi-transaction
> CoinSwap, she receives transactions with amounts (w_0, w_1, w_2....)
> which add up to V.
>
> Privacy relying on the (sparse) subset sum problem works by making it
> computationally infeasible for an adversary to search the entire
> blockchain for sets of transactions (w_0, w_1, w_2....) which add up to
> V. I believe aiming for this kind of privacy isn't practical due to
> block space considerations and others.
>
> Privacy relying on false positives does not make any search
> computationally infeasible, it works by having a large number of other
> sets of transactions (w_0, w_1, w_2....) which add up to V just by
> chance. Then the transactions received by Alice's will have a big crowd
> to hide in. I believe this is practical because the numbers are
> proportional to the n-choose-k function which can still be very large.

Hmm.

So let us return to our example of Alice who owns a 1 BTC coin and a 1 BTC coin.
Now suppose we find, by false-positive-statistics, that 2 BTC subset sums are rare but, say, 1.5 BTC subset sums are significantly more common.
So what Alice should do, if it wants to send 1.2 BTC to Carol via a CoinSwap with maker Bob, would be to split one of her 1 BTC coins to a 0.5 BTC and 0.5 BTC coin.
Then it takes the remaining 1 BTC coin and one of the 0.5 BTC and offers them in a CoinSwap to maker Bob, specifying a payment amount of 1.2 BTC.

It seems to me, however, that this is not much different from just specifying a set of standardized swap amounts.

The initial standards can be derived from false-positive-statistics, but once SwapMarket starts to become popular, then the actual statistics of the chain becomes skewed towards those standard swap amounts.
This makes it even wiser to also use those standard swap amounts, because of the larger anonymity sets.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[Chris Belcher]

Hello ZmnSCPxj,

>>> This "as long as the inputs that should be separate are not co-spent" is precisely what mixdepths protect against, which is why I think some kind of mixdepth facility will still matter in CoinSwap.
>>> Still, you have convinced me that, for the purpose of multi-transaction CoinSwap where you do not merge any of your coins, it is immaterial if the sub-transactions come from the same mixdepth or not.
>>> And if you have to merge your coins (for instance, if you are a maker and your customer wants to get a UTXO that is larger than any you have on hand, you have to merge your coins), you just have to ensure they are in the same mixdepth.
>>> Of course, you could be proposing some other construct --- perhaps you have some relational entry which says "you cannot merge coin A and coin B" which allows you to merge A C D or B C E, but not A B?
>>> (I imagine this would make coin selection even harder, but I am not a mathematician and there may be some trivial solution to this.)
>>> Now --- if you have two coins that cannot be merged in the same onchain tx, what happens when you swap them in a multi-tx CoinSwap with somebody else?
>>> That somebody else does not know that information.
>>> Instead, that somebody else must always assume that any coins it got from the same CoinSwap operation must not be safely mergeable (though they can still be used in the same swap together).
>>> Coins received via receive addresses would also not be mergeable with any other coins, except coins to the same address (because coins in the same address already leak that they are owned by the same owner).
>>
>> Yes I guess you're right. This part about mixdepths requires further
>> thought.
>>
>> CoinSwap can be combined with some kind of CoinJoin (most likely
>> something similar to PayJoin or CoinJoinXT). That should help with the
>> reasoning about co-spending inputs and mixdepths, because other inputs
>> that are not owned by the taker will often be co-spent anyway.
>>
>> Regarding coins which mustn't be co-spent being coinswapped to somebody
>> else, ideally that coinswap maker will receive coins from unrelated
>> takers too, so will merge their coins along with those as well. Also the
>> fact that a coinswap happened means there are two transactions between
>> the taker's-inputs-which-mustnt-be-merged and them actually being merged.
> 
> One of those transactions (the second one) will be a 1-input 1-output tx (it moves the coin from bilateral control to unilateral control of Bob), which chain analysis already knows to be a self-transfer.
> The first transaction will also usually be a 1-input 1-output tx as well (it moves the coin from unilateral of Alice to bilateral control) if you did not do any splitting or merging before providing the coin into the swap (for example if this comes from the taker, and the taker knows all the coins it wants to swap cannot be safely merged together).
> 
> If chain analysis keeps the heuristic "1-input 1-output is a self-payment because srsly who has an exact amount for a payment Bitcoin is volatile lol", then the resulting coins still are not safe to merge, because chain analysis will "pass through" the swap operation and if the two coins are later merged then they still end up *correctly* concluding the original coins were owned by the same owner.
> 
> Using a PayJoin construction for the second tx would help, but if the receiving end does not have a spare UTXO it can merge with (e.g. all its liquidity got tied up in the swap) then there might not be an opportunity to PayJoin.
> 
> There is also little that can be done about the first transaction, in case it ends up being a 1-input 1-output.
> 
> Suppose Alice the taker has a 1 BTC output and a 1 BTC output *and no other coins*, both of which it cannot safely merge, and it has to pay 1.2 BTC to Carol.
> Alice then has to CoinSwap them to Bob the maker, requesting a 1.2 BTC output going to Carol and the rest in whatever loose change Bob has.
> Alice then has to use two 1-input 1-output txes for each of its 1 BTC outputs (because it cannot merge them together) to put them into bilateral control.
> Then Bob claims them from bilateral control with 1-input 1-output txes as well (it cannot merge them together, because that might break Alice privacy, and Bob might not have any other spare coins it can merge with the incoming funds).
> 
> Now, even if Bob PayJoins the second tx for both 1 BTC outputs, it still cannot merge the resulting joined coins together, because the "spent-together" analysis would still tie those coins as being owned by the same owner, it is simply that the surveillor will think the owner owns more coins than it actually does, but the two 1 BTC TXOs that Alice used to own are still analyzed as being owned by the same owner if they are ever merged.
> 
> What Alice could do, to "merge" its 1BTC coins together, would be to swap only one of the 1BTC coins first, for a single 1BTC coin as well.
> Then presumably the incoming 1BTC coin has no linkage with the coin Alice swapped out (Alice hopes), then Alice could spend that new 1BTC coin with the old one it could not merge with the coin it swapped out.
> (Actually Alice does not need to do that as it is the customer after all, but maybe Bob the maker has to do that sometimes, in case it finds there are too many cannot-spend-together constraints in its pool of UTXOs and it is getting harder to select coins --- but if so, who does Bob the maker swap *with*?
> If Bob can encounter that problem, then maybe other makers will also have that problem as well!)
> 
> (the above can be done by PayJoining with the unswapped coin on either the first or second transaction in the swap as well; the idea is more general.)

Chain analysis doesn't in fact know that 1-input-1-output transfers are
self-transfers, this is merely a heuristic that can be flawed. For
example I accept donations in bitcoin and a surprising number of them
are 1-input-1-output or multi-input-1-output, presumably the donators
did it for privacy reasons or cost reasons. Also I believe many people
use 1-input-1-output transactions for funding Lightning channels.

Although even so, your argument suggests that its better for at least
some of the time for Alice and Bob to create 2-output transactions and
mess with the change output detection heuristics to try to get chain
analyzers to assign the wrong output as change.

If the receiving end doesn't have a suitable UTXO for a PayJoin then
they won't get the CoinSwap deal. The liquidity market is a free market,
takers are the maker's customers and they have a wide choice. In such a
case the maker would have been outcompeted by other makers which do have
extra UTXOs.

Your discussion with Alice having two UTXOs she doesn't want to co-spend
is definitely interesting. Perhaps also another way to solve is for
Alice to spend her UTXOs in 2-output transactions and mess with the
change output detection heuristics, say CoinSwapping 0.5 BTC from one
coin and 0.7 BTC from the other, with the total 1.2 BTC going to Carol.


>>>>> Assuming Alice is the taker, and Bob is the maker, then Alice might want a specific coin value (or set of such) that Bob does not have.
>>>>> In that case, Bob will have to split a UTXO it owns.
>>>>> We could constrain it so that Bob at least is not allowed to use the change from splitting for the same CoinSwap, e.g. if Bob has only 9 BTC and 1 BTC coins and Alice wants a 6 BTC / 3 BTC / 1 BTC split, then Bob cannot split its own 9 BTC coin then swap.
>>>>> Or in terms of mixdepths, Bob can split within a mixdepth but each outgoing UTXO in the same swap should be from different mixdepths.
>>>>
>>>> A good way to do it could be for Alice to tell Bob that she wants 10 BTC
>>>> and let Bob figure out on his own how to get that amount, based on the
>>>> amounts he already has. If Alice is making a payment she can provide
>>>> that amount too, but all the other output amounts can be up to Bob.
>>>
>>> This leaks to Bob whether Alice is making a payment or not; it would be better for the privacy of Alice for Alice to always mention some "payment amount", even if this is not actually a payment and Alice is just mixing for herself prior to storing in cold storage.
>>> And if Alice wants to use a single swap to pay to multiple targets at once, that implies Alice has to have the ability to indicate the outputs it wants to Bob, and it would imply as well that Alice has to obfuscate which of those outputs have amounts that actually matter (by always insisting on what the output amounts must be, rather than insisting on N output amounts and letting Bob handle the rest).
>>> (We could constrain it such that Alice can make only one payment per CoinSwap, so that Alice only gives one "target" amount and one "total" amount, but that implies even bigger blockspace utilization, sigh.)
>>> Otherwise, Bob can get information:
>>>
>>> -   "Oh, Alice did not specify any of the outputs, just the total amount, all of my old coins are owned by Alice now."
>>> -   "Oh, Alice specified an exact value for one of the outputs, that one is no longer owned by Alice but the rest are owned by Alice."
>>> -   "Oh, Alice specified exact values for two of the outputs, those two are definitely no longer owned by Alice but the rest are owned by Alice."
>>>
>>> The conclusion here is either Alice never specifies any of the outputs --- in which case Alice cannot use a CoinSwap to pay directly to somebody else --- or Alice specifies all of them.
>>> Again, the maker might be an active surveillor, thus we should reduce information leaks to the maker as much as we can.
>>
>> Yep great point.
>>
>> A benefit of Alice not specifying any amounts is that Bob is able to
>> improve privacy and reduce costs by creating fewer change outputs. A
>> downside is that this leaks Alice's intentions (self-mix vs payment) to Bob.
>>
>> A solution could be to add randomness. Have Alice randomly specify
>> payment amounts with some probability even if she is only self-mixing.
>>
>> Although this doesn't solve everything, because Alice not specifying any
>> amounts implies self-mixing. But at least specifying some amounts
>> doesn't imply a payment.
> 
> I think that maybe it would be a better policy for Alice to always just give a specified payment amount at all times.
> Of course, a sufficiently motivated Bob could always just do statistical analysis on the payment amount (e.g. if it is not equivalent to some round number of United States Green Historical Commemoration Papers, it is unlikely to be a payment but instead a random amount that Alice had to provide on a self-payment).
> So .....
> 
> 
> Anyway, slightly unrelated, maybe we can simply have Alice specify a single payment amount always, as an unremovable part of the protocol.
> 
> I proposed "private key turnover" here: https://github.com/AdamISZ/CoinSwapCS/issues/53
> Basically, after exchanging the swap secret, it is now safe to give your share of bilateral control to your swap partner, so you can just turn over that private key to the swap partner.
> For clarity:
> 
> * Alice owns a 1 BTC coin it wants to swap with a 1 BTC coin from Bob.
> * Alice sends its 1 BTC coin to bilateral control (Alice temporary key and Bob temporary key).
>   * Backoffs and confirmations and etc etc are needed, we all know how to do CoinSwap safely, I elide those details here.
> * Bob sends its 1 BTC to bilateral control (Alice 2nd temporary key and Bob 2nd temporary key).
> * Alice and Bob complete the CoinSwap protocol and now both know the swap secret X, and have to claim the bilateral control before some future blockheight L.
> * Alice can send its Alice temporary key to Bob, so that Bob can change the second transaction as it likes.
>   * Bob can merge it with a coin it happens to have, without having to coordinate signing with Alice (i.e. it gets PayJoin on the second tx for free).
>   * If Bob the maker gets another swap request, it can spend directly from the bilateral control address to another bilateral control address with a different taker, reducing blockchain footprint.
>   * Bob can fee bump using RBF instead of CPFP.
> * Bob can also now send its Bob 2nd temporary key to Alice, for similar advantages for Alice.
> 
> It does require that both Alice and Bob respect the timeout --- the bilateral outputs have to be spent before the timeout, else the timelock branches come into play.
> But Alice and Bob, after private key turnover, need not *immediately* broadcast the claiming transactions --- they can wait a little time for opportunities to change the claiming transaction, for example if they get an incoming payment they could assume that the recently-concluded swap is safe to merge with the new incoming coin and they can CPFP the incoming payment on the mempool with their existing coin, or Bob the maker might get another customer and Bob can cut-through from one swap to the next, reducing 4 transactions for 2 swaps to just 3 transactions (and if it can continuously chain customers that way, in the long run Bob on average has 1 transaction per swap, halving the block space usage needed for CoinSwap).
> 
> This increases complication of the implementation, but you potentially get an improvement in blockchain space for popular makers, with an asymptote of 50% reduction, so it is probably worth implementing.
> 
> 
> Thus, if Alice wants to multipay, she could just sum up all the outgoing values, then specify the sum to Bob.
> Then it can modify the second transaction to pay multiple destinations (since it has the private keys to remake that).
> Of course, all the outgoing payments are now linked together.... but I suppose you can warn the user of Alice of such.
> 
> It would probably be best for both Alice and Bob to always change the destination address as well after private key turnover.

Of course if Alice specified an amount when she was actually
self-mixing, it would be easy for her to come up with a random value
that was close to some round number, either in BTC or another currency.

Private key turnover is a great idea. It could also help with the
earlier problem of 1-input-1-output transactions being markers, because
when the coins in 2-of-2 multisigs are spent they may end up being spent
in a wider variety of ways.


>>> Okay, from what little I understand it seems that "even if sparse subset sum is easier than subset sum, it is still hard, so it probably will not matter in practice", would that be a fair takeaway?
>>
>> Not exactly. Here's another summary:
>>
>> Suppose Alice has V bitcoins and mixes them with multi-transaction
>> CoinSwap, she receives transactions with amounts (w_0, w_1, w_2....)
>> which add up to V.
>>
>> Privacy relying on the (sparse) subset sum problem works by making it
>> computationally infeasible for an adversary to search the entire
>> blockchain for sets of transactions (w_0, w_1, w_2....) which add up to
>> V. I believe aiming for this kind of privacy isn't practical due to
>> block space considerations and others.
>>
>> Privacy relying on false positives does not make any search
>> computationally infeasible, it works by having a large number of other
>> sets of transactions (w_0, w_1, w_2....) which add up to V just by
>> chance. Then the transactions received by Alice's will have a big crowd
>> to hide in. I believe this is practical because the numbers are
>> proportional to the n-choose-k function which can still be very large.
> 
> Hmm.
> 
> So let us return to our example of Alice who owns a 1 BTC coin and a 1 BTC coin.
> Now suppose we find, by false-positive-statistics, that 2 BTC subset sums are rare but, say, 1.5 BTC subset sums are significantly more common.
> So what Alice should do, if it wants to send 1.2 BTC to Carol via a CoinSwap with maker Bob, would be to split one of her 1 BTC coins to a 0.5 BTC and 0.5 BTC coin.
> Then it takes the remaining 1 BTC coin and one of the 0.5 BTC and offers them in a CoinSwap to maker Bob, specifying a payment amount of 1.2 BTC.
> 
> It seems to me, however, that this is not much different from just specifying a set of standardized swap amounts.
> 
> The initial standards can be derived from false-positive-statistics, but once SwapMarket starts to become popular, then the actual statistics of the chain becomes skewed towards those standard swap amounts.
> This makes it even wiser to also use those standard swap amounts, because of the larger anonymity sets.

It's very unlikely for the 2 BTC subset sum to be uncommon but 1.5 BTC
to be common, because they are very close in value, and these functions
seem to end up being smooth and slowly-varying, at least in my brief
tests. It might be a concern when comparing 2 BTC to 20 BTC or 200 BTC.


Regards
CB

Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain protocol using schnorr signatures

[ZmnSCPxj]

Good morning CB,


> Chain analysis doesn't in fact know that 1-input-1-output transfers are
> self-transfers, this is merely a heuristic that can be flawed. For
> example I accept donations in bitcoin and a surprising number of them
> are 1-input-1-output or multi-input-1-output, presumably the donators
> did it for privacy reasons or cost reasons.

A heuristic need not be perfect to be effective, and I am quite sure that, outside of donation, most 1-output transfers will be self-transfers.

Indeed, the old cliche of donating tainted/stolen funds is most likely a cliche for a reason.
Perhaps you are a beneficiary of some movie hero who has stolen the money from a villain who acquired wealth by immoral means.

Unlike change heuristics, misleading the 1-output heuristic is difficult; whoever got control of the single output is either yourself, or somebody who swapped coins with you.


> Also I believe many people
> use 1-input-1-output transactions for funding Lightning channels.

Yes, Lightning helps privacy, that is correct.

However, do note that Lightning channels tend to be long-lived, meaning it will be a large number of blocks that such a TXO will be unspent.
Due to the timeout on CoinSwap, the fund needs to be claimed quickly, in much shorter time than a typical Lightning channel.
This can help narrow down payment heuristics.

>
> Although even so, your argument suggests that its better for at least
> some of the time for Alice and Bob to create 2-output transactions and
> mess with the change output detection heuristics to try to get chain
> analyzers to assign the wrong output as change.

Yes, I agree.

> If the receiving end doesn't have a suitable UTXO for a PayJoin then
> they won't get the CoinSwap deal. The liquidity market is a free market,
> takers are the maker's customers and they have a wide choice. In such a
> case the maker would have been outcompeted by other makers which do have
> extra UTXOs.

PayJoin might not buy you as much as you think.

So Alice has two coins it does not want to CoinJoin for unknown reasons:


    Salary as  ---> Alice
     teacher

    LiveJasmin ---> Alice
     payout

Alice swaps them to Bob, who PayJoins the incoming funds.
Since Bob has been operating for a long time, its coins have a varied and storied history.

    WannaCry  ----> Bob  ----+
                             |
                             |
    Salary as  ---> Alice ---+--> Bob
     teacher

    LiveJasmin ---> Alice ---+--> Bob
     payout                  |
                             |
    ex-JoinMarket -> Bob ----+
     maker

Alice does *not* want Bob to join those two Bob-owned coins, still, because chain analysis would not only implicate her in WannaCry, but also as a LiveJasmin model ***and*** (gasp!) a JoinMarket money launderer (I am being facetious here).

And since the swap has completed, Bob controls those coins.
If another taker comes along, offering a high fee for a big swap, and Bob *has to* merge those two coins (that ultimately got history from Alice) in order to cover what the taker is requesting (because the taker has to make a big single payout to some other party, so needs a single large UTXO, not two small ones), what do you think Bob will do?
In a free market where the takers have wide choice, do you think Bob will economically-rationally help protect the secret life of Alice when not doing so would let Bob earn more coins?

Now of course, it would seem very unlikely that Alice the teacher is the hacker behind WannaCry *and* a LiveJasmin model *and* a money launderer, so no problem, right?
It just makes surveillors looks like fools right?
Except that Bob could have skipped the PayJoin step and just merged those four coins in a single transaction later, and the conclusion of surveillors would still be the same, for much the same effect, at reduced blockspace (spend in a single transaction instead of 3).

So I think it is better if Bob actually avoids small merges of a two or three or four coins, and should do the occasional mass merge of large numbers of coins.
This leads to better misleading of surveillors, and is incentive compatible since it reduces blockspace usage for Bob to do the occasional mass merge rather than PayJoining at every swap.

> Your discussion with Alice having two UTXOs she doesn't want to co-spend
> is definitely interesting. Perhaps also another way to solve is for
> Alice to spend her UTXOs in 2-output transactions and mess with the
> change output detection heuristics, say CoinSwapping 0.5 BTC from one
> coin and 0.7 BTC from the other, with the total 1.2 BTC going to Carol.

That seems to be a good idea indeed, and significantly better than relying on PayJoin to obscure the history of coins.

Of course, doing change-output-heuristic-breaking means splitting up coins, increasing the number of UTXOs.
But that combines well with Bob the maker periodically merging many small coins.

> Of course if Alice specified an amount when she was actually
> self-mixing, it would be easy for her to come up with a random value
> that was close to some round number, either in BTC or another currency.

Yes, and I suggest this is always be done, as part of the protocol.


> Private key turnover is a great idea. It could also help with the
> earlier problem of 1-input-1-output transactions being markers, because
> when the coins in 2-of-2 multisigs are spent they may end up being spent
> in a wider variety of ways.

Indeed.
It gets a few features "for free", at the cost of greater complexity at the simple "I only want to swap once, then forget about the coins for a while" case.

* It gets PayJoin at the second transaction for free.
* It lets Bob the maker cut-through for a new taker.
* It reduces the cost on Bob to merge large numbers of coins at once.
* It lets Alice the taker cut-through for a new maker if she wants to do multi-round swaps (though note the objection "Value-based Directionality" in my writeup https://zmnscpxj.github.io/bitcoin/multiswap.html ; though counternote that if CoinSwaps are as hard to identify as my naive understanding of your math suggests, this should be a relatively minimal problem).

>
> > > > Okay, from what little I understand it seems that "even if sparse subset sum is easier than subset sum, it is still hard, so it probably will not matter in practice", would that be a fair takeaway?
> > >
> > > Not exactly. Here's another summary:
> > > Suppose Alice has V bitcoins and mixes them with multi-transaction
> > > CoinSwap, she receives transactions with amounts (w_0, w_1, w_2....)
> > > which add up to V.
> > > Privacy relying on the (sparse) subset sum problem works by making it
> > > computationally infeasible for an adversary to search the entire
> > > blockchain for sets of transactions (w_0, w_1, w_2....) which add up to
> > > V. I believe aiming for this kind of privacy isn't practical due to
> > > block space considerations and others.
> > > Privacy relying on false positives does not make any search
> > > computationally infeasible, it works by having a large number of other
> > > sets of transactions (w_0, w_1, w_2....) which add up to V just by
> > > chance. Then the transactions received by Alice's will have a big crowd
> > > to hide in. I believe this is practical because the numbers are
> > > proportional to the n-choose-k function which can still be very large.
> >
> > Hmm.
> > So let us return to our example of Alice who owns a 1 BTC coin and a 1 BTC coin.
> > Now suppose we find, by false-positive-statistics, that 2 BTC subset sums are rare but, say, 1.5 BTC subset sums are significantly more common.
> > So what Alice should do, if it wants to send 1.2 BTC to Carol via a CoinSwap with maker Bob, would be to split one of her 1 BTC coins to a 0.5 BTC and 0.5 BTC coin.
> > Then it takes the remaining 1 BTC coin and one of the 0.5 BTC and offers them in a CoinSwap to maker Bob, specifying a payment amount of 1.2 BTC.
> > It seems to me, however, that this is not much different from just specifying a set of standardized swap amounts.
> > The initial standards can be derived from false-positive-statistics, but once SwapMarket starts to become popular, then the actual statistics of the chain becomes skewed towards those standard swap amounts.
> > This makes it even wiser to also use those standard swap amounts, because of the larger anonymity sets.
>
> It's very unlikely for the 2 BTC subset sum to be uncommon but 1.5 BTC
> to be common, because they are very close in value, and these functions
> seem to end up being smooth and slowly-varying, at least in my brief
> tests. It might be a concern when comparing 2 BTC to 20 BTC or 200 BTC.

If it is as smooth and naturally-occurring as you suggest, then it seems to me as well that the distribution of CoinSwap values will be just as smooth and naturally-occurring, so my naive understanding is still "even if sparse subset sum is easier than subset sum, it is still hard, so it probably will not matter in practice".

People will mix due to receiving some amount.
That amount will be sampled from some naturally-occurring distribution.
Thus, CoinSwap values will be sampled from the same naturally-occurring distribution.

People will mix due to having to send some amount they do not want to be tracked to them.
That amount will be sampled from some naturally-occurring distribution.
Thus, CoinSwap values will be sampled from the same naturally-occurring distribution.

....I think?  Maybe?

Regards,
ZmnSCPxj