Cryptographically secure IOUs without a trusted third-party
Posted by Nick Johnson
Recently, a friend and I were discussing peer-to-peer systems, and the difficulty of tracking obligations, and of reliably reporting a peer's actions while making fraud difficult or impossible. A subset of this problem is P2P currency: I want to be able to write someone a promissory note or IOU in such a way that they can transfer it to other parties (presumably to eventually be redeemed by them), but without them being able to duplicate it (or rather, in such a way that duplicates are detectable, and the identity of the peer to duplicate it can be determined). So our hypothetical peer-to-peer currency requires the following attributes:- Non-deniability - The issuer must not be able to plausibly claim they did not issue the IOU. He must also be unable to claim the note has already been redeemed unless he can prove it somehow.
- Transferability - The current owner of a note must be able to transfer it to a new owner, without requiring the involvement of the original issuer, or any trusted third-party.
- Accountability - If the note is modified or duplicated, it must be possible to determine who tampered with it.
To issue a note, the issuer creates a new note, with a header specifying the identity of the issuer, the value of the note, the time it was issued, and any other details - for example, the note may have an expiration date.
Whenever the current owner of the note wishes to transfer it to a new owner, he appends the identity of the new owner to the note and signs the whole thing with his public key. Every note will have at least one owner and signature appended, as the original issuer does this when giving the IOU to its original recipient.
A note's validity can be checked by verifying the 'chain of custody' described by the identities and signatures, which must follow the pattern id(issuer), id(a), sig(issuer), id(b), sig(a), id(c), sig(b), ... Further, any peer can prove to any other peer that they own a particular (valid IOU) by simply sending it to them - notes need not be kept secret, as they are useless to anyone other than the person whose identity is last in the chain of custody. Thus, peers considering an exchange can simply send each other all their notes so they can be examined and offers made.
If a peer wishes to try and duplicate a note, they must either invalidate the chain of custody, rendering the note useless, or duplicate it, appending a different identity in each case and signing it. When the note is discovered to have been duplicated - eg, at the point when someone attempts to redeem a note a second time - the identity of the fraudster can be determined by comparing the chains of custody and identifying the last peer the two notes have in common.
The value of a note to a peer in a system where fraud may be attempted is not the face value of a note, however. The value to a peer is the face value of the note, multiplied by the probability that it believes each peer in the chain was honest and did not duplicate the note, multiplied by other factors, such as a consideration for how close the note is to expiry, if that is implemented. Since this means that notes with longer chains of custody are worth less than those with shorter ones, it should be possible, if the original issuer is online, for a peer to send the note back to the issuer, requesting a 'new' one with a blank chain of custody (but the same value and expiry date) in return. This way, trust can be enhanced without requiring the original issuer to be online at all times.
It is also worth noting that in cases when a peer attempts to redeem or renew a note, only to be told by the issuer that that note has already been redeemed, and that their copy is worthless, that the peer need not take the issuer's word for it - they can demand a copy of the note that was redeemed, which serves as both proof and a means of identifying the culprit.
One major issue that this system does _not_ solve is that any peer can invent as many cryptographic identities as they wish, and if they wish to commit fraud, they can use those identities to do so. Analysis techniques can likely be used to track down the actual culprit in scenarios like this, but this could be arbitrarily difficult to do. Alternately, a trusted third party issuer could be required for certificates only, or the peer's identity could be based on their IP address or other identifying factor, limiting the number of identities they can invent.
Finally, it's worth noting that the system proposed here is very similar to that used to endorse checks in the real world.
Feedback on this algorithm is much appreciated. Ideas on how a practical peer-to-peer transfer or storage system could practically use such an algorithm are also appreciated! Previous Post Next Post