| 00:03:00 | phantomcircuit: | sipa, any idea if that's just because of the current blockchain structure and not necessarily a constant optimum? |
| 00:03:58 | rusty: | gmaxwell: my testing (using traversal from block 8M to block 8M-150, ie. ~back 1 day) indicates doing a breadth-first tree for that case is a real win. eg. average 48 hashes of proof vs. 252. But breadth-first trees aren't incrementally updatable. |
| 00:06:23 | rusty: | sipa: um, crazy idea. What if you select from the "best" blocks (ie. largest backskip) rather than just using exponential choice? |
| 00:08:30 | rusty: | * rusty needs more coffee... |
| 00:27:06 | alferzz: | alferzz is now known as alferz |
| 00:37:56 | rusty: | sipa: OK, so single backlink can fare really badly. eg. my "seed=0" case for 1M hashes has some lucky jumps, so you get ~400 hashes for proof to genesis if you encode the whole tree. 583401 hashes for the single random-exponential backlink. |
| 00:38:47 | rusty: | sipa: of course, that could be terribly unlucky. Running with 100 different seeds now. |
| 00:43:31 | sipa: | rusty: is that the optimal path? |
| 00:43:48 | sipa: | rusty: also, see the code in bitcoin i linked you to |
| 00:44:02 | rusty: | sipa: yep, taking the backlink if dist < overkill. |
| 00:44:20 | sipa: | rusty: that doesn't guarantee optimality |
| 00:44:29 | rusty: | sipa: s/taking/considering/. |
| 00:44:31 | sipa: | you need dynamic programming to find the optimal solution |
| 00:44:45 | sipa: | and for random exponential links, that probably matters a lot |
| 00:45:26 | rusty: | sipa: yeah, already doing that. Of course, may have a bug :) |
| 00:45:29 | sipa: | ideally, finding the optimal path would mean just eager matching |
| 00:52:46 | rusty: | sipa: distribution looks correct. AFAICT the solution just sucks. It makes it exponentially harder to get lucky. Perhaps reversing it and making it 50% jump of N, 25% jump of N/2.... |
| 00:54:41 | sipa: | rusty: see the code i linked you to! |
| 00:55:04 | rusty: | sipa: sure, I'll try that next. |
| 00:55:24 | sipa: | it's made so that further backlinks are likely to very quickly hit other far backlinks |
| 00:55:44 | sipa: | maybe just random backlinks without structure isn't enough |
| 01:05:51 | rusty: | sipa: running more tests. Reversing (ie. 50% jump-to-genesis) did slightly better on average, much better on best case. Bitcoin variant is remarkably consistently bad, 500796-515705(509877+/-3e+03). |
| 01:06:10 | rusty: | sipa: in summary, I'm not convinced that there's a constant factor in this case. |
| 01:06:14 | sipa: | eh? |
| 01:06:25 | sipa: | i have trouble reading your numbers :) |
| 01:06:39 | rusty: | sipa: sorry, that's min - max ( mean +/0 stddev) |
| 01:06:51 | sipa: | what unit? |
| 01:07:27 | rusty: | sipa: number of hashes to get from block 999,999 to 0. Assuming 1 hash requires for each backlink (ie. assuming prev and another are merkled). |
| 01:07:49 | sipa: | it should be around 150 or so |
| 01:10:57 | rusty: | sipa: Maybe. See https://github.com/rustyrussell/rusty-junkcode |
| 01:11:52 | rusty: | sipa: it's pretty easy to reason about why the exponential backlink didn't work. Your chances of jumping back N are 1/N^2. |
| 01:12:12 | sipa: | yeah, i agree |
| 01:12:36 | sipa: | rusty: GetSkipHeight gives the height to jump to, not how far to jump back |
| 01:12:50 | rusty: | sipa: hence backjump = i - GetSkipHeight(i) |
| 01:12:55 | sipa: | ah, yes! |
| 01:13:01 | sipa: | sorry |
| 01:13:19 | rusty: | sipa: I'm sure there are dumb errors, but hopefully they're better hidden than that :) |
| 01:17:55 | sipa: | rusty: why the rng in the decision loop? |
| 01:18:16 | rusty: | sipa: you referring to -1ULL / isaac64_next_uint64(&isaac) ? |
| 01:18:19 | sipa: | yes |
| 01:18:44 | rusty: | sipa: I pick a random u64 as my "block hash", and 0xFFFF.... as my target. |
| 01:18:59 | sipa: | ah |
| 01:19:00 | rusty: | sipa: hence -1ULL / random() => amount I can skip backwards. |
| 01:19:07 | sipa: | right |
| 01:19:29 | sipa: | yeah, if you can't always jump back, i'm sure this solution is worthless |
| 01:19:41 | sipa: | sorry, i shouldn't have brought it up here |
| 01:19:48 | sipa: | it's interesting, but it's a very different problem |
| 01:19:54 | rusty: | sipa: hey, it was fun! |
| 01:20:22 | sipa: | iirc i experimented with just all powers of 2 backwards |
| 01:20:48 | sipa: | which needs a way smaller tree, so fewer hashes per link to use in the proof |
| 01:21:07 | sipa: | and eager selection when jumping back (as far as you can) |
| 01:24:03 | rusty: | sipa: I did that for pettycoin, too. Eager selection was a large factor worse than a real shortest calc though. |
| 01:24:26 | sipa: | possibly, yes |
| 04:38:52 | omni: | omni is now known as Guest22056 |
| 06:32:53 | maaku: | maaku is now known as Guest2758 |
| 06:33:32 | Guest2758: | Guest2758 is now known as maaku |
| 06:54:35 | maaku: | so I added an MMR estimator to rusty's code, and it does worse than rfc6962 |
| 06:54:59 | maaku: | i'm a bit surprised about that |
| 08:44:12 | maaku: | ok, yes i think there was an error in the code |
| 08:48:52 | SubCreative: | SubCreative is now known as Sub|zzz |
| 08:49:14 | Sub|zzz: | Sub|zzz is now known as SubCreative |
| 08:49:21 | SubCreative: | SubCreative is now known as Sub|zzz |
| 09:05:14 | hitchcock.freenode.net: | topic is: This channel is not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja |
| 09:05:14 | hitchcock.freenode.net: | Users on #bitcoin-wizards: andy-logbot d1ggy fluffypony MRL-Relay gues NewLiberty_ cbeams paveljanik MoALTz_ aburan28 maaku coiner Guest22056 TheSeven tlrobinson Dr-G2 ryanxcharles Shiftos Cory tacotime hashtagg alferz Transisto dgenr8 wizkid057 mortale devrandom bosma Luke-Jr Guest89604 Tjopper prepost GAit Graftec Adlai tromp_ NikolaiToryzin bobke kobud rfreeman_w huseby espes__ [d__d] BananaLotus koshii copumpkin amiller harrow optimator c0rw1n Iriez artifexd |
| 09:05:14 | hitchcock.freenode.net: | Users on #bitcoin-wizards: atgreen waxwing iambernie nuke1989 grandmaster gribble prodatalab kumavis_ shesek Sub|zzz Greed v3Rve Guest2104 nsh coryfields bsm117532 ahmed_ isis jgarzik BigBitz coutts BlueMatt cfields Anduck berndj Graet jaromil mr_burdell Eliel gavinandresen nanotube sl01_ PaulCapestany lclc_bnc hguux_ luny AdrianG_ Muis kanzure jbenet mappum lnovy michagogo OneFixt digitalmagus gwillen Grishnakh samson_ kyletorpey CryptOprah btc__ DougieBot5000 |
| 09:05:14 | hitchcock.freenode.net: | Users on #bitcoin-wizards: Starduster wumpus [\\\] phantomcircuit stonecoldpat morcos pi07r eric dansmith_btc mkarrer ompik Emcy toddf heath go1111111 bbrittain DoctorBTC Apocalyptic EasyAt tromp null_radix hollandais midnightmagic starsoccer danneu catcow TD-Linux ryan-c roasbeef smooth mmozeiko Alanius JonTitor warren Krellan fenn LarsLarsen jchp nsh_ asoltys_ K1773R nickler_ a5m0 @ChanServ Meeh comboy btcdrak eordano Nightwolf gmaxwell pigeons andytoshi lechuga_ |
| 09:05:14 | hitchcock.freenode.net: | Users on #bitcoin-wizards: warptangent Fistful_of_Coins HM2 Guest38445 iddo BrainOverfl0w phedny Keefe helo so crescendo petertodd throughnothing Taek poggy burcin livegnik sipa harrigan sneak s1w Logicwax yoleaux azariah kinlo |
| 09:20:05 | MRL-Relay: | [smooth] .win1 |
| 12:59:19 | ahmed_: | ahmed_ is now known as ahmed__ |
| 13:10:13 | NewLiberty_: | NewLiberty_ is now known as NewLiberty |
| 13:59:20 | nsh: | gmaxwell, can you think of a pathological case in which a low-density parity-check algorithm would be nonterminating? |
| 14:00:26 | gmaxwell: | nsh: does not compute. Optimal decode for arbritary inputs isn't tractable. Any decoder is approximate, and time bounded. |
| 14:00:27 | nsh: | (decoding algorithm for a signal encoded with an LDPC encoding) |
| 14:00:42 | nsh: | ah, okay. was trying to parse someone's caveat |
| 14:00:51 | gmaxwell: | (well of course most of the time the decoder won't hit its timebound, it'll actually converge) |
| 14:01:06 | nsh: | "LDPC is a more efficient extension that reaches the Shannon limit [...] harder to do by hand, and the decoding algorithms are iterative and possibly nonterminating" |
| 14:01:22 | nsh: | wasn't intuitive to me how you'd get a nonterminating case |
| 14:01:42 | gmaxwell: | nsh: a naieve unbounded belief propagation could end up in a loop. |
| 14:01:51 | gmaxwell: | "so don't do that" |
| 14:01:55 | nsh: | hmm |
| 14:02:16 | nsh: | surely there's a maximum nonlooping number of iterations. is that the time-bounding? |
| 14:02:34 | gmaxwell: | in any sane implementation! |
| 14:02:41 | nsh: | * nsh nods |
| 14:03:49 | gmaxwell: | even if you didn't care about it being finitely timed, you could implement loop detection cheaply and then it would be technically terminating. But that all seems silly, you put a bound on it and accept that there are some inputs that it could have corrected if it spent just a bit more time on it before giving up. |
| 14:05:03 | nsh: | hmm |
| 15:00:03 | zz_lnovy: | zz_lnovy is now known as lnovy |