Re: Bitcoin P2P e-cash paper
Satoshi Nakamoto wrote: When there are multiple double-spent versions of the same transaction, one and only one will become valid. That is not the question I am asking. It is not trust that worries me, it is how it is possible to have a a globally shared view even if everyone is well behaved. The process for arriving at a globally shared view of who owns what bitgold coins is insufficiently specified. Once specified, then we can start considering whether everyone has incentives to behave correctly. It is not sufficient that everyone knows X. We also need everyone to know that everyone knows X, and that everyone knows that everyone knows that everyone knows X - which, as in the Byzantine Generals problem, is the classic hard problem of distributed data processing. This problem becomes harder when X is quite possibly a very large amount of data - agreement on who was the owner of every bitgold coin at such and such a time. And then on top of that we need everyone to have a motive to behave in such a fashion that agreement arises. I cannot see that they have motive when I do not know the behavior to be motivated. You keep repeating your analysis of the system under attack. We cannot say how the system will behave under attack until we know how the system is supposed to behave when not under attack. If there are a lot of transactions, it is hard to efficiently discover the discrepancies between one node's view and another node's view, and because new transactions are always arriving, no two nodes will ever have the same view, even if all nodes are honest, and all reported transactions are correct and true single spends. We should be able to accomplish a system where two nodes are likely to come to agreement as to who owned what bitgold coins at some very recent past time, but it is not simple to do so. If one node constructs a hash that represents its knowledge of who owned what bitgold coins at a particular time, and another node wants to check that hash, it is not simple to do it in such a way that agreement is likely, and disagreement between honest well behaved nodes is efficiently detected and efficiently resolved. And if we had a specification of how agreement is generated, it is not obvious why the second node has incentive to check that hash. The system has to work in such a way that nodes can easily and cheaply change their opinion about recent transactions, so as to reach consensus, but in order to provide finality and irreversibility, once consensus has been reached, and then new stuff has be piled on top of old consensus, in particular new bitgold has been piled on top of old consensus, it then becomes extremely difficult to go back and change what was decided. Saying that is how it works, does not give us a method to make it work that way. The receiver of a payment must wait an hour or so before believing that it's valid. The network will resolve any possible double-spend races by then. You keep discussing attacks. I find it hard to think about response to attack when it is not clear to me what normal behavior is in the case of good conduct by each and every party. Distributed databases are *hard* even when all the databases perfectly follow the will of a single owner. Messages get lost, links drop, syncrhonization delays become abnormal, and entire machines go up in flames, and the network as a whole has to take all this in its stride. Figuring out how to do this is hard, even in the complete absence of attacks. Then when we have figured out how to handle all this, then come attacks. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Bitcoin P2P e-cash paper
James A. Donald writes: Satoshi Nakamoto wrote: When there are multiple double-spent versions of the same transaction, one and only one will become valid. That is not the question I am asking. It is not trust that worries me, it is how it is possible to have a a globally shared view even if everyone is well behaved. The process for arriving at a globally shared view of who owns what bitgold coins is insufficiently specified. I agree that the description is not completely clear on how these matters are handled. Satoshi has suggested that releasing source code may be the best way to clarify the design. As I have tried to work through details on my own, it does appear that the rules become rather complicated and indeed one needs at least a pseudo-code algorithm to specify the behavior. So perhaps writing real code is not a bad way to go. I found that there is a sourceforge project set up for bitgold, although it does not have any code yet. In answer to James' specific question, about what happens when different nodes see different sets of transactions, due to imperfect broadcast, here is how I understand it. Each node must be prepared to maintain potentially several candidate block chains, each of which may eventually turn out to become the longest one, the one which wins. Once a given block chain becomes sufficiently longer than a competitor, the shorter one can be deleted. This length differential is a parameter which depends on the node's threat model for how much compute power an attacker can marshall, in terms of the fraction of the honst P2P network's work capacity, and is estimated in the paper. The idea is that once a chain gets far enough behind the longest one, there is essentially no chance that it can ever catch up. In order to resolve the issue James raised, I think it is necessary that nodes keep a separate pending-transaction list associated with each candidate chain. This list would include all transactions the node has received (via broadcast by the transactees) but which have not yet been incorporated into that block chain. At any given time, the node is working to extend the longest block chain, and the block it is working to find a hash collision for will include all of the pending transactions associated with that chain. I think that this way, when a candidate chain is deleted because it got too much shorter than the longest one, transactions in it are not lost, but have continued to be present in the pending-transaction list associated with the longest chain, in those nodes which heard the original transaction broadcast. (I have also considered whether nodes should add transactions to their pending-transaction list that they learn about through blocks from other nodes, even if those blocks do not end up making their way into the longest block chain; but I'm not sure if that is necessary or helpful.) Once these rules are clarified, more formal modeling will be helpful in understanding the behavior of the network given imperfect reliability. For example, if on average a fraction f of P2P nodes receive a given transaction broadcast, then I think one would expect 1/f block-creation times to elapse before the transaction appears in what is destined to become the longest chain. One might also ask, given that the P2P network broadcast is itself imperfectly reliable, how many candidate chains must a given node keep track of at one time, on average? Or as James raised earlier, if the network broadcast is reliable but depends on a potentially slow flooding algorithm, how does that impact performance? And then on top of that we need everyone to have a motive to behave in such a fashion that agreement arises. I cannot see that they have motive when I do not know the behavior to be motivated. I am somewhat less worried about motivation. I'd be satisfied if the system can meet the following criteria: 1. No single node operator, or small collection of node operators which controls only a small fraction of overall network resources, can effectively cheat, if other players are honest. 2. The long tail of node operators is sufficiently large that no small collection of nodes can control more than a small fraction of overall resources. (Here, the tail refers to a ranking based on amount of resources controlled by each operator.) 3. The bitcoin system turns out to be socially useful and valuable, so that node operators feel that they are making a beneficial contribution to the world by their efforts (similar to the various @Home compute projects where people volunteer their compute resources for good causes). In this case it seems to me that simple altruism can suffice to keep the network running properly. Distributed databases are *hard* even when all the databases perfectly follow the will of a single owner. Messages get lost, links drop, syncrhonization delays become abnormal, and entire machines go up in flames, and the network as a whole has to take all this in
Re: Bitcoin P2P e-cash paper
James A. Donald wrote: It is not sufficient that everyone knows X. We also need everyone to know that everyone knows X, and that everyone knows that everyone knows that everyone knows X - which, as in the Byzantine Generals problem, is the classic hard problem of distributed data processing. The proof-of-work chain is a solution to the Byzantine Generals' Problem. I'll try to rephrase it in that context. A number of Byzantine Generals each have a computer and want to attack the King's wi-fi by brute forcing the password, which they've learned is a certain number of characters in length. Once they stimulate the network to generate a packet, they must crack the password within a limited time to break in and erase the logs, otherwise they will be discovered and get in trouble. They only have enough CPU power to crack it fast enough if a majority of them attack at the same time. They don't particularly care when the attack will be, just that they all agree. It has been decided that anyone who feels like it will announce a time, and whatever time is heard first will be the official attack time. The problem is that the network is not instantaneous, and if two generals announce different attack times at close to the same time, some may hear one first and others hear the other first. They use a proof-of-work chain to solve the problem. Once each general receives whatever attack time he hears first, he sets his computer to solve an extremely difficult proof-of-work problem that includes the attack time in its hash. The proof-of-work is so difficult, it's expected to take 10 minutes of them all working at once before one of them finds a solution. Once one of the generals finds a proof-of-work, he broadcasts it to the network, and everyone changes their current proof-of-work computation to include that proof-of-work in the hash they're working on. If anyone was working on a different attack time, they switch to this one, because its proof-of-work chain is now longer. After two hours, one attack time should be hashed by a chain of 12 proofs-of-work. Every general, just by verifying the difficulty of the proof-of-work chain, can estimate how much parallel CPU power per hour was expended on it and see that it must have required the majority of the computers to produce that much proof-of-work in the allotted time. They had to all have seen it because the proof-of-work is proof that they worked on it. If the CPU power exhibited by the proof-of-work chain is sufficient to crack the password, they can safely attack at the agreed time. The proof-of-work chain is how all the synchronisation, distributed database and global view problems you've asked about are solved. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
