Skip to Content.
Sympa Menu

bluesky - Re: distributed immutable namespace: Think Cash

bluesky AT lists.ibiblio.org

Subject: Global-Scale Distributed Storage Systems

List archive

Chronological Thread  
  • From: Michael J Freedman <mfreed AT MIT.EDU>
  • To: "Global-Scale Distributed Storage Systems" <bluesky AT franklin.oit.unc.edu>
  • Subject: Re: distributed immutable namespace: Think Cash
  • Date: Thu, 08 Mar 2001 21:00:32 -0500


At 10:32 AM 3/8/2001 -0800, you wrote:
>This same issue came up on the Freenet mailing list a while back. We
>weren't happy with hashcash since it would make your ability to publish
>information proportional to the speed of your PC (which is roughly
>proportional to the size of your wallet), and we didn't like that at a
>philisophical level.

This goes back to the question as to the particular need for POWs such as
hash cash. Our contention is that for resources which become only
temporarily used -- such as bandwidth (Gnutella), CPUs cycles, and caches
(Freenet) -- that you don't need a congestion management mechanism *at all
times*. Rather, you only need to dynamically change your "publishing"
(querying, etc.) requirements based on the current load of your system.
That is, as your system gets congested due to temporary load, raise the
amount of required payments dynamically. We refer to this as an
"accountability slider" in the O'Reilly P2P book.

If your resources are cumulatively used -- such as disk space in permanent
storage systems (Free Haven) -- then enforcing micropayment requirements
when you start getting congested is *already too late.* Thus, for these
types of systems, our contention (in the micropayment world) you need 'em
all the time.

I have some concerns as to the real viability of "Think Cash" in a
distributed P2P environment.


>task. Thinking of a way to do this is not easy - any such mechanism
>would need the following properties:
>
> 1. Only a human should be able to perform the task or test
> 2. A computer should be able to create a test automatically
> 3. A computer should be able to judge the results of the test
>
>
>speech recognition. The problem here is not so much creating the tests
>(requirement 2), but judging them (requirement 3). There is the further
>constraint that each test must have enough possible answers so that a
>computer could not simply attempt all of them.
>

First of all, I think this is actually an incredibly difficult problem
which you suggest. Let's describe this in terms of a normal interactive
protocol (IP) framework.

You are suggesting that your proof system has a prover (P) and verifier
(V), such that after the IP, V should only accept (with probability
1-\epsilon, 1-constant, whatever) if P \element {humans}.

Getting this (completeness). and soundness (no cheating) with small enough
false positives and false negatives is, my opinion, going to be a very hard
problem.

The issue is compounded that you are working in a distributed peer-to-peer
environment. Generally, we would like protocols to be simple,
well-understood, and light-weight. This type of system would likely be
very complex, hard to formalize, and thus hard to really analyze.

You mention the Turing test. Unfortunately, V in that system is a human,
not a computer. The ability for computers to perform natural language
processing is fairly well along, but it's definately *not* a light-weight
operation. But language understanding is much further back, especially if
your language domain is fairly large. For example, MIT LCS's Spoken
Language Systems group has good working systems for language understanding,
but each system only handles a small "problem:" the weather, driving
directions, airplane reservations, etc.


>The seeds of a solution
>I started to think about whether it would be possible to create a system
>where all the users, while being tested by the system, were actually
>testing each-other too. Each user might be asked to provide an answer to
>a question which will demonstrate their intelligence, to provide a
>question which will test someone elses intelligence, and to give an
>opinion as to the answers given by a number of other people to several
>questions. Failure to do any of these things to the best of their
>ability may result in their submission not being accepted.

This proposals layering many two-way interactions in the "intelligence
testing" protocol. It also suggests that users -- who use the system with
widely varying educational backgrounds, computer literacy, cultures,
comprehension of the technologies involved, etc. -- to "judge" each other's
intelligence. And then make operational decisions based on their limited
interaction and limited understanding of each other.

Make the problems too hard, and your false negatives go way up. Make the
problems too each, and I'll write an automated simulator that'll convince
most of them. Your false positives go up. Throw some machine learning in
there? Then you get away from the "user-interaction" model and you added
lots of complexity.

When you aren't formalizing the problem -- like hash cash, client puzzles,
Naor/Dwork's paying for processing -- you aren't establishing complexity
classes, in any sense, for the issues at hand.


>Remaining issues
>Of course, there are still many details to be worked out, how can the
>above system be built so as to make abuse impossible? What if a computer
>made so many submissions that it saturated the system, and could
>validate its own submissions as being correct?

See above.

>None the less, at least this suggests that a robust think-cash mechanism
>is a possibility. As the threat of malicious attacks on the Internet get
>more and more serious, people may be forced to adopt a mechanism such as
>this.

I fear "robust" is something that hardly applies.

Your goal might be an admirable one, but I am very hesitant to think that a
"Think Cash" system as you describe is realizable in the near- to medium-
future.

--mike


-----
"Not all those who wander are lost." mfreed AT mit.edu








  • Re: distributed immutable namespace: Think Cash, Michael J Freedman, 03/08/2001

Archive powered by MHonArc 2.6.24.

Top of Page