--- Day changed Mon Dec 22 2014 00:00 < maaku> so the MMR structure (which rusty is calling a naive merkle array) is better than any considered alternatives after about 1M headers 00:00 < maaku> also easier to implement, so yay 00:02 -!- omni [~omni@ip68-4-111-228.oc.oc.cox.net] has joined #bitcoin-wizards 00:02 < gmaxwell> yep. sounds reasonable to me. 00:02 -!- omni is now known as Guest99220 00:06 -!- soundx [~soundx@gateway/tor-sasl/soundx] has joined #bitcoin-wizards 00:08 -!- adam3us [~Adium@host-92-19-10-191.as13285.net] has joined #bitcoin-wizards 00:11 -!- soundx [~soundx@gateway/tor-sasl/soundx] has quit [Ping timeout: 250 seconds] 00:12 < maaku> petertodd: are there any existing implementations of merkle mountain ranges? 00:12 -!- moa [~kiwigb@opentransactions/dev/moa] has quit [Ping timeout: 255 seconds] 00:12 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has joined #bitcoin-wizards 00:13 < petertodd> maaku: yup: https://github.com/opentimestamps/opentimestamps-client/blob/28333aacb9bf4551210d7ea6b94879b703b1ae51/opentimestamps/journal.py#L147 00:14 < maaku> petertodd: C++? 00:14 < petertodd> nah 00:14 < maaku> ok thanks 00:14 < maaku> (Python will be useful too; I'll need both) 00:14 < gmaxwell> maaku: when you were commenting before about the cpu cost, I thought you were thinking of the same data structure but backwards. (which might be more efficient because long jumps in the unbalanced portions end up being the shorter hashes) 00:14 < petertodd> there's a on-disk version somewhere in there too... 00:16 -!- aburan28 [~ubuntu@static-108-45-93-73.washdc.fios.verizon.net] has quit [Remote host closed the connection] 00:16 < petertodd> the on-disk version is quite nice, as there's a very clear way to store all of the leaf hashes and inner hashes using the standard breadth first tree -> array mapping (forget what that's called exactly) works fine with sparse files too if you want to leave some of the data out 00:17 -!- siraj [~siraj@158.120.0.14] has joined #bitcoin-wizards 00:18 < petertodd> though there's non-trivial complexity in proving a number of statements about MMR's... so I wouldn't jump too quickly to using them without thinking through that stuff. (non-issue in timestamping) 00:19 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 00:22 < maaku> gmaxwell: not sure I parse what you mean by "but backwards" 00:23 < gmaxwell> putting the genesis block at the most unbalanced position, e.g. the version that cannot be efficiently appended to. 00:23 < maaku> petertodd: hate to sound naive, but it seems pretty straightforward, and most importantly its properties are holding up under experiment. 00:23 < maaku> which properties are you talking about? 00:23 < petertodd> maaku: I mean things like proving what index # a proof corresponds too 00:23 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 245 seconds] 00:25 < gmaxwell> maaku: just things like making sure you don't have any cases of inner node / leif emulation and things like that. 00:25 < petertodd> RFC6962's merkle tree is a fair bit more clear in that regard; I'm working on implementing a prunable/summable version of it 00:26 < gmaxwell> petertodd: you might want to be mindful of the compression function input sizes, note that SHA224 has a nice property that two if its output fit in a single compression function input. 00:26 < petertodd> remember that MMR's are basically RFC6962 but with a small decrease in proof length at the cost of another layer of complexity 00:27 < petertodd> gmaxwell: yeah, I write code in Python :) 00:28 -!- fanquake [~anonymous@unaffiliated/fanquake] has quit [Quit: fanquake] 00:28 < petertodd> gmaxwell: I've done crazy low-level optimizations before, but am deeply skeptical of their place in security code 00:29 < gmaxwell> Well there is no free lunch. Thats a pointless halving in performance, ... if the performance isn't needed, better to use a more costly hash function. :) 00:30 < petertodd> a pointless halving of what may easily be 1% of the performance of your system... 00:30 < gmaxwell> (and if one doesn't like SHA224, SHA512/256 is well specified and also has room for metadata in one compression function run, and SHA512 appears to have improved security margin in any case) 00:31 < maaku> petertodd: the number of hashes involved here is significant 00:31 < gmaxwell> petertodd: perhaps, actually checking hashtrees in bitcoin already shows up quite visibly in the profiles. If there were several other proof hashtrees we were carrying around sha256 would be the number one thing in verifying blocks with already cached signatures. 00:32 < petertodd> which gets to my bigger point: if you're architecture for bitcoin is sufficiently poorly scaling that you care about this stuff, you're going down a bad path 00:32 -!- moa [~kiwigb@opentransactions/dev/moa] has joined #bitcoin-wizards 00:32 < maaku> actually after re-reading the MMR doc, I don't think that's what rusty implemented at all 00:33 < gmaxwell> petertodd: I don't agree, all these decisions scoot around the amount of deceneralization you can get for a given scaling level. They also have significance when you want to talk about extracting proofs for embedded devices (and for using inside other ZKP). 00:33 < petertodd> maaku: I'll take a wild guess he made RFC6962 instead... 00:33 < maaku> looking at it now to compare 00:33 < maaku> petertodd: the validation is incremental and cheap, but that doesn't mean we shouldn't care about performance to regenerate/revalidate the current state 00:33 < petertodd> gmaxwell: if ZKP matters to you, specify that as an explicit requirement - ZKP can easily result in needs that *against* normal scaling requirements 00:34 < maaku> or not be concerned about low power, embedded devices 00:34 < petertodd> gmaxwell: +-50% differences don't interest me in the slightest 00:35 < gmaxwell> Good for you. 00:35 < petertodd> the #1 goal of this stuff needs to be to make it understandable and obvious. for instance replacing the easy to read SignatureHash() function with that horrendous class was a huge step backwards for people's understanding of how signature hashes actually work - I routinely have to tell people to look up the old copy when they ask me how sig hashes work 00:36 < maaku> not everyone would agree. i'm going to leave it at that. 00:37 < petertodd> gmaxwell: don't forget I've actually spent the majority of my career *way* in the other direction, creating stupidly resource constrained hardware - I've written thousands of lines of uC assembler, VHDL, etc. but the costs of that kind of development are horrendous 00:39 < maaku> yes, rusty implemented rfc6963, in terms of tree structure at least 00:40 -!- Dr-G3 is now known as BillGates 00:40 -!- BillGates is now known as Dr-G 00:40 < maaku> an efficient serialization of standard bitcoin merkle trees with the right-hashes-elided trick might work too 00:41 < maaku> (basically the same thing in terms of proof size) 00:43 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 00:46 < petertodd> right-hashes-elided trick? 00:47 -!- GAit [~lnahum@enki.greenaddressit.p3.tiktalik.io] has joined #bitcoin-wizards 00:47 < maaku> petertodd: what tiernolan has been posting about recently w.r.t merged mining 00:48 < petertodd> maaku: where's this? 00:48 < maaku> the observation that if you have a merkle tree of 2^n + 1 items, the right-most path could be fully elided by specifying the root left branch and the right most item 00:48 < maaku> bitcoin-development, maybe 2 weeks ago? 00:48 < maaku> he has a 2013 post on bitcointalk with an earlier version of it 00:48 < petertodd> oh right, that one where they're collapsed 00:49 < petertodd> pretty sure there's at least one earlier publication of that idea FWIW 00:50 < maaku> sure, probably 00:53 < maaku> petertodd: so what's the reasoning for 'bagging the peaks' in MMR vs an rfc6962 like construction? 00:54 -!- soundx [~soundx@gateway/tor-sasl/soundx] has joined #bitcoin-wizards 00:54 < petertodd> maaku: makes inclusion proofs from most recent leafs to tip as cheap as possible (amortised) - but that's only relevant in timestamping 00:55 < maaku> rfc6962 does that, no? 00:56 < petertodd> not quite as cheaply, but it's so close I'm not sure the difference is worth the effort 00:56 < petertodd> provind index # in rfc6962 is dead obvious for instance 00:57 < petertodd> *proving 00:59 < petertodd> btw another valuable thing to be able to do is prove T_{i+1} is a superset of T_i, or more generally, T_{i+j} is a superset of T_i 01:01 < petertodd> actually, superset is the wrong term for this... sucession? ie, with tree T_i that commits to array A, I want to show that if I append item a_{i+2} I get tree T_{i+1} 01:02 -!- lclc_bnc is now known as lclc 01:03 < maaku> is there a succinct way of determining the depth of index i of an MMR with N nodes? 01:04 < petertodd> of the top of my head I'm going to say probably not - wasn't a design requirement for what it was designed for 01:05 -!- andy-logbot [~bitcoin--@wpsoftware.net] has quit [Remote host closed the connection] 01:05 -!- andy-logbot [~bitcoin--@wpsoftware.net] has joined #bitcoin-wizards 01:05 * andy-logbot is logging 01:08 -!- TonyClifton [~TonyClift@gateway-nat.fmrib.ox.ac.uk] has joined #bitcoin-wizards 01:13 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Remote host closed the connection] 01:14 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 01:16 -!- gues [~gues@cpe-66-68-54-206.austin.res.rr.com] has joined #bitcoin-wizards 01:18 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Ping timeout: 265 seconds] 01:20 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 01:25 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 244 seconds] 01:25 -!- hashtag_ [~hashtagg_@CPE-69-23-213-3.wi.res.rr.com] has joined #bitcoin-wizards 01:27 -!- hashtagg [~hashtagg_@CPE-69-23-213-3.wi.res.rr.com] has quit [Ping timeout: 252 seconds] 01:32 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 01:32 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Remote host closed the connection] 01:39 -!- lclc is now known as lclc_bnc 01:39 -!- hashtagg_ [~hashtag@CPE-69-23-213-3.wi.res.rr.com] has joined #bitcoin-wizards 01:49 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 02:00 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Remote host closed the connection] 02:03 -!- hashtagg_ [~hashtag@CPE-69-23-213-3.wi.res.rr.com] has quit [Ping timeout: 244 seconds] 02:03 -!- hashtagg_ [~hashtag@CPE-69-23-213-3.wi.res.rr.com] has joined #bitcoin-wizards 02:07 -!- lclc_bnc is now known as lclc 02:15 -!- fanquake [~anonymous@unaffiliated/fanquake] has joined #bitcoin-wizards 02:21 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 02:22 -!- super3 [~Thunderbi@96-32-185-118.dhcp.gwnt.ga.charter.com] has quit [Ping timeout: 244 seconds] 02:23 -!- Shiftos [~shiftos@gateway/tor-sasl/shiftos] has quit [Ping timeout: 250 seconds] 02:24 -!- BananaLotus [~BananaLot@gateway/tor-sasl/bananalotus] has quit [Ping timeout: 250 seconds] 02:25 -!- soundx [~soundx@gateway/tor-sasl/soundx] has quit [Ping timeout: 250 seconds] 02:25 -!- Adlai [~Adlai@gateway/tor-sasl/adlai] has quit [Ping timeout: 250 seconds] 02:25 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 240 seconds] 02:31 -!- Dr-G [~Dr-G@gateway/tor-sasl/dr-g] has quit [Ping timeout: 250 seconds] 02:31 -!- Aquent [~Aquent@gateway/tor-sasl/aquent] has quit [Ping timeout: 250 seconds] 02:34 -!- BananaLotus [~BananaLot@irc.maza.club] has joined #bitcoin-wizards 02:36 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has quit [Ping timeout: 255 seconds] 02:36 -!- siraj [~siraj@158.120.0.14] has quit [Remote host closed the connection] 02:40 -!- fanquake [~anonymous@unaffiliated/fanquake] has quit [Quit: fanquake] 02:44 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has joined #bitcoin-wizards 02:45 < rusty> maaku: so, I implemented "spv path back to N != 0", and tidied things up a a bit. 02:47 < rusty> maaku: the supremacy of "optimal" is even clearer if you ask it to go back from block 5M to 5M-150. 02:47 < rusty> array: proof hashes 142-732(403.4+/-2.6e+02) 02:47 < rusty> optimal: proof hashes 33-101(63.4+/-29) 02:47 -!- Quanttek [~quassel@2a02:8108:d00:870:4045:dd0d:1bd2:496] has joined #bitcoin-wizards 02:52 -!- siraj [~siraj@158.120.0.14] has joined #bitcoin-wizards 02:55 -!- lclc is now known as lclc_bnc 02:56 -!- belcher [~belcher-s@5ec3b035.skybroadband.com] has joined #bitcoin-wizards 02:56 -!- belcher [~belcher-s@5ec3b035.skybroadband.com] has quit [Changing host] 02:56 -!- belcher [~belcher-s@unaffiliated/belcher] has joined #bitcoin-wizards 03:02 -!- NikolaiToryzin [~stqism@freebsd/user/stqism] has quit [Excess Flood] 03:02 -!- NikolaiToryzin [~stqism@freebsd/user/stqism] has joined #bitcoin-wizards 03:03 -!- [d__d] [~d__d]@ec2-54-85-45-223.compute-1.amazonaws.com] has quit [Remote host closed the connection] 03:04 -!- [d__d] [~d__d]@ec2-54-85-45-223.compute-1.amazonaws.com] has joined #bitcoin-wizards 03:05 -!- Graftec [~Graftec@gateway/tor-sasl/graftec] has quit [Remote host closed the connection] 03:06 -!- moa [~kiwigb@opentransactions/dev/moa] has quit [Quit: Leaving.] 03:10 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has quit [Excess Flood] 03:10 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has joined #bitcoin-wizards 03:11 -!- lclc_bnc is now known as lclc 03:12 < rusty> maaku: sleep time for me. Latest variant pushed, w/ two new batching trees. 03:12 < rusty> maaku: Back tomorrow, but I want to try optimizing the proof length directly rather than the path length. Maybe cache the "best" 128 blocks on the LHS of the tree, see if that wins... 03:13 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has left #bitcoin-wizards [] 03:22 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 03:22 -!- Graftec [~Graftec@gateway/tor-sasl/graftec] has joined #bitcoin-wizards 03:24 -!- espes___ [~espes@205.185.120.132] has quit [Ping timeout: 240 seconds] 03:25 -!- huseby [~huseby@unaffiliated/huseby] has quit [Ping timeout: 250 seconds] 03:32 -!- espes__ [~espes@205.185.120.132] has joined #bitcoin-wizards 03:32 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 240 seconds] 03:33 -!- siraj [~siraj@158.120.0.14] has quit [Remote host closed the connection] 03:35 -!- Graftec [~Graftec@gateway/tor-sasl/graftec] has quit [Remote host closed the connection] 03:36 -!- CoinMuncher [~jannes@178.132.211.90] has joined #bitcoin-wizards 03:36 -!- TonyClifton [~TonyClift@gateway-nat.fmrib.ox.ac.uk] has quit [Remote host closed the connection] 03:40 -!- NikolaiToryzin [~stqism@freebsd/user/stqism] has quit [Ping timeout: 240 seconds] 03:41 -!- NikolaiToryzin [~stqism@freebsd/user/stqism] has joined #bitcoin-wizards 03:42 -!- CoinMuncher [~jannes@178.132.211.90] has quit [Quit: Leaving.] 03:52 -!- Quanttek [~quassel@2a02:8108:d00:870:4045:dd0d:1bd2:496] has quit [Ping timeout: 258 seconds] 03:56 -!- huseby [~huseby@blog.linuxprogrammer.org] has joined #bitcoin-wizards 03:59 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 04:09 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has quit [Excess Flood] 04:10 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has joined #bitcoin-wizards 04:18 -!- Shiftos [~shiftos@gateway/tor-sasl/shiftos] has joined #bitcoin-wizards 04:22 -!- Guyver2 [~Guyver2@guyver2.xs4all.nl] has joined #bitcoin-wizards 04:23 -!- siraj [~siraj@158.120.0.14] has joined #bitcoin-wizards 04:26 -!- gues [~gues@cpe-66-68-54-206.austin.res.rr.com] has quit [Ping timeout: 264 seconds] 04:27 -!- gues [gues@gateway/vpn/mullvad/x-wgslrwkpohivkwcz] has joined #bitcoin-wizards 04:29 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 04:33 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has quit [Excess Flood] 04:34 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 272 seconds] 04:34 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has joined #bitcoin-wizards 04:39 -!- siraj [~siraj@158.120.0.14] has quit [Remote host closed the connection] 04:41 -!- siraj [~siraj@158.120.0.14] has joined #bitcoin-wizards 04:42 -!- siraj [~siraj@158.120.0.14] has quit [Remote host closed the connection] 04:43 -!- lclc is now known as lclc_bnc 04:43 -!- siraj [~siraj@158.120.0.14] has joined #bitcoin-wizards 04:51 -!- adam3us [~Adium@host-92-19-10-191.as13285.net] has quit [Quit: Leaving.] 04:57 -!- siraj [~siraj@158.120.0.14] has quit [Remote host closed the connection] 05:01 -!- Persopolis [~Persopoli@cpc10-haye19-2-0-cust19.17-4.cable.virginm.net] has joined #bitcoin-wizards 05:05 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Remote host closed the connection] 05:06 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 05:14 -!- Graftec [~Graftec@gateway/tor-sasl/graftec] has joined #bitcoin-wizards 05:29 -!- coiner [~linker@113.161.87.238] has quit [Ping timeout: 240 seconds] 05:29 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 05:32 -!- fanquake [~anonymous@unaffiliated/fanquake] has joined #bitcoin-wizards 05:34 -!- rfreeman_w [~rfreeman@gateway/tor-sasl/rfreemanw] has joined #bitcoin-wizards 05:34 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 244 seconds] 05:35 -!- fanquake [~anonymous@unaffiliated/fanquake] has quit [Client Quit] 05:50 -!- Profreid [~Profreitt@179.43.148.66] has joined #bitcoin-wizards 05:50 -!- kobud [wq@unaffiliated/fluffybunny] has quit [Remote host closed the connection] 05:51 -!- CoinMuncher [~jannes@178.132.211.90] has joined #bitcoin-wizards 05:53 -!- kobud [ncidsk@unaffiliated/fluffybunny] has joined #bitcoin-wizards 05:53 -!- kobud [ncidsk@unaffiliated/fluffybunny] has quit [Remote host closed the connection] 05:55 -!- kobud [wq@unaffiliated/fluffybunny] has joined #bitcoin-wizards 06:04 -!- maraoz [~maraoz@186.137.72.181] has joined #bitcoin-wizards 06:04 -!- Aquent [~Aquent@gateway/tor-sasl/aquent] has joined #bitcoin-wizards 06:10 -!- gues [gues@gateway/vpn/mullvad/x-wgslrwkpohivkwcz] has quit [Ping timeout: 252 seconds] 06:12 -!- bobke_ [~bobke@d54C6F5E8.access.telenet.be] has quit [Ping timeout: 240 seconds] 06:12 -!- gues [gues@gateway/vpn/mullvad/x-krjlkugxhnuyaaka] has joined #bitcoin-wizards 06:18 -!- bobke [~bobke@d54c6f5e8.access.telenet.be] has joined #bitcoin-wizards 06:20 -!- mortale [~mortale@gateway/tor-sasl/mortale] has joined #bitcoin-wizards 06:20 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has quit [Excess Flood] 06:20 -!- jps [~Jud@cpe-74-72-116-143.nyc.res.rr.com] has joined #bitcoin-wizards 06:21 -!- NikolaiToryzin [~stqism@freebsd/user/stqism] has quit [Ping timeout: 240 seconds] 06:21 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has joined #bitcoin-wizards 06:23 -!- NikolaiToryzin [~stqism@freebsd/user/stqism] has joined #bitcoin-wizards 06:30 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 06:32 -!- waxwing_ is now known as waxwing 06:32 -!- tromp_ [~tromp@rtc35-167.rentec.com] has joined #bitcoin-wizards 06:32 -!- Burrito [~Burrito@unaffiliated/burrito] has joined #bitcoin-wizards 06:33 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has quit [Excess Flood] 06:33 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has joined #bitcoin-wizards 06:34 -!- Adlai [~Adlai@gateway/tor-sasl/adlai] has joined #bitcoin-wizards 06:35 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 252 seconds] 06:37 -!- gonedrk [~gonedrk@d40a6497.rev.stofanet.dk] has joined #bitcoin-wizards 06:41 -!- Graftec [~Graftec@gateway/tor-sasl/graftec] has quit [Remote host closed the connection] 06:47 -!- NewLiberty [~NewLibert@2602:304:cff8:1580:4099:298e:1166:9220] has joined #bitcoin-wizards 06:47 -!- Graftec [~Graftec@gateway/tor-sasl/graftec] has joined #bitcoin-wizards 06:49 -!- CoinMuncher [~jannes@178.132.211.90] has quit [Quit: Leaving.] 06:49 -!- Quanttek [~quassel@ip1f12ed87.dynamic.kabel-deutschland.de] has joined #bitcoin-wizards 06:55 -!- gonedrk [~gonedrk@d40a6497.rev.stofanet.dk] has quit [Quit: Leaving] 07:02 -!- GAit [~lnahum@enki.greenaddressit.p3.tiktalik.io] has quit [Ping timeout: 244 seconds] 07:05 -!- Profreid [~Profreitt@179.43.148.66] has quit [Quit: Profreid] 07:21 -!- jps [~Jud@cpe-74-72-116-143.nyc.res.rr.com] has quit [Quit: jps] 07:21 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Remote host closed the connection] 07:22 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 07:26 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Ping timeout: 244 seconds] 07:28 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 07:28 -!- Dyaheon- [~dya@83-25-196-88.dyn.estpak.ee] has quit [] 07:29 -!- Shiftos [~shiftos@gateway/tor-sasl/shiftos] has quit [Remote host closed the connection] 07:29 -!- Shiftos [~shiftos@gateway/tor-sasl/shiftos] has joined #bitcoin-wizards 07:31 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 07:33 -!- Guest13730 is now known as amiller 07:33 -!- amiller [~socrates1@li175-104.members.linode.com] has quit [Changing host] 07:33 -!- amiller [~socrates1@unaffiliated/socrates1024] has joined #bitcoin-wizards 07:36 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 245 seconds] 07:37 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Remote host closed the connection] 07:37 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 07:40 -!- belcher [~belcher-s@unaffiliated/belcher] has quit [Read error: Connection reset by peer] 07:42 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Ping timeout: 264 seconds] 07:44 -!- GAit [~lnahum@enki.greenaddressit.p3.tiktalik.io] has joined #bitcoin-wizards 07:44 -!- belcher [~belcher-s@5ec3b035.skybroadband.com] has joined #bitcoin-wizards 07:45 -!- belcher [~belcher-s@5ec3b035.skybroadband.com] has quit [Changing host] 07:45 -!- belcher [~belcher-s@unaffiliated/belcher] has joined #bitcoin-wizards 07:47 -!- prepost [rs232@gateway/vpn/mullvad/x-zvtclsjseuajlcyj] has joined #bitcoin-wizards 07:53 -!- zooko [~user@68.233.149.129] has joined #bitcoin-wizards 07:56 -!- cbeams [~cbeams@chello084114181075.1.15.vie.surfer.at] has joined #bitcoin-wizards 07:56 -!- cbeams [~cbeams@chello084114181075.1.15.vie.surfer.at] has quit [Changing host] 07:56 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 08:01 -!- adam3us [~Adium@host-92-19-10-191.as13285.net] has joined #bitcoin-wizards 08:09 -!- gues [gues@gateway/vpn/mullvad/x-krjlkugxhnuyaaka] has quit [Ping timeout: 245 seconds] 08:12 -!- Guest98671 [~Pan0ram1x@095-096-084-122.static.chello.nl] has quit [Ping timeout: 265 seconds] 08:14 -!- Tjopper [~Jop@dhcp-077-249-237-229.chello.nl] has joined #bitcoin-wizards 08:16 -!- coiner [~linker@1.54.73.86] has joined #bitcoin-wizards 08:18 -!- Pan0ram1x [~Pan0ram1x@095-096-084-122.static.chello.nl] has joined #bitcoin-wizards 08:19 -!- Pan0ram1x is now known as Guest89604 08:23 -!- Guyver2 [~Guyver2@guyver2.xs4all.nl] has left #bitcoin-wizards [] 08:33 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 08:34 -!- maraoz [~maraoz@186.137.72.181] has quit [Ping timeout: 255 seconds] 08:37 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 245 seconds] 08:42 -!- user7779078 [user777907@gateway/vpn/mullvad/x-ggdnutqparejvdlr] has joined #bitcoin-wizards 08:50 -!- maraoz [~maraoz@186.137.72.181] has joined #bitcoin-wizards 08:53 -!- soundx [~soundx@gateway/tor-sasl/soundx] has joined #bitcoin-wizards 09:04 -!- hearn [~mike@cpc8-macc3-2-0-cust245.1-3.cable.virginm.net] has joined #bitcoin-wizards 09:33 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 09:34 -!- devrandom [~devrandom@gateway/tor-sasl/niftyzero1] has joined #bitcoin-wizards 09:35 -!- soundx [~soundx@gateway/tor-sasl/soundx] has quit [Remote host closed the connection] 09:38 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 244 seconds] 09:38 -!- belcher [~belcher-s@unaffiliated/belcher] has quit [Read error: Connection reset by peer] 09:39 -!- huseby [~huseby@blog.linuxprogrammer.org] has quit [Changing host] 09:39 -!- huseby [~huseby@unaffiliated/huseby] has joined #bitcoin-wizards 09:40 -!- afk11 [~afk11@89.100.72.228] has joined #bitcoin-wizards 09:49 -!- belcher [~belcher-s@5ec3b035.skybroadband.com] has joined #bitcoin-wizards 09:49 -!- belcher [~belcher-s@5ec3b035.skybroadband.com] has quit [Changing host] 09:49 -!- belcher [~belcher-s@unaffiliated/belcher] has joined #bitcoin-wizards 09:58 -!- devrandom [~devrandom@gateway/tor-sasl/niftyzero1] has quit [Ping timeout: 250 seconds] 10:02 -!- devrandom [~devrandom@gateway/tor-sasl/niftyzero1] has joined #bitcoin-wizards 10:02 -!- Shiftos [~shiftos@gateway/tor-sasl/shiftos] has quit [Remote host closed the connection] 10:04 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has quit [Excess Flood] 10:05 -!- Luke-Jr [~luke-jr@unaffiliated/luke-jr] has joined #bitcoin-wizards 10:05 -!- bosma_ [~bosma@S01067cb21bda6531.vc.shawcable.net] has joined #bitcoin-wizards 10:05 -!- devrando1 [~devrandom@gateway/tor-sasl/niftyzero1] has joined #bitcoin-wizards 10:06 -!- devrandom [~devrandom@gateway/tor-sasl/niftyzero1] has quit [Ping timeout: 250 seconds] 10:06 -!- bosma [~bosma@S01067cb21bda6531.vc.shawcable.net] has quit [Ping timeout: 240 seconds] 10:09 -!- soundx [~soundx@gateway/tor-sasl/soundx] has joined #bitcoin-wizards 10:10 -!- soundx [~soundx@gateway/tor-sasl/soundx] has quit [Remote host closed the connection] 10:11 -!- soundx [~soundx@gateway/tor-sasl/soundx] has joined #bitcoin-wizards 10:11 -!- Profreid [~Profreitt@91.108.183.178] has joined #bitcoin-wizards 10:15 -!- soundx [~soundx@gateway/tor-sasl/soundx] has quit [Ping timeout: 250 seconds] 10:20 -!- devrando1 [~devrandom@gateway/tor-sasl/niftyzero1] has quit [Quit: leaving] 10:20 -!- devrandom [~devrandom@gateway/tor-sasl/niftyzero1] has joined #bitcoin-wizards 10:23 -!- licnep [uid4387@gateway/web/irccloud.com/x-mgfnntdozsodvnqe] has joined #bitcoin-wizards 10:28 -!- pavel_ [~paveljani@79-98-72-216.sys-data.com] has joined #bitcoin-wizards 10:29 -!- paveljanik [~paveljani@unaffiliated/paveljanik] has quit [Ping timeout: 245 seconds] 10:31 -!- pavel_ [~paveljani@79-98-72-216.sys-data.com] has quit [Client Quit] 10:31 -!- paveljanik [~paveljani@79-98-72-216.sys-data.com] has joined #bitcoin-wizards 10:31 -!- paveljanik [~paveljani@79-98-72-216.sys-data.com] has quit [Changing host] 10:31 -!- paveljanik [~paveljani@unaffiliated/paveljanik] has joined #bitcoin-wizards 10:34 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 10:36 -!- mortale [~mortale@gateway/tor-sasl/mortale] has quit [Ping timeout: 250 seconds] 10:37 -!- NewLiberty [~NewLibert@2602:304:cff8:1580:4099:298e:1166:9220] has quit [Ping timeout: 258 seconds] 10:38 -!- NewLiberty [~NewLibert@2602:304:cff8:1580:6156:df06:de8a:8e51] has joined #bitcoin-wizards 10:39 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 272 seconds] 10:40 -!- mortale [~mortale@gateway/tor-sasl/mortale] has joined #bitcoin-wizards 10:46 -!- paveljanik [~paveljani@unaffiliated/paveljanik] has quit [Quit: This computer has gone to sleep] 10:47 -!- tlrobinson [~tlrobinso@204.14.159.136] has joined #bitcoin-wizards 10:53 -!- paveljanik [~paveljani@79-98-72-216.sys-data.com] has joined #bitcoin-wizards 10:53 -!- paveljanik [~paveljani@79-98-72-216.sys-data.com] has quit [Changing host] 10:53 -!- paveljanik [~paveljani@unaffiliated/paveljanik] has joined #bitcoin-wizards 11:02 -!- user7779078 [user777907@gateway/vpn/mullvad/x-ggdnutqparejvdlr] has quit [Remote host closed the connection] 11:02 -!- damethos [~damethos@unaffiliated/damethos] has joined #bitcoin-wizards 11:05 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Remote host closed the connection] 11:05 -!- user7779_ [user777907@gateway/vpn/mullvad/x-qehugaqkpemstepk] has joined #bitcoin-wizards 11:14 -!- cbeams [~cbeams@chello084114181075.1.15.vie.surfer.at] has joined #bitcoin-wizards 11:14 -!- cbeams [~cbeams@chello084114181075.1.15.vie.surfer.at] has quit [Changing host] 11:14 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 11:22 -!- soundx [~soundx@gateway/tor-sasl/soundx] has joined #bitcoin-wizards 11:25 -!- Quanttek [~quassel@ip1f12ed87.dynamic.kabel-deutschland.de] has quit [Ping timeout: 250 seconds] 11:26 -!- soundx [~soundx@gateway/tor-sasl/soundx] has quit [Ping timeout: 250 seconds] 11:32 -!- user7779_ [user777907@gateway/vpn/mullvad/x-qehugaqkpemstepk] has quit [Ping timeout: 265 seconds] 11:35 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 11:40 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 244 seconds] 11:41 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Remote host closed the connection] 11:41 -!- Guest99220 [~omni@ip68-4-111-228.oc.oc.cox.net] has quit [Remote host closed the connection] 11:42 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 11:43 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Read error: Connection reset by peer] 11:43 -!- maraoz [~maraoz@186.137.72.181] has quit [Ping timeout: 245 seconds] 11:43 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 11:47 -!- Guest29370 is now known as mr_burdell 11:47 -!- mr_burdell [~mr_burdel@hop.cryptolabs.net] has quit [Changing host] 11:47 -!- mr_burdell [~mr_burdel@unaffiliated/mr-burdell/x-7609603] has joined #bitcoin-wizards 11:48 -!- maraoz [~maraoz@186.137.72.181] has joined #bitcoin-wizards 11:53 -!- artifexd_ is now known as artifexd 11:56 -!- tlrobinson [~tlrobinso@204.14.159.136] has quit [Ping timeout: 244 seconds] 11:59 -!- iang [~iang@cpc3-lewi16-2-0-cust561.2-4.cable.virginm.net] has joined #bitcoin-wizards 12:00 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Remote host closed the connection] 12:01 -!- user7779078 [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has joined #bitcoin-wizards 12:06 -!- gues [gues@gateway/vpn/mullvad/x-klfcfqefdiprwqmd] has joined #bitcoin-wizards 12:09 < kanzure> adam3us: typos? anti-relay -> anti-replay 12:17 -!- adam3us1 [~Adium@host-92-18-108-128.as13285.net] has joined #bitcoin-wizards 12:19 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 12:19 -!- adam3us [~Adium@host-92-19-10-191.as13285.net] has quit [Ping timeout: 240 seconds] 12:20 -!- ryanxcharles [~ryanxchar@2601:9:4680:dd0:8cec:2a9:c0d0:ce8c] has quit [Ping timeout: 258 seconds] 12:21 -!- user7779078 [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has quit [Read error: Connection reset by peer] 12:22 -!- user7779078 [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has joined #bitcoin-wizards 12:23 -!- tlrobinson [~tlrobinso@204.14.159.136] has joined #bitcoin-wizards 12:30 -!- omni [~omni@ip68-4-111-228.oc.oc.cox.net] has joined #bitcoin-wizards 12:30 -!- omni is now known as Guest17853 12:31 -!- Persopolis [~Persopoli@cpc10-haye19-2-0-cust19.17-4.cable.virginm.net] has quit [] 12:43 -!- belcher [~belcher-s@unaffiliated/belcher] has quit [Ping timeout: 240 seconds] 12:45 -!- belcher [~belcher-s@5ec3b035.skybroadband.com] has joined #bitcoin-wizards 12:45 -!- belcher [~belcher-s@5ec3b035.skybroadband.com] has quit [Changing host] 12:45 -!- belcher [~belcher-s@unaffiliated/belcher] has joined #bitcoin-wizards 12:59 -!- maraoz [~maraoz@186.137.72.181] has quit [Ping timeout: 245 seconds] 13:06 < amiller> adam3us1, everyone meant "anti-replay", not "anti-relay", but you seem to be responding as though you read it as "anti-relay" 13:07 < amiller> or maybe you didn't and it's a benign typo in either case 13:08 < sipa> a proof-of-non-relay seems quite impossible :) 13:13 -!- maraoz [~maraoz@186.137.72.181] has joined #bitcoin-wizards 13:14 -!- vmatekole [~vmatekole@p5DC47ED9.dip0.t-ipconnect.de] has quit [Ping timeout: 272 seconds] 13:18 < gmaxwell> sipa: it's called quantum encryption? :P 13:18 < sipa> Hey. No novel assumptions. 13:19 -!- beamlaser [835ebaa3@gateway/web/freenode/ip.131.94.186.163] has joined #bitcoin-wizards 13:19 -!- wizkid057 [wk@unaffiliated/wizkid057] has quit [Disconnected by services] 13:19 -!- wizkid057 [wk@unaffiliated/wizkid057] has joined #bitcoin-wizards 13:21 -!- damethos [~damethos@unaffiliated/damethos] has quit [Quit: Bye] 13:26 -!- Dr-G [~Dr-G@gateway/tor-sasl/dr-g] has joined #bitcoin-wizards 13:43 -!- narwh4l [~michael@unaffiliated/thesnark] has joined #bitcoin-wizards 13:48 -!- vmatekole [~vmatekole@217.115.146.110] has joined #bitcoin-wizards 13:51 -!- maraoz [~maraoz@186.137.72.181] has quit [Ping timeout: 245 seconds] 13:51 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has joined #bitcoin-wizards 13:55 -!- bosma_ is now known as bosma 13:56 -!- soundx [~soundx@gateway/tor-sasl/soundx] has joined #bitcoin-wizards 13:56 -!- c0rw1n_ is now known as c0rw1n 13:58 -!- soundx_ [~soundx@gateway/tor-sasl/soundx] has joined #bitcoin-wizards 13:59 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has quit [Ping timeout: 240 seconds] 14:00 -!- soundx [~soundx@gateway/tor-sasl/soundx] has quit [Ping timeout: 250 seconds] 14:02 -!- Guest17853 [~omni@ip68-4-111-228.oc.oc.cox.net] has quit [Remote host closed the connection] 14:03 -!- iang [~iang@cpc3-lewi16-2-0-cust561.2-4.cable.virginm.net] has quit [Quit: iang] 14:04 -!- omni [~omni@ip68-4-111-228.oc.oc.cox.net] has joined #bitcoin-wizards 14:04 -!- omni is now known as Guest20839 14:06 -!- user7779_ [user777907@gateway/vpn/mullvad/x-wfyxppaezsivojar] has joined #bitcoin-wizards 14:07 -!- vmatekole [~vmatekole@217.115.146.110] has quit [Remote host closed the connection] 14:08 -!- user7779078 [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has quit [Ping timeout: 244 seconds] 14:13 -!- Quanttek [~quassel@ip1f12ed87.dynamic.kabel-deutschland.de] has joined #bitcoin-wizards 14:24 -!- Profreid_ [~Profreitt@179.43.128.34] has joined #bitcoin-wizards 14:25 -!- siraj [~siraj@adsl-68-93-64-210.dsl.hstntx.swbell.net] has joined #bitcoin-wizards 14:26 -!- orik [~orik@75.149.169.53] has joined #bitcoin-wizards 14:26 -!- Profreid [~Profreitt@91.108.183.178] has quit [Ping timeout: 244 seconds] 14:26 -!- Profreid_ is now known as Profreid 14:29 -!- Profreid [~Profreitt@179.43.128.34] has quit [Quit: Profreid] 14:36 -!- siraj [~siraj@adsl-68-93-64-210.dsl.hstntx.swbell.net] has quit [Remote host closed the connection] 14:39 -!- gues [gues@gateway/vpn/mullvad/x-klfcfqefdiprwqmd] has quit [Ping timeout: 244 seconds] 14:40 -!- siraj [~siraj@adsl-68-93-64-210.dsl.hstntx.swbell.net] has joined #bitcoin-wizards 14:41 -!- gues [gues@gateway/vpn/mullvad/x-imiyplwjdersoexz] has joined #bitcoin-wizards 14:44 -!- siraj [~siraj@adsl-68-93-64-210.dsl.hstntx.swbell.net] has quit [Ping timeout: 240 seconds] 14:51 -!- d1ggy [~d1ggy@cable-62-117-16-154.cust.telecolumbus.net] has joined #bitcoin-wizards 14:51 -!- gues [gues@gateway/vpn/mullvad/x-imiyplwjdersoexz] has quit [Ping timeout: 245 seconds] 14:52 -!- jtimon [~quassel@159.pool85-59-61.dynamic.orange.es] has quit [Ping timeout: 244 seconds] 14:53 -!- gues [~gues@cpe-66-68-54-206.austin.res.rr.com] has joined #bitcoin-wizards 14:57 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has joined #bitcoin-wizards 15:00 -!- adam3us1 [~Adium@host-92-18-108-128.as13285.net] has quit [Quit: Leaving.] 15:00 -!- licnep [uid4387@gateway/web/irccloud.com/x-mgfnntdozsodvnqe] has quit [Quit: Connection closed for inactivity] 15:12 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Read error: Connection reset by peer] 15:13 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 15:17 -!- cbeams [~cbeams@unaffiliated/cbeams] has joined #bitcoin-wizards 15:18 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Read error: Connection reset by peer] 15:18 -!- davejh69 [~davejh69@fence.blueteddy.net] has joined #bitcoin-wizards 15:24 -!- user7779_ [user777907@gateway/vpn/mullvad/x-wfyxppaezsivojar] has quit [Remote host closed the connection] 15:27 -!- d1ggy [~d1ggy@cable-62-117-16-154.cust.telecolumbus.net] has quit [Ping timeout: 240 seconds] 15:30 -!- cbeams [~cbeams@unaffiliated/cbeams] has quit [Ping timeout: 245 seconds] 15:31 -!- dgenr8 [~dgenr8@unaffiliated/dgenr8] has joined #bitcoin-wizards 15:32 -!- soundx [~soundx@gateway/tor-sasl/soundx] has joined #bitcoin-wizards 15:33 -!- soundx_ [~soundx@gateway/tor-sasl/soundx] has quit [Ping timeout: 250 seconds] 15:34 -!- soundx_ [~soundx@gateway/tor-sasl/soundx] has joined #bitcoin-wizards 15:34 -!- user7779078 [~user77790@193.138.219.233] has joined #bitcoin-wizards 15:36 -!- beamlaser [835ebaa3@gateway/web/freenode/ip.131.94.186.163] has quit [Ping timeout: 246 seconds] 15:36 -!- soundx [~soundx@gateway/tor-sasl/soundx] has quit [Ping timeout: 250 seconds] 15:38 -!- Transisto [~Trans@modemcable026.188-59-74.mc.videotron.ca] has quit [] 15:40 -!- siraj [~siraj@adsl-68-93-64-210.dsl.hstntx.swbell.net] has joined #bitcoin-wizards 15:40 -!- user7779078 [~user77790@193.138.219.233] has quit [Remote host closed the connection] 15:43 < rusty> maaku: OK, so I 15:44 < rusty> 've implemented optimization-by-prooflen (rather than optimization by pathlen, then convert to proof). It does make a difference. 15:44 < rusty> eg: (1M blocks, 100 runs): 15:45 < rusty> optimal: proof hashes 315-2143(1031.7+/-5.6e+02) <- old result 15:45 < rusty> prooflen-optimal: proof hashes 265-1719(818.2+/-4.4e+02) <- new result 15:45 -!- siraj [~siraj@adsl-68-93-64-210.dsl.hstntx.swbell.net] has quit [Ping timeout: 245 seconds] 15:45 < rusty> 20% smaller CSPV proofs, basically 15:45 < sipa> how is the size of blocks relevant? 15:46 < rusty> sipa: the size of the merkle proof, not the block... 15:46 < sipa> ah, 1 million blocks, not 1 MB blocks; sure 15:46 < sipa> rusty: i've previously implemented that too 15:46 < sipa> i don't think i have that code anymore 15:46 < rusty> sipa: cool! I'm playing with different topologies for the prevblock merkle. 15:47 < sipa> trying to remember what structure i used 15:47 < rusty> sipa: see https://github.com/rustyrussell/rusty-junkcode (particularly test-trees.c) 15:48 < rusty> sipa: topology makes a big difference. But it was only last night I realized that optimizing SPV # blocks then converting to proof was kinda dumb. 15:48 < rusty> sipa: so implemented that now instead of doing actual work :) 15:49 < sipa> now, one interesting thing is that even a 'skiplist' with only a single reference back (in addition to the direct parent), with exponentially distributed distance back is enough to get within (iirc) a constant factor of optimal 15:50 < rusty> sipa: Hmm, interesting! 15:50 < rusty> sipa: how did you select distance back for block N? 15:51 -!- davejh69 [~davejh69@fence.blueteddy.net] has quit [Ping timeout: 245 seconds] 15:51 < rusty> (I'm trying to parse "exponentially distributed distance back" with "single reference back"... and failing?) 15:52 < sipa> so every block has two references back, its direct parent, and another 15:52 < rusty> Yep, how do you select "another"? 15:52 < sipa> that other is 50% of the time 2 back, 25% of the time 4 back, 12.5% of the 8 back, ... 15:53 < rusty> sipa: ah, nice. Let me simulate that... 15:53 < sipa> iirc it's something like 4x worse 15:53 * rusty continues to ignore that module bug email... 15:53 < sipa> https://github.com/bitcoin/bitcoin/blob/master/src/chain.cpp#L64-L73 <- this is a slightly more complex formula, used in bitcoin itself now 15:53 < sipa> after trying a dozen functions or so, this one was the best 15:55 < rusty> sipa: weird, I didn't know bitcoin had this already! 15:55 < sipa> this is just an implementation detail, to speed up iterating chains 15:55 < gmaxwell> rusty: totally different application, thats an in memory data structure used for node-internal blockchain management. 15:56 < rusty> sipa/gmaxwell: thanks. 15:56 < sipa> in cases where only the size of a proof and not the entire storage matters, this is definitely suboptimal 15:56 -!- Transisto [~Trans@modemcable026.188-59-74.mc.videotron.ca] has joined #bitcoin-wizards 15:56 < sipa> but it's interesting that it's only a constant factor (but a significant one) worse 15:56 < sipa> (iirc, again, this is just how i remember the numbers i saw - no formal proof or anything) 15:57 < rusty> sipa: well, I'll code it up anyway, since I'm here. Plus, procrastination... 15:57 < gmaxwell> the difference in the comitted structure is that you don't have free choice of where you go back unless you commit to all. So e.g. just a constant single backref would usually just not be accessible. 15:59 < gmaxwell> When we were expirementing before I just used octave backrefs with the optimization that if an already included shorter backref was a better path to genesis, in the DP solution, I omitted it. But maaku pointed out that results in long paths to get to anything except genesis. 16:00 -!- epscy [~epscy@176.126.241.239] has quit [Quit: WeeChat 0.4.2] 16:00 -!- Shiftos [~shiftos@gateway/tor-sasl/shiftos] has joined #bitcoin-wizards 16:03 < phantomcircuit> sipa, any idea if that's just because of the current blockchain structure and not necessarily a constant optimum? 16:03 < 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. 16:06 < rusty> sipa: um, crazy idea. What if you select from the "best" blocks (ie. largest backskip) rather than just using exponential choice? 16:07 -!- petahash [~fordlinco@d173-183-97-143.bchsia.telus.net] has joined #bitcoin-wizards 16:08 * rusty needs more coffee... 16:12 -!- hashtagg [~hashtagg_@CPE-69-23-213-3.wi.res.rr.com] has joined #bitcoin-wizards 16:15 -!- hashtag_ [~hashtagg_@CPE-69-23-213-3.wi.res.rr.com] has quit [Ping timeout: 244 seconds] 16:25 -!- alferzz [~alferz@109.201.154.199] has joined #bitcoin-wizards 16:27 -!- alferzz is now known as alferz 16:27 -!- alferz [~alferz@109.201.154.199] has quit [Changing host] 16:27 -!- alferz [~alferz@unaffiliated/alfer] has joined #bitcoin-wizards 16:28 -!- tlrobinson [~tlrobinso@204.14.159.136] has quit [Quit: tlrobinson] 16:31 -!- siervo [uid49244@gateway/web/irccloud.com/x-mugpstdtisansipn] has joined #bitcoin-wizards 16:37 -!- iang [~iang@cpc3-lewi16-2-0-cust561.2-4.cable.virginm.net] has joined #bitcoin-wizards 16:37 < 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. 16:38 < rusty> sipa: of course, that could be terribly unlucky. Running with 100 different seeds now. 16:38 -!- hearn [~mike@cpc8-macc3-2-0-cust245.1-3.cable.virginm.net] has quit [Quit: My MacBook Pro has gone to sleep. ZZZzzz…] 16:41 -!- orik [~orik@75.149.169.53] has quit [Ping timeout: 265 seconds] 16:43 -!- paveljanik [~paveljani@unaffiliated/paveljanik] has quit [Quit: This computer has gone to sleep] 16:43 < sipa> rusty: is that the optimal path? 16:43 < sipa> rusty: also, see the code in bitcoin i linked you to 16:44 < rusty> sipa: yep, taking the backlink if dist < overkill. 16:44 < sipa> rusty: that doesn't guarantee optimality 16:44 < rusty> sipa: s/taking/considering/. 16:44 < sipa> you need dynamic programming to find the optimal solution 16:44 < sipa> and for random exponential links, that probably matters a lot 16:45 < rusty> sipa: yeah, already doing that. Of course, may have a bug :) 16:45 < sipa> ideally, finding the optimal path would mean just eager matching 16:46 -!- tacotime [~mashkeys@198.52.200.63] has quit [Ping timeout: 272 seconds] 16:51 -!- Quanttek [~quassel@ip1f12ed87.dynamic.kabel-deutschland.de] has quit [Ping timeout: 245 seconds] 16:52 -!- hashtag_ [~hashtag@CPE-69-23-213-3.wi.res.rr.com] has joined #bitcoin-wizards 16:52 < 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.... 16:54 < sipa> rusty: see the code i linked you to! 16:55 < rusty> sipa: sure, I'll try that next. 16:55 -!- hashtagg [~hashtagg_@CPE-69-23-213-3.wi.res.rr.com] has quit [Ping timeout: 252 seconds] 16:55 -!- hashtagg_ [~hashtag@CPE-69-23-213-3.wi.res.rr.com] has quit [Ping timeout: 240 seconds] 16:55 < sipa> it's made so that further backlinks are likely to very quickly hit other far backlinks 16:55 -!- hashtagg [~hashtagg_@CPE-69-23-213-3.wi.res.rr.com] has joined #bitcoin-wizards 16:55 < sipa> maybe just random backlinks without structure isn't enough 17:03 -!- iang [~iang@cpc3-lewi16-2-0-cust561.2-4.cable.virginm.net] has quit [Quit: iang] 17:05 < 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). 17:06 < rusty> sipa: in summary, I'm not convinced that there's a constant factor in this case. 17:06 < sipa> eh? 17:06 < sipa> i have trouble reading your numbers :) 17:06 < rusty> sipa: sorry, that's min - max ( mean +/0 stddev) 17:06 < sipa> what unit? 17:07 < 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). 17:07 < sipa> it should be around 150 or so 17:10 -!- tacotime [~mashkeys@198.52.200.63] has joined #bitcoin-wizards 17:10 < rusty> sipa: Maybe. See https://github.com/rustyrussell/rusty-junkcode 17:11 < 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. 17:12 < sipa> yeah, i agree 17:12 < sipa> rusty: GetSkipHeight gives the height to jump to, not how far to jump back 17:12 < rusty> sipa: hence backjump = i - GetSkipHeight(i) 17:12 < sipa> ah, yes! 17:13 < sipa> sorry 17:13 < rusty> sipa: I'm sure there are dumb errors, but hopefully they're better hidden than that :) 17:14 -!- afk11 [~afk11@89.100.72.228] has quit [Ping timeout: 245 seconds] 17:15 -!- Cory [~Cory@unaffiliated/cory] has joined #bitcoin-wizards 17:17 < sipa> rusty: why the rng in the decision loop? 17:18 < rusty> sipa: you referring to -1ULL / isaac64_next_uint64(&isaac) ? 17:18 < sipa> yes 17:18 < rusty> sipa: I pick a random u64 as my "block hash", and 0xFFFF.... as my target. 17:19 < sipa> ah 17:19 < rusty> sipa: hence -1ULL / random() => amount I can skip backwards. 17:19 < sipa> right 17:19 < sipa> yeah, if you can't always jump back, i'm sure this solution is worthless 17:19 < sipa> sorry, i shouldn't have brought it up here 17:19 < sipa> it's interesting, but it's a very different problem 17:19 < rusty> sipa: hey, it was fun! 17:20 < sipa> iirc i experimented with just all powers of 2 backwards 17:20 < sipa> which needs a way smaller tree, so fewer hashes per link to use in the proof 17:21 < sipa> and eager selection when jumping back (as far as you can) 17:22 -!- petahash [~fordlinco@d173-183-97-143.bchsia.telus.net] has quit [Quit: Leaving] 17:23 -!- Shiftos [~shiftos@gateway/tor-sasl/shiftos] has quit [Remote host closed the connection] 17:23 -!- siraj [~siraj@adsl-68-93-64-210.dsl.hstntx.swbell.net] has joined #bitcoin-wizards 17:24 -!- Shiftos [~shiftos@gateway/tor-sasl/shiftos] has joined #bitcoin-wizards 17:24 < rusty> sipa: I did that for pettycoin, too. Eager selection was a large factor worse than a real shortest calc though. 17:24 < sipa> possibly, yes 17:28 -!- siraj [~siraj@adsl-68-93-64-210.dsl.hstntx.swbell.net] has quit [Ping timeout: 244 seconds] 17:30 -!- ryanxcharles [~ryanxchar@2601:9:4680:dd0:958b:8451:87eb:ce30] has joined #bitcoin-wizards 17:39 -!- narwh4l [~michael@unaffiliated/thesnark] has quit [Quit: "sleeptime"] 17:43 -!- Burrito [~Burrito@unaffiliated/burrito] has quit [Quit: Leaving] 17:52 -!- ryanxcharles [~ryanxchar@2601:9:4680:dd0:958b:8451:87eb:ce30] has quit [Ping timeout: 258 seconds] 17:56 -!- siraj [~siraj@adsl-68-93-64-210.dsl.hstntx.swbell.net] has joined #bitcoin-wizards 17:59 -!- soundx_ [~soundx@gateway/tor-sasl/soundx] has quit [Remote host closed the connection] 18:01 -!- ryanxcharles [~ryanxchar@2601:9:4680:dd0:958b:8451:87eb:ce30] has joined #bitcoin-wizards 18:05 -!- belcher [~belcher-s@unaffiliated/belcher] has quit [Ping timeout: 240 seconds] 18:11 -!- user7779078 [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has joined #bitcoin-wizards 18:11 -!- siervo [uid49244@gateway/web/irccloud.com/x-mugpstdtisansipn] has quit [] 18:19 -!- licnep [uid4387@gateway/web/irccloud.com/x-hvgmevqqxvoolvao] has joined #bitcoin-wizards 18:24 -!- user7779_ [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has joined #bitcoin-wizards 18:26 -!- user7779078 [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has quit [Ping timeout: 256 seconds] 18:26 -!- user777__ [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has joined #bitcoin-wizards 18:30 -!- user7779_ [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has quit [Ping timeout: 272 seconds] 18:32 -!- Dr-G2 [~Dr-G@gateway/tor-sasl/dr-g] has joined #bitcoin-wizards 18:32 -!- user7779078 [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has joined #bitcoin-wizards 18:33 -!- user777__ [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has quit [Ping timeout: 245 seconds] 18:35 -!- Dr-G [~Dr-G@gateway/tor-sasl/dr-g] has quit [Ping timeout: 250 seconds] 18:36 -!- jps [~Jud@cpe-74-72-116-143.nyc.res.rr.com] has joined #bitcoin-wizards 18:54 -!- user7779078 [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has quit [Ping timeout: 264 seconds] 19:03 -!- maaku [~quassel@173-228-107-141.dsl.static.fusionbroadband.com] has quit [Ping timeout: 245 seconds] 19:25 -!- tlrobinson [~tlrobinso@204.14.159.136] has joined #bitcoin-wizards 19:27 -!- MoALTz_ [~no@user-164-126-31-182.play-internet.pl] has joined #bitcoin-wizards 19:30 -!- MoALTz [~no@user-164-126-31-182.play-internet.pl] has quit [Ping timeout: 258 seconds] 19:53 -!- SDCDev [~quassel@unaffiliated/sdcdev] has quit [Ping timeout: 250 seconds] 20:07 -!- Guest20839 [~omni@ip68-4-111-228.oc.oc.cox.net] has quit [Remote host closed the connection] 20:11 -!- Aquent [~Aquent@gateway/tor-sasl/aquent] has quit [Ping timeout: 250 seconds] 20:26 -!- siraj [~siraj@adsl-68-93-64-210.dsl.hstntx.swbell.net] has quit [Remote host closed the connection] 20:33 -!- TheSeven [~quassel@rockbox/developer/TheSeven] has quit [Ping timeout: 244 seconds] 20:34 -!- TheSeven [~quassel@rockbox/developer/TheSeven] has joined #bitcoin-wizards 20:35 -!- coiner [~linker@1.54.73.86] has quit [Ping timeout: 245 seconds] 20:38 -!- omni [~omni@ip68-4-111-228.oc.oc.cox.net] has joined #bitcoin-wizards 20:38 -!- omni is now known as Guest22056 20:50 -!- licnep [uid4387@gateway/web/irccloud.com/x-hvgmevqqxvoolvao] has quit [Quit: Connection closed for inactivity] 20:59 -!- user7779078 [user777907@gateway/vpn/mullvad/x-abiqvkgawijpomqy] has joined #bitcoin-wizards 20:59 -!- hashtag_ [~hashtag@CPE-69-23-213-3.wi.res.rr.com] has quit [Ping timeout: 244 seconds] 21:11 -!- jps [~Jud@cpe-74-72-116-143.nyc.res.rr.com] has quit [Quit: jps] 21:41 -!- spinza [~spin@197.89.19.57] has quit [Ping timeout: 240 seconds] 21:46 -!- rusty [~rusty@pdpc/supporter/bronze/rusty] has quit [Quit: Leaving.] 21:47 -!- zooko [~user@68.233.149.129] has quit [Ping timeout: 265 seconds] 22:28 -!- coiner [~linker@113.161.87.238] has joined #bitcoin-wizards 22:32 -!- maaku [~quassel@173-228-107-141.dsl.static.fusionbroadband.com] has joined #bitcoin-wizards 22:32 -!- maaku is now known as Guest2758 22:33 -!- Guest2758 is now known as maaku 22:38 -!- user7779078 [user777907@gateway/vpn/mullvad/x-abiqvkgawijpomqy] has quit [Remote host closed the connection] 22:39 -!- user7779078 [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has joined #bitcoin-wizards 22:41 -!- user7779_ [~user77790@193.138.219.233] has joined #bitcoin-wizards 22:44 -!- user7779078 [~user77790@c-73-1-104-107.hsd1.fl.comcast.net] has quit [Ping timeout: 272 seconds] 22:53 -!- aburan28 [~ubuntu@static-108-45-93-73.washdc.fios.verizon.net] has joined #bitcoin-wizards 22:54 < maaku> so I added an MMR estimator to rusty's code, and it does worse than rfc6962 22:54 < maaku> i'm a bit surprised about that 23:04 -!- user7779_ [~user77790@193.138.219.233] has quit [] 23:43 -!- MoALTz__ [~no@user-164-126-31-182.play-internet.pl] has joined #bitcoin-wizards 23:46 -!- MoALTz_ [~no@user-164-126-31-182.play-internet.pl] has quit [Ping timeout: 258 seconds] 23:47 -!- MoALTz_ [~no@user-164-126-31-182.play-internet.pl] has joined #bitcoin-wizards 23:50 -!- MoALTz__ [~no@user-164-126-31-182.play-internet.pl] has quit [Ping timeout: 264 seconds]