document popularity estimation / amortizable hashcash (Re: Hollywood Hackers)

[Adam Back]

This paper is quite interesting and proposes another method of
metering content [1]:

	http://citeseer.nj.nec.com/naor98secure.html

It's proposed in the context of web site traffic metering to determine
site traffic rates (for advertising payment or other applications).

It relies on a trusted auditor, which could become a central failure
point so is perhaps less attractive for file sharing, but perhaps that
could be fixed.

Another problem is that it presumes a communication pattern where the
auditor sends a secret to each user, the user makes a cheap
computation involving the secret to send with each request, and then
the respective server collects all of the requests it gets and does
some computation to arrive at a compact proof that it received some
number k of requests.  (The server also receives a secret, but this is
not problematic, it it anyway wants to participate).

On the plus side their approach is not probabilistic -- it gives an
accurate measurement of traffic, it is also not vulnerable to server
traffic inflation, and is somewhat resistant to multiple client and
server collusion.  (Though of course any scheme is generically
vulnerable to server traffic inflation -- servers can _act_ as
multiple clients and simply generate the claimed traffic themselves,
or contract other parties to do this for them.)

Adam

[1]

@article{Naor:98:secure-and-efficient-metering
    author = "Moni Naor and Benny Pinkas",
    title = "Secure and Efficient Metering",
    journal = "Lecture Notes in Computer Science",
    volume = "1403",
    pages = "576--??",
    year = "1998",
    note = "Also available as \url{http://citeseer.nj.nec.com/naor98secure.html}" 
}

On Wed, Jul 31, 2002 at 09:34:35PM +0100, Adam Back wrote:
> I proposed a construct which could be used for this application:
> called "amortizable hashcash".
> 
> 	http://www.cypherspace.org/hashcash/amortizable.pdf
> 
> The application I had in mind was also file sharing.  (This was
> sometime in Mar 2000).  I described this problem as the "disitrbuted
> document popularity estimation" problem.  The other aspect of the
> problem is you have to distribute the popularity estimate and make it
> accessible, so I think you want it to be workably compact (you don't
> want to ship around 1 million hash collisions on the document hash).
> Amortizable hashcash addresses this problem.
> 
> There is also some discussion of it here:
> 
> 	http://archives.neohapsis.com/archives/crypto/2000-q1/0440.html
> 
> Adam
> 
> On Wed, Jul 31, 2002 at 04:25:30PM +0200, Eugen Leitl wrote:
> > It should use scarce resources (e.g. crunch) to generate a trust
> > currency in each node, a kind of decentralized mint (nothing
> > crunches quite a few million boxes on the Net).