Bitcoin Forum
March 29, 2024, 01:12:54 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 [2] 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 »
  Print  
Author Topic: CoinJoin: Bitcoin privacy for the real world  (Read 294477 times)
Luckybit
Hero Member
*****
Offline Offline

Activity: 714
Merit: 510



View Profile
August 23, 2013, 05:00:41 AM
 #21

This seems overly complicated. Is there any reason why Bitcoin isn't private enough as it is?

You presented a hypothetical situation which has not occurred yet.  It's not perfectly private but compared to credit cards and banks its very private. It's almost as private as cash.
1711674774
Hero Member
*
Offline Offline

Posts: 1711674774

View Profile Personal Message (Offline)

Ignore
1711674774
Reply with quote  #2

1711674774
Report to moderator
According to NIST and ECRYPT II, the cryptographic algorithms used in Bitcoin are expected to be strong until at least 2030. (After that, it will not be too difficult to transition to different algorithms.)
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1711674774
Hero Member
*
Offline Offline

Posts: 1711674774

View Profile Personal Message (Offline)

Ignore
1711674774
Reply with quote  #2

1711674774
Report to moderator
1711674774
Hero Member
*
Offline Offline

Posts: 1711674774

View Profile Personal Message (Offline)

Ignore
1711674774
Reply with quote  #2

1711674774
Report to moderator
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1120
Merit: 1147


View Profile
August 23, 2013, 06:03:30 AM
 #22

I'll accept that, but the counter-proposals/additions to your initial proposal do nothing to keep the complexity for the user down. As an end user who is looking for ease of use and decent privacy, some of the other schemes here, unless done transparently, are just too much to keep up with.

My proposal can be 100% automated - the user doesn't even need to know it's happening behind the scenes.

It's also not really any different in spirit from what gmaxwell suggested in the first place - I've only fleshed out details with a particular way to do it.

gmaxwell (OP)
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
August 23, 2013, 06:41:58 AM
Last edit: August 23, 2013, 06:57:51 AM by gmaxwell
 #23

This seems overly complicated. Is there any reason why Bitcoin isn't private enough as it is?
You presented a hypothetical situation which has not occurred yet.  It's not perfectly private but compared to credit cards and banks its very private. It's almost as private as cash.
I edited that post down from a longer (4000 word?) version which included some specific examples that I had some personal involvement in: The (third?) ozcoin thief, who was identified by sending funds to a wallet service that reused addresses (and ultimately had those funds clawed back), and a person who had an insecure brain wallet found by a whitehat, ultimately tracked down and contacted due to a mining pool which reused addresses.

There are many other examples of privacy in Bitcoin being weak— one only needs to spend a few minutes browsing through bc.i's public block explorer interface to see real names attached to transactions (found by spidering webforums) and frequently accurate IP addresses (associated by connecting to many nodes), and from there you can find additional related addresses with the taint analysis button. Or look at the academic research "Bitcoin is not inherently anonymous. It may be possible to conduct transactions is such a way so as to obscure your identity, but, in many cases, users and their transactions can be identified." (papers on Bitcoin are of, ahem, highly variable quality— but the point remains, Bitcoin's privacy as it is today is not very good).

The privacy gap between Bitcoin and cash for most users is enormous, enough so that we have an explicit warning on Bitcoin.org:
Quote from: bitcoin.org
"Some effort is required in order to protect your privacy with Bitcoin. All Bitcoin transactions are stored publicly and permanently on the network, which means anyone can see the balance and transactions of any Bitcoin address. However, the identity of the owner cannot be associated with their Bitcoin address until personal information is revealed by the owner during an exchange. This is why it is recommended for Bitcoin owners to use many different Bitcoin addresses; in fact, you should create a new one each time you receive money. This is especially important for public uses such as websites. You might also want to consider hiding your computer's IP address with a tool like Tor so that it cannot be logged."

Ignorance of these limitations makes the situation worse because without being acutely aware of the risk you will transact in ways that leaks more information about you and the parties you trade with.
phelix
Legendary
*
Offline Offline

Activity: 1708
Merit: 1019



View Profile
August 23, 2013, 09:23:39 AM
 #24

We need a concept for a practical implementation of this in the main client. Then bounties and popcorn.

TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1077


View Profile
August 23, 2013, 10:12:45 AM
 #25

I'm actually thinking that mixes should have a small number of participants, usually two or three. Remember that we want the process of creating a tx to be as fast as possible, and multiple rounds of mixes wind up with just as much anonymity as fewer rounds with more participants in each round.

If it was locked to 2 participants, then you could use something like

flip a coin

If heads, send a broadcast with "I'll pay for <my outputs>".
If tails, wait for a broadcast and then broadcast to 50% of peers "I'll pay into mix(<other's outputs> <my outputs>)"

(Tails needs a timeout)

wait until you receive tx with all outputs broadcast from 1/3 of peers [ * ]

Wait 5 to 15 seconds at random from that point to broadcast tx with signed inputs that pay to the full set of outputs [ ** ]

One or other of the 2 participants can broadcast the full transaction to the network.

The fee would have to be agreed in advance.  Each participant would pay half the fee.

I still think standard coin sizes would help with the mixing.  However, the trick where you create a coin to mix with a person's change address is a good idea.

You could actually mix with both pieces.

I send 0.1BTC and 0.01BTC change.  The other person might buy something for 0.9 BTC with change of 0.1, 0.01 and <remainder>.  They get their change mostly mixed and would still be paying a tx fee.

[ * ]
If you send the broadcast, then this is 1/3 of the nodes you didn't send it to.  This could be restricted to outbound nodes.
This syncs both participants to have the same start time.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
Nordstern
Member
**
Offline Offline

Activity: 108
Merit: 10



View Profile
August 25, 2013, 09:50:28 AM
 #26

Paying for anonymity isn't a good idea! It let look the coin like some commercial instrument (what we all dont want!). Maybe it is a good idea to pay with some stake or similar concept?
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518
Merit: 521


View Profile
August 25, 2013, 03:36:03 PM
Last edit: August 25, 2013, 04:14:57 PM by AnonyMint
 #27

Check my logic. I don't see the point.

As I understand the problem-to-solve is that if someone reveals your identity for any transaction then any other spends from the same public key are associated with your identity and any spends (inputs) from other public keys to the same transactions as the identified public key are with high-likelihood associated with your identity.

The CoinJoin solution is dual pronged in that if a greater percentage of blockchain transactions are inputs from multiple parties, then the high-likelihood case is reduced in likelihood for all users of the blockchain that don't use CoinJoin. The second prong is the mixing of parties for a transaction using CoinJoin protects the identity of the public keys for the parties spending using CoinJoin.

Note the first prong is an improvement even when someone reveals your identity for all the input public keys of a transaction, because you may use one of those public keys later with other uncompromised public keys in other transactions that were not revealed.

However, CoinJoin is unnecessary if no one ever knows your identity.

If you must provide your identity, then why are you using Bitcoin and not your credit card, cash, money order, paypal, etc?

I suppose there are rare cases where you want to give your identity to someone trusted but not the identity of the merchant to your bank. But that hardly seems like a compelling use case to justify such convoluted systems as proposed for CoinJoin. Credit card numbers can be stolen but in the relatively rare event, most of the time your issuer will remove any unauthorized charges. If identity theft is your concern, then again why are you providing your identity.

And against the NSA and the government, plausible deniability is not a defense (btw jim is James A Donald, first person ever publicly recorded as interacting with Satoshi). So if they know your IP then they can compel you to unmix all the mixing stages.

Thus, I view zerocoin and CoinJoin as a lower priority than a high-latency Chaum mix-net (or dc-net), which we don't have available today.

If you are littering your identity all over the web, then nothing is going to help you.

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
jdillon
Member
**
Offline Offline

Activity: 70
Merit: 18


View Profile
August 26, 2013, 04:41:07 AM
Last edit: August 29, 2013, 02:32:49 AM by jdillon
 #28

Edit: donating more

I may be jumping the gun a bit, but please accept this 10.11BTC donation to the fund:


-----BEGIN PGP MESSAGE-----
Version: GnuPG v1.4.11 (GNU/Linux)

hQIOAwAAAAAAAAAAEAgAhYb+uVMQsS/LBxtWH3PKcfQkpBhbygfrRLtaZn4DSPGP
F12rmQQ8QRJOiRyKgrXrwXWoLZ4cFA9q2VabhyiYLWo/NO+pdP+h/XnHteTmjvTI
rRwZjMtXntGZO2Awh+BpsKlUyfnDpCuPbkZGT82/iubUWhTrbQAPseEISVArP9Jd
SvPVnw2cHQnvBu9aU6+qzf7rmYox2dMYPHkAtRLtAYO5WU087dhGWoNW0S7E6pNG
P8NkYYg18YJA7wHZ9raBf6QzhhEJY4ppuIIe6P60CzxsU+acswPA3yFKjzPXaMQv
ZeglXsOC/jWX36s/f7Q03ICPg2wEguJiMrKPDew9fwf/eX+or4F1QLJWX7e2bPbS
hMsI+H/EjV9iuNoRmYmWQq+Q+aP6RZC6SwESXEgp0lqr3poLO0za7mYuxiiZg2IQ
1255u2yVz0ikdGv1VKr2tyEZLitARID3YVetEWdTIm/rlHsKV7stF6zh+fnVIHjx
jkmaKa4G8dGGOhDt2xLsgfB6oJ9iuDJHSDL9nXU3aanTPc7E8NFhUHrxBW+CWu6E
wo7xlnfjYrSYFTjrhVqm0ywbWmpyTdhb54w7AroOjeTU7axgcbNV4b59v0H8HSx2
EGlDnSf4wKWPX28c9r/aXevd5Jt2GQtwI48noqKNC4ryPVgZF65FpaRy7Z0E9s21
CIUBDAMAAAAAAAAAAAEH/0QxCBCEp8x+QwA1WwvyD4/f4OW8LAjKO2idR9NNJFx0
yLK0ohtX5nGryZujvAwvZmG1Haanj9QFQ26Xxpe4NINGee3EZ/kBMIxDWQ7vqXmx
yvU+g6W8lhwWO4Fs9mX5yrt/KnYL2AS5e4A3ZKXiJzLvd+fQ26NuuO9UTeHvB4fv
DaivRxV+Jytfym875cob+q4BvjklqjW4QSKMLMZbHXUgYlqmEWbVdIqOMoa/11nA
c9vYWzMBv4+dzX1QNILtAjH57zac2axowKDanZ0zCmp0WyZu3ZzDRP3/SIIilCKr
TrKxTeRzgJssOacxahH9qSFxYlWbtZ61mZJmU8Ny7HaFAQwDAAAAAAAAAAABB/9D
krpjhcyVrDTq/6b8QiCxznCiv8GvMLQEs4amVStGXYY8YnwuTqcOpzrMno0/FQp/
atkMc8mR1LoeWd182YRvnRRDqBM3Iz8OsEPOM2Pnjgi/ZTrKkncWMOiZALjH2vLT
JKCJa62ou08cDL6Y+sX9SHQOpxG3kG1/QcKaaqwpbQLLm6lz4TxF1+c/Mjd9Zukq
3qq9h2v7gwbc6KJXsq3ZbXp5prNgAhtoJPRIv+kcxnfEwO0hpGnyoJ1xb16YsqMN
L6JmmHKJhi60B6t4S8TWvth7piVfce1d6izDpXQJ2gmkNS/mah3rw/jpeCdHgeQd
PnqaSkj5Nmqa98rbYQyo0ukBYW9cHSZONbFqT994oSU/7C+8GVFPXet+gxbja9nB
kaWwi1PL7ngSSrYbchzrREmLxNY3RALVwcjWyPrc7Dax+G+vfVw+dANzxQtt0a22
J6hFVBAp70XvNM9YCg1CkAIqnyd+Y8bYmgAcAkNOovg2KZh0wWmziAEP/FizNbZm
xpWd4TXzTKNae3usoJxjBGUS6DAk26fZFkvczqEDJBW3GCPHYcupIa9k9FECnIaF
Wp/YodreY3bzFWidJpFZtpvt4qLz/PovxhZoR/9nqBjwsCJSEXtx7VcuPjKKWCRx
7miDE/xzKS8QIKV8/BZjcNf0S6H/BwxnGyzLTVSpukPvqy8B/RxUO+nf4RFSNpNT
jp+0tlILpncwzTDL2h6FF/jtj+nl4cTT23ZazbkuYAlxnwMxU+GU6jtQZLHAoYdo
n9TjMNDZZCRN5spMWu1UWnKqQ1Gc43q0vUJ+s5KWj2T3lOoYoSsNYrAQmPoilsLH
3Lh0Lg4sPVoG1DwwKXOVrkJF34utSlCFl63h/PMFXmjRgcueb0Ta6POU4njGg8VY
sEKc0bux7+lK0bMgoQA3O/quxHsK0Q3uQVWmNtTjqU2uf/sE3mz5twTGU8bDOWYu
88PuGBANtQHkNR1Cz1yHnPug5tI8NXYsC3PNKnu9DmI9y4TBK6qFSfJm8cZVbfLS
AcD7vvQgizaMTNi8FW4/NfKi0tNLE8foZgV1m6pXgYr4pzfWhWdcJUZ7ClV41Vzl
RDayvveBOWy/w68eUc8/5nWmH6+phmwtpjFWuht/OIGY1Oo91LoO0h+CgMKf5kur
zCBa72DTZfVpaDzwaRcr8tcP60u77PYrL8NMw6LP9q7760bbij+DJ274tWlmJnsM
9q/ZhVXm7bW5m1gXIGO7Hl4Dce9S3ImxxzCogcwP0VaZP4IZPNCmmK8xkmIiAKDV
Rr8mKh00KtaP0tby06IOuRr5bo2XbMo0knEwsdVHyM/yocAfPMbfPlJlao5ZI/XA
xV5db7pETa08sjKoYGHyjvJnclQ9P0yFy8jK/b8LoFAej/bVGQwdckIsBIEUg28F
C1tOskPkd7B4fiL4tGqfEkI7msvGYgH366kI63osglOcaYTj4BzvufkqSO4LwgLK
yzZlmyVfx+PaJzoL1F+IGUAmD9E4Fz5dporFHGW2elAtIh8MEywyZyPWvr1kJ5Q8
iEe3CHLM0X834PwLQ7snKzuoCulRvQnuiwfqVqASTwwjR05XpzhcalWAkhSPgRG/
rj1GXIngmSEO/hiFSOE=
=AaHO
-----END PGP MESSAGE-----

What I most like about this concept is its simple engineering pragmatism. You know, ZeroCoin solves exactly one problem really well, but it solves it so well because they pushed the envelope so far in one particular direction. From an academic point of view it makes for great papers and clever theory, but the history of cryptography is littered with empty and disused ivory towers, and in any case often those towers lack railings.

I have to wonder how many of the people pushing ZeroCoin so hard even recognize that it needs a mix net or a standard way of getting your transactions to those you are paying to be useful?

AnonyMint: You come so close to being pragmatic in how you recognize the need for mixers for communication. But then you miss so badly, like it or not, normal users will make mistakes that reveal their identity, and CoinJoin can help make those mistakes less devastating. In any case it is usually not the boogeyman of three-letter-agencies who the users of CoinJoin would be trying to protect themselves from, but individuals and businesses who simply want to use Bitcoin with the same level of financial privacy they enjoy in with the convention banking system.

Look at the above. I am happy to have the world know I am giving 5BTC to this effort, and I am happy for Gregory Maxwell to know that it is me where the money is coming from. But why should I give the whole world insight into my finances? With CoinJoin I won't have to use something as convoluted as encrypting an access key, and the proposals above share a common thread of being such that all the actual complexity can be hidden away in software with a sufficiently sophisticated implementation.
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518
Merit: 521


View Profile
August 26, 2013, 05:46:34 AM
Last edit: August 30, 2013, 03:08:00 PM by AnonyMint
 #29

AnonyMint: You come so close to being pragmatic in how you recognize the need for mixers for communication. But then you miss so badly, like it or not, normal users will make mistakes that reveal their identity, and CoinJoin can help make those mistakes less devastating. In any case it is usually not the boogeyman of three-letter-agencies who the users of CoinJoin would be trying to protect themselves from, but individuals and businesses who simply want to use Bitcoin with the same level of financial privacy they enjoy in with the convention banking system.

That is if there is no cost to having multiplexed transactions, unlimited number of public keys, and the delays and limited time windows of CoinJoin or the blockchain + hash check bloat of Zerocoin. I am also thinking of a Visa-scalable block chain. Your naive users will never be using Bitcoin any way, because the blockchain can't scale. By making CoinJoin popular, you will have further cemented Bitcoin's inability to modify the block chain design in this respect (although there may be a way to scale the block chain with multiplexed transactions and unlimited public keys, I am still studying this).

If there is no cost, I am not against it. I am arguing it is lower priority, not that it isn't worth considering if it fits into the big picture goals.

If we aren't concerned about the bogeyman who can see everyone's IP address or deposit viruses on our machine, then employing a high-latency Chaum mix-net with a standalone machine (e.g. Rasberry PI running L4 Linux) isn't that crucial. Then the only way users reveal their identity is by:

1. Explicitly giving it to the recipient.

2. Using the same browser for both entering their spending public key and browsing the internet, e.g. Google's cookies.

3. Use Windows 8

Did I miss any?

If we are concerned about more sophisticated harvesting of identity (which I am, because of Anonymity or Regulation and more), then with a high-latency Chaum mix-net built in for all incoming transactions, the above two pitfalls still apply.

And even with CoinJoin or Zerocoin, the above three pitfalls still apply.

I still don't see how CoinJoin or Zerocoin practically gain the naive user anything. Either the user stops giving up their identity by not doing the above three items, or they don't.

I understand the concept that IF users only give up their identity by mistake infrequently, thus delinking the block chain can in theory recover from such user error. However, I think users do what they do habitually.

P.S. CoinWitness is interesting because it can move the multiplexing of transactions off the blockchain, so then people employing decentralized mixing don't burden the block chain design. However, if a future design limits public keys, still need to support in the blockchain some way to retire and regenerate public keys for those coming out the other side of the offline mixer. (EDIT: note that last sentence might not be true, if the output can pay to existing key which is not yourself.)

Look at the above. I am happy to have the world know I am giving 5BTC to this effort, and I am happy for Gregory Maxwell to know that it is me where the money is coming from. But why should I give the whole world insight into my finances? With CoinJoin I won't have to use something as convoluted as encrypting an access key, and the proposals above share a common thread of being such that all the actual complexity can be hidden away in software with a sufficiently sophisticated implementation.

So why not have a separate individual BTC pool of capital for those purposes where you explicitly want to be public? Else send him a paypal to his email address. (Personally I wouldn't be announcing publicly my ownership of Bitcoin, because I think the governments are going to demand capital gains taxes in arrears, when they declare it isn't money rather a good like gold).

You are conflating use cases of BTC, just because you want it to be more convenient in one way, yet you potentially make it less capable in another way (for someone who is considering any possible blockchain design for the future) by choosing that convenience over other considerations.

We have to be sophisticated in our analysis of tradeoffs.

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
gmaxwell (OP)
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
August 26, 2013, 07:34:44 PM
 #30

The bounty address is now up and already has 12.19262795 BTC assigned to it.
gmaxwell (OP)
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
August 26, 2013, 07:39:23 PM
 #31

Another potentially useful idea I had in this space is CoinJoin software for doing matching charitable contributions.

E.g. you announce "I'll pay ~1 BTC to the EFF if 10 other people do too" and form a joint transaction with a single output. This may be fun, socially beneficial, and improve user privacy because even 1 TX output transactions couldn't be assumed to reveal common ownership of the input keys. Likewise, common donation outputs could be used to receive jagged change ediges in other kinds of join transactions which would otherwise be data revealing.
TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1077


View Profile
August 26, 2013, 08:04:15 PM
 #32

you announce "I'll pay ~1 BTC to the EFF if 10 other people do too" and form a joint transaction with a single output.

It has the nice feature as a leading application that it would be harder to shut down as it is charitable.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
Natanael
Newbie
*
Offline Offline

Activity: 27
Merit: 0


View Profile WWW
August 26, 2013, 08:10:21 PM
 #33

I have one suggestion that among others uses Secure Multiparty Computation (SMPC). https://en.wikipedia.org/wiki/Secure_multi-party_computation

Step one: Peer finding is done using a DHT network. This can be done inside I2P or Tor if you want to for increased anonymity. You might want to do reputation tracking where nodes uses public-key based pseudonyms (if you reuse a pseudonym, you must make sure to not spend inputs that can be tied to you personally more than just once (or rather not more often than the average, some identifiable inputs might by chance be involved with the same 3rd party multiple times) with that pseudonym since it otherwise can be directly correlated with your pseudonym).

To make verification of inputs simple and quick, each client keeps an updated Merkle tree hash of all currently valid spendable outputs in the blockchain (basically those that not have been spent yet) in this form: [Address]-[Transaction ID]-[Amount of BTC].

The SMPC uses cryptography to emulate a trusted 3rd party computer, running code all participants have agreed on. Unless a majority of the participants collude (Sybil attacks are a potential issue, be careful about who you run this with), no participant can get any other information out of it than they are *supposed* to get out of it.

Now, everybody puts in their transactions and their private keys for them. The SMPC checks if all participants really have the correct private keys for the (valid) previous outputs they claim as inputs through checking what addresses they correspond to, what transaction ID was claimed and how many bitcoins are claimed, and checks this data against the Merkle hash tree.

It then checks that the outputs aren't larger than the inputs. A transaction is then generated with all the user provided inputs and outputs, and signs it with all the private keys.

The signed transaction is given as an output to all the participants, and any one of them can publish it (or all of them at once).

Nobody can know which transactions came from whom, other than that they know their own. Out comes a signed Bitcoin transaction that includes them all in one. Either everything gets signed properly or it exits with an error. The protocol doesn't allow the generated transaction to be created in any other way than the correct way. All user specified outputs will be included, all user specified inputs will be included, no user can specify larger outputs than inputs (unless everybody agrees), etc...

The only major risk here is that of a Sybil attack (a large number of colluding nodes), and the major risk in here is private-key disclosure, the second is identifying which pseudonym spent what input. I hope that we can get around that somehow. One possible way is to not have the private keys provided to the SMPC, but to use simply prove you have the private key through signing a challenge of some sort, where the challenge can be a random number that is a checksum of all random numbers provided as inputs by the participants, so you only need one signature per participant. The SMPC would then only output an unsigned transaction, where all participants needs to sign it. The question then is how they all share their signatures with the other participants, ideally they should be able to hide that it came from them. Chaumian blinding could maybe be used in this step.

If you decide to not use blinding (to just pass on your signature), and not use any permanent pseudonym of any kind, then you'll have a risk of DoS attempts through both doublespend attempts (making the generated transaction invalid) and through canceled SMPC runs at the last step (thus wasting CPU power).

My intent is to make the system as automatable and fast as possible while maintaining full security.
phelix
Legendary
*
Offline Offline

Activity: 1708
Merit: 1019



View Profile
August 26, 2013, 08:14:03 PM
 #34

The bounty address is now up and already has 12.19262795 BTC assigned to it.
What about putting it somewhere on the OP top and adding a tldr?

CoinJoin - Improving Bitcoin Privacy using Shared Transactions

Will spin it on http://blockchained.com

gmaxwell (OP)
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
August 26, 2013, 08:18:07 PM
 #35

I don't see any reason to hand your private key over to the SMPC, the point of this thread is that our transaction design is already such that users can separately sign a transaction. You could use SMPC to build the transaction to sign, and then everyone signs.  This would be less brittle, e.g. sybils don't get your private key they can only jam the process or get a user unfairly banned. OH you say that at the end.

I don't follow why you think you need signature privacy at the end? You could use a homorphic mix, or just use SMPC to do the combine (e.g. two phases)... but the signatures only show ownership of an input, and the input side is normally not considered as private.

I'm not aware of any general production scale implementations of SMPC, it would be very exciting for a lot of things— are you aware of any system that could be realistically tasked with signing bitcoin transactions with commodity hardware separated by consumer internet connections?
Natanael
Newbie
*
Offline Offline

Activity: 27
Merit: 0


View Profile WWW
August 26, 2013, 08:28:39 PM
 #36

I don't see any reason to hand your private key over to the SMPC, the point of this thread is that our transaction design is already such that users can separately sign a transaction. You could use SMPC to build the transaction to sign, and then everyone signs.  This would be less brittle, e.g. sybils don't get your private key they can only jam the process or get a user unfairly banned. OH you say that at the end.

I don't follow why you think you need signature privacy at the end? You could use a homorphic mix, or just use SMPC to do the combine (e.g. two phases)... but the signatures only show ownership of an input, and the input side is normally not considered as private.

I'm not aware of any general production scale implementations of SMPC, it would be very exciting for a lot of things— are you aware of any system that could be realistically tasked with signing bitcoin transactions with commodity hardware separated by consumer internet connections?

gmaxwell: Yes, in the last part of that comment, that's what I suggested.

If a pseudonym is reused often, then correlation could be used to link all inputs with the pseudonym that provided them. This could the be further used to see if outputs from mixed transactions that the pseudonym in question has been part in often has some outputs in common, thus deanonymizing users who use this frequently for the same outputs (assuming the recipient has repeating or non-individual payment/donation addresses, which is common).

I've read that SMPC has been used IRL successfully for auctions for farms selling their goods. Can't remember the source. SMPC should be possible to run on most hardware. There's multiple implementations of it, some in Java and some in C.

How would a homomorphic mix work?

Two-round SMPC could certainly work, where the inputs simply are the individual signatures plus the previously unsigned transaction, creating a properly signed transaction.

Edit: SMPC implementations:
FairplayMP: http://www.cs.huji.ac.il/project/Fairplay/
Sepia: http://www.sepia.ee.ethz.ch/
Viff: http://viff.dk/
SIMAP (nothing available for download?): http://ny.alexandra.dk/uk/labs/Security-lab/Pages/Secure-Multiparty-Computation.aspx
gmaxwell (OP)
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
August 26, 2013, 08:37:27 PM
 #37

If a pseudonym is reused often, then correlation could be used to link all inputs with the pseudonym that provided them. This could the be further used to see if outputs from mixed transactions that the pseudonym in question has been part in often has some outputs in common, thus deanonymizing users who use this frequently for the same outputs (assuming the recipient has repeating or non-individual payment/donation addresses, which is common).
Ah okay, yes the anti-dos pseudonym tracking is why I had suggested the method of using the input coin itself as the identity.

Quote
I've read that SMPC has been used IRL successfully for auctions for farms selling their goods. Can't remember the source. SMPC should be possible to run on most hardware. There's multiple implementations of it, some in Java and some in C.
A specialized for doing a meet in the middle auction (e.g. a few comparison operations and an arithmetic average) is a whole other of magnitude less complex than running a complete transaction processing program in it. Going and figuring out where the state of the art is in that space has been on my todo list.

Quote
How would a homomorphic mix work?
Every participants has a key for a homomorphic encryption scheme (which can be decrypted or encrypted in arbitrary order). Each party encrypts their signature with everyones key, the signatures are grouped up and passed around, with each peer permuting their order and applying a re-encryption operation. At the end they all decrypt in sequence and you get a mixed output. The downside is that people can silently jam the mix by replacing or corrupting data during reencryption. To prevent this you need to do cut and choose (e.g. mix 10000 times, commit to all of them, one gets picked as the real mix output and you reveal the rest) and that takes a lot of bandwidth.

As an aside— I hope the cryptowizardy for the decenteralized versions of this aren't scaring people off. Part of the merit of CoinJoin as an idea is that there are braindead simple ways of using these ideas that don't require cryptomagic and are only somewhat compromised compared to what you can do with maximal magic.  I personally find the magic very exciting, but I find actual systems that people can use even _more_ exciting.  I hope people will work at this space from both ends.
Natanael
Newbie
*
Offline Offline

Activity: 27
Merit: 0


View Profile WWW
August 26, 2013, 08:51:54 PM
 #38

Quote
using the input coin itself as the identity

I don't see how that would help countering DoS, you won't likely be reusing inputs so there can't be reputation tracking.

Quote
A specialized for doing a meet in the middle auction (e.g. a few comparison operations and an arithmetic average) is a whole other of magnitude less complex than running a complete transaction processing program in it. Going and figuring out where the state of the art is in that space has been on my todo list.

It was a bit more than that IIRC. It was highest bid wins, with winner paying the price set by the second highest bid, and it was NOT just two or three participants, it was a LARGE auction. A very large amount of offered goods and bids.

Besides for risk of sybil+correlation attacks (which can be partially countered through reputation tracking), I like my SMPC scheme.
gmaxwell (OP)
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
August 26, 2013, 08:59:37 PM
 #39

Quote
using the input coin itself as the identity
I don't see how that would help countering DoS, you won't likely be reusing inputs so there can't be reputation tracking.
You don't reuse your inputs if the transaction completes successfully. Basically having an available (potentially aged) input of sufficient size that has not been used to jam the mix is a scarce resource that would limit attackers. The network already rate-limits people's ability to create new outputs as part of its own dos protection. This isn't the greatest anti-DoS possible, though you could add PoW to it too if you wanted, but in the lightweight schemes the harm of jamming the mix is very low, so the protection doesn't have to be especially great.
Natanael
Newbie
*
Offline Offline

Activity: 27
Merit: 0


View Profile WWW
August 26, 2013, 09:10:34 PM
 #40

Ok, so coin age would be your DoS countermeasure?

Note that attackers don't actually have to spend that input if they disrupt the protocol. They can use the same one over and over, even many times simultaneously.

PoW could be an option where participants can set a minimum PoW accepted and a maximum PoW they're themselves willing to perform. So for example if 10 people all have 2^15 work within their range of acceptable PoW (one has 2^15 as their lowest, another as their highest, they'll all generate a common input for PoW and start working on it. Then they start this scheme with the SMPC. That would indeed make the attack costly for somebody trying to break the scheme for as many as possible (DoS) and would make Sybil very costly.
Pages: « 1 [2] 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 »
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!