The SETI@Home Protocol
March 6, 2000
Speaker: David Molnar
Scribe: David Andersen

Handout

Protocol Parties

Primitives

We assume we have a collision-resistant hash function, which we can denote h(). We further assume that we have the ability to make a transcript of a computation.

Protocol

  1. Server sends work unit to client.
  2. Client performs work on work unit. Client creates transcript S of computation.
  3. Client computes h(S).
  4. Client sends result of work unit and h(S) to the server.
  5. Server flips a coin at random to decide whether to audit client. Alternatively, the server selects a random subset of clients to audit and checks whether this client is in that set.
  6. If server decides to audit Client, then server re-does computation on work unit, creates a transcript S', and then computers h(S'). Alternatively, server asks Client to send a transcript S' for the specified work unit. The client sends a transcript, which the server checks for correctness, and then computes h(S').
  7. Server checks to see whether h(S) = h(S'). If they do then client is considered compliant. If they do not, then client is considered cheating.

Questions I have

What are the exact requirements for the transcript? Paul Crowley on sci.crypt suggested that producing a fake transcript must be at least as expensive as producing a real one. In addition, we also want that a fake transcript can be identified as fake on inspection. What else?

Why do we have the hashes at all? Why doesn't the server just check the work directly?

What other kinds of problems will this approach help? What problems seem similar but will not be helped?

Discussion

With the questions raised by the handout in mind, David Molnar from Harvard summarized the SETI problem:

SETI@Home

One very-discussed solution to the clients is to remove the incentive for modified clients by eliminating rankings. Some other projects have taken this approach, but it's also a useful tool for building and maintaining user interest. Unfortunately, removing rankings does nothing to combat actively malicious users who wish to forge or hide data.

Transcription

What kind of transcript can be used?

Other verification

Can we detect clients based on their long-term history as a weight? Can we perform early detection, and what do we do if too many (2/3s or more) of the clients are taken over?
Brought to you by the MIT LCS Applied Security Reading Group