Cryptographically secure IOUs without a trusted third-party

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.
The solution, it turns out, is relatively simple. First, assume ...