Re: unintended?
On Fri, Nov 14, 2008 at 02:29:24PM -0700, Chad Perrin wrote: On Fri, Nov 14, 2008 at 01:26:29PM +, [EMAIL PROTECTED] wrote: (snicker) from the local firefox en-us.add-ons.mozilla.com:443 uses an invalid security certificate. The certificate is not trusted because the issuer certificate is not trusted. (Error code: sec_error_untrusted_issuer) What does Perspectives have to say? What installation of Firefox did you use? I don't have that problem when I visit: https://addons.mozilla.org/en-US/firefox/ Do you perhaps have some kind of malicious redirection going on there? -- Chad Perrin [ content licensed PDL: http://pdl.apotheon.org ] perspectives is not installed. I've never taken the default and added a cert that was not in the firefox trusted list... (at least on a permanent basis) Mozilla/5.0 (Macintosh; U; PPC Mac OS X 10.4; en-US; rv:1.9.0.2) Gecko/2008091618 Firefox/3.0.2 and yes, a redirect might be in play - except this happens w/ multiple, different caches (fm the house, work, panera, starbucks and even the cows end) --bill - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Bitcoin P2P e-cash paper
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
Re: Bitcoin P2P e-cash paper
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.
Re: Bitcoin P2P e-cash paper
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
Re: Bitcoin P2P e-cash paper
Ray Dillinger wrote: 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. Right, it's ECC digital signatures. A new key pair is used for every transaction. It's not pseudonymous in the sense of nyms identifying people, but it is at least a little pseudonymous in that the next action on a coin can be identified as being from the owner of that coin. 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. There is no reliance on identifying anyone. As you've said, it's futile and can be trivially defeated with sock puppets. The credential that establishes someone as real is the ability to supply CPU power. 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? Section 11 calculates the worst case under attack. Typically, 5 or 10 blocks is enough for that. If you're selling something that doesn't merit a network-scale attack to steal it, in practice you could cut it closer. But in the absence of identity, there's no downside to them if spends become invalid, if they've already received 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. This is a version 2 problem that I believe can be solved fairly satisfactorily for most applications. The race is to spread your transaction on the network first. Think 6 degrees of freedom -- it spreads exponentially. It would only take something like 2 minutes for a transaction to spread widely enough that a competitor starting late would have little chance of grabbing very many nodes before the first one is overtaking the whole network. During those 2 minutes, the merchant's nodes can be watching for a double-spent transaction. The double-spender would not be able to blast his alternate transaction out to the world without the merchant getting it, so he has to wait before starting. If the real transaction reaches 90% and the double-spent tx reaches 10%, the double-spender only gets a 10% chance of not paying, and 90% chance his money gets spent. For almost any type of goods, that's not going to be worth it for the scammer. Information based goods like access to website or downloads are non-fencible. Nobody is going to be able to make a living off stealing access to websites or downloads. They can go to the file sharing networks to steal that. Most instant-access products aren't going to have a huge incentive to steal. If a merchant actually has a problem with theft, they can make the customer wait 2 minutes, or wait for something in e-mail, which many already do. If they really want to optimize, and it's a large download, they could cancel the download in the middle if the transaction comes back double-spent. If it's website access, typically it wouldn't be a big deal to let the customer have access for 5 minutes and then cut off access if it's rejected. Many such sites have a free trial anyway. Satoshi Nakamoto - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Bitcoin P2P e-cash paper
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. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: unintended?
[Moderator's note: Top posting is considered untasteful. --Perry] It doesn't need to be malicious. It depends on the situation. For example, lots of corporations do SSL session inspection using products like Bluecoat. The Bluecoat does a MiTM attack to expose the plaintext for analysis, and expects that corporate users trust the certificate it provides (and have pushed it out to all corporate browsers). If you've just loaded Firefox, it won't have that trusted cert loaded by default, and you'll see exactly the below. Ian. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Chad Perrin Sent: Saturday, November 15, 2008 8:29 AM To: cryptography@metzdowd.com Subject: Re: unintended? On Fri, Nov 14, 2008 at 01:26:29PM +, [EMAIL PROTECTED] wrote: (snicker) from the local firefox en-us.add-ons.mozilla.com:443 uses an invalid security certificate. The certificate is not trusted because the issuer certificate is not trusted. (Error code: sec_error_untrusted_issuer) What does Perspectives have to say? What installation of Firefox did you use? I don't have that problem when I visit: https://addons.mozilla.org/en-US/firefox/ Do you perhaps have some kind of malicious redirection going on there? -- Chad Perrin [ content licensed PDL: http://pdl.apotheon.org ] John Kenneth Galbraith: If all else fails, immortality can always be assured through spectacular error. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Bitcoin P2P e-cash paper
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 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
