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