On Monday, November 19, 2001, at 12:39 PM, Ken Brown wrote:
Tim May wrote:
So, here's the punchline,
Regardless of companies trying to make money, not be run out of business by money laundering laws, trying to be banker- and Homeland Fascism-friendly, IS THERE A FUNDAMENTAL REASON WHY TWO-WAY UNTRACEABILITY IS NOT "POSSIBLE."
I believe counterexamples have already been developed, showing there is nothing wired into the nature of mathematics that makes two-way untraceability impossible. I'll save these examples for later.
I don't know if there is. I'll have to think about it. Any train of thought that involves a distinction betwen "seller" and "buyer" is probably going up the wrong track. As is any that involves a distinction between "cash" and "goods?" Yes, I suspect. So we can think of it as barter, but digital barter, so moneychanging *is* a good model. It is sufficient to prove that you can do anoynymous, safe, digital money-changing.
Yes, you are on the same track I am on. Just as there is no real difference between a "buyer" and a "seller" (think barter, think trading songs, think swap meet), so, too, MONEY IS JUST ANOTHER GOOD BEING TRADED. While we think of the crisp $20 bill we got at the swap meet as being more "real" (guaranteed value) than something we get in trade (a radio, for example, which might turn out to be defective...), this is just a matter of degree. Counterfeit bills exist, and swap meets, by the way, happen to be where a lot of them turn up. But I risk digressing... The point is that even Chaumian "coins" (the unblinded numbers, presumptively unlinkable in the usual Chaumian ways) are essentially just goods. A recipient of such a coin has worries: has it already been spent (double-spending issue), will the issuer simply say "No good" (for whatever reason, including a deliberate "take the real money then renege on all redemption attempts" strategy. All money, all currency, all goods, are just "things" with various beliefs about them. And note that many of the "attacks" or "weaknesses" in digital cash schemes are actually present all around us. Examples abound, and could be put into a long list of potential frauds, scams, defaults, etc. Confidence gamers have been using these scams for centuries, longer. Banks have been failing, refusing to honor their notes, their "coins," for just as long. And governments have been looting banks, freezing assets, devaluing currencies. The list of "failure modes" is long. And yet it doesn't stop banks, money, and commerce. All crypto is economics. It's the ecology that matters, not just the absolute perfection of each sub-component. Your questions below need longer answers, but here are a few notes (take them as comments) on each of them:
The full, hard, question then is something like this:
Is there are protocol that allows moneychanging between different forms of digital money that
1) allows complete anonymity to both partners to a transaction, and
If Alice and Bob are "already" in possession of unspent (*) coins (I will use this term to refer to unblinded numbers, dispensing with talk about modular exponentiation, raising things to the one third power, blah blah), then Alice can give Bob 100 of her coins and "get back" 99 of Bob's coins. (His commission for moneychanging, for example.) (* Double spending will be an issue. I claim solutions exist, probabalistically.) Some don't like the mention of "coins." I mean it as shorthand to replace the often-confusing rewrite rules about what the transactions unfold into. Better to think in terms of atomic Chaumian protocols, unless the detailed rewrites matter in a particular case. Or for implementation, of course.
2) provides strong defences against fraud to both parties, and
This is best solved probabalistically, which we use for zero knowledge proofs. For example, I wish to know whether a bank (Bob) is "honest" about redeeming its digital money. I can "ping" the bank by withdrawing digital coins (again, same as "giving them a blinded number, getting back their version, unblinding the number," etc.) and then seeing whether they redeem the coin. As their coins are untraceable to me, I can have someone I trust test them. This is how people test their banks with ordinary cash. (Most don't, because enough others _have_. Banking regulations have very little to do with bank trustworthiness....ask the hawalla banks and their customers.)
3) works well if one partner has much more to lose than the other (& therefore for arbitrarily large amounts) and
Best done by splitting into lots of smaller pieces, pieces which can be used to ping. (Not just to test, but to buy the advantages of being part of an ecology. An issuer who decides to "burn" customers cannot do it for just one particular customer. Your "size" or "more to lose" issue has some interesting mathematical issues connected to with it. "Streams" offer one outlook...no time here to explain. In some of my articles from several years ago.)
4) works without a trusted 3rd party (broker, bank, court, police, godfather, whatever), and
I think third parties play a very important role. They don't have to be police or courts, etc., and it's better that they are not. A courier is a good example. An employee who moves packages, or even does banking. (Couriers are often bonded, the "more to lose on a burn than he makes" point you made. But couriers are also given incomplete knowledge. It helps that a courier doesn't know whether he's transporting $2000 or $200,000. Usual principles. Application to crypto protocols is not obvious, but there's something _there_.)
5) can be relied upon for a single transaction - in other words the partners have no previous knowledge of each other, and need never have a further relationship.
This is always problematic. Even in the real world of real money and real drugs. Drug deals often go bad for this reason. So physical security, snipers in high places, all the usual movie and t.v. drama. Can a system work without deadlock, where Alice makes a good (a song, for example) and Bob does the same (another song)? Sending partial bits out is only a crude engineering solution...both get their songs more or less simultaneously. Note that any system where Alice unlocks her song with a key is no solution at all. (This is often _seen_ as a solution, but bits are bits, and so this solution misses the point.) Note that no digital money scheme solves this problem, either. (Which is why I put in terms of straight barter, with no issues of translation into money even necessary to consider.) I believe, and have believed since 1988 when Dave Ross first suggested it in a discussion a bunch of us were having, that third party escrow services, untraceable to each but having a digital nym, is the optimum solution to this "delivery deadlock" problem. Much has been written, by me and by others, on escrow services.
?
The protocol needs to be stateless between trades. (though not, of course, within them). Everyone comes to the table with no history and leaves it with no requirement to return.
Well, "reputation" is a form of persistent state. The reputation (belief) that a piece of metal is actually gold, the belief that a gold market will exit in 2 hours, the belief in a bank, and so on. I believe the notion that persistent states are not desirable, that only a kind of "purely functional (in the sense of Scheme or ML) protocol is desirable is the ROOT CAUSE of much of the failures talked about here.
Several slightly weaker cases are of course trivially possible, if we allow some pseudonymity, or assume that the transactions are small enough that fraud will hurt neither party.
It is trivially possible if there are repeated pseudnymous transactions, and there is enough time for the parties to build up a reputation.
And this matches how things work in the real world, in all cultures and over nearly all periods in history. Kids learn that money has value by a Bayesian expectation that dollar bills will continue to buy candy. Those with checking accounts establish a Bayesian belief that their checks will continue to be honored so long as they meet expected deposit requirements. Etc. for a dozen other good examples. Why do we expect digital money to be different? (Yes, there are fascinating aspects to one _part_ of the blinding process...but isn't this akin to only focussing on the "untraceable" part of a gold coin and saying that's the only reason money works?) We have been taking a couple of elegant protocols and expecting this to be the monetary system. And when they fail, or fail to get implemented (the real reason), we say "untraceability is not possible." (Given certain flaws in non-digital money systems, would we say that "traceability must be added"? Government thinks so, with money laundering and currency transport laws, and with likely outlawing of cash within out lifetimes. But these are for political reasons.)
Requirement (4) need not be true if both parties are allowed to have a pseudonymous relationship with a 3rd party, but that just gets us back to banking, which is boring.
Not if anyone is a potential bank, a mint. If coins are just another form of bartered "things," and if traceability to a physical true name is not essential for barter (my basic thesis), then look what happens...
It is also easy if only one party is really worried about fraud. Ordinary cash transactions for small amounts work like that already. The shopkeeper doesn't care who I am or, really, if my cash is any good. If I pass him a few dud coins he has lost a tiny part of his turnover. I do care that the goods I am buying are good though. So he has to reassure me of his reliability not the other way round. Though they do care if lots of people start to pass forged coins. If their turnover is high enough they have an interest in the average quality of money, not the quality of any one coin. The system only has to be good enough, not perfect.
Pseudonymous exchange can be achieved by breaking trades down into small increments none of which is significant enough to damage either player. If I'm going to give you a thousand pounds for 1600 dollars we could do it a dollar at a a time and just withdraw - but we know this already so no point in thinking aloud along those lines
First, it is by no means pointless to talk in terms of these smaller sub-trades. It solves many problems. Second, even very high-value transactions can be done with mutually-trusted third parties, even untraceable. (Physical identity is just another credential. Sometimes offered, sometimes not.) Thanks for the interesting comments, yours and Adam Shostack's. It's helping me to dredge up out of my memory some of the good discussions from the early list years and from the 1995-97 years when "everyone a mint" was being discussed a lot. I feel more than ever that the ecology approach, the agoric approach, is the key. --Tim May "A democracy cannot exist as a permanent form of government. It can only exist until the voters discover that they can vote themselves money from the Public Treasury. From that moment on, the majority always votes for the candidate promising the most benefits from the Public Treasury with the result that a democracy always collapses over loose fiscal policy always followed by dictatorship." --Alexander Fraser Tyler