Is a distributed private key possible? (for poker)

[luv2drnkbr]

I'm still fairly new to cryptography, but I feel like there's a way to implement this.  Is it possible with cryptography for multiple people to have one portion of a private key, and then they all interact somehow to find out what the public address is, and once that's done with, they cannot individually derive it again (or get all of the private key) without that same cooperation repeating?

This way, for example, Bob could get an address to send money to, for oh let's say a p2p poker client whose blockchain contains which parties have the necessary parts of a private key with X btc on it... and then when Bob later wants to cash out, he can simply request all the private key chunks from peers and then he pieces it together on his own computer.

So is it possible to derive a public key without any of the people who own a part of the private key being able to get access to it?  That is, is it possible put the private key together from separate chunks, do the steps to get the public key, and then display the public key and also the people who own bits of that private key, but without any of those people individually being able to know the full private key?

I feel like that might be possible, but I'm not sure.  (The "who is richer" problem is what makes me think this might somehow be possible.)  If it is possible, it could pave the way for p2p bitcoin poker without a server, and without having the blockchain contain every damned hand history...  and without having to send btc over the bitcoin network after every single hand or even after every single action within a hand.

What I'm thinking is, after a hand of poker occurs and is signed by all the players, the blockchain then simply records new balances for each player without the need for storing additional information.  So the blockchain has player balances, bitcoin public addresses of addresses in the "poker" network, and then along with each address, a list of users necessary to access that private key.  This way, the blockchain doesn't become unwieldy.

(Credit where credit is due:  I was reading about Open Transactions when I thought about the blockchain simply updating balances, which then lead me to the thought about how to deposit and cash out, which lead me to the distributed private key question.)

[Forp]

Google for "How to share a secret", a paper by Shamir. Might answer your question.

[bracek]

maybe this leads u to solution...

http://point-at-infinity.org/ssss/


edit: posted almost at the same time

[Stephen Gornick]

Is it possible with cryptography for multiple people to have This way, for example, Bob could get an address to send money to, for oh let's say a p2p poker client whose blockchain contains which parties have the necessary parts of a private key with X btc on it

Having part of the key makes the key easier to break, so that isn't a good solution if that is something you might be worried about.

You might wish to read about OP_CHECKMULTISIG.  It might be useful here.
 - http://bitcointalk.org/index.php?topic=38928.0
 - https://gist.github.com/39158239e36f6af69d6f

[Andrew Bitcoiner]

Poker is totally the wrong application for this.

[casascius]

Poker is totally the wrong application for this.

I would agree.  You don't want to be producing bitcoin transactions per hand.  Bitcoin transactions should be limited to cash-in and cash-out only.

[TTBit]

Google for "How to share a secret", a paper by Shamir. Might answer your question.

That is super cool.

Create a private key and give a share to your lawyer, college roomate, aunt Mary, neighbor, co-worker, etc. These people would never be able to come together without you being aware. However, upon your untimely death they could seek each other out, and if you have the threshold amount of shares, they can decrypt your coins.

[Meni Rosenfeld]

Secret sharing is relevant to this, but it needs a "dealer" to do the initial generation of keys, since this is about sharing of an arbitrary secret.

Doing this in a distributed way for ECDSA without changing the protocol has been discussed here.

Doing this by changing the protocol has been discussed here, as Stephen linked.

And this seems also relevant to some of your use cases.

[phillipsjk]

You can't defeat "cause and effect." You can't force any of the participants to "unlearn" what they know.

When I saw the topic title, I was assuming you were asking if there was a way for peers to securely shuffle a deck without mutual trust. It turns out, it is possible to securely suffle cards over a peer-to-peer network.

Essentially, every participant encrypts every card in the deck with its own key and shuffles it. When a specific card becomes public, every participant publishes the private key they used for that card in the deck.

Edit: author says there is no formal proof, so take with a grain of salt.

[Meni Rosenfeld]

You can't defeat "cause and effect." You can't force any of the participants to "unlearn" what they know.

What I understood is that the OP doesn't want participants to unlearn what they know, rather that they will never know. The public key should never exist. Rather, each participant will only have his own piece, and with a joint computation they can obtain a signature which is equivalent to what the private key would generate, and can be verified with the public key, but again without anyone sharing their secret or the private key ever existing.

This sounds like one of those things that seems impossible at first but cryptography comes to the rescue. I'll see Shamir today and if I get the chance I'll try to ask him about this.

Anyway, the solution for the use cases will probably not be in new cryptography but rather adding an address type which simply needs signatures from several keys to send coins.

[Elwar]

The thing about this is that you would need a wallet created at some point and then distributed unless the client is changed in such a way that the wallet is encrypted and distributed at the same time.

I had a similar question of a voting mechanism where members of a club all contribute to the same address, then they vote on how the money is spent. At the end if the vote is unanimous they all submit their slice of the encryption and the money is available for distribution to the selected address/addresses.

But the key is that once the wallet is created on any hardware, it is vulnerable to being taken by anyone with access to that hardware.

Also, for poker. What if you had a sore loser. He loses and does not give up his portion of the key. Sure you could then get everyone else together and use that amount of information to try to decrypt the rest of the key but that would take a long time if it is a small group.

I do see this as good potential for a democratic voting system though with something like a small village or club. The most ideal vote is a 100% vote, that way everyone agrees on where their money is being spent. But you cannot count on 100% because you might have that one guy who just wants to get his way and is willing to hold everyone else up to get what he wants. So the vote can then be a 100% - (X% * time). So if you have 1% not in agreement, it may take a day or two to get the money spent. If you have 10% not in agreement, it may take a week to a month...all the while having people try to deal with the 10% hold out. If 40% do not agree then it could take years, while most likely they would come up with a better solution where more people agree.

Who knows, maybe Bitcoin could revolutionize democracy.

[TiagoTiago]

Whatever the answer is, it should be called CPPKC (Captain Planet Public Key Cryptography)

[Daily Anarchist]

Poker is totally the wrong application for this.

I would agree.  You don't want to be producing bitcoin transactions per hand.  Bitcoin transactions should be limited to cash-in and cash-out only.

Who would the cashier be?

I think the whole idea would be to have the entire poker client distributed/decentralized so that there is no central server with which to shut down.

Poker is totally the wrong application for this.

I totally disagree. I think this would be an excellent application for poker. A provably fair poker game that cannot be shut down by anybody? Sign me up!

[luv2drnkbr]

I've actually got an even better layout that requires NO distribution of any kind.  All that is needed is a bootstrapping method of connecting to peers.  That's it.  The rest is handled through local WOT ratings which users can query other users for to get a faux-distributed network wide wot rating on other players, and then multiple people "host" a game and collect my with m-of-n transactions or split or multiplied private keys, which are backed up by the table in the form of secret shares in the event of disconnect.  And then the actions can be proven and signed, as well as using a version of mental poker protocol to shuffle the deck in combination with zero knowledge proofs for hole card exposure, and the host simply holds the money, and the signed hand histories are the proof of the play, so you can verify that your cashout is correct, and in the event it is, you rate the host higher.  So accurate ratings develop very quickly, and the host also rakes the game, so he has incentive to stay honest.  It actually works very well on paper, but I don't know enough to implement it, and nobody else seems even remotely interested.  :-(

[labestiol]

Mental Poker seems like an old cryptographic problem, unfortunately without solution yet (afaik).
RSA also published a dedicated paper on the topic.
Here's a nice and recent review of the problem by a cryptography blogger.

Would be nice to see it solved one day, even if it means the end of the always entertaining "online poker is rigged" debates.

[Daily Anarchist]

If a distributed poker client could be pulled off, I think we could see rake free poker.

[BkkCoins]

I believe you can do what you want right now with bitaddress.org. Each member can generate a key pair and publish their public key. All the public keys can be combined to create a master public address. You can pay into that address and only spend when all the private keys are likewise combined to make a master private key.

I tested this on bitaddress.org and it worked - so to make it easier I wrote up a simple html page that does it in one step (rather than several on bitaddress). I've pasted the html page below for others to test and try.

I'm NOT an expert in the ECC math but my limited reading and understanding is that this works in the same way as vanity address split keys work. I'd definitely get feedback from a math guru before depending on this but it seems to work in practice - the right values are produced, and I think the underlying math is ok.

Here is my html code and you will also need bitcoinjs-min.js from it's github page.

Code:

<!DOCTYPE html> 
<html lang="en"> 
<head>
    <meta charset="utf-8">
    <title>Bitcoin Key Chains Utility</title>

<script src="bitcoinjs-min.js"></script>
<script language=javascript>
function addPubKeys() {
	var keys = document.getElementById("pubkeys").value.split("\n");
	var curve = getSECCurveByName("secp256k1").getCurve();
	var result = Crypto.util.hexToBytes(keys[0]);
	keys.splice(0,1);
	keys.map(function(k){
		if (k != "") {
			var akey = ECPointFp.decodeFrom(curve, Crypto.util.hexToBytes(k));
			result = ECPointFp.decodeFrom(curve, result).add(akey).getEncoded(0);
		}
	})
	var addr = new Bitcoin.Address(Bitcoin.Util.sha256ripe160(result));
	document.getElementById("resultPub").innerHTML = addr.toString();
    }
function addPrivKeys() {
	var keys = document.getElementById("privkeys").value.split("\n");
	var result = BigInteger.fromByteArrayUnsigned(Bitcoin.ECKey.decodeString(keys[0]));
	keys.splice(0,1);
	keys.map(function(k){
		if (k != "") {
			var akey = BigInteger.fromByteArrayUnsigned(Bitcoin.ECKey.decodeString(k));
			result = result.add(akey).mod(getSECCurveByName('secp256k1').getN());
		}
	})
	document.getElementById("resultPriv").innerHTML = new Bitcoin.ECKey(result).getExportedPrivateKey();
    }
</script>
</head>
<body>
Enter multiple public keys here (one per line):<br>
<textarea id="pubkeys" rows="5" cols="90"></textarea><br>
<input value="Calculate Master Address" onclick="javascript:addPubKeys();" type="button"><br><br>
<div id="resultPub"></div><br>
Enter multiple private keys here (one per line):<br>
<textarea id="privkeys" rows="5" cols="90"></textarea><br><br>
<input value="Calculate Master Key" onclick="javascript:addPrivKeys();" type="button"><br><br>
<div id="resultPriv"></div>
</body>

I'm adding this html page into my GitHub misc repo. Please let me know if this is not mathematically sound, and I'll fix/nuke it.

edit: There is something fishy on a second test I did so I'm trying to track down what's wrong, ie. don't use except for testing. yet.

edit^2: I see now. I have to make sure blank lines are skipped. Fixed now. It works with both 3 and 5 pairs tested against bitaddress.org.

[HostFat]

This is an old good discussion about the topic:
https://bitcointalk.org/index.php?topic=1487.0