Bitcoin Forum
December 08, 2016, 08:37:00 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Decentralized coin mixing algorithm, using Namecoin and SIGHASH_ALL  (Read 1248 times)
Qoheleth
Legendary
*
Offline Offline

Activity: 882


Spurn wild goose chases. Seek that which endures.


View Profile WWW
July 17, 2012, 12:12:51 AM
 #1

Here's the algorithm:
  • Someone registers a K-V pair on the Namecoin network. The key is something like 'Melt:xxxxxxxxxxxx:0/3:1:InitialKey' - the xs are a randomly generated base58 round id (to distinguish from past and simultaneous swaps), the 0 is the id of the participant, the 3 is the number of bits of participants you're looking for (so, eight participants total, with ids 0-7), the 1 is the number of bitcoins that will be melted from each participant. The value assigned to this key will be your public key for communication with your fellow round participants.
  • Other people chime in with their public keys at addresses like 'Melt:xxxxxxxxxxxx:5/3:1:InitialKey' (this guy would be claiming id 5 in the cabal's range 0-7).
  • Each person posts their input and output addresses, encrypted with their binary-closest counterparty's private key. For instance, id 5 would post their input and output to 'Melt:xxxxxxxxxxxx:5/3:3:TxList', encrypted with the key at 'Melt:xxxxxxxxxxxx:4/3:1:InitialKey'.
  • Each person posts the input and output addresses of their group of two, encrypted with the private key of that group's counterparties. For instance, id 5 would post his input and output, combined with those of id 4, to 'Melt:xxxxxxxxxxxx:5/3:2:TxList' - two copies would be posted there, the first encrypted with the key at 'Melt:xxxxxxxxxxxx:6/3:1:InitialKey', the second encrypted with the key at 'Melt:xxxxxxxxxxxx:7/3:1:InitialKey'.
  • Things proceed. id 5 would post the combined inputs and outputs of ids 4-7 to 'Melt:xxxxxxxxxxxx:5/3:1:TxList', posting four copies: one each for ids 0-3 to read.
  • Now everyone knows the transaction that will be submitted to the Bitcoin network. They all do so, requesting the transfer of their own coins, making finalization of the transaction contingent on everyone else's coins arriving, and setting the transaction to void itself if it is not finalized by some period from the earliest InitialKey registration time among those involved InitialKeys.

My playing through this algorithm as id 5 means that only the participant at id 4 knows the mapping of my coins from input to output. The participants at id 6 and 7 only know that my output belongs to "either id 4 or id 5". The participants at ids 0-4 only know that my output belongs to one of 0-4's inputs. Everyone else only knows that my output belongs to someone who participated.

The overhead of this method per round is however much it costs to do log2(n)+1 Namecoin registrations, where n is number of participants in the round. Obviously, you'd want to do more than one round, so that your closest counterparty isn't aware of the "true" input->output mapping, but only the mapping for that round.

Thoughts?

If there is something that will make Bitcoin succeed, it is growth of utility - greater quantity and variety of goods and services offered for BTC. If there is something that will make Bitcoin fail, it is the culture of naive fools and conmen, the former convinced that BTC is a magic box that will turn them into millionaires, and the latter arriving by the busload to devour them.
1481229420
Hero Member
*
Offline Offline

Posts: 1481229420

View Profile Personal Message (Offline)

Ignore
1481229420
Reply with quote  #2

1481229420
Report to moderator
1481229420
Hero Member
*
Offline Offline

Posts: 1481229420

View Profile Personal Message (Offline)

Ignore
1481229420
Reply with quote  #2

1481229420
Report to moderator
There are several different types of Bitcoin clients. EWallets are like banks -- a central organization has complete control over your money. You shouldn't put much money in EWallets.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481229420
Hero Member
*
Offline Offline

Posts: 1481229420

View Profile Personal Message (Offline)

Ignore
1481229420
Reply with quote  #2

1481229420
Report to moderator
1481229420
Hero Member
*
Offline Offline

Posts: 1481229420

View Profile Personal Message (Offline)

Ignore
1481229420
Reply with quote  #2

1481229420
Report to moderator
1481229420
Hero Member
*
Offline Offline

Posts: 1481229420

View Profile Personal Message (Offline)

Ignore
1481229420
Reply with quote  #2

1481229420
Report to moderator
iCEBREAKER
Legendary
*
Offline Offline

Activity: 1512


Crypto is the separation of Power and State.


View Profile WWW
July 18, 2012, 04:54:23 AM
 #2

Sounds good to me!

Reducing dependence on centralized coin mixers should be a priority.  This is the first step towards that goal.

Plus it helps the dot-bit project.  Win-win!

Question:  Would it be a good idea to first clean the Namecoins used in a recursive manner?   Huh

The difference between bad and well-developed digital cash will determine whether we have a dictatorship or a real democracy.  David Chaum 1996
Fungibility provides privacy as a side effect.  Adam Back 2014
"Monero" : { Private - Auditable - 100% Fungible - Flexible Blocksize - Wild & Free® - Intro - Wallets - Podcats - Roadmap - Dice - Blackjack - Github - Android }


Bitcoin is intentionally designed to be ungovernable and governance-free.  luke-jr 2016
Blocks must necessarily be full for the Bitcoin network to be able to pay for its own security.  davout 2015
Blocksize is an intentionally limited resource, like the 21e6 BTC limit.  Changing it degrades the surrounding economics, creating negative incentives.  Jeff Garzik 2013


"I believed @Dashpay instamine was a bug & not a feature but then read: https://bitcointalk.org/index.php?topic=421615.msg13017231#msg13017231
I'm not against people making money, but can't support questionable origins."
https://twitter.com/Tone_LLT/status/717822927908024320


The raison d'être of bitcoin is trustlessness. - Eric Lombrozo 2015
It is an Engineering Requirement that Bitcoin be “Above the Law”  Paul Sztorc 2015
Resiliency, not efficiency, is the paramount goal of decentralized, non-state sanctioned currency -Jon Matonis 2015

Bitcoin is intentionally designed to be ungovernable and governance-free.  luke-jr 2016

Technology tends to move in the direction of making surveillance easier, and the ability of computers to track us doubles every eighteen months. - Phil Zimmerman 2013

The only way to make software secure, reliable, and fast is to make it small. Fight Features. - Andy Tanenbaum 2004

"Hard forks cannot be co
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
July 18, 2012, 05:22:23 AM
 #3

Wow, excellent idea.

What if you enhanced it as follows:

1 - find some other way for the parties to communicate other than Namecoin.  What if all the mixing nodes (which are software bots, of course) just hooked up with one another in an IRC channel and communicated in real time?

2 - have three rounds so that the participants at the beginning of the round aren't disadvantaged.  During the first round, participants pass around bogus inputs and payout keys.  During the second round, participants add the real ones to the bogus data set, which will look indistinguishable from the bogus ones, which prevents the second participant from knowing which real keys belong to the first etc.  During the third round, participants remove the bogus data they added to the set.

So example:

Parties A,B,C,D,E,F get together in an IRC channel and all agree to start mixing.  They each generate an RSA keypair.  Let's assume the parties will speak in order, though ideally a simple deterministic hashing scheme based on their public keys could randomize the order (assuming they hash-commit to their public keys first).

All parties throw out their public key for everyone to see.  From then on, messages are encrypted for their intended recipient unless otherwise noted.

Party A chooses 100 random unspent txids from the block chain (that are probably not his), and generates 100 bitcoin addresses.  Basically he is creating a false claim that he wants to mix those coins to camouflage the coins he's going to add to the dataset in a future round.  At the same time, he creates a random mapping of how he'd supposedly like those 100 txids to be paid to his bitcoin addresses.  He sends the whole thing to B.  (Actually, he could add any number of each, but I'm using 100 for simplicity).

Party B does the same thing, adds his data to the set generated by party A, and sends it to party C.

Same thing, to party D, then E, then F.  When F sends it back to A, there should be 600 txids and 600 bitcoin addresses.

Round 2: party A adds the txids of the real coins he wants to mix, and new payout addresses to receive them, and sends them to B to do the same.  Then it goes to C, D, E, F, and back to A.

Round 3: Party A removes all of the bogus information he added in round 1, sends it to B.  Then C,D,E,F, and when it gets back to A, only the real information should remain.

Party A announces the proposed transaction publicly.  Each party confirms that the mixing will result in them getting the same number of coins they put in.

If all parties agree to the transaction, they generate the signatures.  They also generate a bunch of bogus placeholder signatures, so they can exchange signatures without divulging e.g. how many real signatures they are delivering.

To exchange the signatures, they encrypt them repeatedly, onion style (think Tor), so they must be passed back and forth among participants in multiple rounds to unpeel the layers.  They are passed back and forth in random order, so no participants can identify the originator of any particular signature.

If one party doesn't agree with the proposed transaction (for example it omits a payout and shortchanges him), he generates all bogus signatures and no real ones, so his refusal to sign doesn't identify him to the person who altered the transaction to withhold his payout.

Once somebody/anybody has all the signatures (and the bogus signatures thrown out), the transaction is signed and broadcast.

During all rounds, outputs can only be specified in the following amounts of BTC: 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, etc.  Also, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01, 0.005, etc.... this uncouples the outputs from the inputs.  Otherwise, the guy who added 17.43233 BTC to the mix is probably the same guy with the 17.43233 BTC output.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
Gavin Andresen
Legendary
*
Offline Offline

Activity: 1652


Chief Scientist


View Profile WWW
July 18, 2012, 03:15:38 PM
 #4

That sounds more complicated than it needs to be.

If you can assume some mixers are honest and won't disclose what they added to the mix, then just do a series of pair-wise mixes.

E.g.

A and B communicate securely and create a transaction that has 2 inputs and 2 outputs, all of the same amount of bitcoins (A and B might need to send-to-selves to get the right sized outputs).  The output order is randomized. They each sign their input (after checking to make sure their output goes to them).

A could then repeat with C, then D and, assuming B, C, and D aren't all actually the same person recording his IP address and the mixes, would have a coins linked to the wallets of A/B/C/D.  I believe after a few mixing steps a simple clustering analysis would think everybody who participated in the mix is sharing one big wallet (but I know very little about that stuff, and I wouldn't be surprised to find out there are more sophisticated clustering techniques that look at transaction times and overall transaction ordering that might be able to see through the fog and figure out who is who).

If all the other participants in the mixes are actually the same person (Sybil attack) then I believe no matter WHAT algorithm you use you're sunk.

My intuition is that if you can make the pairwise-mixing case work, then involving more than 2 people at once might be a useful optimization.  But you should start with the 2-person case and prove it is secure before getting more complicated.

How often do you get the chance to work on a potentially world-changing project?
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
July 18, 2012, 03:31:32 PM
 #5

I thought about my idea as presented further and realized much of it wouldn't work: the whole idea of selecting bogus transactions from the start is flawed because in the end, everyone is going to know which inputs never made it into the final transaction.

Here is another idea: what if a bitcoin client optionally swapped amounts with peers?  Let me refer to this as a dance.

On a random periodic basis, node A could say to randomly selected node B, "I got 25 BTC, want to trade?".  Node B could say, "Sure, here is a txid of mine worth 25 BTC and a new receiving address for me."  Node A would say, "Here is a transaction that combines our 25BTC and then pays us each 25BTC, signed by me."  Node B ensures that the transaction will cause him to remain with even money if executed, and if so, signs and broadcasts it.

After such a transaction completed, the two 25BTC outputs would be indistinguishable.  One would know that either output must have come from one of the two parties, which isn't a huge distraction.  But if, network wide, dances involving 25BTC were commonplace, and getting from point X to point Y potentially involved six or ten or more junctions that each cool the trail by a factor of 50%, then the 25BTC chunks will be extremely hard to follow after little more than a few dances.

Dancing probably works best if change doesn't have to be involved.  Keeping it to a few well-defined amounts systemwide would be important so that making change doesn't have to be considered and so nodes can plan on having txid's available that are worth exactly the amount of a dance.  So if a peer with say 123 BTC wants to dance, he first sendmany's himself to four of his addresses so they have 25,25,25,23 BTC.  The 25BTC chunks will periodically be involved in dances and the 23 will not.

If there were multiple standard dance amounts besides 25BTC, that would allow any size wallet to be accommodated.  The 23BTC in the prior example could be split into 23 chunks of 1BTC, each of which dance with other peers who have a 1BTC transaction handy.

Also, if instead of peer A asking peer B to swap coins, it could ask several of its peers simultaneously, and construct a transaction that combines four or five 25BTC chunks instead of two.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
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!