Re: [Bitcoin-development] New paper: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies
This is great to see. On Monday 02 March 2015 11:48:24 Andrew Miller wrote: > One of the main goals of our work is to build a bridge between the > computer science research community and the cryptocurrency community. > Many of the most interesting ideas and proposals for Bitcoin come from > this mailing list and forums/wikis/irc channels, where many academic > researchers simply don’t know to look! This is indeed a problem in the research community. Often ideas from here are just overlooked, and e.g., re-invented or not properly acknowledged. Of course, this is (in almost all cases) not intentionally. It's just difficult to keep track of everything. Your paper is a definitely the right approach to bring the researchers closer to the Bitcoin community. Best, Tim -- Dive into the World of Parallel Programming The Go Parallel Website, sponsored by Intel and developed in partnership with Slashdot Media, is your hub for all things parallel software development, from weekly thought leadership blogs to news, videos, case studies, tutorials and more. Take a look and join the conversation now. http://goparallel.sourceforge.net/ ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
Hmm, you are right. Lightweight clients are an interesting point, we have to think about a policy for them. As you said, the worst case is that the tx will not confirm. So the only possible attack is DoS. For clients that rely on servers it's reasonable to trust their servers not to perform DoS. (Anyway, the servers could do worse attacks.) For SPV-clients (without servers), I'm not sure at the moment. Something like getUTXO seems to be a possibility. I think even SPV-clients can verify the validity of the tx that created the input that is designated for mixing. Then the only remaining reason why it could be invalid is that the input could have been spent already otherwise. But in this case, only one honest client with full information would suffice: a signed transaction that spends the money would convince even SPV-clients that the participant with this inputs tries to cheat. This transaction could even be provided by lightweight client that got if from a server; the transaction is signed by the cheating participant anyway. Tim On Monday 11 August 2014 02:30:16 Chris Pacia wrote: > Actually getUTXO would probably work here as well. It isn't authenticated > but it should be good enough for this purpose. The worst that would happen > is the tx doesn't confirm. > > On Aug 11, 2014 2:25 AM, "Chris Pacia" wrote: > > One issue I do see is the protocol requires participants to check the > > inputs submitted by others are valid. Lite clients (at least of the p2p > > variety) cannot perform this check. > > > > You could skip the verification part and if the inputs turn out to be > > invalid then you'll find out when it doesn't confirm. This would problem > > open the protocol up to dos attacks and prevent part of the "blame" phase > > from working properly. > > > > Alternatively you can have the participants submit the merkle proof for > > the input. This would require inputs to have at least one confirmation, > > however. signature.asc Description: This is a digitally signed message part. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
You are raising valid questions and one goal of our posting here is indeed to discuss exactly these system issues. On Thursday 07 August 2014 15:00:11 you wrote: > I think the description at your website leaves out the truly interesting > part: How do you decentralize this securely? > - How do Alice, Bob, Charlie and Dave communicate, i.e. which network is > used for communication and how? The simplest approach is obviously to use direct connections to a randomly elected leader, who is also responsible for the broadcasts. One advantage of CoinShuffle is that the unlinkability between input and output addresses is guaranteed, no matter which underlying network you use. (Still, it is a good idea in general to hide your IP address but we can let the user decide here.) Of course, there would be other possibilities, such as overlay networks. Coinmux, a CoinJoin prototype by Michael Pearce (http://coinmux.com/) uses TomP2P, a distributed hash table, for communication. Do you have any hints regarding this point? > - How does Alice know that Bob, Charlie and Dave are not the same person? > (= how do you prevent a Sybil attack?) > > Because thats the real problem with mixing it seems - ensuring that your > mixing partners are actually 100 people and not just 1 attacker. There are > probably many mixing algorithms which work if you solve that problem, but I > don't see how you offer a solution for it :( It's true that there are a few proposals for mixing protocols which all have their advantages and disadvantages. However, it's not true that the mixing itself becomes simple if you solve the problem of Sybil attacks. Still, mixing is difficult to get right: Even if there are no Sybil attacks, you have to ensure that the participants (or a server) cannot break unlinkability or steal money. Actually that's why there are several proposals for mixing protocols, because there is no obvious perfect solution. Regarding your question: It is indeed very important to get this right. Fundamentally, there is nothing that prevents the attacker from creating a lot of identities participating in a lot of CoinJoins. However, there are ways that make it hard for the attacker to put an honest user together only with malicious users. For a moment, assume that you can reliably establish a pool of users that would like to participate in the protocol. (I will discuss this later.) You have to divide the users to individual groups, i.e., CoinJoins runs. If the assignment cannot be influenced by the attacker, then the probability that there are also honest users in a run is quite high. Of course, the attacker is able to reduce your anonymity set but they cannot just put you together only with their malicious identities. Note that the attacker has to pay transaction fees for joining many transaction. One could even increase the required fee depending on the number of users in the pool (enforced by honest CoinShuffle participants that would not accept CoinJoins that pay a lower transaction fee). And making sure that the attacker cannot influence the assignment is simple: One can use the hash of all users' public keys in the pool to determine the assignment for example. For the initial setup step, i.e., creating the pool of participants, you need some kind of "bulletin board". One possibility is to use an underlying peer-to-peer network. Bitcoin itself is the first that comes to the mind but it does not allow arbitrary messages. So if we do not want to change the Bitcoin protocol, chans in Bitmessage are a very promising possibility. Bitmessage relies basically on the same broadcast mechanism as Bitcoin. If you as a peer use enough outgoing connections to other peers, it's very difficult for an attacker to ensure that your message will not be spread among the network. (Btw, people have used this to do CoinJoin manually already https://forum.namecoin.info/viewtopic.php?f=2&t=1694 .) Solutions like distributed hashtables (TomP2P again) are another possibility. We are not sure which of those approaches provides the best robustness against malicious nodes that try to stop single participants from reaching the network. For the setup step, latency is not an issue, so Bitmessage is indeed a promising candidate here. I think that in general, P2P is the way to go here, but there are other approaches as well: - A possibility is to have a lot of servers acting as bulletin boards. The user sends his announcement message to all of the servers and the user waits until at some of the servers send back a guarantee to include the user. After some time, the servers agree on the pool of the users just by taking all the users that have registered with at least one of the servers. There are well-understood protocols to achieve this goal or similar goals, because essentially the same problem arises in e-voting (see http://arxiv.org/pdf/1401.4151 for just one example. this paper provides also a detai
[Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
es can start a new run of the protocol without the misbehaving participant. Also in case of passive disruption, i.e., some participant does not respond (for whatever reason), the remaining participants can agree on starting a new run without this participant. This ensures that the protocol will finally succeed even in the presence of malicious participant (although this can take quite a while then). - Only public-key encryption and signatures: The protocol requires only well-established cryptographic primitives. Besides signatures and hash functions (that are already used by Bitcoin), only standard public-key encryption is necessary. - Efficiency: A run of the protocol with 30 participants takes less than 100 seconds (in a setting with reasonable bandwidth and delay). This is not much, given that 10 min (on average) are required to confirm the mixing transaction anyway. The costs are almost completely caused by communication. The computation overhead is minimal. (This is the main achievement actually. In theory, it is clear that a protocol with all the properties can be built. However, generic constructions cannot be used in practice yet, because the computation and communication costs are huge.) - Compatibility: As CoinShuffle works on top of Bitcoin, it is fully compatible with the current Bitcoin system. No changes to the Bitcoin protocol are required. By the way: The NXT cryptocurrency picked up our idea and an implementation of CoinShuffle for a part of NXT is under way. ( https://twitter.com/comefrombeyond/status/485429369268350977 ) TL,DR: Mixing is the way to improve anonymity in Bitcoin now, as it does not require changes to the Bitcoin protocol. We propose CoinShuffle, a decentralized protocol to perform mixing in a secure way without trusted third parties, see http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/ for a technical overview. Our next step is to implement the protocol. Help in design and coding would be great but we also would like to hear your comments, criticism, and improvements for the protocol itself. Best, Tim Ruffing, Pedro Moreno-Sanchez, Aniket Kate signature.asc Description: This is a digitally signed message part. -- Infragistics Professional Build stunning WinForms apps today! Reboot your WinForms applications with our WinForms controls. Build a bridge from your legacy apps to the future. http://pubads.g.doubleclick.net/gampad/clk?id=153845071&iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
