--- Log opened Sun Sep 22 00:00:05 2013
00:08 < warren> darn, wouldn't have the gitian linux -> mac cross compile goal have been a worthy grant proposal?
00:09 < warren> too late now
01:47 < amiller> i'm going to call my new abstraction of the hashcash puzzle, "Scratch-Off Puzzles"
01:47 < amiller> since proof-of-work isn't quite the right definition after all
01:48 < amiller> also i'm going to write a series of papers called "Money from Scratch," "Decentralized Storage from Scratch," etc.
01:49 < gmaxwell> I might have complained about "Scratch-Off Puzzles", but those justify it—
01:49 < amiller> it's a solid three-way pun
01:49 < gmaxwell> "Scratch-Off Puzzles" sort of suggests that there is a dealer.
01:49 < amiller> especially the bootstrapping problem implied by "Money from Scratch" is the best
01:49 < amiller> yeah.
01:49 < gmaxwell> (I suppose the network actually is a dealer, but it has no secret)
01:49 < amiller> is it the "puzzle" that suggests that?
01:50 < amiller> scratch-off challenge is almost better
01:50 < gmaxwell> The finiteness of the scratch-off contributes too, but it's actually correct... it's actually finite due to the network acting as a dealer.
01:51 < amiller> it might not be a "puzzle" if it's not guaranteed to have a solution
01:52 < amiller> riddle, etc., has the same connotation
01:53 < gmaxwell> it's not hard to describe a construction where a solution is guaranteed, I think. e.g. a keyed permutation, network state is one input, you search for a key. Pigeonhole principle says there is always a solution.
01:55 < amiller> it doesn't seem like that's important in any case, i mean it's low enough probability it would happen with sha2 right
01:56 < gmaxwell> right. (in fact, because how how we're setup where we have >256 bits of input I wouldn't be surprised if it were actually impossible to have no solution, though we can't prove that)
01:57 < amiller> even if it's a random oracle it's possible to have no soultion
01:57 < gmaxwell> just pointing out, you can actually create a sutible structure where you _can_ prove that... if you care.
01:57 < amiller> because bitcoin doesn't use the full infinite domain of the hash function, it has a bounded size header
01:59 < gmaxwell> It could turn out that sha256^2 has no output with >74 leading zero bits, even with infinite length inputs.
02:00 < amiller> yes but if it were a random oracle, that would happen with probability zero
02:01 < amiller> it could happen with nonzero probability to "sponges", since those have bounded internal state
02:01 < amiller> i think sha2 is closer to a sponge
02:03 < gmaxwell> (dunno if you noticed, but we now have a hash with 73 leading zeros)
02:08 < gmaxwell> I'm wondering if it would trick anyone if I wrote a obfscuated paper describing some fictitious attack on SHA256 that produced some of bitcoins very low value outputs. esp since the input will look random.
02:09 < gmaxwell> I wonder if you could use bitcoin's biproduct to break some protocols which are secure under random oracle.
02:09 < gmaxwell> er byproduct.
02:09 < amiller> that's a cool observation.
02:09 < amiller> no one cares about the zeros
02:10 < amiller> but it's definitely non-random, it's a pickable (not just recognizable) pattern, like 123456789
02:11 < gmaxwell> well, it just means you can get lots of sha256 inputs that give you a common prefix. E.g. a DHT that stored things by content hash uniformly distributed to nodes with <2^32 nodes would be totally devastated by a feed of bitcoin shares.
02:11 < amiller> yeah, perfect
02:12 < gmaxwell> amiller: because bitcoin is sha256^2 the inputs to sha256 that produce the low values are quite non-obvious.
02:13 < gmaxwell> (I previously verified that our shares wouldn't break freenet, they add extra data to the hash)
02:13 < gmaxwell> Otherwise we would— and a trivally modified bitcoin fpga farm could break freenet pretty good. :(
02:14 < amiller> did you write anything about that
02:14 < amiller> er, mention it anywhere
02:15 < gmaxwell> (nodes will move their locations to split up the hash space better— but it's insanely unlikely that two locations will ever become close enough to split hashes sharing a 32 bit common prefix)
02:15 < gmaxwell> I went and asked the freenet developers what was in their hash, but thats it.
02:16 < gmaxwell> (freenet locations are randomly generated, and then the network swaps them to optimize… so if the keys are non-uniform… saddness abounds)
02:16 < gmaxwell> I expect lots of DHTs are vulnerable to something like this, but since they're generally made of fail I don't know that it matters.
02:17 < gmaxwell> I'm sure the serious cryptographers would go "see, random oracle assumptions suck"; But this attack works with a real random oracle too.
02:18 < amiller> it's really fun trying to define the reward-claiming part of the puzzle
02:18 < amiller> because the proof-of-work puzzles and client-puzzles don't
02:18 < amiller> the fun part is that since i want to include the stealable puzzle stuff, i'm being careful not to say you have to choose the message before starting
02:18 < amiller> so it's something like non-malleability
02:19 < amiller> given just the scratch-off-proofs generated by arbitrarily many other parties, who dedicate it to messages m1, m2, m3, .... , however many, that doesn't give you any help in producing a scratch-off-proof dedicated to some other message m
05:36 < warren> jgarzik: https://github.com/bitcoin/bitcoin/issues/2770#issuecomment-24756647
05:37 < warren> jgarzik: you said you had people that could reproduce the macos corruption?  severely delayed but here's a build to test.  GPG signed.
05:38 < warren> jgarzik: we have a dedicated machine to doing our builds, setup we *think* in exactly the same way gavinandresen does it, we aren't certain.
16:14 < warren> jgarzik: saw the above?
16:15 < jgarzik> warren, da
--- Log closed Sun Sep 22 22:19:31 2013