Zero Knowledge Contingent Payment - Revision history

Calliptamus at 15:58, 17 May 2025

2025-05-17T15:58:37Z

← Older revision		Revision as of 15:58, 17 May 2025
Line 1:		Line 1:

	It's possible to make payments using Bitcoin which are released if and only if some knowledge is disclosed by the payee and to do this in a trustless manner where neither the payer or payee can cheat. This is accomplished using the combination of a hash-locked transaction and a bitcoin-external protocol to set things up so that the data revealed in the hashlock release is the data they need.		It's possible to make payments using [[Bitcoin]] which are released if and only if some knowledge is disclosed by the payee and to do this in a trustless manner where neither the payer or payee can cheat. This is accomplished using the combination of a hash-locked transaction and a bitcoin-external protocol to set things up so that the data revealed in the hashlock release is the data they need.

	==Protocol outline==		==Protocol outline==

JonathanCross: /* Hash locked transactions */ Its => It's

2020-04-08T11:17:08Z

Hash locked transactions: Its => It's

← Older revision		Revision as of 11:17, 8 April 2020
Line 5:		Line 5:
	===Hash locked transactions===		===Hash locked transactions===

	~~Its~~ possible to author a payment in the existing Bitcoin system that requires the redeemer to provide a "secret" which hashes to a specified value. [https://blockexplorer.com/tx/9969603dca74d14d29d1d5f56b94c7872551607f8c2d6837ab9715c60721b50e The 0.01 output here with the SHA256 opcode] is an example of such a transaction. "To collect these funds your transaction must provide a value that hashes to this other value."		It's possible to author a payment in the existing Bitcoin system that requires the redeemer to provide a "secret" which hashes to a specified value. [https://blockexplorer.com/tx/9969603dca74d14d29d1d5f56b94c7872551607f8c2d6837ab9715c60721b50e The 0.01 output here with the SHA256 opcode] is an example of such a transaction. "To collect these funds your transaction must provide a value that hashes to this other value."

	Used directly, like in the above example, this is insecure: Once you've published the spending transaction another node could just drop your transaction and use the password in a new transaction that pays him instead.		Used directly, like in the above example, this is insecure: Once you've published the spending transaction another node could just drop your transaction and use the password in a new transaction that pays him instead.

Dooglus: /* Further mproving privacy */ typos

2016-02-27T04:06:44Z

Further mproving privacy: typos

← Older revision		Revision as of 04:06, 27 February 2016
Line 55:		Line 55:
	Alternatively, you could construct the payment as an anyone can pay transaction where the output is greater than the input you provide. You would give him this transaction, then he would add funds of his own and announce it and wait for it to be mined before announcing the key in the transaction spending it. This way he could not lock up your funds without locking up funds of his own.		Alternatively, you could construct the payment as an anyone can pay transaction where the output is greater than the input you provide. You would give him this transaction, then he would add funds of his own and announce it and wait for it to be mined before announcing the key in the transaction spending it. This way he could not lock up your funds without locking up funds of his own.

	==Further ~~mproving~~ privacy==		==Further improving privacy==
	Many other transaction types also use the same hash locked pattern, but privacy can be further improved:		Many other transaction types also use the same hash locked pattern, but privacy can be further improved:
	A ZK-payment can be transformed using the [https://bitcointalk.org/index.php?topic=321228.0 CoinSwap] approach where ~~they~~ payer first pays into an ordinary 2-of-2 escrow+refund with the payee. ~~The~~ then would perform the ZK-payment transactions described above externally to the Bitcoin network, and if everything goes through without cheating the payer just signs a 2-of-2 release to pay the payee directly, without disclosing to the network that a hashlocked transaction was used. If the payer fails to release the escrow directly, the payee can just release it by announcing the hashlock and hashlock redeem.		A ZK-payment can be transformed using the [https://bitcointalk.org/index.php?topic=321228.0 CoinSwap] approach where the payer first pays into an ordinary 2-of-2 escrow+refund with the payee. They then would perform the ZK-payment transactions described above externally to the Bitcoin network, and if everything goes through without cheating the payer just signs a 2-of-2 release to pay the payee directly, without disclosing to the network that a hashlocked transaction was used. If the payer fails to release the escrow directly, the payee can just release it by announcing the hashlock and hashlock redeem.

Dooglus: /* Hash locked transactions */ typo

2016-02-27T03:59:16Z

Hash locked transactions: typo

← Older revision		Revision as of 03:59, 27 February 2016
Line 11:		Line 11:
	So— the advice is that you shouldn't use a password alone, you should require a signature and a password. But then what is the use of that?		So— the advice is that you shouldn't use a password alone, you should require a signature and a password. But then what is the use of that?

	There are a couple uses but I'll give an example here of one of the more impressive ~~and~~ and far-out ones:		There are a couple uses but I'll give an example here of one of the more impressive and far-out ones:

	===Zero knowledge proof to binding===		===Zero knowledge proof to binding===

Gmaxwell at 22:21, 26 February 2016

2016-02-26T22:21:48Z

← Older revision		Revision as of 22:21, 26 February 2016
Line 45:		Line 45:
	You then form a Bitcoin payment which requires both my public key and password K. In order to redeem this transaction I must disclose K, the key you need to decrypt Ex and give you your solution. So neither of us can cheat, so no trust is required.		You then form a Bitcoin payment which requires both my public key and password K. In order to redeem this transaction I must disclose K, the key you need to decrypt Ex and give you your solution. So neither of us can cheat, so no trust is required.

	The [https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/ first ZKCP] was performed on the Bitcoin network in 2016, after ~~a number of~~ years ~~waiting~~ for sufficiently powerful general purpose ZKPs to become practically available.		The [https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/ first ZKCP] was performed on the Bitcoin network in 2016, after waiting almost 5 years for sufficiently powerful general purpose ZKPs to become practically available.

	==But what if they're just anti-social and don't redeem the txn?==		==But what if they're just anti-social and don't redeem the txn?==

Gmaxwell: Finally reality!

2016-02-26T21:39:20Z

Finally reality!

← Older revision		Revision as of 21:39, 26 February 2016
Line 45:		Line 45:
	You then form a Bitcoin payment which requires both my public key and password K. In order to redeem this transaction I must disclose K, the key you need to decrypt Ex and give you your solution. So neither of us can cheat, so no trust is required.		You then form a Bitcoin payment which requires both my public key and password K. In order to redeem this transaction I must disclose K, the key you need to decrypt Ex and give you your solution. So neither of us can cheat, so no trust is required.

	The reason this isn't something people are using yet is because while the academics have proven it to be possible, actually converting complicated programs like compositions of ciphers and hash-functions into zero-knowledge proofs with useful levels of performance currently requires toolkits that are not yet publicly available. However, the [~~http~~://~~scipr-lab~~.org/ ~~SCIPR Lab team] have claimed they will open source their software some time in 2014. "[http:~~//~~eccc.hpi-web.de~~/~~report~~/~~2013/165~~/~~download/ Verifying computations without reexecuting them: from theoretical possibility to near practicality~~]~~" is~~ a ~~good paper that gives an overview~~ of ~~progress fo far~~.		The [https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/ first ZKCP] was performed on the Bitcoin network in 2016, after a number of years waiting for sufficiently powerful general purpose ZKPs to become practically available.

	==But what if they're just anti-social and don't redeem the txn?==		==But what if they're just anti-social and don't redeem the txn?==
Line 55:		Line 55:
	Alternatively, you could construct the payment as an anyone can pay transaction where the output is greater than the input you provide. You would give him this transaction, then he would add funds of his own and announce it and wait for it to be mined before announcing the key in the transaction spending it. This way he could not lock up your funds without locking up funds of his own.		Alternatively, you could construct the payment as an anyone can pay transaction where the output is greater than the input you provide. You would give him this transaction, then he would add funds of his own and announce it and wait for it to be mined before announcing the key in the transaction spending it. This way he could not lock up your funds without locking up funds of his own.

	==~~Improving~~ privacy==		==Further mproving privacy==
			Many other transaction types also use the same hash locked pattern, but privacy can be further improved:
	A ZK-payment can be transformed using the [https://bitcointalk.org/index.php?topic=321228.0 CoinSwap] approach where they payer first pays into an ordinary 2-of-2 escrow+refund with the payee. The then would perform the ZK-payment transactions described above externally to the Bitcoin network, and if everything goes through without cheating the payer just signs a 2-of-2 release to pay the payee directly, without disclosing to the network that a hashlocked transaction was used. If the payer fails to release the escrow directly, the payee can just release it by announcing the hashlock and hashlock redeem.		A ZK-payment can be transformed using the [https://bitcointalk.org/index.php?topic=321228.0 CoinSwap] approach where they payer first pays into an ordinary 2-of-2 escrow+refund with the payee. The then would perform the ZK-payment transactions described above externally to the Bitcoin network, and if everything goes through without cheating the payer just signs a 2-of-2 release to pay the payee directly, without disclosing to the network that a hashlocked transaction was used. If the payer fails to release the escrow directly, the payee can just release it by announcing the hashlock and hashlock redeem.

Mike: /* Zero knowledge proof to binding */ fix link

2014-05-07T13:15:09Z

Zero knowledge proof to binding: fix link

← Older revision		Revision as of 13:15, 7 May 2014
Line 23:		Line 23:
	* H() could be a password hashing algorithm and you're looking for the password that gives you a particular hash in order to crack it.		* H() could be a password hashing algorithm and you're looking for the password that gives you a particular hash in order to crack it.
	* Perhaps H() is a complicated program that decides if a piece of music is one you would find beautiful (i.e. Y is a true/false output)		* Perhaps H() is a complicated program that decides if a piece of music is one you would find beautiful (i.e. Y is a true/false output)
	* H() could be a program that verifies possession of a valid [http://en.wikipedia.org/wiki/~~Machine-readable_passport~~ machine readable travel document] issued to a particular person. In this case, you would be able to define a payment to someone based on some arbitrary attributes about them, such as their name + date of birth, or perhaps by providing a photo of their face that's then matched against the travel document using the Eigenfaces algorithm. There would be no need to obtain a public key from them ahead of time meaning that, for example, you could send money to someone who was only just born and doesn't yet have a wallet.		* H() could be a program that verifies possession of a valid [http://en.wikipedia.org/wiki/Biometric_passport machine readable travel document] issued to a particular person. In this case, you would be able to define a payment to someone based on some arbitrary attributes about them, such as their name + date of birth, or perhaps by providing a photo of their face that's then matched against the travel document using the Eigenfaces algorithm. There would be no need to obtain a public key from them ahead of time meaning that, for example, you could send money to someone who was only just born and doesn't yet have a wallet.
	* H() could be a program that interprets another program on some secret input and yields true if the input data manages to put the program into a corrupted state. This would allow security researchers to sell exploits to software developers so they can be fixed, but in an anonymous and low trust way.		* H() could be a program that interprets another program on some secret input and yields true if the input data manages to put the program into a corrupted state. This would allow security researchers to sell exploits to software developers so they can be fixed, but in an anonymous and low trust way.

Mike: /* Zero knowledge proof to binding */ Add more examples of what H() could be. Fold practicality update at the end of the page into main text.

2014-05-07T13:13:49Z

Zero knowledge proof to binding: Add more examples of what H() could be. Fold practicality update at the end of the page into main text.

← Older revision		Revision as of 13:13, 7 May 2014
Line 17:		Line 17:
	Let H() be a complicated computer program. For some H(X)=Y you want to know some X that gives you a particular Y.		Let H() be a complicated computer program. For some H(X)=Y you want to know some X that gives you a particular Y.

	~~Perhaps H() is a password hashing algorithm~~ and ~~you~~'~~re looking for the password that gives you a particular hash in order~~ to ~~crack~~ it~~. Or perhaps H() is a complicated program that decides if a image is one~~ you ~~would find beautiful (e~~.g. ~~Y is either~~ zero ~~or one, and you want some X where Y==1)~~.		Say I happen to _know_ some X that answers your question... and I'd like to sell it to you. But we don't trust each other at all, and because we're computer geeks we have no friends who can act as trusted mediators. Can we make this exchange using Bitcoin with zero trust? The answer turns out to be yes.

	~~Say I happen to _know_~~ some X that answers your question... and I'd like to sell it to you. But we don't trust each other at all, and because we're computer geeks we have no friends who can act as trusted mediators. Can we make this exchange using Bitcoin with zero trust? Yes.		Here are some examples of what H() could be:

	A [https://en.wikipedia.org/wiki/Zero-knowledge_proof zero-knowledge proof] lets someone prove a mathematical fact to another person without teaching them anything about the fact itself. It has been proven that you can convert any computer program into a zero-knowledge proof(~~e.g.~~ [http://en.wikipedia.org/wiki/IP_%28complexity%29#PSPACE_is_a_subset_of_IP PSPACE⊂IP] <!-- IIRC there is a better more direct statement about this someplace but I forget what to look for, please provide a better link -->). So, using a zero-knowledge proof I could prove to you that I know some X such that H(X)=Y ... which is helpful but it's not enough because you could pay me and I could not tell you the answer (or I could tell you and then you don't pay). Here is where the password locked transactions come in.		* H() could be a password hashing algorithm and you're looking for the password that gives you a particular hash in order to crack it.
			* Perhaps H() is a complicated program that decides if a piece of music is one you would find beautiful (i.e. Y is a true/false output)
			* H() could be a program that verifies possession of a valid [http://en.wikipedia.org/wiki/Machine-readable_passport machine readable travel document] issued to a particular person. In this case, you would be able to define a payment to someone based on some arbitrary attributes about them, such as their name + date of birth, or perhaps by providing a photo of their face that's then matched against the travel document using the Eigenfaces algorithm. There would be no need to obtain a public key from them ahead of time meaning that, for example, you could send money to someone who was only just born and doesn't yet have a wallet.
			* H() could be a program that interprets another program on some secret input and yields true if the input data manages to put the program into a corrupted state. This would allow security researchers to sell exploits to software developers so they can be fixed, but in an anonymous and low trust way.

			A [https://en.wikipedia.org/wiki/Zero-knowledge_proof zero-knowledge proof] lets someone prove a mathematical fact to another person without teaching them anything about the fact itself. It has been proven that you can convert any computer program into a zero-knowledge proof (this is referred to mathematically as [http://en.wikipedia.org/wiki/IP_%28complexity%29#PSPACE_is_a_subset_of_IP PSPACE⊂IP] <!-- IIRC there is a better more direct statement about this someplace but I forget what to look for, please provide a better link -->). So, using a zero-knowledge proof I could prove to you that I know some X such that H(X)=Y ... which is helpful but it's not enough because you could pay me and I could not tell you the answer (or I could tell you and then you don't pay). Here is where the password locked transactions come in.

	First I encrypt X with random key K, Ex=AES(X,K).		First I encrypt X with random key K, Ex=AES(X,K).
Line 40:		Line 45:
	You then form a Bitcoin payment which requires both my public key and password K. In order to redeem this transaction I must disclose K, the key you need to decrypt Ex and give you your solution. So neither of us can cheat, so no trust is required.		You then form a Bitcoin payment which requires both my public key and password K. In order to redeem this transaction I must disclose K, the key you need to decrypt Ex and give you your solution. So neither of us can cheat, so no trust is required.

	The reason this isn't something people are using yet is because while the academics have proven it to be possible actually converting complicated programs like compositions of ciphers and hash-functions into zero-knowledge proofs ~~is apparently~~ not ~~something anyone has figured out how to do practically~~.		The reason this isn't something people are using yet is because while the academics have proven it to be possible, actually converting complicated programs like compositions of ciphers and hash-functions into zero-knowledge proofs with useful levels of performance currently requires toolkits that are not yet publicly available. However, the [http://scipr-lab.org/ SCIPR Lab team] have claimed they will open source their software some time in 2014. "[http://eccc.hpi-web.de/report/2013/165/download/ Verifying computations without reexecuting them: from theoretical possibility to near practicality]" is a good paper that gives an overview of progress fo far.

	~~''2013 Update'': This is rapidly changing and~~ [http://scipr-lab.org/ ~~practical systems~~] ~~now appear practically possible~~. "[http://eccc.hpi-web.de/report/2013/165/download/ Verifying computations without reexecuting them: from theoretical possibility to near practicality]" ~~gives~~ a good overview, of ~~recent~~ progress.

	==But what if they're just anti-social and don't redeem the txn?==		==But what if they're just anti-social and don't redeem the txn?==

Gmaxwell: /* Zero knowledge proof to binding */ survey link

2013-12-04T18:21:20Z

Zero knowledge proof to binding: survey link

← Older revision		Revision as of 18:21, 4 December 2013
Line 40:		Line 40:
	You then form a Bitcoin payment which requires both my public key and password K. In order to redeem this transaction I must disclose K, the key you need to decrypt Ex and give you your solution. So neither of us can cheat, so no trust is required.		You then form a Bitcoin payment which requires both my public key and password K. In order to redeem this transaction I must disclose K, the key you need to decrypt Ex and give you your solution. So neither of us can cheat, so no trust is required.

	The reason this isn't something people are using yet is because while the academics have proven it to be possible actually converting complicated programs like compositions of ciphers and hash-functions into zero-knowledge proofs is apparently not something anyone has figured out how to do practically. ''2013 Update'': This is rapidly changing and [http://scipr-lab.org/ practical systems] now appear practically possible.		The reason this isn't something people are using yet is because while the academics have proven it to be possible actually converting complicated programs like compositions of ciphers and hash-functions into zero-knowledge proofs is apparently not something anyone has figured out how to do practically.

			''2013 Update'': This is rapidly changing and [http://scipr-lab.org/ practical systems] now appear practically possible. "[http://eccc.hpi-web.de/report/2013/165/download/ Verifying computations without reexecuting them: from theoretical possibility to near practicality]" gives a good overview, of recent progress.

	==But what if they're just anti-social and don't redeem the txn?==		==But what if they're just anti-social and don't redeem the txn?==

Mike: /* Zero nowledge proof to binding */

2013-12-04T16:03:10Z

Zero nowledge proof to binding

← Older revision		Revision as of 16:03, 4 December 2013
Line 13:		Line 13:
	There are a couple uses but I'll give an example here of one of the more impressive and and far-out ones:		There are a couple uses but I'll give an example here of one of the more impressive and and far-out ones:

	===Zero ~~nowledge~~ proof to binding===		===Zero knowledge proof to binding===

	Let H() be a complicated computer program. For some H(X)=Y you want to know some X that gives you a particular Y.		Let H() be a complicated computer program. For some H(X)=Y you want to know some X that gives you a particular Y.