The first successful Zero-Knowledge Contingent Payment
6 messages, 26 Feb 2016. Started by Gregory Maxwell.
Gregory Maxwell (3), Tier Nolan (2), Sergio Demian Lerner
I am happy to announce the first successful Zero-Knowledge Contingent Payment (ZKCP) on the Bitcoin network.
ZKCP is a transaction protocol that allows a buyer to purchase information from a seller using Bitcoin in a manner which is private, scalable, secure, and which doesn’t require trusting anyone: the expected information is transferred if and only if the payment is made. The buyer and seller do not need to trust each other or depend on arbitration by a third party.
Imagine a movie-style “briefcase swap” (one party with a briefcase full of cash, another containing secret documents), but without the potential scenario of one of the cases being filled with shredded newspaper and the resulting exciting chase scene.
An example application would be the owners of a particular make of e-book reader cooperating to purchase the DRM master keys from a failing manufacturer, so that they could load their own documents on their readers after the vendor’s servers go offline. This type of sale is inherently irreversible, potentially crosses multiple jurisdictions, and involves parties whose financial stability is uncertain–meaning that both parties either take a great deal of risk or have to make difficult arrangement. Using a ZKCP avoids the significant transactional costs involved in a sale which can otherwise easily go wrong.
In today’s transaction I purchased a solution to a 16x16 Sudoku puzzle for 0.10 BTC from Sean Bowe, a member of the Zcash team, as part of a demonstration performed live at Financial Cryptography 2016 in Barbados. I played my part in the transaction remotely from California.
The transfer involved two transactions:
8e5df5f792ac4e98cca87f10aba7947337684a5a0a7333ab897fb9c9d616ba9e 200554139d1e3fe6e499f6ffb0b6e01e706eb8c897293a7f6a26d25e39623fae
Almost all of the engineering work behind this ZKCP implementation was done by Sean Bowe, with support from Pieter Wuille, myself, and Madars Virza.
Read more, including technical details at https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/
[I hope to have a ZKCP sudoku buying faucet up shortly. :) ]
Congratulations!
It a property of the SKCP system that the person who performed the trusted setup cannot extract any information from a proof?
In other words, is it proven hard to obtain information from a proof by the buyer?
On Fri, Feb 26, 2016 at 6:42 PM, Gregory Maxwell via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (52 lines)
> I am happy to announce the first successful Zero-Knowledge Contingent > Payment (ZKCP) on the Bitcoin network. > > ZKCP is a transaction protocol that allows a buyer to purchase > information from a seller using Bitcoin in a manner which is private, > scalable, secure, and which doesn’t require trusting anyone: the > expected information is transferred if and only if the payment is > made. The buyer and seller do not need to trust each other or depend > on arbitration by a third party. > > Imagine a movie-style “briefcase swap” (one party with a briefcase > full of cash, another containing secret documents), but without the > potential scenario of one of the cases being filled with shredded > newspaper and the resulting exciting chase scene. > > An example application would be the owners of a particular make of > e-book reader cooperating to purchase the DRM master keys from a > failing manufacturer, so that they could load their own documents on > their readers after the vendor’s servers go offline. This type of sale > is inherently irreversible, potentially crosses multiple > jurisdictions, and involves parties whose financial stability is > uncertain–meaning that both parties either take a great deal of risk > or have to make difficult arrangement. Using a ZKCP avoids the > significant transactional costs involved in a sale which can otherwise > easily go wrong. > > In today’s transaction I purchased a solution to a 16x16 Sudoku puzzle > for 0.10 BTC from Sean Bowe, a member of the Zcash team, as part of a > demonstration performed live at Financial Cryptography 2016 in > Barbados. I played my part in the transaction remotely from > California. > > The transfer involved two transactions: > > 8e5df5f792ac4e98cca87f10aba7947337684a5a0a7333ab897fb9c9d616ba9e > 200554139d1e3fe6e499f6ffb0b6e01e706eb8c897293a7f6a26d25e39623fae > > Almost all of the engineering work behind this ZKCP implementation was > done by Sean Bowe, with support from Pieter Wuille, myself, and Madars > Virza. > > > Read more, including technical details at > > https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/ > > [I hope to have a ZKCP sudoku buying faucet up shortly. :) ] > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
On Fri, Feb 26, 2016 at 11:06 PM, Sergio Demian Lerner <sergio.d.lerner@gmail•com> wrote:
Quoted text (7 lines)
> Congratulations! > > It a property of the SKCP system that the person who performed the trusted > setup cannot extract any information from a proof? > > In other words, is it proven hard to obtain information from a proof by the > buyer?
Yes, the secrecy is information theoretic (assuming no implementation bugs); beyond the truth of the outcome. This holds even if the initialization is malicious.
The soundness of this scheme is computational-- we're trusting a deep stack of cryptographic assumptions that the proofs cannot be forged.
That is very interesting.
There has been some recent discussion about atomic cross chain transfers between Bitcoin and legacy altcoins. For this purpose a legacy altcoin is one that has strict IsStandard() rules and none of the advanced script opcodes.
It has a requirement that Bob sends Alice a pair [hash_of_bob_private_key, bob_public_key]. Bob has to prove that the hash is actually the result of hashing the private key that matches bob_public_key.
This can be achieved with a cut-and-choose scheme. It uses a fee so that an attacker loses money on average. It is vulnerable to an attacker who doesn't mind losing money as long as the target loses money too.
Bob would have to prove that he has an x such that
xG = <bob_public_key> hash(x) = hash_of_bob_private_key
Is the scheme fast enough such that an elliptic curve multiply would be feasible? You mention 20 seconds for 5 SHA256 operations, so I am guessing no?
On Fri, Feb 26, 2016 at 11:06 PM, Sergio Demian Lerner via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (71 lines)
> Congratulations! > > It a property of the SKCP system that the person who performed the trusted > setup cannot extract any information from a proof? > > In other words, is it proven hard to obtain information from a proof by > the buyer? > > On Fri, Feb 26, 2016 at 6:42 PM, Gregory Maxwell via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation•org> wrote: > >> I am happy to announce the first successful Zero-Knowledge Contingent >> Payment (ZKCP) on the Bitcoin network. >> >> ZKCP is a transaction protocol that allows a buyer to purchase >> information from a seller using Bitcoin in a manner which is private, >> scalable, secure, and which doesn’t require trusting anyone: the >> expected information is transferred if and only if the payment is >> made. The buyer and seller do not need to trust each other or depend >> on arbitration by a third party. >> >> Imagine a movie-style “briefcase swap” (one party with a briefcase >> full of cash, another containing secret documents), but without the >> potential scenario of one of the cases being filled with shredded >> newspaper and the resulting exciting chase scene. >> >> An example application would be the owners of a particular make of >> e-book reader cooperating to purchase the DRM master keys from a >> failing manufacturer, so that they could load their own documents on >> their readers after the vendor’s servers go offline. This type of sale >> is inherently irreversible, potentially crosses multiple >> jurisdictions, and involves parties whose financial stability is >> uncertain–meaning that both parties either take a great deal of risk >> or have to make difficult arrangement. Using a ZKCP avoids the >> significant transactional costs involved in a sale which can otherwise >> easily go wrong. >> >> In today’s transaction I purchased a solution to a 16x16 Sudoku puzzle >> for 0.10 BTC from Sean Bowe, a member of the Zcash team, as part of a >> demonstration performed live at Financial Cryptography 2016 in >> Barbados. I played my part in the transaction remotely from >> California. >> >> The transfer involved two transactions: >> >> 8e5df5f792ac4e98cca87f10aba7947337684a5a0a7333ab897fb9c9d616ba9e >> 200554139d1e3fe6e499f6ffb0b6e01e706eb8c897293a7f6a26d25e39623fae >> >> Almost all of the engineering work behind this ZKCP implementation was >> done by Sean Bowe, with support from Pieter Wuille, myself, and Madars >> Virza. >> >> >> Read more, including technical details at >> >> https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/ >> >> [I hope to have a ZKCP sudoku buying faucet up shortly. :) ] >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation•org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > >
On Fri, Feb 26, 2016 at 11:33 PM, Tier Nolan via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (6 lines)
> That is very interesting. > > There has been some recent discussion about atomic cross chain transfers > between Bitcoin and legacy altcoins. For this purpose a legacy altcoin is > one that has strict IsStandard() rules and none of the advanced script > opcodes.
One might wonder why anyone would want to own coins that couldn't keep up technologically, but to each his own. (especially one defunct enough that it can't even update IsStandard rules...)
I don't think it's infeasible to do the EC multiply in a snark, but an efficient implementation would be a lot of work. You'd probably want to build a circuit for the field operations using 128 bit operations. Fortunately the overall operation is pretty easy to directly convert into a circuit (e.g. no branching).
Why not use the single-show-signature scheme I came up with a while back on the Bitcoin side to force the bitcoin side to reveal a private key?
http://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000344.html
On Fri, Feb 26, 2016 at 11:45 PM, Gregory Maxwell <greg@xiph•org> wrote:
Quoted text (7 lines)
> Why not use the single-show-signature scheme I came up with a while > back on the Bitcoin side to force the bitcoin side to reveal a private > key? > > > http://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000344.html >
Thanks for the info, I will give it a look.