A while ago, I wrote about transferring money through chains of IOUs. I’ve since discovered that such transfers are now sometimes being called “transitive transactions”.
So, for example, if Alice wants to pay Frank $600, but Frank doesn’t trust Alice’s IOUs, they might find a path through existing trust relationships, so Alice gives Bob an IOU for $600, Bob gives his own IOU to Charles, Charles gives one to Denise, Denise gives one to Edith, and Edith gives one to Frank. Alice has paid $600, Frank has received an IOU for $600 from someone he trusts, and everyone in between has given an IOU for $600 and received an IOU for the same amount from someone they trust.
But Charles will be upset if he thinks the transaction is going ahead, and gives his IOU to Denise, only to discover later that Bob didn’t agree to this transaction; and Denise will be equally upset if Charles then demands his IOU back, but she’s already given hers to Edith. Or, Alice will be upset if she gives her IOU to Bob, but discovers later that Frank never received the money, because Denise, who neither Alice nor Frank know or trust, ran off with the money. So how do all these people coordinate, so that they all agree on whether or not the transaction is going through?
This could be seen as a version of the so-called Byzantine generals problem, in which a number of generals are trying to coordinate some action in a situation in which anything might go wrong: some of the generals might be under attack and unable to respond to messages; others might be traitors; and some of the messages might get delayed, captured, or tampered with before they’re delivered.
It’s been proven that in an asynchronous network (like the internet), it’s impossible to guarantee agreement in finite time, even if only one of the generals is a traitor, and every message is eventually delivered. In practice, you can arrange for a very high probability of agreement in a reasonable length of time, with reasonable assumptions about how many errors, traitors, or delays there might be.
Even so, our situation would seem to be hopeless; how can we possibly coordinate a long chain of IOUs when the participants are only expected to have a trust relationship with their immediate neighbours in the chain, and mightn’t even know who all the other people are?
What a solution should achieve
Well, the nature of the action to be coordinated gives us a way out. I believe that we can design a protocol that has the property that if you make a payment without receiving a compensating one, then it’s because of one of the following:
- your own error or attempted treachery,
- error or treachery on the part of someone you explicitly trust, or
- failure of communication between you and someone you explicitly trust.
This would mean that the negative consequences of failure to coordinate would affect only those who were most likely to have been able to prevent the failure: by being more careful to avoid errors, by being more careful about who they trust, or by doing more to secure their communication links to those they trust. This is the reason for the word “responsible” in the title.
First of all, we observe that the chain of trust relationships is actually a cycle; there is a trust relationship between Alice and Frank. You might wonder: If that’s true, then why doesn’t Alice just give Frank an IOU instead of going through the whole chain?
Well, the trust only needs to go one way; maybe Frank doesn’t trust Alice’s IOUs, but Alice trusts that once Frank has received the payment, he’ll give her the computer she was trying to buy.
It’s worth noting that other trust relationships in the chain might also be one-way. Perhaps Denise is a bank at which Charles has deposits. Although Denise doesn’t trust Charles’s IOUs, she can trust Charles for promises to pay anything up to the amount of his current deposits; if there’s a dispute about whether Charles should have paid Denise a certain amount, Denise can simply refuse to let Charles withdraw more than she thinks his balance really is.
Now, assume that all the people in the chain have agreed to consider a chain involving specified payments to and from themselves. Before any attempt is made to have the transaction actually go ahead, Alice (who initiates the payment) must have the cryptographic signatures of everyone in the chain, affirming this agreement-to-consider. (People in the chain might be known only by their cryptographic public key, except to their immediate neighbours who trust them.)
This agreement-to-consider includes not only how much everyone agrees to pay if the transaction goes ahead (and a specified time when the agreement-to-consider expires), but also each person’s promise about how quickly they’ll be able to process a message they receive from the person after them in the chain, and, depending on what it says, compose their own message and send it to the person before them in the chain. (Alice makes a promise about how quickly she can get such a message to Frank.) This means that everyone in the chain can figure out how long (at most) information that’s being passed backwards along the chain should take to reach them.
When Alice decides she really does want to make that payment through that chain, she specifies another, possibly earlier, expiry time on the agreement-to-consider and signs it again, upgrading it to a conditional agreement, meaning “I agree to pay Bob, as long as everyone else signs this, and all the signatures reach me before the specified time”. Then she sends the signed conditional agreement to Frank.
If Frank hasn’t changed his mind about accepting payment through that path, he signs the conditional agreement, too, meaning “if everyone else signs this, and I get the signatures on time, I’ll give Alice her computer”. In Frank’s case, “on time” means “at or before the time specified by Alice, plus the maximum time in which she promised to be able to get a message to me”. Then he sends the conditional agreement to Edith, along with his and Alice’s signatures.
As long as no-one has changed their mind about their willingness to participate in this payment, the conditional agreement proceeds backwards along the chain collecting signatures until it reaches Bob. In each case, “on time” means “at or before the time specified by Alice, plus the maximum time, according to everyone’s promises, it should take information to reach me if it goes backwards along the chain from Alice”.
When Bob gets the conditional agreement with everyone else’s signatures, if he’s still willing to participate in that payment, and he thinks he can get the message to Alice on time, he signs it, and since there are no more signatures left to collect, his signature means an unconditional “I agree to pay Charles”. Thus, the conditional agreement is upgraded to a complete agreement.
Since Bob has just unconditionally agreed to pay Charles, he must now get the complete agreement with everyone’s signatures to Alice before the time she specified; but that’s ok, because he only signed the agreement because he thought he could achieve this; if he fails, and has to pay Charles without receiving payment from Alice, then it’s his own fault, or the fault of the communication link between himself and Alice, which he’s jointly responsible for; if there’s a dispute about whose fault the communication failure was, then it’s a dispute between Alice and Bob, who have a trust relationship.
When Alice receives the complete agreement on time, she’s obliged, by her earlier promise, to pay Bob. So now, to receive her computer, she has to get the complete agreement to Frank on time. But “on time” in this case allows for the length of time in which she promised to be able to get messages to Frank, so she should be able to do it, and if she can’t, and doesn’t get her computer, then it’s her fault, or the fault of the communication link she’s jointly responsible for.
If all goes well, the complete agreement should be able to pass all the way back along the chain to Charles, so that everyone’s obliged to make their payment. If anyone doesn’t get the complete agreement on time, they’re not obliged to make their payment, but if they do get it on time, and they’re therefore obliged to pay, then, according to their own communication promise, they’re able to get it on time one step further back in the chain, so that they receive their compensating payment.
Therefore, this protocol ensures that the incentives to prevent failures (and the negative consequences of not preventing failures) are in exactly the right places: with those most able to prevent them.