Fidelity bonds
A fidelity bond is a proposed mechanism where Bitcoins are deliberately sacrificed to make a cryptographic identity expensive to obtain. The sacrifice is done in a way that can be proven to a third party. By making the identity expensive it can be trusted not to commit unwanted acts, such as spamming message boards, or committing fraud, because upon detection of the unwanted acts the identity becomes useless, requiring the owner of the identity to purchase another one.
Mechanism
The core of the fidelity bond is the sacrifice - the mechanism by which Bitcoins are provably taken from their original owner. The Bitcoins may be given to someone else or destroyed, but regardless it must not be possible for their original owner to regain control of them.
An effective form of sacrifice is to simply create a transaction assigning the coins to an unspendable output, either an address known to not have a corresponding secret key, or to a scriptPubKey that is provably unspendable. The Bitcoins are removed from circulation forever, a criticism of this mechanism.
The Bitcoins can also be donated to a third party, such as a charity, however such donations can be controversial, allow the charity itself (or anyone with access to their funds) to purchase bonds at little or no cost, pose the problem of verifying the bonds validity in the future should the chosen charity(s) change, and finally, pose the problem of coming to a consensus on the charities themselves.
In the context of Bitcoin, miners have been proposed as a third party whom any Bitcoin user can agree should receive funds, as miners act to secure the network from attack for everyone. The value is sacrificed to miners in the form of transaction fees.
Single/Consecutive Block Sacrifices
The sacrifice can be done with transactions that pay abnormally high fees, either single such transactions, or groups of multiple ones in a row, latter intended to prevent miners themselves from creating the sacrifices and mining them in their own blocks. Problems with consecutive transaction sacrifices include the potential for gaps, as well as the large size of the proofs of the sacrifices.[1]
Announce/Commit Sacrifices
To ensure that the miner collecting the sacrificed Bitcoin is picked at random the announce/commit sacrifice was proposed.[2] First a sacrifice transaction is prepared that either sacrifices value to transaction fees, or spends coins to an Anyone-Can-Spend Output. With nLockTime the transaction is made invalid until some time in the future.
The second step is the announcement. The transaction is enclosed in another transaction as data, for instance by using a prunable output. The announcement is then broadcast and is included in the blockchain, proving that anyone could have seen the inner transaction prior to it becoming valid.
Finally the inner transaction becomes valid when the nLockTime is reached. Because mining is a random process, any miner can collect the value sacrified, and the purchaser of the fidelity bond has no control over where that value goes.
The proof of the sacrifice is then two transactions: the proof the announcement transaction exists in the chain, and the proof that the inner sacrifice exists in the chain. (possibly with proof of the inner sacrifice inputs to prove what fees were actually paid)
Coinbase TxOut Sacrifices
Coinbase transactions are unique in that they can't be spent for 100 blocks, thus solving the problem of proving a transaction output was made public prior to it being possible to spend that output in a single transaction. In addition coinbase transactions can be created anonymously without linking the transaction to any other transaction provided that the creator has the ability to mine anonymously. (Or have someone else do so on their behalf.)
A proof for a coinbase txout is particularly short if the txout is the last txout and the script is meant to be unspendable. SHA256 midstate compression can then be used to prove the committed digest, and that the last opcode was OP_RETURN; it is not possible for a script to return true unless without the last opcode being executed. Fortunately the anyone-can-spend version can-not be proven so easily - consider the following txout fragment:
<SHA256 midstate> <scriptPubKey length> <digest> <nLockTime>
The problem is the fragment could actually be part of this scriptPubkey:
<pubkey> OP_CHECKSIGVERIFY OP_PUSHDATA (<scriptPubKey length> <digest>)
In reality this isn't a true sacrifice. The only way around this problem is if the proven data is greater than the maximum pushdata length allowed, 520 bytes, which undesirably depends on a constant whose value may be changed in a future hard-fork.
Passports
This wiki combats spam, while still allowing for users to sign up anonymously, by requiring users to pay a small amount of Bitcoins to the wiki before editing privileges are granted. Creating large numbers of "sock-puppets" to add spam content to articles is thus made expensive. The fee approach can be generalized with the concept of a Passport, first proposed by Mike Hearn,[3] tied to the users identity. Wikis, forums, webmail and other services can then create blacklists of users who violate the rules of the services, with those blacklists tied to passports.
The advantage of fidelity bonds in that application over simply charging fees is re-usability of an identity across multiple services, as well as the neutrality: if the value required to create the passport provably does not go to the person adding the passport to a blacklist, there is no incentive to do so to collect new sign-up fees.
Financial Services
Fidelity bonds can be used to make financial fraud unprofitable. For instance the original fidelity bond proposal[4] - called "Trusted identities" at that time - included the idea of using fidelity bonds to create decentralized green addresses. Someone wishing for their transactions to be accepted without confirmations would first purchase a fidelity bond of some value tied to their identity. Someone determining if they should accept a payment without confirmations can check that the bond was sufficiently expensive to make it unprofitable for the sender to commit fraud. If the sender does commit fraud by double-spending the payment, the recipient can prove that fraud to the world by providing both transactions spending the same inputs. This proof is added to some sort of blacklist, centralized or decentralized, which later recipients can consult to determine if the fidelity bond is now invalidated.
Time-Locked Fidelity Bond
A related concept which uses time-locked bitcoins to prove a sacrifice. The purchaser of the fidelity bond sends bitcoins to a time-locked address and can reveal the UTXO and redeemScript to prove the sacrifice. The thing being sacrificed here is time rather than money (although because of the time-value-of-money they are somewhat related). This idea may be particularly useful for creating a cost to deliberately DOS interactive protocols like CoinJoin or CoinSwap.
The lock-time can be chosen to be far enough in the future to provide a suitable cost. Note that from the point of view of an investor of many bitcoins, they can purchase bonds for nearly-free because they intend to hold their bitcoins for a very long time anyway. Although presumably a long-term bitcoin investor won't want to DOS coinjoin protocols that make bitcoin more private and fungible, as that would hurt the value of their own investment coins.