--- Log opened Sat Dec 28 00:00:01 2013 --- Day changed Sat Dec 28 2013 00:00 < andytoshi> "maximum plausible participants" 00:00 < gmaxwell> I wonder if this is some crazy maximal matching problem. 00:01 < andytoshi> yeah, i'll get some paper and see what happens :P 00:01 < andytoshi> i haven't thought about this in any detail up to now 00:08 < andytoshi> ok, i've translated this into a graph theory problem, i'll type it up and post it 00:08 < andytoshi> it's actually pretty neat, maybe it's something well-known 00:15 * gmaxwell waits for the max-flow problem 00:16 < andytoshi> i don't think it's that, i'm looking for a graph on a given vertex set with the maximum number of disconnected components 00:16 < andytoshi> with the edgeset satisfying a bunch of conditions 00:21 < andytoshi> does this look right?: http://download.wpsoftware.net/bitcoin/coinjoin.pdf 00:22 < andytoshi> sorry, it took me forever to find a latex template.. 00:24 < gmaxwell> andytoshi: 2.1 is incorrect. You could have a fee only input. 00:24 < gmaxwell> oh nevermind misread 00:24 < gmaxwell> 2.1 is just that the graph is biparte. 00:25 < andytoshi> that's right, i knew there was a word for that.. 00:25 < andytoshi> but i do fix the input and output sets, and i want to ensure these are the same across every plausible join 00:25 < andytoshi> so i'm not sure how best to say that 00:29 < andytoshi> so, my hunch at this point is that "sort the inputs and outputs somehow then match greedily" will provably give the best plausible join 00:29 < andytoshi> based on, that is how literally every school graph theory problem goes 00:29 < gmaxwell> hahahah 00:30 < gmaxwell> I'm trying to figure out how to refactor this into finding a maximal cut. 00:36 < gmaxwell> I don't think the greedy solution works. 00:37 < gmaxwell> say you have an input of 1.55 which was split into 1.4 and .15 and you greedily assign it a 1.5 output. then you'll be left with a straggler. 00:38 < nsh> greedy doesn't work so well when you have inequalities, i'd guess 00:42 < gmaxwell> andytoshi: hitting set problem 00:56 < andytoshi> oh thx, i'll look that up 01:00 < andytoshi> this is not quite the set hitting problem, that would be if we are trying to cover all the outputs with the least number of inputs 01:00 < andytoshi> here a want a cover by the greatest number of disjoint subsets of inputs 01:01 < gmaxwell> yea.. :-/ 01:01 < BlueMatt> who would be interested in getting a -wizards meetup together at some point in the late march/early april timeframe? 01:02 < andytoshi> BlueMatt: i will know in a week or two what my midterm schedule looks like, but i'd be down 01:03 < andytoshi> i also don't think a greedy algorithm works, this problem does not quite have the right structure 01:03 < gmaxwell> andytoshi: amusingly even that little transaction from tonight is intractable if evaluated via a maximally dumb algorithim that selects all solutions. 01:03 < gmaxwell> s/selects/tests/ 01:04 < andytoshi> cool, do you know how many tests would need to be done? 01:04 < gmaxwell> e.g. there are 9*13=117 edges in the graph, so 2^117. (9 because I merged the dupe address inputs) 01:04 < warren> BlueMatt: will there be a minimum bar of entry? 01:05 < BlueMatt> warren: well, I'll be there, so the bar is set pretty low 01:05 < BlueMatt> in other words...lurkers welcome 01:05 < andytoshi> i think "no floating outputs" is a reasonable assumption, so 117 is a bit high 01:05 < andytoshi> but not by much 01:05 < warren> BlueMatt: what would goals be there? 01:05 < andytoshi> woah 01:06 < BlueMatt> warren: get together, discuss -wizards concepts in person (with whiteboards...), and personally, I'd like to see discussion of moving more things towards implementation 01:06 < andytoshi> i've noticed how hard this is, for example when i was testing the "display max(unsigned txs, mpo outputs)" code (which didn't work, i forgot to update the copy of coinjoin that the site uses :}), some stranger joined with me 01:06 < andytoshi> i was distracted and i trust my joiner, so i just signed what came out without looking at whose outputs are whose 01:07 < gmaxwell> andytoshi: yea, I was just thinking about the dumb algorithim, because sometimes it obviously yields some kind of recursive structure that turns straight into a dynamic programming solution, but I'm not seeing one here. 01:07 < andytoshi> yeah, i'd like to be able to say "if there is a better solution, we can move toward it somehow", but it's not clear at all how different solutions are related 01:07 < gmaxwell> andytoshi: lol, I was thinking it would be good to have a simple tool where you feed it two raw transaction— your merged one and the orignal one, and it just checks that one is a proper subset of the other. 01:08 < gmaxwell> andytoshi: I suspect in most cases there are bunch of "forced edges", and then there are bunch of "equivilent edges" which can be assigned in a greedy way. 01:09 < andytoshi> yeah, for example, can we assume every component is a complete bipartite graph? 01:09 < andytoshi> yes: that doesn't affect any of the three plausible join conditions 01:09 < gmaxwell> Yes. 01:10 < andytoshi> awesome, that feels like a big simplification 01:15 < gmaxwell> so, does that reduce the search— it's obvious to me thats enough to make this sufficient: consider all permutations of inputs, all permutations of outputs, all partitionings of inputs, all partitions of outputs. = 9! * 13! * 2^(9-1) * 2^(13-1) ≈ 2^71 01:16 < gmaxwell> there, I made is 7e13 times faster. 01:17 < andytoshi> yeah, that's about where i am 01:17 < andytoshi> but maybe there is a smarter way to match up partitions of inputs and partitions of outputs (?) 01:19 < andytoshi> is that the right number for 'partitionings of inputs' tho? don't you want http://oeis.org/search?q=partition ? 01:21 < gmaxwell> they're ordered. So it's just like sticking a edge between each vertex whic is either cut or not. 01:21 < andytoshi> oh, yeah, i see 01:21 < andytoshi> right, i definitely don't want integer partitions, those compensate for overcountings which are completly unrelated to this 01:22 < gmaxwell> well the permute/partition is wasteful, since we don't care about orders within the partitions. 01:23 < gmaxwell> which might just be the partition numbers /me thinks 01:23 < andytoshi> yeah, sounds like it, i think that's what set me looking at partition numbers in the first place 01:24 < andytoshi> but i wasn't explicitly thinking about permutations, so when you brought them up i confused myself 01:26 < andytoshi> OK, for each n from 1 up to the number of outputs, consider the partitions of outputs into n subsets, and also the partitions of inputs into n subsets 01:26 < andytoshi> call the number of output partitions O_n, the number of input partitions I_n 01:26 < andytoshi> then the number of plausible joins with n participants is at most O_n*I_n 01:27 < andytoshi> so we can reduce the space to sum_n O_nI_n 01:27 < andytoshi> which is ugly to write, but probably easy to compute, and might even be tractable 01:28 < gmaxwell> numbpart(13)*numbpart(9) = 3030 01:28 < andytoshi> that gives us an upper bound on the sum, right? 01:29 < andytoshi> yeah, it does, write each numbpart() as a sum of O_n's or I_n's, then their product will be the dot-product sum_n I_nO_n plus a bunch of nonnegative cross terms 01:33 < andytoshi> so if we can efficiently loop through these partitions we can brute-force the problem from here ... provided we have fewer than, say, 45 inputs and 45 outputs 01:33 < gmaxwell> there is probably some trivial greedy preprocessing that can be done. 01:34 < gmaxwell> Obviously you should merge all inputs with the same scriptpubkey and all outputs with the same scriptpubkey. 01:34 < gmaxwell> and force any input/output pair with the same scripubkey to be connected, perhaps, (e.g. just remove the output and deduct the input) 01:35 < andytoshi> oh, this is true .. coinjoin already merges outputs, but it doesn't have knowledge of the inputs 01:35 < gmaxwell> well your coinjoin does, but of course I was thinking in terms of an abstract tool that could be run on any transaction. 01:36 < CodeShark> are we talking generalized coin selection optimization? 01:36 < gmaxwell> then there may be other outputs which are forced which I think can be found in a greedy way. 01:36 < gmaxwell> hm. 01:36 < CodeShark> or is this some specific problem? 01:37 < andytoshi> CodeShark: we are looking at "given some transaction, what is the maximum possible number of participants?" 01:37 < gmaxwell> CodeShark: no, talking about taking a transaction and identifying the maximum number of coinjoin participants under reasonable constraints. 01:37 < gmaxwell> (reasonable constraints like the CJ participants not giving away their money) 01:38 < gmaxwell> CodeShark: e.g. what is the largest plausable number of participants in this transaction: https://blockchain.info/tx/a0350aa856b77edeaa08ae9df5047855d487c40490d11713461d200ea70b09c6 01:39 < CodeShark> so the minimum is obviously one, the maximum is the number of inputs with distinct redeemscripts, yes? 01:40 < andytoshi> well, if there are fewer outputs than inputs, then the total number of outputs could be the maximum 01:40 < gmaxwell> CodeShark: nah, because there may be no plausable flow. For example, say you had 10 distinct inputs.. and 1 output. There is only one participant (under reasonable constraints) 01:41 < CodeShark> ok, so maximum = min(distinct input scripts, output scripts) 01:41 < gmaxwell> nah, because if you constrain them to not throw away values you must look at the values. 01:42 < andytoshi> no, there still might not be a plausible flow .. eg if there are 10 inputs and 10 outputs 01:42 < gmaxwell> Say you have 50,.5,.5 in and 25,25,1 out. 01:42 < andytoshi> and one input is massive, all the others are 0.1, and every output is 0.2 01:42 < gmaxwell> In that case you have a maximum of 2. 01:42 < CodeShark> right, my bounds were very weak 01:43 < gmaxwell> yea, you're giving loose bounds, we want the tight maximum bound. As its a measure of privacy the coinjoin provides. 01:43 < andytoshi> it would be nice if 1 wasn't always plausible :) 01:44 < andytoshi> even a lower bound would be useful if it was nontrivial 01:44 < CodeShark> what if we simply required all inputs to be the same value? then each participant would first have to create outputs of specific denominations 01:44 < CodeShark> and join a transaction of a particular denomination 01:44 < gmaxwell> 1 being plausable is good because its also what makes ordinary txn look potentially like CJs. :P 01:44 < CodeShark> yeah, ok :) 01:45 < andytoshi> CodeShark: well, that makes CJ's stand out, and it's also easy to work around by just going back one layer in the transaction dag 01:46 < gmaxwell> andytoshi: hm. interestingly, I think the maximal maximal count may not always have the highest entropy! 01:46 < andytoshi> and then you've even got free association information from the homogeonizing transactions 01:46 < andytoshi> gmaxwell: that is interesting, and that feeling is why i don't think we can do this 100% greedily 01:46 < andytoshi> but for me, for now, it is just a feeling .. 01:48 < CodeShark> I'm not even entirely clear on coin selection optimization within a single wallet, let alone coinjoin :p 01:48 < andytoshi> well, coin selection (to evade this analysis) is an even harder problem, i think 01:49 < CodeShark> if we want coinjoin to be obscure, we want it to mimic typical coin selection strategies for common wallets 01:49 < gmaxwell> can't— goals are to different, instead wallets should mimic coinjoins. :) 01:49 < gmaxwell> s/to/too/ 01:49 < gmaxwell> coinjoins can't be fully obscure simply because >2 outputs are rare. 01:51 < CodeShark> yeah, true - and while there's a good use case for sendmany from servers, for typical interactive users, these use cases are more rare 01:52 < gmaxwell> andytoshi: e.g. there may be some mapping that gives you N users but is unique, e.g. only 1 N user path between inputs and outputs. But then there is some oh, fascinating 01:53 < andytoshi> what on earth can we say about that? 01:53 < andytoshi> about its anonymity* 01:54 < gmaxwell> well for a coinjoin over all you could just count all plausable mappings (for all possible N) and the coinjoin's entropy is log2(that). 01:55 < gmaxwell> e.g. 50,.5,.5 in and 25,25,1 out has an entropy of 1 bit. 01:55 < andytoshi> hmm, if that is the most useful metric than it saves us the trouble of doing all this optimization 01:56 < gmaxwell> I dunno that it does, because you still have to reject impluausable mappings. 01:56 < andytoshi> if we loop over every possible mapping, that's easy, just a bunch of addition 01:57 < gmaxwell> Finding the maximum N is just a subset of the problem.. it's just the highest N for which there remain any plausable mappings. 01:58 < andytoshi> yeah, but we can use a weak upper bound for N in this case 01:59 < andytoshi> i wonder if we want to compute something sharper: the entropy of the individual outputs 01:59 < andytoshi> (it's really not clear to me how to define that) 02:00 < gmaxwell> the interesting thing about output entropy is that it's not independant. 02:01 < gmaxwell> e.g. output X could have come from input 2 if and only if output Y didn't. 02:02 < andytoshi> we can arrange these possibilities in a giant decision tree, and compute some sort of entropy on that.. 02:03 < andytoshi> there is also something called mutual information 02:03 < gmaxwell> I guess measuring per output has some useful properties.. since in a wallet you'd want to know e.g. which of your inputs are tainted. 02:03 < andytoshi> http://mathoverflow.net/questions/88364/is-this-a-situation-where-triple-mutual-information-is-always-non-negative 02:04 < gmaxwell> andytoshi: I'm trying to come up with a "conservative" version of it which isn't trivial. 02:04 < andytoshi> (this was a question my supervisor asked about whether he could apply some tool called 'diversities' (i have a single-author paper on the analytic properties of these) to computing mutual information 02:04 < gmaxwell> E.g. assume the attacker knows "a lot" about the other outputs, what is your entropy. The problem with that is that the obvious form of a lot is "knows all the other outputs" in which case the entropy is 0 02:05 < andytoshi> now, what this tells you is that "all the other outputs" is strongly coupled to your output 02:05 < andytoshi> maybe you want to know, how strongly are my various outputs coupled to each other? 02:06 < gmaxwell> andytoshi: multial infomation is just the joint entropy minus the conditional entropies. 02:07 < gmaxwell> andytoshi: well I'd like to be able to answer how tightly my keys (inputs or outputs) are coupled after a transaction. So that I can decide to group the keys and freely merge them in future txn if they are too tightly coupled. 02:07 < nsh> hmm 02:08 < andytoshi> yeah, so this is a more useful thing to wonder about than "how tightly coupled are all the outputs of this specific transaction" 02:08 < gmaxwell> interestingly, even when paying someone without coinjoin the number of players is 2 and we can talk about the coupling in the change output(s). 02:09 < gmaxwell> though the most entropy we can have in a single output when there are only two players is 1 bit. 02:10 < andytoshi> here is a selfish question: if we take the definition of diversity from page 2 of http://arxiv.org/pdf/1307.1897.pdf , can we describe this coupling as a diversity? 02:10 < andytoshi> (it is selfish because if the answer is yes, then i can perhaps finangle a publication while still doing something useful for bitcoin) 02:12 < andytoshi> describe some measure of coupling* 02:13 < gmaxwell> I must confess, the first sentence of the abstract triggered turboencabulator-detection for me. 02:14 < gmaxwell> ( https://www.youtube.com/watch?v=rLDgQg6bq7o ) 02:15 < andytoshi> hahaha 02:16 < andytoshi> what is meant by that claim is, "this is used by biologists for some tree-calculation something", which is true but not anything i know anything about 02:16 < andytoshi> i admit, the core of that paper is almost cartoonishly "mathematicians inventing problems for no reason except to have fun solutions" 02:19 < andytoshi> but here is a paper relating this stuff to flow problems: http://arxiv.org/abs/1312.5408 02:19 < andytoshi> so i am not blowing smoke when i suggest that it's applicable :) 02:20 < gmaxwell> I think for any of this stuff you could imagine some hypothetical 'mixer' with perfect knoweldge of the inputs to output mapping, and just measure the entropy of his knoweldge. It gets more interesting when you consider graphs with many coinjoins. 02:20 < gmaxwell> esp if the many coinjoins are not wired up like a switching network, so that the inadmissablity of multiple inputs later deanonymizes earlier coinjoins. 02:20 < andytoshi> yeah, i think that's the most useful thing for the joiner itself to output 02:21 < andytoshi> but if, for example, some output always winds up matched to a certain input, the owner of that output would like to know this 02:22 < gmaxwell> yea. indeed. though at least that can be solved purely locally. 02:22 < gmaxwell> but I don't think an obvious greedy algorithim exists. 02:23 < andytoshi> so, for the joiner's calculation, it needs to know if certain inputs are obviously linked 02:23 < andytoshi> and "obviously linked" does not sound well-defined to me 02:24 < andytoshi> would it suffice to assume the inputs are independent, and just look at the entropy of the mixer's input-to-output mapping 02:24 < andytoshi> ? 02:25 < andytoshi> that's nice because it's context-independent -- you give me any rawtx and i can compute that without even a network 02:26 < gmaxwell> andytoshi: you can assume the inputs are independant after doing the trivial preprocessing to merge ones with duplicate scriptpubkeys. 02:27 < gmaxwell> if that raw tx is signed you can still do it by looking at the scriptsigs ... most of the time. 02:28 < gmaxwell> andytoshi: the other weird thing is that this 'plausable' metric is kinda odd in that any funnybusiness at all results in a misestimation of 0 entropy. 02:29 < gmaxwell> which actually suggests that it's worth thinking about how we can enable that kind of funny business because— just like the argument for CJ existing— if the funny business exists with enough frequency, an attacker is forced to assume any txn might involve funny bussiness. 02:29 < andytoshi> can you give an example of this? 02:30 < gmaxwell> andytoshi: yea, sure, say you and I do a coinjoin. But I actually happened to owe you money, and so the real mapping isn't a 'plausable' one because it transers some of my coin to you. 02:30 < andytoshi> oh, i get what you mean 02:31 < gmaxwell> concretly e.g. you put in 1 and I put in 5, and then you get out 2 and I get out 4. all that we've discussed above would decide the maximal users there was 1. 02:31 < andytoshi> right, that's great, and it's not at all hard to do now .. if you owe me money, i'd say "let's get in on the next join session" 02:31 < andytoshi> (and with me personally you could even use the donation output 02:32 < andytoshi> ) 02:32 < gmaxwell> yea, even outside of the context of a specific coinjoin: you can do this generally for payments as a way to consoldate change. E.g. if I want you to pay me, I could give you some extra inputs to include.. then you sign and give me the half signed txn. 02:32 < andytoshi> ah, that would require better tool support 02:32 < gmaxwell> Yea, but it could just be an addon in the payment protocol pretty easily. 02:33 < gmaxwell> "Add these extra inputs to the transaction and pay them to me, thanks" 02:34 < gmaxwell> the interesting question is that once you've relaxed the defintiion of 'plausable' to include the possiblity of payments.. I think _any_ mapping is possible. 02:34 < gmaxwell> and the entropy of the coinjoin is basically log2(inputs*outputs) 02:35 < andytoshi> yeah, i think that's correct, which is pretty cool 02:35 < gmaxwell> as there is an auxiliary table of users paying other users. 02:35 < andytoshi> now, perhaps nsa with its psychologists can get information out that we can't 02:35 < gmaxwell> but the problem is that if no one ever does this— then it doesn't matter. An attacker isn't really constrained to consider corner cases. 02:35 < andytoshi> but that's probably not a threat model we can do anything about 02:35 < andytoshi> right, exactly 02:36 < andytoshi> for now our definition of 'plausible' is good, so let's work with that 02:36 < gmaxwell> oh sure, not all payments are equally likely. For example, I can say that as a prior that auxliary payment table is probably _sparse_ e.g. that it has a low l_0 norm. 02:36 < gmaxwell> and that non-sparse payment tables are very much less likely than sparse ones. 02:36 < gmaxwell> even in a world where people use this frequently. 02:37 < andytoshi> that seems plausible, though it's hard to say in the presence of fees 02:37 < andytoshi> maybe people only want to do transactions if they need to do transactions 02:37 < gmaxwell> well, its just unlikely that you could find N people who all want to pay a bit to each other, for N>2 :P 02:38 < andytoshi> oh, yeah :P 02:38 < gmaxwell> cut-throughs also add some interesting analysis wrinkles, again— if they actually existed. 02:39 < andytoshi> now, here's a silly question: our definition of coinjoin entropy as "entropy of the mixer's knowledge" .. is it monotonic? 02:39 < andytoshi> monotonic wrt the number of transactions 02:39 < gmaxwell> you mean the number of contributors to a mix? 02:39 < andytoshi> so if my joiner says "there's a 10-bit transaction in here", can somebody put in a transaction which reduces the entropy? 02:39 < gmaxwell> No, it must go up. 02:39 < andytoshi> yeah 02:39 < gmaxwell> (or stay the same) 02:39 < andytoshi> is that obvious? 02:41 < gmaxwell> I think so, otherwise I could just grab a random unrelated txn, add it to a transaction I was analyizing "assume this was joined in" and magically know more about the original transaction. :P 02:41 < andytoshi> i like that argument :) 02:42 < gmaxwell> The understanding that it was monotonic is why I've favored including poorly mixing transactions too, if thats all thats available. 02:43 < gmaxwell> likewise it would be useful to join coinjoins. e.g. if you had a 1 BTC mix and a 0.5 btc mix going on, might as well make the final txn contain both of them. Maybe you'll get lucky and some change will be ambigious. 02:43 < gmaxwell> And if the attacker is forced to the N^2 model (where people are paying people) then the entropy increases enormously. 02:44 < andytoshi> cool, this all sounds good 02:45 < andytoshi> i'll spend some time trying to compute this entropy 02:45 < andytoshi> maybe i can compute the entropy of output values, and say "the highest-entropy output is XXX" rather than "the most popular output is XXX" 02:46 < andytoshi> i'm not sure if there's a good way to define such a thing.. 02:46 < gmaxwell> hm. I wonder what the entropy impact is if you limit the aux matrix to a maximum column L_0 norm of 2. uhh. like "You can may at yourself and at most one other party", or futher "optionally yourself and optionally one other party, and if you are paying that other party, that other party pays no one else" 02:46 < andytoshi> it'd be awesome if i could make the transaction entropy be the sum of the output values' entropy 02:47 < andytoshi> my guess is, it'd reduce the attacker's search space from N^2 to 2N 02:47 < andytoshi> or somethin 02:47 < andytoshi> something drastic* 02:48 < gmaxwell> e.g. a realistic use of the non-admissable coinjoins is one where at most half the participants are each paying up to one additional other participant (who isn't paying anyone but themselves) 02:49 < gmaxwell> I guess one interesting thing when you allow payments is, in fact, that you add up to 'outputs' worth of 'shadow' inputs that provide 0 in. 02:49 < andytoshi> yeah, my guess is that this would be the most common case, after admissable coinjoins, by -far- 02:50 < gmaxwell> well it generalizes all transactions too.. e.g. a regular payment to you with change fits this model now. 02:50 < andytoshi> oh yeah 02:52 < gmaxwell> in any case, a whole bunch of neat papers could come out of this, but I think so long as coinjoins are more acadmic than reality any attacker will just go "lets assume that never happens and we'll sort it out if we do ever find a case where it did" 02:52 < andytoshi> agreed, for now i will compute the entropy assuming no funny business 02:53 < andytoshi> link to a short document explaining the calculation and how to do funny business which makes the tx safer than claimed 02:57 < gmaxwell> BlueMatt: will the pulltester still run if I close a pull? 03:10 < BlueMatt> gmaxwell: no 03:12 < gmaxwell> BlueMatt: seeing things like this pass is always not a happy moment: https://github.com/bitcoin/bitcoin/pull/3469 03:12 < gmaxwell> but as expected since regtest overrides. 03:13 < gmaxwell> but ... reasons I don't love regtest being a seperate mode… 03:15 < BlueMatt> true, though pull-tester is designed to test subtle bugs, not head-smacking bugs 03:16 < BlueMatt> it fails at both, but still 03:18 < gmaxwell> Ideally we should be able to test pulltester by inserting head-smacking bugs though, and making sure that every possible headsmacking bug we can think to insert fails... (The reason being that headsmacking bugs are easy to insert and be sure that they're actually bugs and not equally okay changes) 03:18 < BlueMatt> agreed 03:18 < BlueMatt> feel free to code it :p 03:37 < sipa> dang: http://bitcoin.stackexchange.com/questions/19455/searching-for-the-comprehensive-guide-to-creating-crypto-currency 03:39 < warren> sipa: we need someone to actually write the clonecoin generator that we all threatened to write. 03:39 < sipa> yeah 03:39 < warren> option: Set exchange bribe amount [minimum 100 BTC] 03:40 < warren> checkboxes for various bad ideas 03:49 < warren> sipa: would others fund this? I can get one of my students to do this. 03:49 < warren> I can throw in some money. 03:50 < gmaxwell> heck, if done right (costs a small bitcoin payment to make it build) it can be revenue producing. 03:50 < warren> hahah 03:51 < warren> don't release source for the generator. make it a web app that outputs everything. 03:51 < gmaxwell> oh absolutely. 03:51 < gmaxwell> heck, you could even charge more to get source out with your binaries (take care not to violate the LGPL, it needs to be relinkable) :P 03:52 < warren> checkbox: "Steal sunnyking's proprietary source for centralized broadcast checkpoints. Will he sue?" 03:52 < warren> haha 03:54 < gmaxwell> [ ] set your own alert key [....] {+.1 BTC} 03:56 < midnightmagic> lol 03:56 < midnightmagic> that would be so much win 03:56 < midnightmagic> + seednode code generator 03:56 < gmaxwell> yea, it needs to also provide a standalone miner and pool setup. which is kinda a pita. 03:57 < gmaxwell> the miner isn't so bad so long as it uses sha256 / scrypt / primecoin but the pool setup is more of a pain. 03:57 < warren> hence you charge more 03:58 < warren> it can spit out VM's for block explorers, *cointalk.org SMF, bribe form letter to 03:58 < warren> make it very easy 03:58 < warren> programmatically create a shill army too 03:58 < warren> mechanical turk? 04:00 < sipa> [ ] Use less than 2 year old Butcoin source code {+.3 BTC} 04:00 < sipa> ehm... that actually is a typo, i meant Bitcoin 04:01 < BlueMatt> well if you dont pay it forks buttcoin instead 04:01 < gmaxwell> well buying and selling accounts on bitcointalk is permitted. 04:01 < gmaxwell> so you can even one-stop buy your shill army. 04:02 < warren> would you sell after-sale support? 04:02 < warren> 1 BTC/hour 04:02 < warren> NO WARRANTY 04:03 < sipa> [ ] Use doge-styled shill army posts 04:04 < sipa> actually, the opposite perhaps should cost money 04:04 < sipa> so we'll get easily recognizable dummy posts by defauly 04:06 < warren> http://aurawallet.com/ somehow this site causes chrome to use 100% of 4 cores. maybe I'm mining for them. =P 04:08 < midnightmagic> lol 04:12 < midnightmagic> it would be an excellent example of why scamcoins are pointless. what a statement. 04:14 < warren> what's up with this Nxtcoin thing? written in java. entirely premined. 04:14 < _ingsoc> 100% PoS apparently. 71 one people own all of it. Yup. :/ 04:15 < _ingsoc> No mining! It's a winner. 04:15 < _ingsoc> They figured out to do what Bitcoin does and more with no mining necessary. I bet you're all feeling pretty dumb right now. 04:15 < gmaxwell> 100% PoS? does it suffer from the nothing-at-stake attack that PPC originally did then? 04:16 < gmaxwell> or is it a consenus that requires quadratic communication, requires all nodes with stake to be online, and is trivally jammed by any participant? 04:17 < warren> the PoA design sounded great in that regard, except after we realized it encourages banking cartels. 04:18 < gmaxwell> well, glad to hear that its something different. 04:18 < gmaxwell> "Nxt doesn’t use so-called “scripts” aka predicates. This simplifies and accelerates transaction processing. Advanced features like multisig will be created on top of the core as 3rd party services." 04:18 < gmaxwell> hopefully '3rd party services' means something domain specific. 04:19 < warren> sounds like they will have centeralized issuers like ripple 04:19 < warren> sounds very much like ripple 04:19 < warren> including the not open source part 04:19 < gmaxwell> yea, indeed not open source 0_o crazy 04:21 < _ingsoc> warren: That was my first thought too. 04:22 < gmaxwell> apparently it's currently being dossed and they are trying to train a "Neural net" to remove spam. 04:23 < _ingsoc> gmaxwell: Nxt? 04:23 < gmaxwell> yea, I can't find anything about how it works though. 04:23 < gmaxwell> apparently it's a blockchain, so that probably rules out it being a standard quadratic consensus. 04:23 < gmaxwell> which probably means its vulnerable to the nothing at stake attacks. 04:27 < warren> I was thinking, woudl there be a way to cancel out the extra orphan risk of larger blocks 04:27 < gmaxwell> oh wow, this is partially the work of that Come-from-Beyond guy... 04:28 < warren> if the difficulty was fudged by some factor of the transactions (quantity, days destroyed, fees, or something) 04:28 < _ingsoc> gmaxwell: Has he done anything else? 04:28 < _ingsoc> That we know of. 04:29 < gmaxwell> beyond being a confused jerk on the forums? 04:29 < gmaxwell> what a bummer. 04:29 < gmaxwell> after seeing that I'd estimate less than 1% chance that it works. 04:30 < _ingsoc> xD 04:30 < gmaxwell> I guess thats part of why I didn't see it, I have him on ignore on the forum. 04:30 < gmaxwell> https://bitcointalk.org/index.php?topic=352286.msg3794431#msg3794431 04:31 < _ingsoc> Hahaha. 04:31 < _ingsoc> Do you know why he's on ignore? 04:31 < _ingsoc> Not to detract. 04:35 < gmaxwell> no idea, but it would be the same as anyone else— nasty*ignorant > threshold. 04:35 < midnightmagic> but.. it's in java. who cares if he releases the code? 04:35 < _ingsoc> ^^ 04:37 < gmaxwell> I don't agree. I don't personally like java, but its currently the language I'd prefer any mediocre programmer use if I'm ever to run their software at all. 04:38 < midnightmagic> oh I just meant that unless he's running weird obfuscators it can be decompiled to fairly readable 04:38 < _ingsoc> I couldn't care less about all these coins. They should have the right to present their ideas and get the support if people want to. I just wish it wasn't so damn sketchy. How many people now have just taken money or made absurd promises? Countless people have been suckered into that type of belief system, and that sucks. 04:38 < _ingsoc> gmaxwell: Mediocre programmers should be roping people in. :/ 04:38 < gmaxwell> uh.. nxtcoin addresses appear to be 20 base 10 digits... 66 bits? 0_o 04:39 < _ingsoc> shouldn't* 04:42 < gmaxwell> this thing is amazing. 04:42 < gmaxwell> it's like every bad idea multipled into an swimming orgy of bad ideas. 04:43 < gmaxwell> it _forces_ you to use brainwallets. 04:43 < gmaxwell> and the addresses are ~20 base 10 digits, based on a kind of first bits system where the system remembers the first pubkey it's seen spend for any prefix and then always uses that pubkey. 04:44 < sipa> wait, parts are closed source? 04:45 < gmaxwell> sipa: it's all closed source except for some small parts they released. 04:45 < _ingsoc> Reasoning? 04:47 < gmaxwell> well it's an entirely premined coin. 04:47 < midnightmagic> so.. much.. development effort that could have been put to constructive use. :( gaw how disappointing. 04:47 < gmaxwell> it doesn't appear to actually be that much. 04:48 < sipa> "a single source file", "no comments"... these guys are satoshi reborn! 04:48 < _ingsoc> Hahaha. 04:49 < maaku> _ingsoc: the problem is that ignorant people with money to invest actually find these things more credible than real projects :\ 04:50 < gmaxwell> here is their PoS mining code in their early source release: 04:50 < gmaxwell> int elapsedTime = getEpochTime(System.currentTimeMillis()) - lastBlock.timestamp; 04:50 < gmaxwell> if (elapsedTime > 0) { 04:50 < gmaxwell> 04:50 < gmaxwell> BigInteger target = BigInteger.valueOf(Block.getBaseTarget()).multiply(BigInteger.valueOf(account.getEffectiveBalance())).multiply(BigInteger.valueOf(elapsedTime)); 04:50 < gmaxwell> if (hits.get(account).compareTo(target) < 0) { 04:50 < gmaxwell> 04:50 < gmaxwell> account.generateBlock(user.secretPhrase); 04:50 < _ingsoc> maaku: I think you'd be surprised. There are so many people who are new to this field looking to be part of something that they can grow with. That's the appeal. So they justify "investing" money they might not have because their urge to be part of it outweighs rational thought about the project itself. 04:52 < gmaxwell> no, having talked to VCs, maaku's characterization appears to be spot on. Wild, unsupported, even impossible claims add credibility. I think people seem to believe that you'll actually accomplish some fixed percentage of what you claim to, so the guy who claims infinite things is obviously the best. 04:53 < _ingsoc> True, I'm not denying there wouldn't be bigger money involved, but you bet there are smaller guys getting burned by these things. 04:54 < _ingsoc> But I guess you do your research and go with what you believe in. 04:54 < gmaxwell> yea, this is totally vulerable to a nothing at stake attack. 04:55 < gmaxwell> they create ECDSA signatures of a candidate block and hash them, then compare them to a target that depends on time and the value of that account. 04:56 < gmaxwell> so of course, the same attack PPC got nailed with applies trivially. 04:56 < maaku> yeah Jorge and I have talked to quite a few VCs trying to get funding for Freimarkets. it always seems like we're at a perpetual disadvantage by only claiming what we think can be reasonably achieved 04:57 < sipa> gmaxwell: yes, but if the mining code is not open sourced, that is no problem, right? :p 04:57 < maaku> and in VC eyes, a project that got funding is treated as credible (assuming that someone somehwere did due diligence, I suppose) 04:59 < gmaxwell> pretty sure I can just hack the java bytecode directly here to make it mine all the blocks. 04:59 < gmaxwell> it just needs one extra wrapping loop, with a break when its actually successful. :P 05:05 * midnightmagic grits teeth and discovers more reasons why macports feels broken 05:06 < midnightmagic> https://trac.macports.org/ticket/35358#comment:28 05:40 < gmaxwell> wow: ... this thread has gone a bit pear shaped since I last looked at it!!! https://trac.torproject.org/projects/tor/ticket/8106 06:22 < jtimon> gmaxwell what java bytecode can you hack? 06:28 < _ingsoc> jtimon: Nxt. 06:40 < jtimon> oh, Nest, thank you 06:41 < jtimon> wasn't that source closed? I assumed it was a ripple fork 06:52 < _ingsoc> They've released some snippets apparently. 07:15 < gmaxwell> So random not very bitcoin idea. 07:16 < gmaxwell> Tor HSs have had some amount of problems with attackers exploiting the now-popular vanity addresses. 07:16 < gmaxwell> onion addresses are only 80 bits long, 5 bits per character, and there are super fast gpu vanity generators, so some not nice people have been generating lookalike names and then leaving links around. 07:18 < gmaxwell> Some future HS system could make lookalike attacks much harder by requring any HS address generation to also generate a lookalike address. You prove you have your required lookalike by just disclosing the second address inside your HS directory entry, so the urls are no longer. 07:19 < gmaxwell> And the advantage of this is that since it's a collision a 64 bit lookalike takes only ~2^32 operations. But someone trying to pick a specific value instead of pick only any two similar ones, has a much harder time. 12:06 * andytoshi quietly adds this to the tor-like payment protocol in his "if i had an alt" document 12:22 * sipa should also start such a document 12:30 < gmaxwell> @#$*(@*#$(@* why isn't there a @#*(*$@(#* augmented PAKE that doesn't add a communication round?!@# 12:32 < sipa> PAKE? 12:36 < gmaxwell> Password authenticated key exchange. 12:38 < petertodd> BlueMatt: re -wizards meetup, I'm in 12:39 < andytoshi> gmaxwell: regarding our calculation last night about the number of input/output partitions we have to brute-force through .. i was badly wrong about the partition numbers giving an estimate 12:39 < andytoshi> http://oeis.org/A000110 12:40 < andytoshi> (number of partitions of a set of labelled element, which grow exponentially) 12:42 < andytoshi> so we need to be more intelligent to compute the entropy we want 12:45 < andytoshi> petertodd: do you recognize this as some well-known matching problem?: 12:45 < andytoshi> http://download.wpsoftware.net/bitcoin/coinjoin.pdf 13:11 < petertodd> andytoshi: nope, I could however write a paper talking about it in terms of post-modern art critique... 13:11 * petertodd is a fine arts grad 13:12 < warren> does mastercoin know this? =) 13:12 < petertodd> warren: probably 13:13 < petertodd> warren:though their process for hiring me consisted of me talking to one of their people on the phone for an hour... 13:37 < andytoshi> what is also interesting, is that in the join a0350aa856b77edeaa08ae9df5047855d487c40490d11713461d200ea70b09c6, there is roughly 0.005 btc going to (presumably) the donation output, so this output mucks up the naive plausible join analysis 13:38 < andytoshi> by doing exactly the funny business you suggested 13:39 < andytoshi> s/you/gmaxwell 13:49 < andytoshi> OK, rosemary thinks that the 'find maximal number of plausible participants' is NP-hard 13:49 < andytoshi> it reduces to the partition problem 13:50 < petertodd> andytoshi: is that np-hard per tx, or for whole tx graphs? 13:51 < andytoshi> np-hard per tx :( 13:51 < petertodd> andytoshi: maybe that's better? tx's have limits on how big they are... 13:51 < petertodd> andytoshi: remember that two-party-mixes are most likely to be what people actually use 13:52 < andytoshi> petertodd: well, the example we are using is http://blockexplorer.com/tx/a0350aa856b77edeaa08ae9df5047855d487c40490d11713461d200ea70b09c6 which is probably intractable 13:53 < andytoshi> and there are actually only 3 people in there 13:53 < petertodd> andytoshi: that's still a much bigger tx than the expected everyday two-party-mix case 13:54 < andytoshi> yeah, but if you only need one of them to hide a drug deal, you're golden 13:55 < petertodd> sure, point is, I'd be very interested to see algorithms giving some plausible answers for how much privacy even the simple two-party-mixes are adding, and it sounds like the computation required to do that shouldn't be ridiculous 13:57 < andytoshi> petertodd: well, rosemary's reduction involves constructing a 2-party mix corresponding to a given multiset .. if you can determine that it might be a 2-party mix, then you've solved the partition problem for that multiset 13:57 < andytoshi> determine whether it could be a 2-party mix* 13:58 < andytoshi> though as you say, maybe this is OK because the number of inputs and outputs is small 13:59 < andytoshi> but 'only 2 people' does not let us slip into P 13:59 < petertodd> exactly, even if it's some crazy n^n algorithm, the n is small 14:00 < petertodd> from a usability point of view we have to assume that naive two-party mixes are what is going to be most popular 14:27 < sipa> who/what is rosemary? 14:32 < andytoshi> :P i was wondering if somebody would ask that.. 14:33 < andytoshi> rosemary is my girlfriend, she is not so into bitcoin 14:33 < andytoshi> but her degree was largely CS, so i badger her with a lot of these questions 14:33 < sipa> she does seem into complexity analysis :) 14:33 < andytoshi> mmhmm :) 14:52 * maaku would love to read andytoshi and sipa's "if i had analt" documents 14:52 < maaku> BlueMatt: wizards meetup, where are you thinking? 14:52 * sipa guesses it will be too far for europeans 14:53 < warren> do it in Hawaii 14:53 < sipa> even further :( 14:54 < petertodd> pity there isn't an island in the atlantic ocean... 14:54 < andytoshi> maaku: right now i don't have any of the cool stuff (agressive pruning, utxo commits, etc) written down, because i haven't taken the time to make those decisions 14:55 < warren> petertodd: Iceland! 14:55 < maaku> petertodd is a renaissance man. where'd you do your fine arts? 14:55 < maaku> yeah iceland. or the azores 14:55 < sipa> Iceland is very cool8 14:55 < sipa> cold, even 14:56 < petertodd> heh, iceland it is! 14:56 < warren> we can enjoy puffin meat 14:56 < petertodd> maaku: http://www.ocadu.ca/ 14:56 < petertodd> warren: and go aroudn taking beautiful phtoos 15:04 < maaku> heh, you got my wife excited about a trip to iceland now 15:05 < sipa> warren: puffin is nice! 15:05 < andytoshi> oh, that's right, petertodd said he was a -canadian-, not a mathematician 15:06 < andytoshi> that's why i asked you about the matching problem :P 15:06 < petertodd> andytoshi: minor typo, the keys are like right next to each other 15:07 < sipa> someone read too much bash.org 15:07 < maaku> maybe we can get Cloud Hashing to host it 15:07 < petertodd> sipa: +1 15:07 < maaku> i don't think they're in reykjavik though 15:08 < warren> how much of the world's hashing will be in iceland... 15:09 < maaku> arctic air and geothermal power... 15:09 < petertodd> warren: I was just doing the math on if my parents could heat their house profitably with bitcoin mining... 15:09 < sipa> if you can heat your house at acceptable cost using electricity, you certainly can when using mining hardware instead 15:09 < sipa> except: noise, hardware cost 15:10 * maaku is waiting for an HVAC insert to replace heating coils with bare ASICs 15:11 < petertodd> sipa: problem is we're really talking about hashing not mining 15:11 < sipa> unsure what distinction you mean 15:11 < petertodd> maaku: I'm waiting for silicon that can run at > 100degC 15:11 < sipa> petertodd: GPUs! 15:12 < petertodd> sipa: it doesn't buy us a damn thing with regard to decentralization 15:12 < warren> decentralized hashing means nothing if cex.io 15:12 < petertodd> warren: yup 15:17 < petertodd> sipa: so fwiw fuel oil is about 1/3rd of the cost of electrical heat up here, and electricity is $0.3/kwh - what's interesting is that the more northern communities tend to have electricity costs similar to fuel oil heating costs because it's all diesel generators anyway 15:17 < petertodd> sipa: here in yellowknife though they have (expensive) hydro-electricity from a small damn a little further north 15:18 < petertodd> *dam 15:27 < maaku> petertodd: you're in yellowknife? 15:27 < maaku> that is far north 15:27 < maaku> i was watching a special the other day about the mining and prospecting boom up there 15:28 < maaku> (old school mining) 15:29 < maaku> I grew up on a steady diet of Jack London. In another life I'd probably be up there myself. 15:42 < petertodd> maaku: yeah, visiting the parents, they moved up there 9 years ago 15:43 < petertodd> maaku: there's two former gold mines within city limits here, and tens of millions of tones of water soluable arsenic trioxide left over from one of them... 15:43 < maaku> ugh 15:45 < petertodd> yup, plan is to freeze it in place to be par of the permafrost; there's a small river that runs directly over the caverns the stuff is stored in, and god knows what global warming will do 15:46 < petertodd> *part 15:47 < petertodd> I love to use it as an example of how the safety of nuclear waste disposal is overblown: at least nuclear waste becomes safer over time, that arsenic will be toxic forever 16:02 < BlueMatt> petertodd: nice 16:02 < BlueMatt> maaku/sipa: looking at north carolina (east coast) as there will likely be a mini-btc-conf there around that timeframe (hence why I was suggesting it) 16:03 < BlueMatt> and if someone doesnt want to pay the flights, its possible they can commit to giving a quick talk and getting that covered 16:03 < BlueMatt> sipa: at least its not as far as mtv :p 16:05 < petertodd> BlueMatt: lots of nice caves in that area :P 16:06 < sipa> BlueMatt: yeah. but finding a reason to visit mtv is easy :) 16:07 < BlueMatt> true 16:07 < BlueMatt> sipa: still, it only costs like 1-2 BTC these days... 16:08 < petertodd> BlueMatt: not all of us are satoshi :P 16:08 < sipa> damn, that really sounds cheap... 16:08 * BlueMatt bought a laptop for 2 btc a few weeks ago because it sounded too cheap 16:08 < sipa> i recently topped up my mobile account using btc 16:08 < sipa> in .be 16:09 < sipa> i wanted to add just 10 eur, and accidentally added 25 eur though... 16:10 < sipa> i really don't have any reference for BTC prices (and i guess nobody does)... but compared to the amount i have (some leftover from mining 2 years ago...) it all sounds like nothing 16:12 < sipa> petertodd. maaku. gmaxwell: what's the latest evolution regarding TXO MMRs? 16:13 < maaku> defer to petertodd & gmaxwell on this 16:13 < petertodd> sipa: doing a writeup for them is on my never-ending todo list... 16:13 < petertodd> sipa: the thinking behind them hasn't changed fwiw 16:15 < sipa> i heard something about splitting it up into... i suppose a non-changing txo part and a changing spentness part? 16:16 < petertodd> sipa: oh, that was my plan from the beginning 16:16 < sipa> i didn't catch that part initially then 16:17 < petertodd> sipa: well the key thing is you want to still provide a zero-trust way for wallets to sync data, so a per-block index still makes a lot of sense 16:18 < petertodd> sipa: main thing is the two ideas are separate really 16:18 < sipa> you mean... still have a merkle UTXO tree too? 16:18 < petertodd> sipa: no, a per-block txo tree sorted by H(scriptPubKey) or similar 16:19 < sipa> ok 16:19 < petertodd> sipa: my main thinking is that wallet software wants to be able to sync transactions, rather than just funds. this also ties into a paper I'm writing on privacy issues and blockchain data 16:29 < sipa> petertodd: not sure i'm following the big picture anymore 19:28 < maaku> petertodd sipa: two separate indices under consideration here right? 19:29 < maaku> the TXO MMR which is an append/update structure whose hash root is committed to the coinbase 19:30 < maaku> you append each new output, and update a spent-bit for each input 19:30 < maaku> and a separate, per-block tree of outputs indexed by TXO, right? 19:35 < gmaxwell> At some point I'd convinced myself that it made sense to have seperate append only and insert only datastructures, though I don't know why. Obviously managing an append only one is much easier. 19:40 < maaku> oh i guess it can be the same structure as actual insertion/append order within a block doesn't matter 19:42 < maaku> gmaxwell: for double-spend validation I still think an updatable trie structure is best 19:42 < maaku> but lately I've been thinking about a MMO-like structure for the scriptPubKey index 20:05 < gmaxwell> justanotheruser: So perhaps its possible to construct a precisely brittle cryptosystem and paired signature system such that I encrypt data using keys plus some additional data which I give you, such that knoweldge of _any_ signature with the key is enough to decrypt the data. 20:05 < gmaxwell> but not enough to forge signatures. 20:06 < nsh> i really want to see more of a sketch of how this would work, and elaborations on the intractability of adaptive difficulty 20:06 < nsh> or at least some clearer idea of to achieveable precision in likely decryption window 20:06 < nsh> *the 20:07 < gmaxwell> DSA like schemes can be constructed so that they leak a linear relationship between the the private key and the message. So the trickyness would be figuring out how to leak just enough that the encryption is revealed but not forgery. 20:07 < nsh> (re: POW which turns the distributed computation into ticking for timelock encryption) 20:07 < nsh> right 20:07 < gmaxwell> nsh: yea, I dunno, it's a very vague sketch. I was happy that something like it sounded possible because it just seemed to me to be the most realistic way of having non-trustbased timelock encryption I'd ever heard or thought of. 20:08 < justanotheruser> I wish this was possible with bitcoin because this altcoin would only be valuable for secret keeping meaning the only exchanges would be between miners and secret sharers 20:08 < justanotheruser> and speculator 20:08 < justanotheruser> s 20:08 < gmaxwell> But the obvious ways to go about bilding it are super ugly. 20:08 < nsh> mmm 20:09 < gmaxwell> justanotheruser: Well, as I said before a two phase protocol could make it possible to pay for it in bitcoin. The advantage of the alt thing is just that the pow would be "useful". 20:09 < gmaxwell> E.g. lets not go building a bunch of things that require people to needlessly burn energy when we can instead just build one. :P 20:11 < justanotheruser> gmaxwell: So you're saying the secret miners would be securing the network in this altcoin, while they wouldn't be in bitcoin? 20:11 < justanotheruser> I mean you're saying that's your concenr 20:12 < gmaxwell> justanotheruser: right. The idea on the altcoin page is that you have a cryptocurrency who's POW has a side effect of yielding previously unknown private keys for public keys which were set way in advance. 20:12 < gmaxwell> which IMO is way more useful than that primecoin crap. :P 20:14 < gmaxwell> My example of using DLP cracking is lame because DLP cracking is super-not-progress-free. You get a quadratic speedup from being stateful... but there are a LOT of different cryptosystems out there. I would be really surprised if something weren't reasonably sutiable. But even ignoring that details like handling difficulty seem hard to get right. 20:14 < justanotheruser> gmaxwell: Is there a use for primecoins PoW? No one has been able to explain who wants Cunningham chains 20:15 < gmaxwell> No. There is no use as far as I can tell, except abstract numbertheory navel gazing. 20:15 < gmaxwell> of course, insight comes from unexpected places at times. 20:16 < gmaxwell> plus, I _suspect_ that PoW might be the _only_ really viable way to have truly secure timelock encryption. 20:16 * nsh nods 20:16 < gmaxwell> just because the timelock usage alone could never really fund enough processing power to make it secure. 20:17 < justanotheruser> The problem I see is your secret being worth 3 times as much as the secret rewards meaning your secret is found 4 times as fast as it should have been. 20:17 < gmaxwell> well thats part of the reason I propose encrypting with all intermediate keys. 20:18 < gmaxwell> so the comparison is not one blocks reward, its all rewards between here and now. 20:21 < justanotheruser> hm 20:21 < justanotheruser> gmaxwell: Do you consider any altcoins useful other than namecoin? 20:21 < gmaxwell> You could also strengthen a decenteralized timelock with distributed timelocks. 20:22 < nsh> hmm 20:22 < gmaxwell> justanotheruser: not really so far, mostly they've done absolutely nothing interesting. The few that aren't just copied of the bitcoin code with a few lines changed are mostly either pure marketing and vaporware or are trivially insecure rubbish. 20:23 < andytoshi> i bet a way to find cunningham chains quickly would also yield some useful number-theory results 20:23 < andytoshi> so primecoin will become useful exactly when it's destroyed :) 20:23 < gmaxwell> E.g. To decrypt this message you need all the blocks between now and 2016 and 6 of 10 timelock servers OR all the blocks between now and 2017. 20:24 < justanotheruser> gmaxwell: how do you handle an increasing network power? 20:24 < maaku> justanotheruser: one of many unsolved problems here 20:24 < gmaxwell> hm? no I proposed a solution, but its kludgy. 20:25 < justanotheruser> Or is this the centralized distributed solution with the servers verifying the block time 20:26 < maaku> gmaxwell: it's not on your alt page... 20:26 < maaku> you've got a mechanism for scaling reward 20:26 < justanotheruser> maaku: "POW which turns the distributed computation into ticking for timelock encryption" 20:26 < maaku> but say I want to encrypt something to 2016. how do I know how far to go? 20:27 < gmaxwell> justanotheruser: I suggested running multiple problems. Say your problems are just H("timelock is great"||x||y) = pubkey. and x and y start at 0. When a solution for a given problem is found, y is incremented. 20:27 < maaku> justanotheruser: i'm talking about difficulty adjustment specifically 20:27 < gmaxwell> If difficulty is too low then to solve a block you start requiring work on x=0 and x=1 ... if it's still too low you require work on x=0 and x=1 and x=2 20:27 < maaku> gmaxwell: ah, i misunderstood. so you break each key into multiple problems? 20:27 < justanotheruser> maaku: your concern is it being found faster with higher network hashpower? 20:28 < gmaxwell> and so basically instead of solving one timelock sequence you solve 1 to n time lock sequences, with n depending on difficulty. 20:29 < gmaxwell> you can encrypt your message with as many of the sequences are you believe will exist in the future, but there is some risk if the difficulty is too low that the network is not solving the sequence you need. 20:29 < justanotheruser> gmaxwell: That involves centralization right? 20:29 < gmaxwell> wtf 20:29 < gmaxwell> no 20:29 < gmaxwell> sorry, I'm just confused as to where you'd get that idea! :P 20:29 < justanotheruser> I was confused by "and 6 of 10 timelock servers" 20:30 < gmaxwell> justanotheruser: oh I thought you were talking about me explaining how difficulty adjustment works. 20:30 < gmaxwell> that was just a comment on 17:21 < gmaxwell> You could also strengthen a decenteralized timelock with distributed timelocks. 20:30 < gmaxwell> and yes, its not decenteralized. 20:30 < justanotheruser> I see 20:31 < gmaxwell> But, e.g. decenteralized + distributed OR lots-more-decenteralized doesn't seem too bad to me. 20:31 < maaku> justanotheruser: my concern is that you cannot predict which keys to use to encrypt something such that it won't be release until day X in the future 20:32 < justanotheruser> I don't see how 6 of 10 timelock servers verifying blockchain length to release a secret is different from them verifying the data 20:32 < gmaxwell> maaku: well you can in my example, you just encrypt using x=0 y={0..expected time in the future} 20:32 < gmaxwell> justanotheruser: huh? there is no verifying the blockchain at all. 20:32 < justanotheruser> brb 20:33 < maaku> gmaxwell: but then in the future when people have asic ecdsa crackers for this, difficulty will require each block to iterate x=0..(some very large amount) 20:33 < maaku> but it could just as easily be built to do x=0 y=(0.. some large amount) 20:34 < andytoshi> maaku: presumably they'd not do this, prefering to get the block reward 20:34 < gmaxwell> maaku: yes, correct. Though if they did that they'd not get the block reward. 20:34 < andytoshi> i don't think this is safe against an asic explosion 20:34 < maaku> so they give up 1 block reward in order to destroy entirely the utility of the timelock encryption 20:35 < gmaxwell> maaku: No, because you have the option of also using the higher Xs... but it puts a tradeoff over the risk that the network may not tick for all the work you need in the future. 20:36 < gmaxwell> basically, to use it with perfect security requires you to predict the future difficulty. But it can be constructed so that if you fail to guess right all is not lost. 20:36 < maaku> Which means you might as well just make the network tick with a single appended value, so you guarantee all keys are moved through 20:36 < maaku> Then you can use it to say "I encrypt this until the network expends X computational cycles" 20:37 < gmaxwell> maaku: no, that gives you no control of the time at all. And you _do_ guarentee that all keys are moved through for all levels under the difficulty. 20:37 < maaku> lack of control over tiem is precisly my point... 20:37 < gmaxwell> you can achieve that in the multilevel scheme by threshold encrypting. 20:38 < gmaxwell> basically the multilevel scheme allows you basically freedom between choosing absolute work, and absolute time (but with race ahead risk) 20:39 < gmaxwell> e.g. you can encrypt the problem to X=0 * 1000 or X=0*500 + X=1*500 or X=0*250 + X=1*250 + X=2*250 + X=3*250 ... to achieve absolute work (to whatever degree you wish to approximate it) 20:40 < andytoshi> [unrelated] new optimization of koblitz curve optimization: http://eprint.iacr.org/2012/519 20:41 < maaku> gmaxwell: but presumably you reveal which ones you encrypt against right? (to avoid combinatorial explosion in decrypting) 20:42 < maaku> so someone need only "work ahead" those keys to decrypt 20:42 < gmaxwell> or you can encrypt to X=0 only, and have absolute time but perhaps a race-ahead risk if the difficulty goes way up. Or you can have some guess at future difficulty (e.g. if the system is already on asics, then projecting mooress law or whatever).. or you can use all of these at once. 20:42 < maaku> (and if they're a miner they can later reuse that work for the subsidy) 20:42 < gmaxwell> No, the work can't be reused. 20:42 < gmaxwell> The attempts you make in the cracking are based on the hashes of the prior blocks, or you don't have a consensus. 20:43 < gmaxwell> maaku: But what I described there achieves absolute work ("X=0 * 1000 or X=0*500 + X=1*500 or X=0*250 +"), regardless of the difficulty. You can "race ahead" sure, but there is no faster way than doing a certan absolute amount of work. 20:44 < maaku> gmaxwell: I'm not sure I follow. the public keys are known in advance right? and the problem is to find the private keys right? 20:45 < gmaxwell> maaku: correct. The hash of your header tells you what part of the solution space to check. Finding a block requires proving you checked the right part of the space and found a distinguished point. 20:45 < gmaxwell> (a distinguished point is either the solution to the current problem, or some 'near miss' based on some arbritary criteria) 20:47 < gmaxwell> Wrt the absolute stuff, I was only pointing out that my hierarchical scheme allows you to get any mixture of "absolute work" or "absolute time with race ahead risk (diff overshoot risk)" or "absolute time with failure to decrypt (diff undershot risk)" that you like. It's not perfect, by any means, but I think it could be reasonably successful. 20:49 < gmaxwell> maaku: e.g. forget that there is a faster way of solving ECDLP than just testing secret keys. To mine this you take your header hash and multiply it by the base point and then measure the current solution's hamming distance to the current digits of pi or whatever is the current x=0 target problem. If its below a threshold you have a x=0 solution. 20:50 < gmaxwell> if you raced ahead previously, that work isn't useful to you because the secret keys you checked weren't derrived from hashing a vaid header. 20:50 < gmaxwell> (at least not useful for mining) 20:53 < gmaxwell> andytoshi: that paper is about classical koblitz— which is for characteristic 2 fields. I can't believe people are still doing stuff with characteristic 2 in 2012. 20:54 < andytoshi> oh, damn 20:54 < andytoshi> also it's 2014 :P 20:57 < nsh> let's split the difference for another couple of days eh? :) 21:12 < nsh> *sigh* 21:12 < nsh> https://www.openssl.org/ <-- compromised 21:13 * gmaxwell not going to load a compromised site. 21:13 < nsh> just says "TurkGuvenligiTurkSec Was Here @turkguvenligi + we love openssl _" 21:13 < nsh> no html. but good policy :) 21:17 < justanotheruser> In blockchain time It's already April 2014 21:32 < gmaxwell> So I think I have a goofy convoluted protocol for centeralized timelocking, between alice and a clock though it requires having some substr opcode we don't have. 21:33 < nsh> what's at the centre? 21:33 < gmaxwell> The idea is that alice and the clock can make a (complicted) series of transactions which sets things up so that alice learns a public key for which the clock knows the secret. Alice and the clock both put up funds, if the clock releases the secret on time it gets both its funds back and alices funds. 21:34 < gmaxwell> If the clock releases the secret early, then it doesn't get its funds back. If it doesn't release it alice gets its funds. 21:35 < gmaxwell> the basic idea is that if you give me a signature with a key of yours, and if we had the right opcodes, I could write a scriptpubkey which allowed you to redeem it if and only if you reuse the same k value, thus disclosing the private key. 21:35 < nsh> hmmm 21:36 < gmaxwell> so then you setup a complicated sequence of timelocked n of m fiddly transactions so that there are three ways the thing can be released... early— and the funds can only go to fee or alice.. ontime the funds go to the clock, or late and the funds go to alice. 21:40 < gmaxwell> I dunno if it would be useful though, esp I don't know how to prevent people from freeloading. E.g. alice publishes the initial signature and now any number of people can use that timelock 21:42 < nsh> i'm not sure that's too much of a problem, necessarily 21:45 < gmaxwell> well, if the bitcoin incentives are to have any point at all they should be fairly large... and it's not reasonable to ask clock to lock up funds for a long time without a considerable return. the more people who use it without paying the more incentive for clock to make a deal with someone and never disclose or disclose early. 21:47 < gmaxwell> how about a different one, how about a semi-anonymous quorum timelock. 21:48 < gmaxwell> N players have a distributed public private key. The private key is split into polynomial shares such that— say— 50% of them are required to recover the private key. 21:49 < nsh> right 21:49 < gmaxwell> over time, some M of the N player drop out— they vanish without any of the other playeryers hearing from them for a while, and so they do some quourum consensus and decide those M players are defunct. 21:50 < gmaxwell> They invite M new players, and do some protocol needing 50% of the original N to update help the new M players recover the shares of the M that left. 21:51 < gmaxwell> ignoring how you'd go about doing that— how would this break down? 21:52 < nsh> i think i'm lost 21:53 < warren> http://www.openssl.org/ <--- sigh 21:53 < gmaxwell> nsh: well you get how you can have a key shared among many people such that you need a majorty? You can do this in ec groups such that there doesn't need to be any trusted dealer. 21:53 < nsh> sure 21:53 < maaku> if you love openssl you wouldn't do that... 21:54 < gmaxwell> nsh: just information theoretically, if M of the N leave, but M (maybe they love openssl, but not as much as fleeting noteriety in dubious social circles) 21:55 < nsh> gmaxwell, can they repopulate without revelaing the secret itself though? 21:55 < nsh> that seems less obvious 21:55 < gmaxwell> (after all, they could just recover the whole key and than split it up again) 21:55 < nsh> depends on the sharing scheme i guess 21:56 < gmaxwell> nsh: Yea, I haven't figured out how to do it, I'm pretty sure it can be done though. Just assume they can for the moment— it's pointless if the scheme isn't useful regardless of doing that. 21:56 < nsh> okay 21:56 < maaku> nsh: probably helps them get their next job. i've heard that some major art thefts are only to enable the theives to get "in" to an organization 21:56 < gmaxwell> nsh: or actually I'm completely sure it can be done, I don't know how easy it is to do it. 21:56 * nsh nods 21:57 < gmaxwell> nsh: I'm completely sure because the remaining N-M plus new M could use secure multiparty computation to secretly regenerate the whole key and then split it back up and give it to the new N users. 21:57 < nsh> yes, that makes sense 21:57 < gmaxwell> Though I also think its likely that there is a less horriffic way than invoking SMPC. 21:57 < nsh> modulo some computational/bandwidth costs 21:57 * nsh nods 21:58 < gmaxwell> seems to me that you could get a pretty darn robust timelock this way. 21:58 < gmaxwell> you just need some sybil resistant way to select players. 21:59 < nsh> i'm missing bits still. how do you go from N of M secrets (with dropouts and repopulation) to timelock? 21:59 < gmaxwell> And then you can do {magic} to continually redistribute the key so that people coming and going don't break you. 21:59 < gmaxwell> oh just as the "rules of the system" the N parties agree that once the time passes they'll all publish their keys. 21:59 < nsh> backed by fidelity bonds? 22:00 < gmaxwell> So it's secure so long as the majority follows the rule. But systems like that often aren't pratical because they don't handle the members changing over time. 22:00 < nsh> hmmm. i don't know how easy it would be to find N people who would reliably publish on schedule 22:01 < gmaxwell> nsh: maybe? or love for their commnuity. It's not like this is an expensive operation. Generally the reason I think majority of N systems are not pratical isn't that you can't trust the majority for most things you'd want, but because of membership complications. 22:01 < gmaxwell> nsh: well its not people, of course, it's people's software. :P 22:01 < nsh> sure :) 22:02 < nsh> i think you could set up an adaptive cracking challenge via a set of clues running on daemons spread about place such that the Nth clue is published encrypted with a puzzle of difficulty chosen on the basis of how quickly the N-1th puzzle was cracked 22:02 < gmaxwell> e.g. you could do this very simply, with all of us here.. but a year from now many of us may have moved on, gotten hit by bussess, become pissed off at the group. And a bunch of new people would have arrived. Maybe N/2 is unfindable a year or two from now. or you just barely have N/2 still standing, and a few people decide to hold the group randsom. 22:03 < nsh> the general principle of "topping up" the multiparty pool seems a pretty useful one 22:04 < gmaxwell> and this isn't just wank, you could use something like this to enable p2pool to hold a abalance. e.g. have a private key escrowed to the p2pool hashrate, and keep "topping up". 22:04 < nsh> but perhaps open to sneaky people who (being coerced to) fake absence until a threshold is reached 22:05 < nsh> it might be possible to modulate each share when topping up such that people who have dropped out are no longer able to partake in revealing 22:05 < gmaxwell> sure, well one thing about the SMPC approch to it is that you could totally redo everyone's shares. The original interpolation way I was thinking about this was vulnerable to people "leaving" in ordre to come back and get someone elses share. 22:05 < nsh> right 22:06 < gmaxwell> yea, you could achieve that at least under the SMPC case... where you have no risk of an incremental break as the shares are just unrelated. (e.g. you have an encrypted secret which is shared, and inside the smpc you reencrypt, so the shares are unrelated) 22:06 < nsh> right 22:07 < gmaxwell> I guess one problem is being at all confident that "there is anything in the box". 22:08 < gmaxwell> e.g. a bunch of jokers begin such a system with an encryption of nothing, but promising it is the key to great riches. And they all gradually leave, selling their share in the pot to other people. 22:08 < nsh> heh, sounds like religion 22:08 < nsh> :) 22:09 < gmaxwell> but I guess that too isn't bad in the SMPC model, since the SMPC could just produce a proof of knowledge (E.g. signature) as a side effect at every remix. 22:09 < gmaxwell> ohhh I found a problem. 22:09 < gmaxwell> A old majority could fork a past state. 22:09 < nsh> (there was a schoolboy prank where you'd get a bunch of people to stand at the corner of a tall problem and all point up and look excited. then wait for more people to arrive until it was sustained enough for the original pranksters to wander off) 22:09 < nsh> fork? 22:10 < nsh> s/problem/building/ # heh.. 22:10 < gmaxwell> e.g. people leave the system until none of the original players are left. The one day the original players meet up and go, "oh I wish we still controlled that key" ... "But wait! I saved my old share, if we all did!" 22:11 < nsh> ah, right 22:11 < gmaxwell> so that would bugger the timelock case where you can't usefully rotate the keys as topups happen. 22:11 < nsh> well, there's no way around that i can think of that doesn't require a T3rdP 22:12 < gmaxwell> but it wouldn't hurt the p2pool "keeps a balance" case, since the pool could just keep moving the funds. (e.g. the bitcoin network is the trusted third party) 22:12 < nsh> right 22:12 < nsh> i think ways of using the bitcoin network as a trusted third party will be a pretty big area of research in future 22:12 < gmaxwell> and tada, if we had scalable threshold signatures in bitcoin we wouldn't need anything else for the p2pool case. 22:13 < gmaxwell> you take your N p2pool hashes (selected by their shares in the p2pool sharechain), and you assign funds to them... then late a largely overlapping new N are selected, and the they generate a new threshold key, and the old N move the funds to the new threshold key. 22:13 < nsh> (are there any threads/mailpost/notes on scalable threshold signatures?) 22:14 < gmaxwell> nsh: they're straightforward if you use schnorr instead of DSA, or so says adam3us— I've not personally implemented. At least the N of N case is obvious enough. 22:14 < gmaxwell> basically for the N of N you can just directly compose the public keys.. and to sign directly compose the signatures. 22:15 < nsh> mmm, right 22:15 < gmaxwell> The N of M works based on schnorr basically testing a linear relation, but I've not actually worked through how it works. 22:16 < gmaxwell> lack of scalable threshold signatures I think is a major shortcoming in bitcoin, probably the script limitation with the greatest impact on other protocols. 22:16 < nsh> hmmm 22:16 < gmaxwell> esp because other limitations you can generally work around by invoking multisig. 22:17 < gmaxwell> e.g. how coinswap makes any complicated protocol look like a multisig. :P 22:17 < nsh> assuming schnorr sigs allow for M-of-N, could you add the functionality via a new OP without changing out ECDSA completely? 22:17 < gmaxwell> correct. 22:17 < nsh> right 22:17 < nsh> we definitely need to have a script-extension playground 22:17 < gmaxwell> it's a little tricky to make it backwards compatible. you just can't add a OP_NEWCHECKSIG 22:17 < nsh> that would be very useufl 22:18 < gmaxwell> e.g. it would need to be somehting like a P2SH style change. 22:18 < nsh> what does P2SH style mean? 22:19 < nsh> a generalization of payability? 22:19 < gmaxwell> the reason you can't just take one of the existing NO_OP opcodes and make it into a OP_NEWCHECKSIG is that I could write a transaction that did OP_NEWCHECKSIG OP_NOT OP_VERIFY. 22:19 < gmaxwell> e.g. this transaction is only valid if the newsignature fails. 22:20 < nsh> hmm, and this shoots other places than your (transaction sender's) own foot? 22:20 < gmaxwell> what I mean by p2sh style is that the whole _new syntax_ script is completely hidden from old nodes, they just see a boring hashlocked transaction. 22:21 < nsh> oh, i see 22:21 < gmaxwell> nsh: yea, if OP_NEWCHECKSIG looks like OP_TRUE to old nodes, then I could author a transaction which new nodes would accept but old nodes would reject, and that forks the network. 22:21 < gmaxwell> but no biggie, just hide the whole new script from old nodes completely. 22:21 * nsh nods 22:22 < nsh> so it's as solved as backwards compatible P2SH, at least 22:22 < gmaxwell> though I don't know if any future script extensions are realisitc at all. There are now several actually functional full node implementations, whos going to make those people implement any particular change? 22:24 < nsh> hmm 22:25 < nsh> there should be families of end-to-end functionality for which it doesn't matter if there exist nodes that are blind to the internals maybe 22:26 < nsh> it's not a problem for using P2SH if older nodes don't recognize them? 22:26 * nsh needs to read more about the proposals 22:32 < andytoshi> P2SH uses the same set of opcodes that have always been around 22:32 < andytoshi> older nodes might think they're nonstandard, but they'll just not relay them 22:34 < nsh> hmm 22:35 < gmaxwell> andytoshi: older nodes don't even _see_ the interior script opcodes. 22:35 < gmaxwell> They just see some binary data on the stack. 22:36 < nsh> what i meant was, if we can implement p2sh without unduly worrying about old nodes, shouldn't the same logic hold for implementing threshhold sigs? 22:37 < gmaxwell> only if it were implemented in the same way. 22:37 < nsh> right, so only people who want the new functionality are required to run nodes implementing it 22:37 * nsh nods 22:37 < gmaxwell> no. ugh 22:37 < nsh> oh 22:37 < gmaxwell> none of these changes are secure unless at least a majority of hashpower enforces them. 22:37 < nsh> ah 22:38 < nsh> right, sorry. 22:38 < nsh> so the concern is that at some point changes to the reference client might not necessarily lead to 50(+whatever)% hashpower realization 22:39 < gmaxwell> the trickyness in deployment is that if its not done carefully you can end up where the new feature creates a fatal forking bug even if 90% of the hashpower deploys. P2SH shows one way to do it safely. 22:39 < nsh> although there was some talk about disentangling validation from mining the other day... 22:39 < gmaxwell> nsh: I don't even know what you mean there, it's already quite disentangled. 22:39 < nsh> neither do i, never mind... :) 22:39 < gmaxwell> Most "miners" have never participated in validation. :( 22:40 < nsh> i can't remember exactly what was said such that i took that away from it. was probably not paying much attention 22:40 < gmaxwell> in any case, it's not just hashpower. lets say 80% of hashpower were to have deployed p2sh, but most full nodes don't. 22:41 < gmaxwell> that means that later some super majority of the miners might go "hey, lol, we could make a lot more if we rob all those suckers using p2sh and assign all their coins to us" 22:41 < gmaxwell> e.g. if ~everyone doesn't eventually deploy the new rule it leaves the mining incentives potentially out of wack. 22:42 < gmaxwell> a majority of hashpower is necessary for the new thing to be safe, but it's not really sufficient. 22:42 < nsh> hmmm 22:42 < nsh> i'd love if some student made pretty diagrams illustrating all these things graphically for a thesis or something --- Log closed Sun Dec 29 00:00:36 2013