Bitcoin Forum
December 09, 2016, 02:07:44 AM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: on making Bitcoin more anonymous -- thoughts?  (Read 1121 times)
andrewbadr
Full Member
***
Offline Offline

Activity: 162

MadPay.com — lowest rake of any dice game


View Profile WWW
September 12, 2011, 05:47:38 PM
 #1

Bitcoins are not anonymous, but they can be made more so. All existing "laundries" are ineffective. These are my thoughts on why, and how an ideal anonymity-strengthening relay (ASR) might work. I'd been waiting to post this until I reached more definitive conclusions, but Kaminsky's announcement of BlitCoin (http://bitcoin.stackexchange.com/questions/771/what-is-blitcoin) made me think it was better to get a discussion started earlier. A more secure Bitcoin is a more useful Bitcoin. There are just a couple ideas here, mostly obvious, taken to their logical conclusion.

The existing so-called "laundry" services work as follows: Coins are sent in, possibly from multiple origin addresses. The laundry mixes them around with other addresses, ideally shared between multiple ongoing launderings, and then send them to the destination address (provided out-of-band) in one or more transactions.

No matter how cleverly a laundry mixes up the coins, though, X coins go in one end and X coins come out the other. This might be obfuscated by using more transactions, using more intermediate addresses, or spreading them out over time. but ultimately a sufficiently motivated adversary can calculate X and identify the corresponding input and output transactions. To the right algorithm, current laundry attempts are nothing more than an inconvenience. Making the intermediate transactions more wild may even be counterproductive, leaving an identifiable pattern in the block chain. Rather than security by obscurity, our ideal ASR would rely on a simple yet rigorous design. Here are three changes that I believe would get us to such a solution:

1. Multiple outputs in the same amount. Consider two people sending transactions through the ASR, in amounts X and Y such that X > Y. If the ASR forwards to output addresses A, B, and C Bitcoins in the amounts of Y, Y, X-Y, then the addresses A and B and have, to an extent, been anonymized. With existing laundries, there would only be two outputs, which ultimately have balances X and Y, making the transactions traceable. This type of operation can (and should) obviously be generalized to more simultaneous inputs and more output addresses per input. Notice the two things our ASR needs: support for multiple output addresses (ideally, unlimited), and volume. Attaining volume means low or nonexistent fees, and usage for a variety of transactions, maybe even those that don't need security (more on this later).

2. Outputs of as few amounts as possible. Anonymity is not binary, but a spectrum: the coins from the example above are "2-anonymized", meaning that there are two possible origins they could have come from. The more outputs in the same amount, the better. Therefore, the fewer size-buckets we can put our outputs into, the better. It would be nice to have some defined set of buckets that is small, but can conveniently accommodate the full range of Bitcoin amounts (1 Satoshi to 21M Bitcoin). There's a tradeoff here: we want fewer buckets (for security), but more buckets would allow us to use fewer output addresses per transaction. An exponentially distributed set of buckets (…0.1, 1, 100, 1000…) is an obvious solution. Using base-10 is a good choice because it's secure, easy to understand, and matches the protocol, but base-2 is also reasonable and would require fewer output addresses.

3. Different levels of anonymity. Different ASR use-cases need different levels of anonymity. Many transactions don't need any at all. By using the ASR anyway, low-security transactions can provide liquidity for high-sec transactions. So ideally, every Bitcoin transaction should be sent through one or more ASRs. Our ideal ASR should let you choose, along with your destination addresses, a desired security level and possibly a time limit. For example,  low-security transaction might require the ASR to make it 1-anonymized (i.e. not at all), but offer to let the coins wait for up to an hour before being output, in case they are useful in providing anonymization liquidity to another transaction. A high-security transaction might ask that as many coins as possible be 5-anonymized, with the remainder going to a designated "overflow" address (possibly for later retry) if they can't be secured within the given time.

The ASR should of course have an API allowing users to creating input/output bindings with all the above mentioned parameters, in addition to a time limit for how long the created binding should be retained in memory (for security). Integrating this API into everyday Bitcoin services would improve the security for everyone.

I've avoided the subject of transaction fees and funding the ASR, but these can be addressed pretty trivially. I've also avoided talking about how outputs would be timed, but a batch approach seems safe, while a "randomized stream" approach seems tricky to make truly secure.

There are a number of obstacles to the creation of such an ASR.  Trust in the ASR is perhaps the biggest. The ASR would have to be trusted to not steal coins; this could come with time. It would have to be trusted to be secure, and securely erase input-output associations, or else there would be no gain at all in anonymity; this could be addressed by using multiple chains ASRs for a transaction.

Increased transaction times would be one inconvenience. Client support is another, and would probably be critical to get people using long lists of output addresses. (You could enter the amount to get a string combining multiple receipt addresses, and the sending side could support the same packing format.) 

The ASR would have to maintain transaction volume in order to provide transaction security. This is something of a chicken-and-egg problem. One way to address might be to start by only supporting outputs of one size (e.g. 10 BTC) and expanding from there.

Finally, users have to be careful not to de-anonymize their Bitcoins. If the same coins get sent through too rapidly, it's probably just noise, and transactions nearby in time are less secure. Or, the user from the example in (1) could combine their coins from outputs B and C.

For the future, improvements to anonymity could even be incorporated into the next iteration of Bitcoin protocol. Though this would require more thought, something like: only allow addresses in some small set of sizes (e.g., powers of 2), and don't allow multiple inputs to an address, except to combine two smaller values. The obvious downside is that many destination addresses would have to be provided for common amounts. As above, client support on both ends would greatly mitigate this inconvenience.

madpay.com · btckink.com
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481249264
Hero Member
*
Offline Offline

Posts: 1481249264

View Profile Personal Message (Offline)

Ignore
1481249264
Reply with quote  #2

1481249264
Report to moderator
1481249264
Hero Member
*
Offline Offline

Posts: 1481249264

View Profile Personal Message (Offline)

Ignore
1481249264
Reply with quote  #2

1481249264
Report to moderator
1481249264
Hero Member
*
Offline Offline

Posts: 1481249264

View Profile Personal Message (Offline)

Ignore
1481249264
Reply with quote  #2

1481249264
Report to moderator
BTCGameMaker
Newbie
*
Offline Offline

Activity: 24


View Profile
September 13, 2011, 05:37:44 AM
 #2

This post doesn't seem to be getting a lot of attention, which is interesting considering anonymity is one of the best features of Bitcoin.  Part of the problem might be that you're explanations seem kind of technical and are hard to follow.  That being said, I've been thinking along the same lines as this for a while.  This is the working theory that I've come up with.

1. You have user clients and an ASR as you said.
2. All transactions between the clients and the ASR will be for 5 BTC.
3. If a user wants to send 6 BTC to a third party.  They will send 5 BTC to two separate addresses controlled by the ASR.  From any other addresses the ASR will send a total of 6 BTC to the third party.  The ASR will then log the balance of 4 BTC under a unique address.
4. If a user wants to receive 6 BTC from a third party the ASR generates a unique address for the user.  After receiving the 6 BTC, the ASR sends 5 BTC to the user and records the balance of 1 BTC under a unique address.
5. The user can as necessary draw from the balance to cover transactions less than 5 BTC or withdraw 5 BTC at a time if the balance exceeds this amount.  In this way the ASR will have control over a maximum of less than 5 BTC for any given user.

With enough traffic this should significantly conceal the connections of any transactions entering or leaving the ASR.

Other safety measures I've considered.

1. Have the ASR broken into programs split across multiple servers, so that hacking one server will not allow for control of the entire system.
2. Require that all transactions be confirmed by multiple servers independently.
3. Have all database entries double encrypted with one key being held on the server and one key being held by the user client.  In this way no database entries would be readable without the client that created them.
4. Have all programs making of the ASR sufficiently obfuscated and rewritten on a regular basis.  In this manner, even if someone hacked the server and gained access to the software, by the time they deciphered the software new software would be in place.

I've been playing around with how to implement this already, but it's kind of a big undertaking.  The user client would have to control all the tracking of funds behind the scenes so that it is easy for the user and the least amount of information possible is available to the ASR.  Then you would also need to create the ASR broken into multiple parts, and create an obfuscation program that could randomly replace variables and insert code to properly disguise the functioning of the program.

I agree with you that this is an issue that needs to be addressed and that current systems don't work.  But based on the attention this thread has gotten so far, I'm not sure the community actually takes this that seriously.

Robit Coin Raiser New Bitcoin Game Coming Soon.
Read more at https://bitcointalk.org/index.php?topic=122656.0
Play the Demo at http://www.socialrosity.com/robit_demo/index.php
d'aniel
Sr. Member
****
Offline Offline

Activity: 461


View Profile
September 13, 2011, 11:08:14 AM
 #3

Here's a post I made a little while ago along these lines:

Very low trust bitcoin mixes

A group of mix operators can get together, announce that they're running a mixing pool that closes at some future block.  They would select an untraceable, unlinkable digital cash server, operating as a Tor hidden service, that would create a single bitcoin address that pool participants would send their bitcoins to in a cryptographic exchange for an equivalent amount of digital cash.  The participants would do this via bitcoin transaction scripts that also ensure that

1) future transactions from the address require unanimous consent from the mix operators (using CHECKMULTISIG)
2) if unanimous consent to distribute them is not reached within some timeframe, then the coins are automatically returned (using nLockTime)

Upon recipt of the digital cash, the participants break it up into pieces of desired standardized sizes, which are necessary to maintain a large enough anonymity set.  Once the pool closes they request redemption of these pieces to newly created individual bitcoin addresses.  If after all the redemption requests come in there are enough bitcoins in the address to satisfy them all, then the digital cash server has clearly not cheated by overissuing, and the mix operators can safely release the bitcoins.  If not, then they are all either returned immediately to their original owners if the mix operators are still present and cooperating, or they can be claimed by the participants after the specified timeframe via the previously alluded to transaction script.

Notice that the participants are only at risk of losing their coins if not one mix operator is honest.  Their anonymity is as good as what Tor can provide them when communicating with the hidden digital cash server, as well as the size of the anonymity sets in the relevant standardized bitcoin quantities.

Of course fees would be charged in order to make this economical for all participants. The blockchain fee per participant scales proportionally to the number of pool operators, while the costs incurred by the mix operators and the digital cash server are proportional to the number of participants, and are relatively small compared to the overall blockchain fees.

If all this works, it would be nice to have a client that can easily interface with these mixes, will only spend your freshly mixed bitcoins without annoying warnings, will manage everything in such a way as to minimize mixing costs, and will only run over Tor.

And speaking of Tor, how anonymous is Bitcoin run over Tor?  Apparently BitTorrent isn't at all (http://arstechnica.com/tech-policy/news/2011/04/not-anonymous-attack-reveals-bittorrent-users-on-tor-network.ars), so could this also be the case with Bitcoin?
Jack of Diamonds
Sr. Member
****
Offline Offline

Activity: 252



View Profile
September 13, 2011, 01:57:53 PM
 #4

Would the laundry setting a minimum & maximum threshold in full amounts fulfill your criteria?

(e.x. minimum amount is 5 BTC at a time, maximum is 20, the only possible other amounts are 10/15)

Obviously transactions that could be pinpointed (such as a 6.8775 BTC) are not fit for laundering,
so using laundry-predefined full amounts would definitely obfuscate the origin & identity of the receiver if there is large enough volume on the site.

1f3gHNoBodYw1LLs3ndY0UanYB1tC0lnsBec4USeYoU9AREaCH34PBeGgAR67fx
BTCGameMaker
Newbie
*
Offline Offline

Activity: 24


View Profile
September 13, 2011, 02:53:15 PM
 #5

It should really be stressed that mixing services aren't enough.  Every bitcoin that comes in and every bitcoin that goes out of your possession needs to be obfuscated for true anonymity.  To accomplish this right now you could theoretically use a mixing service to accept all your coins and a mixing service to send all your coins. 

However, you still run into the amount tracking method.  It's pretty easy to look at the public transactions and say 5.93407 BTC when in here and 5.93407 BTC went out there.

To fix this problem you could have an "anonymous" account on an exchange or an online wallet accept and send all your transactions and only release 5 BTC to yourself at a time.  Of course how safe and reliable the exchanges and online wallets are still remains to be seen. 

However, now you run into the traffic problem.  If you're the only person doing this the 5 BTC transactions stand out pretty clearly.

There is also the problem of convenience which is tied to the traffic problem.  Doing all this manually is a pain in the a$$.  What is really needed is a client that will do it all for you.

Robit Coin Raiser New Bitcoin Game Coming Soon.
Read more at https://bitcointalk.org/index.php?topic=122656.0
Play the Demo at http://www.socialrosity.com/robit_demo/index.php
BTCGameMaker
Newbie
*
Offline Offline

Activity: 24


View Profile
September 13, 2011, 03:00:04 PM
 #6

Would the laundry setting a minimum & maximum threshold in full amounts fulfill your criteria?

(e.x. minimum amount is 5 BTC at a time, maximum is 20, the only possible other amounts are 10/15)

Obviously transactions that could be pinpointed (such as a 6.8775 BTC) are not fit for laundering,
so using laundry-predefined full amounts would definitely obfuscate the origin & identity of the receiver if there is large enough volume on the site.

Yeah I've played around with different ideas for different amounts to make it more universal.  What I've come up with is the idea of having your balance at the ASR to customizable to higher amounts.  So for example you could set your balance at the ASR to 25 BTC.  Then if you want to make a 19 BTC transaction, the ASR immediately sends the 19 BTC.  Then over the course of a certain time like and hour or whatever, your client would automatically send 5 BTC transactions to the ASR to refill the balance.

If done this way then you could have transaction sizes of 5 BTC and maybe 50 BTC for people that do large transactions amounts.  It's really determined by the volume of traffic.  If only a few people are passing blocks of 50 BTC at a time, then there really isn't any anonymity for them.

Robit Coin Raiser New Bitcoin Game Coming Soon.
Read more at https://bitcointalk.org/index.php?topic=122656.0
Play the Demo at http://www.socialrosity.com/robit_demo/index.php
andrewbadr
Full Member
***
Offline Offline

Activity: 162

MadPay.com — lowest rake of any dice game


View Profile WWW
September 13, 2011, 11:12:10 PM
 #7

This post doesn't seem to be getting a lot of attention, which is interesting considering anonymity is one of the best features of Bitcoin.  Part of the problem might be that you're explanations seem kind of technical and are hard to follow.  That being said, I've been thinking along the same lines as this for a while.  This is the working theory that I've come up with.

1. You have user clients and an ASR as you said.
2. All transactions between the clients and the ASR will be for 5 BTC.
3. If a user wants to send 6 BTC to a third party.  They will send 5 BTC to two separate addresses controlled by the ASR.  From any other addresses the ASR will send a total of 6 BTC to the third party.  The ASR will then log the balance of 4 BTC under a unique address.
4. If a user wants to receive 6 BTC from a third party the ASR generates a unique address for the user.  After receiving the 6 BTC, the ASR sends 5 BTC to the user and records the balance of 1 BTC under a unique address.
5. The user can as necessary draw from the balance to cover transactions less than 5 BTC or withdraw 5 BTC at a time if the balance exceeds this amount.  In this way the ASR will have control over a maximum of less than 5 BTC for any given user.

With enough traffic this should significantly conceal the connections of any transactions entering or leaving the ASR.

Other safety measures I've considered.

1. Have the ASR broken into programs split across multiple servers, so that hacking one server will not allow for control of the entire system.
2. Require that all transactions be confirmed by multiple servers independently.
3. Have all database entries double encrypted with one key being held on the server and one key being held by the user client.  In this way no database entries would be readable without the client that created them.
4. Have all programs making of the ASR sufficiently obfuscated and rewritten on a regular basis.  In this manner, even if someone hacked the server and gained access to the software, by the time they deciphered the software new software would be in place.

I've been playing around with how to implement this already, but it's kind of a big undertaking.  The user client would have to control all the tracking of funds behind the scenes so that it is easy for the user and the least amount of information possible is available to the ASR.  Then you would also need to create the ASR broken into multiple parts, and create an obfuscation program that could randomly replace variables and insert code to properly disguise the functioning of the program.

I agree with you that this is an issue that needs to be addressed and that current systems don't work.  But based on the attention this thread has gotten so far, I'm not sure the community actually takes this that seriously.

Thanks for your comments. It seems like you can either restrict in the inputs (as you propose above) or the outputs (as I proposed), to the same effect. There are advantages to each. One downside to maintaining a balance on the server is that it's a form of state to maintain, whereas the ASR I described above would not maintain any state except temporarily.

Unless some big exchange or other service starts using the ASR, it'll be really hard to get traction.

madpay.com · btckink.com
Explodicle
Hero Member
*****
Offline Offline

Activity: 947


View Profile
September 13, 2011, 11:44:32 PM
 #8

I've asked this on a couple other threads, but I haven't yet seen an explanation: why do the wallets need to be operated by a participant in the anonymity scheme? If you used existing online wallet services, your coins would be mixed with those belonging to thousands of other uninvolved people.  This would bootstrap off currently more popular services and look like normal commerce to an outside observer.
andrewbadr
Full Member
***
Offline Offline

Activity: 162

MadPay.com — lowest rake of any dice game


View Profile WWW
September 14, 2011, 12:18:17 AM
 #9

I've asked this on a couple other threads, but I haven't yet seen an explanation: why do the wallets need to be operated by a participant in the anonymity scheme? If you used existing online wallet services, your coins would be mixed with those belonging to thousands of other uninvolved people.  This would bootstrap off currently more popular services and look like normal commerce to an outside observer.

Because online wallets aren't designed for anonymity. They keep a record of your transaction history. Even if they let you delete it, their systems aren't designed from the ground-up to ensure that the records are fully deleted. They could be present in logs or backups or anything else. You also don't know how their wallet system works behind the scenes. It may not be like you're imagining, and it could change at any time. Finally, online wallets are trying to become big, profitable, legitimate companies. This kind of operation generally ends up complying with a lot more regulations.

madpay.com · btckink.com
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!