06:18:55Krellan_:Krellan_ is now known as Krellan
07:48:48Dr-G2:Dr-G2 is now known as Dr-G
08:05:19sinisalo.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
08:05:19sinisalo.freenode.net:Users on #bitcoin-wizards: andy-logbot lclc torsthaldo optimator CoinMuncher p15_ pen Luke-Jr dgenr8 SDCDev koshii CoinHeavy TheSeven irclouis Dr-G Starduster_ toffoo ericp4 justanot1eruser Transisto oujh nsh gavinandresen LarsLarsen tacotime mortale GAit Alanius espes__ tromp K1773R andytoshi fanquake [Derek] shesek tucenaber comboy devrandom nsh- rfreeman_w melvster Sangheili mkarrer gmaxwell Taek42 mappppum jchp pajarillo Krellan throughnothing Burrito waxwing
08:05:19sinisalo.freenode.net:Users on #bitcoin-wizards: Guest14609 xenogis jaekwon1 quackgyver OneFixt_ Meeh copumpkin Logicwax roasbeef Dyaheon samson_ altoz grishnakh__ jaromil wiretapped pi07r Eliel grubles ryan-c Graet sipa Adohgg mr_burdell nickler Graftec starsoccer kanzure spinza EasyAt BigBitz phantomcircuit gwillen nuke1989 BrainOverfl0w HM_ otoburb postpre CryptOprah_ DoctorBTC btc jgarzik Keefe smooth michagogo warren Muis artifexd Fistful_of_coins azariah4 Hunger- zibbo tromp_ fierbuq
08:05:19sinisalo.freenode.net:Users on #bitcoin-wizards: forrestv harrow pigeons cfields [\\\] bobke midnightmagic CodeShark maaku Anduck zling_____ helo crescendo epscy mmozeiko Guest50253 asoltys berndj-blackout BlueMatt digitalmagus7 sl01 weex Iriez abc56889 lechuga_ SomeoneWeird bbrittain nanotube rs0 davidlatapie jbenet poggy_ TD-Linux a5m0 catcow amiller dansmith_btc danneu LaptopZZ_ burcin optimator_ jcorgan [d__d] petertodd UukGoblin wizkid057 kinlo so phedny gribble nkuttler @ChanServ
08:05:19sinisalo.freenode.net:Users on #bitcoin-wizards: Apocalyptic lianj wumpus
09:41:36OneFixt_:OneFixt_ is now known as OneFixt
13:42:29wallet42:wallet42 is now known as Guest95392
13:42:29wallet421:wallet421 is now known as wallet42
16:32:01brisque:in terms of SPV security, is there any reason the header of a block couldn't have a bloom filter set of it's transaction contents as a consensus rule?
16:32:24brisque:the advantage being that you could prove to a non-node client that a block doesn’t contain the transactions you’re interested in. if the wallet has an pubkeyhash/script interest they can request the whole block, else ignore it and just nab the header.
16:32:39brisque:it takes away the need to have a bloom filter service offered by the p2p network, and I can’t think of any reasons just yet that would it an impossibility.
16:38:56tromp_:how many bytes would that add to the header?
16:43:06brisque:probably too many. bloom filters have a tradeoff between size and false positives.
16:44:05tromp_:it would be orders of magnitude larger right?
16:44:44tromp_:let's say you want 10e-6 false rate
16:44:53tromp_:i mean 1e-6
16:48:24sipa:an optimal bloom filter has half of its bits set, so 20 hash functions are necessary
16:48:38sipa:for 1/2**20 false positive rate
16:51:12sipa:i think
16:53:22gmaxwell:brisque: would make a specific matching scheme normative, which would be pretty ugly.
16:53:34brisque:tromp_: for a sort of normalish block and a false positive rate of 1E-06 you're looking at about a 115k bit filter, I think.
16:53:41gmaxwell:e.g. all works great and then you start using some other scriptpubkey style and it misses your txn.
16:53:43tromp_:that's about 3KB for up to 1000 tx
16:57:02gmaxwell:brisque: a preferable design is probably to reorganize the structure of transactions so that the input list, signatures, and outputs can be provided seperately. So you could just follow the onputs in blocks. with the data cut down N fold you need much less specific filtering, or no filtering at all.
17:00:06gmaxwell:e.g. 2000 36 byte txouts is 76k, which compares pretty favorable to even a modest false positive rate.
17:02:06brisque:gmaxwell: yep, that makes sense. main thing I found interesting about a bloom-header is that I couldn't find an obvious reason why it doesn't work, but I agree it's super ugly, restrictive in terms of script and not a likely addition to anything.
17:02:32gmaxwell:It's also not particularly private.
17:03:37brisque:I guess having the reorganised block system would be a bit more so, you could randomise where you download the full block from to avoid revealing what you're interested in.
17:03:38gmaxwell:(since you still need to disclose what bits you're interested in, or at least disclose which blocks you're interested in the content of)
17:03:56brisque:* brisque nods
17:04:31fanquake_:fanquake_ is now known as fanquake
17:05:19gmaxwell:hm. it is an interesting point, you could do a information theoretic PIR-ish approach where you get the map from one place, and if something interesting was in it, you randomly connect someplace else and get the whole block (or its whole txout list, if possible)
17:05:54gmaxwell:and assuming the security of tor someone wouldn't learn any correlations in blocks you were interested in.
17:07:38brisque:I'm surprised bitcoinj/electrum doesn't do this already, actually. instead they set all the filters they want and subscribe to the same addresses all on the one peer.
17:08:26brisque:I guess it depends on which you think is less risky. a large number of peers knowing something you're interested in, or one peer knowing everything you're interested in.
17:11:36gavinandresen_:gavinandresen_ is now known as gavinandresen
17:24:17Eliel:tromp_: I think 1E-06 false positive rate is way overkill for this purpose. A false positive just means you process one extra block and realize there were no transactions you wanted in it.
17:24:51gmaxwell:Eliel: keep in mind the user may have 100,000 addresses they are checking.
17:25:04gmaxwell:otherwise you create insane pressure to reuse scriptpubkeys.
17:25:39Eliel:gmaxwell: I think that's a case for running a full node yourself already.
17:26:30gmaxwell:Eliel: sure, but assuming you're not. It's not in the networks interest to offer services which encourage harmful behaviors. (because the bad behaviors harm everyone; e.g. miners getting ordered to censor particular addresses is only really thinkable in a world where people are frequently reusing addresses)
17:27:27gmaxwell:brisque: I agree this is a better design... even without the commitment it has the same trust model, but somewhat overhead. What interesting is that it avoids any of the cpu exhaustion risk, since the data is the same for all and can be computed just once.
17:30:13fanquake_:fanquake_ is now known as fanquake
17:31:01brisque:gmaxwell: yes, in terms of speed you don't even need to be recalculating the filter for each extraNonce, you can cache the bloom header and just add in the coinbase for each round. it's almost a pretty solution except for restricting scriptPubKey types for SPV nodes, as you pointed out.
17:34:40gmaxwell:well I think you can reduce the problem there by just saying "you can only use this for exact scriptpubkey matches"
17:35:17gmaxwell:the hashes should be salted by the prevblock hash to make it harder for people to try to pollute the filter.
17:35:39brisque:oh good point.
17:36:08gmaxwell:really it would be best if it were the current block hash, but; kind of a cyclic dependency there. :P
17:36:44Eliel:merkle root hash is not good enough?
17:36:48gmaxwell:another nice thing is that you could keep this data around-- it's farily small, and it would enable faster rescans.
17:37:38gmaxwell:Eliel: it would be except we'd need the commitment to be in the coinbase. If we're talking ideals, yes, that would be pretty good... then it's like a cut and choose proof. can't change the data to gunk it up without rerandomizing it entirely.
17:38:40Eliel:oh right, that'd be mining in itself :P
17:40:38gmaxwell:one downside of the randomization is that you wouldn't be able to choose scriptpubkeys which collide with your other scriptpubkeys.
17:40:58Eliel:if merkle root is not possible, perhaps you could take the the second has from the next level in the tree?
17:41:34gmaxwell:Eliel: you'd have to use log() hashes to cover the rest of the tree. It could be done.
17:43:40brisque:as tromp_ asked before, making the filter scalable and of a reasonable false positive rate isn't actually that difficult. it also means that you have plausible deniability on your getblock.
17:45:28Eliel:if you store the bloom hashes in a merkle tree and commit the root of that, you could also get the plausible deniability by choosing how much of the bloom filter to request.
17:47:57brisque:for #320,014 (713KB, 1075 tx, 3680 outputs in set)
17:48:06brisque:p=0.0001 gives a 8.61 KiB filter
17:48:06brisque:p=0.001 gives a 6.46 KiB filter
17:48:06brisque:p=0.01 gives a 4.31 KiB filter
17:58:39fanquake_:fanquake_ is now known as fanquake
18:05:28Denisverm_:Denisverm_ is now known as Denisverm
18:26:28gmaxwell:Eliel: the connecting proofs end up being not much smaller than the whole filter.
19:16:33gmaxwell:brisque: so I wonder what the false positive profiles look like for 10,000 keys, if first the script pubkeys are hashed into (say) 8 buckets in a non-salted way, and then you do 8 bloomfilters (one per bucket)... and you grind your addresses to all use a single bucket.
19:23:33brisque:gmaxwell: is that desirable from a privacy standpoint? it means you can ger easy confirmation of the connection between two otherwise unrelated addresses.
19:23:51brisque:either that or I've misunderstood what you mean, which is likely.
19:27:10jgarzik:Related: I had a need a year or so ago for merging bloom filters
19:27:48jgarzik:i.e. for N sets of keys or whatever, you may desire to create N bloom filters, then combine that into a master filter
19:28:00jgarzik:is it feasible to merge two filters, without knowing input data?
19:28:21gmaxwell:sure. just or them.
19:28:44gmaxwell:brisque: there is a privacy tradeoff there, which was why I used a small number.
19:29:16brisque:jgarzik: yes, you can add but not subtract