pull down to refresh

0 sats \ 19 replies \ @BitcoinHistory OP 14 Nov 2023 freebie \ on: Bitcoin P2P e-cash paper | Satoshi Nakamoto satoshi at vistomail.com Fri Oct 31 bitcoin
Hal Finney https://www.metzdowd.com/pipermail/cryptography/2008-November/014827.html hal at finney.org Fri Nov 7 18:40:12 EST 2008 Previous message: NIST Special Publication 800-108 Recommendation for Key Derivation Using Pseudorandom Functions Next message: This is a test. This is only a test... Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] Bitcoin seems to be a very promising idea. I like the idea of basing security on the assumption that the CPU power of honest participants outweighs that of the attacker. It is a very modern notion that exploits the power of the long tail. When Wikipedia started I never thought it would work, but it has proven to be a great success for some of the same reasons.
I also do think that there is potential value in a form of unforgeable token whose production rate is predictable and can't be influenced by corrupt parties. This would be more analogous to gold than to fiat currencies. Nick Szabo wrote many years ago about what he called "bit gold"[1] and this could be an implementation of that concept. There have also been proposals for building light-weight anonymous payment schemes on top of heavy-weight non-anonymous systems, so Bitcoin could be leveraged to allow for anonymity even beyond the mechanisms discussed in the paper.
Unfortunately I am having trouble fully understanding the system. The paper describes key concepts and some data structures, but does not clearly specify the various rules and verifications that the participants in the system would have to follow.
In particular I don't understand exactly what verifications P2P nodes perform when they receive new blocks from other nodes, and how they handle transactions that have been broadcast to them. For example, it is mentioned that if a broadcast transaction does not reach all nodes, it is OK, as it will get into the block chain before long. How does this happen - what if the node that creates the "next" block (the first node to find the hashcash collision) did not hear about the transaction, and then a few more blocks get added also by nodes that did not hear about that transaction? Do all the nodes that did hear it keep that transaction around, hoping to incorporate it into a block once they get lucky enough to be the one which finds the next collision?
Or for example, what if a node is keeping two or more chains around as it waits to see which grows fastest, and a block comes in for chain A which would include a double-spend of a coin that is in chain B? Is that checked for or not? (This might happen if someone double-spent and two different sets of nodes heard about the two different transactions with the same coin.)
This kind of data management, and the rules for handling all the packets that are flowing around is largely missing from the paper.
I also don't understand exactly how double-spending, or cancelling transactions, is accomplished by a superior attacker who is able to muster more computing power than all the honest participants. I see that he can create new blocks and add them to create the longest chain, but how can he erase or add old transactions in the chain? As the attacker sends out his new blocks, aren't there consistency checks which honest nodes can perform, to make sure that nothing got erased? More explanation of this attack would be helpful, in order to judge the gains to an attacker from this, versus simply using his computing power to mint new coins honestly.
As far as the spending transactions, what checks does the recipient of a coin have to perform? Does she need to go back through the coin's entire history of transfers, and make sure that every transaction on the list is indeed linked into the "timestamp" block chain? Or can she just do the latest one? Do the timestamp nodes check transactions, making sure that the previous transaction on a coin is in the chain, thereby enforcing the rule that all transactions in the chain represent valid coins?
Sorry about all the questions, but as I said this does seem to be a very promising and original idea, and I am looking forward to seeing how the concept is further developed. It would be helpful to see a more process oriented description of the idea, with concrete details of the data structures for the various objects (coins, blocks, transactions), the data which is included in messages, and algorithmic descriptions of the procedures for handling the various events which would occur in this system. You mentioned that you are working on an implementation, but I think a more formal, text description of the system would be a helpful next step.
Hal Finney
[1] http://unenumerated.blogspot.com/2005/12/bit-gold.html
write
preview
0 sats \ 18 replies \ @BitcoinHistory OP 14 Nov 2023
Satoshi Nakamoto https://www.metzdowd.com/pipermail/cryptography/2008-November/014832.html satoshi at vistomail.com Sat Nov 8 20:58:48 EST 2008 Previous message: Bitcoin P2P e-cash paper Next message: Bitcoin P2P e-cash paper Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] Hal Finney wrote:
it is mentioned that if a broadcast transaction does not reach all nodes, it is OK, as it will get into the block chain before long. How does this happen - what if the node that creates the "next" block (the first node to find the hashcash collision) did not hear about the transaction, and then a few more blocks get added also by nodes that did not hear about that transaction? Do all the nodes that did hear it keep that transaction around, hoping to incorporate it into a block once they get lucky enough to be the one which finds the next collision?
Right, nodes keep transactions in their working set until they get into a block. If a transaction reaches 90% of nodes, then each time a new block is found, it has a 90% chance of being in it.
Or for example, what if a node is keeping two or more chains around as it waits to see which grows fastest, and a block comes in for chain A which would include a double-spend of a coin that is in chain B? Is that checked for or not? (This might happen if someone double-spent and two different sets of nodes heard about the two different transactions with the same coin.)
That does not need to be checked for. The transaction in whichever branch ends up getting ahead becomes the valid one, the other is invalid. If someone tries to double spend like that, one and only one spend will always become valid, the others invalid.
Receivers of transactions will normally need to hold transactions for perhaps an hour or more to allow time for this kind of possibility to be resolved. They can still re-spend the coins immediately, but they should wait before taking an action such as shipping goods.
I also don't understand exactly how double-spending, or cancelling transactions, is accomplished by a superior attacker who is able to muster more computing power than all the honest participants. I see that he can create new blocks and add them to create the longest chain, but how can he erase or add old transactions in the chain? As the attacker sends out his new blocks, aren't there consistency checks which honest nodes can perform, to make sure that nothing got erased? More explanation of this attack would be helpful, in order to judge the gains to an attacker from this, versus simply using his computing power to mint new coins honestly.
The attacker isn't adding blocks to the end. He has to go back and redo the block his transaction is in and all the blocks after it, as well as any new blocks the network keeps adding to the end while he's doing that. He's rewriting history. Once his branch is longer, it becomes the new valid one.
This touches on a key point. Even though everyone present may see the shenanigans going on, there's no way to take advantage of that fact.
It is strictly necessary that the longest chain is always considered the valid one. Nodes that were present may remember that one branch was there first and got replaced by another, but there would be no way for them to convince those who were not present of this. We can't have subfactions of nodes that cling to one branch that they think was first, others that saw another branch first, and others that joined later and never saw what happened. The CPU power proof-of-work vote must have the final say. The only way for everyone to stay on the same page is to believe that the longest chain is always the valid one, no matter what.
As far as the spending transactions, what checks does the recipient of a coin have to perform? Does she need to go back through the coin's entire history of transfers, and make sure that every transaction on the list is indeed linked into the "timestamp" block chain? Or can she just do the latest one?
The recipient just needs to verify it back to a depth that is sufficiently far back in the block chain, which will often only require a depth of 2 transactions. All transactions before that can be discarded.
Do the timestamp nodes check transactions, making sure that the previous transaction on a coin is in the chain, thereby enforcing the rule that all transactions in the chain represent valid coins?
Right, exactly. When a node receives a block, it checks the signatures of every transaction in it against previous transactions in blocks. Blocks can only contain transactions that depend on valid transactions in previous blocks or the same block. Transaction C could depend on transaction B in the same block and B depends on transaction A in an earlier block.
Sorry about all the questions, but as I said this does seem to be a very promising and original idea, and I am looking forward to seeing how the concept is further developed. It would be helpful to see a more process oriented description of the idea, with concrete details of the data structures for the various objects (coins, blocks, transactions), the data which is included in messages, and algorithmic descriptions of the procedures for handling the various events which would occur in this system. You mentioned that you are working on an implementation, but I think a more formal, text description of the system would be a helpful next step.
I appreciate your questions. I actually did this kind of backwards. I had to write all the code before I could convince myself that I could solve every problem, then I wrote the paper. I think I will be able to release the code sooner than I could write a detailed spec. You're already right about most of your assumptions where you filled in the blanks.
Satoshi Nakamoto
reply
0 sats \ 17 replies \ @BitcoinHistory OP 14 Nov 2023
Satoshi Nakamoto https://www.metzdowd.com/pipermail/cryptography/2008-November/014833.html satoshi at vistomail.com Sat Nov 8 22:09:49 EST 2008 Previous message: Bitcoin P2P e-cash paper Next message: Bitcoin P2P e-cash paper Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] James A. Donald wrote:
The core concept is that lots of entities keep complete and consistent information as to who owns which bitcoins.
But maintaining consistency is tricky. It is not clear to me what happens when someone reports one transaction to one maintainer, and someone else transports another transaction to another maintainer. The transaction cannot be known to be valid until it has been incorporated into a globally shared view of all past transactions, and no one can know that a globally shared view of all past transactions is globally shared until after some time has passed, and after many new transactions have arrived.
Did you explain how to do this, and it just passed over my head, or were you confident it could be done, and a bit vague as to the details?
The proof-of-work chain is the solution to the synchronisation problem, and to knowing what the globally shared view is without having to trust anyone.
A transaction will quickly propagate throughout the network, so if two versions of the same transaction were reported at close to the same time, the one with the head start would have a big advantage in reaching many more nodes first. Nodes will only accept the first one they see, refusing the second one to arrive, so the earlier transaction would have many more nodes working on incorporating it into the next proof-of-work. In effect, each node votes for its viewpoint of which transaction it saw first by including it in its proof-of-work effort.
If the transactions did come at exactly the same time and there was an even split, it's a toss up based on which gets into a proof-of-work first, and that decides which is valid.
When a node finds a proof-of-work, the new block is propagated throughout the network and everyone adds it to the chain and starts working on the next block after it. Any nodes that had the other transaction will stop trying to include it in a block, since it's now invalid according to the accepted chain.
The proof-of-work chain is itself self-evident proof that it came from the globally shared view. Only the majority of the network together has enough CPU power to generate such a difficult chain of proof-of-work. Any user, upon receiving the proof-of-work chain, can see what the majority of the network has approved. Once a transaction is hashed into a link that's a few links back in the chain, it is firmly etched into the global history.
Satoshi Nakamoto
NOTE: This reply by satoshi quote an email that may have been rpivatly sent to Satoshi by James, since this source email by James is no where to be found on the cryptography mailing list. We assume this reply by James is in reply to Satoshi's reply to Hal, since it fits the conversation flow being had at the time very closely, and more than to any other conversation tangent at the time. This reply also comes right after the hal finney reply, so its very likely in the correct order as seen here on stacker.news.
reply
0 sats \ 16 replies \ @BitcoinHistory OP 14 Nov 2023
James A. Donald https://www.metzdowd.com/pipermail/cryptography/2008-November/014835.html jamesd at echeque.com Sun Nov 9 03:56:53 EST 2008 Previous message: Bitcoin P2P e-cash paper Next message: Bitcoin P2P e-cash paper Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] -- Satoshi Nakamoto wrote:
The proof-of-work chain is the solution to the synchronisation problem, and to knowing what the globally shared view is without having to trust anyone.
A transaction will quickly propagate throughout the network, so if two versions of the same transaction were reported at close to the same time, the one with the head start would have a big advantage in reaching many more nodes first. Nodes will only accept the first one they see, refusing the second one to arrive, so the earlier transaction would have many more nodes working on incorporating it into the next proof-of-work. In effect, each node votes for its viewpoint of which transaction it saw first by including it in its proof-of-work effort.
OK, suppose one node incorporates a bunch of transactions in its proof of work, all of them honest legitimate single spends and another node incorporates a slightly different bunch of transactions in its proof of work, all of them equally honest legitimate single spends, and both proofs are generated at about the same time.
What happens then?
reply
0 sats \ 15 replies \ @BitcoinHistory OP 14 Nov 2023
Satoshi Nakamoto https://www.metzdowd.com/pipermail/cryptography/2008-November/014838.html satoshi at vistomail.com Sun Nov 9 11:31:26 EST 2008 Previous message: Bitcoin P2P e-cash paper Next message: Bitcoin P2P e-cash paper Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] James A. Donald wrote:
OK, suppose one node incorporates a bunch of transactions in its proof of work, all of them honest legitimate single spends and another node incorporates a different bunch of transactions in its proof of work, all of them equally honest legitimate single spends, and both proofs are generated at about the same time.
What happens then?
They both broadcast their blocks. All nodes receive them and keep both, but only work on the one they received first. We'll suppose exactly half received one first, half the other.
In a short time, all the transactions will finish propagating so that everyone has the full set. The nodes working on each side will be trying to add the transactions that are missing from their side. When the next proof-of-work is found, whichever previous block that node was working on, that branch becomes longer and the tie is broken. Whichever side it is, the new block will contain the other half of the transactions, so in either case, the branch will contain all transactions. Even in the unlikely event that a split happened twice in a row, both sides of the second split would contain the full set of transactions anyway.
It's not a problem if transactions have to wait one or a few extra cycles to get into a block.
Satoshi Nakamoto
reply
0 sats \ 14 replies \ @BitcoinHistory OP 14 Nov 2023
James A. Donald https://www.metzdowd.com/pipermail/cryptography/2008-November/014841.html jamesd at echeque.com Sun Nov 9 14:57:54 EST 2008 Previous message: Bitcoin P2P e-cash paper Next message: Bitcoin P2P e-cash paper Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] --
James A. Donald wrote:
OK, suppose one node incorporates a bunch of transactions in its proof of work, all of them honest legitimate single spends and another node incorporates a different bunch of transactions in its proof of work, all of them equally honest legitimate single spends, and both proofs are generated at about the same time.
What happens then?
Satoshi Nakamoto wrote:
They both broadcast their blocks. All nodes receive them and keep both, but only work on the one they received first. We'll suppose exactly half received one first, half the other.
In a short time, all the transactions will finish propagating so that everyone has the full set. The nodes working on each side will be trying to add the transactions that are missing from their side. When the next proof-of-work is found, whichever previous block that node was working on, that branch becomes longer and the tie is broken. Whichever side it is, the new block will contain the other half of the transactions, so in either case, the branch will contain all transactions. Even in the unlikely event that a split happened twice in a row, both sides of the second split would contain the full set of transactions anyway.
It's not a problem if transactions have to wait one or a few extra cycles to get into a block.
So what happened to the coin that lost the race?
On the one hand, we want people who make coins to be motivated to keep and record all transactions, and obtain an up to date record of all transactions in a timely manner. On the other hand, it is a bit harsh if the guy who came second is likely to lose his coin.
Further, your description of events implies restrictions on timing and coin generation - that the entire network generates coins slowly compared to the time required for news of a new coin to flood the network, otherwise the chains diverge more and more, and no one ever knows which chain is the winner.
You need to make these restrictions explicit, for network flood time may well be quite slow.
Which implies that the new coin rate is slower.
We want spenders to have certainty that their transaction is valid at the time it takes a spend to flood the network, not at the time it takes for branch races to be resolved.
At any given time, for example at 1 040 689 138 seconds we can look back at the past and say:
At 1 040 688 737 seconds, node 5 was *it*, and
he incorporated all the coins he had discovered
into the chain, and all the new transactions he
knew about on top of the previous link

At 1 040 688 792 seconds, node 2 was *it*, and
he incorporated all the coins he had discovered
into the chain, and all the new transactions he
knew about into the chain on top of node 5's
link.

At 1 040 688 745 seconds, node 7 was *it*, and
he incorporated all the coins he had discovered
into the chain, and all the new transactions he
knew about into the chain on top of node 2's
link.
But no one can know who is it right now
So how does one know when to reveal one's coins? One solution is that one does not. One incorporates a hash of the coin secret whenever one thinks one might be it, and after that hash is securely in the chain, after one knows that one was it at the time, one can then safely spend the coin that one has found, revealing the secret.
This solution takes care of the coin revelation problem, but does not solve the spend recording problem. If one node is ignoring all spends that it does not care about, it suffers no adverse consequences. We need a protocol in which your prospects of becoming it also depend on being seen by other nodes as having a reasonably up to date and complete list of spends - which this protocol is not, and your protocol is not either.
reply
0 sats \ 13 replies \ @BitcoinHistory OP 14 Nov 2023
Satoshi Nakamoto https://www.metzdowd.com/pipermail/cryptography/2008-November/014843.html satoshi at vistomail.com Mon Nov 10 17:18:20 EST 2008 Previous message: Bitcoin P2P e-cash paper Next message: Bitcoin P2P e-cash paper Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] James A. Donald wrote:
So what happened to the coin that lost the race?
... it is a bit harsh if the guy who came second is likely to lose his coin.
When there are multiple double-spent versions of the same transaction, one and only one will become valid.
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.
The guy who received the double-spend that became invalid never thought he had it in the first place. His software would have shown the transaction go from "unconfirmed" to "invalid". If necessary, the UI can be made to hide transactions until they're sufficiently deep in the block chain.
Further, your description of events implies restrictions on timing and coin generation - that the entire network generates coins slowly compared to the time required for news of a new coin to flood the network
Sorry if I didn't make that clear. The target time between blocks will probably be 10 minutes.
Every block includes its creation time. If the time is off by more than 36 hours, other nodes won't work on it. If the timespan over the last 62430 blocks is less than 15 days, blocks are being generated too fast and the proof-of-work difficulty doubles. Everyone does the same calculation with the same chain data, so they all get the same result at the same link in the chain.
We want spenders to have certainty that their transaction is valid at the time it takes a spend to flood the network, not at the time it takes for branch races to be resolved.
Instantant non-repudiability is not a feature, but it's still much faster than existing systems. Paper cheques can bounce up to a week or two later. Credit card transactions can be contested up to 60 to 180 days later. Bitcoin transactions can be sufficiently irreversible in an hour or two.
If one node is ignoring all spends that it does not care about, it suffers no adverse consequences.
With the transaction fee based incentive system I recently posted, nodes would have an incentive to include all the paying transactions they receive.
Satoshi Nakamoto
reply
0 sats \ 12 replies \ @BitcoinHistory OP 14 Nov 2023
James A. Donald https://www.metzdowd.com/pipermail/cryptography/2008-November/014847.html jamesd at echeque.com Thu Nov 13 01:16:31 EST 2008 Previous message: Bitcoin P2P e-cash paper Next message: Fwd: [Announce] Introducing Tor VM – Tor in a virtual machine. Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] 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.
reply
0 sats \ 7 replies \ @BitcoinHistory OP 14 Nov 2023
Satoshi Nakamoto https://www.metzdowd.com/pipermail/cryptography/2008-November/014849.html satoshi at vistomail.com Thu Nov 13 17:56:55 EST 2008 Previous message: Bitcoin P2P e-cash paper Next message: WSJ Story on NSA history Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] 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.
view replies
0 sats \ 3 replies \ @BitcoinHistory OP 14 Nov 2023
Hal Finney https://www.metzdowd.com/pipermail/cryptography/2008-November/014848.html hal at finney.org Thu Nov 13 11:24:18 EST 2008 Previous message: Comment Period for FIPS 186-3: Digital Signature Standard Next message: Bitcoin P2P e-cash paper Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] 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 its stride.
A very good point, and a more complete specification is necessary in order to understand how the network will respond to imperfections like this. I am looking forward to seeing more detail emerge.
One thing I might mention is that in many ways bitcoin is two independent ideas: a way of solving the kinds of problems James lists here, of creating a globally consistent but decentralized database; and then using it for a system similar to Wei Dai's b-money (which is referenced in the paper) but transaction/coin based rather than account based. Solving the global, massively decentralized database problem is arguably the harder part, as James emphasizes. The use of proof-of-work as a tool for this purpose is a novel idea well worth further review IMO.
Hal Finney
view replies