00:05:12kloeri:[Global Notice] Happy new years to all those people following fST (or UTC)
00:44:31justanotheruser:Is there any trustless way to pay someone in BTC to mine an altchain that is inherently worthless? (specifically I was wondering if you could subsidize merged mining of a votecoin))
00:49:31Emcy:i suppose you could make some shitty system that bloats the fuck out of bitcoin because they wont merge mine a specialised votecoin
00:50:14Emcy:but i dont think we really know how reluctant the poolops are to merge mine something decent because no ones ever tried
00:51:01justanotheruser:Emcy: I don't really want to use the bitcoin blockchain. A new blockchain could be created cheaply and be disposable.
00:51:26Emcy:well thats a refreshing attitude
00:53:29justanotheruser:Emcy: anonymous voting would require many coinjoins and coinswaps. If there were millions of voters, the election could cost millions of dollars in bitcoins
00:54:07justanotheruser:with all the transaction costs. Not much of a point.
00:54:38Emcy:i wonder how much those shitty diebold contracts cost
00:54:59Emcy:did you work out how to issue votes anonymously
00:55:08Emcy:*issue ballots
00:56:13justanotheruser:Emcy: everyone gets a vote, everyone has a public bitcoin address associated with their name.
00:56:27justanotheruser:Coinswaps and coinjoins are used to anonymize the votes
00:56:48justanotheruser:then when everyone has sufficient anonymity, they to 1ALGORE or 1GEORGEBUSH
00:56:56justanotheruser:*they pay to
00:57:41justanotheruser:I just wish I could pay someone automatically in bitcoins for finding a block without a central authority
01:00:04Emcy:what about vote selling
01:00:34gmaxwell:justanotheruser: thats really dumb. sorry, it's often repeated enough you should have seen other people calling it out.
01:00:48gmaxwell:Bitcoin is not a jamming resistant network. Congrats you just let the miners decide the election outcomes.
01:01:15justanotheruser:gmaxwell: What do you mean by jamming resistant
01:01:43justanotheruser:Emcy: That is possible without decentralized voting (but I agree, this makes it easier)
01:02:05Emcy:oh yeah hes right
01:02:46petertodd:gmaxwell: timelock crypto can be used to circumvent miner censorship of votes in some conditions
01:02:56Emcy:i think when i first brought up some sort of votecoin was years ago back when i still thought every responsible citizen could have a miner in the cupboard
01:02:59justanotheruser:Blocks could be rejected if they didn't include a certain number of transactions
01:04:29Emcy:justanotheruser when youre talking about elections there are incentives which easily override money concerns
01:04:42petertodd:justanotheruser: now you've turned pow mining into a weird pow/proof-of-stake/proof-of-sacrifice combo, doesn't necessarily help re: elections
01:04:56Emcy:in the money/power chicken and egg game, power always came first
01:05:25justanotheruser:petertodd: What? How is there any prooof of stake/sacrifice?
01:05:48petertodd:justanotheruser: the transactions - how do you distinguish a "legit" tx from one the miner made?
01:06:39justanotheruser:petertodd: network rule that only allows a coin to be transacted a certain number of times
01:07:27petertodd:justanotheruser: right, so by including a transaction you have sacrificed someone, hence, it's proof-of-sacrifice
01:08:00justanotheruser:petertodd: how have a sacrificed someone?
01:08:28petertodd:justanotheruser: you sacrificed something, coinage, or coins, or whatever scheme you decide to use
01:09:20justanotheruser:petertodd: to get a block you have to have done a PoW with a certain number of transactions. The miners have no sacrifice
01:10:05petertodd:justanotheruser: something was sacrificed, or miners can stuff the block full of their own transactions at zero cost
01:10:48petertodd:justanotheruser: anyway, this works for voting: http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03524.html
01:10:50justanotheruser:petertodd: The miners can only have a limited number of transactions
01:11:12petertodd:justanotheruser: limited how?
01:11:43justanotheruser:petertodd: because everyone only gets one votecoin and they only can be transacted 100 times from the coinbase
01:12:06gmaxwell:justanotheruser: dude, wtf. you are trying to employ bitcoin to do one of the things it doesn't really do at all— antijamming. If you can assign ballots to people the voting process is largely done, nothing hard remains.
01:12:32justanotheruser:gmaxwell: anonymizing remains
01:12:42gmaxwell:(well, except anti-coercion is basically impossible in a online voting context)
01:12:43petertodd:justanotheruser: there are much better ways to anonymize votes
01:13:04gmaxwell:anonymizing is kinda pointless if you don't generally have anti-coercion, but anonymizing is trivial, go look up "reencryption mix"
01:13:05justanotheruser:petertodd: anything other than zerocoin of a central authority?
01:13:12gmaxwell:electronic voting is a _very_ well studied subject.
01:13:16petertodd:justanotheruser: this has been a "sexy" problem in crypto for years, and people way smarter than any of us have spent whole phds on the subject
01:14:00gmaxwell:invoking bitcoin for it is just a redneck suggesting his trusty shotgun as a solution to multivariet calculus. :P
01:14:18gmaxwell:Bitcoin solves an entirely unrelated problem, and it doesn't solve the important problems in voting.
01:14:22petertodd:justanotheruser: if you need decentralized consensus about the results of a vote then blockchain's can make sense, but rarely do you need that
01:14:24justanotheruser:Is there another decentralized voting method?
01:14:51petertodd:justanotheruser: so why is this vote required to be "decentralized", and what do you mean by that term?
01:15:24justanotheruser:petertodd: I would like it to be decentralized because it prevents vote manipulation and what's happening in Russia.
01:15:27gmaxwell:justanotheruser: what you were suggesting didn't sound decenteralized. But assuming you get as far as somehow giving ballots to voters, there are systems which are no less decenteralized than bitcoin.
01:15:52gmaxwell:justanotheruser: how do you plan on giving each person one ballot without someone getting 500 in a decenteralized manner?
01:16:26petertodd:justanotheruser: right, so you're applying this voting scheme to a typical thing where the list of voters is already defined by a central authority, so you don't need blockchains - existing crypto works just fine
01:16:27justanotheruser:gmaxwell: That is centralized, but you can verify that someone isn't getting too many votes, no votes, or that imaginary people are getting votes.
01:16:49petertodd:justanotheruser: you can't with crypto - those are all human problems
01:16:54gmaxwell:okay if you can do that you can just apply the mountains of evoting lit.
01:17:34justanotheruser:petertodd: Yes it is
01:17:40justanotheruser:*Yes they are
01:17:56petertodd:justanotheruser: I mean, once you solve the problem of figuring out who the voter list is, you can start using crypto, but you already have a central authority so standard algorithms and techniques work - they don't use blockchains
01:18:33gmaxwell:and blockchains don't work, because you get crap like "a majority of hashpower can rig the election" which is undesirable to a high degree.
01:19:12petertodd:gmaxwell: yes, unless the voter list is defined in terms of hashing power :P
01:19:16gmaxwell:I do kinda like idea of using OWAS to create a jamming proof communications mesh, I don't think I've seen that proposed outside of #-wizards.
01:19:27gmaxwell:petertodd: yea okay, sure you can just leave out the voters list then... miners decide. :P
01:19:56petertodd:gmaxwell: more seriously, with my timelock thing you *can* do a vote with well-defined limits for how easy it is to rig the election
01:20:31justanotheruser:gmaxwell: yes, that was my original problem, I wanted to have the merged mining to be paid it bitcoin somehow. This would increase the number of miners and prevent 51% (hopefully)
01:20:41gmaxwell:fagmuffinz: One Way Aggregatable signatures.
01:20:57gmaxwell:fagmuffinz: cryptographic signatures which you can merge and still validate, but you cannot unmerge.
01:21:45gmaxwell:fagmuffinz: so e.g. you give me your vote and I merge in the vote I have (which is a merge of petertodd and mine) and then we pass it on.. and someone can't later pick apart our votes to only includ yours in the election, unless they get a clean copy of yours from you.
01:22:13fagmuffinz:I looked up your previous explanation =]
01:22:31fagmuffinz:Would be decent for building the mesh
01:23:42gmaxwell:well my though is that politics often follow social lines, so you could still perhaps rig, but it would be highly detectable when virtually all of the votes for one candidate disappear. :P
01:24:01maaku:petertodd: but how do you have a timelock system that isn't at the DoS-mercy of the person running the timelock?
01:24:19fagmuffinz:Yea, still, it's not quite the long-term solution yet
01:24:48fagmuffinz:There's probably no good way, without centralized trust, to resolve that issue
01:25:04gmaxwell:fagmuffinz: oh nah, in most cases the voting systems don't really need jamming free communication. what they do is make it easy to check what votes are included before the count, and then trust that if your vote is omitted you will scream from the hilltops.
01:25:30fagmuffinz:Yea, that'd be sufficient
01:25:33gmaxwell:e.g. disencranchisement is detectable.
01:25:36fagmuffinz:Assuming good citizenry
01:25:40maaku:which works in democracy, but not automated consensus systems
01:25:55petertodd:maaku: read the paper, it's not a central timelock, just a sequantial hard algorithm
01:26:10fagmuffinz:Yea, guaranteeing that your vote made it after the count is sufficnet
01:26:13fagmuffinz:sufficient ***
01:26:14petertodd:maaku: obviously cracking the timelock is computationally intensive of course
01:26:47fagmuffinz:petertodd: Is a timelock explanation above?
01:27:05maaku:fagmuffinz: only if there is repercussions for cheating
01:27:18midnightmagic:if a citizen doesn't care if his vote is counted, it's not really disenfranchisement.
01:27:29maaku:in some applications - PoS vote on validation rules, for example, it is useless to complain
01:27:54fagmuffinz:Voting is a social system
01:28:17fagmuffinz:Separate from guaranteeing existence in something
01:28:17maaku:the votes drive some consensus process, and there's no way to back out other than to abondon the whole system, which would be a successful DoS outcome
01:29:07fagmuffinz:DoS is a universal threat that you have to accept upon automating this shit
01:29:50fagmuffinz:The only sure way of mitigating DoS is having enough infrastructure
01:30:00justanotheruser:fagmuffinz: not necessarily in a decentralized system
01:30:21justanotheruser:for example: Bitcoin is very difficult to DoS
01:30:43maaku:petertodd: ok i understand, it just maks decrypting have a cost
01:30:55fagmuffinz:Hence you're trying to use it for voting
01:31:53justanotheruser:fagmuffinz: that's not the reason I want to use it for voting. It's more to verify that everyone who got a vote had their vote counted.
01:32:40maaku:petertodd: if some joker puts a ballot in that is ill-formed, junk, or encrypted with different key, it would be nice to have a compact, quickly verified proof of that
01:35:24petertodd:maaku: yeah, that's a very interesting crypto problem actually, I suspect it may be incompatible with the sequential-hard scheme
01:36:21fagmuffinz:justanotheruser: Are you just inquiring or do you have some partial plan? I'm thinknig about what gmaxwell put forward in terms of aggregating a single score for verification...
01:36:32maaku:petertodd: i have a rather near term application if a jamming-resistant proof-of-stake voting scheme can be found
01:36:52fagmuffinz:You could tell your vote made it into the list
01:37:04petertodd:maaku: of course the whole thing is dependent on the fact that the fastest sequential implementations of a lot of algorithms are reasonable close to each other in performance - off-the-shelf is basically the best you can get within an order of magnitude
01:37:08petertodd:maaku: oh yeah?
01:37:10fagmuffinz:You'd need to take additional steps to ensure the list was properly counted
01:37:32justanotheruser:fagmuffinz: Is is possible to do that anonymously?
01:37:47maaku:yeah, demurrage distribution - "repbulicoin". i forget if I've told you about it already
01:38:56petertodd:maaku: ah yeah, that'd work
01:38:58maaku:demurrage distributed according to forced coinbase payments determined by a proof-of-stake vote on a jamming-free ledger
01:39:09petertodd:maaku: damn expensive those in terms of cpu-power
01:39:12maaku:i got it worked out up to the jamming-free part :\
01:39:45maaku:yeah, hence the need for cheap verification..
01:40:00maaku:i'm okay with votes being expensive, but validating nodes that count the votes need to be cheap
01:40:01petertodd:yup, and I'm pretty sure that's been proven to be impossible
01:40:35maaku:well you could do it with gmaxwell's ticking timelock pow for example
01:40:38petertodd:obviously you can easily pass around the decryption keys proving a vote exists, but not the other way around
01:40:42maaku:so there's an existence proof
01:40:56maaku:oh you mean the cheap validation
01:41:30petertodd:well keep in mind that part of the reason why the scheme can work if embedded in otherwise-normal looking transactions is that miners would (in theory) find it too expensive to just block all transactions
01:42:07petertodd:the moment you have a "well-known" place where the vote would be recorded it becomes much easier for miners to rig the vote
01:48:34maaku:yes it would have to be either steganographically encrypted, or taken out of the miners hands
01:50:09fagmuffinz:justanotheruser: you could have people agree to some protocol that would operate the same way some central authority would, and if compliance with that protocol can be algorithmically guaranteed, then you could decentralize it
01:50:22fagmuffinz:Thinking on that algorithm
01:55:21fagmuffinz:I mean, you don't need a proof of work for it at all
01:55:28fagmuffinz:If you actually count the vote right...
01:55:35fagmuffinz:There's no incentive to keep recounting it
01:55:42fagmuffinz:All you care about is verification
01:55:57fagmuffinz:Which is easily agreeable in a shared protocol
01:56:05justanotheruser:fagmuffinz: how do you do this anonymously?
01:56:32justanotheruser:while verifying that everyone who started with a vote, and only those that started with a vote are counted
01:56:47fagmuffinz:That's harder
01:56:54fagmuffinz:First part is easy, just random key generation every time
01:57:05fagmuffinz:Now you're asking about assigning people keys
01:57:25fagmuffinz:Let's say...
01:57:33fagmuffinz:Everyone agreed to do a shamir's secret sharing algo
01:57:47fagmuffinz:And you could generate M keys...
01:57:55justanotheruser:fagmuffinz: If the central authority can make 10000000 votes for themselves, then it is no better than the current situation
01:58:53fagmuffinz:The M keys could be applicable to use, then, for signing given enough length
01:59:23fagmuffinz:Thinking about retooling shamir's
02:00:21fagmuffinz:I think this would work...
02:00:44justanotheruser:When assigned keys, you either need to say who you gave them to, which would remove anonymity, or not say, which would allow them to make as many votes as they wanted
02:00:44fagmuffinz:Is it important to outside parties to verify the result of an election?
02:00:59fagmuffinz:I've already gotten past that
02:01:25justanotheruser:What, using shamir?
02:01:31fagmuffinz:I've got it actually
02:01:37fagmuffinz:As long as outside parties don't need to vote
02:01:43fagmuffinz:Or verify
02:01:52justanotheruser:How would you use shamirs for voting?
02:02:01fagmuffinz:God, that's gorgeous
02:02:12fagmuffinz:Let's say there's a blockchain that starts with some initial seed
02:02:21fagmuffinz:Everyone shamir's secrets that seed
02:02:27fagmuffinz:And generates M keys to vote with
02:02:49fagmuffinz:Encrypt this initial seed with the key Shamir's secret sharing generates
02:03:02fagmuffinz:Save it as the next seed for the next "voting block"
02:03:10fagmuffinz:Everyone who's in knows it
02:03:23fagmuffinz:Those people then use their M keys to cast a vote
02:03:27fagmuffinz:Moot after that point
02:04:22fagmuffinz:You could add people potentially
02:04:31fagmuffinz:Everyone agrees that each key also gets to elect one new person to join
02:06:38justanotheruser:fagmuffinz: Wouldn't everyone know everyone elses votes if there was a shared seed that was the other half of everyones secret?
02:06:59fagmuffinz:But you can make that pseudononymous
02:07:44justanotheruser:So there are pseudonyms associated with the votes? Meaning the votes aren't guaranteed to be associated with a person?
02:07:59fagmuffinz:The issue I'm running into right now mentally...
02:08:16fagmuffinz:Is ensuring the keys generated that suffice shamir's secret sharing...
02:08:25fagmuffinz:Can be isomorphic to a private/public key pair...
02:08:34fagmuffinz:Or guarantee some private/public key pair
02:12:20fagmuffinz:If p and q were your public/private key pair
02:12:25fagmuffinz:You could do something like...
02:12:30fagmuffinz:G = p^q
02:12:43fagmuffinz:Then sign G with p
02:13:07fagmuffinz:One of the M keys
02:13:11fagmuffinz:Sign (G,p)
02:13:54fagmuffinz:All of this modulo some N
02:21:23fagmuffinz:K, scratch part of that. All that's necessary to ensure that whoever had the key actually cast the vote is signing off an (p,N) message with one of the shamir's keys, for a p/q mod N public/private key pair. I currently have no way of guaranteeing good behavior to those included in the vote, aside from the protocol penalizing them during the next voting round(s)
02:27:30fagmuffinz:Is that sufficient?
02:40:07justanotheruser:sorry, I was away, you still there fagmuffinz
02:41:53justanotheruser:I don't really understand what you mean by penalizing them
04:40:21fagmuffinz:I'm not exactly sure what I mean either thinking about it
04:40:25fagmuffinz:Or any good way of enforcing it
04:40:52fagmuffinz:The issue is in verifying everyone else's key in the SSS (Shamir Secret Sharing), you could easily use any of their keys to vote
04:41:52fagmuffinz:So you're assuming good behavior amongst the voting population
04:41:54fagmuffinz:That's probably a no-no
06:15:46midnightmagic:fagmuffinz: man you have a terrible nickname
06:18:42gmaxwell:fagmuffinz: I'm not sure what you're trying to accomplish, I missed the history.
06:19:47justanotheruser:gmaxwell: It was the voting thing again.
06:35:21phantomcircuit:midnightmagic, maybe he likes his muffinz with fags
06:35:31phantomcircuit:although that sounds a bit gritty
19:38:17maaku:can Grover's algorithm be used for quantum mining?
19:39:23gmaxwell:sure, in theory, if there existed hardware that could run it.
19:40:39gmaxwell:it's only a sqrt speedup. It would unhinge the difficulty update somewhat. (though if it got far out of wack it would still have quadratic convergence)
19:44:47maaku:Some FUD on lesswrong about quantum computing leading to centralization
19:45:39warren:No tech breakthroughs are needed for human behavior to cause centralization.
19:46:32maaku:heh, yeah
19:49:46gmaxwell:I don't see where that conclusion comes from, unless it's just some assumption that only one party will have access to the faster miner.
19:50:01maaku:gmaxwell: yes, that's the (rediculous) assumption
19:50:29gmaxwell:Not only that— Its quite likely that should someone successfully use Grover it'll be _slower_ for some time. Simply because the quantum machine runs at 100khz or whatever.
19:50:48maaku:that someone will invent a quantum computer capable of doing more work than the entire bitcoin network
19:51:47Alanius:isn't the "quadratic speedup" irrelevant when considering sha 256?
19:52:13Alanius:it's quadratic only for large enough problems
19:52:20Alanius:but the problem size is fixed in this case
19:54:04andytoshi:maaku: lesswrong link? istm that any non-infinite speedup would be covered by the difficulty algo
19:54:16maaku:Sybil successfully Sybil-attacked psychiatrics: http://www.npr.org/2011/10/20/141514464/real-sybil-admits-multiple-personalities-were-fake
19:54:48sipa:Alanius: the quadratic speedup is about finding a preimage
19:55:17Alanius:... isn't that what Grover's algorithm does?
19:57:08maaku:andytoshi: http://lesswrong.com/r/lesswrong/lw/je7/a_proposed_inefficiency_in_the_bitcoin_markets/a8xl
19:57:26sipa:Alanius: right, it's only quadratic if you see the size of the hash output as variable
19:58:55andytoshi:sipa: is it correct to think of mining that way,
19:58:59K1773R_:K1773R_ is now known as K1773R
19:59:36andytoshi:"find a SHA16 preimage of 00", then a SHA32 preimage of 0000, and so on
20:00:41Alanius:I guess you could devise a variant of Grover's algorithm that finds a partial collision instead of a full one, and you'd probably see that quadratic speedup with regards to the inverse of the target :)
20:02:00andytoshi:Alanius: yeah, that's what i'm trying to say
20:03:11sipa:right, it's grover on truncated double sha256, with variable truncation length
20:07:30gmaxwell:Alanius: If you're saying that you're going to find complete preimages (size at maximum) than the work factor is still 2^128, which is infeasable.