--- Log opened Sat Oct 19 00:00:22 2013
00:11 < petertodd> jgarzik: http://www.rubygems-openpgp-ca.org/ <- interesting signing authority for ruby gems, the model could have some relevance when thinking about SINs
00:32 < gmaxwell> those people who's pow I was tearing apart a awhile back? they've posted a new one now offering a bounty to "convince [them] it's not better than scrypt"
00:32 < gmaxwell> I quote a line from their implementation:
00:32 < gmaxwell>                             fc::usleep( fc::microseconds(1000*1000*(1-_effort)) );
01:02 < phantomcircuit> gmaxwell, lolololol
01:02 < phantomcircuit> gmaxwell, what's the bounty?
01:02 < gmaxwell> 30 BTC. Have at it.
01:03 < phantomcircuit> gmaxwell, goat them into making it more
01:03 < phantomcircuit> then claim it
01:03 < gmaxwell> Well, I know from my past expirence with them that they're claim any flaw is a placeholder, so collecting will likely be hard unless you really smoke them bad.
01:03 < phantomcircuit> gmaxwell, it's the mastercoin people right?
01:03 < gmaxwell> (and indeed, I'm sure the sleep for low difficulty really is just a placeholder honestly.. still crazy to see it there)
01:06 < gmaxwell> phantomcircuit: these people: https://bitcointalk.org/index.php?topic=313479.0
01:14 < phantomcircuit> oh
01:14 < phantomcircuit> shrug
04:43 < petertodd> gmaxwell: oh, that was fun to tear apart - I nearly wound up replying with a bunch of VHDL code
04:44 < gmaxwell> petertodd: hahah
04:44 < gmaxwell> I had fun de-memoryhardening their last one.
04:44 < gmaxwell> but it was even more of a toy.
04:45 < petertodd> gmaxwell: I actually sketched out a VHDL implementation of an ASIC, although I held off posting because I was sure there was enough detail there to make a fool of myself :P
04:45 < petertodd> what was there last one?
04:46 < warren> will they actually pay?
04:47 < gmaxwell> https://bitcointalk.org/index.php?topic=279771.msg2996823#msg2996823
04:49 < petertodd> sheesh
04:49 < gmaxwell> they they responded with a bunch of "oh it's not really done" and then rapidly put up a new one.
04:49 < gmaxwell> and apparently they have a new one still. :P
04:49 < petertodd> Though this is an interesting question: maybe it's not possible to make a proof-of-work algorithm where verification is symmetric, and yet doing the work must be sequential - there's a similar result from timelock puzzles IIRC.
04:51 < gmaxwell> verification is symmetric?
04:51 < petertodd> er, asymemetric
04:53 < gmaxwell> well does fiat-shamirizing my idiot solution to proof of storage yield what you want?   POS the data you are working on, sort the leafs, build a new hashtree and construct a verification proof that convinces someone that it queries an sorted version of the list.
04:53 < gmaxwell> The proof would be somewhat bit, alas.
04:54 < sipa> wait, a PoW functiin that sleeps...?
04:54 < gmaxwell> I'm pretty sure I know how to boost such a proof to arbritary soundness using an error correcting code... but the POW might end up being rather large (tens of kb) for 128 bit security.
04:54 < petertodd> gmaxwell: Yeah, I came up with that idea myself, and as far as I could tell you get into a situation where "fraud" in the NI proof is what allows you to parallelize the problem.
04:55 < petertodd> gmaxwell: I don't know anything about error correction though.
04:55 < petertodd> sipa: Yes! Like my example of a consensus currency system where you just write transactions down on post-it-notes and hope everyone is honest...
04:55 < gmaxwell> petertodd: yes, thats always the problem you get unless you have a local test of the proof with probably of detecting fraud of at least p=0.5, once you have that you can boost up to make fraud simply infeasable.
04:56 < petertodd> gmaxwell: So how do these error correcting codes work?
05:00 < gmaxwell> petertodd: by expanding the state with additional binary relations e.g. parity checks which also must be true if the data is valid (it's easy to see how you can do that for a simple greater than or equality relationship). If you expand enough with the right structure the probablity of a random test (e.g. reading out one spot and the other values in the proof it is the parity of) failing can be made 0.5. Once you achieve that, ...
05:00 < gmaxwell> ... fiat-shamirizing a couple dozen of these tests makes fraud infeasable.
05:00 < gmaxwell> easier to explain with a whiteboard.
05:01 < gmaxwell> sipa: the sleep makes me think of http://weknowmemes.com/wp-content/uploads/2011/10/i-am-not-a-clever-man-comic.jpg  somehow.   "YOU MADE A POW FUNCTION THAT CALLS USLEEP?" "I AM NOT A SKILLED CRYPTOGRAPHER"
05:02 < petertodd> gmaxwell: Hmm... we're getting dangerously close to leaving joe-random in the dust; I'm going to have to do some reading.
05:03 < petertodd> gmaxwell: I take it no-one has even attempted to do a dumbed down explanation of that stuff yet right?
05:04 < gmaxwell> petertodd: I can explain it to you, but there is no dumbed down explaintion of it. Worst, most things talking about are talking about building proofs for arbritary poly-time (or NP) languages.
05:04 < gmaxwell> one for this set of values is a sorted list would be much simpler, like I could reason that one out on a whiteboard without much trouble.
05:05 < petertodd> Yeah, I don't really know what an "arbitrary poly-time language" is :/
05:05 < petertodd> Sorted list sounds more promising. :)
05:11 < gmaxwell> lemme try the short explination over IRC,   here is an example image representing an error correcting code http://www.spiral.net/hardware/graphics/tanner.gif  message bits on the bottom, you feed them in and the wires just do xor, giving you those parity bits.
05:12 < gmaxwell> When you use them for communications you do things like take an errored message + parity bits, and construct the most likely message using some efficient decoding algorithim. But thats not relevant for using them in proofs.
05:13 < gmaxwell> if I gave you a message + parity, you could go and check all the edges and tell me easily if it was a non-errored  message (and paritity),  "A valid codeword for the system"
05:14 < gmaxwell> Thats straight forward.  Turns out that if you construct a parity check matrix with the right graph structure (and a long enough ratio of parity bits to message bits),  that if the codeword is invalid if you just just one or two bits (and their edges)  that you'll have a 50% chance of detecting the error.
05:15 < petertodd> huh
05:15 < petertodd> and 50% iterated soon gets to nearly 100%
05:15 < gmaxwell> Right.
05:15 < petertodd> what kind of ratios are we talking about?
05:17 < petertodd> by "their edges" you mean the bits going into the XOR operation right?
05:17 < gmaxwell> yes.
05:17 < petertodd> which looks rather like a merkle tree...
05:17 < gmaxwell> Right, so there are graph transformations that take any existing error correcting code and expand it into the kind with the probablistically checkable structure. Generically they have quadratic growth, I believe, so they get big but they're regular.
05:17 < petertodd> "regular"?
05:18 < gmaxwell> repeated, e.g. you don't need to go and seralize out the whole thing. it's not a random graph.
05:19 < gmaxwell> so what you do is you write out a little set of booleian circuts to test your constrant and then outputs its truths, e.g. little binary comparitors.. And take this is a kind of degerate error correcting code. E.g. you've got inputs and then a bunch of 'true' outputs. And the constraints are all satisfied if and only if your data is good.
05:19 < gmaxwell> Then you take that graph and pass it through the transformation to one of these probablistically checkable graphs.
05:19 < gmaxwell> and then construct a merkle tree over it... and use the root of the tree to select your tests.
05:20 < gmaxwell> (because a parity check graph is just a satistifaction problem you can convert any program execution into one of these, but it gets inefficient fast)
05:21 < petertodd> so dumb question time: how do you know the circuits actually tested the constraint you thought they did? (given the partial information youre given)
05:22 < gmaxwell> validator knows the graph, it's fixed for the statement being proven. .. and all the state is under the proof.
05:22 < petertodd> right, because it's structure is regular?
05:22 < petertodd> (like a merkle tree would be)
05:23 < gmaxwell> so it gets point 2394892384 and it knows that it should be equal to 12319831 xor 32849284 xor 589583 xor 5837485743   (or whatever), and it gets those too.
05:23 < gmaxwell> right. or at least if you want this to be feasable it better damn be regular. :)  The expansion itself is regular, but the whole thing is only regular if the thing you're checking is really trivial.
05:27 < gmaxwell> petertodd: it may help your understanding a bit to know that these are also called holographic proofs. :)
05:27 < petertodd> Hmm... lets try a toy problem, heck, a toy toy problem: So I have a list of bits, and I want to know if they are all zero. I construct my merkle tree over all the bits, and pick random samples. By that p=0.5 thing you said before, I can very quickly determine that at least half the bits are false with overwhelming probability, correct?
05:28 < petertodd> Now, the error corecting code business is basically taking that toy problem, and using binary relations in ways that "spread" out my tests to actualy have better coverage than one-test-one-bit.
05:28 < petertodd> Like a hologram where you're checking if the low-resolution fragment looks roughly right...
05:29 < gmaxwell> petertodd: yea, and actually a trivial code should work for that, i think. Repetition. like you virtually repeat your data enough times that you have a 50% chance of hitting any message bit with a single test.
05:30 < petertodd> Huh, so how do you "virtually repeat" the data?
05:31 < gmaxwell> hm. no straight reptition doesn't work (now that I write it out. :P oh  duh right)
05:32 < gmaxwell> okay so initially you have p=1/s  in finding your bad bit in a single test.
05:32 < gmaxwell> (s is size)
05:33 < petertodd> right
05:38 < gmaxwell> petertodd: so my brain isn't working since I don't remember the transform trick to get high success rates without looking it up :P   I can show you how to increase it.
05:39 < petertodd> ha, better than nothing!
05:39 < gmaxwell> petertodd: e.g. take your s bits in your message and create s^2  pairs (all the pairs).  Probablity of detecting a bad bit in the new data is 2/s  instead of 1/s. :)
05:40 < petertodd> create a s-bit tuple and we can make the probability 1!
05:41 < petertodd> though I'll admit that s^2 pairs has less bandwidth to prove :P
05:41 < petertodd> there is something neat about that...
05:41 < gmaxwell> e.g. for s=4   you start off with 1/4 probablity.   but in the s^2 form you have p=7/16.
05:42 < petertodd> hmm, very close to the p=0.5 threshold
05:45 < petertodd> now, I guess if we can fairly choose our PRNG seed still, we don't need to calculate all s^2 pairs right? like, if we did the merkle tree of, say, just s and then used it to pick pairs
05:52 < gmaxwell> ah dur, for that trivial example:
05:52 < gmaxwell> s=4  {0 1 2 3}
05:52 < gmaxwell> 01 01 02 03
05:52 < gmaxwell> 10 12 12 13
05:52 < gmaxwell> 20 21 23 23
05:52 < gmaxwell> 30 31 32 30
05:52 < gmaxwell> P=0.5
05:53 < petertodd> ?
05:53 < gmaxwell> those are the pairs if you count up the number of each number in the grid, you'll see there are 8 of each, and 16 total pairs.
05:54 < gmaxwell> had to replace the moronic XX diagonal with repeats of the neghbor code.
05:57 < petertodd> So seems to me we could do merkle(s), use that as the PRNG seed, then sample random pairs of from s by just picking pairs of (PRNG(i), PRNG(i+1)
06:00 < gmaxwell> totally OT but I have a puzzle that will blow your mind.
06:00 < petertodd> oh yeah?
06:01 < gmaxwell> Say there is a contest. You sipa and I  are each going go be given a hat.  The hat will be red or blue, assigned totally at random (by coinflip).  We can't see our own hats.
06:02 < gmaxwell> We get sent into a room where we can see each others hats but we are permitted no communication _at all_. Then we leave the room seperately.
06:02 < gmaxwell> Each of us then must write down.  Either Pass  or  the color of our own hat Red or Blue.
06:03 < gmaxwell> If at least one of us is correct and none are incorrect (e.g. correct pass pass is fine). Then we all win a million dollars.
06:03 < gmaxwell> What is the ideal strategy for us to use, and what our are chances of winning this game.
06:03 < HM2> 2 write down red, 1 writes down blue
06:04 < sipa> can we assume that we all have the same purpose?
06:04 < sipa> (winning)
06:04 < gmaxwell> we all want to win. and We ALL win. if  at least one of us is correct and none are incorrect.
06:04 < HM2> oh wait you mean pass pass red/blue = win
06:04 < sipa> and there is no difference in result between one being incorrect or all passing?
06:05 < gmaxwell> yea, pass pass pass is lose.
06:05 < gmaxwell> and wrong wrong wrong is lose.
06:05 < sipa> if 3 pass, 0% of winning
06:05 < sipa> if 2 pass, 50% of winning
06:05 < HM2> is it something to do with the order you leave the room?
06:05 < gmaxwell> as is wrong right right and so on.
06:05 < sipa> if 1 passes, 25% of winning
06:06 < gmaxwell> HM2: no, no side channels.
06:06 < sipa> do we know whether we lost, if someone gave the wrong answer?
06:06 < sipa> or does that also count as a side channel
06:06 < sipa> not that it matters, as we're lost in any case
06:06 < petertodd> that we all get to see the same thing minus our own hate is a information channel - is this an ideal situation, or can we use rules like "if the person on the left has a blue hat"?
06:06 < gmaxwell> yea thats communicaton.  You're all effectively answering concurrently.
06:07 < petertodd> s/hate/hat/
06:07 < gmaxwell> petertodd: you can see the other hats, you can have person specific rules if you want (so person ordering is fine)
06:07 < HM2> petertodd, that's what i was thinking. e.g. the person who left before me had a blue hat
06:09 < sipa> gmaxwell: do we have access to a RNG?
06:09 < sipa> (each individually)
06:09 < gmaxwell> sipa: sure, you can flip coins.
06:09 < sipa> oh, right, we can see the other's colors
06:09 < sipa> hmmm
06:09 < gmaxwell> but right.
06:10 < sipa> if i couldn't see the other's hats, i'd say each uses a RNG to determine whether he's going to answer or not
06:10 < HM2> well if 2 pass and 1 doesn't you have 50/50
06:11 < HM2> you have to be able to do better than that
06:11 < sipa> if my math is right, with answering with chance 0.45308, we have a 30% chance of winning
06:12 < petertodd> nothing says we can't agree before hand that two of us are going to pass no matter what, and the last man out always picks blue for 50%
06:12 < sipa> oh, we can communicate in advance?
06:12 < gmaxwell> yea, you can agree on the rules in advance. Sorry.
06:12 < HM2> it'd be a bit difficult to have a strategy if you couldn't communicate outside the room
06:12 < gmaxwell> but you know nothing of which hats you have then.
06:13 < sipa> is there a known probability distribution on the hat colors?
06:13 < petertodd> well, 50:50 is already sounding pretty good :)
06:13 < gmaxwell> coin flip, assume the coin is fair.
06:13 < sipa> ok
06:13 < petertodd> so we can't tell if our other teammates passed or picked right?
06:13 < HM2> If you saw 2 blue hats, write red. If you saw 2 red hats, write blue. If you saw differing colours, pass
06:14 < sipa> HM2: why?
06:14 < gmaxwell> petertodd: that would be communicating. No communicating.
06:14 < sipa> the hat colors are presumably independent
06:14 < gmaxwell> <3
06:14 < gmaxwell> "If you see two of the same color, call the opposite, otherwise pass"
06:14 < gmaxwell> 0 0 0 = 1 1 1  Lose
06:14 < gmaxwell> 0 0 1 = P P 1  Win
06:14 < gmaxwell> 0 1 0 = P 1 P  Win
06:14 < gmaxwell> 0 1 1 = 0 P P  Win
06:14 < gmaxwell> 1 0 0 = 1 P P  Win
06:14 < gmaxwell> 1 0 1 = P 0 P  Win
06:14 < gmaxwell> 1 1 0 = P P 0  Win
06:14 < HM2> sipa, because seeing 2 blue hats means if you have red the other 2 will pass
06:14 < gmaxwell> 1 1 1 = 0 0 0  Lose
06:14 < gmaxwell> P_win = 6/8 = 0.75
06:14 < HM2> likewise with 2 red hats
06:14 < sipa> right!
06:15 < gmaxwell> The awesome thing about this is that morons who fail at stats will actually get it right faster than non-morons.
06:15 < gmaxwell> Because if you think the hats are not independant you'll chance into that solution.
06:15 < HM2> So where's my million dollars?
06:16 < petertodd> ha, so I was at least right in thinking that the shared partial view was a communications channel
06:16 < gmaxwell> Now further mindblowing: This works with any number of people, but coming up with the assignment codes is hard. It becomes _more_ successful the more people you have.
06:17 < sipa> right, it's probably harder than generalizing to "vote the opposite of the majority you see"
06:17 < petertodd> right, so now I just need to construct a merkle tree of it, and start picking samples for my non-interative proof :P
06:17 < gmaxwell> This is the covering code problem: https://en.wikipedia.org/wiki/Covering_code
06:17 < HM2> it makes sense from a raw information perspective as well. each player effectively can convey 1 bit of information about what they saw. a guess (worthless) or no guess
06:18 < HM2> so you have 3 bits of information and 2^3 hat combinations
06:19 < HM2> so it at least seems feasible to me that there is a very good strategy
06:19 < sipa> if we're into riddles, here's another (which sounds similar): in a monastery, monks live solitary lives; they only meet once per day for dinner, and only the abbot is allowed to speak. one day he speaks: "brothers, a terrible disease has broken out. the disease is characterized by a black dot on the forehead; anyone who knows he has the disease has to commit suicide at night". A week later, the disease is eradicated, and you can assume no...
06:20 < sipa> additional infections happened during the week
06:20 < sipa> how many were sick?
06:20 < gmaxwell> I'm glad it seemed feasable to you! But I took a while to even realize there was a dumb 50% strategy. :P
06:21 < HM2> the abbot poisoned their dinner
06:21 < sipa> HM2: perhaps, but irrelevant :)
06:21 < HM2> i'm confused as to what the problem is
06:21 < HM2> do they not have mirrors?
06:22 < sipa> nope
06:22 < sipa> no communication at all
06:23 < HM2> so no monks know if they're infected
06:23 < sipa> indeed
06:23 < HM2> and they can't tell their neighbours if they're infected
06:23 < HM2> and a week later the disease is gone
06:23 < sipa> indeed
06:23 < petertodd> was at least one monk infected?
06:23 < HM2> sounds like you have an empty monastary after one week
06:23 < gmaxwell> Do they all have the disease? No one said the disase kills you, only knowing about it.
06:24 < sipa> i'll strengthen: one week later, the disease is eradicated, and not earlier
06:24 < gmaxwell> ahh
06:24 < sipa> and nobody dies of the disease itself
06:24 < petertodd> can you die of the disease?
06:24 < sipa> not within one week :)
06:24 < petertodd> how does the disease spread?
06:24 < HM2> how can anyone commit suicide if they don't know they have it?
06:24 < gmaxwell> What I think happens is that the abbot is being replaced.
06:25 < sipa> petertodd: it doesn't spread within that week
06:25 < gmaxwell> hm.
06:25 < sipa> how we got the current situation is irrelevant
06:25 < petertodd> how can the monks learn they have it exactly?
06:25 < HM2> you cant' even collaborate if you can't communicate
06:25 < sipa> petertodd: for you to find out
06:26 < sipa> oh
06:26 < HM2> there can't be a protocol for solving it at dinner if they can't establish a protocol through communication
06:26 < sipa> no, nevermind
06:26 < sipa> HM2: no need :)
06:26 < sipa> (we have to assume all the monks are highly intelligent and obeying)
06:27 < petertodd> sipa: so basically this monestary is full of the borg?
06:27 < sipa> Potentially.
06:27 < gmaxwell> sipa: does the abbot say anything else or is this just a one time announcement?
06:27 < sipa> that's the only time he speaks within that week
06:27 < HM2> ah
06:28 < HM2> if you kill yourself, you don't show up for dinner the next day
06:28 < sipa> bingo
06:28 < HM2> so there's something there
06:29 < HM2> I'm not sure how that helps you determine if you have it though
06:29 < HM2> I guess dont' show up, then show up the next day and see if anyone is surprised
06:30 < sipa> everyone alive is required to be at dinner
06:30 < gmaxwell> We're all apparently dumb, because Kat solved it like instantly.
06:31 < sipa> i can't remember whether i actually ever found it myself
06:31 < sipa> probably with a lot of hints
06:31 < HM2> the protocol can't be that complex
06:31 < petertodd> can the monks know if the disease has been stopped?
06:31 < HM2> otherwise it couldn't be established without collaboration
06:31 < sipa> petertodd: no need
06:32 < sipa> assume there is only one sick person
06:32 < sipa> what happens
06:32 < HM2> nothing if he doesn't know he has it :|
06:32 < sipa> what does he see?
06:32 < petertodd> right, but the sick person has no way of knowing they are sick... and i take it monks won't kill themselves unless they know for sure
06:32 < HM2> oh, healthy monks
06:32 < sipa> bingo
06:33 < HM2> but how does that work in the general case
06:33 < sipa> first reason on
06:33 < sipa> one sick person; what happens?
06:33 < HM2> he goes home and kills himself because he knows he is the sick one
06:33 < sipa> and what does the rest see the next day?
06:33 < petertodd> sipa: so we damn well better catch it in the first case
06:34 < petertodd> sipa: healthy monks
06:34 < sipa> there you go
06:34 < sipa> now assume there were two sick
06:34 < sipa> what happens?
06:34 < petertodd> sipa: no-one kilsl themselves
06:34 < HM2> no
06:35 < HM2> they both kill themselves the following night
06:35 < sipa> why?
06:35 < HM2> because the next day they see the other is still alive
06:35 < petertodd> how do they know how many are sick?
06:35 < HM2> and realise they are the other unhealthy monk
06:35 < sipa> indeed
06:35 < HM2> and if there are 3 unhealthy monks it still works
06:35 < sipa> they expect that if they 1 see sick monk, that he will be dead the next day
06:35 < HM2> but 7 days only works for an upper bound on the number of monks, i think?
06:36 < sipa> obviously there are >=7 monks (abbot included)
06:36 < gmaxwell> 03:24 < sipa> i'll strengthen: one week later, the disease is eradicated, and not earlier
06:36 < petertodd> so exactly 7 monks were sick?
06:36 < sipa> indeed
06:36 < HM2> damn
06:36 < HM2> i  had forgotten the number of sick monks was the actual question
06:36 < sipa> if you see N sick monks, you will expect that they kill themself after N days
06:37 < sipa> if they don't, you have to assume you are the N+1'th
06:37 < sipa> so technically there is a communication channel: observing whether your peers stay alive
06:38 < gmaxwell> so this is a riddle from http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml  but its not actually hard:
06:38 < gmaxwell> An evil king has 1000 bottles of wine. A neighboring queen plots to kill the bad king, and sends a servant to poison the wine. The king's guards catch the servant after he has only poisoned one bottle. The guards don't know which bottle was poisoned, but they do know that the poison is so potent that even if it was diluted 1,000,000 times, it would still be fatal. Furthermore, the effects of the poison take one month to surface. The ...
06:38 < gmaxwell> ... king decides he will get some of his prisoners in his vast dungeons to drink the wine. Rather than using 1000 prisoners each assigned to a particular bottle, this king knows that he needs to murder no more than 10 prisoners to figure out what bottle is poisoned, and will still be able to drink the rest of the wine in 5 weeks time. How does he pull this off?
06:38 < gmaxwell> ---
06:38 < gmaxwell> You'll all solve that right away.
06:38 < petertodd> sipa: note though how the monks need to be able to put themselves into a sequence for that strategy to work
06:38 < gmaxwell> petertodd: nah, they don't.
06:39 < gmaxwell> petertodd: its a quroum sensing thing. They all commit suicide at once.
06:39 < sipa> indeed, they don't
06:39 < sipa> from each point of view, he himself is the N+1'th
06:39 < petertodd> gmaxwell: if there are 8 monks, 4 of which are sick, the remaining 4 have no way of not all killing themselves, so it's never optimal
06:39 < sipa> but others will see that differently
06:39 < sipa> petertodd: eh sure, after 4 days they see the sick ones dead and everyone is happy
06:40 < HM2> gmaxwell, divide in to 10 x 100 bottle sets, blend each set
06:40 < HM2> you waste 10% of the wine
06:40 < HM2> but after 5 weeks you can drink the other 90%
06:40 < sipa> but he doesn't want to waste any wine except the poisoned one, i assume?
06:40 < gmaxwell> HM2: "that even if it was diluted 1,000,000 times, it would still be fatal"
06:41 < HM2> gmaxwell, and?
06:41 < petertodd> sipa: ok, so on day 4, when monks decide to kill themselves, how do the healthy monks know if they should kill themselves or not? all they know is that someone should
06:41 < gmaxwell> sipa: and yea, assume he doesn't waste.
06:41 < HM2> gmaxwell, the poison is only in one 100 bottle set
06:41 < sipa> petertodd: i don't understand; as soon as you see all originally sick people having killed themself, you know you can't be sick yourself
06:42 < HM2> gmaxwell, does the king need all the wine after 5 weeks? or is he happy with a steady supply?
06:42 < gmaxwell> HM2: I see what you're saying, but no, he's EVIL he wants all his wine (Except the poisoned bottle)
06:42 < sipa> good question
06:42 < sipa> without the 1-month delay it was easy :)
06:42 < sipa> oh
06:42 < sipa> got it
06:43 < petertodd> sipa: ok, so if exactly one person is sick it works nicely: I know someone is sick, everyone else I look at isn't sick, therefore it must be me. If there are two people sick though every monk sees one or two monks... and I got it finally. :P
06:43 < HM2> well if a prisoner dies on day N, you know the poison bottle was from day N-30
06:43 < HM2> (assuming 30 days is the kill time)
06:45 < HM2> you essentially have 30 x 10 = 300 bottles on hold, but after 30 days you've only covered 30% of the bottles
06:45 < HM2> so you have to mix the wine somehow during the process
06:45 < sipa> you can know which bottle is poisoned after exactly 30 days :)
06:47 < sipa> petertodd: :)
06:47 < HM2> i don't see how you can preserve 999 bottles if you have to mix the wine
06:47 < sipa> oh
06:47 < sipa> didn't take that into account
06:47 < HM2> on the other hand, i can't see a way to do it without mixing the wine
06:47 < sipa> you need to be able to take a sample from every bottle in any case
06:47 < gmaxwell> HM2: they can drink some from each bottle, they only need a drop.
06:48 < gmaxwell> We'll just imagine this doesn't spoil the wine.
06:49 < HM2> could you still do it (in a  longer period of time) with 1 prisoner?
06:49 < sipa> no
06:49 < gmaxwell> sipa: so the really hard version of this that Kat and I independantly came up with and solved:  What if, instead, you know exactly two bottles are poisoned. How many prisoners do you need?    But we don't have a proof our solution is optimal.
06:49 < gmaxwell> HM2: well in a really long time, sure, sip from one bottle per month.
06:50 < gmaxwell> (and hope he doesn't die of natural causes first)
06:50 < sipa> gmaxwell: impossible with less than 19 prisoners
06:50 < sipa> though i don't have a contructive proof :)
06:50 < sipa> i think i can prove it's impossible with 18
06:51 < HM2> Ok, i have an idea
06:51 < gmaxwell> I can prove its impossible with less than 20.
06:51 < HM2> take 4 bottles per day
06:51 < HM2> give prison A samples from bottles 12, B gets 13, C gets 24, D gets 34
06:51 < gmaxwell> sipa: since prisoners are integers. you can't have .9 a prisoner.
06:51 < HM2> when the poison gets them, 2 prisoners will die
06:51 < sipa> gmaxwell: there are 1000*999/2 potentials outputs
06:51 < sipa> each equally likely
06:52 < HM2> but you're still only doing 4 bottles per day
06:52 < gmaxwell> sipa: where are you getting the /2 from?
06:52 < sipa> gmaxwell: the order of the poisoned bottles doesn't matter
06:52 < gmaxwell> sipa: oh indeed. 19 then.
06:52 < gmaxwell> (but yea, our solution is not at that bound)
06:52 < gmaxwell> (alas)
06:53 < sipa> #bitcoin-riddles
06:56 < HM2> you can do 6 bottles per day with a mixing strategy
06:56 < HM2> when 2 die you can determine which bottle on that day was poisoned
06:56 < sipa> 6 bottles per day?
06:56 < HM2> because there are 6 combinations of 2 in 4
06:56 < HM2> yeah
06:57 < sipa> where do you get that number?
06:57 < HM2> Prisoners A,B,C,D. Bottles 1-6. A = 125, B = 136, C = 246, D = 345
06:57 < HM2> 1 bottle is poisoned, 2 prisoners die
06:57 < HM2> always determinable
06:58 < petertodd> Lol! Someone claiming to be a Mastercoin investor just offered me a Bitcoin in exchange for giving them some pointers on their transaction encoding troubles - they still don't seem to have figured out that Bitcoin doesn't check if multisig pubkeys are actually real ECC pubkeys. :/
06:58 < HM2> but that still only gets you 30 x 6 = 180 bottles tested after a month
06:59 < HM2> you can't do better on combinations in 4 either
06:59 < HM2> 6 is centre of pascals triangle
07:00 < HM2> so I must be barking up the wrong tree
07:02 < HM2> wait a minute
07:02 < HM2> there are 10 prisoners not 4
07:02  * HM2 facepalms
07:07 < HM2> so you can test 252 bottles a day? :|
07:08 < HM2> because there are 252 combinations of 5 in 10
07:08 < HM2> so after 30 days, 5 prisoners will die
07:09 < HM2> you can determine which of the 252 bottles you mixed was poisoned on the day in question
07:09 < HM2> so total time is 34 days
07:09 < HM2> given a precise 30 day lag time on the poison
07:10 < gmaxwell> you can solve this even if the timing is unreliable.
07:11 < HM2> :P
07:11 < HM2> is it?
07:12 < gmaxwell> Lets just say that it is somewhat unreliable, but enough to meet your deadline.
07:14 < HM2> well since my solution only takes 4 days, you can just space the test days out. Test, no test, test, no test, test, no test, test
07:14 < gmaxwell> the party is in 5 weeks however.
07:14 < HM2> that gives you +/- 24 hour margin and takes 7 days on top of your existing 1 month/4 week deadline
07:14 < sipa> not sure how timing is of any relevance
07:14 < sipa> but i haven't actually followed
07:14 < HM2> for 5 weeks total
07:14 < gmaxwell> sipa: it's not, HM2 is deftly evading the intended solution.
07:15 < HM2> it's a solution nonetheless?
07:15 < HM2> how many prisoners die in your solution?
07:15 < sipa> on average 5
07:16 < sipa> binomially distributed
07:16 < HM2> mine always kills 5
07:16 < sipa> you're so deterministically evil
07:17 < HM2> and wastes err
07:17 < gmaxwell> HM2: and you identify the unique bottle?
07:17 < HM2> sure
07:18 < sipa> oh, you're giving different mixer to the same prisoner before they die?
07:18 < sipa> *mixes
07:18 < HM2> yeah
07:18 < HM2> overlapping mixtures
07:18 < gmaxwell> and timing the death.
07:18 < sipa> got it; yeah that way you can use the timing
07:18 < sipa> but it's unnecessary :)
07:19 < HM2> I give up :)
07:19 < gmaxwell> HM2: yea, so imagine instead all poisoned die on the first of the month regardless of when they drank.
07:20 < sipa> or all prisoners will be beheaded in one month + one hour anyway
07:20 < gmaxwell> yea, he's evil afterall and they drank his wine!
07:20 < HM2> gmaxwell,  i don't follow
07:20 < sipa> HM2: assume you cannot observe when a prisoner dies
07:21 < sipa> you only get to check back right before the party in 30 days
07:24  * sipa food
07:28 < HM2> what
07:28 < HM2> so the solution has to be diluting the wine
07:28 < HM2> hmm
07:28 < HM2> if you can dilute the poison below the deadly threshold
07:28 < HM2> then it may be possible to have a different mixing strategy
07:29 < HM2> such that the mixtures becomespoisonous again when combined
07:29 < HM2> (since realistically it should be an absolute of poison that's deadly, not a ratio of wine:poison)
07:30 < gmaxwell> how about another approach. You'd get the most information from a prisoner if he was 50% likely to live/die, right?  (this was the kind of thing you pointed out for the hats problem)
07:31 < HM2> sure
07:31 < gmaxwell> do you have a scheme that results in each prisoner being 50% likely to live?
07:31 < HM2> ensure they sample half the wine
07:31 < HM2> 500 bottles
07:33 < gmaxwell> right, now if each samples the same half, thats not so useful.
07:33 < HM2> 2^10 = 1024
07:33 < HM2> so you divide the wine in to 1024 samples?
07:33 < HM2> :\
07:34 < HM2> hmm
07:35 < HM2> so you give each prisoner a distinct 5-mixture from 100 bottle sets
07:35 < HM2> so they sample 500 bottles total
07:36 < HM2> that gives them a 50% chance of dying
07:36 < HM2> nope, that doesn't work
07:37 < HM2> how does a probabilistic solution help anyway?
07:37 < HM2> "My lord! there is only a 0.1% chance you will die if you drink this lovely 1758. It was a good year!"
07:38 < gmaxwell> ah, I wasn't suggesting that it was a probablistic solution, only that a maximum information one would give the prisoners 50% odds of dying (apriori)
07:38 < gmaxwell> because anything other than 50% wouldn't make good use of them.
07:38 < sipa> each prisoner is essentially one bit of information
07:38 < sipa> you want to maximize the entropy in each
07:43 < HM2> you only need to determine which of 1000 bottles is poisoned. so that's < 10 bits
07:43 < HM2> so i agree it should be feasible, but i've clouded my thinking now with mixing overlapping sets of wine
07:45 < HM2> you can easily divide the wine in to 10 x 100 bottle sets and mix 5 different sets together for each prisoner
07:46 < HM2> 5 will still be dead after 30 days, as in my solution, but i don't think you will be 100% certain of the result?
07:48 < HM2> but i totally give up for now
07:49 < gmaxwell> HM2: yea, if it doesn't just come to you later we'll tell you. :) (you've put some much time into it, it would be a let down to not let you solve it though)
07:49 < gmaxwell> you've probably worked yourself into a rut, it'll probably be obvious as soon as you stop thinking about it.
07:49 < HM2> i maintain i solved it and poison works like countdown ;P
07:51 < HM2> wait a minute
07:52 < HM2> isn't this just a parity problem
07:53 < HM2> hmm
07:54 < HM2> 0 to 1024 in binary
07:54 < HM2> 10 prisoners
07:54 < HM2> each get a coefficient of the radix
07:54 < HM2> so 1 prisoner drinks all the odd bottles
07:55 < HM2> another 1 in 4
07:55 < HM2> another 1 in 8
07:55 < HM2> etc
07:55 < HM2> if they die then you know a bit of the poison bottle number
07:57 < HM2> sipa, and it's less than 5 on average :P
07:57 < HM2> because there are less than 1024 bottles
08:05 < gmaxwell> HM2: tada.
08:09  * HM2 grumbles
08:20 < HM2> what sucks about that is my solution isn't even better for < 10 prisoners
08:34 < HM2> the monk riddle was harder
08:45 < gmaxwell> yea, well I mostly mentioned the evil kings riddle in order to present the version of it where exactly two bottles are poisoned.
08:45 < gmaxwell> which is harder than the monks riddle.
09:43 < HM2> gmaxwell, interesting
17:04 < Luke-Jr> gmaxwell: that guy is obviously trolling, but I don't think he's completely wrong about pull request purgatory. I've seen useless/silly things get merged while truly useful pulls sit ignored.
17:05 < gmaxwell> well I don't think he's being intentionally trolling. if he got confused about how things works thats a problem in and of itself.
17:06 < gmaxwell> Considering that he claimed bitcoin was written in typescript, I suspect he's not trying very hard... none the less, unfortunate that he didn't feel welcome. (and weird that he though a ~dead project welcomed him...)
17:06 < Luke-Jr> gmaxwell: comparing it with namecoin? I don't see any "defecting from bitcoin" in #namecoin
17:06 < gmaxwell> and yea, the pull process is bumpy. usless things are easier to merge: they're usually more obviously harmless. :)
18:51 < midnightmagic> petertodd: thanks for dust-b-gone btw
18:51 < midnightmagic> very much more convenient than waiting until my miners mine a block..
18:57 < petertodd> midnightmagic: cool!
18:57 < petertodd> Luke-Jr: I was having some trouble getting coin-join txs mined on eligius - what are the current rules for a tx that has a single OP_RETURN, 0-value, output?
18:59 < petertodd> Luke-Jr: s/coin-join/dust-be-gone/
19:02 < Luke-Jr> petertodd: data carriers are currently blocked entirely by Eligius, IIRC
19:03 < petertodd> Luke-Jr: right, but this scriptPubKey is just OP_RETURN, with no data
19:03 < Luke-Jr> hmm
19:03  * Luke-Jr pulls out the code
19:04 < petertodd> Luke-Jr: I picked that because I wanted the dust-b-gone utility to be absolutely clear that no-one other than miners could get any financial benefit from the coins destroyed
19:06 < Luke-Jr> http://codepad.org/L2J8i1HV
19:06 < Luke-Jr> I don't actually see anything that should change behaviour from mainline that would affect this
19:08 < petertodd> does the push-tx thing on eligius.st submit directly to the node that would be mining the transactions?
19:08 < Luke-Jr> yes
19:09 < petertodd> huh, weird
19:09 < petertodd> give me a sec; I'll make up a tx right now
19:13 < Luke-Jr> give me advance notice of the push; someones are IBDing from Eligius atm
19:14 < petertodd> 'k
19:16 < petertodd> well, it's getting rejected right now, so maybe a previous attempt is still in your mempool, but anyway here is what I tried to pushtx: http://0bin.net/paste/yuxubWzRRKtvj1QX#BFoxJ/sAq5pdwrkufd9BBSRmkYC+BPGKVWbDRHZlafY=
19:17 < petertodd> see how much easier replace-by-fee would make this? :P
19:19 < petertodd> oh, BTW, any objection to be making the TXO discussion we had the other day public? I mean, -wizards is semi-private simply by how it's a bit obscure, and there aren't public logs anywhere (AFAIK)
19:19 < Luke-Jr> which discussion was this?
19:20 < petertodd> two days ago, oct 17th
19:20 < Luke-Jr> I don't see any I participated in
19:21 < petertodd> yeah, I don't think you did
19:21 < Luke-Jr> well, then you don't need *my* permission :P
19:21 < Luke-Jr> just permission from those who spoke in it
19:22 < petertodd> heh, I wasn't asking you, although that you assumed that says something about the relative privacy of -wizards :P
19:23 < Luke-Jr> well, freenode policy makes that matter clear anyway
19:23 < petertodd> oh yeah?
19:23 < Luke-Jr> public channels need to have the log in the topic or onjoin
19:23 < petertodd> ah
19:24 < petertodd> specifically I'm asking because of this guy: https://bitcointalk.org/index.php?topic=314467.0
19:24 < Luke-Jr> gmaxwell: maaku: I think you guys were in the convo?
19:26 < petertodd> amiller: you too
19:27 < amiller> wat
19:27 < amiller> oh, yeah this should be public
19:27 < petertodd> amiller: mind if I make our conversation from two days ago re: TXO commitments public
19:28 < petertodd> amiller: thanks
19:28 < amiller> my understanding is this channel isn't even meant to be obscure, it's just that we discuss stuff that's too weird/frightening for someone trying to build bitcoind
19:28 < petertodd> same
19:29 < petertodd> I think setting up a public archive for this channel would be a good thing re: patents for instance
19:30 < gmaxwell> it's not meant to be obscure, though I have kinda avoided inviting people with ideas which I think are weird because the author is an idiot.
19:30 < petertodd> yeah, that's an issue too
19:31 < gmaxwell> e.g. if your idea is far out because you're dumb I tell you to go away, if its far out because its advanced or really speculative but still sane, I say join #bitcoin-wizards.
19:31 < gmaxwell> it's something of a personal failing that I don't respond really well to people who are agressively promoting jibberish. I'm working on doing better. :)
19:32 < gmaxwell> (if nothing else its at least a failing because my jibberish filter sometimes has false positives)
19:33 < petertodd> https://s3.amazonaws.com/peter.todd/bitcoin-wizards-13-10-17.log <- this is it to be specific
19:33 < gmaxwell> (I'm happy that things here go however everyone else wants them to, but if we get too many people with batshit technobable I'll probably stop participating myself)
19:34 < petertodd> god help us if we need to make #bitcoin-sane-wizards
19:46 < petertodd> alright, replied: https://bitcointalk.org/index.php?topic=314467.msg3371043#msg3371043
19:46 < petertodd> bbl
19:47 < gmaxwell> petertodd: you also posted about the idea in the forum in the bitspam (or whatever it's called) thread.
19:51 < sipa> gmaxwell: i think you answered very politely to the open-source criticism person :)
20:16 < gmaxwell> sipa: thanks.
20:16 < gmaxwell> petertodd: https://bitcointalk.org/index.php?topic=314467.new#new
20:17 < nanotube> hehe loved the riddles.
20:19 < gmaxwell> sipa: I came up with a slight enhancement to PT's MMR-tree idea, just the simple observation that if all nodes are required to store the N top most levels of the tree (by virtue of never including them in proofs), that wallets only need to monitor the fragments of blocks which are making update to parts of the tree where they have UTXOs.
20:20 < gmaxwell> sipa: e.g. you could have wallets 'bloom filter' blocks still in this model.
20:21 < nanotube> sad to say that while i was reading the blue/red hats one for clarifications, hm2's solution snuck up on me. >_< the monk one took a few hints from sipa before i grokked. poisoned wine was easy. and thanks for that riddles link, gmax. :)
20:21 < gmaxwell> (e.g. in addition to normal bloom filtering, they'd recieve the parts of blocks that modify any parts of the history where they have coins)
20:21 < sipa> gmaxwell: i really need to think hard about those MMRs
20:25 < gmaxwell> Crap crap. I solved some wizards relevant problem recently.. and I've forgotten to tell you all. I remembered it while writing that MMR post but then forgot it again by the end.
20:26 < gmaxwell> sipa: at the moment, the worst I can say about MMR is that enjoying its full potential requires more compromises than perhaps we can accept in bitcoin.
20:27 < gmaxwell> E.g. if you go 100% of the way to no one has the full history, then a bootstraping node must only have SPV security.
20:27 < gmaxwell> OHHHHHH
20:27 < gmaxwell> petertodd: So I figured out how to make fraud proofs safe from an engineering perspective. You'll love it.
20:28 < gmaxwell> petertodd: recall one concern we have about fraud proofs is that because they make fraud worthless to try, the damn code won't work right. And then the fraud proofs themselves will be an enormous consensus failure liablity... because eventually someone will create fraud and the proof itself will only partially work. Or they'll make a false fraud proof and kill non-fradulent blocks.
20:29 < gmaxwell> petertodd: The solution: All blocks are required to commit to two versions of the block. One is the real block, the other is required to be fradulent.
20:29 < gmaxwell> petertodd: and the a fraud proof is used to kill the fradulent one.
20:29 < gmaxwell> so the fraud proof code becomes essential and applies to every block.
20:30 < gmaxwell> (note that I said you'll love it, I kinda expect everyone else to hate this idea)
20:30 < gmaxwell> guess I'll go post it before I forget it again.
20:32 < sipa> It is etched forever in my IRC logs.
20:33 < midnightmagic> i hate the idea!
20:33  * midnightmagic ducks
20:34 < HM2> sipa commits his logs in to the blockchain
20:34 < sipa> yeah, using this method: http://xkcd.com/378/
20:51 < gmaxwell> Luke-Jr: did you get a chance to look at petertodd's OP_RETURN transaction and see why eligius isn't taking it?
23:21 < amiller> gmaxwell, unless it's randomly fraudulent or something that wont have the desired effect
23:22 < amiller> if it could be 'any' fraud, then everyone would just throw it softballs
23:22 < amiller> only 1% of the fraud check codebase would be tested and any real fraud would still get through
23:22 < maaku> petertodd: i consider what I say on #bitcoin-wizards public
23:22 < maaku> but thanks for asking
23:23 < gmaxwell> amiller: I dunno about that, if the reference implementation did not throw softballs then there would at least be some fraction of non-softballs and that would be enough to see that its tested.
23:23 < amiller> unrelated: thanks for your recent post in that utxo thread, it's a good summary of all the cool ideas
23:24 < gmaxwell> I suppose it could actually require the fraud to be of a specific type, and you just don't know which block is which.
23:24 < maaku> petertodd: i think that's a very good point re: patents
23:24 < maaku> and logging #bitcoin-wizards
23:24 < gmaxwell> e.g. prior block hash picks the fraud, ... but I'd worry somewhat that adding more network rules has its own risks.
23:27 < amiller> right now the main defense against people mining without checking the whole history is that there's no command line parameter in the reference client to override the start point
23:27 < amiller> (er, well, that and the fact you need to start from the beginning to get a utxo index)
23:27 < gmaxwell> amiller: yea, no accident that there is no way to do that.
23:27 < amiller> we should be able to rely on something like spv security with that
23:27 < gmaxwell> but thats ... uhhh fragile.
23:28 < amiller> it would take some kind of economic thing i guess
23:28 < amiller> but what we *hope* is that people *want* to check back as far as they can
23:28 < amiller> that it's *cheap* enough for them to be able to do so
23:28 < gmaxwell> because eventually something like btcgo (which has insanely slow ecdsa validation) will just offer a don't validate anyhting mode, I guess.
23:28 < amiller> and to the extent that it requires the public good of everyone dragging around enough data to do so, and being willing to share it when needed, that should be incentivized as well
23:29 < amiller> also it really only is a problem if *miners* haven't validated
23:29 < amiller> because everyone else is gonna be spv anyway
23:29 < petertodd> amiller: who's going to to run the full nodes for the spv nodes to connect too?
23:30 < amiller> so the cost to validate as a function of how far back you want to go is (part of) what determines how far back people will check
23:30 < petertodd> gmaxwell: I'm starting to think maybe the think to do is 1) make fraud detection profitable, and 2) make creating fradulent blocks cheap or even free
23:31 < gmaxwell> petertodd: subsidy rewarded to the provider of the fraud notice? :P
23:31 < petertodd> gmaxwell: yes!
23:32 < gmaxwell> kinda like your mining via successful fraud idea.
23:32 < petertodd> lol, yeah
23:32 < petertodd> mainly I want to make it possible for people to cheaply test out fraud detection
23:32 < petertodd> and equally, force everyone else to verify because it's cheap to commit fraud to rip off the non-verifying community
23:33 < petertodd> obviously actually getting the right set of incentives will be hard, but I think the very general idea has merit
23:33 < amiller> i like the concept of "anti-fragile" here
23:33 < amiller> we're best off encouraging a constant balanced supply of fraud and fraud detection
23:34 < petertodd> that's a very good term for it
23:34 < amiller> people should get frauded, a little bit
23:34 < petertodd> look at how non-standard transactions catch up so many alt-implementations, yet it hardly gets tested because only eligius mines them (and I think they might not be right now)
23:34 < amiller> maybe you can force fraud detection to have holes
23:34 < amiller> that would encourage some frauds to get through
23:35 < amiller> maybe everyone has a different hole
23:35 < amiller> but they're all different
23:35 < amiller> that way you can make a fraud, it gets through *someone*, bad luck for them you take their fraud bond
23:36 < amiller> if there's a systematic error then it will be *really* profitable to make it
23:36 < amiller> because you'll take everyone's punctured fraud checker bond
23:36 < petertodd> yeah, that's part of it too, you want people to have incentives to, say, test miners that aren't checking
23:36 < amiller> but generally there will always be some level of success with it
23:37 < petertodd> the idea of having every block commit to two different blocks is an interesting one, though it's almost like you want to be able to prove fraud in the form of "neither block is fraudulent"
23:38 < petertodd> heck, maybe make the de-facto rule be "extend the first block, except when it's been proven fraudulent", which allows miners who get away with non-detected fraud to have their rivals do useless work
23:41 < amiller> what you don't want is mutually assured destruction though, where no one makes the fraud, and no one checks the fraud, because they both overestimate the effectiveness of the others, and then all the missiles are rusted
23:41 < amiller> that may or may not have made any sense
23:41 < amiller> but the point is that there *should* be a healthy amount of fraud in the stationary case
23:42 < petertodd> right, but it's not MAD, because you're only actualy punished if both blocks are fraudulent
23:53 < amiller> MAD wasn't the right analogy
23:53 < amiller> put it this way, who's going to be *paying* for the costs of the constant fire drills
23:54 < petertodd> the only cost is that you need more confirms for a tx to be sure
23:55 < petertodd> the auditing *should* be done anyway
23:56 < amiller> i think you're missing my point but i only have a weak grasp of my point anyway so maybe i'll bring it up again if i have a solution in mind :o
23:57 < petertodd> ha
23:59 < gmaxwell> the important thing is to make firedrills cheap.
23:59 < gmaxwell> then even counting on a few altruists to do them isn't a big deal.
--- Log closed Sun Oct 20 00:00:13 2013