Anonymity in the Bitcoin: Splitting Transactions

[edufgf]

Hi all,

I would like to know the opinion of the community on this idea that I have.
Also I'd like to know if this was ever implemented before, but as far as I have researched I couldn't find any evidence of it.

Background
We know that Bitcoin is not an anonymous system but rather it is a pseudonymous environment.

Take for example, 4chan where users can make posts but there are no usernames or any sort of way of linking between different author's post. (anonymous)
Reddit, on the other hand, there are usernames and actions/posts can be linked because of that. (pseudonymous)

In Bitcoin anyone can have multiple public addresses ('usernames') and because transactions are public we can track everyone's actions.
In a transaction you are either paying or being paid, and that's how we can link different addresses to same entities.

Let's then consider both cases:

1) Receiving payment
Let's consider the case where you are being paid, and you don't want those payments to be linked to you.
An easy solution for this would be, for every new payment, make a new address, receive payment, done. No linking and you got the payment.

2) Issuing a payment
Unfortunately, this is a more complex situation.
Here the linking can happen in a transaction that will generate a payment change output address;
or when you use multiple input addresses to sum up for the amount you need to pay. The input addresses are linked.

We can break it down to 3 cases, depending on how much you need to spent and how much you own for some address.

Let's say you want to pay X bitcoins.

2.1) You have an address with exactly X bitcoins
Easy? Make a single transaction with input = output, however I see that maybe we need to account for transaction fees.
I don't know what is the likelihood of this situation, where you own X + Y bitcoins, where Y is the fee amount for the transaction, resulting in a 'no change' transaction.
This would be the case where no change is needed.
If you don't want this transaction to be linked to your original address, you could them use one of the mixing services before you make the transaction and 'break' the link.

2.2) You have an address with more than X bitcoins
In this case, the naive transaction will result in a change address. The problem is that now this change address will carry the history of this payment.
Also, if your original address was already identified somehow, then the change address will probably be linked to it.
The solution I see, is to breakdown your bitcoins by creating new addresses and distributing among them.
If possible, create one address with X bitcoins, then we are in case 2.1).
Again use some mixing service to 'break' the link with the original address and do the payment with no changes.

However I see it must be really hard to get addresses with the exact amount we want, and some mixing services ask for chunking the bitcoins in some amount they set.
And then we end up on case 2.3)

2.3) You have multiple addresses with less than X bitcoins.
This is where I am concerned on what people currently do.
I believe that users will just make transactions using multiple input addresses and make the payment, possibly with a change output.

If all those multiple addresses you own are originated from a mixing service, then maybe you don't really care that now you are linking again some addresses.
But maybe this linking can be detected and de-anonymized by an attacker because of the value of the transaction or because of the time it happened.
And you will probably end up with a change address that now is linked to all the input used.

But let's say you are WikiLeaks or another entity that gets payments(donations) on new addresses everytime.
If you use a multiple input transaction to make up for the amount you need to pay, you have just created the linking point for an attacker, and he can maybe detect who you are (by side channels) and infer the donors.


My proposal here is to increase the anonymity for users by avoiding the creation of multiple input transactions.

The idea is to breakdown the transaction value X into N smaller transactions with values that match up the buyer's bitcoin amounts.
This could be set with an agreement (maybe smart contract) between the buyer and the seller.
This way we can always try to get N-1 transactions of type (2.1) with no changes and only one with a change.
The advantage here is that there would be no link between those N transactions.

There are some details to analyze:
1) Fees, how many transactions is the user willing to create in order to have this better guarantee of unlinkability, taking into account the fees by transaction.
1.1) Maybe we don't mind linking some addresses, maybe some addresses are more sensitive. So we can split the transaction in various ways.
2) How effective this technique would be in practice, against current de-anonymizing techniques/algorithms.

To summarize I believe that this proposal, together with mixing services, could enhance the system privacy.

Please let me know your thoughts on this. 

[1714489229]

1714489229

[achow101]

This isn't that hard to do, just enable an advanced user mode and choose which inputs you want to spend. This is easily done in Bitcoin Core and Armory.

There are a few problems here, though not major ones. You are operating under the assumption that change outputs are easily spotted, however that is not the case. If the change is sent to a new address, then that change cannot be easily tracked or identified as change. It can be rather difficult to identify the change outputs especially if both outputs are either outputs with weird uneven values (e.g. 0.3595412) or both are even values (e.g. 0.25). Furthermore, with newly generated change address and newly generated payment addresses, an observer cannot be certain which output is your change and which is someone you are paying.

Additionally, if you have enough inputs, you can create identical outputs which would make it near impossible for an observer to distinguish which output is for whom. That is also achievable by using even output values or uneven output values for all of the outputs.

Another solution which is perhaps better but slightly harder to do is a CoinJoin transaction; it requires coordinating between multiple parties. CoinJoins combine inputs from various people, so you could have a bunch of your own inputs there and no one would know that those were your inputs, for all they know it could be some other person who participated in that CoinJoin. Then the outputs are all the same amount so it is difficult to distinguish which output is for which person.

[edufgf]

This isn't that hard to do, just enable an advanced user mode and choose which inputs you want to spend. This is easily done in Bitcoin Core and Armory.

Yeah, maybe not hard, but the 'trick' is to arrange with the seller how the transaction is going to be (with multiple transactions with sum of output summing up to original price).

There are a few problems here, though not major ones. You are operating under the assumption that change outputs are easily spotted, however that is not the case. If the change is sent to a new address, then that change cannot be easily tracked or identified as change. It can be rather difficult to identify the change outputs especially if both outputs are either outputs with weird uneven values (e.g. 0.3595412) or both are even values (e.g. 0.25). Furthermore, with newly generated change address and newly generated payment addresses, an observer cannot be certain which output is your change and which is someone you are paying.

I agree with you, but some scientific support here would be good. This would indicate that using transactions with change addresses is not really a problem.
But I was thinking in the cases where the change address can be easily spotted like say, you buy something from Walmart (and Walmart uses some known address).
That is, it would be nice to know how much of the transactions are like this (easily spotted vs. not so easy).

Additionally, if you have enough inputs, you can create identical outputs which would make it near impossible for an observer to distinguish which output is for whom. That is also achievable by using even output values or uneven output values for all of the outputs.

I think I get you, but it still links all the input addresses. I was working under the assumption that all the input addresses will be linked somehow, and I think this is how naive deanonymizing algorithms work (I was told that BitIodine does that).

Another solution which is perhaps better but slightly harder to do is a CoinJoin transaction; it requires coordinating between multiple parties. CoinJoins combine inputs from various people, so you could have a bunch of your own inputs there and no one would know that those were your inputs, for all they know it could be some other person who participated in that CoinJoin. Then the outputs are all the same amount so it is difficult to distinguish which output is for which person.

Yes sure. This was another thing I thought before, but I was told that mostly transactions on the network with multiple input addresses aren't CoinJoin operations (and from this I was assuming to always link input addresses).

We can also view it this way, instead of trying to use the CoinJoin (which has it's disadvantages) the splitting of the transaction could take place instead.
CoinJoin would mix some entities (and maybe make some algorithms think it its only one entity), while the splitting technique avoids the linking at all.

I will look for some study on this, but I might agree that the case of newly generated change addresses might not be a problem.
However we still have the multi input transaction, where you suggest CoinJoin (which works at some extent) but this here might be another solution.

My goal here is to get more thoughts on the topic and then decide if this is a promising thing or not.
Thanks.

[danda]

It sounds useful to me as a power user feature.   The change address linking has always bothered me.

It is less powerful than complete coin control, but adds a useful level of convenience/automation.

Also, it seems pretty simple to implement for the command-line.   Eg, the sendtoaddress API could be modified (or wrappered by an external script).

afaik, there is no tool available for using coin control (selecting inputs) on the command-line.

More thoughts:

* If there are N transactions it may be useful to have m change addresses, where m is random.  Just to add variance.

* Ideally the change amounts would resemble the non-change amounts.  ie similar both in quantity and number of digits. 

* this is orthogonal but the software could also have a mode that attempts to send without any change address.  eg, it could prompt the user that the best match from available inputs is 1.234 BTC when the payment amount is 1.1 BTC.   Send without change: Yes/No?      A limit could be supplied so it would auto choose Yes if the difference is under the limit.

[shorena]

-snip-
Yes sure. This was another thing I thought before, but I was told that mostly transactions on the network with multiple input addresses aren't CoinJoin operations (and from this I was assuming to always link input addresses).

This is a common misconception. Even here on bitcointalk accounts are linked by spend linked addresses, which could be CoinJoin TX. I would argue that a human could probably identify a CoinJoin (just by the larger number of inputs and outputs), but not reliably. I remember there was a paper about CoinJoin and they just assumed that  5 or more inputs are CoinJoin, because they couldnt be sure and couldnt check all TX by hand either.

We can also view it this way, instead of trying to use the CoinJoin (which has it's disadvantages) the splitting of the transaction could take place instead.
CoinJoin would mix some entities (and maybe make some algorithms think it its only one entity), while the splitting technique avoids the linking at all.

But isnt that the point of anonymity? To blend in with the masses in a way that makes your payments intertwined with everyone elses. That way its impossible to find a single person, not because there are no links, but because there are links from (almost) everyone to (almost) everyone.

A CoinJoin implementation in more wallets than just bc.i would be a great step and AFAIK Samourai wallet and/or Mycelium devs are working on that. Mycelium will implement the code once its finished.

I think it would go be good to remove the "only criminals need anonymity" stigma though, as it seems many attempts to get this rolling failed because they required high skill and(!) high user participation to work[1].

[1] e.g. https://bitcointalk.org/index.php?topic=432121.0

[edufgf]

But isnt that the point of anonymity? To blend in with the masses in a way that makes your payments intertwined with everyone elses. That way its impossible to find a single person, not because there are no links, but because there are links from (almost) everyone to (almost) everyone.

Yes, blending is an option, but if you don't need to blend, that would be even better.
CoinJoin you need to trust and find some peers. Using this transaction split, you only need to trust the peer you are dealing with.

This arise some questions, like how feasible and reliable are today's CoinJoin transactions.

[belcher]

CoinJoin is implemented today in the JoinMarket project. It has created an average of 14-15 coinjoin transactions per day in the last 9 months.

https://bitcointalk.org/index.php?topic=919116.msg10096563

It's not clear that coinjoin is the best way with what you're writing about here. Have you read this blog post about the topic? https://medium.com/@octskyward/merge-avoidance-7f95a386692f (However ignore what's written about CoinJoin here, much of it is now inaccurate)

[HeroCat]

Blockchain offer anonymity in BTC transfers, just tick your BTC receiving address as not public address and that's all 

[edufgf]

CoinJoin is implemented today in the JoinMarket project. It has created an average of 14-15 coinjoin transactions per day in the last 9 months.

https://bitcointalk.org/index.php?topic=919116.msg10096563

It's not clear that coinjoin is the best way with what you're writing about here. Have you read this blog post about the topic? https://medium.com/@octskyward/merge-avoidance-7f95a386692f (However ignore what's written about CoinJoin here, much of it is now inaccurate)

Thank you!

This is pretty much what I was thinking! He calls Merge Avoidance and I called it Splitting Transactions.
Doing a quick search, i think that this was ignored or postponed by the community... I might look up on this and do some research on the effectiveness of this technique.

[spartacusrex]

I like.

I was wondering, will this explode the size of the UTXO set ?

As in, will there be more outputs than inputs generated per txn ? Since normally you spend multiple inputs for just 1 output (+ change)

Now you would be using multiple inputs to fulfil the requests, but there are multiple outputs too..

 

[Sophia Lockhart]

Hi there,

Are you are aware that NAV coin is has a fully anonymous transaction system and a fully anonymous chat system. Check it out http://www.navajocoin.org/ They are a great coin to invest in at the moment as well as they are in process of decentralising their anonymous system. Happy trading

[Hyena]

I think the best way to stay anonymous is to sell your bitcoins for whatever altcoin, then transfer those altcoins to another exchange and buy back your bitcoins. if the exchange is on Tor there is a good chance that the LEs will never get the data that could lead to your identity.

[danda]

I took a quick look at the NAV Coin website.   The following text is enough to give me major doubts.

NAV Coin is the worlds first fully anonymous cryptocurrency. NAV Coin offers optional anonymous transactions that are sent through our double encrypted network of servers which all run on decentralized block chain technology.

fully anonymous... ok cool!     except:   optional anonymous transactions.  fail.

imho the the only coin that may ever be able take the mantle away from bitcoin is one that makes all transactions anon by default so that the funds are fully fungible.   If anon tx are an optional step then many/most will not use them and thus any anon tx automatically look suspicious and are also easier to de-anon using various techniques because they are only mixed in with a small subset of total tx.

I did not even get as far as trying to figure out HOW the anon tech works.  The above text alone is enough to sour me on the concept.  I don't mean to be a downer, just calling it like I see it.

Hi there,

Are you are aware that NAV coin is has a fully anonymous transaction system and a fully anonymous chat system. Check it out http://www.navajocoin.org/ They are a great coin to invest in at the moment as well as they are in process of decentralising their anonymous system. Happy trading

[PHP.guru]

but first of all bitcoin wasnt built to be anonymous, its rather the opposite .

[Hyena]

I took a quick look at the NAV Coin website.   The following text is enough to give me major doubts.

NAV Coin is the worlds first fully anonymous cryptocurrency. NAV Coin offers optional anonymous transactions that are sent through our double encrypted network of servers which all run on decentralized block chain technology.

fully anonymous... ok cool!     except:   optional anonymous transactions.  fail.

imho the the only coin that may ever be able take the mantle away from bitcoin is one that makes all transactions anon by default so that the funds are fully fungible.   If anon tx are an optional step then many/most will not use them and thus any anon tx automatically look suspicious and are also easier to de-anon using various techniques because they are only mixed in with a small subset of total tx.

I did not even get as far as trying to figure out HOW the anon tech works.  The above text alone is enough to sour me on the concept.  I don't mean to be a downer, just calling it like I see it.

Hi there,

Are you are aware that NAV coin is has a fully anonymous transaction system and a fully anonymous chat system. Check it out http://www.navajocoin.org/ They are a great coin to invest in at the moment as well as they are in process of decentralising their anonymous system. Happy trading

Yes the anonymity part of cryptocurrencies also bothers me a lot. All those altcoins that claim to provide anonymity are scams because none of them has actually implemented true anonymity. There are many very smart cryptography experts involved in cryptocurrencies so the fact that none of them has come up with a truly anonymous coins tells us that it is probably impossible the way we would imagine it to work.

Therefore, I propose that a truly anonymous coin has to make a compromise and somehow be less effective than bitcoin and it's derivatives while beating them at anonymity. Look at the image compression problem, for example. We have to choose between lossless and lossy algorithms such as PNG and JPG. While PNG is lossless, files compressed with PNG are pretty much always larger than files compressed with JPG. So which one to use? As always, it depends.

So, here's my message to all those hard-core cryptography experts trying to figure out how to make a truly anonymous cryptocurrency: be willing to make a sacrifice. Perhaps a truly anonymous coin is not able to send the exact amount of coins to the receiver but instead +- 10% of the amount defined by the sender, depending on some unpredictable factors?

[edufgf]

I like.

I was wondering, will this explode the size of the UTXO set ?

As in, will there be more outputs than inputs generated per txn ? Since normally you spend multiple inputs for just 1 output (+ change)

Now you would be using multiple inputs to fulfil the requests, but there are multiple outputs too..

That is a good point! And I believe it is true, the number of UTXO would increase indeed. But I don't know by which factor (x100? x1000?) and how bad it would be, what is the size of an UTXO? If small, maybe not a problem to have 1000x more UTXOs.

I think the best way to stay anonymous is to sell your bitcoins for whatever altcoin, then transfer those altcoins to another exchange and buy back your bitcoins. if the exchange is on Tor there is a good chance that the LEs will never get the data that could lead to your identity.

Yeah, and then end up paying 50% of your bitcoins as transfer fees
Aside from that, you still have the hurdle of doing all of this transfer by yourself. (Okay, here one integrated solution would help).

but first of all bitcoin wasnt built to be anonymous, its rather the opposite .

I think it is more about privacy. Just imagine if all the bank transactions were public and not anonymous, which means, anyone could know exactly how much you have in your account and your payment history.
That is not something we want to share.
In today's Bitcoin it is not so easy to do that, but also not impossible. And this technique would only make it more difficult to get to that, and so improving privacy.

I took a quick look at the NAV Coin website.   The following text is enough to give me major doubts.

NAV Coin is the worlds first fully anonymous cryptocurrency. NAV Coin offers optional anonymous transactions that are sent through our double encrypted network of servers which all run on decentralized block chain technology.

fully anonymous... ok cool!     except:   optional anonymous transactions.  fail.

imho the the only coin that may ever be able take the mantle away from bitcoin is one that makes all transactions anon by default so that the funds are fully fungible.   If anon tx are an optional step then many/most will not use them and thus any anon tx automatically look suspicious and are also easier to de-anon using various techniques because they are only mixed in with a small subset of total tx.

I did not even get as far as trying to figure out HOW the anon tech works.  The above text alone is enough to sour me on the concept.  I don't mean to be a downer, just calling it like I see it.

Hi there,

Are you are aware that NAV coin is has a fully anonymous transaction system and a fully anonymous chat system. Check it out http://www.navajocoin.org/ They are a great coin to invest in at the moment as well as they are in process of decentralising their anonymous system. Happy trading

Yes the anonymity part of cryptocurrencies also bothers me a lot. All those altcoins that claim to provide anonymity are scams because none of them has actually implemented true anonymity. There are many very smart cryptography experts involved in cryptocurrencies so the fact that none of them has come up with a truly anonymous coins tells us that it is probably impossible the way we would imagine it to work.

Therefore, I propose that a truly anonymous coin has to make a compromise and somehow be less effective than bitcoin and it's derivatives while beating them at anonymity. Look at the image compression problem, for example. We have to choose between lossless and lossy algorithms such as PNG and JPG. While PNG is lossless, files compressed with PNG are pretty much always larger than files compressed with JPG. So which one to use? As always, it depends.

So, here's my message to all those hard-core cryptography experts trying to figure out how to make a truly anonymous cryptocurrency: be willing to make a sacrifice. Perhaps a truly anonymous coin is not able to send the exact amount of coins to the receiver but instead +- 10% of the amount defined by the sender, depending on some unpredictable factors?

In lot of scenarios we face with the tradeoff invariant, but I believe this might not be the case.

There is already a project being developed to implement a system which makes everything anonymous. The key concept behind it is zero-proof (https://en.wikipedia.org/wiki/Zero-knowledge_proof).
The wiki page has a really cool example to understand it.

Zcash is one currency that is implementing it (https://z.cash/). 
I think they were the same guys under the name of Zerocoin, and both use the Zerocash protocol.

Maybe there are other altcoins doing the same, but I think that Zcash is the main one, where the researcher who proposed the Zerochash protocol is working on it.

For now it is under development. So until there we can keep implementing those 'hacks' to enhance current privacy.

Thanks for all the input!

[Hyena]

There is already a project being developed to implement a system which makes everything anonymous. The key concept behind it is zero-proof (https://en.wikipedia.org/wiki/Zero-knowledge_proof).
The wiki page has a really cool example to understand it.

However, digital cryptography generally "flips coins" by relying on a pseudo-random number generator, which is akin to a coin with a fixed pattern of heads and tails known only to the coin's owner. If Victor's coin behaved this way, then again it would be possible for Victor and Peggy to have faked the "experiment".

Isn't the above paragraph from the wiki undermined by the fact that block hash itself provides us a source of random numbers? For example, Peggy and Victor could agree to decide their action based on the block hash of some future block that has not been mined yet. Neither Peggy nor Victor could fake the outcome of a dice roll based on a block hash.

edit:
to those who are interested in the essence of the zero proof knowledge but find that the wiki page sucks at explaining it, here's a good find:

http://mathoverflow.net/questions/22624/example-of-a-good-zero-knowledge-proof

The classic example, given in all complexity classes I've ever taken, is the following: Imagine your friend is color-blind. You have two billiard balls; one is red, one is green, but they are otherwise identical. To your friend they seem completely identical, and he is skeptical that they are actually distinguishable. You want to prove to him (I say "him" as most color-blind people are male) that they are in fact differently-colored. On the other hand, you do not want him to learn which is red and which is green.

Here is the proof system. You give the two balls to your friend so that he is holding one in each hand. You can see the balls at this point, but you don't tell him which is which. Your friend then puts both hands behind his back. Next, he either switches the balls between his hands, or leaves them be, with probability 1/2 each. Finally, he brings them out from behind his back. You now have to "guess" whether or not he switched the balls.

By looking at their colors, you can of course say with certainty whether or not he switched them. On the other hand, if they were the same color and hence indistinguishable, there is no way you could guess correctly with probability higher than 1/2.

If you and your friend repeat this "proof" $t$ times (for large $t$), your friend should become convinced that the balls are indeed differently colored; otherwise, the probability that you would have succeeded at identifying all the switch/non-switches is at most $2^{-t}$. Furthermore, the proof is "zero-knowledge" because your friend never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.

[Kprawn]

There are many people in our meetups, who wants to sacrifice anonymity for more acceptance from governments and banks. They feel the pseudo-anonymity is hurting our

cause, and should only apply to secure a small degree of financial privacy. I strongly disagree with this train of thought, but I am willing to swap hats to view this from both

sides. We have seen Alt coins like Ripple going this route and they might just get the edge by doing this. If we had 100% anonymity built into the Bitcoin protocol, we would

have attracted a lot more bad characters. { We are already being labelled as Pedo's and drug smugglers and this will just add fuel to the fire }      

[Hyena]

There are many people in our meetups, who wants to sacrifice anonymity for more acceptance from governments and banks. They feel the pseudo-anonymity is hurting our

cause, and should only apply to secure a small degree of financial privacy. I strongly disagree with this train of thought, but I am willing to swap hats to view this from both

sides. We have seen Alt coins like Ripple going this route and they might just get the edge by doing this. If we had 100% anonymity built into the Bitcoin protocol, we would

have attracted a lot more bad characters. { We are already being labelled as Pedo's and drug smugglers and this will just add fuel to the fire }      

Actually money laundering should not be a crime. The only real crime here is government taxation. If there wasn't for taxes no one would care who was the previous owner of the coins you get. It might be easier to strip governments of their powers than to regulate and even ban cryptocurrencies. One should not stop paying taxes because of their own greed but to stop governments from funding wars. If you pay taxes you are more of a criminal than the person who doesn't.

[btccashacc]

I think the best way to stay anonymous is to sell your bitcoins for whatever altcoin, then transfer those altcoins to another exchange and buy back your bitcoins. if the exchange is on Tor there is a good chance that the LEs will never get the data that could lead to your identity.

i ever try this method, and it's pretty cool really work, ok the explanation like this
i have some bitcoin then i bought dogecoin on other exchanger like bittrex,poloniex or yobit then i transfer to another wallet and then deposite to my local exchanger then sell it for bitcoin, tadaaaa they can't trace me
dogecoin has a low tx fee btw