--- Log opened Sun Nov 03 00:00:14 2013 08:57 < adam3us> btw i was misinterpreting https://blockchain.info/q/hashrate as in GH rather than the correct TH in my comparison a few days ago of network has to eff des cracker ($250k, 56hrs to break one O(2^56) des key) 08:58 < sipa> gribble has a ;;nethash command that gives a good estimate in GH/s 08:59 < sipa> (it's pulled from my site) 08:59 < sipa> oh, you're not in #bitcoin-dev ? 08:59 < adam3us> so.. bitcoin is actually doing O(2^71) work puzzles (or O(2^72) if you count each of the double hashes) per 10mins, and if bitcoin was attacking DES (which is probably easier than 1 SHA256 round as DES is ASIC friendly) could do in 9.4ms per DES key to deepcracks 56hrs 08:59 < sipa> that reasoning is flawed IMHO, as the current ASICs cannot do DES at all 08:59 < adam3us> and if focussed on skipjack (80bit previously secret NSA cipher in clipper) it could break one of those every 2 days 09:00 < sipa> yes, it would cost the same of less to produce a similar amount of ASICs that could do DES 09:00 < sipa> but contrary to Bitcoin mining, it does not pay for itself 09:00 < adam3us> sipa: yes its a what if and gmaxwell noted DES is actually more ASIC friendly 09:00 < sipa> i'm sure it is 09:00 < sipa> but i don't think that's very relevant 09:01 < sipa> unless you just want a "how much would it cost to crack DES" computation 09:01 < adam3us> sipa: sure; i just think its interesting to express security of the hash in O(2^k) for comparison and ... 72-bits is a surprising amount for 10mnis 09:01 < adam3us> sipa: (eg for comparison to the birthday attack on p2sh addresses which is itself O(2^80) + tmto) 09:02 < sipa> it's 2**51.85 double-SHA256 per second 09:02 < adam3us> sipa: that makes the RIPEMD160 birthday attack not entirely theoretical 09:02 < adam3us> sipa: err that sounds like my previous gh calc 09:03 < adam3us> https://blockchain.info/q/hashrate = 3983800.965092061 09:03 < sipa> we're at 2**73.5 double-SHA256 in total, ever 09:03 < adam3us> and thats TH so basically 4 PH 09:03 < sipa> i refuse to look at b.i 09:04 < adam3us> sipa: ok but bitcoin hashrate as a ballpark is well known to be n the peta hash range 09:04 < sipa> yes, 4 PH/s 09:04 < sipa> that's 2**52 H/s 09:05 < adam3us> log(2,4*1000^6*600) 09:05 < adam3us> 71.02352439846840313959 09:05 < sipa> you must still be off; i get 2**61 per 10 minutes 09:06 < sipa> 1:kilo, 2:mega, 3:giga, 4:tera, 5:peta 09:06 < adam3us> sipa: well i did before, but KH=1000,HM=1000.. etc 09:06 < sipa> so it's ^5, not ^6 09:06 < sipa> ^6 is exa 09:06 < adam3us> sipa: oh doh 09:07 < adam3us> sipa: damn i was right the first time, undo wiki edit! (confusing exa and peta order) 09:07 < sipa> adam3us: the reference client outputs the total amount of work done in a chain when it updates the tip 09:07 < sipa> SetBestChain: new best=0000000000000000bd36abfbfaf30511e69d9747b1b4c9238739b20d7a92e760 height=267715 log2_work=73.502314 tx=26423141 date=2013-11-03 13:58:03 09:07 < adam3us> sipa: gotcha, thats nice 09:07 < sipa> i trust that computation very much, as it is consensus-critical 09:08 < sipa> (it's used to determine the longest chain) 09:08 < sipa> adam3us: http://bitcoin.sipa.be/powdays-50k.png 09:09 < sipa> that's how long, at max-hashrate-ever-seen-until-point-X, it would take to redo all the computational work in the best chain known at point X 09:09 < adam3us> sipa: a quite relevant metric :) 09:09 < sipa> it's painfully low these days 09:10 < sipa> we came up with it, when trying to reason like "how many days of PoW-equivalent work would it take, to safely reduce verification" 09:10 < adam3us> sipa: indeed it is - i think it should be temporary perhaps as asic catchup with moore's law 09:10 < sipa> so for example, one idea was to only do signature checking in the last month worth of PoW 09:10 < adam3us> sipa: however the other metric is the market availability 09:10 < sipa> but as you can see, that would mean everything now :) 09:12 < sipa> hmm, i wonder, is this coincidence? 09:12 < sipa> tera ~ quatro (1000^4) 09:12 < sipa> peta ~ penta (1000^5) 09:12 < sipa> exa ~ hexa (1000^6) 09:13 < sipa> at least for peta and exa it is not coincidence 09:13 < sipa> tera ~ tetra works even better 09:14 < adam3us> yeah, you see it in greek naming for geometric shapes also 09:14 < sipa> and above: zetta ~ hepta 09:14 < sipa> yotta ~ octo 09:16 < adam3us> sipa: i think i just illustrated even to myself that k=61 O(2^k) security notation is better - it gets confusing to work with metric units you dont normally use 09:17 < sipa> yup 09:19 < sipa> knowing that an exabyte addresses is close to what you can represent in a 64-bit integer, also helps :) 09:22 < adam3us> sipa: probably proof of stake contribution to voting is a defense though that also is imperfect 13:21 < warren> more leveldb corruption "Getting same error on 8.5.1 OS/X 10.9 Mavericks out of the blue, my system never sleeps and Litecoin was shut down properly, but received this error on re-opening wallet." 13:21 < warren> clean shutdown 14:43 < adam3us> sipa: re pow-equiv days - you might consider also the days to redo all work since last checkpoint, an even lower number 15:20 < gmaxwell> adam3us: we hope to remove checkpoints or at least significantly reduce their role. They're creating seriously problems for people understanding the consensus model, to the extent where people are producting altcoins where the developers just constantly announce checkpoints via an alert like mechenism to control the consensus and this is judged to be the same kind of thing as bitcoin. 15:26 < jrmithdobbs> you know, haskell really is the most fun i've had with CS stuff since initial dive into bitcoin stuff 15:26 < jrmithdobbs> why doesn't everyone use this language? 17:27 < sipa> jrmithdobbs: haskell is cool :) 17:28 < sipa> adam3us: right, as gmaxwell says: this idea of using PoW-equivalent time as a criterion is mostly intended as a replacement for checkpoints 17:29 < adam3us> sipa: i see i didnt get that before; so you propose to eg pick a number of days, and say a new client only starts that far back with its validation? 17:30 < adam3us> sipa: or validate back to current pow-equivalent 17:30 < sipa> adam3us: you always start from the genesis, there is no way to retrieve the UTXO set at any other point in a trust-free way 17:31 < adam3us> sipa: wonder if there's a way to batch process DSA sig verify 17:31 < sipa> adam3us: but some parts of the validation, in particular script validation, can be skipped without impacting 17:31 < sipa> adam3us: there is, but it requires the full R point, instead of just R.x mod n 17:33 < sipa> without impacting later state 17:33 < adam3us> sipa: so (the proposal would be) you just validate inputs add to outputs and the hashing, but not the sigs before pow-equiv? reasoning being the whole network could've forged history to that depth? 17:33 < sipa> i had to finish that sentence 17:33 < sipa> indeed 17:34 < sipa> or some compromise, like only checking a random N% 17:34 < sipa> when buried deep enough 17:34 < gmaxwell> adam3us: right, or move to probablistic validation of deep history. So you still can be reasonable confident that if there is trechery and a good number of honest users it will be discovered... but removing 99.9% of the computational cost for the far history. 17:35 < sipa> then again, saying "more than a month of PoW" won't work anytime soon :) 17:36 < gmaxwell> sipa: I dunno if I ever mentioned it, but I was thinking that it actually should be validation of the history where it is uniquely dominated by POW-days work. E.g. if there are two compeating forks with less than powdays-tresh between them, you still check both completely in case the signatures are a cause for the fork. 17:36 < sipa> you have mentioned that before, i believe 17:37 < gmaxwell> okay. Wasn't sure. 17:39 < adam3us> sipa, gmaxwell: i wonder if you only need 50% PoW-equiv , because isnt sying full hashrate PoW days assuming 100% hashrate hostility? 17:40 < sipa> it's a scaling factor anyway 17:40 < sipa> something to judge what a potential attacker could amass 17:40 < gmaxwell> adam3us: bitcoin, in the original vision promises to now allow some attacks even in the face of full hashrate hostility. This is important because its part of what makes greedy-optimal miners behave honestly (in the ficticious world where miners are optimal self interested agents, hah). 17:42 < gmaxwell> So it's not really quite good enough to say "we're going to make things maximally brittle against >50%" because part of the argument that an attacker won't amass 50% is the limitations on what they can do with it. For example: if it were sufficient for 50% of miners to peg the subsidy at 25 btc forever then the argument that it wouldn't happen is pretty soft. 17:42 < gmaxwell> (since even if the miners are independant they have a common interest in continuing to recieve subsidy) 17:43 < adam3us> gmaxwell: yes there are somethings eg also committed coins seemingly you can continue to transact in the face of 99% hostlle (maybe 100%) their attack degrades to random DoS if they cant tell whats happening 17:44 < adam3us> gmaxwell: (commited tx not coins) and also 50% is probability argument only: you can double spend with various probabilities with 25% of 75% hashrate its not binary 17:45 < gmaxwell> adam3us: yea, well at >50% you can exclude other blocks and if you can attack for infinite time you'll eventually get ahead. (infinite becoming smaller the more over 50% you are). 18:16 < adam3us> sipa: (about batch ECDSA verification) "sipa: adam3us: there is, but it requires the full R point, instead of just R.x mod n" - you could arrange that in a format compatible way analogous to the s vs -s issue; just only use R=(r,f(r)) with positive f(r). 18:17 < gmaxwell> you still have to then 'uncompress' the r there then, which would remove some (much?) of the batch speedup. 18:33 < sipa> i believe it would still be a speedup 18:34 < sipa> but it's pointless: it would mean an incompatible change of the script language, or at least an op_eval like structure with a new address structure 18:34 < sipa> and if we do that, there are far better changes to make 18:35 < sipa> hmm, i didn't read what you said entirely 18:36 < sipa> putting an extra requirement on r is always possible of course, and only a soft fork 18:59 < adam3us> sipa: maybe could restrict f(r) >= 0 while fixing (r,s) vs (r,-s) sig malleability (and the serialization ones) .. just towards enabling batch sig vrfy later? 18:59 < adam3us> sipa: mean R.y>=0 19:00 < sipa> the '>' operator doesn't have much meaning in a Z_p set 19:00 < gmaxwell> gonna make life hard for determinstic dsa signers. Also makes life harder for people to make txn slightly smaller by chosing smaller rs. 19:01 < sipa> i'm not sure batch verification is worth it 19:01 < sipa> iirc the speedup wasn't very impressive 19:01 < gmaxwell> in any case the speedup from batch verification is pretty small. 19:01 < adam3us> sipa, gmaxwell: seems like forget that then :) 19:24 < amiller> hm, i wonder if there's an accelerated utxo check 19:24 < amiller> well nvm it probably wouldn't make much difference 19:26 < amiller> but you don't have to use a *random access* data structure just for checking a utxo, since you can have some untrusted hints about after how many blocks an element will have to be removed at all 19:30 < sipa> amiller: anything that adds performance increases for the common case, means a potential DoS attack by someone not following the common case :) 19:35 < amiller> i guess... can't stop anyone from just downloading a "trusted" utxo and skipping validation anyway though, so it seems like reducing the cost of actually checking it (if that's even possible) would be good to know how to do --- Log closed Mon Nov 04 00:00:16 2013