--- Log opened Thu Oct 24 00:00:38 2013 00:09 < amiller> petertodd, so about DIANNA 00:10 < amiller> it claims that by being requiring that it contains a hash to a prent block in the Bitcoin chain that it's invulnerable to a 51% attack on DIANNA miners, as long as there's no 51% attack on Bitcoin proper 00:11 < amiller> and that just absolutely doesn't work 00:12 < gmaxwell> I tried to tell people about that on some other recent MM thread, but my patience in arging with people is, in fact, not boundless. (shocking, I know) 00:12 < petertodd> I think we found a bug in gmaxwell 00:13 < gmaxwell> Unfortunately I wasn't able to come up with a crisp statement about the security model, at least in the general cause absent a lot of implementation details. 00:13 < petertodd> I haven't gotten around to reading it, but it's probably vulnerable to data hiding attacks where you timestamp your chain and release it later 00:14 < gmaxwell> petertodd: if bitcoin miners aren't also XXX miners then a tiny minority of bitcoin hashpower can insert $bad or whatever commitments for the other thing. What happens then depends on the details of how the other thing works. 00:14 < petertodd> I wouldn't assume it's worthless though; it looks like in specific conditions timestamping instead of proof-of-work can work, for consensus although the incentives get weird and you become subject to attack by bitcoin miners 00:15 < amiller> oh i think i get it 00:15 < amiller> okay it is how i thought it was before 00:15 < amiller> so it does have to be a valid bitcoin block 00:15 < gmaxwell> petertodd: perhaps not worthless, but strong statements like "as strong as bitcoin" can't be true. 00:16 < petertodd> amiller: yeah, that's the only sane way to do it 00:16 < amiller> ugh i can't tell whether "the longest dianna chain" is choosen just by chronological order in bitcoin or whether it adds up the difficulty 00:16 < amiller> i think there isn't even any code for this for me to dredge through 00:16 < petertodd> gmaxwell: nope, OTOH statements like "way stronger than your shitty MM chain" can be 00:16 < gmaxwell> amiller: haha this totally sounds like this discussion: https://bitcointalk.org/index.php?topic=313347.0 00:16 < amiller> anyway in either case it offers no security beyond being an otherwise merge mined chain so they're flat wrong 00:16 < petertodd> if there's no code I wouldn't put too much effort into it 00:18 < amiller> ok, deletd 00:19 < amiller> btw i'm working on a paper to submit to IEEE Security and Privacy, in 3 weeks, the academic security conference for bigshots 00:19 < amiller> it's a "systemization of knowledge", so kind of a survey, but this one is about protocols using bitcoin as a platform, and all the proposed ideas for modifying bitcoin and altcoins, etc 00:20 < amiller> i'd paste a link but it's in too poor shape atm :/ 00:20 < petertodd> oh yeah? I'm working on something about colored coins, which has kinda extended a bit into consensus systems in general 00:21 < petertodd> I'll post a link because I have no shame: https://github.com/petertodd/decentralized-consensus-systems 00:24 < gmaxwell> petertodd: https://bitcointalk.org/index.php?topic=317028.0 < perhaps they need some contract work done to produce nice proofs of ownership investors can check. 00:24 < petertodd> gmaxwell: good idea. 00:24 < petertodd> there was another group at the conf with a similar problem 00:25 < gmaxwell> if we're to have a future which isn't stuffed full of fractional reserve the tools need to exist soon so the community can force them onto people. 00:25 < gmaxwell> but it would be nice if someone who wanted them as a competative advantage would pay to get them built. 00:26 < amiller> what is the challenge with making a merkle tree storage-hard pow 00:27 < gmaxwell> no one who cares a lot about alternative pows has enough braincells to understand why such a thing would be desirable? 00:27 < amiller> i thought the scheme i described a long time ago that's based directly on dwork&naor memory-bound moderately hard puzzles works fine and is "asymmetric" in the sense that it's cheap to check rewgardless of how much work it takes 00:27 < gmaxwell> oh you mean for the proof of storage once. 00:27 < amiller> yes 00:28 < amiller> petertodd just reminded me about it 00:28 < gmaxwell> amiller: your stuff is more like "Proof of storage throughput over some data" 00:28 < amiller> right it involves reading instead of writing and reading 00:28 < gmaxwell> amiller: the storage-hard stuff we're talking about is proof of using up space. 00:29 < gmaxwell> (no real throughput component at all) 00:29 < amiller> and a merkle tree over it is too hard? 00:29 < amiller> oh 00:29 < amiller> but the space can be arbitrarily large 00:29 < amiller> as a parameter 00:30 < gmaxwell> amiller: yea. The idea is that you can use temporarily chewing up disk space as a gatekeeper to opening a peering connection, so that a diskspace bounded attacker can't use up all the connection capacity on the network. 00:31 < amiller> okay i think i see 00:31 < gmaxwell> (also has the benefit of basically zero hardware specialization gain, even stronger than any memory hard throughput function has) 00:32 < amiller> well i dont see about that 00:32 < amiller> you can make the memory hard throughput puzzle (or if you don't need it to be a scratchoff puzzle you can just do a single proof of tretrievability which is like one round of that) use arbitrary as much space 00:33 < petertodd> gmaxwell: and no, no luck in getting them mined 00:33 < gmaxwell> sure, but throughput puzzles at least have gains from making faster space. Bulk storage is one less thing to optimize for. And it can avoid an ongoing cost. 00:34 < amiller> well forget throuhgput, this isn't for mining 00:34 < amiller> it can be interactive challenge/responsse 00:34 < amiller> you can make them commit to an arbitrary merkle tree of power-of-two number of leaves n 00:35 < amiller> each leaf i consists of H(challenge || i) 00:35 < gmaxwell> amiller: for the goal I stated you need different state per every "server" or a client could have one copy of the data and connect to 100k servers. 00:35 * gmaxwell lets you talk 00:36 < amiller> okay so to make it a little easier do H(verifierID || i) for each leaf i 00:36 < amiller> (so they don't have to interact with you before preparing their disk) 00:36 < amiller> then verifier sends a challenge 00:36 < gmaxwell> and the challenge is? 00:36 < amiller> random string to use for this session or the next five minutes or whatever 00:37 < amiller> generated by the verifier (the person who's about to accept a connection if the puzzle is responded correctly) 00:37 < gmaxwell> and what happens next? 00:38 < gmaxwell> (what does the responder do with the challenge?) 00:38 < amiller> you use that challenge as seed to a prf to generate random plinko paths down the tree 00:38 < amiller> the responder returns with some k number of merkle tree branches each long n 00:38 < amiller> log n* 00:38 < gmaxwell> great and you do that and you conclude that you should end up at ID 8 00:38 < gmaxwell> and then you compute H(verifierID || 8) 00:39 < gmaxwell> Where is your storage hardness? :P 00:39 < amiller> you need to produce the whole merkle branch 00:39 < amiller> that's really hard unless you've precomputed and stored it 00:39 < amiller> maybe it should be H(verifierID || proverID || i) 00:39 < amiller> so that multiple peopel can't share the same disk to sybil connect you 00:39 < amiller> but still the point is you make the leaves easily computed 00:40 < gmaxwell> amiller: nah, I can compute the data once, and just store the top N levels of the tree. (just a few hashes) 00:40 < amiller> but you make it so you basically need nearly all of them to answer a response 00:40 < gmaxwell> then I get a 2^N speedup in computing the answer. 00:40 < amiller> i see and then recompute some of them 00:40 < amiller> hm. 00:40 < gmaxwell> (I actually have a solution to this, I'm toying with you to see if you come up with it too, I was surprised at how long it took me) 00:40 < gmaxwell> (or if you come up with another one) 00:41 < amiller> uh, well, the next thing i usually think of is where each leaf depends on the previous so you actually have to compute them sequentially 00:41 < amiller> but that's hard to verify efficiently (at least i don't know how) 00:41 < gmaxwell> yea, but then how does the verifier not have to do the same 00:41 < gmaxwell> exactly. 00:42 < gmaxwell> okay, I give you my solution: https://bitcointalk.org/index.php?topic=310323.0 (when you care to look, it's simple) 00:42 < amiller> there might be trapdoor kind of things where the verifier has a shortcut but the prover has to do it sequentially 00:42 < amiller> that kind of thing is generally much easier in this interactive setting 00:44 < gmaxwell> amiller: yea, I came up with something which followed that description pretty exactly using fully homorphic encryption. (Basically the challenger asks the prover to run a secret sequential function, saving the intermediate results.. and with knoweldge of the function the challenger can instead run an algebraically simplified version) but FHE = yuck. 00:45 < gmaxwell> fortunately there is a simpler way. 00:46 < amiller> i've read that three times (at various times in the last two weeks) and haven't gotten it 00:46 < gmaxwell> wow, sorry. :( 00:46 < amiller> but now that i've paged in all the other naive ideas i can probably close the gap now 00:46 < amiller> "The server then can periodically pick a random index and perform log2(size) hash operations to determine the value at that index and then can challenge the client to provide the corresponding index for that value. 00:46 < amiller> " 00:46 < amiller> could you write that part out? 00:47 < gmaxwell> H(verifierID || proverID) is the seed to a tree structured pseudorandom function. E.g. you have efficient random access to this pseudorandom function. 00:47 < gmaxwell> the prover hashes the leaves of this function and stores the results. 00:48 < gmaxwell> The verifier picks a random leaf, computes its hash, and challenges the prover to tell it the matching index. 00:48 < amiller> i get how {Left, Right} = H(seed) is used to construct the tree the first time 00:49 < amiller> ohhh..... you sort the leaves when you're done 00:49 < gmaxwell> Right. 00:50 < amiller> can't you estimate the path for a value pretty closely 00:50 < gmaxwell> I'm asking you to have performed precomputation for a preimage attack on this function. 00:50 < gmaxwell> If you only know the seed and I ask you "What index leaf value begins with 0xDEADBEEF" what do you do? 00:51 < gmaxwell> There is nothing to estimate, its strongly pseudorandom, you couldn't do better than decoding sequentually until you find 0xDEADBEEF 00:52 < amiller> okay i think i get it 00:52 < midnightmagic> gmaxwell: It's computed on-the-fly as the server asks for it? 00:52 < midnightmagic> (first time rather) 00:53 < gmaxwell> midnightmagic: first time, I suppose. But the idea is to pick parameters where if you don't store the result you'll be wasting a ton of computation recomputing the whole thing for every challenge. 00:53 < gmaxwell> Where otherwise it would be just a couple IOs to find the right answer. 00:53 < amiller> it takes n log n setup time 00:53 < amiller> where n = 2^k 00:54 < midnightmagic> gmaxwell: I imagine th eguard time to allow the client time to compute would be spent just idling? What happens before the table is finally computed? 00:55 < gmaxwell> midnightmagic: if you made the seed H(your ip || peer's IP) you could actually compute it offline before ever trying to connect to them. 00:55 < gmaxwell> (argument against actually using IPs is nats, alas... more pratically you could connect, get your challenge and get kicked off, then come back later with your table built) 00:55 < midnightmagic> gmaxwell: In order for the server to verify that, it would also need to do it, but it doesn't know in advance who's going to connect? 00:56 < gmaxwell> midnightmagic: nope, the idea here is that the server doesn't need to do anything expensive to verify. 00:56 < gmaxwell> The function is fast to run in one direction, but not the other. :) 00:56 * midnightmagic reads it again.. 00:57 < midnightmagic> ah. 00:57 < gmaxwell> The server picks an index at random, and then does log2(N) hash operations to find the leaf value at that index. (thats cheap) 00:57 < gmaxwell> then it gives you the leaf value and asks you for the index. 00:58 < midnightmagic> I guess Evil Server sits and listens for 50,000 incoming connections, has the client do single lookups, and disconnects without actually being a bitcoin node? 00:59 < gmaxwell> midnightmagic: perhaps. The way I envision this is that you'd have a server you already like, and you do this protocol with it to get yourself a privleged connection slot. So if the server gets dos attacked you don't get punted. 00:59 < midnightmagic> so we're talking one-way trust in that case. client knows the server is happy, server doesn't know the client is happy. 01:00 < gmaxwell> so if nodes are doing this only with servers they already like, the evil server attack isn't so concerning... but indeed, thats a point. 01:00 < midnightmagic> makes sense, I like it. 01:00 * midnightmagic files away conceptual technique for application to other things 01:01 < midnightmagic> the tahoe people were trying to do proof-of-storage to try to prevent servers from claiming they had data but actually not having it at all, and misleading clients into thinking the file was safe. 01:01 < midnightmagic> (without transferring the files) 01:05 < gmaxwell> this only works, sadly, with random data... but the reason for that is it requires the verifier to have never done the work. if you don't mind the verifier having had the data at one time, you can do this easily. 01:05 < midnightmagic> i wonder if the prng seed could be used to build an un-precomputable path through the blockchain 01:08 < midnightmagic> i guess that doesn't increase resources more than every bitcoin node already has. 01:08 < gmaxwell> sure but you'd have that same data for all peers, so it wouldn't stop you from connecting to 100k nodes successfully. 01:09 < gmaxwell> (otherwise, yea would be best to make the data bitcoin data, since the verifier already has that, and it's in our interest to copy it) 01:34 < amiller> gmaxwell, https://gist.github.com/amiller/7131876 http://codepad.org/Nzp2Vdsk 01:34 < amiller> seems fine to me now, i buy it 01:44 < amiller> i don't know why no one has done that before but i don't think i've seen anything like it 01:44 < amiller> really cool 01:52 < amiller> hrm it kind of isn't such a great tradeoff because there's a long setup time 01:52 < amiller> i mean, the setup time is the time to fill the disk, plus to sort it 01:52 < amiller> you would want like a btree kind of sort anyway which would be kind of slow 01:52 < amiller> i guess that's where the idea left off 02:00 < amiller> it would be really good to reduce the I/Os by the k factor 02:01 < amiller> the merkle tree based solutions have that problem too, pretty much 02:01 < amiller> well not exactly because you can go straight to the data which can be large than the index 02:32 < gmaxwell> amiller: did you see my similarly structred idea for lamport keys? I've still not seen anything like that either, they're kinda related. 02:32 < amiller> gmaxwell, no 02:35 < gmaxwell> amiller: so, you have a firm mental model for lamport right. And that you can put your public key in a hashtree and use the root.. when you sign you reveal the preimages selected by the message bits and then only the minimum necessary set of tree fragments to show that your preimages came from the right public key 02:35 < gmaxwell> e.g. you can send less than hash_size * 2 hashes because of common branch compression in the pubkey. 02:37 < gmaxwell> So take the same idea and use the same kind of tree csprng to expand a single secret value to all your secret values. Now when signing you can do the same kind of tree compression of the hash preimages! you selectively reveal chunks of the tree-csprng state so that the verifier can recover the preimages you were required to reveal and no others. 02:38 < gmaxwell> this is actually far more powerful for things other than lamport though. 02:38 < gmaxwell> It has powerful applications to making protocols for secure permutations (e.g. voting) use less bandwidth. 02:39 < gmaxwell> e.g. You want me to permute some ballots but don't want me to cheat and replace them. 02:39 < gmaxwell> I produce 200,000 permuted sets and commit to a hashtree of them. 02:40 < gmaxwell> The hash tells me which ballot is the one ballot we're going to use, and then I reveal the log2(n) secrets required to recover all 200,000-1 other ballot sets and check my root. 02:41 < gmaxwell> so now we can do a secure shuffle and only send 2*log2(security parameter)+few hashes 02:50 < gmaxwell> it's an idea I'd like to publish but I just don't have the free cycles to actually determine if its been published before. 02:50 < gmaxwell> There are a bunch of little protocols you can get out of using tree-structured-secrets. 16:32 < midnightmagic> gmaxwell: I thought of a reason why proof-of-blockchain storage would still be useful. One could prevent access from all non-archival storage nodes who are connecting just to connect. You can be more sure they are at least helping store the blockchain, even if they may not necessarily do things like relay tx and just act as listening-post black holes. 16:33 < midnightmagic> plus ongoing validation could be if not guaranteed, at least tested for. 16:48 < Luke-Jr> sipa: cannot reproduce after make clean :< 16:52 < sipa> good! 16:54 < Luke-Jr> not really 16:54 < Luke-Jr> means there's some subtle bug in the build system *sigh* 16:54 < Luke-Jr> test_bitcoin seems to still be broken too :< 16:54 < Luke-Jr> (or again?) 16:59 < Luke-Jr> .. or am I running a stale bin :/ 19:55 < HM2> I love this channel 19:55 < HM2> I never feel dumber just idling here and reading the scrollback like some of the others on freenode --- Log closed Fri Oct 25 00:00:42 2013