00:15:50rusty:gmaxwell: am trying to apply https://en.bitcoin.it/wiki/User:Gmaxwell/block_network_coding to your server idea for the data unavailability solution. Have many dumb questions, if you have a moment.
00:29:52rusty:gmaxwell: in particular, how would you encode the data such that the sizeof(data + overhead) responses would allow it all to be recovered?
01:00:44c0rw1n:c0rw1n is now known as c0rw|sleep
01:01:15kanzure:andytoshi: https://gitweb.torproject.org/tor.git/blob_plain/HEAD:/src/or/circuitbuild.c
01:03:07sipa:rusty: i haven't read gmaxwell's text, but i know it relies on forward error correction codes
01:03:52sipa:i you haven't heard about it, https://en.wikipedia.org/wiki/Fountain_code may be interesting
01:06:17rusty:sipa: ah, thanks, that's the clue I was missing. Well, one of them :)
01:09:52Burnin8:Burnin8 has left #bitcoin-wizards
01:43:05kanzure:http://diyhpl.us/~bryan/papers2/security/The%20Pynchon%20Gate:%20A%20secure%20method%20of%20pseudonymous%20mail%20retrieval%20-%20Len%20Sassaman%20-%20Bram%20Cohen%20-%20Nick%20Mathewson.pdf
01:45:06kanzure:it always seemed a little strange to associate this work with email in particular
01:45:11kanzure:out of all the possible protocols to be working with
01:45:43kanzure:maybe that is camelflage
01:45:57kanzure:camouflage
01:50:36kanzure:protocol spec http://web.archive.org/web/20090406081037/http://www.abditum.com/pynchon
01:51:18kanzure:http://web.archive.org/web/20090408052657/http://freehaven.net/pynchon/doc/pynchon-spec.txt
02:13:41nsh:* nsh double-underlines "replace all spaces in kanzure's papers folder with underscores" in mental to-do list
02:14:16kanzure:underscores are hard to type man
02:14:26kanzure:paperbot2 will have a tagging system
02:14:47fenn:paperbot2 will read the papers for you
02:14:58kanzure:( paperbot2: https://github.com/kanzure/paperbot/tree/master/paperbot )
02:24:28nsh:* nsh contends that %20 is harder to read than _ is to type
02:42:21wallet421:wallet421 is now known as wallet42
03:24:05Sub|out:Sub|out is now known as SubCreative
03:30:23Nekokamisama:Nekokamisama is now known as kumavis
04:20:53gmaxwell:rusty: the page there doesn't need a locally decodable code, so I don't go into an example there. Fountain codes are locally decodable though. (and with constraint can be made as locally decodable as you want)
04:21:38rusty:gmaxwell: yeah, sipa pointed me in the right direction, am playing with an implementation of simple LT fountain codes now to get a feel for it.
04:22:15fanquake_:fanquake_ is now known as fanquake
04:22:59rusty:gmaxwell: I've also been thinking about the UXTO tree; I think it makes sense to combine the UXTO, consumed TXO and produced TXO trees into one hash tree.
04:24:05rusty:gmaxwell: since for checking, you always want to see (or not see) the equivalent nodes in the other trees.
04:25:33rusty:gmaxwell: and the data the server fountain-encodes looks like: [TX ][Fee amount][TX merkle proof][Spent & consumed TXO proof].
04:26:32rusty:... oops, I mean:
04:26:59rusty:[TX ][Fee amount][TX merkle proof][consumed TXO proof]+[created TXOs proof]
04:27:00gmaxwell:Technically you shouldn't need to track spent data. There us unspent and you make updates to it. (it may be adventagious to track spent things, but for your scaling purposes perhaps not)
04:29:18rusty:gmaxwell: I think you need it, to report a missing UTXO.
04:29:36rusty:gmaxwell: otherwise it could be missing because a TX used it, and disproving requires all the TXs.
04:30:19rusty:gmaxwell: I was going to write up all the failure modes and proofs required for them (online, not just scribbled on my whiteboard :)
04:30:27gmaxwell:The only way it could be missing is if something updated the tree to remove it, or if something failed to add it, both of which are locally provable.
04:31:36rusty:gmaxwell: Am assuming evil miner drops UTXO from UTXO tree, right. You notice that, how do you prove it?
04:32:18gmaxwell:you reveal the miners update that removes the utxo, that doesn't have a transaction with it.
04:33:14rusty:gmaxwell: am confused... I assume UTXO tree was a simple merkle hash of [TXHASH, OUTPUTNUM] included in each coinbase. Is it something else?
04:35:10op_null:the UTXO is a database validating nodes make that contains all unspent outputs in the network.
04:35:20gmaxwell:In bitcoin it would be the complete state of the system needed to verify a new block / transaction. It's a merkleized search tree with keys {txid,vout} and values {version, height, cb flag, scriptpubkey, value}.
04:37:43rusty:gmaxwell: right, I had height and txoffset, so you could go back and ask for the rest. But the idea is the same.
04:38:04rusty:gmaxwell: so, back to my question: how do you demonstrate "that doesn't have a transaction with it"?
04:38:28rusty:gmaxwell: demonstrating there is no transaction which used a UXTO requires all the transactions, AFAICT. There's not compact proof.
04:39:29rusty:op_null: sure, in this case I was referring to the idea of embedding it in the block, which has some nice properties.
04:40:00amiller:rusty, no it's a search tree, you can give a compact proof that the search returns no result
04:40:26rusty:amiller: what is a search tree? Confused...
04:41:28rusty:amiller: specifically, what is the "it's" in your sentence?
04:41:29gmaxwell:rusty: its ordered by key (how the tree is balances is implementation defined, though non level compressed patrica trees are nice when keys are cryptographic hashes)
04:43:25rusty:gmaxwell: so, the UTXO tree is a patricia tree, or the txs themselves are hashed into a patricia tree? I still don't see how to prove "there's no tx which spent this txo" compactly...
04:44:11gmaxwell:rusty: basically, any datastructure can be be made autheticated, resulting in proofs O(amount of data read by someone using the data structure). So take a regular binary search tree (e.g. how you might implement a map in software), partica trie, red/black, whatever. Add hashes. The result is something with compact authenticated operations for anything that had compact operation in the original data structure.
04:45:06anao69:anao69 has left #bitcoin-wizards
04:45:49rusty:gmaxwell: that's all true, but you need a sort key to do that. Since a tx has multiple inputs, we'd need multiple sort keys, implying multiple trees.
04:45:49gmaxwell:rusty: You don't show "there is no tx which spent this txo" you show "this this change from hashx to hashy has no justification" ... the change actually happened at some point. Thats the point you show.
04:45:59gmaxwell:rusty: ugh no.
04:47:08gmaxwell:rusty: There is a single datastructure. The set of spendable coins. Every coind has an ID and some parameters. A block starts with a prior state, given to it from the prior blocks, and then adds transactions which update that state and result in a new state, chaining one after another.
04:47:35rusty:gmaxwell: sure, OK.
04:48:35gmaxwell:So state is X, tx Y shows up and proves some updats to X yielding state Z. TX Q shows up and proves some updates that mutate Z to R.. and so. on. The final state is just the last one. If someone does something wrong one of those updates will be unfaithful, e.g. not supported by update proofs or a valid transaction.
04:48:50gmaxwell:So to prove the invalidity you show the first place its gone off the rails.
04:50:42rusty:gmaxwell: so the miner commits state after each TX, and presents them all (presumably nicely hashed into a tree for compactness)?
04:51:46gmaxwell:Or at some updated interval, if it's larger than a transaction it works too but the size sets the minimum amount you can usefully validate.
04:52:05gmaxwell:(or smaller, e.g. state updates could be per each txin and txout processed)
04:52:58rusty:gmaxwell: I'd have to think harder to be sure that you could validate a single step, without knowing the entire state at that point.
04:56:07gmaxwell:you know the starting and ending state commitments, so {assuming the beginning state was good, this update passes the rules} is what you conclude. Maybe the initial state was BS, but if so, it would be visible in someone checking a prior step.
04:56:17rusty:gmaxwell: ah, I think I see. If you have merkle proofs (ignoring rebalancing) of the state tree before, it provides sufficient proof (for a single txoout or txin).
04:57:35rusty:gmaxwell: right... I had never thought of encoding the state like this, but it makes sense. OK, will return after more thought :)
04:57:43gmaxwell:even rebalancing isn't a problem though some care has to be taken so that rebalancing doesn't require touching off-path data. e.g. you should be able to compose two update proofs and not need some branch that neither contained. :)
04:57:59gmaxwell:rusty: yea, sorry, more tech we take for granted here.
05:00:33rusty:gmaxwell: You need to give a "100 future ideas for bitcoin" talk... any chance of getting you out to NZ for linux.conf.au in January?
05:02:09rusty:Damn, gtg. Back later...
05:02:58gmaxwell:man, that would be a murderous travel schedule; lca is 12-16 ... MIT mystery hunt in boston is on the 16th. alas.
05:03:44op_null:gmaxwell: time zones though. you could do both, almost
05:28:09zooko:kanzure: my wife, ambimorph, wrote a tagging system this summer: https://github.com/ambimorph/protagonist
06:29:31lclc_bnc:lclc_bnc is now known as lclc
06:58:49maaku_:maaku_ is now known as maaku
08:02:23espes___:espes___ is now known as espes
09:05:16weber.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:16weber.freenode.net:Users on #bitcoin-wizards: andy-logbot jaekwon_ damethos soundx oakpacific CoinMuncher AaronvanW go1111111 askmike Graftec coiner DougieBot5000 TheSeven fanquake fenn Dr-G2 dgenr8 eristisk aburan28 Starduster Nightwolf rfreeman_w spinza postpre op_null prodatalab ryanxcharles iddo Hunger- HaltingState d4de nuke1989 Emcy luny nubbins` SDCDev Pan0ram1x adlai arowser jaekwon samson_ lclc K1773R s1w koshii_ Eliel_ kanzure bobke LaptopZZ waxwing warptangent maaku Shiftos isis
09:05:16weber.freenode.net:Users on #bitcoin-wizards: btcdrak iambernie sneak harrigan michagogo hguux_ c0rw|sleep gavinandresen SubCreative JonTitor devrandom ebfull phantomcircuit sl01 mkarrer grandmaster Cory Grishnakh sipa mortale DoctorBTC Flyer33 Alanius epscy jbenet HM dansmith_btc artifexd btc__ kumavis mappum Muis bosma azariah4 nanotube orw MRL-Relay fluffypony tromp berndj jgarzik PaulCapestany BlueMatt a5m0 kgk Luke-Jr LarsLarsen Baz___ gazab AdrianG yoleaux gwillen livegnik BananaLotus
09:05:16weber.freenode.net:Users on #bitcoin-wizards: Myagui @ChanServ burcin coutts wizkid057 Dyaheon bbrittain NikolaiToryzin forrestv null_radix nickler mr_burdell Logicwax zibbo Meeh tromp_ Krellan poggy pi07r_ comboy mmozeiko lnovy Taek optimator_ [\\\] Apocalyptic throughnothing petertodd crescendo CryptOprah cfields-away Fistful_of_Coins gmaxwell kinlo ahmed_ so Anduck [d__d] espes BigBitz otoburb wumpus EasyAt starsoccer hollandais jaromil helo Keefe Iriez huseby phedny midnightmagic nsh
09:05:16weber.freenode.net:Users on #bitcoin-wizards: coryfields andytoshi BrainOverfl0w fds4345 warren pigeons asoltys gribble Graet smooth amiller danneu catcow TD-Linux [Tristan] ryan-c roasbeef harrow abc56889 lechuga_ Guest39111
09:14:30lclc:lclc is now known as lclc_bnc
09:17:17lclc_bnc:lclc_bnc is now known as lclc
11:19:48cbeams_:cbeams_ is now known as cbeams
12:21:15nnnm:I'm looking at blockchain.info block explorer now. There seem to be weird block distribution in the recent hour. Is that usual?
12:23:41gmaxwell:(1) bc.i data is very frequently totally wrong and busted, (2) what do you think is weird? ... blocks gaps are exponential, they ofen look bursty.
12:24:23nnnm:I was sure that with Bitcoin's hashrate it is practically impossible to have 40-min gap
12:24:47gmaxwell:;;tblb 2400
12:24:48gribble:The expected time between blocks taking 40 minutes and 0 seconds to generate is 8 hours, 53 minutes, and 40 seconds
12:25:07gmaxwell:nnnm: try more like 2.6 times per day on average.
12:25:34nnnm:ok great thank you
13:44:54kanzure:"There is a subdirectory named ".protagonist/tags", and a subdirectory ".protagonist/tags/t" for every existing tag, t. Any file which is tagged with t is given a unique identifier and a hard link in the directory t."
13:44:59kanzure:i dunno about this...
14:45:22oakpacific:;;tblb 3600
14:45:23gribble:The expected time between blocks taking 1 hour and 0 seconds to generate is 2 days, 21 hours, 40 minutes, and 58 seconds
14:45:38oakpacific:;;tblb 36000
14:45:39gribble:An error has occurred and has been logged. Please contact this bot's administrator for more information.
14:45:46oakpacific:;;tblb 7200
14:45:47gribble:The expected time between blocks taking 2 hours and 0 seconds to generate is 3 years, 18 weeks, 1 day, 13 hours, 35 minutes, and 3 seconds
14:57:30contrapumpkin:contrapumpkin is now known as copumpkin
15:22:42lclc:lclc is now known as lclc_bnc
16:23:18HM:hmm
16:52:55wallet42:wallet42 is now known as Guest71162
16:52:56wallet421:wallet421 is now known as wallet42
19:57:49zooko```:zooko``` is now known as zooko
22:51:09kanzure:.tw https://twitter.com/zooko/status/538392148127657984
22:51:10yoleaux:@petertoddbtc Challenge: key generation alg with entirely analog, homebuilt components: marbles, blocks, paper, rubber bands, etc. (@zooko, in reply to tw:538391798763118592)
23:55:34fanquake_:fanquake_ is now known as fanquake