| 00:00:12 | hearn: | std::string is a vector of bytes |
| 00:00:26 | justanotheruser: | yes, but its more explicit that way |
| 00:00:28 | hearn: | sure |
| 00:00:45 | hearn: | i am not a big fan of using std::string to hold arbitrary binary data. it's pretty common in the google c++ codebase though |
| 00:01:09 | hearn: | sipa: i think std::string is not null terminated unless you call c_str() |
| 00:01:11 | bramc: | In Python it started that strings were just binary strings, then encoding/decoding support was added with people mostly using uft8 because by that time it had become clear that utf16 was a blight upon humanity |
| 00:01:37 | hearn: | the java guys are working on an interesting way of handling strings. |
| 00:01:55 | hearn: | they want to detect whether a string is ascii or unicode at runtime and then "compress" utf-16 strings down to a variant of ascii on the fly |
| 00:01:58 | bramc: | Now there's bytes for mutable ones and a separate unicode string type in python3 |
| 00:03:05 | bramc: | I think Python does something like that too, although that's got an SEP field around it. |
| 00:03:50 | bramc: | I'm mad at the Java people for making the string.encode() method not require an encoding and defaulting to the local system one. |
| 00:04:21 | bramc: | I once had a bunch of overseas developers who thought that Java just magically solved encoding problems for them and that's why it didn't need the parameter |
| 00:04:32 | bramc: | Of course it turned out that their machines had the locale set to latin-1 |
| 00:05:10 | hearn: | String.getBytes() without an encoding parameter is deprecated |
| 00:05:14 | hearn: | so they weren't paying attention, apparently |
| 00:05:18 | hearn: | or this was a looooong time ago |
| 00:10:57 | CoinCadence_: | CoinCadence_ is now known as CoinCadence |
| 00:13:14 | gmaxwell: | hearn: "though using std::string to hold arbitrary binary data is not uncommon in many c++ code bases" yea, well, I hear there are also people who huff glue. |
| 00:14:35 | bramc: | hearn, 2006. Some of us are old :-P |
| 00:15:17 | Luke-Jr: | lol |
| 00:15:25 | bramc: | Does C++ do array bounds checking? |
| 00:15:27 | hearn: | ah ok, my mistake, it's not deprecated actually. it just states that the behaviour is unspecified :) |
| 00:15:41 | hearn: | ah i see. it's the ranged version that's deprecated |
| 00:15:49 | bramc: | "Don't have to worry about the encoding problem any more, ops fixed it!" |
| 00:15:50 | hearn: | gmaxwell: well, BigTable does that, and it's one of the best engineered systems i've seen. |
| 00:16:05 | hearn: | though possibly only glue huffers would think "hey let's put the entire web into a database" :) |
| 00:16:30 | hearn: | bramc: it bounds checks std::vector if you use the .at() method which nobody does. the [] operator overload doesn't bounds check |
| 00:16:48 | phantomcircuit: | bramc: yeah null terminated strings are a C thing only these days |
| 00:16:49 | phantomcircuit: | even then |
| 00:16:50 | phantomcircuit: | ew |
| 00:17:05 | phantomcircuit: | hearn: and PHP :P |
| 00:17:06 | bramc: | For anyone missing the joke, a local latin-1 encoding will cause encode() and decode() to return the string passed into them |
| 00:17:29 | phantomcircuit: | php is actually both null terminated and not null terminated which leads to an entirely hilarious class of exploits |
| 00:17:29 | hearn: | * hearn tries hard to forget that PHP exists |
| 00:17:39 | hearn: | phantomcircuit: lol how does that work? |
| 00:17:58 | hearn: | my father writes code in PHP |
| 00:17:59 | phantomcircuit: | hearn, certain functions treat strings as null terminated and others use their length property |
| 00:18:07 | hearn: | haha. yes that sounds about right. |
| 00:18:16 | bramc: | The upshot of all of this for bitcoin is that unicode shouldn't be allowed anywhere near bitcoind |
| 00:18:31 | gmaxwell: | bramc: huh? |
| 00:18:39 | phantomcircuit: | hearn, iirc strlen is just a direct call to libc strlen |
| 00:18:59 | phantomcircuit: | so you get fun code where only the part before the nulls are sanitized and there's escape codes afterwards |
| 00:19:15 | bramc: | gmaxwell, bitcoin handles binary strings fine as byte arrays, the dangerous thing would be to add unicode strings in somewhere |
| 00:19:23 | brisque: | phantomcircuit: yeah, you can do lots of trickery with that. there's a whole class of php related exploits where you can inject null bytes and bypass security limitations. |
| 00:19:52 | bramc: | JCF terminated, it's the future. |
| 00:20:11 | phantomcircuit: | bramc, except that i dont think bitcoin uses strings anywhere except for the remote client version identifier |
| 00:20:31 | sipa: | and reject messages |
| 00:20:43 | phantomcircuit: | hmm |
| 00:20:45 | sipa: | which have already almost caused a vulnerability |
| 00:20:46 | hearn: | and message type codes |
| 00:20:50 | bramc: | phantomcircuit, I'm not arguing against that |
| 00:20:53 | phantomcircuit: | right |
| 00:21:00 | hearn: | and subVer fields |
| 00:21:08 | bramc: | although remote client version identifies should probably be utf-8 and that's the end of it. |
| 00:21:11 | sipa: | hearn: those are constant size (message commamds) |
| 00:21:14 | hearn: | right |
| 00:21:39 | sipa: | alerts have several strings |
| 00:21:40 | gmaxwell: | bramc: I think you've spent too much time exposed to languages which needlessly conflate strings with everything. The bitcoin protocol isn't text, its a simple binary protocol, with many fixed length and length encoded fields. There is nearly no text anywhere in it. (nearly: exceptions being things like that client version string thing; which we had _two_ vunlerabilties related to) |
| 00:21:43 | phantomcircuit: | hearn, subVer is what i was talking about |
| 00:21:49 | brisque: | phantomcircuit: subversion, and reject messages I think. |
| 00:22:10 | gmaxwell: | (and which I still think should never have been added, now that _every_ downside I predicted has come true. :) ) |
| 00:22:12 | phantomcircuit: | brisque, yeah that seems to be everything |
| 00:22:31 | phantomcircuit: | gmaxwell, every every or just 99% every |
| 00:23:18 | hearn: | gmaxwell: you don't see the upsides |
| 00:23:18 | gmaxwell: | Well, I'd have to dig, I predicted security bugs, that it would not be set to accurate values, and that software would bogusly test against it. All of which have been true. I might have predicted doom of other forms. |
| 00:23:24 | bramc: | constant size implies that they're binary. If they're unicode with constant binary size then they just happen to be putting in conveniently displayable data but they're still binary |
| 00:24:14 | gmaxwell: | There has been some doom I haven't predicted, it actually makes for some mild deanonymization attacks that I didn't quite expect. (people leave the data in logs, because it doesn't seem identifying, and you can watermark version strings when you connect) |
| 00:24:27 | bramc: | gmaxwell, The bittorrent protocol works that way too. It's fairly clear that satoshi had reasonable familiarity with at least the wire specification of bittorrent |
| 00:24:58 | bramc: | starting with how bitcoin was intended to be defined based on a protocol rather than 'whatever this codebase does' (modulo a few bugs which snuck in of course) |
| 00:26:07 | bramc: | Things like version strings should be binary strings, and when people ask about unicode the answer is 'use utf-8 dumbass' |
| 00:26:27 | gmaxwell: | hearn: upsides are limited by the downsides, a lot of hosts lie about their subver. |
| 00:26:53 | hearn: | i was referring to reject messages. nonetheless, subVer is still useful. |
| 00:27:15 | gmaxwell: | bramc: sure. well thats been the C/Unix land answer to unicode anything pretty much. though its not quite a perfect answer. (e.g. stuff utf-8 into a array of a maximum number of bytes in size...) |
| 00:27:22 | bramc: | In its heart of hearts, is a filename a binary string displayed as unicode or a unicode string encoded as binary? |
| 00:28:46 | bramc: | gmaxwell, Microsoft totally got fucked by utf-16. They were earnestly trying to do the right thing and follow the 'standard'. |
| 00:28:50 | phantomcircuit: | bramc, the first one which can be super annoying |
| 00:29:23 | phantomcircuit: | (it's valid on most filesystems to save a file with a name that isn't valid utf-8) |
| 00:29:40 | bramc: | phantomcircuit, If only file system apis provided quoting functions to get the local way of encoding an arbitrary fucking filename |
| 00:29:50 | brisque: | hearn: for bitcoin in particular this sort of thing has a higher impact than anywhere else. did anyone else think that you could use the subversion string as a deanonymization side channel? it's really in the clients best interest just to avoid even "harmless" things as much as possible. |
| 00:30:21 | bramc: | And then there are the ... interesting behaviors when you try to make a file whose name is the null character, or zero length, or front slash... |
| 00:30:38 | phantomcircuit: | bramc, sure but rogue programs can still produce filenames which cannot be deleted by "rm" because rm considers the filename invalid |
| 00:30:42 | phantomcircuit: | that's always fun |
| 00:31:07 | hearn: | clients are almost always connecting with their real IP address today over unencrypted connections. subVer fields are really not high up the list of things to worry about. meanwhile there is an actual need for features to aid development, monitoring and administration. |
| 00:31:13 | phantomcircuit: | brisque, client authors want people to know that people are using their client |
| 00:31:19 | gmaxwell: | hearn: I've found rejects useful at times, though the tradeoff is still somewhat unclear to me: For the moderate additional help in trouble shooting we also gained three vulnerabilties (sanitization, memory exhaustion (even though the code tried to limit the size initially it did so too late), and a potential for infinite loops because it could reject reply to a reject message |
| 00:31:32 | phantomcircuit: | (and it's not like identifying clients based on their protocol handling is difficult) |
| 00:31:51 | bramc: | phantomcircuit, I'm continually terrified of trying to store files with filenames suggested by an untrusted source. For example having a file name '~/.profile' in a multifile torrent |
| 00:31:58 | brisque: | phantomcircuit: subvers as an advertising method seems a little far fetched to me |
| 00:32:03 | gmaxwell: | hearn: subver is wrong more often than it's right now if you exclude bitcoin core and bitcoinj _lots_ of things claim to be bitcoin core which are not. So I think that basically makes it useless for monitoring. |
| 00:32:30 | bramc: | Sorry for the dumb question, but what are rejects and subver? |
| 00:32:45 | phantomcircuit: | brisque, it's definitely going on i see version numbers with urls for exchanges sometimes |
| 00:32:51 | gmaxwell: | bramc: subver is a text string that gives the remote peers software version (or whatever else it wasnts to send instead) |
| 00:32:53 | hearn: | i'd like to see a systematic framework for catching memory usage issues. |
| 00:32:56 | phantomcircuit: | (it's actually just the one but im not going to advertise for them here...) |
| 00:33:08 | hearn: | accounting/disconnecting nodes that used up more than their fair share, etc. |
| 00:33:35 | gmaxwell: | bramc: reject is a response that can be sent to messages to say you rejected them. |
| 00:33:40 | phantomcircuit: | hearn, identify all the allocation events and walk the stack backwards |
| 00:33:40 | gmaxwell: | (and maybe why) |
| 00:33:46 | bramc: | Ah, I see |
| 00:33:47 | hearn: | bear in mind that there might be tens of thousands of developers who can develop faster over the next 5 years because of (say) reject, so the benefits pile up over time |
| 00:33:58 | hearn: | bugs are nasty but they get fixed and then the benefits accumulate. |
| 00:34:25 | bramc: | So rejects are a way for developers to tell other developers that their shit is busted? |
| 00:34:26 | hearn: | phantomcircuit: you don't really want to do it that way. you can just use a custom allocator that tracks and accounts memory usage whilst a peer is "in scope". the problem is what to do if a peer goes over its budget |
| 00:34:39 | gmaxwell: | hearn: The time it save in diagnostics mostly translates into "I don't have to test against my own node to see why it rejects things" |
| 00:34:41 | hearn: | bramc: yeah it's an error message scheme for the protocol basically. like HTTP error codes. |
| 00:35:31 | brisque: | bramc: not even that, you can reject for things like an input already being spent. |
| 00:36:08 | phantomcircuit: | hearn, i suspect that would end up being more risky than it sounds since you'd have to track which peer triggered the allocation and that information isn't currently available |
| 00:36:20 | brisque: | hearn: point was that you can use a subversion side channel to deanonymise users. ask them to supply a log, they don't scrub the subversion, and you now know what their real IP address is. |
| 00:36:21 | hearn: | gmaxwell: sometimes the production network doesn't match your local setup, though. i mean that argument applies to any network protocol that has an open source server available. we could just make every network protocol just return ERROR if something goes wrong, MS/DOS style. |
| 00:36:22 | bramc: | brisque, I would argue that a 'that input is already spent' message has enough semantic meaning that it should be its own message type instead of relying on the 'human readable' reject message |
| 00:36:58 | hearn: | phantomcircuit: most processing for a peer happens whilst a message is on stack, so you can just put a CPeer reference into a TLS slot, for example (and make sure to propagate it across threads when that happens for eg. signature checking) |
| 00:37:21 | bramc: | You could even make it implicit by making the 'error' response be to send the transaction which you yourself had accepted |
| 00:37:53 | gmaxwell: | hearn: it's all much simpler to just avoid the case where a peer can cause you to use memory beyond some trivial amount you can always handle. |
| 00:38:08 | brisque: | bramc: it has both, a machine readable reject reason and a string. |
| 00:39:15 | hearn: | i'd rather have automatic solutions as much as possible. eg it'd be simpler to use C and just avoid writing bugs, but in practice, the automatic facilities C++ provides do help (and going up one level, automatic gc helps etc) |
| 00:39:27 | hearn: | the code might be being evolved 15 years from now by people we have never met |
| 00:39:56 | brisque: | hearn: like an antimony pill? |
| 00:40:05 | hearn: | from time to time people will make mistakes or network conditions will change, assumptions will be invalidated, etc. better put in place crash mats now. |
| 00:40:27 | hearn: | antimony pill? |
| 00:40:36 | brisque: | sorry that was a horrible joke. |
| 00:40:38 | phantomcircuit: | hearn, er there's stuff passed between threads which you'd have to handle correctly |
| 00:40:51 | hearn: | phantomcircuit: yes i said that. you have to propagate the peer across thread boundaries. |
| 00:40:53 | phantomcircuit: | it's probably easier than im thinking but harder than you're thinking |
| 00:41:06 | hearn: | * hearn has experience of building systems that work this way |
| 00:41:24 | phantomcircuit: | and either way just identifying all the potential ridiculous allocation issues and limiting their size is probably easier and saner |
| 00:41:59 | gmaxwell: | Sometimes things sold as crash mats turn out to be spike covered death traps in production. e.g. several different attempts at BGP congestion handling resulted in large scale internet outages, because they could turn small single device failures into big convergence faults. Making something automatic at the expense of making it harder or impossible to analyize may not be a win. ... though some ki |
| 00:42:00 | hearn: | i hope at some point to get time to prototype this sort of framework |
| 00:42:05 | gmaxwell: | nds of automatic are safer than others. |
| 00:42:29 | bramc: | As a general rule what makes the codebase for something like bitcoin maintainable is having a coherent protocol specification. First you design the protocol, then you make the codebase conform to it. If it's coherent you can always scrap the current codebase and reimplement |
| 00:42:59 | brisque: | hearn: (in the 19th centuary people would make a pill out of antimony (a poisonous metal) and use it for a sort of laxative effect, birth control or hangover cure. being a metal you could reuse it infinite times, and it would be passed down through families. I was likening the bitcoin codebase to this.) |
| 00:43:03 | bramc: | You should see the garbage generated by people who don't understand that point and are all proud of how well they understand C++ because of all the template metaprogramming and multithreading they've thrown in. |
| 00:43:04 | phantomcircuit: | bramc, except like you cant with bitcoin.... |
| 00:43:17 | gmaxwell: | bramc: the 'protocol' is unimportant, can be replaced at any time.. and in fact the bitcoin system is run over several different protocols now. :) |
| 00:43:50 | hearn: | brisque: huh, i didn't know that. interesting. |
| 00:44:09 | hearn: | brisque: sounds about as wise as sweetening wine with lead :) |
| 00:44:33 | bramc: | There's always a tension between the de facto protocol and the in principle protocol, but in the case of bitcoin the de facto one is largely subservient |
| 00:44:39 | bramc: | Except for time warp attacks :-P |
| 00:44:50 | gmaxwell: | Bitcoin starts with an authenticated data structure; thats the 'protocol' that counts (transactions and blocks); though it's not what most people are thinking about when they say protocol. |
| 00:45:26 | bramc: | gmaxwell, It peels apart in layers. There's the blockchain format, which is most fundamental, then there's the bitcoin protocol and spv |
| 00:46:03 | brisque: | hearn: (similar concept really. you would make a cup out of antimony, and if you'd been heavily drinking you would fill the cup with water before you went to bed. it would leech into the water overnight, and act as a hangover cure in the morning) |
| 00:46:05 | sipa: | sipa has left #bitcoin-wizards |
| 00:46:55 | brisque: | bramc: SPV isn't really something that needs to be part of the network protocol. |
| 00:46:59 | gmaxwell: | bramc: right but there are alternative protocols; e.g. bluematt's relay network protocol, or the electrum stratum stuff that replace the p2p protocol with varrying levels of completeness. |
| 00:47:37 | bramc: | gmaxwell, right and the further they get away from the block chain the easier they are to change |
| 00:47:43 | brisque: | bramc: I have a sort of half-assed build of a bitcoin transport which uses tumblr.com as the communication medium. |
| 00:48:27 | gmaxwell: | brisque: ohhhh "Bitcoin tumbler" |
| 00:49:34 | gmaxwell: | (for some reason people referring to bitcoin tx graph obfscuation things as 'bitcoin tumbler'; I have no clue where it came from, and no clue why it irritates me.) |
| 00:49:35 | phantomcircuit: | brisque, except for the part where it was poisonous |
| 00:50:01 | hearn: | i guess it conjures images of lottery machines |
| 00:50:03 | hearn: | at least it does for me |
| 00:50:16 | bramc: | It all has to do with difficulty of change. If engineered correctly it should be easy to rework the actual codebase, because it has a coherent behavioral specification which is dependent on implementation details |
| 00:50:31 | bramc: | Web browsers are awful things to work on for this reason |
| 00:51:00 | brisque: | phantomcircuit: to "cure" syphilis they fed mercury to goats and drank the milk. I don't think a lot of these cures are particularly well thought through or researched. |
| 00:52:00 | phantomcircuit: | heh |
| 00:52:39 | bramc: | According to the interwebs the human body can handle antimony fairly well, probably because it's much more widely occuring in our natural environment than lead. |
| 00:54:10 | phantomcircuit: | bramc, long term chronic exposure is poorly studied and probably has similar health risks as other heavy metals |
| 00:54:35 | phantomcircuit: | intentionally consuming large amounts via an "antimony cup" seems ill conceived |
| 00:54:41 | phantomcircuit: | and back on topic |
| 00:54:53 | bramc: | Also while mercury poisoning sucks in the days before antibiotics risking it beat reliably dying of syphilis |
| 00:55:07 | phantomcircuit: | why does the bloomfilter stuff even have a "hash" parameter? |
| 00:55:12 | phantomcircuit: | (ie iteration count) |
| 00:55:44 | phantomcircuit: | or i guess it's not iterations but actually different hash functions? |
| 00:56:06 | brisque: | it's different hash functions |
| 00:56:26 | brisque: | one hash function with a "tweak" causing different outputs |
| 00:56:39 | gmaxwell: | basically it lets you change your collission set. |
| 00:56:41 | hearn: | it's a part of the Bloom algorithm, check wikipedia |
| 00:59:49 | Adlai: | gmaxwell: 'coin tumbler' dates back to when taint had mass :) |
| 01:00:10 | Adlai: | http://rocktumbler.com/blog/coins-in-a-rock-tumbler/ |
| 01:00:52 | brisque: | Adlai: hm, I thought it was a reference to laundry |
| 01:01:00 | brisque: | could be dual-origin I suppose. |
| 01:01:36 | phantomcircuit: | gmaxwell, is it really necessary? |
| 01:08:56 | phantomcircuit: | guess i should take a bit to read about bloom filters some more... |
| 01:20:42 | phantomcircuit: | oh i see |
| 01:20:53 | phantomcircuit: | each hash function produces a single index |
| 01:21:00 | phantomcircuit: | that doesn't exactly seem optimal |
| 01:22:47 | phantomcircuit: | MurmurHash3 produces 32 bits of output per call |
| 01:22:56 | phantomcircuit: | why not simply use the first k bits of output as indexes? |
| 01:43:56 | mike420: | http://www.ebay.com/itm/271801501789?ssPageName=STRK:MESELX:IT&_trksid=p3984.m1555.l2649 |
| 01:43:59 | mike420: | good price? |
| 01:44:58 | Luke-Jr: | Luke-Jr has kicked mike420 from #bitcoin-wizards |
| 02:28:12 | bramc: | So the IBLT proposed by Gavin only uses xor, no fancy ECC? |
| 02:30:02 | phantomcircuit: | bramc, any opinion on bloom filter hash function usage? |
| 02:30:25 | bramc: | phantomcircuit, I'm going off this, written by rusty: http://rustyrussell.github.io/pettycoin/2014/11/05/Playing-with-invertible-bloom-lookup-tables-and-bitcoin-transactions.html |
| 02:30:49 | phantomcircuit: | yeah i just meant normal bloom filters |
| 02:30:56 | bramc: | Which hash unction you use shouldn't really matter. I'd go with siphash keyed off the block id, because I'm paranoid like that |
| 02:31:31 | bramc: | And because, uh, there's no downside in terms of performance |
| 02:33:32 | bramc: | phantomcircuit, Not really sure what your question is |
| 02:37:53 | bramc: | I don't have much to add to rusty's analysis. If I were to analyze it seriously I'd just re-run the tests he's done, which seems pointless |
| 02:38:22 | bramc: | Also I agree that it doesn't make sense to compress 1M of data down to 1M. |
| 02:38:47 | bramc: | And I don't know how very large transactions get broken up - are they split into pieces or something? |
| 02:46:00 | justanotheruser: | Any reason not to just use FNV for the bloom filter? |
| 02:47:08 | bramc: | justanotheruser, Using siphash would keep anybody from doing a dos where they intentionally make a bunch of transactions hit the same place and render the summary useless |
| 02:47:46 | justanotheruser: | that seems like a miners problem |
| 02:47:58 | justanotheruser: | and makes malleability a feature! |
| 02:48:54 | phantomcircuit: | bramc, the standard algorithm is to set a bit in a bitfield once for each hash call |
| 02:49:05 | bramc: | In all seriousness, using siphash keyed off the block id is exactly the kind of thing siphash is meant for. |
| 02:49:07 | phantomcircuit: | but the hash function returns 32 bits |
| 02:49:26 | phantomcircuit: | so you should be able to get more than 1 bit in the bitfield per hash function call |
| 02:49:43 | bramc: | phantomcircuit, You expand out the hash value in some random way to get all the locations |
| 02:49:44 | phantomcircuit: | i dont think it gets you a whole lot of advantage |
| 02:49:49 | phantomcircuit: | but it's potentially something |
| 02:50:19 | phantomcircuit: | bramc, no the standard implementation is that you call the hash function again with a new tweak value to get the next bit |
| 02:50:32 | phantomcircuit: | so for k=10 you call H 10 times |
| 02:50:37 | bramc: | phantomcircuit, six, dozen/2 |
| 02:50:41 | justanotheruser: | I suppose miners wouldn't even have to optomize the transactions for non-collision, but if they did the fee would have to correlate with the increased risk or reorg from including their collision tx' |
| 02:50:54 | phantomcircuit: | bramc, wat |
| 02:51:24 | bramc: | justanotheruser, I have no idea if you're joking |
| 02:51:47 | justanotheruser: | bramc: why, am I wrong? |
| 02:51:51 | phantomcircuit: | bramc, is siphash considered secure? |
| 02:51:55 | phantomcircuit: | i didn't think it was |
| 02:52:29 | bramc: | phantomcircuit, there's key data and you pick positions in the filter based off it. How you mash up that key data to determine the positions doesn't matter |
| 02:52:48 | phantomcircuit: | bramc, right |
| 02:52:55 | bramc: | phantomcircuit, siphash is considered secure against an attacker intentionally making hash collisions when they don't know the key for the hash |
| 02:53:13 | phantomcircuit: | but the standard (and the current bitcoin) implementation is 1 bit is set per hash function call |
| 02:53:26 | bramc: | phantomcircuit, If you run numbers on bloom filters it turns out that you get the maximum storage when roughly half the bits in the filter are set |
| 02:53:28 | phantomcircuit: | but i guess it's not worth it actually to change that |
| 02:54:07 | phantomcircuit: | bramc, the attacker knows the key though |
| 02:54:20 | phantomcircuit: | since the key has to be deterministic |
| 02:54:29 | bramc: | phantomcircuit, You could speed it up a little bit by not throwing out any of the bits from hash calls |
| 02:55:00 | bramc: | phantomcircuit, If you use the block id as the key then the attacker doesn't know it when they're trying to do their attack |
| 02:55:04 | phantomcircuit: | bramc, yeah but i just realized that complicates things enough that it's not worth it |
| 02:55:26 | phantomcircuit: | bramc, iirc the idea was to include a hash of the bloom filter in the block |
| 02:55:36 | phantomcircuit: | but if you're not doing that then yeah |
| 02:57:04 | bramc: | phantomcircuit, I don't see the point of putting the bloom filter hash in the block |
| 02:57:24 | phantomcircuit: | bramc, soft forking rule change |
| 02:57:54 | bramc: | You could also hash together everything but the bloom filter id for the bloom filter's key |
| 02:58:09 | phantomcircuit: | presumably using something like the merkle tree root would make the raw time to bruteforce the tweak value high enough as to be unreasonable by itself |
| 02:58:13 | phantomcircuit: | but that's just a gut feeling |
| 02:58:35 | phantomcircuit: | bramc, cant include the nonce value in the block header of course |
| 02:58:49 | bramc: | merkle tree root should be plenty |
| 02:58:53 | phantomcircuit: | i suspect keying off just the merkle tree root would be sufficient |
| 03:05:09 | phantomcircuit: | bramc, maybe |
| 03:12:50 | bramc: | phantomcircuit, Since the attacker's vector is by guessing the key and introducing transactions which work with it, using the transaction root should kill any such attacks because each new transactions gets secure hashed into it |
| 03:13:40 | bramc: | rusty, If you're here I have some questions about the IBLT format, starting with why use a whole 32 bits for count? Shouldn't the last 8 bits of it be sufficient? |
| 03:14:08 | rusty: | bramc: am here.... was a while since I played with it. Let me dig out my code for a refresh. |
| 03:15:47 | tromp: | bramc: you want to avoid count overflowing |
| 03:16:07 | bramc: | tromp, I don't understand, aren't you mostly looking for exact matches? |
| 03:16:19 | phantomcircuit: | bramc, bruteforcing a merkle tree root which causes a siphash collision might not be as expensive as it sounds |
| 03:16:52 | brisque: | you're going to have to be doing that for every 2^32 nonces though |
| 03:17:08 | bramc: | phantomcircuit, I think the key to siphash is kinda big |
| 03:17:12 | brisque: | probably a little more with nrolltime. |
| 03:17:13 | rusty: | bramc: I used 6 bytes for id, 2 for index. |
| 03:17:41 | tromp: | you want to use count==1 as a single item. 257 items xored together could cause havoc when interpreted as one |
| 03:17:59 | bramc: | rusty, and there's 32 bits for 'count' |
| 03:18:15 | rusty: | bramc: ah, that doesn't really matter. The iblt is small. |
| 03:18:37 | rusty: | bramc: assuming it gets wire encoded down to something more minimal. |
| 03:18:59 | bramc: | tromp the vast majority of the time you're looking for exact match. You start looking for additions/deletions by finding one which is off by 1 |
| 03:19:29 | brisque: | can the iblt actually be processed by a node more quickly than a direct block push? |
| 03:19:32 | tromp: | but what if they're really off by 257? |
| 03:19:38 | phantomcircuit: | brisque, hmm you're right that could get expensive |
| 03:19:54 | bramc: | tromp I'm guessing the chances of accidentally hitting something really off by 257 is vanishingly small |
| 03:20:29 | rusty: | tromp: if you're missing 257 in one bucket you have other problems; you're not going to be able to recover :) |
| 03:20:41 | phantomcircuit: | brisque, oh derp you use the previous block hash as the tweak value |
| 03:20:46 | bramc: | brisque, the iblt is vastly smaller than a whole block, and yes it should be fast to process. Xor is quick like that. |
| 03:20:51 | phantomcircuit: | not perfect but pretty damned close |
| 03:21:39 | tromp: | bramc, rusty: ok, i'll take your word for it:) |
| 03:21:45 | bramc: | rusty, I suspect that making a decent standard wire encoding for that is tough and it's more expedient to just reduce it to 8 bits |
| 03:22:15 | rusty: | bramc: there are a couple more refinements possible to my codebase. First, I insist on recovering the entire transaction (all slices) otherwise I don't remove any from the iblt. This leads to the cliff effect I see. |
| 03:22:37 | rusty: | bramc: Someone did a java implementation which did that, for much more win. |
| 03:22:53 | bramc: | rusty, got a link for that? |
| 03:23:20 | bramc: | Also, I suspect that thresholding behavior is totally reasonable. If you're off, you're likely to well and truly to be able to get back anything |
| 03:23:21 | rusty: | bramc: kallen rosenbaum, commented on http://rustyrussell.github.io/pettycoin/2014/11/05/Playing-with-invertible-bloom-lookup-tables-and-bitcoin-transactions.html#Using-IBLTs |
| 03:24:25 | brisque: | bramc: still going to be slower than a direct TCP squirt, but I suppose it's a reasonable tradeoff if you can manage it. |
| 03:24:30 | phantomcircuit: | brisque, lol yeah derp previous black hash is perfect as a tweak value since it's (more or less) not controlled by the miner |
| 03:25:05 | rusty: | bramc: my next step was testing with some real blocks and txs, but never quite got that round tuit I need. |
| 03:25:12 | rusty: | Sorry, gtg. |
| 03:25:37 | bramc: | brisque, I think the whole context here is that it's supposed to be something for the fast relay network to redistribute |
| 03:25:45 | brisque: | phantomcircuit: if you're talking about blocks with bloom in them, you don't want the client to have to rebuild their filter for every single block |
| 03:26:04 | brisque: | phantomcircuit: it's sort of unavoidable though. |
| 03:27:05 | brisque: | if you're not I'm going to need to go read some scrollback for context. |
| 03:32:20 | phantomcircuit: | brisque, que? |
| 03:32:29 | phantomcircuit: | the bloom filter in the block would cover just that block |
| 03:32:31 | phantomcircuit: | nothing else |
| 03:33:11 | brisque: | phantomcircuit: yes, but you want to salt the filter to avoid people brute forcing elements in the filter which set all the bits to zero. |
| 03:33:23 | brisque: | set them to one, rather. |
| 03:36:55 | phantomcircuit: | brisque, right |
| 03:37:03 | phantomcircuit: | im thinking the previous blocks hash works well for that |
| 03:37:37 | brisque: | yep. |
| 03:37:37 | phantomcircuit: | it's effectively immutable (who is going to bruteforce a block such that the next blocks bloom filter has a high false positive rate??) |
| 03:37:53 | bramc: | If you cram a transaction's length into its id that should solve the variable sizes problem |
| 03:37:59 | brisque: | it gets uglier with big wallets unfortunately. |
| 03:38:30 | bramc: | phantomcircuit, An attacker knows the previous block when trying to attack the next block though. What's your problem with using the merkle transaction root? |
| 03:38:49 | brisque: | if you have 5000 keys in your wallet and 10,000 blocks to sync, you're going to be doing an awful lot of hashes. |
| 03:39:12 | bramc: | This IBLT thing is an example of Fun Things I Shouldn't Be Working On |
| 03:39:38 | brisque: | more like, Things I Should Be Paid For But Aren't Very Marketable |
| 03:40:00 | brisque: | you put the bloom filter in the block, and then we ride it all the way to the moon! |
| 03:40:26 | bramc: | brisque, I'm working full time on cryptocurrency stuff now but really need to keep focused on things which will actually help get a working project out the door |
| 03:43:18 | phantomcircuit: | brisque, maybe |
| 05:13:28 | petertod1: | petertod1 is now known as petertodd |
| 05:26:08 | s1w-: | s1w- is now known as s1w |
| 08:05:18 | wilhelm.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:18 | wilhelm.freenode.net: | Users on #bitcoin-wizards: andy-logbot Mably go1111111 lclc_ aburan28 Dr-G toffoo SDCDev hktud0 wallet42 damethos koeppelmann spinza zooko Visheate phedny dignork- s1w yorick_ face_ amiller_ petertodd iddo_ kanzure_ p15x_ nuke_ rusty RoboTeddy moa p15 moleccc nubbins` d1ggy_ justanotheruser LeMiner mkarrer_ afk11 arubi adam3us1 Emcy c0rw1n PaulCapestany vmatekol_ bramc napedia luktgf Iriez Luke-Jr dc17523be3 hashtagg Adlai waxwing michagogo yrashk btcdrak catcow Muis |
| 08:05:18 | wilhelm.freenode.net: | Users on #bitcoin-wizards: cfields Zouppen sneak coryfields_ binaryatrocity_ Starduster oaavi stevenroose tromp_ GAit shesek alferz gribble MoALTz__ Cory antgreen LarsLarsen jcorgan cryptowest_ ajweiss melvster berndj kinlo Logicwax kyletorpey midnightmagic Pan0ram1x devrandom crescendo wizkid057 bosma grandmaster harrow otoburb copumpkin wumpus jaekwon GreenIsMyPepper phantomcircuit jgarzik BlueMatt jaromil espes__ dgenr8 Apocalyptic gwillen dasource bbrittain fenn |
| 08:05:18 | wilhelm.freenode.net: | Users on #bitcoin-wizards: amincd HM2 prepost tromp eordano nickler Alanius PRab BananaLotus guruvan ryan-c lnovy DoctorBTC ebfull cluckj brisque sdaftuar veorq helo Hunger- xabbix runeks null_radix bedeho gmaxwell SwedFTP epscy nanotube andytoshi bliljerk101 starsoccer comboy nsh Taek EasyAt maaku NikolaiToryzin livegnik optimator fluffypony Meeh cursive yoleaux dansmith_btc [d__d] morcos Fistful_of_Coins dardasaba isis smooth Xzibit17 artifexd kumavis mariorz Krellan |
| 08:05:18 | wilhelm.freenode.net: | Users on #bitcoin-wizards: platinuum Oizopower BrainOverfl0w roasbeef so hguux__ MRL-Relay azariah btc___ throughnothing @ChanServ brand0 davout NeatBasis mr_burdell d9b4bef9 a5m0 Anduck CryptOprah leakypat TD-Linux K1773R indolering warptangent veox Eliel Graet jessepollak lechuga_ AdrianG warren gnusha heath wiz jbenet mappum eric JonTitor catlasshrugged Keefe |
| 12:25:56 | betarigs-admin: | betarigs-admin has left #bitcoin-wizards |
| 12:54:26 | face_: | face_ is now known as face |
| 13:16:51 | yorick_: | yorick_ is now known as yorick |
| 13:50:52 | nuke__: | nuke__ is now known as nuke1989 |
| 15:15:06 | fanquake: | fanquake has left #bitcoin-wizards |
| 15:29:06 | wallet42: | wallet42 has left #bitcoin-wizards |
| 15:30:24 | betarigs-admin: | betarigs-admin is now known as beta |
| 15:30:52 | beta: | beta is now known as betarigs-admin |
| 15:46:29 | c0rw1n: | c0rw1n is now known as c0rw|away |
| 15:47:01 | betarigs-admin: | betarigs-admin is now known as betarigs_admin |
| 16:23:24 | fluffypony: | this is neat: http://notanumber.net/archives/183/cuckoo-byte-stuffing-algorithm |
| 16:24:47 | fluffypony: | looks like it'd be much more efficient than COBS |
| 16:30:06 | ahmed_: | ahmed_ has left #bitcoin-wizards |
| 17:07:09 | tromp: | COBS? |
| 17:15:59 | fluffypony: | tromp_: consistent overhead byte stuffing |
| 17:18:03 | oaavi: | sounds delicious |
| 17:18:45 | gmaxwell: | man, I'm sure I've seen before someone do an escape with PRNG replacement on hit that was pretty close to this but don't remember the name. |
| 18:08:55 | kanzure_: | kanzure_ is now known as kanzure |
| 20:00:31 | RastaRoyale: | What do you think about the $120M "21" qualcomm deal? |
| 20:02:44 | RastaRoyale: | It seems like people have been trying to get mobile wallets to end consumers forever. |
| 20:03:33 | Adlai: | you think a mobile wallet needs $120 stealth funding? |
| 20:04:15 | RastaRoyale: | I guess it's not so stealth if it's clear that qualcomm is involved? |
| 20:04:54 | fluffypony: | RastaRoyale: #bitcoin is that-a-way |
| 20:06:33 | RastaRoyale: | ah thanks |
| 22:22:57 | AlexStraunoff: | AlexStraunoff is now known as NikolaiToryzin |