A short while ago I wrote this comment on the dbs list describing a transferable off-line ecash idea I'd been thinking about with on-and-off:
On Fri, Mar 29, 2002 at 02:43:42AM +0000, Adam Back wrote: > [...] > I spent some time a few years back trying to find ways to do the > free-circulating tokens ala mondex but with out the trust-me anonymity > (with proper trust-no-one blinding anonymity) and with off-line fraud > tracing.) I'm not sure it's possible, but I think it would be cool if > it could be done. If someone could come up with a way to do that, I'd > be willing for Bob to call that bearer ecash :-) While looking for a reference to something else to do with ecash I found that a somewhat general way to convert an off-line ecash scheme into a transferable off-line ecash scheme has already been proposed: See Section 8 of "Easy come - easy go divisible cash", by Agnes Chan, Yair Frankel and Yiannis Tsiounis [1] references [vA90] H van Antwerpen "Electronic cash", Master's thesis, CWI 1990 as providing a general way to make coins transferable from a shop (who now acts as a payer) to another payee. They say of van Antwerpen's approach: "8 Extensions and open problems Transferability: There is a general method with which a coin can be transferred from the shop (who now acts as a payer) to another payee, proposed in [vA90]. The method preserves the anonymity of the shop and is applicable to all anonymous off-line e-cash schemes. The coins grow upon each transfer, but [CP93a] showed that this is inevitable, and the approach is asymptotically optimal. Intuitively, the shop obtains a "blank" (zero-valued) blind coin from the bank, and includes it in the hash of the random challenge to the user (for exact payments divisible "blank" coins can be obtained). Then the shop can transfer the payment by "spending" the blank coin with a payee. Note that the blank coin is "bound" to the original payment (since it is included in the random challenges used for that payment), while the shop cannot over-spend, or it is identified. The shop only needs to contact the bank (in an off-line manner) in order to obtain "blank" coins; finding algorithms to withdraw multiple (unlinkable) "blank" coins faster than performing multiple withdrawals in parallel is a problem pending further research." So I'm presuming from this description that the trick is, you just bind a 0-valued fresh coin to the spent coin. If the 0-valued coin with spent-coin is double spent it will be the double-spender who is caught. The coins here also grow as there will be the original coin, plus a chain of appended 0-valued fresh-coins taking ownership at each spend. (My experiments were somewhat related in that I had got to the stage of a coin and receipt which grew once with each spend, but had not thought of directly using a 0-value fresh-coin, and instead was experimenting with more complex requirement of having the payer and payee run a protocol to change the embedded off-line fraud information (eg the identity) as the coin changed hands). Also they note as I figured that it is unavoidable that the coins must grow for this type of scheme and reference a proof about this in [CP93a]. But I would think that is anyway obvious for simple storage arguments. Also in trying to find an electronic copy of [vA90], I see that Brands [2] notes that [vA90] also applies to his ecash scheme. Getting interesting. (Divisibility of Chan et al is nice but it still has linkability across the divided coins, and I'm not sure how much analysis Chan's scheme has compared to Brands). However I still can't find [vA90]. Hans van Antwerpen seems to have disappeared off the 'Net. So at a high-level this means you can have off-line ecash with fraud-tracing the identifies the double-spender, and the participants do not need to involve the bank they can just transfer coins peer-to-peer for a fairly arbitrary number of hops. (The only restriction being that the coin increases in size by one coin's size at each spend). I think depending on the scheme involved (this would be the case for Brands) you could potentially distribute the double spend database. Ie there is nothing to stop the users or 3rd party services having double spend databases to improve the odds of catching double spenders before the coin gets back to the bank. This also means that a bank could realistically be more off-line yet, not needing high availability, or even itself being pseudonymous (which tends to mean less online -- eg behind a nymserver account) provided there was some receiver anonymous way to transfer resources of whatever kind the ecash represents to it. Potentially the operation of running the double-spend database could be separated from the coin minting part which would also occasionally exchange fresh-coins for multiply exchanged coins which were getting unworkably large. Techniques like merkle authentication trees as used in time-stamp servers where a server can commit to a values publication without seeing the value and without being able to later retract that statement could perhaps be used to deter or prevent conflicts of interest between the nodes participating in the distributed double spending database. Adam [1] "Easy come - easy go divisible cash" http://www.cs.neu.edu/home/yiannis/papers/EC98.ps [2] An efficient off-line electronic cash system based on the respresentation problem, tech report CS-R9323, 1993 http://citeseer.nj.nec.com/rd/35069582%2C280560%2C1%2C0.25%2CDownload/http%253A%252F%252Fciteseer.nj.nec.com/cache/papers/cs/13702/http%253AzSzzSzcert.unisa.itzSzpubzSzDocumentationzSzEcashzSz.zSzCS-R9323.ps.gz/brands93efficient.ps.gz [va90] "Electronic Cash", Hans van Antwerpen, Master's Thesis [CP93a] "Transferred cash grows in size", D Chaum and T Pedersen Eurocrypt 92
