Zero Knowledge Contingent Payments

[gmaxwell]

I've finally moved my old (Nov 2011, yikes) "Why hash locked" page on the Bitcoin Wiki to the main namespace:

https://en.bitcoin.it/wiki/Zero_Knowledge_Contingent_Payment  (Go read this if you haven't before)

I'd like to get around to actually performing one of these transactions as a public demo, but I've struggled a bit with finding a simply understood (e.g. answer to some complicated science question is not so good) example which is not politically controversial ("I'll pay you for the masterkey that breaks Widevine DRM") but also one that isn't so contrived that everyone doesn't just say "Why not used a trusted arbitrator".

Any ideas?

[Qoheleth]

"I've got here a program that can win at stocks."

The seller can do a zero-knowledge proof that this claim is true for any given historical period the buyer wants to test. Do enough of these tests for the buyer to be satisfied, then proceed as normal.

The interesting thing about this case is that it's one I've seen in the wild, on this very forum; people sell "trading bots" and "trading strategies" and so forth, and there's always this worry of "why would you be selling it if it actually worked". With this technology, the buyers don't have to trust that the algorithm works; the seller can prove it!

[gmaxwell]

Hm. Interesting point. It doesn't actually have to be backtesting based.  E.g. You say "I have a program that can win at stocks" I respond "Past performance doesn't indicate future results: Give me a proof that you timestamped your program in the blockchain N months ago, and a ZKP that your program also predicted future prices for the following N months", though a little care must be taken to eliminate post-selection: e.g. where I timestamp a million programs and then only offer to sell you ones that won retrospectively.

[Mike Hearn]

I added a link from the contracts page, though by the time I saw this I'd already titled the section "Pay for proofs" which is perhaps a bit clear than zero knowledge contingent payments?

One use for this is paying to an identity rather than a key/address. You might want this if you were paying someone who doesn't use Bitcoin yet, or hasn't actually been born (but you know roughly when they will be born and what their name is, i.e. you are their parent).

The program would then be a program that verifies ownership and (a subset of) properties of some digital ID, like name, date of birth, etc.

You could also pay to an email address by requiring that the program verifies a digital signature issued by a certificate with CN=user@host.com - these are given out for free by companies like Comodo because all they have to do is email you a clickable link to verify.

[Mike Hearn]

Generalising that, pay-to-certificate feels like a fairly powerful and useful paradigm.

You can imagine a distributed charity that wants to encourage healthy living by rewarding people who reach a certain age without any lifestyle diseases. However the charity does not really exist and its anonymous members, for obvious reasons, do not want to be in the business of having or checking peoples medical data themselves.

So the charities members post bounties that require a proof that you obtained a clean bill of health from a doctor (with a global counter so a single person can only claim one outstanding bounty at a time). The doctors can be arranged into a kind of PKI. The certificates would assert that you aren't obese, a smoker, drug addict, that you do some exercise regularly or whatever. Anyone can then claim a bounty by creating a private key, getting the public key signed by a doctor, then running a program that proves existence of the certificate chain.

Of course you would need infrastructure on top to ensure that whoever wishes to claim an outstanding bounty can find and connect to the bounty-poster, so the proof protocols can be run.


Edit: One might wonder why anyone would post such bounties. Perhaps it's a way to reduce insurance premiums. A group of people might calculate that it's cheaper to incentivise people to live healthily than pay the insurance premiums for treating them when they have a heart attack. I suppose actuaries calculate this sort of thing all the time. That group could then engage in an assurance contract to raise the money for the bounties. Bitcoin script isn't powerful enough at the moment to reflect spending transactions and ensure they are of a particular structure, so you'd need a trusted third party to ensure the contract money was actually used in the way the participants expected, but that is probably solvable with a more advanced scripting language.

If you don't like the idea of fallible human doctors doing the issuance, you can imagine it's actually a portable health testing kit with some secure hardware inside that can attest to its findings. Or you can just use old fashioned techniques like auditing to ensure doctors are playing by the rules (claiming a bounty could require you to present an anonymous ID proof along with a proof that this ID had not claimed such a bounty within the last 5 years).

[gmaxwell]

The idea in the ZKCP page is that you take some information you want to pay-for-disclosure for but which the Bitcoin network can't currently evaluate a disclosure test for and you use a ZKP to replace your original wish ("I want data X") with one the Bitcoin network can pay-to-proof ("I want the hash preimage of Y, because I know that if I have that I can decrypt something to get data X").

One of the limitations of this approach which reduces its usefulness for pay-to-identity it that it's interactive. You need a hashed key provided by the proving party and you need to see the out-of-band proof before writing the actual payment transaction.

If, instead, script could validate a SNARK you could remove the interaction and have a real "pay to proof" rather than an interactive "pay for proof" which would then make it more useful for things like the identity based payment.

[Mike Hearn]

Yeah I'd love to see checking of SNARKs be a future opcode (waaay future).

I think interactive protocols might become more practical in future at least if they aren't too CPU intensive (so not snark based protocols then). People are now carrying around with them always-on computers that can be woken up and reached over the network on demand. It's not unimaginable to have an app on your phone that sits there for 6 months and eventually gets silently started in the background to complete the protocol. Android does this sort of thing all the time.