00:01:28andytoshi:cool, all good
00:06:50gmaxwell:andytoshi: cool. it works, you might want to put both links on the bottom of the page.
00:11:48andytoshi:now i'll go spam anontalk with it..
00:12:01gmaxwell:Whats anontalk?
00:12:27andytoshi:i don't think that's what it's called .. there used to be an anonymous board at http://ci3hn2uzjw2wby3z.onion/
00:12:38andytoshi:maybe it has gone down
00:13:38gmaxwell:I guess the next missing piece for your tool is an auto-participater. e.g. something that polls periodically and if there is a open CJ of the right size, it participates for you.
00:15:54sipa:TD: what timezone are you in? :)
00:17:21TD:sipa: why?
00:18:28sipa:not used to seeing you join at this time :)
00:18:47andytoshi:gmaxwell: yeah, that'd be cool
00:19:07andytoshi:right now i'm working on having any coinjoins going on, when i'm not 50% of the participants
00:20:09gmaxwell:andytoshi: yea well part of the challenge, of course, is that when someone uses it there may be no one else, or /worse/ just someone with a non-match that doesn't really increase their privacy.
00:29:08andytoshi:yeah, that happened to my this morning..
00:29:10andytoshi:;;cjs c11fc9bd5b462946
00:29:11gribble:Coinjoin Status: session ``AMEMB Lanceros PFS Sex Tess IDB 15kg'' is completed. The submitted transaction ID was 80819213bb25df35f890fab55f8d3b71c8f5bed3b823bb949ce26e1471686e61.
00:29:36andytoshi:https://blockchain.info/tx/80819213bb25df35f890fab55f8d3b71c8f5bed3b823bb949ce26e1471686e61 i was the 0.2's
00:29:52andytoshi:it clearly said, "most popular output is 0.2. use that output size"
00:32:38gmaxwell:might be better if the person starting a join could mandate a size?
00:34:22andytoshi:maybe, i dunno, i don't want to make it too irritating .. i am already disappointed by the ~0 uptake
00:35:30gmaxwell:andytoshi: yea, sorry about that. I could have warned you. See also the ~0 uptake in PT's dust-be-gone.
00:37:13andytoshi:lol, s'fine, i learned a lot from this
00:37:29andytoshi:and i found a bug in the rust compiler, so my github account claims i have "contributed" to rust, which is cool
00:40:56gmaxwell:My expirence with dust-b-gone suggests that even with an automated participater the usage will be low. I'm not sure what it takes to get it used.
00:41:15andytoshi:calling it doge <.<
00:41:33gmaxwell:I ... worry... that there are basically few actual cryptocurrency people in Bitcoin.
00:42:28sipa:is there anything coinjoin-related already usable/released?
00:42:38sipa:* sipa has hardly followed up recently...
00:43:28andytoshi:i worry about this too, but then i remember that there are like 30-40 serious people here, and we are able to connect on #bitcoin-wizards and exchange research in a way that would've been impossible even 10 years ago, even if we'd had bitcoin back then
00:43:57andytoshi:well, irc was around 10 years ago, but i don't think the preprint archives were, nor do i think academics spent a lot of time on public forums
00:44:32andytoshi:sipa: i have a joiner at http://xnpjsvp7crbzlj3w.onion/ which is "usable" if you can deal with rawtx's
00:46:23andytoshi:one of maaku's 17 million projects is an automatic p2p joiner
00:46:53andytoshi:but idk if that's usable right now
00:48:03sipa:well, i don't think you can't expect any measurable uptake without any serious wallet application having integration or even automatic using it
00:49:56pigeons:are the sessions submitted at https://www.wpsoftware.net/coinjoin/ shared with http://xnpjsvp7crbzlj3w.onion/ ?
00:51:07pigeons:since there is such low usage i would want to submit to the one that gets the higher chance of someone else submitting a transaction if not
00:51:11andytoshi:pigeons: yes, they are the same site
00:51:34andytoshi:the .onion gets routed to the wpsoftware.net one at my tor node
00:52:08andytoshi:(and the webserver is on the same hardware as my tor node)
00:53:33maaku:andytoshi: haha yeah i got way too much going on right now
00:54:10maaku:i need to focus on finishing just one of them
00:54:46maaku:i'm reworking the protocol messages to include multiple bucket sizes and explicit fees
00:55:03maaku:but that stalled while i was working on the utxo validation index bips
00:55:57maaku:i'm going to work the python proof-of-concept to the point where you can do joins from the command line
00:56:09maaku:and I got an offer from someone else to handle the messaging via bitmessage + tor
00:56:33maaku:but after that, I'd rather see it reworked into C++ and integrated into (a fork of) the reference client directly
00:56:35andytoshi:oh, nice
00:59:53maaku:i'm hoping that the work i'm doing will be the foundation of a future protocol extension everyone uses
01:00:00maaku:but i have no illusions of it happening quickly :)
01:09:11pigeons:if i send you btc isn't that 100% profit for you rather than 50%?
01:09:14sipa:who has op here?
01:13:01nsh:gmaxwell has done all the +b that i've seen
01:13:49gmaxwell:gmaxwell has kicked nOgAn0o from #bitcoin-wizards
01:19:26gmaxwell:I was the only +o in here, but I've now added +o to petertodd amiller adam3us sipa warren maaku jgarzik Luke-Jr (top talkers in here)
01:19:53maaku:* maaku fantasy power trips
01:25:44gmaxwell:andytoshi: you might want to make the there is no current messages include a "Go to https:// to start one."
01:28:10andytoshi:oh, hey, that's a great idea
01:29:00andytoshi:there we go
01:29:11andytoshi:(i'm going to do all my testing on #bitcoin from now on for advertising purposes)
01:29:51andytoshi:so far i've netted -0.0006btc on this joiner, by participating in pretty-much every join :P
01:31:04nsh:ballads will be sung for generations to come of your entrepreneurial acumen :)
02:08:35Luke-Jr:andytoshi: what testing? #bitcoin is explicitly non-logged FYI
02:10:35andytoshi:Luke-Jr: coinjoin
02:10:41andytoshi:log testing i do on #andytoshi :P
02:10:56andytoshi:but thx for the heads up
03:34:28gmaxwell:T-25 minutes for andytoshi's coinjoin. Time to prep your transactions if you're joining.
03:34:58andytoshi:0.5 btc outputs
03:35:03andytoshi:i guess i should prep mine..
04:01:36gmaxwell:;;balance 1ForFeesAndDonationsSpendHerdtWbWy
04:03:01andytoshi:does anyone know who did that?
04:03:46nsh:* nsh is confused
04:04:18gmaxwell:told you that you should have made it a spendable address!
04:04:39gribble:Coinjoin Status: current session is open for 16 more minutes. There are currently 3 transactions in the pot. The most popular output value is 0.5.
04:06:09nsh:what's the current 'accessibility' of coinjoin?
04:06:33gmaxwell:andytoshi: ^ that should probably say max(count(most_popular),ntransactions) to avoid disclosing the number of players when it wouldn't be obvious from the inputs.
04:06:48gmaxwell:nsh: you can use andy's thing if you can spend via a raw transaction.
04:07:04gmaxwell:It's actually slightly safer than a normal raw transaction, since it prevents to common all coins to fees failure mode.
04:07:44nsh:how hard would it be to let any-random-noob perform the rawtx spend safely?
04:08:14nsh:(i assume it would be better for privacy is the barrier-to-entry for coinjoin was as low as possible)
04:08:56nsh:or bc.i users can do it now?
04:09:03gmaxwell:nsh: yea, ultimately there needs to be dumb wallet integrated tools. But getting there requires more expirence with the technology, so tools like andy's n00b unfriendly one are a stepping stone.
04:09:31gmaxwell:nsh: bc.i has something they're calling "coinjoin" which is really only kinda coinjoin. As it depends on you trusting bc.i to do the right thing.
04:09:36nsh:(wasn't being critical in any way, just wondering how to increase the utility)
04:09:53nsh:but i guess not trusting bc.i much more than people already do?
04:10:16gmaxwell:(really part of the premise I had in promoting this style of txn is that we can't really get wide adoption if its predicated on additional trust, because the trust is a cost too)
04:10:32nsh:* nsh nods
04:10:38gmaxwell:yea, if you're already using Bc.i you're already exposed, it's not really too much worse.
04:11:39andytoshi:gmaxwell: what should the display say if i'm actually publishing max(count(most_popular),ntransactions) ?
04:11:46andytoshi:"there are something like 3 transactions in the pot"
04:12:52gmaxwell:andytoshi: "there are ~N transactions in the pot"
04:13:09nsh:the awesome liability-reducing power of the tilde
04:28:00andytoshi:holy shit, these cj's get confirmed fast
04:28:09andytoshi:less than a minute this time
04:29:36nsh:there's good marketing for you :) "want faster confirmations *AND* increased privacy? use coinjoin!"
04:29:37gmaxwell:andytoshi: I guess you should share a link to the txn in #bitcoin — worse the slight loss in privacy to show people that its real.
04:30:09nsh:(just add a tilde if it's not actually faster on average)
04:31:20andytoshi:i've got to jack up the fees required fee tho, that time the fee was 0.00035786
04:31:49andytoshi:and i only demanded 0.00024 from people, so it's possible that i wound up paying most of that myself
04:33:11nsh:charge slightly over the odds and disburse the difference as a faucet or something
04:33:34gmaxwell:andytoshi: set fees to whatever sane value you think they need to bet to get people to use it, I'll pay you out of the CJ bounty fund (or, if the other signers don't agree, out of my own pocket) later.
04:34:10nsh:* nsh nods
04:35:09andytoshi:well, i'm not too concerned about the personal loss, but rather what happens when i'm not involved with a join
04:35:19andytoshi:i suppose i could attach a faucet..
04:36:50andytoshi:right now, the only person outside of this channel i've heard comment on the fees said they were "practically nothing"
04:37:14gmaxwell:really the problem with the fees is that they dork up going from round valued outputs to round valued outputs.
04:37:36andytoshi:yeah, that's really irritating
04:37:58nsh:could you have a dummy input and output in every join that soaks up the fee, ehm, jaggedness?
04:38:23nsh:(from some holding wallet run as part of the service)
04:38:35nsh:no, that doesn't make sense
04:38:38gmaxwell:right. :P
04:38:45nsh:shh, it's late
04:39:23gmaxwell:andytoshi: could do that if he basically gave people fee tokens. e.g. send in some coin to andy and he gives you a fee token, and then you can use that in multiple txn to pay your fees (meaning andy just pays them). But it's a lot of complexity— too much for a simple manual process.
04:39:29andytoshi:well, if it was always us, i could do something like that, since i trust that people here would pay up if i asked
04:39:42nsh:* nsh nods
04:39:45andytoshi:i definitely don't want to add complexit
04:39:54nsh:you even simplified the word!
04:40:04andytoshi:for now i bumped the fee up from 8000 to 10000 satoshi, since that's rounder ;)
04:40:06gmaxwell:yea, but I suspect we'll not learn more if it's just us. What I think we should try doing is these daily ones for a few days and see if we get any more players.
04:40:19andytoshi:and in this case, we would have paid the minimum network fee even if everyone had only given 10k sat
04:40:43nsh:i wonder if you could make it a wee bit "gamier" to entice people
04:41:12nsh:(not quite gambling, but some chance element that adds 'fun')
04:41:26andytoshi:it's tough without increasing complexity .. i could do something like give all the donations to a random participant
04:41:36andytoshi:but then they'd have to provide an additional address alongside the rawtx
04:41:48gmaxwell:well and then you'll un round one of my pretty round coins. you bastard. :P
04:41:57nsh:but can that be done without trusting that you aren't getting backhanders to pick certain people to win?
04:42:09andytoshi:nsh: lol nope
04:42:11gmaxwell:nsh: not without making it more complex.
04:42:14nsh:is there a way to add some randomness to dispersal in script
04:42:24nsh:i thought there was an OP that gave a random bit...
04:42:34nsh:as an artefact of something or other
04:42:36gmaxwell:there isn't but there are ways to do that but not without making it more complex.
04:43:00gmaxwell:part of the point is that these txn should be generally indistinguishable from ordinary ones— except perhaps that they have many equally sized outputs.
04:43:10nsh:* nsh nods
04:43:26gmaxwell:so that they're hard to exclude from tracing tools, and if a tracing tool starts excluding them, it'll be easy to make 'fake' CJ transactions.
04:43:47nsh:hmm, how would that help?
04:44:37andytoshi:(if NSA excluding these from analysis, then you can get all your ordinary transactions excluded just by spending to several outputs -- then you win)
04:44:53gmaxwell:nsh: because even without participating in an actual CJ you can form a txn all by yourself that looks like one (a bunch of equal sized outputs) and then various automatic deanonymization methods would hit it and fire of their CJ huresitic and give up.
04:45:00gmaxwell:yea, as andytoshi says.
04:45:29nsh:though in practice it might rather go as "okay all of these guys are definite terrorists. *dronestrike*"
04:45:37gmaxwell:well different threat model.
04:45:42nsh:* nsh nods
04:46:03gmaxwell:Either dumb web tools that automatically trace coins frequently gives BS results from CJs in which case they're easily debunked and few trust them... or they ignore CJs and you just make some fake ones and basically opt out of their tracing. win win.
04:46:12gmaxwell:NSA .. I can't help you with. You're probably screwed. :P
04:46:18andytoshi:if SR were still up i'd be sending all the donations there :P
04:46:28gmaxwell:andytoshi: you could send them to the FBI. :P
04:46:46nsh:people are still "sending" money to that addresss...
04:46:57nsh:but that's another subject
04:47:10gmaxwell:whatever jackass hacked john dillon sent a bunch of btc there that he'd sent me in a private key for the CJ fund. :(
04:47:52nsh:sucks :(
04:54:41andytoshi:ok, i tried doing the max(unsigned tx count, mpo count) thing
04:54:47andytoshi:we'll know in a minute or so if it worked..
04:54:56gmaxwell:andytoshi: perhaps the count should actually be min(distinct_in_addresses,max(ntransactions,n_most_pop_outputs)) .. otherwise on this one it would have displayed 10 which was clearly impossible vs 9 which is at least more credible.
04:55:47gmaxwell:I suppose there really should be some maximum_credible_amount which does some value analysis.
04:57:24andytoshi:the point of this display is to give people a swag of their anonymity
04:58:10gmaxwell:right, but e.g. if I submit to you a txn that itself looks like a coinjoin, e.g. two addresses each with enough to form a uniform output, the display shouldn't leak that.
04:58:46andytoshi:ah, i see
04:59:30gmaxwell:maybe it should work from a pure analysis of the transaction submitted so far, just some metric some attacker might use to guess the participants.
04:59:47andytoshi:i think i'll modify coinjoin to calculate how many participants it thinks its merging
05:00:01andytoshi:"maximum plausible participants"
05:00:36gmaxwell:I wonder if this is some crazy maximal matching problem.
05:01:20andytoshi:yeah, i'll get some paper and see what happens :P
05:01:30andytoshi:i haven't thought about this in any detail up to now
05:08:05andytoshi:ok, i've translated this into a graph theory problem, i'll type it up and post it
05:08:19andytoshi:it's actually pretty neat, maybe it's something well-known
05:15:15gmaxwell:* gmaxwell waits for the max-flow problem
05:16:32andytoshi: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
05:16:47andytoshi:with the edgeset satisfying a bunch of conditions
05:21:49andytoshi:does this look right?: http://download.wpsoftware.net/bitcoin/coinjoin.pdf
05:22:03andytoshi:sorry, it took me forever to find a latex template..
05:24:21gmaxwell:andytoshi: 2.1 is incorrect. You could have a fee only input.
05:24:37gmaxwell:oh nevermind misread
05:24:50gmaxwell:2.1 is just that the graph is biparte.
05:25:02andytoshi:that's right, i knew there was a word for that..
05:25:26andytoshi:but i do fix the input and output sets, and i want to ensure these are the same across every plausible join
05:25:32andytoshi:so i'm not sure how best to say that
05:29:22andytoshi:so, my hunch at this point is that "sort the inputs and outputs somehow then match greedily" will provably give the best plausible join
05:29:33andytoshi:based on, that is how literally every school graph theory problem goes
05:30:18gmaxwell:I'm trying to figure out how to refactor this into finding a maximal cut.
05:36:09gmaxwell:I don't think the greedy solution works.
05:37:14gmaxwell: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.
05:38:12nsh:greedy doesn't work so well when you have inequalities, i'd guess
05:42:53gmaxwell:andytoshi: hitting set problem
05:56:33andytoshi:oh thx, i'll look that up
06:00:43andytoshi: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
06:00:57andytoshi:here a want a cover by the greatest number of disjoint subsets of inputs
06:01:21gmaxwell:yea.. :-/
06:01:39BlueMatt:who would be interested in getting a -wizards meetup together at some point in the late march/early april timeframe?
06:02:16andytoshi:BlueMatt: i will know in a week or two what my midterm schedule looks like, but i'd be down
06:03:16andytoshi:i also don't think a greedy algorithm works, this problem does not quite have the right structure
06:03:37gmaxwell:andytoshi: amusingly even that little transaction from tonight is intractable if evaluated via a maximally dumb algorithim that selects all solutions.
06:04:03andytoshi:cool, do you know how many tests would need to be done?
06:04:30gmaxwell:e.g. there are 9*13=117 edges in the graph, so 2^117. (9 because I merged the dupe address inputs)
06:04:50warren:BlueMatt: will there be a minimum bar of entry?
06:05:10BlueMatt:warren: well, I'll be there, so the bar is set pretty low
06:05:16BlueMatt:in other words...lurkers welcome
06:05:16andytoshi:i think "no floating outputs" is a reasonable assumption, so 117 is a bit high
06:05:30andytoshi:but not by much
06:05:33warren:BlueMatt: what would goals be there?
06:06:35BlueMatt:warren: get together, discuss -wizards concepts in person (with whiteboards...), and personally, I'd like to see discussion of moving more things towards implementation
06:06:43andytoshi: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
06:06:59andytoshi:i was distracted and i trust my joiner, so i just signed what came out without looking at whose outputs are whose
06:07:12gmaxwell: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.
06:07:46andytoshi: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
06:07:49gmaxwell: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.
06:08:46gmaxwell: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.
06:09:05andytoshi:yeah, for example, can we assume every component is a complete bipartite graph?
06:09:38andytoshi:yes: that doesn't affect any of the three plausible join conditions
06:10:03andytoshi:awesome, that feels like a big simplification
06:15:29gmaxwell: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
06:16:06gmaxwell:there, I made is 7e13 times faster.
06:17:06andytoshi:yeah, that's about where i am
06:17:33andytoshi:but maybe there is a smarter way to match up partitions of inputs and partitions of outputs (?)
06:19:24andytoshi:is that the right number for 'partitionings of inputs' tho? don't you want http://oeis.org/search?q=partition ?
06:21:01gmaxwell:they're ordered. So it's just like sticking a edge between each vertex whic is either cut or not.
06:21:21andytoshi:oh, yeah, i see
06:21:53andytoshi:right, i definitely don't want integer partitions, those compensate for overcountings which are completly unrelated to this
06:22:39gmaxwell:well the permute/partition is wasteful, since we don't care about orders within the partitions.
06:23:35gmaxwell:which might just be the partition numbers /me thinks
06:23:56andytoshi:yeah, sounds like it, i think that's what set me looking at partition numbers in the first place
06:24:20andytoshi:but i wasn't explicitly thinking about permutations, so when you brought them up i confused myself
06:26:29andytoshi: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
06:26:42andytoshi:call the number of output partitions O_n, the number of input partitions I_n
06:26:58andytoshi:then the number of plausible joins with n participants is at most O_n*I_n
06:27:12andytoshi:so we can reduce the space to sum_n O_nI_n
06:27:37andytoshi:which is ugly to write, but probably easy to compute, and might even be tractable
06:28:05gmaxwell:numbpart(13)*numbpart(9) = 3030
06:28:43andytoshi:that gives us an upper bound on the sum, right?
06:29:52andytoshi: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
06:33:17andytoshi: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
06:33:44gmaxwell:there is probably some trivial greedy preprocessing that can be done.
06:34:03gmaxwell:Obviously you should merge all inputs with the same scriptpubkey and all outputs with the same scriptpubkey.
06:34:41gmaxwell:and force any input/output pair with the same scripubkey to be connected, perhaps, (e.g. just remove the output and deduct the input)
06:35:08andytoshi:oh, this is true .. coinjoin already merges outputs, but it doesn't have knowledge of the inputs
06:35:51gmaxwell:well your coinjoin does, but of course I was thinking in terms of an abstract tool that could be run on any transaction.
06:36:11CodeShark:are we talking generalized coin selection optimization?
06:36:23gmaxwell:then there may be other outputs which are forced which I think can be found in a greedy way.
06:36:56CodeShark:or is this some specific problem?
06:37:22andytoshi:CodeShark: we are looking at "given some transaction, what is the maximum possible number of participants?"
06:37:25gmaxwell:CodeShark: no, talking about taking a transaction and identifying the maximum number of coinjoin participants under reasonable constraints.
06:37:43gmaxwell:(reasonable constraints like the CJ participants not giving away their money)
06:38:42gmaxwell:CodeShark: e.g. what is the largest plausable number of participants in this transaction: https://blockchain.info/tx/a0350aa856b77edeaa08ae9df5047855d487c40490d11713461d200ea70b09c6
06:39:37CodeShark:so the minimum is obviously one, the maximum is the number of inputs with distinct redeemscripts, yes?
06:40:22andytoshi:well, if there are fewer outputs than inputs, then the total number of outputs could be the maximum
06:40:40gmaxwell: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)
06:41:20CodeShark:ok, so maximum = min(distinct input scripts, output scripts)
06:41:38gmaxwell:nah, because if you constrain them to not throw away values you must look at the values.
06:42:03andytoshi:no, there still might not be a plausible flow .. eg if there are 10 inputs and 10 outputs
06:42:04gmaxwell:Say you have 50,.5,.5 in and 25,25,1 out.
06:42:21andytoshi:and one input is massive, all the others are 0.1, and every output is 0.2
06:42:40gmaxwell:In that case you have a maximum of 2.
06:42:56CodeShark:right, my bounds were very weak
06:43:30gmaxwell:yea, you're giving loose bounds, we want the tight maximum bound. As its a measure of privacy the coinjoin provides.
06:43:55andytoshi:it would be nice if 1 wasn't always plausible :)
06:44:06andytoshi:even a lower bound would be useful if it was nontrivial
06:44:13CodeShark:what if we simply required all inputs to be the same value? then each participant would first have to create outputs of specific denominations
06:44:32CodeShark:and join a transaction of a particular denomination
06:44:45gmaxwell:1 being plausable is good because its also what makes ordinary txn look potentially like CJs. :P
06:44:55CodeShark:yeah, ok :)
06:45:41andytoshi: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
06:46:09gmaxwell:andytoshi: hm. interestingly, I think the maximal maximal count may not always have the highest entropy!
06:46:11andytoshi:and then you've even got free association information from the homogeonizing transactions
06:46:45andytoshi:gmaxwell: that is interesting, and that feeling is why i don't think we can do this 100% greedily
06:46:57andytoshi:but for me, for now, it is just a feeling ..
06:48:09CodeShark:I'm not even entirely clear on coin selection optimization within a single wallet, let alone coinjoin :p
06:48:58andytoshi:well, coin selection (to evade this analysis) is an even harder problem, i think
06:49:11CodeShark:if we want coinjoin to be obscure, we want it to mimic typical coin selection strategies for common wallets
06:49:35gmaxwell:can't— goals are to different, instead wallets should mimic coinjoins. :)
06:49:58gmaxwell:coinjoins can't be fully obscure simply because >2 outputs are rare.
06:51:08CodeShark:yeah, true - and while there's a good use case for sendmany from servers, for typical interactive users, these use cases are more rare
06:52:34gmaxwell: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
06:53:05andytoshi:oh, fascinating
06:53:14andytoshi:what on earth can we say about that?
06:53:23andytoshi:about its anonymity*
06:54:44gmaxwell: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).
06:55:26gmaxwell:e.g. 50,.5,.5 in and 25,25,1 out has an entropy of 1 bit.
06:55:33ghtdak:ghtdak has left #bitcoin-wizards
06:55:34andytoshi:hmm, if that is the most useful metric than it saves us the trouble of doing all this optimization
06:56:06gmaxwell:I dunno that it does, because you still have to reject impluausable mappings.
06:56:10ghtdak:ghtdak has left #bitcoin-wizards
06:56:44andytoshi:if we loop over every possible mapping, that's easy, just a bunch of addition
06:57:16gmaxwell:Finding the maximum N is just a subset of the problem.. it's just the highest N for which there remain any plausable mappings.
06:58:07andytoshi:yeah, but we can use a weak upper bound for N in this case
06:59:05andytoshi:i wonder if we want to compute something sharper: the entropy of the individual outputs
06:59:37andytoshi:(it's really not clear to me how to define that)
07:00:31gmaxwell:the interesting thing about output entropy is that it's not independant.
07:01:36gmaxwell:e.g. output X could have come from input 2 if and only if output Y didn't.
07:02:48andytoshi:we can arrange these possibilities in a giant decision tree, and compute some sort of entropy on that..
07:03:22andytoshi:there is also something called mutual information
07:03:31gmaxwell: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.
07:04:24gmaxwell:andytoshi: I'm trying to come up with a "conservative" version of it which isn't trivial.
07:04:25andytoshi:(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
07:04:52gmaxwell: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
07:05:37andytoshi:now, what this tells you is that "all the other outputs" is strongly coupled to your output
07:05:48andytoshi:maybe you want to know, how strongly are my various outputs coupled to each other?
07:06:02gmaxwell:andytoshi: multial infomation is just the joint entropy minus the conditional entropies.
07:07:16gmaxwell: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.
07:08:27andytoshi:yeah, so this is a more useful thing to wonder about than "how tightly coupled are all the outputs of this specific transaction"
07:08:58gmaxwell: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).
07:09:49gmaxwell:though the most entropy we can have in a single output when there are only two players is 1 bit.
07:10:05andytoshi: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?
07:10:31andytoshi:(it is selfish because if the answer is yes, then i can perhaps finangle a publication while still doing something useful for bitcoin)
07:12:03andytoshi:describe some measure of coupling*
07:13:56gmaxwell:I must confess, the first sentence of the abstract triggered turboencabulator-detection for me.
07:14:30gmaxwell:( https://www.youtube.com/watch?v=rLDgQg6bq7o )
07:16:09andytoshi: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
07:16:40andytoshi:i admit, the core of that paper is almost cartoonishly "mathematicians inventing problems for no reason except to have fun solutions"
07:19:12andytoshi:but here is a paper relating this stuff to flow problems: http://arxiv.org/abs/1312.5408
07:19:23andytoshi:so i am not blowing smoke when i suggest that it's applicable :)
07:20:00gmaxwell: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.
07:20:35gmaxwell:esp if the many coinjoins are not wired up like a switching network, so that the inadmissablity of multiple inputs later deanonymizes earlier coinjoins.
07:20:58andytoshi:yeah, i think that's the most useful thing for the joiner itself to output
07:21:14andytoshi:but if, for example, some output always winds up matched to a certain input, the owner of that output would like to know this
07:22:08gmaxwell:yea. indeed. though at least that can be solved purely locally.
07:22:19gmaxwell:but I don't think an obvious greedy algorithim exists.
07:23:30andytoshi:so, for the joiner's calculation, it needs to know if certain inputs are obviously linked
07:23:39andytoshi:and "obviously linked" does not sound well-defined to me
07:24:41andytoshi:would it suffice to assume the inputs are independent, and just look at the entropy of the mixer's input-to-output mapping
07:25:04andytoshi:that's nice because it's context-independent -- you give me any rawtx and i can compute that without even a network
07:26:24gmaxwell:andytoshi: you can assume the inputs are independant after doing the trivial preprocessing to merge ones with duplicate scriptpubkeys.
07:27:04gmaxwell:if that raw tx is signed you can still do it by looking at the scriptsigs ... most of the time.
07:28:04gmaxwell: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.
07:29:12gmaxwell: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.
07:29:27andytoshi:can you give an example of this?
07:30:18gmaxwell: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.
07:30:31andytoshi:oh, i get what you mean
07:31:27gmaxwell: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.
07:31:30andytoshi: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"
07:31:59andytoshi:(and with me personally you could even use the donation output
07:32:20gmaxwell: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.
07:32:39andytoshi:ah, that would require better tool support
07:32:55gmaxwell:Yea, but it could just be an addon in the payment protocol pretty easily.
07:33:19gmaxwell:"Add these extra inputs to the transaction and pay them to me, thanks"
07:34:15gmaxwell: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.
07:34:35gmaxwell:and the entropy of the coinjoin is basically log2(inputs*outputs)
07:35:09andytoshi:yeah, i think that's correct, which is pretty cool
07:35:15gmaxwell:as there is an auxiliary table of users paying other users.
07:35:38andytoshi:now, perhaps nsa with its psychologists can get information out that we can't
07:35:40gmaxwell: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.
07:35:46andytoshi:but that's probably not a threat model we can do anything about
07:35:52andytoshi:right, exactly
07:36:24andytoshi:for now our definition of 'plausible' is good, so let's work with that
07:36:26gmaxwell: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.
07:36:44gmaxwell:and that non-sparse payment tables are very much less likely than sparse ones.
07:36:51gmaxwell:even in a world where people use this frequently.
07:37:15andytoshi:that seems plausible, though it's hard to say in the presence of fees
07:37:22andytoshi:maybe people only want to do transactions if they need to do transactions
07:37:49gmaxwell:well, its just unlikely that you could find N people who all want to pay a bit to each other, for N>2 :P
07:38:04andytoshi:oh, yeah :P
07:38:47gmaxwell:cut-throughs also add some interesting analysis wrinkles, again— if they actually existed.
07:39:03andytoshi:now, here's a silly question: our definition of coinjoin entropy as "entropy of the mixer's knowledge" .. is it monotonic?
07:39:09andytoshi:monotonic wrt the number of transactions
07:39:22gmaxwell:you mean the number of contributors to a mix?
07:39:30andytoshi:so if my joiner says "there's a 10-bit transaction in here", can somebody put in a transaction which reduces the entropy?
07:39:40gmaxwell:No, it must go up.
07:39:48gmaxwell:(or stay the same)
07:39:49andytoshi:is that obvious?
07:41:36gmaxwell: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
07:41:45andytoshi:i like that argument :)
07:42:31gmaxwell:The understanding that it was monotonic is why I've favored including poorly mixing transactions too, if thats all thats available.
07:43:08gmaxwell: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.
07:43:27gmaxwell:And if the attacker is forced to the N^2 model (where people are paying people) then the entropy increases enormously.
07:44:36andytoshi:cool, this all sounds good
07:45:13andytoshi:i'll spend some time trying to compute this entropy
07:45:45andytoshi: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"
07:46:05andytoshi:i'm not sure if there's a good way to define such a thing..
07:46:42gmaxwell: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"
07:46:42andytoshi:it'd be awesome if i could make the transaction entropy be the sum of the output values' entropy
07:47:35andytoshi:my guess is, it'd reduce the attacker's search space from N^2 to 2N
07:47:40andytoshi:or somethin
07:47:48andytoshi:something drastic*
07:48:35gmaxwell: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)
07:49:09gmaxwell: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.
07:49:17andytoshi:yeah, my guess is that this would be the most common case, after admissable coinjoins, by -far-
07:50:21gmaxwell:well it generalizes all transactions too.. e.g. a regular payment to you with change fits this model now.
07:50:59andytoshi:oh yeah
07:52:31gmaxwell: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"
07:52:55andytoshi:agreed, for now i will compute the entropy assuming no funny business
07:53:23andytoshi:link to a short document explaining the calculation and how to do funny business which makes the tx safer than claimed
07:57:20gmaxwell:BlueMatt: will the pulltester still run if I close a pull?
08:10:58BlueMatt:gmaxwell: no
08:12:24gmaxwell:BlueMatt: seeing things like this pass is always not a happy moment: https://github.com/bitcoin/bitcoin/pull/3469
08:12:56gmaxwell:but as expected since regtest overrides.
08:13:07gmaxwell:but ... reasons I don't love regtest being a seperate mode…
08:15:48BlueMatt:true, though pull-tester is designed to test subtle bugs, not head-smacking bugs
08:16:00BlueMatt:it fails at both, but still
08:18:13gmaxwell: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)
08:18:52BlueMatt:feel free to code it :p
08:37:15sipa:dang: http://bitcoin.stackexchange.com/questions/19455/searching-for-the-comprehensive-guide-to-creating-crypto-currency
08:39:10warren:sipa: we need someone to actually write the clonecoin generator that we all threatened to write.
08:39:42warren:option: Set exchange bribe amount [minimum 100 BTC]
08:40:07warren:checkboxes for various bad ideas
08:49:38warren:sipa: would others fund this? I can get one of my students to do this.
08:49:52warren:I can throw in some money.
08:50:42gmaxwell:heck, if done right (costs a small bitcoin payment to make it build) it can be revenue producing.
08:51:07warren:don't release source for the generator. make it a web app that outputs everything.
08:51:13gmaxwell:oh absolutely.
08:51:50gmaxwell: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
08:52:01warren:checkbox: "Steal sunnyking's proprietary source for centralized broadcast checkpoints. Will he sue?"
08:54:17gmaxwell:[ ] set your own alert key [....] {+.1 BTC}
08:56:10midnightmagic:that would be so much win
08:56:22midnightmagic:+ seednode code generator
08:56:46gmaxwell:yea, it needs to also provide a standalone miner and pool setup. which is kinda a pita.
08:57:17gmaxwell:the miner isn't so bad so long as it uses sha256 / scrypt / primecoin but the pool setup is more of a pain.
08:57:28warren:hence you charge more
08:58:10warren:it can spit out VM's for block explorers, *cointalk.org SMF, bribe form letter to
08:58:16warren:make it very easy
08:58:42warren:programmatically create a shill army too
08:58:49warren:mechanical turk?
09:00:15sipa:[ ] Use less than 2 year old Butcoin source code {+.3 BTC}
09:00:49sipa:ehm... that actually is a typo, i meant Bitcoin
09:01:01BlueMatt:well if you dont pay it forks buttcoin instead
09:01:03gmaxwell:well buying and selling accounts on bitcointalk is permitted.
09:01:12gmaxwell:so you can even one-stop buy your shill army.
09:02:03warren:would you sell after-sale support?
09:02:09warren:1 BTC/hour
09:02:23warren:NO WARRANTY
09:03:14sipa:[ ] Use doge-styled shill army posts
09:04:01sipa:actually, the opposite perhaps should cost money
09:04:23sipa:so we'll get easily recognizable dummy posts by defauly
09:06:28warren:http://aurawallet.com/ somehow this site causes chrome to use 100% of 4 cores. maybe I'm mining for them. =P
09:12:35midnightmagic:it would be an excellent example of why scamcoins are pointless. what a statement.
09:14:15warren:what's up with this Nxtcoin thing? written in java. entirely premined.
09:14:53_ingsoc:100% PoS apparently. 71 one people own all of it. Yup. :/
09:15:05_ingsoc:No mining! It's a winner.
09:15:50_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.
09:15:52gmaxwell:100% PoS? does it suffer from the nothing-at-stake attack that PPC originally did then?
09:16:35gmaxwell:or is it a consenus that requires quadratic communication, requires all nodes with stake to be online, and is trivally jammed by any participant?
09:17:20warren:the PoA design sounded great in that regard, except after we realized it encourages banking cartels.
09:18:18gmaxwell:well, glad to hear that its something different.
09:18:36gmaxwell:"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."
09:18:51gmaxwell:hopefully '3rd party services' means something domain specific.
09:19:02warren:sounds like they will have centeralized issuers like ripple
09:19:07warren:sounds very much like ripple
09:19:13warren:including the not open source part
09:19:54gmaxwell:yea, indeed not open source 0_o crazy
09:21:23_ingsoc:warren: That was my first thought too.
09:22:10gmaxwell:apparently it's currently being dossed and they are trying to train a "Neural net" to remove spam.
09:22:45jarpiain:jarpiain is now known as Guest20474
09:23:06_ingsoc:gmaxwell: Nxt?
09:23:25gmaxwell:yea, I can't find anything about how it works though.
09:23:40gmaxwell:apparently it's a blockchain, so that probably rules out it being a standard quadratic consensus.
09:23:52gmaxwell:which probably means its vulnerable to the nothing at stake attacks.
09:27:32warren:I was thinking, woudl there be a way to cancel out the extra orphan risk of larger blocks
09:27:40gmaxwell:oh wow, this is partially the work of that Come-from-Beyond guy...
09:28:18warren:if the difficulty was fudged by some factor of the transactions (quantity, days destroyed, fees, or something)
09:28:39_ingsoc:gmaxwell: Has he done anything else?
09:28:44_ingsoc:That we know of.
09:29:01gmaxwell:beyond being a confused jerk on the forums?
09:29:07gmaxwell:what a bummer.
09:29:16gmaxwell:after seeing that I'd estimate less than 1% chance that it works.
09:30:55gmaxwell:I guess thats part of why I didn't see it, I have him on ignore on the forum.
09:31:20_ingsoc:Do you know why he's on ignore?
09:31:48_ingsoc:Not to detract.
09:35:20gmaxwell:no idea, but it would be the same as anyone else— nasty*ignorant > threshold.
09:35:38midnightmagic:but.. it's in java. who cares if he releases the code?
09:37:09gmaxwell: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.
09:38:02midnightmagic:oh I just meant that unless he's running weird obfuscators it can be decompiled to fairly readable
09:38:04_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.
09:38:28_ingsoc:gmaxwell: Mediocre programmers should be roping people in. :/
09:38:45gmaxwell:uh.. nxtcoin addresses appear to be 20 base 10 digits... 66 bits? 0_o
09:42:41gmaxwell:this thing is amazing.
09:42:52gmaxwell:it's like every bad idea multipled into an swimming orgy of bad ideas.
09:43:03gmaxwell:it _forces_ you to use brainwallets.
09:43:52gmaxwell: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.
09:44:47sipa:wait, parts are closed source?
09:45:29gmaxwell:sipa: it's all closed source except for some small parts they released.
09:47:01gmaxwell:well it's an entirely premined coin.
09:47:19midnightmagic:so.. much.. development effort that could have been put to constructive use. :( gaw how disappointing.
09:47:49gmaxwell:it doesn't appear to actually be that much.
09:48:31sipa:"a single source file", "no comments"... these guys are satoshi reborn!
09:49:30maaku:_ingsoc: the problem is that ignorant people with money to invest actually find these things more credible than real projects :\
09:50:11gmaxwell:here is their PoS mining code in their early source release:
09:50:12gmaxwell:int elapsedTime = getEpochTime(System.currentTimeMillis()) - lastBlock.timestamp;
09:50:15gmaxwell:if (elapsedTime > 0) {
09:50:20gmaxwell:BigInteger target = BigInteger.valueOf(Block.getBaseTarget()).multiply(BigInteger.valueOf(account.getEffectiveBalance())).multiply(BigInteger.valueOf(elapsedTime));
09:50:24gmaxwell:if (hits.get(account).compareTo(target) < 0) {
09:50:43_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.
09:52:41gmaxwell: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.
09:53:47_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.
09:54:15_ingsoc:But I guess you do your research and go with what you believe in.
09:54:37gmaxwell:yea, this is totally vulerable to a nothing at stake attack.
09:55:54gmaxwell: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.
09:56:08gmaxwell:so of course, the same attack PPC got nailed with applies trivially.
09:56:13maaku: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
09:57:32sipa:gmaxwell: yes, but if the mining code is not open sourced, that is no problem, right? :p
09:57:41maaku:and in VC eyes, a project that got funding is treated as credible (assuming that someone somehwere did due diligence, I suppose)
09:59:08gmaxwell:pretty sure I can just hack the java bytecode directly here to make it mine all the blocks.
09:59:40gmaxwell:it just needs one extra wrapping loop, with a break when its actually successful. :P
10:05:37midnightmagic:* midnightmagic grits teeth and discovers more reasons why macports feels broken
10:40:41gmaxwell:wow: ... this thread has gone a bit pear shaped since I last looked at it!!! https://trac.torproject.org/projects/tor/ticket/8106
11:22:53jtimon:gmaxwell what java bytecode can you hack?
11:28:03_ingsoc:jtimon: Nxt.
11:40:30jtimon:oh, Nest, thank you
11:41:10jtimon:wasn't that source closed? I assumed it was a ripple fork
11:52:26_ingsoc:They've released some snippets apparently.
12:15:43gmaxwell:So random not very bitcoin idea.
12:16:00gmaxwell:Tor HSs have had some amount of problems with attackers exploiting the now-popular vanity addresses.
12:16:39gmaxwell: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.
12:18:23gmaxwell: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.
12:19:39gmaxwell: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.
17:06:57andytoshi:* andytoshi quietly adds this to the tor-like payment protocol in his "if i had an alt" document
17:22:01sipa:* sipa should also start such a document
17:30:22gmaxwell:@#$*(@*#$(@* why isn't there a @#*(*$@(#* augmented PAKE that doesn't add a communication round?!@#
17:36:36gmaxwell:Password authenticated key exchange.
17:38:47petertodd:BlueMatt: re -wizards meetup, I'm in
17:39:49andytoshi: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
17:40:07andytoshi:(number of partitions of a set of labelled element, which grow exponentially)
17:42:27andytoshi:so we need to be more intelligent to compute the entropy we want
17:45:37andytoshi:petertodd: do you recognize this as some well-known matching problem?:
18:11:29petertodd:andytoshi: nope, I could however write a paper talking about it in terms of post-modern art critique...
18:11:50petertodd:* petertodd is a fine arts grad
18:12:13warren:does mastercoin know this? =)
18:12:23petertodd:warren: probably
18:13:11petertodd:warren:though their process for hiring me consisted of me talking to one of their people on the phone for an hour...
18:37:47andytoshi: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
18:38:22andytoshi:by doing exactly the funny business you suggested
18:49:31andytoshi:OK, rosemary thinks that the 'find maximal number of plausible participants' is NP-hard
18:49:35andytoshi:it reduces to the partition problem
18:50:50petertodd:andytoshi: is that np-hard per tx, or for whole tx graphs?
18:51:04andytoshi:np-hard per tx :(
18:51:28petertodd:andytoshi: maybe that's better? tx's have limits on how big they are...
18:51:47petertodd:andytoshi: remember that two-party-mixes are most likely to be what people actually use
18:52:59andytoshi:petertodd: well, the example we are using is http://blockexplorer.com/tx/a0350aa856b77edeaa08ae9df5047855d487c40490d11713461d200ea70b09c6 which is probably intractable
18:53:07andytoshi:and there are actually only 3 people in there
18:53:56petertodd:andytoshi: that's still a much bigger tx than the expected everyday two-party-mix case
18:54:22andytoshi:yeah, but if you only need one of them to hide a drug deal, you're golden
18:55:42petertodd: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
18:57:44andytoshi: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
18:57:53andytoshi:determine whether it could be a 2-party mix*
18:58:15andytoshi:though as you say, maybe this is OK because the number of inputs and outputs is small
18:59:11andytoshi:but 'only 2 people' does not let us slip into P
18:59:16petertodd:exactly, even if it's some crazy n^n algorithm, the n is small
19:00:04petertodd:from a usability point of view we have to assume that naive two-party mixes are what is going to be most popular
19:27:32sipa:who/what is rosemary?
19:32:39andytoshi::P i was wondering if somebody would ask that..
19:33:04andytoshi:rosemary is my girlfriend, she is not so into bitcoin
19:33:28andytoshi:but her degree was largely CS, so i badger her with a lot of these questions
19:33:35sipa:she does seem into complexity analysis :)
19:33:54andytoshi:mmhmm :)
19:52:17maaku:* maaku would love to read andytoshi and sipa's "if i had analt" documents
19:52:36maaku:BlueMatt: wizards meetup, where are you thinking?
19:52:51sipa:* sipa guesses it will be too far for europeans
19:53:10warren:do it in Hawaii
19:53:20sipa:even further :(
19:54:24petertodd:pity there isn't an island in the atlantic ocean...
19:54:25andytoshi: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
19:55:31warren:petertodd: Iceland!
19:55:33maaku:petertodd is a renaissance man. where'd you do your fine arts?
19:55:45maaku:yeah iceland. or the azores
19:55:47sipa:Iceland is very cool8
19:55:56sipa:cold, even
19:56:11petertodd:heh, iceland it is!
19:56:24warren:we can enjoy puffin meat
19:56:38petertodd:maaku: http://www.ocadu.ca/
19:56:51petertodd:warren: and go aroudn taking beautiful phtoos
20:04:40maaku:heh, you got my wife excited about a trip to iceland now
20:05:45sipa:warren: puffin is nice!
20:05:57andytoshi:oh, that's right, petertodd said he was a -canadian-, not a mathematician
20:06:07andytoshi:that's why i asked you about the matching problem :P
20:06:54petertodd:andytoshi: minor typo, the keys are like right next to each other
20:07:11sipa:someone read too much bash.org
20:07:35maaku:maybe we can get Cloud Hashing to host it
20:07:36petertodd:sipa: +1
20:07:40maaku:i don't think they're in reykjavik though
20:08:20warren:how much of the world's hashing will be in iceland...
20:09:03maaku:arctic air and geothermal power...
20:09:05petertodd:warren: I was just doing the math on if my parents could heat their house profitably with bitcoin mining...
20:09:46sipa:if you can heat your house at acceptable cost using electricity, you certainly can when using mining hardware instead
20:09:52sipa:except: noise, hardware cost
20:10:44maaku:* maaku is waiting for an HVAC insert to replace heating coils with bare ASICs
20:11:09petertodd:sipa: problem is we're really talking about hashing not mining
20:11:43sipa:unsure what distinction you mean
20:11:47petertodd:maaku: I'm waiting for silicon that can run at > 100degC
20:11:59sipa:petertodd: GPUs!
20:12:02petertodd:sipa: it doesn't buy us a damn thing with regard to decentralization
20:12:26warren:decentralized hashing means nothing if cex.io
20:12:39petertodd:warren: yup
20:17:26petertodd: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
20:17:57petertodd:sipa: here in yellowknife though they have (expensive) hydro-electricity from a small damn a little further north
20:27:17maaku:petertodd: you're in yellowknife?
20:27:33maaku:that is far north
20:27:55maaku:i was watching a special the other day about the mining and prospecting boom up there
20:28:09maaku:(old school mining)
20:29:44maaku:I grew up on a steady diet of Jack London. In another life I'd probably be up there myself.
20:42:20petertodd:maaku: yeah, visiting the parents, they moved up there 9 years ago
20:43:11petertodd: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...
20:45:56petertodd: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
20:47:30petertodd: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
21:02:27BlueMatt:petertodd: nice
21:02:58BlueMatt: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)
21:03:16BlueMatt:and if someone doesnt want to pay the flights, its possible they can commit to giving a quick talk and getting that covered
21:03:25BlueMatt:sipa: at least its not as far as mtv :p
21:05:31petertodd:BlueMatt: lots of nice caves in that area :P
21:06:47sipa:BlueMatt: yeah. but finding a reason to visit mtv is easy :)
21:07:43BlueMatt:sipa: still, it only costs like 1-2 BTC these days...
21:08:10petertodd:BlueMatt: not all of us are satoshi :P
21:08:15sipa:damn, that really sounds cheap...
21:08:34BlueMatt:* BlueMatt bought a laptop for 2 btc a few weeks ago because it sounded too cheap
21:08:55sipa:i recently topped up my mobile account using btc
21:08:56sipa:in .be
21:09:20sipa:i wanted to add just 10 eur, and accidentally added 25 eur though...
21:10:34sipa: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
21:12:11sipa:petertodd. maaku. gmaxwell: what's the latest evolution regarding TXO MMRs?
21:13:22maaku:defer to petertodd & gmaxwell on this
21:13:26petertodd:sipa: doing a writeup for them is on my never-ending todo list...
21:13:53petertodd:sipa: the thinking behind them hasn't changed fwiw
21:15:58sipa:i heard something about splitting it up into... i suppose a non-changing txo part and a changing spentness part?
21:16:36petertodd:sipa: oh, that was my plan from the beginning
21:16:57sipa:i didn't catch that part initially then
21:17:55petertodd: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
21:18:07petertodd:sipa: main thing is the two ideas are separate really
21:18:23sipa:you mean... still have a merkle UTXO tree too?
21:18:41petertodd:sipa: no, a per-block txo tree sorted by H(scriptPubKey) or similar
21:19:48petertodd: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
21:29:45sipa:petertodd: not sure i'm following the big picture anymore