[RC5] Tree search algorithms and the next d.net

Adam C Luter gryn at gryn.dyn.marko.net
Wed Apr 21 17:43:48 EDT 1999


Double checking, if you do the math, is the least efficient method of
reducing error.  Primarily because the double-check itself is subseptable
to error.  Even if you somehow reduced the error (say by removing
offending IP's), you would still have some, and it would help, but still
be inefficient.

However, error isn't that big of a problem.  The percent error -is- our
chance of not winning (the first time around).  So we are only unlikely to
win if 50% of all submitted blocks were bad.  At worst you would then try
again.  (which at the same level of error give us a 25% chance of losing
the second time around [error^n]).  Which assuming lower error than that,
is pretty good.

Now, I had mentioned removing offenders.  Even if this worked (the
offenders didn't just go to new computers once their current ones were
blocked), you wouldn't really speed things up, as I believe someone
mentioned earlier (though with a slightly different problem).  It is only
the total rate of everyone that isn't an offender that really matters.
(Consider picking grabbing keys from a hat, if it isn't the correct one,
you put it back in the hat, well doesn't matter how many people "dont
look" (not process the key), or how many "yell bingo" (false win), it only
matters how many people are actually looking and checking properly that
decide how quickly we find the key.
(yes, it delays it a little, since keys "checked" aren't processed again
unless we run out, but overall that's fairly negliable)

Anyway, I don't think anyone could handle double checking the current
project :) .  I wouldn't mind for GIMPS though.

In fact, if we -didn't- find a key for RC5, I would be excited.  Then
would come the process of figuring out how and howmuch cheaters were
present!

Cheers,
  Gryn

p.s. pardon some of my spelling please

p.p.s. I don't think this is much of a problem.

> 
> Hmm, there must be a better way to trust results that are coming back
> in than just duplicating work (or duplicating a little bit as a
> doublecheck). Is there someone out there with enough crypto knowledge
> who knows a better way?
> 
> Ivo
> 

--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list