--- Log opened Sun May 05 00:00:05 2013
03:24 < amiller> i haven't looked at my anti-coalition puzzle for a while, but i've learned how to use two crypto primitives to do roughly what i want
03:24 < amiller> the first is a zero knowledge proof, the second is an extractable hash function
03:24 < amiller> i'll explain what the point of this is
03:25 < amiller> to encourage decentralization (or discourage pooling resources) we might want to design a proof of work puzzle that is difficult to outsource
03:25 < amiller> the basic scenario is this
03:26 < amiller> suppose Alice and Bob each have a personal budget, and they have two options: either they pool resources and purchase one big Asic, or they each mine independently with their GPUs
03:26 < amiller> also they don't inherently trust each other
03:26 < amiller> it's more efficient for them to pool resources and buy an asic, although this option is also more centralized and therefore worse for the network overall
03:27 < amiller> assume that if they buy the asic then Alice has to operate it at her house
03:28 < amiller> since they don't trust each other, the only way they'd agree to this is if they can work out an arrangement where Alice can prove that she's operating the asic fairly, meaning in a way that benefits them both equally
03:28 < amiller> the current proof of work puzzle mostly accomplishes this
03:28 < amiller> the basic technique is for Alice to show Bob her shares, like the closest she gets to a winning block each day
03:29 < amiller> more specifically, the winning nonces are a set, and the "shares" are a much larger superset of the winning ones
03:29 < amiller> each computed hash in bitcoin contains a hash commitment to a particular block, so by revealing the block alice can prove that she was running at roughly the correct rate, and that she was only working on blocks that would have paid out equally to both of them
03:30 < amiller> okay so this is bad for decentralization, because in the extreme case everyone might want to pay for shares of a huge mining operation that gets cheap power in sweden or something
03:31 < amiller> what we'd basically want as an alternative is a proof of work puzzle that doesn't admit such a safe outsourcing protocol
03:32 < amiller> the idea is that whoever is operating the asic and doing the hashing should be enabled to run away with whatever the winnings are
03:33 < amiller> what makes the safe outsourcing protocol work for the hashcash pow is that the work contains a commitment to a particular payout strategy
03:34 < amiller> to get this desired anti-coalition property, it should be malleable in the sense that the payout destination is undefined until after the work is complete!
03:35 < amiller> the current work can be thought of as this:   h( nonce || block-commitment || payout-commitment ) < difficulty
03:35 < amiller> the basic structure of my suggestion is this:  h( nonce || block-commitment || privatekey ) < difficulty
03:35 < amiller> so you can still commit to a block, just it's everything except the actual thing it takes to win the coin
03:36 < amiller> like whoever possesses the private key can claim the prize
03:36 < amiller> so far this is all just a recap i've done this same ramble previously in #bitcoin-dev
03:36 < amiller> now for the new material...
03:36 < amiller> there's a certain property of this hash function that we want which is that it should be "extractable"
03:36 < amiller> extractable is like the opposite of obfuscatable
03:37 < amiller> if it's not extractable, then there's the potential for the involved parties to create some wacky obfuscated hash function where the private key is built into the hash and there's no way to recover it just from evaluating it on different nonces
03:37 < amiller> if it's extractable then that's not possible
03:38 < amiller> extractable hash functions are discussed here: http://eprint.iacr.org/2011/443
03:38 < amiller> it's sort of a recently popular concept because it's equivalent to the super-efficient circuit verification i talked about last time
03:39 < amiller> but it's kind of on shaky ground as far as assumptions go, it doesn't seem possible to prove that a construction is extractable, but there are constructions that are thought to be...
03:39 < amiller> okay so the next problem is
03:40 < amiller> normally you have to revael the nonce and the block commitment etc as plaintext
03:40 < amiller> but in my scheme where that's a private key, it wouldn't be safe to do so
03:40 < amiller> this is where a zero knowledge proof comes in, all you have to do is construct a zero knowledge proof that you know a privatekey such that the condition holds
03:41 < amiller> and you can still open the block-commitment as normal
03:48 < amiller> to actually give a formal definition for this property i'd have to have something more to say
03:48 < amiller> about like the kind of joint work protocols that i'd consider
03:48 < amiller> because like
03:49 < amiller> any hash function at all could be done as a multiparty computation or a homomorphic outsourcing thing
03:49 < amiller> but basically those would be way less efficient (hopefully)
03:50 < amiller> so i think like the best that can be done is to say something to the effect of well if you want to form a coalition among untrusting parties, then you'd have to use a heavy generic technique which would probably obliterate any advantage from economy of scale
20:43 < sipa> warren: btw, i have a branch of my bitcoin repository (secp256k1) that uses my library, and doesn't need OpenSSL/EC
--- Log closed Mon May 06 00:00:08 2013