From: tcmay@netcom.com (Timothy C. May)
Date: Wed, 31 Aug 94 00:24:55 PDT
To: Hal <hfinney@shell.portal.com>
Subject: Re: Problems with anonymous escrow 3--response
Message-ID: <199408310724.AAA20251@netcom7.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



The third of my responses to Hal. Also included at the end is a discussion
of a "crypto simulation environment," as it comes up in the context of
Hal's comments about game theory and the need to simulate iterated
prisoner's dilemma types of problems in a crypto context.


>Another argument sometimes advanced in favor of trustworthy escrow
>agents is the "iterated prisoner's dilemma".  This refers to Axelrod's
>simulations of computer program agents which repeatedly interacted in
>a simple "prisoner's dilemma" game which captures much of the essence
>of the trust relationship (see his book "The Evolution of Cooperation").

I agree that evolutionary game theory has rich implications for real world
cryptography, especially as it involves trading, interactions, cooperation,
etc.

>again).  It has been argued that interacting pseudonymous entities
>satisfy the basic requirements for Axelrod's analysis because their
>pseudonyms have continuity over time, and people can use past history
>as a basis for future predictions (as in the escrow agency example).
>
>There are some significant differences, though, between Axelrod's
>scenario and the anonymous agents we are talking about.  One is the
>issue of pseudonym continuity.  Although it is true that pseudonyms
>can have continuity, they are not forced to, unlike in Axelrod's
>experiments.  One of the main reasons why cheating is a bad idea in

I think they are. Agents in an IPD (Iterated Prisoner's Dilemma) game can
change their strategy...that is itself a strategy (e.g., "cooperate for the
first 10 rounds, then nuke opponent"). Is this a change of strategy or a
change in the agent? Maybe this is a semantic misunderstanding, but I don't
see how "Pr0duct Cypher" or "Thoth" is not an Axelrodian agent?

>Axelrod's runs is that the cheating is punished in future
>interactions (generally, by being cheated on in return).  But of
>course in real life situations, cheaters don't hang around to receive
>their punishment.  Implicit in the escrow cheating scenario above was
>that the agent vanishes.  He isn't forced to stay in business to be
>cheated repeatedly by customers until they get even.  He is able to
>opt out of the system.  Axelrod's programs don't have that option.

Because Axelrod and his contributors [well-described, by the way, in
Hofstadter's "Metamagical Themas" book] barely scratched the surface of how
real ecologies, real economies work. Reputations do matter, as shown by
another classic game theory result, the "game of chicken." An escrow agent
that defects faces some repercussions (who trusts whom in such disputes is
another issue, possibly handled by selective disclosure, a la Chaum, by
reputation rating services, etc.).

>
>Worse, a pseudonymous cheater has other options which allow him to
>continue to benefit from interactions with others while cheating.  He
>can use multiple identities to, in effect, wipe the slate clean when
>he has cheated.  This plays havoc with the crucial assumption in

Not in a "positive reputation" system. In a negative reputation system, it
is true that an agent can alway flee and "start over" ("a fresh start').
But in a positive rep. system, each reputation only fairly slowly builds up
a rep. [There are scams, such as the "brilliant penny" scam, to use
collusive reputation setups to "inflate" a rep...nobody claimed it would be
easy.]

...
>know that they are reaching the end of their interaction period.  In
>particular, on the last interaction, it is hard to avoid cheating
>since one knows that the other player will have no opportunity to
>apply punishment.  But then, if it is a foregone conclusion that the
>last round will result in cheating, then it is hard to justify not
>cheating on the next-to-last round, since the results of the last
>round are foreordained and hence don't really provide feedback for
>what is done this time.  This leads to a disastrous regress in which
>one finds that the stable cooperative solution collapses into a string
>of cheating interactions.

It's best that it never be known how many rounds there are to be. Sort of
like not saying whether one is a source or sink of remailed
messages...leave them guessing. (Or more mundanely, keeping the number of
characters in a password a secret...the opponent doesn't have any
"terminal" states or nodes.)

I don't claim to know what the results are, this experiment not having been
done that I know of, but looking around me I see people who interact with
other people and who generally act as though "the game" will go on without
limit. While they certainly don't act purely in a tit-for-tat way, they
also interact as if their reputation for truthfulness, intelligence, etc.
matters to them. (This is true even for most of the pseudonyms we have
here, who give evidence of wanting whatever postivive reputations that have
accrued to them to continue. Financial matters are not necessarily the
same, granted.)

>Although in real life it will not frequently happen that both parties
>know that a particular interaction is the last, it may be that one
>party will know.  If a business has suffered reversals and is doing
>poorly, it may know that time is running out.  In that case it will be

This is a good point, and needs more analysis. It may be that using a set
of escrow agents will lessen the risk that any one of them is about exit,
stage left.

But bear also in mind that many escrow functions can be set up so as to
have almost no benefits to the escrow agent if he defects and attempts to
welch on the deal (kind of a "zero incentive" system). (This is how IOU
systems often work.)

...
>Based on these comments, it would be interesting to consider a
>variation of Axelrod's game, one modelled more on what we feel are the
>properties of a system of interacting pseudonyms.  We might include
>the possiblity for competing programs to "quit" by retiring old
>pseudonyms and to create new ones.  We might also simulate bankruptcy
>by having a rule that if the cumulative score of an agent ever became
>negative, it was out of the game.  It would be interesting to see
>whether these changed rules again promoted the development of "nice"
>strategies or whether they tipped the balance in favor of cheating.
>
>This might actually be a doable project for an interested programmer.
>It would be interesting to see whether others agree that it could shed
>light on the problem.

Here I agree most strongly with Hal. I have described my interest in this
area to several Cypherpunks and their friends, including Nick Szabo, Eric
Hughes, and Ted Kaehler (one of the developers of Smalltalk). The "protocol
ecologies" idea I talked about here a month or so ago is related to this.

To wit, building ecologies of interacting "cryptoids" which can scheme,
game, apply various crypto protocols, etc. (I don't mean any high-falutin
artificial intelligence, just a "testbed" for exploring agents that
implement crypto methods as, well, as _methods_.)

Toward this eventual end, if I can pull it off, I'm evaluating
"SmalltalkAgents," a programming environment for the Mac (soon for
Windows/Chicago, then Unix, etc.) which supports several interesting
features, including run-time dynamic typing, multiple threads,
agent-oriented methods (similar to Dylan, and maybe to the elusive
Telescript), and a persistent object store (so that the evolved agents
"remember" what they've learned and don't start from scratch each time).

For you Perl and C fans, why Smalltalk? First, because I get to pick
whatever environment I want. Second, because I enjoyed Lisp programming at
Intel (and a bit since, in Scheme) more than C programming. Third, while I
think the C++ class libraries are a powerful tool, I'm not interested in
using them right now. Fourth, the advent of 50-100 MIPS processors for not
much money places more premium on powerful prgramming environments and not
on runtime efficiency. Fifth, SmalltalkAgents can do external calls of C,
or whatever, code, so the the programming environment of Smalltalk can be
coupled with specific C code fragments. Sixth, the focus on CORBA, OpenDoc,
OLE, and other object protocols.

(I wrote down some of my thoughts on tools for crypto, beyond subroutine
libraries, a few months ago. "Crypto compilers," "intermediate design
languages" (IDLs for crypto anyone?), provably correct synthesis, etc.)

I think Hal is right that ecologies of interacting agents implementing
various crypto protocols (spending digital money, trying to collude with
others, etc.) is a ripe area for study. We learned a lot two years ago with
the "Crypto Anarchy Game" we played with paper and pencil, but we quickly
realized that humans are poor at remembering and enforcing complicated,
multi-stage, multi-party protocols, and that someday these would have to be
programmed into "crypto simulation" tools.

When, if ever, will I have results on this? I don't know. Do I want to
spend the next several years of my life on this? (As surely it's a
thesis-complexity job, or a several man-year job for a small group of
programmers...)

I haven't decided. I haven't decided even if it's the most important--and
interesting, since I'm working for myself, as most of us are--thing to work
on.

Enough writing for now.

--Tim May

..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets,
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."