Re: Proof of Work - atmospheric carbon
John Gilmore writes: The last thing we need is to deploy a system designed to burn all available cycles, consuming electricity and generating carbon dioxide, all over the Internet, in order to produce small amounts of bitbux to get emails or spams through. It's interesting to consider the ultimate technological resolution to this issue. Will a global-scale proof-of-work based system inherently consume substantial amounts of energy? Or are there ways of doing computing which would allow such a system to use only moderate energy consumption? This question relates to the thermodynamics of computation. It has long been known that logically reversible transformations can be done with arbitrarily low energy dissipation. Hence attention is focused on irreversible transformations, particularly those that require bit erasure. Erasing a bit dissipates approximately energy of approximately kT where k is Boltzmann's constant and T is temperature. The question is whether a POW system inherently involves a great deal of irreversible logical transitions, causing bit erasure and dissipating energy? Or could a POW token be created using solely reversible logic? One note is that any algorithm can in principle be made reversible except for the size of the output: compute it using reversible logic, possibly creating many excess bits which will allow the reversal, until we get the answer; then make a copy of the output; then reverse the calculation, consuming all the excess bits until we get back to the original value. The only irreversible step was saving the output. However this is impractical for large calculations like we are talking about, because the number of excess bits would dwarf the size of the calculation. The hash collisions used in systems like Bitcoin or Hashcash (technically not collisions, rather searches for pre-images of hash values with many leading zero bits) seem inherently irreversible. The algorithm typically sets up a pre-image that includes a counter value, computes the hash, increments the counter and repeats until a hash is found with the desired properties. The hash function itself typically uses many intrinsically irreversible transitions, since logical irreversibility is a defining requirement of a hash function. Even if we use the trick in the preceding paragraph to eliminate the cost of the intermediate steps in computing the hash, we would still need to erase the output result each iteration, dissipating energy. Typical POW systems in use today require millions to billions of iterations, and this would be likely to increase in the future, so the dissipation could be substantial. Replacing the hash with a logically invertible function might help to reduce the number of intermediate bits, and eliminate the need to use the run-backwards trick. One would require that both the pre-image and the post-image contain a number of bits in fixed positions. However this would still seem to require the same kind of search algorithm, causing dissipation as each intermediate result is erased. Perhaps a variation on this idea would work, if the logically invertible function was itself very slow, perhaps paramaterized to have a huge number of rounds. Then only a relatively small number of iterations would be needed before a lucky result is found, for a given level of POW effort. This would reduce dissipation. However it would slow down verification, and since verification of the POW will be done far more often than creation, we can't afford to tip things too far in that direction. Another idea I had was to use a deterministic POW rather than a random one like hash collision. Cryptographic work on timed commitments and related topics has shown that repeated squarings modulo an unknown RSA modulus allow for a relatively concise and quickly verifiable proofs that some very large number of squarings had taken place, with no shortcuts possible for the creation of the resulting certification. Broadly speaking, modular squaring is logically reversible, in that one could theoretically compute the square root. But in practice, as with the hash computation, computing a modular square using logically reversible operations will produce a large number of excess bits. Even if the excess from a single squaring could be consumed using the trick mentioned above, one would still be forced to erase the temporarily result of each individual squaring operation, as the POW would require a very large number of squarings. So the overall dissipation would appear to be similar to the hash computation. (Also, it's not clear that a deterministic POW works well for an application like Bitcoin; it might let the owner of the fastest computer win every POW race, giving him too much power.) So the question from John's challenge remains open: is there a POW system which could be built solely on logically reversible computation? The computation has to be intrinsically time consuming, but with a short and quickly verifiable
Re: What EV certs are good for
On Wed, Jan 28, 2009 at 5:14 AM, William Soley william.so...@sun.com wrote: On Jan 27, 2009, at 6:04 AM, Jerry Leichter wrote: It might be useful to put together a special-purpose HTTPS client which would initiate a connection and tell you about the cert returned, then exit. I use ... openssl s_client -connect www.whatever.com:443 -showcerts Ships with Mac OS, Solaris, Linux, etc. And to use TOR, put torify on the front. Having run the tor server, of course. Except on MacOS, where torify doesn't (can't? Does anyone know better) work. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Obama's secure PDA
Jerry Leichter leich...@lrw.com writes: There's a Classified USB Cable for file transfer with Classified PC I wonder what a classified USB cable is. Perhaps it's an unclassified USB cable with the little three-prong USB logo blacked out by the censors. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What EV certs are good for
I just received a phishing email, allegedly from HSBC: Dear HSBC Member, So did the link have a EV cert? Hardly matters. HSBC has vast numbers of web servers all over the world, some with EV certs, some without. For example, their US customer site for deposit customers at https://www.us.hsbc.com/ doesn't, but their site for credit cards at https://www.hsbccreditcard.com/ does, although it's kind of hard to tell because they tend to put you on a non-https page until you log in. R's, John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Obama's secure PDA
pgut...@cs.auckland.ac.nz (Peter Gutmann) writes: Jerry Leichter leich...@lrw.com writes: There's a Classified USB Cable for file transfer with Classified PC I wonder what a classified USB cable is. Perhaps it's an unclassified USB cable with the little three-prong USB logo blacked out by the censors. I would imagine it is a tempest shielded cable, and appropriately altered connectors. Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
full-disk encryption standards released
http://www.computerworld.com/action/article.do?command=viewArticleBasicarticleId=9126869intsrc=hm_ts_head --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Proof of Work - atmospheric carbon
(Also, it's not clear that a deterministic POW works well for an application like Bitcoin; it might let the owner of the fastest computer win every POW race, giving him too much power.) Indeed. And don't forget that through the magic of botnets, the bad guys have vastly more compute power available than the good guys. You know those crackpot ideas that keep showing up in snake oil crypto? Well, e-postage is snake oil antispam. R's, John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Proof of Work - atmospheric carbon
On Jan 27, 2009, at 2:35 PM, Hal Finney wrote: John Gilmore writes: The last thing we need is to deploy a system designed to burn all available cycles, consuming electricity and generating carbon dioxide, all over the Internet, in order to produce small amounts of bitbux to get emails or spams through. It's interesting to consider the ultimate technological resolution to this issue. Will a global-scale proof-of-work based system inherently consume substantial amounts of energy? Or are there ways of doing computing which would allow such a system to use only moderate energy consumption? ... [Proposals to use reversible computation, which in principle consume no energy, elided.] There's a contradiction here between the computer science and economic parts of the problem being discussed. What gives a digital coin value is exactly that there is some real-world expense in creating it. We talk about proof of work, but in fact work done by a computer doesn't, in and of itself, have any value. It gets a value only when it's a limited resource *which might have been used for something else* - i.e., the value of the spare cycles that might be thrown at doing the computations comes from the opportunity cost incurred. If this were not so, anyone could just create as many as they wanted at no cost to themselves. In fact, this is behind the cost model 'bot herders using other people's machines. But ultimately that only works for the 'bot herders because there is no significant loss to the owners of those machines either! Now, if instead we used algorithms not based on some abstraction notion of work, but on the equivalent power that had to be dissipated to do the computation, then the value of a digital token would truly be grounded in the real world. Spare cycles would no longer be free - they would show up on your power bill. Sure, the 'bot herders wouldn't have to pay - but if the owners of the pwned machines saw a real cost, they would have an incentive to do something about it (which they basically don't, today). Eliminating the power cost puts you back to amortizing the fixed cost of the CPU and memory doing the computation - a cost that's dropping all the time. I don't see how you get to an economically viable mechanism that way. So, how do you tie the cost of a token to power? Curiously, something of the sort has already been proposed. It's been pointed out - I'm afraid I don't have the reference - that CPU's keep getting faster and more parallel and a high rate, but memories, while they are getting enormously bigger, aren't getting much faster. So what the paper I read proposed is hash functions that are expensive, not in CPU seconds, but in memory reads and writes. Memory writes are inherently non-reversible so inherently cost power; a high-memory-write algorithm is also one that uses power. (BTW, a number of years back, a VC friend ran by me a proposal to buy the spare cycles on people's set-top boxes - which have pretty hefty chips in them - and rent out the resulting distributed compute server. The claim was that you didn't have to pay people much of anything for use of their boxes - you'd only do it when they were otherwise unoccupied, so they should be happy to get even very small payments. I pointed out the cost they had neglected: Increased power use. Sure, individuals probably wouldn't notice - but at some point some consumer organization would. The resulting bad publicity would kill the business. We did a bit of calculation to add that in to what would be paid to the box owners and the whole enterprise started looking less interesting from a purely economic point of view - not that it didn't have plenty of other problems.) -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Obama's secure PDA
On Jan 28, 2009, at 2:03 PM, Perry E. Metzger wrote: There's a Classified USB Cable for file transfer with Classified PC I wonder what a classified USB cable is. Perhaps it's an unclassified USB cable with the little three-prong USB logo blacked out by the censors. I would imagine it is a tempest shielded cable, and appropriately altered connectors. That's probably a big part of it. I commented earlier that $3200 seemed surprisingly cheap. One of the articles on this claimed this was absurdly expensive - typical DoD gold plating. Well ... the real price of a standard Blackberry is a couple of hundred dollars, and put one in a room with a speaker phone and listen to the famous Blackberry buzz. Shielding these things, even to avoid obvious interference, is *not* easy. Getting it to Tempest specs must take some impressive engineering. For a non-mass- market device with that kind of engineering, $3200 seems pretty cheap. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
