Re: Economic Model for Key Cracking

[Bill Stewart <stewarts@ix.netcom.com>]

At 04:29 PM 8/18/95 -0600, howard@cs.ualberta.ca wrote:
> Distribute work when a request is received.
> When the final results come back, pay the worker e-cash.
>
>We need to make sure that someone did do the work honestly, but I don't know
>how to check this (other than doing the work yourself to confirm the results,
>but this defeats the whole point of the system). 

For the usual NP-hard problems, including keycracking, checking the answer
once you have it is easy - the hard part is finding the answer.
Another way to look at it is that most of the work is throwing away the
2**N-1 keys that aren't correct, and if you've got one correct key you don't
need to know about the rest (except in special cases where there are multiple
keys that work, but usually you don't care about that.)

Most people are honest, except Bad Guys.  

The honesty problem is more serious for negative results - if somebody says
"Range N1-N2 doesn't have the key", they could be honest, or they could
be a Bad Guy who knows that the key really _is_ in that range and wants
to prevent you from searching it, or they could be a scammer who wants to
get paid for searching but didn't actually do the work.  If people are
willing to be paid in lottery-mode (only the person who finds they key gets
paid),
then honesty's not a problem.  Otherwise, only hire honest people (plus Bad
Guys),
and if they don't find the key after the first sweep, try again (switching off
ranges so one Bad Guy doesn't get to lie about the same range twice.)

Alternatively, you could do a model where everybody gets paid, but only after
the answer is found, which discourages scammers (since they don't get paid if
they lie about searching the range that has the real key.)  If a Bad Guy lies
about the key not being in his range, people do have an incentive to look for it
if the first pass fails, and have an incentive to finger him if they do find 
the key on a later pass.
#---
#                                Thanks;  Bill
# Bill Stewart, Freelance Information Architect, stewarts@ix.netcom.com
# Phone +1-510-247-0664 Pager/Voicemail 1-408-787-1281
#---

	   "The fat man rocks out
	Hinges fall off Heaven's door
	   "Come on in," says Bill"    Wavy Gravy's haiku for Jerry