pull down to refresh

0 sats \ 16 replies \ @BitcoinHistory OP 14 Nov 2023 \ parent \ on: Bitcoin P2P e-cash paper | Satoshi Nakamoto satoshi at vistomail.com Fri Oct 31 bitcoin
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?
write
preview
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.
reply
0 sats \ 6 replies \ @BitcoinHistory OP 14 Nov 2023
Ray Dillinger https://www.metzdowd.com/pipermail/cryptography/2008-November/014857.html bear at sonic.net Fri Nov 14 21:20:23 EST 2008 Previous message: NSA history Next message: Bitcoin P2P e-cash paper Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] Okay.... I'm going to summarize this protocol as I understand it.
I'm filling in some operational details that aren't in the paper by supplementing what you wrote with what my own "design sense" tells me are critical missing bits or "obvious" methodologies for use.
First, people spend computer power creating a pool of coins to use as money. Each coin is a proof-of-work meeting whatever criteria were in effect for money at the time it was created. The time of creation (and therefore the criteria) is checkable later because people can see the emergence of this particular coin in the transaction chain and track it through all its "consensus view" spends. (more later on coin creation tied to adding a link).
When a coin is spent, the buyer and seller digitally sign a (blinded) transaction record, and broadcast it to a bunch of nodes whose purpose is keeping track of consensus regarding coin ownership. If someone double spends, then the transaction record can be unblinded revealing the identity of the cheater. This is done via a fairly standard cut- and-choose algorithm where the buyer responds to several challenges with secret shares, and the seller then asks him to "unblind" and checks all but one, verifying that they do contain secret shares any two of which are sufficient to identify the buyer. In this case the seller accepts the unblinded spend record as "probably" containing a valid secret share.
The nodes keeping track of consensus regarding coin ownership are in a loop where they are all trying to "add a link" to the longest chain they've so far recieved. They have a pool of reported transactions which they've not yet seen in a "consensus" signed chain. I'm going to call this pool "A". They attempt to add a link to the chain by moving everything from pool A into a pool "L" and using a CPU- intensive digital signature algorithm to sign the chain including the new block L. This results in a chain extended by a block containing all the transaction records they had in pool L, plus the node's digital signature. While they do this, new transaction records continue to arrive and go into pool A again for the next cycle of work.
They may also recieve chains as long as the one they're trying to extend while they work, in which the last few "links" are links that are not in common with the chain on which they're working. These they ignore. (? Do they ignore them? Under what circumstances would these become necessary to ever look at again, bearing in mind that any longer chain based on them will include them?)
But if they recieve a longer chain while working, they immediately check all the transactions in the new links to make sure it contains no double spends and that the "work factors" of all new links are appropriate. If it contains a double spend, then they create a "transaction" which is a proof of double spending, add it to their pool A, broadcast it, and continue work.
If one of the "new" links has an inappropriate work factor (ie, someone didn't put enough CPU into it for it to be "licit" according to the rules) a new "transaction" which is a proof of the protocol violation by the link-creating node is created, broadcast, and added to pool A, and the chain is rejected. In the case of no double spends and appropriate work factors for all links not yet seen, they accept the new chain as consensus.
If the new chain is accepted, then they give up on adding their current link, dump all the transactions from pool L back into pool A (along with transactions they've recieved or created since starting work), eliminate from pool A those transaction records which are already part of a link in the new chain, and start work again trying to extend the new chain.
If they complete work on a chain extended with their new link, they broadcast it and immediately start work on another new link with all the transactions that have accumulated in pool A since they began work.
Do I understand it correctly?
Biggest Technical Problem:
Is there a mechanism to make sure that the "chain" does not consist solely of links added by just the 3 or 4 fastest nodes? 'Cause a broadcast transaction record could easily miss those 3 or 4 nodes and if it does, and those nodes continue to dominate the chain, the transaction might never get added.
To remedy this, you need to either ensure provable propagation of transactions, or vary the work factor for a node depending on how many links have been added since that node's most recent link.
Unfortunately, both measures can be defeated by sock puppets.
This is probably the worst problem with your protocol as it stands right now; you need some central point to control the identities (keys) of the nodes and prevent people from making new sock puppets.
Provable propagation would mean that When Bob accepts a new chain from Alice, he needs to make sure that Alice has (or gets) all transactions in his "A" and "L" pools. He sends them, and Alice sends back a signed hash to prove she got them. Once Alice has recieved this block of transactions, if any subsequent chains including a link added by Alice do not include those transactions at or before that link, then Bob should be able to publish the block he sent Alice, along with her signature, in a transaction as proof that Alice violated protocol. Sock puppets defeat this because Alice just signs subsequent chains using a new key, pretending to be a different node.
If we go with varying the work factor depending on how many new links there are, then we're right back to domination by the 3 or 4 fastest nodes, except now they're joined by 600 or so sock puppets which they use to avoid the work factor penalty.
If we solve the sock-puppet issue, or accept that there's a central point controlling the generation of new keys, then generation of coins should be tied to the act of successfully adding a block to the "consensus" chain. This is simple to do; creation of a coin is a transaction, it gets added along with all the other transactions in the block. But you can only create one coin per link, and of course if your version of the chain isn't the one that gets accepted, then in the "accepted" view you don't have the coin and can't spend it. This gives the people maintaining the consensus database a reason to spend CPU cycles, especially since the variance in work factor by number of links added since their own last link (outlined above) guarantees that everyone, not just the 3 or 4 fastest nodes, occasionally gets the opportunity to create a coin.
Also, the work requirement for adding a link to the chain should vary (again exponentially) with the number of links added to that chain in the previous week, causing the rate of coin generation (and therefore inflation) to be strictly controlled.
You need coin aggregation for this to scale. There needs to be a "provable" transaction where someone retires ten single coins and creates a new coin with denomination ten, etc. This is not too hard, using the same infrastructure you've already got; it simply becomes part of the chain, and when the chain is accepted consensus, then everybody can see that it happened.
			Bear
reply
0 sats \ 4 replies \ @BitcoinHistory OP 14 Nov 2023
Satoshi Nakamoto https://www.metzdowd.com/pipermail/cryptography/2008-November/014858.html satoshi at vistomail.com Fri Nov 14 23:43:00 EST 2008 Previous message: Bitcoin P2P e-cash paper Next message: Bitcoin P2P e-cash paper Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] I'll try and hurry up and release the sourcecode as soon as possible to serve as a reference to help clear up all these implementation questions.
Ray Dillinger (Bear) wrote:
When a coin is spent, the buyer and seller digitally sign a (blinded) transaction record.
Only the buyer signs, and there's no blinding.
If someone double spends, then the transaction record can be unblinded revealing the identity of the cheater.
Identities are not used, and there's no reliance on recourse. It's all prevention.
This is done via a fairly standard cut-and-choose algorithm where the buyer responds to several challenges with secret shares
No challenges or secret shares. A basic transaction is just what you see in the figure in section 2. A signature (of the buyer) satisfying the public key of the previous transaction, and a new public key (of the seller) that must be satisfied to spend it the next time.
They may also receive chains as long as the one they're trying to extend while they work, in which the last few "links" are links that are not in common with the chain on which they're working. These they ignore.
Right, if it's equal in length, ties are broken by keeping the earliest one received.
If it contains a double spend, then they create a "transaction" which is a proof of double spending, add it to their pool A, broadcast it, and continue work.
There's no need for reporting of "proof of double spending" like that. If the same chain contains both spends, then the block is invalid and rejected.
Same if a block didn't have enough proof-of-work. That block is invalid and rejected. There's no need to circulate a report about it. Every node could see that and reject it before relaying it.
If there are two competing chains, each containing a different version of the same transaction, with one trying to give money to one person and the other trying to give the same money to someone else, resolving which of the spends is valid is what the whole proof-of-work chain is about.
We're not "on the lookout" for double spends to sound the alarm and catch the cheater. We merely adjudicate which one of the spends is valid. Receivers of transactions must wait a few blocks to make sure that resolution has had time to complete. Would be cheaters can try and simultaneously double-spend all they want, and all they accomplish is that within a few blocks, one of the spends becomes valid and the others become invalid. Any later double-spends are immediately rejected once there's already a spend in the main chain.
Even if an earlier spend wasn't in the chain yet, if it was already in all the nodes' pools, then the second spend would be turned away by all those nodes that already have the first spend.
If the new chain is accepted, then they give up on adding their current link, dump all the transactions from pool L back into pool A (along with transactions they've received or created since starting work), eliminate from pool A those transaction records which are already part of a link in the new chain, and start work again trying to extend the new chain.
Right. They also refresh whenever a new transaction comes in, so L pretty much contains everything in A all the time.
CPU-intensive digital signature algorithm to sign the chain including the new block L.
It's a Hashcash style SHA-256 proof-of-work (partial pre-image of zero), not a signature.
Is there a mechanism to make sure that the "chain" does not consist solely of links added by just the 3 or 4 fastest nodes? 'Cause a broadcast transaction record could easily miss those 3 or 4 nodes and if it does, and those nodes continue to dominate the chain, the transaction might never get added.
If you're thinking of it as a CPU-intensive digital signing, then you may be thinking of a race to finish a long operation first and the fastest always winning.
The proof-of-work is a Hashcash style SHA-256 collision finding. It's a memoryless process where you do millions of hashes a second, with a small chance of finding one each time. The 3 or 4 fastest nodes' dominance would only be proportional to their share of the total CPU power. Anyone's chance of finding a solution at any time is proportional to their CPU power.
There will be transaction fees, so nodes will have an incentive to receive and include all the transactions they can. Nodes will eventually be compensated by transaction fees alone when the total coins created hits the pre-determined ceiling.
Also, the work requirement for adding a link to the chain should vary (again exponentially) with the number of links added to that chain in the previous week, causing the rate of coin generation (and therefore inflation) to be strictly controlled.
Right.
You need coin aggregation for this to scale. There needs to be a "provable" transaction where someone retires ten single coins and creates a new coin with denomination ten, etc.
Every transaction is one of these. Section 9, Combining and Splitting Value.
Satoshi Nakamoto
reply
0 sats \ 3 replies \ @BitcoinHistory OP 14 Nov 2023
Ray Dillinger https://www.metzdowd.com/pipermail/cryptography/2008-November/014859.html bear at sonic.net Sat Nov 15 02:04:21 EST 2008 Previous message: Bitcoin P2P e-cash paper Next message: Bitcoin P2P e-cash paper Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] On Sat, 2008-11-15 at 12:43 +0800, Satoshi Nakamoto wrote:
I'll try and hurry up and release the sourcecode as soon as possible to serve as a reference to help clear up all these implementation questions.
Ray Dillinger (Bear) wrote:
When a coin is spent, the buyer and seller digitally sign a (blinded) transaction record.
Only the buyer signs, and there's no blinding.
If someone double spends, then the transaction record can be unblinded revealing the identity of the cheater.
Identities are not used, and there's no reliance on recourse. It's all prevention.
Okay, that's surprising. If you're not using buyer/seller identities, then you are not checking that a spend is being made by someone who actually is the owner of (on record as having recieved) the coin being spent.
There are three categories of identity that are useful to think about. Category one: public. Real-world identities are a matter of record and attached to every transaction.
Category two: Pseudonymous. There are persistent "identities" within the system and people can see if something was done by the same nym that did something else, but there's not necessarily any way of linking the nyms with real-world identities. Category three: unlinkably anonymous. There is no concept of identity, persistent or otherwise. No one can say or prove whether the agents involved in any transaction are the same agents as involved in any other transaction.
Are you claiming category 3 as you seem to be, or category 2? Lots of people don't distinguish between anonymous and pseudonymous protocols, so it's worth asking exactly what you mean here.
Anyway: I'll proceed on the assumption that you meant very nearly (as nearly as I can imagine, anyway) what you said, unlinkably anonymous. That means that instead of an "identity", a spender has to demonstrate knowledge of a secret known only to the real owner of the coin. One way to do this would be to have the person recieving the coin generate an asymmetric key pair, and then have half of it published with the transaction. In order to spend the coin later, s/he must demonstrate posession of the other half of the asymmetric key pair, probably by using it to sign the key provided by the new seller. So we cannot prove anything about "identity", but we can prove that the spender of the coin is someone who knows a secret that the person who recieved the coin knows.
And what you say next seems to confirm this:
No challenges or secret shares. A basic transaction is just what you see in the figure in section 2. A signature (of the buyer) satisfying the public key of the previous transaction, and a new public key (of the seller) that must be satisfied to spend it the next time.
Note, even though this doesn't involve identity per se, it still makes the agent doing the spend linkable to the agent who earlier recieved the coin, so these transactions are linkable.
In order to counteract this, the owner of the coin needs to make a transaction, indistinguishable to others from any normal transaction, in which he creates a new key pair and transfers the coin to its posessor (ie, has one sock puppet "spend" it to another). No change in real-world identity of the owner, but the transaction "linkable" to the agent who spent the coin is unlinked. For category-three unlinkability, this has to be done a random number of times - maybe one to six times?
BTW, could you please learn to use carriage returns?? Your lines are scrolling stupidly off to the right and I have to scroll to see what the heck you're saying, then edit to add carriage returns before I respond.
If it contains a double spend, then they create a "transaction" which is a proof of double spending, add it to their pool A, broadcast it, and continue work.
There's no need for reporting of "proof of double spending" like that. If the same chain contains both spends, then the block is invalid and rejected.
Same if a block didn't have enough proof-of-work. That block is invalid and rejected. There's no need to circulate a report about it. Every node could see that and reject it before relaying it.
Mmmm. I don't know if I'm comfortable with that. You're saying there's no effort to identify and exclude nodes that don't cooperate? I suspect this will lead to trouble and possible DOS attacks.
If there are two competing chains, each containing a different version of the same transaction, with one trying to give money to one person and the other trying to give the same money to someone else, resolving which of the spends is valid is what the whole proof-of-work chain is about.
Okay, when you say "same" transaction, and you're talking about transactions that are obviously different, you mean a double spend, right? Two transactions signed with the same key?
We're not "on the lookout" for double spends to sound the alarm and catch the cheater. We merely adjudicate which one of the spends is valid. Receivers of transactions must wait a few blocks to make sure that resolution has had time to complete.
Until.... until what? How does anybody know when a transaction has become irrevocable? Is "a few" blocks three? Thirty? A hundred? Does it depend on the number of nodes? Is it logarithmic or linear in number of nodes?
Would be cheaters can try and simultaneously double-spend all they want, and all they accomplish is that within a few blocks, one of the spends becomes valid and the others become invalid.
But in the absence of identity, there's no downside to them if spends become invalid, if they've already recieved the goods they double-spent for (access to website, download, whatever). The merchants are left holding the bag with "invalid" coins, unless they wait that magical "few blocks" (and how can they know how many?) before treating the spender as having paid.
The consumers won't do this if they spend their coin and it takes an hour to clear before they can do what they spent their coin on. The merchants won't do it if there's no way to charge back a customer when they find the that their coin is invalid because the customer has doublespent.
Even if an earlier spend wasn't in the chain yet, if it was already in all the nodes' pools, then the second spend would be turned away by all those nodes that already have the first spend.
So there's a possibility of an early catch when the broadcasts of the initial simultaneous spends interfere with each other. I assume here that the broadcasts are done by the sellers, since the buyer has a possible disincentive to broadly disseminate spends.
If the new chain is accepted, then they give up on adding their current link ... and start work again trying to extend the new chain.
Right. They also refresh whenever a new transaction comes in, so L pretty much contains everything in A all the time.
Okay, that's a big difference between a proof of work that takes a huge set number of CPU cycles and a proof of work that takes a tiny number of CPU cycles but has a tiny chance of success. You can change the data set while working, and it doesn't mean you need to start over. This is good in this case, as it means nobody has to hold recently recieved transactions out of the link they're working on.
Is there a mechanism to make sure that the "chain" does not consist solely of links added by just the 3 or 4 fastest nodes?
If you're thinking of it as a CPU-intensive digital signing, then you may be thinking of a race to finish a long operation first and the fastest always winning.
Right. That was the misconception I was working with. Again, the difference between a proof taking a huge set number of CPU cycles and a proof that takes a tiny number of CPU cycles but has a tiny chance of success.
Anyone's chance of finding a solution at any time is proportional to their CPU power.
It's like a random variation in the work factor; in this way it works in your favor.
There will be transaction fees, so nodes will have an incentive to receive and include all the transactions they can. Nodes will eventually be compensated by transaction fees alone when the total coins created hits the pre-determined ceiling.
I don't understand how "transaction fees" would work, and how the money would find its way from the agents doing transactions to those running the network. But the economic effect is the same (albeit somewhat randomized) if adding a link to the chain allows the node to create a coin, so I would stick with that.
Also, be aware that the compute power of different nodes can be expected to vary by two orders of magnitude at any given moment in history.
			Bear
view replies
0 sats \ 0 replies \ @BitcoinHistory OP 14 Nov 2023
James A. Donald https://www.metzdowd.com/pipermail/cryptography/2008-November/014865.html jamesd at echeque.com Mon Nov 17 18:57:39 EST 2008 Previous message: Bitcoin P2P e-cash paper Next message: unintended? Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] Ray Dillinger wrote:
Okay.... I'm going to summarize this protocol as I understand it.
I'm filling in some operational details that aren't in the paper by supplementing what you wrote with what my own "design sense" tells me are critical missing bits or "obvious" methodologies for use.
There are a number of significantly different ways this could be implemented. I have been working on my own version based on Patricia hash trees, (not yet ready to post, will post in a week or so) with the consensus generation being a generalization of file sharing using Merkle hash trees. Patricia hash trees where the high order part of the Patricia key represents the high order part of the time can be used to share data that evolves in time. The algorithm, if implemented by honest correctly functioning peers, regularly generates consensus hashes of the recent past - thereby addressing the problem I have been complaining about - that we have a mechanism to protect against consensus distortion by dishonest or malfunctioning peers, which is useless absent a definition of consensus generation by honest and correctly functioning peers.
First, people spend computer power creating a pool of coins to use as money. Each coin is a proof-of-work meeting whatever criteria were in effect for money at the time it was created. The time of creation (and therefore the criteria) is checkable later because people can see the emergence of this particular coin in the transaction chain and track it through all its "consensus view" spends. (more later on coin creation tied to adding a link).
When a coin is spent, the buyer and seller digitally sign a (blinded) transaction record, and broadcast it to a bunch of nodes whose purpose is keeping track of consensus regarding coin ownership.
I don't think your blinding works.
If there is a public record of who owns what coin, we have to generate a public diff on changes in that record, so the record will show that a coin belonged to X, and soon thereafter belonged to Y. I don't think blinding can be made to work. We can blind the transaction details easily enough, by only making hashes of the details public, (X paid Y for 49vR7xmwYcKXt9zwPJ943h9bHKC2pG68m) but that X paid Y is going to be fairly obvious.
If when Joe spends a coin to me, then I have to have the ability to ask "Does Joe rightfully own this coin", then it is difficult to see how this can be implemented in a distributed protocol without giving people the ability to trawl through data detecting that Joe paid me.
To maintain a consensus on who owns what coins, who owns what coins has to be public.
We can build a privacy layer on top of this - account money and chaumian money based on bitgold coins, much as the pre 1915 US banking system layered account money and bank notes on top of gold coins, and indeed we have to build a layer on top to bring the transaction cost down to the level that supports agents performing micro transactions, as needed for bandwidth control, file sharing, and charging non white listed people to send us communications.
So the entities on the public record are entities functioning like pre 1915 banks - let us call them binks, for post 1934 banks no longer function like that.
But if they recieve a longer chain while working, they immediately check all the transactions in the new links to make sure it contains no double spends and that the "work factors" of all new links are appropriate.
I am troubled that this involves frequent retransmissions of data that is already mostly known. Consensus and widely distributed beliefs about bitgold ownership already involves significant cost. Further, each transmission of data is subject to data loss, which can result in thrashing, with the risk that the generation of consensus may slow below the rate of new transactions. We already have problems getting the cost down to levels that support micro transactions by software agents, which is the big unserved market - bandwidth control, file sharing, and charging non white listed people to send us communications.
To work as useful project, has to be as efficient as it can be - hence my plan to use a Patricia hash tree because it identifies and locate small discrepancies between peers that are mostly in agreement already, without them needing to transmit their complete data.
We also want to avoid very long hash chains that have to be frequently checked in order to validate things. Any time a hash chain can potentially become enormously long over time, we need to ensure that no one ever has to rewalk the full length. Chains that need to be re-walked can only be permitted to grow as the log of the total number of transactions - if they grow as the log of the transactions in any one time period plus the total number of time periods, we have a problem.
Biggest Technical Problem:
Is there a mechanism to make sure that the "chain" does not consist solely of links added by just the 3 or 4 fastest nodes? 'Cause a broadcast transaction record could easily miss those 3 or 4 nodes and if it does, and those nodes continue to dominate the chain, the transaction might never get added.
To remedy this, you need to either ensure provable propagation of transactions, or vary the work factor for a node depending on how many links have been added since that node's most recent link.
Unfortunately, both measures can be defeated by sock puppets. This is probably the worst problem with your protocol as it stands right now; you need some central point to control the identities (keys) of the nodes and prevent people from making new sock puppets.
We need a protocol wherein to be a money tracking peer (an entity that validates spends) you have to be accepted by at least two existing peers who agree to synchronize data with you - presumably through human intervention by the owners of existing peers, and these two human approved synchronization paths indirectly connect you to the other peers in the network through at least one graph cycle.
If peer X is only connected to the rest of the network by one existing peer, peer Y, perhaps because X's directly connecting peer has dropped out, then X is demoted to a client, not a peer - any transactions X submits are relabeled by Y as submitted to Y, not X, and the time of submission (which forms part of the Patricia key) is the time X submitted them to Y, not the time they were submitted to X.
The algorithm must be able swiftly detect malfunctioning peers, and automatically exclude them from the consensus temporarily - which means that transactions submitted through malfunctioning peers do not get included in the consensus, therefore have to be resubmitted, and peers may find themselves temporarily demoted to clients, because one of the peers through which they were formerly connected to the network has been dropped by the consensus.
If a peer gets a lot of automatic temporary exclusions, there may be human intervention by the owners of those peers to which it exchanges data directly to permanently drop them.
Since peers get accepted by human invite, they have reputation to lose, therefore we can make the null hypothesis (the primary Bayesian prior) honest intent, valid data, but unreliable data transmission - trust with infrequent random verification. Designing the system on this basis considerably reduces processing costs.
Recall that SET died on its ass in large part because every transaction involved innumerable public key operations. Similarly, we have huge security flaws in https because it has so many redundant public key operations that web site designers try to minimize the use of https to cover only those areas that truly need it - and they always get the decision as to what truly needs it subtly wrong.
Efficiency is critical, particularly as the part of the market not yet served is the market for very low cost transactions.
If we solve the sock-puppet issue, or accept that there's a central point controlling the generation of new keys,
A central point will invite attack, will be attacked.
The problem with computer networked money is that the past can so easily be revised, so nodes come under pressure to adjust the past - "I did not pay that" swiftly becomes "I should not have paid that", which requires arbitration, which is costly, and introduces uncertainty, which is costly, and invites government regulation, which is apt to be utterly ruinous and wholly devastating.
For many purposes, reversal and arbitration is highly desirable, but there is no way anyone can compete with the arbitration provided by Visa and Mastercard, for they have network effects on their side, and they do a really good job of arbitration, at which they have vast experience, accumulated skills, wisdom, and good repute. So any new networked transaction system has to target the demand for final and irreversible transactions.
The idea of a distributed network consensus is that one has a lot of peers in a lot of jurisdictions, and once a transaction has entered into the consensus, undoing it is damn near impossible - one would have to pressure most of the peers in most of the jurisdictions to agree, and many of them don't even talk your language, and those that do, will probably pretend that they do not. So people will not even try.
To avoid pressure, the network has to avoid any central point at which pressure can be applied. Recall Nero's wish that Rome had a single throat that he could cut. If we provide them with such a throat, it will be cut.
reply
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
reply
0 sats \ 2 replies \ @BitcoinHistory OP 14 Nov 2023
Satoshi Nakamoto https://www.metzdowd.com/pipermail/cryptography/2008-November/014853.html satoshi at vistomail.com Fri Nov 14 13:55:35 EST 2008 Previous message: unintended? Next message: Bitcoin P2P e-cash paper Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] Hal Finney wrote:
I think it is necessary that nodes keep a separate pending-transaction list associated with each candidate chain. ... One might also ask ... how many candidate chains must a given node keep track of at one time, on average?
Fortunately, it's only necessary to keep a pending-transaction pool for the current best branch. When a new block arrives for the best branch, ConnectBlock removes the block's transactions from the pending-tx pool. If a different branch becomes longer, it calls DisconnectBlock on the main branch down to the fork, returning the block transactions to the pending-tx pool, and calls ConnectBlock on the new branch, sopping back up any transactions that were in both branches. It's expected that reorgs like this would be rare and shallow.
With this optimisation, candidate branches are not really any burden. They just sit on the disk and don't require attention unless they ever become the main chain.
Or as James raised earlier, if the network broadcast is reliable but depends on a potentially slow flooding algorithm, how does that impact performance?
Broadcasts will probably be almost completely reliable. TCP transmissions are rarely ever dropped these days, and the broadcast protocol has a retry mechanism to get the data from other nodes after a while. If broadcasts turn out to be slower in practice than expected, the target time between blocks may have to be increased to avoid wasting resources. We want blocks to usually propagate in much less time than it takes to generate them, otherwise nodes would spend too much time working on obsolete blocks.
I'm planning to run an automated test with computers randomly sending payments to each other and randomly dropping packets.
  1. 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.
It's very attractive to the libertarian viewpoint if we can explain it properly. I'm better with code than with words though.
Satoshi Nakamoto
reply
0 sats \ 1 reply \ @BitcoinHistory OP 14 Nov 2023
James A. Donald https://www.metzdowd.com/pipermail/cryptography/2008-November/014861.html jamesd at echeque.com Sat Nov 15 19:00:04 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:
Fortunately, it's only necessary to keep a pending-transaction pool for the current best branch.
This requires that we know, that is to say an honest well behaved peer whose communications and data storage is working well knows, what the current best branch is - but of course, the problem is that we are trying to discover, trying to converge upon, a best branch, which is not easy at the best of times, and becomes harder when another peer is lying about its connectivity and capabilities, and yet another peer has just had a major disk drive failure obfuscated by a software crash, and the international fibers connecting yet a third peer have been attacked by terrorists.
When a new block arrives for the best branch, ConnectBlock removes the block's transactions from the pending-tx pool. If a different branch becomes longer
Which presupposes the branches exist, that they are fully specified and complete. If they exist as complete works, rather than works in progress, then the problem is already solved, for the problem is making progress.
Broadcasts will probably be almost completely reliable.
There is a trade off between timeliness and reliability. One can make a broadcast arbitrarily reliable if time is of no consequence. However, when one is talking of distributed data, time is always of consequence, because it is all about synchronization (that peers need to have corresponding views at corresponding times) so when one does distributed data processing, broadcasts are always highly unreliable Attempts to ensure that each message arrives at least once result in increased timing variation. Thus one has to make a protocol that is either UDP or somewhat UDP like, in that messages are small, failure of messages to arrive is common, messages can arrive in different order to the order in which they were sent, and the same message may arrive multiple times. Either we have UDP, or we need to accommodate the same problems as UDP has on top of TCP connections.
Rather than assuming that each message arrives at least once, we have to make a mechanism such that the information arrives even though conveyed by messages that frequently fail to arrive.
TCP transmissions are rarely ever dropped these days
People always load connections near maximum. When a connection is near maximum, TCP connections suffer frequent unreasonably long delays, and connections simply fail a lot - your favorite web cartoon somehow shows it is loading forever, and you try again, or it comes up with a little x in place of a picture, and you try again
Further very long connections - for example ftp downloads of huge files, seldom complete. If you try to ftp a movie, you are unlikely to get anywhere unless both client and server have a resume mechanism so that they can talk about partially downloaded files.
UDP connections, for example Skype video calls, also suffer frequent picture freezes, loss of quality, and so forth, and have to have mechanisms to keep going regardless.
It's very attractive to the libertarian viewpoint if we can explain it properly. I'm better with code than with words though.
No, it is very attractive to the libertarian if we can design a mechanism that will scale to the point of providing the benefits of rapidly irreversible payment, immune to political interference, over the internet, to very large numbers of people. You have an outline and proposal for such a design, which is a big step forward, but the devil is in the little details.
I really should provide a fleshed out version of your proposal, rather than nagging you to fill out the blind spots.
reply
0 sats \ 0 replies \ @BitcoinHistory OP 14 Nov 2023
Satoshi Nakamoto https://www.metzdowd.com/pipermail/cryptography/2008-November/014863.html satoshi at vistomail.com Mon Nov 17 12:24:43 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:
Fortunately, it's only necessary to keep a pending-transaction pool for the current best branch.
This requires that we know, that is to say an honest well behaved peer whose communications and data storage is working well knows, what the current best branch is -
I mean a node only needs the pending-tx pool for the best branch it has. The branch that it currently thinks is the best branch. That's the branch it'll be trying to make a block out of, which is all it needs the pool for.
Broadcasts will probably be almost completely reliable.
Rather than assuming that each message arrives at least once, we have to make a mechanism such that the information arrives even though conveyed by messages that frequently fail to arrive.
I think I've got the peer networking broadcast mechanism covered.
Each node sends its neighbours an inventory list of hashes of the new blocks and transactions it has. The neighbours request the items they don't have yet. If the item never comes through after a timeout, they request it from another neighbour that had it. Since all or most of the neighbours should eventually have each item, even if the coms get fumbled up with one, they can get it from any of the others, trying one at a time.
The inventory-request-data scheme introduces a little latency, but it ultimately helps speed more by keeping extra data blocks off the transmit queues and conserving bandwidth.
You have an outline and proposal for such a design, which is a big step forward, but the devil is in the little details.
I believe I've worked through all those little details over the last year and a half while coding it, and there were a lot of them. The functional details are not covered in the paper, but the sourcecode is coming soon. I sent you the main files. (available by request at the moment, full release soon)
Satoshi Nakamoto
reply on another page