--- Log opened Sun Oct 13 00:00:05 2013
01:27 < warren> who is the primary person behind pull tester?
02:25 < sipa> warren: bluematt
07:13 < gmaxwell> petertodd: I just thought up another storage hard function. This one is super simple.
07:14 < gmaxwell> Say you have a tree structured pseudorandom function:   e.g   H(seed) = {Left half, Right half}  ... H(Left half) = {Left half, Right half}  and so on so a single seed can expand to a ginormous tree.
07:14 < gmaxwell> Server gives the client a random seed and the tree size.  The client goes and computes the leafs of the tree and stores the results.
07:15 < gmaxwell> Then the server can challenge the client:  The server randomly picks a leaf, evaluates it itself.. and says to the client "tell me what the index is for the leaf with value X"
07:16 < gmaxwell> the only efficient way for the client to answer would be to have computed a hashtable over the results... otherwise it has to recompute the whole tree.
07:35 < gmaxwell> yippie.
07:43 < gmaxwell> unrelayed: http://cryptome.org/2013/10/homo-crypto-sym.pdf  claims fully homorphic encryption with much better performance and only linear plaintext expansion. (factor of 16)
13:19 < amiller> i sort of have a wrench in the works as far as consensus theory goes
13:19 < amiller> i normally say something like 'every valid transaction is eventually included'
13:19 < amiller> but 'valid' is a moving target and can change, for example in a double spend when one transaction invalidates another
13:20 < amiller> suppose there were an opcode that let you refer to the current blocks' transaction height
13:20 < amiller> and you could make a transaction that was only valid every 1000th block
13:20 < amiller> would that transaction be guaranteed to get committed eventually?
13:21 < amiller> this is basically about whether a sub-50% attacker can consistently snipe a particular block as long as it's not too oftne
13:21 < sipa> well the script system is designed such that a transaction that is once valid, is never invalidated (except for double spending)
13:21 < amiller> well with multisigs the doublespend might not be in your control
13:21 < sipa> it is never in your control
13:21 < amiller> also this is specifically about a hypothetical new opcode
13:22 < amiller> it's in your control if you kept your private key private and don't do it
13:22 < sipa> one of your predecessors may double-spend
13:22 < amiller> good point
13:22 < amiller> hm
13:22 < sipa> it's why software doesn't allow you to spend without confirmations
13:23 < sipa> because it's not enough to trust coins you receive; you must also trust that they're unlikely to be reverted by the senders of the senders
13:24 < amiller> there's other related things like sd_lerner's suggestion to have 'invalid after <date>' opposite of locktime
13:26 < sipa> it does mean a receiver needs to track recent (all?) history of its inputs, to judge how likely they are to become permanently unspendable
13:27 < sipa> as a reorg of a transaction right at the border it very risky
13:27 < amiller> if it's safe to wait 6 blocks anyway, then that's enough
13:28 < amiller> like if you wait long enough that the last guy can't revert it, then no one before can either
13:28 < sipa> true
13:28 < amiller> but still my question is about the other direction
13:29 < amiller> how quickly can you get a tx in a block
13:29 < sipa> i wouldn't say it's always guaranteed that you can
13:29 < sipa> it depends on economic factors
13:29 < amiller> if someone wants to prevent you from getting a tx in even 1/1000 blocks, can they?
13:30 < sipa> assuming miners are greedy/rational and choose transactions with the highest fee/byte ratio
13:31 < sipa> all that's needed is someone constantly creating transactions with higher fee than yours
15:29 < HM3> or they could take your family hostage and threaten to beat them if you make said transaction.
16:39 < nanotube> or put a bounty of 80kUSD on the head of any miner who mines it into a block. >_>
16:39 < nanotube> to soon? :P
16:43 < nanotube> ... slowly getting my connection count back after node restart. up to 88 now.
16:57 < HM3> why aren't node addresses stored persistently?
16:57 < sipa> they are
16:57 < sipa> peers.dat
16:59 < HM3> ah
17:54 < nanotube> what's the default expiration of errors? i'm still seeing the 'check date and time' error in getinfo, though my timeoffset has settled to 0. (probably initially caused by my initial peer set being significantly off, i recall gmax mentioning something about there being some mistimed peers out there.)
18:00 < gmaxwell> nanotube: some error never go away (unless replaced by another one), thats one of them.
18:01 < nanotube> doh
18:02  * nanotube thinks it should go away once timeoffset drops below some threshold
18:02 < nanotube> though... it's rather immaterial.
18:07 < nanotube> well would you lookit this, a live bitcoin node counter: http://getaddr.bitnodes.io/
18:08 < HM3> cool site
18:08 < gmaxwell> yea, except the numbers on the front page are pure bullshit.
18:08 < gmaxwell> (they're counting addr messages)
18:08 < gmaxwell> if you click through to the report, e.g. http://getaddr.bitnodes.io/194/
18:09 < gmaxwell> the field "nodes_version (version)" is how many they actually connected to.
18:09 < HM3> i don't know why that is bad
18:09 < HM3> what is nodes_getaddr?
18:10 < gmaxwell> how many unique IPs they got from address messages.
18:10 < gmaxwell> which includes scads and scads of never-reachable addresses, due to god knows what.
18:11 < HM3> but those nodes may be connected out right?
18:11 < gmaxwell> Some, but most? Unlikely, considering the addresses include e.g. huge ranges of sequential numbers.
18:11 < nanotube> gmaxwell: oh... crap. and there i was being happy we have 100knodes.
18:12 < HM3> so probably people with dynamic IPs
18:12 < gmaxwell> HM3: out only nodes don't announce themselves in any case.
18:12 < HM3> stale messages
18:12 < HM3> ah
18:12 < gmaxwell> HM3: and moronic dos attacks, and misconfigured firewalls, and who knows what.
18:13 < sipa> my crawler tracks 66k addresses now
18:13 < sipa> of which it considers 3.8k "good"
18:13 < nanotube> what's 'good', how many have been reachable within the past 30days?
18:13 < sipa> it has also banned 730k addresses for being consistently bad :p
18:13 < nanotube> heh
18:13 < sipa> the rules are fuzzy and too complex
18:14 < sipa> go read the source :p
18:15 < nanotube> haha well, 'really roughly'
18:16 < HM3> so probably bigger than Tor in terms of relay nodes, but probably smaller than the number of skype users who signed off in the time it took me to type this.
18:16 < nanotube> lol yea
18:16 < gmaxwell> well, in particular, it means we're dangerously close to runing out of sockets.
18:17 < gmaxwell> (even absent an attack)
18:17 < HM3> what?
18:17 < gmaxwell> as 4000*125/8 = 62500 ... so it means that we can only support 62500 nodes with good listeners (including bitcoinj nodes and such that would never announce)
18:18 < nanotube> hm well, it seems we're not /that/ close. after a day-ish of uptime, i'm only at 83 connections out of 512.
18:18 < gmaxwell> nanotube: 83 is 66% of the normal capacity.
18:18 < nanotube> if we were really close, i presume my slots would fill up much faster.
18:18 < gmaxwell> (I think 2/3 is not super comfortable)
18:19 < gmaxwell> (and the /16 limitation means that we're not very equally distributed)
18:19 < sipa> nanotube: https://github.com/sipa/bitcoin-seeder/blob/master/db.h#L103
18:19 < nanotube> sure, i dig.
18:19 < gmaxwell> It's not urgent yet, but it seems we have a trend that isn't good either.
18:19 < HM3> what's this socket limit about?
18:20 < nanotube> HM3: listener nodes allow 125 max inbound connections by default.
18:20 < gmaxwell> HM3: we have memory usage per peer, so there is a limit to the number of concurrent peers. Right now the default limit is 125 (and few nodes adjust that)
18:20 < nanotube> non-listener nodes try to make 8 outbound.
18:21 < HM3> oh i see
18:22 < gmaxwell> Obviously one path is to try to really get the per peer resources down so we could have nodes with a thousand peers or whatever... but thats resource heavy, and still leaves the network more DOS vulnerable than one with just more nodes.
18:22 < HM3> so you need a listening node to out node ratio of 125:8
18:22 < nanotube> though 4k listening nodes at 125 each suggests that we should have 500k open slots.
18:22 < HM3> with perfect meshing
18:23 < gmaxwell> nanotube: yes, but nodes use 8 slots... sooooo. at 62k we start to saturate.
18:23 < HM3> err 8 : 125
18:24 < gmaxwell> of course, this is absent attacks. One issue with this model is that an attacker with a single IP can use 1/slots of the whole network's capacity, even if we implement kicking off duplicate connections. (thus conversations about things like proof of storage and private bloom queries)
18:24 < nanotube> gmaxwell: yea, but if we put in your logic about randomly dumping peers based on some scoring criteria, thus ensuring node churn, being at 62k nodes won't be a big problem.
18:25 < nanotube> but yes, certainly it's something we need to think about before it becomes a problem.
18:25 < gmaxwell> nanotube: or at least less of one, if the order of nodes drops too far the risk of partitioning increases. (though thats a reason e.g. to priortize peers that give you novel transactions and blocks)
18:26 < nanotube> mm
18:26 < nanotube> anyway.. foodtime. o/
18:26 < HM3> Why is there a high memory cost to a connection?
18:26 < sipa> buffers
18:27 < HM3> I mean I have a Bittorrent client that maintains hundreds of connections
18:27 < sipa> and quite some state
18:27 < HM3> still uses less memory than bitcoind
18:27 < gmaxwell> HM3: most of bitcoinds memory is not connections right now.
18:29 < HM3> any thoughts on how you'll solve it?
18:30 < sipa> adding a builtin solitaire in bitcoin-qt may increase the number of fullnodes?
18:30 < gmaxwell> We need more nodes regardless, we could do things to scale up the connection count... but I think thats less important simply because if we have only a couple thousand nodes its too trivial to dos them regardless of their max connection counts.
18:30 < gmaxwell> Once we have headers first and pruning there should be less disavantage to running full nodes.
18:31 < gmaxwell> It may also be that we can't solve it before a major outage happens, because right now users don't think they have any personal reason to take the costs of running a full node. :(
18:32 < HM3> bundling. integrate bitcoind in to a popular torrent client so people can tip seeders :P you'll have millions overnight
18:33 < gmaxwell> and then someone implements another version that uses a SPV node instead, and you'll lose millions overnight.
18:34 < HM3> well then you play the starving hacker card and say serving "Linux ISOs" is a team sport
18:34 < gmaxwell> If that worked, then we could use Bitcoin users — who presumably already have more skin in keeping bitcoin running.
18:35 < sipa> fancy graphs!
18:35 < sipa> and some animations
18:35 < sipa> how the chain is being built
18:35 < sipa> matrix-style
18:35 < HM3> defrag style
18:35 < HM3> coloured blocks
18:36 < sipa> yeeeees
18:39 < HM3> how many fullnode implementations are there out there now?
18:40 < gmaxwell> correct ones? who the fuck knows. I have very little confidence in the other teams, most of them have not even run and passed the block tester.
18:40 < gmaxwell> It's a very hard task.
18:40 < sipa> bitcoinj has one (certainly incomplete), btcd, bitsofproof, ...
18:40 < sipa> no idea how correct they are
18:40 < sipa> i'm sure there are a ton other attempts
18:40 < HM3> i think btcd guy said he had passed some of your tests?
18:40 < gmaxwell> btcd talked a good talk but was trivially forked.
18:40 < sipa> but those are certainly near-complete
18:41 < HM3> ah
18:41 < sipa> gmaxwell: which rule did they miss?
18:41 < gmaxwell> sipa: they were evaluating validity in untaken branches in scripts.
18:41 < sipa> ah
18:41 < gmaxwell> (and their response was to try to report it as a bug and suggest we fix it)
18:42 < HM3> lol
18:42 < gmaxwell> ::shrugs::
18:42 < HM3> please do, i might be richer on that fork :P
18:42 < sipa> do they even understand the concept of a hardfork?
18:42 < sipa> or rather, the distinction between soft and hard forks
18:42 < gmaxwell> I don't know. I can't tell. They're eager to please.
18:42 < gmaxwell> So everything I say they agree with.
18:44 < gmaxwell> (which I suppose is better than arguing with everything)  But I just don't know how hard they're working at it. They've not discovered any surprising behavior on their own, which is my normal benchmark, but that only works for so long.
18:44 < gmaxwell> (eventually I become all knowing and so no implementations can tell me something I didn't know. :P)
18:45 < sipa> which, ironically, makes you the #1 person capable of writing an alt fullnode
18:45 < jgarzik> maxcoin?
18:45 < sipa> i wonder how well i'd do implementing bitcoin from scratch, only looking up constants and opcodes and stuff
18:47 < sipa> BlueMatt: seems the comparisontool jar you gave me doesn't even accept current bitcoind...
18:47 < sipa> as in git head, pre-headersfirst
18:48 < gmaxwell> There are degrees of knowing. I knew how the evaluation logic worked, but I might have made the same evaluation mistake even though I "knew" better.
18:49 < HM3> it's probably easier to make a specification for the post-hardfork version
18:50 < sipa> HM3: i've been wanting to write a bitcoin-like thing from scratch for a while, with all sillyness (in my opinion, of course) fixed :p
18:50 < gmaxwell> well, don't think a good spec magically makes this stuff easy. It just makes it slightly less awful.
18:50 < HM3> sure, and nobody follows specs anyway
18:50 < sipa> finding time for that is obviously a joke
18:51 < jgarzik> a good spec is simply Knuth's semantic programming
18:51 < gmaxwell> If not for the need to have a fast database as part of the validation logic I'd argue that you could do a lot about extracting all the validation logic into some code which could simply be used (and machine translated to other languages even).
18:51 < jgarzik> code -- organized like a book for easy reading
18:51 < gmaxwell> Right. What matters is the behavior. Any spec accurate enough to be complete should be _technically_ executable, though we may lack a compiler for it if the choice of langage is poor (e.g. english)
18:52 < gmaxwell> (of course any complete spec in english wouldn't really be in english, it would be in some domain specific english which has formally defined out the ambiguity.)
18:53 < HM3> lolcat
18:54 < gmaxwell> E.g. if not for the database, I'd totally be tempted to say "here is your spec, it's in literate C with ACSL annotations for proving correctness. If you want a python node, you compile the code to mips assembly and use a tiny MIPS emulator to run the spec" :P  but this becomes lame the larger the normative part is.
18:54 < sipa> can i hazh block?
18:54 < gmaxwell> HM3: https://en.wikipedia.org/wiki/LOLCODE
18:54 < HM3> lol
18:54 < sipa> kthxbye
18:55 < HM3> the lolcode logo is a block shaped cat
18:55 < HM3> it's an omen i tell you
18:56 < HM3> and CATena is italian for chain
19:10 < HM3> I'm on the hunt for a new personal project
19:12 < HM3> all out of ideas though, it's a time of year thing i think
19:38 < gmaxwell> petertodd: fwiw, https://bitcointalk.org/index.php?topic=310323.msg3332919
19:43 < jgarzik> two coins I would actually like to see:  theorycoin, and notarycoin
19:43 < jgarzik> the former for "what bitcoin would be, if written from scratch" and the latter being a smart property / data timestamping chain
19:44 < jgarzik> if the latter were merge-mined and commonly used, could take some pressure off main chain data timestamping
19:49 < sipa> theorysipacoin: merkleized abstract syntax tree script, script+txid-indexed utxo set as state, transaction destinations specified as H(script) while in-chain H(H(script)), no malleability in signatures, pubkey recovery for small inputs, payment-protocol only (p2p is just for broadcasting to miners), txouts state the size/cpu limitations of the script that will spend them, tx fees go into a to-be-mined pool which is only partially paid out in...
19:49 < sipa> each block
19:50 < HM3> i'd add a better name to that list
19:50 < HM3> :P
19:50 < sipa> (none of these are original ideas, btw)
20:10 < gmaxwell> I was joking that it should be called scamcoin in order to discourage use. But then someone went and created an altcoin called scamcoin.
20:10 < gmaxwell> And people are using it.
20:10 < gmaxwell> So... Well. I'm worthless apparently. :P
20:13 < HM3> hobocoin
20:21 < warren> did they buy scamcoin.org?
20:22 < gmaxwell> hell if I know? Do you think they could buy it with scamcoins?
20:23 < HM3> namecoins :P
20:26 < jgarzik> outflank them.  get scamcoin.us, scamcoin.eu, scamcoin.asia, scamcoin.africa, ...
20:26 < warren> yeah, because if you bought all *coin*.* domains, that'll stop future clones.
20:27 < gmaxwell> "our scamcoin 1000x more scam. Using only pure unadulterated conjectural cryptography!"
20:27 < warren> nevermind the coins that exist only as forum threads.
20:27 < warren> the client download is stored in 5,000 avatars uploaded to bitcointalk
20:28 < warren> they are unable to upgrade their client now due to the bitcointalk lockdown
20:28 < HM3> .io are where all the cool people are these days
20:28 < sipa> .io?
20:28 < warren> EIE.io was sadly taken.
20:28 < HM3> http://techslides.com/io-domains-in-alexa-top-1-million/
20:54 < warren> jgarzik: how did you learn about the china visa thing?
20:59 < amiller> gmaxwell,
20:59 < amiller> on your storage hard scheme
20:59 < amiller> isn't it roughly the same as fabien coelho's nearly-constant verification merkle tree?
20:59 < amiller> the premise of that is that you generate all the leaves of a merkle tree
20:59 < amiller> then the root
21:00 < amiller> then you use the hash of the root as an index to select a particular index
21:00 < amiller> your proof is the branch from the root to a few of the leaves
21:00 < amiller> the only difference is that you're recommending using predefined data at each leaf rather than some prf
21:00 < amiller> and the way you've described it there's interaction (which is fine)
21:01 < amiller> rather than noninteractively using the root hash to choose the branch to squery
21:01 < gmaxwell> The goal isn't achieved without interaction.
21:01 < amiller> i'm not sure why not but it's orthogonal in any case
21:01 < gmaxwell> You could indeed use fiat-shamir to make a kind of non-interactive proof out of it, but thats really orthogonal.
21:02 < gmaxwell> (and the non-interactive portion really would not be useful. Since you could just perform it once and then delete the data, and then again and again and have 100,000 connections)
21:05 < amiller> i really like the idea overall
21:05 < amiller> the use of pow for eaxctly this purpose (preventing connection DoS) is known as client puzzles and is one of the most common proposed uses for pow but no one actually has used it (other than captcha, arguably)
21:05 < gmaxwell> Do you see what I'm saying here about not being able to make it non-interactive?  We want a proof of "integral storage" e.g. not storage for a moment, but for the whole time you're connected.
21:06 < amiller> well yeah so the recipient periodically has to interact no matter what
21:06 < gmaxwell> e.g. you use a finite resource (storage) but only so long as you're connected, and then you get it back.
21:06 < amiller> it's about preventing precomputing basically
21:06 < gmaxwell> yea, but thats really cheap.. one disk lookup periodically.
21:06 < amiller> or you could use the blockchain
21:07 < amiller> make each challenge depend on the newest blocks
21:07 < gmaxwell> You could do partial non-interactive by basically doing a kind of signature of knoweldge using it.
21:07 < gmaxwell> Right, or just any message you send.
21:07 < amiller> sure
21:07 < amiller> we agree here
21:07 < gmaxwell> You send a message H(message) that tells you the challenge.
21:07 < gmaxwell> and it proves you have this big table sitting around just for that peer, and you're not multiplexing a zillion peers.
21:07 < amiller> i really think there's a deep solution using PoW to baiscally replace IP based routing even
21:08 < gmaxwell> I think this idea is really simple and easily implemented too, I have no idea why it took me so long to come up with it.
21:09 < amiller> how do you tune it
21:12 < gmaxwell> well, I think it likely has a pretty wide range of acceptable parameters. e.g. I don't think 1GB is that burdensome even on a smartphone (new ones now have 32 gb storage, I think?) and yet 1TB connect to 1000 peers sounds like a ton. even  1TB for 8192 peers (128MBytes per connection) sounds like a fairly effective deterrent.
21:12 < gmaxwell> An obvious way is to just keep the N most costly POSs subject to some threshold, and just tell peers how much storage they need in order to make the cut.
21:13 < HM3> my phone has 8 GB of space, my laptop has 8 TB connected to it right now
21:13 < HM3> 1 GB on the phone is not cool
21:13 < gmaxwell> HM3: add a microsd card.
21:13 < HM3> no slot damnit
21:14 < gmaxwell> well, in any case, As I said, "new ones".  I think the parameters generally work out okay. You could certantly do 128MBytes, right?
21:14 < HM3> i guess
21:15 < HM3> is this a proof to ensure people are using fullnodes?
21:15 < HM3> tx history
21:15 < gmaxwell> No.
21:16 < gmaxwell> It's not. Go read the post. Its to make it harder for an attacker to be able to DOS the whole network as soon as they're able to DOS just one node.
21:19 < gmaxwell> sipa: http://bitcoin.sipa.be/speed-lin-2k.png  < ready to rerange your charts again? :P
21:20 < HM3> "ifficulty"
21:21 < gmaxwell> amiller: I can't really think of an application for the fully non-interactive version of this.. like "I had a bunch of storage once" seems kinda odd. :P
21:26 < HM3> 2 petahash/s
21:55 < jgarzik> warren, US State Dept website
22:35 < nanotube> what's the china visa thing?
22:35 < nanotube> gmaxwell: wouldn't the server also have to store the entire 1gb, for each of the clients it's using the PoS scheme for?
22:37 < HM3> damn Lamport invented Paxos as well
22:42 < gmaxwell> nanotube: nope.
22:42 < gmaxwell> nanotube: the function allows efficient random access by index, but not by vale.
22:42 < gmaxwell> er value.
22:44 < jgarzik> nanotube, longtime desire to visit China
22:44 < jgarzik> nanotube, been studying Mandarin off and on for a couple years, studying its history for longer
22:44 < gmaxwell> e.g. say the tree is 32 levels high (so 4 billion outputs, or maybe 50Gbytes). The server pickes index 0 to challenge the client to provide. It then just has to compute 32 hash operations (H() take left H() take left H() take left...) and then it knows the value at index 0.  Then it asks the client to provide the index for that value.
22:45 < nanotube> jgarzik: ah cool. hf! i was in china for a week once, in shanghai. still don't speak a lick of chinese.
22:45 < jgarzik> nanotube, hoping to catch a meetup in Hong Kong or mainland, or even better, flash the "core dev" badge and get invited to a speaking event somewhere in PRC
22:45 < nanotube> gmaxwell: aaah i see. it asks for index by value, not value by index.
22:45 < gmaxwell> so because of the tree structure H() is efficient without storage in one direction.. but running it backwards requires storage to be efficient.
22:45 < gmaxwell> nanotube: yup.
22:46 < nanotube> in that case... carry on. :)
22:46 < gmaxwell> nanotube: well, I still dunno that anyone would want to use it! but I now haz a construct.
22:46  * nanotube missed that part in reading your post >_<
22:47 < HM3> gmaxwell, clever
22:47 < nanotube> i think it's pretty cool, as far as raising dos costs
22:48 < jgarzik> I'm incredibly thrilled, though unsurprised, that Chinese like bitcoin.  Under a layer of thick communist oppression, there is an amazing undercurrent of raw capitalism in China.  Sometimes they are more libertarian/capitalist than Americans, though they basically operate under "wrath of God" mode:  In china, you will be OK as long as you don't wander into the political realm or make.  If you do, they aim a huge cannon at you
22:48 < jgarzik>  and your business.
22:48 < jgarzik> *make waves
22:49 < jgarzik> hopefully bitcoin gets entrenched. freedom++
22:49 < nanotube> heh
22:49 < nanotube> aye
22:49 < HM3> sell treasuries, buy bitcoin :P
22:50 < nanotube> gmaxwell: what prevents the attacker from calculating the hash tree on the fly when needed? 2^32 hashes are pretty fast to calculate.
22:54 < gmaxwell> nanotube: Adjust the hash cost vs size to taste. E.g. last step in the tree can just iterate the hash N times. It needs to be just slow enough that simply recomputing it every query isn't a win.
22:56 < gmaxwell> But yea, this is a bit of a pain, because you can get a hardware speedup on that. Point.
22:57 < nanotube> yea, stick a couple of ati gpus on your attack node, and you'll outcompute anything running on a vps.
22:59 < gmaxwell> nanotube: well, not quite that bad, I mean the storage full clients has a ~4 billion advantage factor over your gpu device once their table is built.
23:00 < nanotube> well, 4billion/32 :) so only 134million advantage.
23:01 < nanotube> i suppose if the challenge/response in frequent enough
23:01 < nanotube> you won't be able to maintain too many connections even with significantly more computing power.
23:02 < nanotube> it just has to be something on the order of minutes, rather than on the order of days/hours.
23:03 < gmaxwell> right, and its cheap for the server so it could be querying you once every minute or two.
23:03 < nanotube> yes, and a 'legitimate' storage client should have no problem responding.
23:03 < nanotube> mk then, back to our regularly scheduled programming. :)
23:03 < gmaxwell> yea, not even a burden to query fairly often.
23:15 < nanotube> hm, so if we're targeting 1gb storage, and a sha3-512 hash is 64bytes, we can store roughly 2^24 hashes in the tree. which gives us roughly a 2^20 advantage for query vs response. since a couple-gpu box is roughly 2^10 faster at hashing than a cpu, that makes the attacker a disadvantage of only 2^10. still not bad. a couple-gpu box could probably handle a hundred or so connections without using storage... but at this rate it's cheaper t
23:15 < nanotube> o just buy a few 1tb hdds and handle even more.
23:16 < gmaxwell> nanotube: well not quite, you don't need to store the whole hash.
23:16 < nanotube> speaking of which... i could buy 10 1tb usb disks for roughly $700. which is the cost of maybe 1 high-end ati gpu.
23:16 < nanotube> so for 1gb per connection, it'd only cost me 700 bucks to eat up 10k slots.
23:17 < nanotube> which is still a lot more than what it'd cost me right now to eat those same slots, i suppose.
23:18 < nanotube> gmaxwell: ok fair point. by storing only a large-enough-to-effectively-guarantee-uniqueness subchunk of a hash, we can achieve a much higher compute cost per GB.
--- Log closed Mon Oct 14 00:00:08 2013