A magazine dedicated to all things Bitcoin
Webs of Trust and How To Decentralize Themauthor: Vitalik Buterin
published: 2011-05-20 20:18:48 UTC
The majority of economic transactions require a certain degree of trust between the participants. When a physical product is sold for bitcoin, the seller has the opportunity to defraud by not sending the product, and since Bitcoin is an untraceable currency with irreversible transactions, the buyer cannot get his money back. For some arrangements this is not the case: if one person agrees to regularly supply a product or service in exchange for regular payment then the value of the relationship is worth more to both parties than the gain from defrauding the other party once. But as the Bitcoin economy matures, and especially with the advent of the Global Bitcoin Stock Exchange, which presents a prime opportunity for a scammer to start a business, acquire "startup capital" but then run away with the money, a system to penalize people who defraud others becomes necessary. The conventional economy can rely on courts to enforce contracts by force of law, but conventional courts cannot be applied to the Bitcoin economy: courts rely on knowing physical identity to enforce laws, while one of the main purposes of bitcoin is to allow economic activity to be untraceable to physical location. The GLBSE, for example, intends to operate anonymously from "cypherspace", out of reach of any specific land-controlling government.
The solution is reputation: people are more willing to trade with reputable members of the community, so reputation becomes a valuable asset. If someone defrauds someone else, the victim cannot find the perpetrator physically and demand justice by force. However, the Bitcoin economy is not anonymous, it is pseudonymous: the perpetrator has a name, and the victim can report the fraud to the community. The perpetrator can switch to a new name, but the old name is forever tarnished, and the effort spent building it up is lost.
Online identity thus becomes critical, but online identities are far more vulnerable than physical identities to identity theft. If Alice is a well-respected member of the community, what prevents Carl from contacting Bob with a business offer and then defrauding him? Some informal solutions include email and forum accounts: only Alice has control over her account, so Carl would not be able to pretend to be Alice without breaking into her account. The problem with these solutions, aside from the fact that they limit the user to one communication channel, is that they are insecure, and centralized; if Carl finds an exploit in the forum he will be able to steal thousands of identities at once. Also, an employee of the forum would be able to easily take over accounts, and a government agency can do so while compelling everyone involved not to reveal that surveillance is going on. Finally, forums could simply go off the internet. Such informal systems are centralized and introduce a single point of failure, so they should not be trusted for the same reasons that Bitcoin users chose Bitcoin rather than e-gold, some other online currency or simply credit cards and Paypal.
So how can identities be kept more secure? One solution is sending messages with public key signing. Alice, when she wants to contact Bob, uses a widely known hash function like SHA1 to create a short 160-bit hash of her message. The hash function has the property that a one-letter change to the message changes the hash completely, and it is virtually impossible to create a message that hashes to a given value. She then encrypts the hash with her private key and sends the message to Bob. Bob decrypts Alice's encrypted hash with Alice's public key, which she publishes to everyone, and himself hashes the message. If the two hashes match up, then the message is legitimately from Alice; Carl, lacking Alice's private key, cannot encrypt the hash so that Alice's public key can decrypt it, so he cannot impersonate Alice.
This is the foundation of a reputation system, but is not by itself adequate. If Bob only wants to deal with reliable people like Alice and not strangers whom no one has ever heard of, once he verifies the identity of a potential business partner how does he determine his reputation? Googling him might work, but is unreliable - Carl might set up a hundred shell accounts to praise himself. The solution is a web of trust: a place where one can report successful interactions with other people and report frauds, and where the identity of the people reporting successful interactions or frauds can itself be determined. If Bob sees the Alice is trusted by a hundred people, then he can check if they are shell accounts or themselves known members of the community - in the first case, Alice is not to be trusted, while in the second case she has enough value behind her identity to start up a GLBSE business. Similarly, if Alice has a hundred negative reviews, if these are all Carl's shell accounts trying to slander her then they can be disregarded.
We already have such a web of trust: the Bitcoin OTC Web of Trust. The problem with the Bitcoin OTC web of trust, however, is that it is itself centralized; while the identities that it measures are secure, the ratings are stored on a centralized server, and if Carl has some way of taking over Bitcoin OTC - having an employee as a friend, being a skilled hacker, or being a government agency, then he can give himself a high reputation. Even though an individual needs to prove to Bitcoin OTC that he is who he says he is by public key, the wider community does not have access to this proof. The web of trust is only as secure as the site backing it up. This is acceptable for now, and a comprehensive solution to the problem may not yet be worth the trouble, but as the value of bitcoin increases and the economic value of the business deals being done through BTC and the businesses started through the GLBSE increases, the web of trust will become too big to fail, and therefore too big to keep centralized.
There is another, more practical, problem with public keys: an identity mapped to a single key does not expire, and there is no redundancy against the possibility of the user losing his private key, or an attacker finding his public key. It is possible to send a signed message saying "I'm switching keys, this public key represents me now", but this is useless after the fact in the cases of both loss and theft. So one solution to guard against loss is to send a signed message saying "This key, and this other key can both represent me". Let's assume that in the normal case the chance of loss is 1 in 1000 and the chance of theft is also 1 in 1000. Here, the chance of loss goes down to 1 in 1000000, but the chance of theft goes up to 2 in 1000. Requiring two keys to be used at once has the opposite problem. So a further solution is to require 2 out of 3 keys to represent you - here, the chance of loss, since 3 combinations of 2 keys could be lost, is 3 in 1000000, and the chance of theft is also 3 in 1000000. This is far more secure, and has the advantage that two keys can be used to expire and replace the third, so if one key is discovered it will eventually be replaced even if the individual does not realize the discovery. The problem now, however, becomes one of mere practicality: how do we keep track of all the keys? We need a timestamp server to sign messages of expiration, so the attacker cannot find two old keys and use them to expire and replace the victim's identity.
These two problems, however, already have a solution, and a very decentralized one: something similar to the bitcoin network itself. Timestamps are integrated into the blockchain, and one would only need to scan through the blockchain and see which keys map to which identity at what time. Sending a signed message would not require confirmation - if a message is sent, it is checked against the keys mapping to the identity now, and if the keys are expired one can ask the sender to resend using the new keys. Thus a bitcoin-like block chain application, just like Namecoin, can be developed to support such a system, and the system could in fact be built off of Namecoin itself: Namecoin has a "personal" name space as well as a DNS name space, and a web of trust is merely an extension of web pages hyperlinking to each other. Decentralized money needs decentralized peripherals: a decentralized exchange, a decentralized DNS, Namecoin, and also a decentralized web of trust.
In a previous article, I talked about the Global Bitcoin Stock Exchange and how it differs from traditional...
Some wonder who is the real man under the Satoshi Nakamoto mask; a hard question - how many libertarian cryptographers are there? But the interesting thing is, Satoshi could be anybody. Bitcoin i...