Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 1E4F8CBC for ; Wed, 13 Dec 2017 22:08:49 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f68.google.com (mail-wm0-f68.google.com [74.125.82.68]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 777034F6 for ; Wed, 13 Dec 2017 22:08:47 +0000 (UTC) Received: by mail-wm0-f68.google.com with SMTP id r78so7837642wme.5 for ; Wed, 13 Dec 2017 14:08:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:reply-to:from:date:message-id:subject:to; bh=yjxYPmuoIRPvV30F7MwYuolFwfNfBLzDcm6rdd9qWts=; b=PioamIpDt8/iQ+GVsMKFKWKt+pkYaGVqre9+pb6soOu/dQH5cDTv8uYNIJqu42zvMu 7AdJkQUE+8eb+CptJcqCSoOBOjdBUFW//inhdn1Emx63Qj1tbe7ujZcv8NzbtsdlZpBs XP/JlVBxpmATDqES7rAmK+mu2R5c+K6cqzepV3Tfa9L6L7AnxLbvM+oYjVZxLcURYW5I ybVzVGqlj3gbuT3lOAoVjBJ53oHXvC9HOWa/3TL+bcqaYu8d4sB9OPQ2IFwZSgRYpFH2 xzckTsoHr0/19ABNvNL9jnQWk++MxpTAaFTK1dq8JKgQ2An6xazp+BatUv9AlWUqk3cI Q2nQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:reply-to:from:date:message-id :subject:to; bh=yjxYPmuoIRPvV30F7MwYuolFwfNfBLzDcm6rdd9qWts=; b=oSYXuVJvRhcGw7jL++Id8Vk5a/dj/u/dI5C8iC9EhnIc7nsloZKEcIBLSePDrRaJTB Q6KdhIMBB68A9A8p0PFLwhfIpHjpE2pTcd2Iz9nGi2Cn8pt2Lw/ub0KufXtOf7W+tBoP zmJO7rAdzJoMkNuoax+DgxmxsMXUePGTi2bCpYzoR6Clk+z+3tPaJpQXLA4j8jD9B8zL AffZZ8k/wNsup8h2VcX7oMKdFx4NAaoKOcm/zRH1KdwDVqrV8PTDXQtvqmBRh9UCjzRI 3QDgC6CPIYgpzlrHXN13J6hvvUC6OxMXLPny6/Jvb3nIcOqFDYOxhC+b8omhwYYVQBvL Lieg== X-Gm-Message-State: AKGB3mIyrnT+7KeRPDzibdbw/G/pg/n/zfQ84QEaNaYBP9Btd9Iutvdv cFp35Q+PXF+y3xKOJLs4Z+IvZ0s5yu6A9kv1O5X9ft2w X-Google-Smtp-Source: ACJfBov4R988wNo5p2MtFnYdH4yU7NTq4+2B+xj2PNwFDIVB52VCG73JTwkl6yzYx5oYlVhYaoacR9dWz8vh/9MiN5E= X-Received: by 10.80.182.5 with SMTP id b5mr9492438ede.227.1513202925849; Wed, 13 Dec 2017 14:08:45 -0800 (PST) MIME-Version: 1.0 Received: by 10.80.148.125 with HTTP; Wed, 13 Dec 2017 14:08:05 -0800 (PST) Reply-To: nathan.f77@gmail.com From: Nathan Broadbent Date: Thu, 14 Dec 2017 05:08:05 +0700 Message-ID: To: bitcoin-dev@lists.linuxfoundation.org Content-Type: multipart/alternative; boundary="94eb2c0e3950de522305604002ce" X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM, HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Wed, 13 Dec 2017 22:12:44 +0000 Subject: [bitcoin-dev] BIP Proposal: Bitcoin nodes could be used as a trusted third party that broadcasts encrypted transactions X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 13 Dec 2017 22:08:49 -0000 --94eb2c0e3950de522305604002ce Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hello, I would like propose a way for full Bitcoin nodes to be used as simple trusted third parties (TTPs) [1]. The idea is that parties would work together to randomly select a Bitcoin node. The parties would then perform a secure multi-party computation (MPC) [2], where every party has a secret value that they don't want to share with anyone else. The result of this computation would be a Bitcoin transaction that was encrypted by the random node's public key. Any of the parties could then send the encrypted transaction to this node. The node would decrypt the transaction and broadcast it to its peers. Nodes would receive a small fee for providing this service. *Mental Poker* Mental Poker [3] is where you play a fair game of poker without the need for a trusted third party who moderates the game. A paper titled "A Toolbox for Mental Card Games" [4] describes how you can use MPC to play decentralized poker. This works great when you're just playing for fun, but everything falls apart when you're playing for Bitcoin. The problem is that MPC is not fair, because one party will always learn the outcome of a computation before anyone else. If they find out that they lost the round, they can abort the computation and prevent anyone else from gaining that information. The other players will know what happened, but they can't force the cheater to broadcast the Bitcoin transaction. The game would just be stalled, and people would use their timelock transactions to get their money back. In a paper titled "How to Use Bitcoin to Play Decentralized Poker" [5], the authors describe how penalties could be used to force players into revealing the outcome. If one player aborts the computation after learning that they lost, they would automatically pay a penalty to the other players= . There's one big problem with this penalty system: A group of dishonest players can simply ignore that player and force them to pay the penalty. The outcome of the round doesn't even matter. It would be easy to set up an army of bots that never finishes a round and just collects penalties. *Mental Poker With Random Bitcoin Nodes as TTPs* The fairness problem might be solved if a randomly selected Bitcoin node served as a simple TTP. The node could provide a public key, and result of the MPC would then be an *encrypted* Bitcoin transaction that could only be decrypted and broadcast by that randomly selected node. No players would gain any information about the outcome until they saw the unconfirmed transaction in the mempool. The following example is very long and detailed (as is this whole email!), but it demonstrates all of the functions that a node would need to perform. *Example Protocol* Alice and Bob choose a random full Bitcoin node that supports this new protocol. (Alice might shuffle all of the IP addresses and send Bob the Merkle tree root hash. Bob then picks one index at random, and Alice sends Bob the full Merkle tree. Now they've both committed to a random node.) Alice sends the request to the randomly selected node. The node generates a one-time-use key pair, and encrypts the one-time private key using its static public key. It also signs "" using its static private key. *Note: This one-time-use key pair is generated so that Alice and Bob can encrypt up to 32 bytes of metadata and send this with the one-time key and their encrypted transaction. The node would broadcast the transaction and return their decrypted data. Also note that the node would use the same static key pair as P2P encryption. (BIP151) [6]* The node sends Alice the fee amount (maybe 20 Satoshis), an address where she should send the fee, the node's static public key, and the one-time public key / encrypted private key / signature. Alice sends this data to Bob. Bob connects to the node himself, and fetches the fee and static public key. Bob uses the public key and signature to verify that the one-time key pair was generated and signed by this node. Alice and Bob now play a round of decentralized poker. At the end of the round, they use MPC to create an encrypted Bitcoin transaction that sends the money to the winner. The MPC also has an output for the encrypted showdown (the cards that are revealed at the end of the round.) Either Bob or Alice (or both) now send this encrypted transaction to the node, plus the encrypted showdown, the one-time key data. The node then decrypts and verifies the Bitcoin transaction. If it's valid and it contains the correct fee output, it broadcasts the transaction to its peers. The node also decrypts the one-time private key, and uses the decrypted private key to decrypt the metadata that was sent. The node returns the decrypted metadata to the sender, who now knows the other player's cards. Note that one player can still abort the computation and send the encrypted transaction as soon as they have it, which prevents the other player from learning about the cards. A solution could be that the node keeps the decrypted metadata in memory for a short time, and the other player can access that data by sending the one-time-use public key. *Example Protocol Notes:* This example only uses a single TTP node. It would be far more secure if the parties randomly select a large number of nodes. The encrypted transaction would contain fee outputs for every node. Shamir's Secret Sharing could be used so that *n* of *t* nodes are needed to decrypt the transaction. The MPC could encrypt the individual key parts using each node's public key. The node would either broadcast a fully decrypted transaction, or return a partially decrypted transaction to the sender. People might be tempted to use the seed nodes more often, because they're hard-coded in the Bitcoin source code. Don't do that. For important transactions, you should just use a large number of TTP nodes (e.g. require decryption by 20 out of 50 randomly selected nodes.) *Real-World Applications* People could anonymously vote on the distribution of funds without revealing their vote to anyone. No-one would know the outcome of the vote until the transaction was broadcast. It would also be possible to create a fully decentralized Bitcoin lottery. Sorry for the incredibly long email. I hope you found this interesting! I've probably made a few mistakes, but I hope I've explained things clearly, and I look forward to reading your feedback. Best Regards, Nathan Broadbent *References:* [1] https://en.wikipedia.org/wiki/Trusted_third_party [2] https://en.wikipedia.org/wiki/Secure_multi-party_computation [3] https://en.wikipedia.org/wiki/Mental_poker [4] http://www.cs.miami.edu/home/burt/projects/smpc/doc/schindelhauer98toolbox.= pdf [5] http://people.csail.mit.edu/ranjit/papers/poker.pdf [6] https://github.com/bitcoin/bips/blob/master/bip-0151.mediawiki =E2=80=8C --94eb2c0e3950de522305604002ce Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hello,

I would like pro= pose a way for full Bitcoin nodes to be used as simple trusted third partie= s (TTPs) [1]. The idea is that parties would work together to randomly sele= ct a Bitcoin node. The parties would then perform a secure multi-party comp= utation (MPC) [2], where every party has a secret value that they don't= want to share with anyone else. The result of this computation would be a = Bitcoin transaction that was encrypted by the random node's public key.= Any of the parties could then send the encrypted transaction to this node.= The node would decrypt the transaction and broadcast it to its peers. Node= s would receive a small fee for providing this service.


Mental Poker

Mental Poker [3] is where you play a fair game of poker without the need = for a trusted third party who moderates the game. A paper titled "A To= olbox for Mental Card Games" [4] describes how you can use MPC to play= =C2=A0decentralized poker.

This works great when y= ou're just playing for fun, but everything falls apart when you're = playing for Bitcoin. The problem is that MPC is not fair, because one party= will always learn the outcome of a computation before anyone else. If they= find out that they lost the round, they can abort the computation and prev= ent anyone else from gaining that information. The other players will know = what happened, but they can't force the cheater to broadcast the Bitcoi= n transaction. The game would just be stalled, and people would use their t= imelock transactions to get their money back.

In a= paper titled "How to Use Bitcoin to Play Decentralized Poker" [5= ], the authors describe how penalties could be used to force players into r= evealing the outcome. If one player aborts the computation after learning t= hat they lost, they would automatically pay a penalty to the other players.=

There's one big problem with this penalty sys= tem: A group of dishonest players can simply ignore that player and force t= hem to pay the penalty. The outcome of the round doesn't even matter. I= t would be easy to set up an army of bots that never finishes a round and j= ust collects penalties.


Mental P= oker With Random Bitcoin Nodes as TTPs

The fairness problem might be solved if a randomly selected Bitcoin node= served as a simple TTP. The node could provide a public key, and result of= the MPC would then be an encrypted Bitcoin transaction that could o= nly be decrypted and broadcast by that randomly selected node. No players w= ould gain any information about the outcome until they saw the unconfirmed = transaction in the mempool.

The following example = is very long and detailed (as is this whole email!), but it demonstrates al= l of the functions that a node would need to perform.

<= div>
Example Protocol

Alice a= nd Bob choose a random full Bitcoin node that supports this new protocol. (= Alice might shuffle all of the IP addresses and send Bob the Merkle tree ro= ot hash. Bob then picks one index at random, and Alice sends Bob the full M= erkle tree. Now they've both committed to a random node.)
Alice sends the request to the randomly selected node. The node= generates a one-time-use key pair, and encrypts the one-time private key u= sing its static public key. It also signs "<one-time-use public key= ><encrypted one-time-use=C2=A0private key>" using its static = private key.

Note: This one-time-use key p= air is generated so that Alice and Bob can encrypt up to 32 bytes of metada= ta and send this with the one-time key and=C2=A0their encrypted transaction= . The node would broadcast the transaction and return their decrypted data.= Also note that the node would use the same static key pair as P2P encrypti= on. (BIP151) [6]

The node sends Alice=C2= =A0the fee amount (maybe 20 Satoshis), an address where she should send the= fee, the node's static=C2=A0public key, and the=C2=A0one-time public k= ey / encrypted private key / signature.

Alice = sends this data to Bob. Bob connects to the node himself, and fetches the f= ee and static public key. Bob uses the public key and signature to verify t= hat the one-time key pair was generated and signed by this node.
=
Alice and Bob now play a round of decentralized poker. At th= e end of the round, they use MPC to create an encrypted Bitcoin transaction= that sends the money to the winner. The MPC also has an output for the enc= rypted showdown (the cards that are revealed at the end of the round.)

Either Bob or Alice (or both) now send this encrypted trans= action to the node, plus the encrypted showdown, the one-time key data.
The node then decrypts and verifies the Bitcoin transaction= . If it's valid and it contains the correct fee output, it broadcasts t= he transaction to its peers. The node also decrypts the one-time private ke= y, and uses the decrypted private key to decrypt the metadata that was sent= .=C2=A0The node returns the decrypted metadata to the sender, who now knows= the other player's cards.

Note that one playe= r can still abort the computation and send the encrypted transaction as soo= n as they have it, which prevents the other player from learning about the = cards. A solution could be that the node keeps the decrypted metadata in me= mory for a short time, and the other player can access that data by sending= the one-time-use public key.


=
Example Protocol Notes:

This exam= ple only uses a single TTP node. It would be far more secure if the parties= randomly select a large number of nodes. The encrypted transaction would c= ontain fee outputs for every node.

Shamir's Se= cret Sharing could be used so that n of t nodes are needed to= decrypt the transaction. The MPC could encrypt the individual key parts us= ing each node's public key. The node would either broadcast a fully dec= rypted transaction, or return a partially decrypted transaction to the send= er.

People might be tempted to use the seed nodes = more often, because they're hard-coded in the Bitcoin source code. Don&= #39;t do that. For important transactions, you should just use a large numb= er of TTP nodes (e.g. require decryption by 20 out of 50 randomly selected = nodes.)


Real-World= Applications

People could anonymously vote on= the distribution of funds without revealing their vote to anyone. No-one w= ould know the outcome of the vote until the transaction was broadcast.

It would also be possible to create a fully decentrali= zed Bitcoin lottery.



Sorry for the incredibly long email. I hope you found this interesti= ng! I've probably made a few mistakes, but I hope I've explained th= ings clearly, and I look forward to reading your feedback.
=E2=80=8C
--94eb2c0e3950de522305604002ce--