For a decentralized currency, centralized escrows seem to be the norm for BitCoin today. An example:
Alice wants to buy $5 USD worth of BitCoins from Bob, but neither Alice nor Bob fully trust the other, so they go to a site they both trust--say Mt. Gox. There they deposit their respective monies and there they have Mt. Gox make the exchange for them.
No offense to Mt. Gox (a site I like), but can we do without its escrow service?
An almost distributed alternative:
- Charlie, a trusted third-party, generates a BitCoin private key.
- Charlie then uses the Unix command split to split the private key in half--giving one half to Alice and one half to Bob.
- Bob deposits $5 USD worth of BitCoins into the split BitCoin account;
- Alice verifies the transaction using the public block;
- Alice sends $5 USD to Bob by PayPal;
- Bob verifies the PayPal transaction;
- Bob sends Alice his half of the split private key so Alice can access the BitCoins he deposited earlier.
(For simplicity I omit part of the PayPal details like who pays the transaction fee and how long you should wait to avoid chargeback fraud. I also omit any incentive for Bob to perform the final step.)
More advanced almost-distributed examples can be made if we substitute something more sophisticated for the Unix command split. For example: a Shamir's secret sharing scheme implementation like ssss. A utility like ssss allows Alice and Bob to appoint an arbiter in case they get in a disagreement.
The problem with all of this, of course, is that we must trust Charlie to not abuse the full copy of the private key he creates.
The ideal solution would be for Alice and Bob to each generate half of the private key on their own. I don't fully understand the math used in modern keypairs, but I doubt this is possible with the current algorithm.
Is there an alternative way for Alice and Bob to each acquire half of a private key without giving the whole key to any party?
 See: http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing