MIME-Version: 1.0
Reply-To: nathan.f77@gmail.com
From: Nathan Broadbent <nathan.f77@gmail.com>
Date: Thu, 14 Dec 2017 05:08:05 +0700
Message-ID: <CAPXHQbOpwmL2LxbwDByJ++CGBd+Mnv6mmJbnPVifVDP7fJAU=Q@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary="94eb2c0e3950de522305604002ce"
Subject: [bitcoin-dev] BIP Proposal: Bitcoin nodes could be used as a
 trusted third party that broadcasts encrypted transactions
Precedence: list

--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 "<one-time-use public key><encrypted
one-time-use private key>" 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

<div dir=3D"ltr"><div>Hello,</div><div><br></div><div><div>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&#39;t=
 want to share with anyone else. The result of this computation would be a =
Bitcoin transaction that was encrypted by the random node&#39;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.</div><div><br></div=
></div><div><br></div><div><b>Mental Poker</b></div><div><br></div><div><di=
v>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 &quot;A To=
olbox for Mental Card Games&quot; [4] describes how you can use MPC to play=
=C2=A0decentralized poker.</div><div><br></div><div>This works great when y=
ou&#39;re just playing for fun, but everything falls apart when you&#39;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&#39;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.</div><div><br></div><div>In a=
 paper titled &quot;How to Use Bitcoin to Play Decentralized Poker&quot; [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.=
</div><div><br></div><div>There&#39;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&#39;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.</div><div><br></div><div><br></div><div><b>Mental P=
oker With Random Bitcoin Nodes as TTPs</b><br></div><div><br></div></div><d=
iv>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 <i>encrypted</i> 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.</div><div><br></div><div>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><div><br></div><=
div><br></div><div><b>Example Protocol</b></div><div><br></div><div>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&#39;ve both committed to a random node.)</div><div><br=
></div><div>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 &quot;&lt;one-time-use public key=
&gt;&lt;encrypted one-time-use=C2=A0private key&gt;&quot; using its static =
private key.</div><div><div><br></div><div><i>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]</i></div></div><div><br></div><div>The node sends Alice=C2=
=A0the fee amount (maybe 20 Satoshis), an address where she should send the=
 fee, the node&#39;s static=C2=A0public key, and the=C2=A0one-time public k=
ey / encrypted private key / signature.<br></div><div><br></div><div>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.</div><div>=
<br></div><div>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.)</div=
><div><br></div>Either Bob or Alice (or both) now send this encrypted trans=
action to the node, plus the encrypted showdown, the one-time key data.<div=
><br></div><div>The node then decrypts and verifies the Bitcoin transaction=
. If it&#39;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&#39;s cards.</div><div><br></div><div>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.</div><div><div><br></div><div><br></div><div>=
<div><div><b>Example Protocol Notes:</b></div><div><br></div><div>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.</div><div><br></div><div>Shamir&#39;s Se=
cret Sharing could be used so that <i>n</i> of <i>t</i> nodes are needed to=
 decrypt the transaction. The MPC could encrypt the individual key parts us=
ing each node&#39;s public key. The node would either broadcast a fully dec=
rypted transaction, or return a partially decrypted transaction to the send=
er.</div><div><br></div><div>People might be tempted to use the seed nodes =
more often, because they&#39;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.)</div><div><b><br></b></div><div><b><br></b></div><div><b>Real-World=
 Applications</b></div><div><br></div><div>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.</div=
><div><br></div><div>It would also be possible to create a fully decentrali=
zed Bitcoin lottery.</div></div><div><br></div><div><br></div><div><br></di=
v><div>Sorry for the incredibly long email. I hope you found this interesti=
ng! I&#39;ve probably made a few mistakes, but I hope I&#39;ve explained th=
ings clearly, and I look forward to reading your feedback.</div><div><br></=
div><div><br></div><div>Best Regards,</div><div>Nathan Broadbent</div><div>=
<br></div><div><div><br></div><div><br></div><div><b>References:</b></div><=
div><br></div><div>[1]=C2=A0<a href=3D"https://en.wikipedia.org/wiki/Truste=
d_third_party">https://en.wikipedia.org/wiki/Trusted_third_party</a><br></d=
iv><div>[2] <a href=3D"https://en.wikipedia.org/wiki/Secure_multi-party_com=
putation">https://en.wikipedia.org/wiki/Secure_multi-party_computation</a><=
br></div><div>[3] <a href=3D"https://en.wikipedia.org/wiki/Mental_poker">ht=
tps://en.wikipedia.org/wiki/Mental_poker</a></div><div>[4] <a href=3D"http:=
//www.cs.miami.edu/home/burt/projects/smpc/doc/schindelhauer98toolbox.pdf">=
http://www.cs.miami.edu/home/burt/projects/smpc/doc/schindelhauer98toolbox.=
pdf</a></div><div>[5]=C2=A0<a href=3D"http://people.csail.mit.edu/ranjit/pa=
pers/poker.pdf">http://people.csail.mit.edu/ranjit/papers/poker.pdf</a></di=
v><div>[6]=C2=A0<a href=3D"https://github.com/bitcoin/bips/blob/master/bip-=
0151.mediawiki">https://github.com/bitcoin/bips/blob/master/bip-0151.mediaw=
iki</a></div></div></div></div>=E2=80=8C</div>

--94eb2c0e3950de522305604002ce--