--- 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