00:03:00phantomcircuit:sipa, any idea if that's just because of the current blockchain structure and not necessarily a constant optimum?
00:03:58rusty: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:23rusty:sipa: um, crazy idea. What if you select from the "best" blocks (ie. largest backskip) rather than just using exponential choice?
00:08:30rusty:* rusty needs more coffee...
00:27:06alferzz:alferzz is now known as alferz
00:37:56rusty: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:47rusty:sipa: of course, that could be terribly unlucky. Running with 100 different seeds now.
00:43:31sipa:rusty: is that the optimal path?
00:43:48sipa:rusty: also, see the code in bitcoin i linked you to
00:44:02rusty:sipa: yep, taking the backlink if dist < overkill.
00:44:20sipa:rusty: that doesn't guarantee optimality
00:44:29rusty:sipa: s/taking/considering/.
00:44:31sipa:you need dynamic programming to find the optimal solution
00:44:45sipa:and for random exponential links, that probably matters a lot
00:45:26rusty:sipa: yeah, already doing that. Of course, may have a bug :)
00:45:29sipa:ideally, finding the optimal path would mean just eager matching
00:52:46rusty: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:41sipa:rusty: see the code i linked you to!
00:55:04rusty:sipa: sure, I'll try that next.
00:55:24sipa:it's made so that further backlinks are likely to very quickly hit other far backlinks
00:55:44sipa:maybe just random backlinks without structure isn't enough
01:05:51rusty: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:10rusty:sipa: in summary, I'm not convinced that there's a constant factor in this case.
01:06:25sipa:i have trouble reading your numbers :)
01:06:39rusty:sipa: sorry, that's min - max ( mean +/0 stddev)
01:06:51sipa:what unit?
01:07:27rusty: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:49sipa:it should be around 150 or so
01:10:57rusty:sipa: Maybe. See https://github.com/rustyrussell/rusty-junkcode
01:11:52rusty: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:12sipa:yeah, i agree
01:12:36sipa:rusty: GetSkipHeight gives the height to jump to, not how far to jump back
01:12:50rusty:sipa: hence backjump = i - GetSkipHeight(i)
01:12:55sipa:ah, yes!
01:13:19rusty:sipa: I'm sure there are dumb errors, but hopefully they're better hidden than that :)
01:17:55sipa:rusty: why the rng in the decision loop?
01:18:16rusty:sipa: you referring to -1ULL / isaac64_next_uint64(&isaac) ?
01:18:44rusty:sipa: I pick a random u64 as my "block hash", and 0xFFFF.... as my target.
01:19:00rusty:sipa: hence -1ULL / random() => amount I can skip backwards.
01:19:29sipa:yeah, if you can't always jump back, i'm sure this solution is worthless
01:19:41sipa:sorry, i shouldn't have brought it up here
01:19:48sipa:it's interesting, but it's a very different problem
01:19:54rusty:sipa: hey, it was fun!
01:20:22sipa:iirc i experimented with just all powers of 2 backwards
01:20:48sipa:which needs a way smaller tree, so fewer hashes per link to use in the proof
01:21:07sipa:and eager selection when jumping back (as far as you can)
01:24:03rusty:sipa: I did that for pettycoin, too. Eager selection was a large factor worse than a real shortest calc though.
01:24:26sipa:possibly, yes
04:38:52omni:omni is now known as Guest22056
06:32:53maaku:maaku is now known as Guest2758
06:33:32Guest2758:Guest2758 is now known as maaku
06:54:35maaku:so I added an MMR estimator to rusty's code, and it does worse than rfc6962
06:54:59maaku:i'm a bit surprised about that
08:44:12maaku:ok, yes i think there was an error in the code
08:48:52SubCreative:SubCreative is now known as Sub|zzz
08:49:14Sub|zzz:Sub|zzz is now known as SubCreative
08:49:21SubCreative:SubCreative is now known as Sub|zzz
09:05:14hitchcock.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:14hitchcock.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:14hitchcock.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:14hitchcock.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:14hitchcock.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:05MRL-Relay:[smooth] .win1
12:59:19ahmed_:ahmed_ is now known as ahmed__
13:10:13NewLiberty_:NewLiberty_ is now known as NewLiberty
13:59:20nsh:gmaxwell, can you think of a pathological case in which a low-density parity-check algorithm would be nonterminating?
14:00:26gmaxwell:nsh: does not compute. Optimal decode for arbritary inputs isn't tractable. Any decoder is approximate, and time bounded.
14:00:27nsh:(decoding algorithm for a signal encoded with an LDPC encoding)
14:00:42nsh:ah, okay. was trying to parse someone's caveat
14:00:51gmaxwell:(well of course most of the time the decoder won't hit its timebound, it'll actually converge)
14:01:06nsh:"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:22nsh:wasn't intuitive to me how you'd get a nonterminating case
14:01:42gmaxwell:nsh: a naieve unbounded belief propagation could end up in a loop.
14:01:51gmaxwell:"so don't do that"
14:02:16nsh:surely there's a maximum nonlooping number of iterations. is that the time-bounding?
14:02:34gmaxwell:in any sane implementation!
14:02:41nsh:* nsh nods
14:03:49gmaxwell: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.
15:00:03zz_lnovy:zz_lnovy is now known as lnovy