Stored Hashcash

One of the greatest inventions in the history of computer security is Hashcash. Internet blights like spam and denial-of-service attacks are what economists call “tragedy of the commons” problems. They exploit the fact that it’s free to send email and make web requests. At zero cost, you can have a profitable business even at extremely low success rates.

One way to fix these problems is to impose tariffs that hurt bad actors without hurting good actors. For example, you could impose “postage fees” on every email and web request. Unfortunately, in practice, this is impossible, because you’d have to set up billing relationships between every computer that wants to communicate.

The brilliant idea behind Hashcash is to replace a monetary postage fee with a computational postage fee. In order to send an email, the sender first has to solve a math problem. Legitimate activities suffer an indiscernible delay, but illegitimate activities that require massive volume are hobbled.

Hashcash is a great idea, but cumbersome in practice. For example, the cost imposed on senders varies widely depending on the performance of their email servers. It also hinders legitimate bulk emails like clubs and retailers sending updates to their mailing lists.

The offline analogy to Hashcash is a postal system where senders are required to perform some work every time they want to send something. If you’re a lawyer, you need to practice some law before you send mail. If you’re a doctor, you need to cure something before you send mail. Etc. This of course would be a preposterous postal system.

Adam Smith called money “stored labor“. You do your work and then store your labor as money, which you can later exchange for labor stored by other people. Storing labor in the form of money turns out to be a very flexible system for trading labor, and far superior to the barter system of performing work whenever your counterparty performs work.

So Adam Smith’s version of Hashcash is a system where you get credits for doing computation. You store your computational credits and spend them at your leisure. If you want to send an email, you can spend a little stored Hashcash. If I send you an email and you reply, we’re even. If you send out a billion spam emails, it costs you a lot and undermines your spammy business model. 

There are other important problems that stored Hashcash could solve. Denial-of-service attacks are spam attacks except they happen on HTTP instead of SMTP and the payoff is ransom instead of spam offers. Computer scientists have long believed that pricing schemes could dramatically reduce network congestion. Like every large-scale distributed system, the Internet benefits when scarce resources are efficiently allocated.

It seems plausible that if a system like stored Hashcash were developed, some people would prefer to purchase stored Hashcash directly instead of generating it themselves. A market for stored Hashcash would emerge, with the value being some function of the supply and demand of scarce Internet resources.

So here’s my question: suppose someone invented a way to store Hashcash. It could dramatically reduce spam and denial-of-service attacks, and more efficiently allocate network bandwidth and other Internet resources. How valuable would stored Hashcash be?

36 thoughts on “Stored Hashcash

  1. deepwatrcreatur says:

    It shouldn’t be difficult to prevent the tragedy of the commons with appropriate property rights, and I think you see that by wanting to charge for email delivery and web requests, etc. But why do we need to develop a new monetary unit for that purpose? Crypto-currencies have a severe deficiency in that they tend to be very unstable in value, and the work involved in proof-of-work systems tends to be wasteful of resources. Bitcoin enthusiasts note that there is no good system for micro-payments in dollars. But ISPs are pretty good at counting the exact number of packets we use when billing us for data, and likewise they should be able to incorporate fees for sending email and web requests based on aggregates, without needing a solution to the micro-payments problem.

  2. Simone Brunozzi says:

    I don’t think that hashcash should also be the currency. I’d simply like to see a system like this in effect, where each email server needs to “buy” some credit in advance. 0.0005$/email would be a fair amount. No need to involve bitcoin in this; you could simply buy a 10$ certificate and send 20,000 emails with it. The big question is: how can I convince EVERY email server on the planet to adopt it? Well, it could be gradual. “certified” email would be less spammy, and over time anti-spam filters would start trusting it more, etc. Not easy to do.

  3. mherf says:

    Great post!

    Few thoughts:
    1. Proof of work needs to get harder over time, or the work required becomes trivial in a few years. (You could “merge” currency over time as hardness doubled…)
    2. Many systems are challenge/response because they can’t allow replay attacks (hardest problem with your idea I think? I don’t have a good idea for this.)
    3. GPU is 100-1000x faster than CPU, so people could publish free “stored” work vastly greater than they’d personally need.

    Neat thing: we used Hashcash for spam prevention when sending mail from Picasa in 2003. All our clients had relatively similar-spec machines, which is sort of the best situation for using it.

  4. pasha sadri says:

    Stored labor implies the original labor was valuable (eg practicing law). Is mining for bitcoins a valuable activity in as of itself?

  5. deepwatrcreatur says:

    Mining bitcoins enables a distributed ledger of transactions, which is useful for people who want to make illegal sales without meeting in person, or who want to bypass restrictions on transmitting money between countries, etc. But the case described in this post doesn’t require a distributed ledger; it should be legal to charge for access to the inbox.

  6. clienthunter says:

    “How valuable would stored Hashcash be?”

    You said legitimate users would not be able to discern the presence of the required computations, so we can infer that commoditized units of hashcash are of no value to them: there just isn’t a situation where they’d want to buy more.

    Spammers are the only people who value it. You said that price would be function of “the supply and demand of scarce internet resources”, but this isn’t the case here, there is no scarce resource being allocated. Demand – and ergo price – would be a function of the underlying spammy goods. Just as money is “stored labour”, hashcash would become stored mail order viagra.

    The supply curve isn’t really worth discussing until the proof of work function makes electricity price a factor. I’m assuming such a function’s difficulty evolution is predictable or even defined with high accuracy. Mapping difficulty to electricity price is not hard as any BTC miner can attest.

    So…

    D= f( E[aggregate spam conversion rate], E[aggregate spammy product price])
    S= f( a, W )

    Where E is the expectation operator, a is the ‘difficulty function’ function defined above, and W is the price of electricity. Price is where the two lines meet, i.e. when D=S. It’s not actually ridiculous to suppose you could figure out a number today if you did your research right.

  7. Jonathan Wilkins says:

    The problem with hashcash as a spam prevention method is that it presumed a certain level of asymmetry that hasn’t held up. Today, spammers would just use botnets to externalize the costs.

    There were a few proposals for email bonds where you put up a certain amount in escrow and forfeited it if enough people flagged your messages as unwanted. This could work with bitcoin pretty easily and be a better tradeoff.

  8. Martin Drapeau says:

    The problem with Hashcash or any type of toll is that it creates a barrier to entry. I operate a small website and would hate to have to add complexity and pay for this on top of what I already do. Computation costs money.

    It also breaks the free web model which is so fundamental.

  9. Just curious why hasn’t this taken off, given it was invented in 1997? It seems to make sense theoretically, as a deterrent factor against spamming. Has it been put in practice for tests?

  10. Bitcoin would be the way to go, as some people have already mentioned.

    And I think it would be pretty to implement with little or no changes on both client and server

    - SMTP(E) already supports extensions for authentication
    - most email servers (qmail, postfix that I know of) already permit the creation and use of plugins

    It would basically be a problem of implementing a plugin using bitcoin as the authentication. It would work this (simplified) way:
    - client connects
    - server says hello
    - server would send AUTH STANDARDAUTH
    - authenticated users would login
    - if previous authentication failed, server would send AUTH BITCOIN DESTINATIONWALLET (plugin serverside)
    - client would have to transfer some amount of btc to specified address
    - client would have to reply with a btc transaction id/address (client/spammers problem)
    - server would check the transaction and allow login if transaction was valid or deny login if invalid or non-existent; aditionally this would have an impact on the client/spammer since a bitcoin transaction takes some time to be verified

    Some issues and answers:

    - this would mean making some changes on the client side; that would be the spammers problem, authenticated users would still login with no changes on their side; spammers already have the capability of messing with the email headers, so “you want it to work then implement it”

    - it would create a problem of “you’d be selling your users addresses to be spammed”; yes,especially if you used your own bitcoin wallet address to get the bitcoins; this could be solved by creating an opt-in list where users would register their wallet address and receive the spammers bitcoin transactions; maybe make the servers operator bitcoin wallet address the default one; this would also allow the servers operator to create multiple honeypot/false email addresses registered in the the opt-in list, publicize them, and have an aditional revenue stream with marginal costs; servers operator would actually be charging the spammers for any spam they might able to put through existing spam filters; and the spam messages wouldnt actually be delivered ie. no gains, just costs on the spammers side.

    - spammers could use the transaction id repeatedly since it would always be valid; yes, some registration of transaction ids would have to exist in the serverside plugin and no repeated ids would be allowed

    Some previous posters comments:
    - “until the proof of work function makes electricity price a factor”: bitcoin payments would be a perfect proxy for energy consumption
    - “Proof of work needs to get harder over time”: bitcoin would do this
    - “Many systems are challenge/response because they can’t allow replay attacks”: yes, registering transaction ids and refusing duplicates would solve this, see above
    - “I operate a small website and would hate to have to add complexity and pay for this”: there would be no changes in existing client code, as long as a standard auth was provided
    - “spammers would just use botnets to externalize the costs”: they would be free to do that, we accept any colour of bitcoins :-)
    - “Stored labor implies the original labor was valuable (eg practicing law). Is mining for bitcoins a valuable activity in as of itself?”: some people make money by buying something cheap and selling it at a higher value; and they actually store their labour in small pieces of paper and small round pieces of metal; is intermediating/arbitrage a valuable activity? yes, as long as people believe in pieces of paper that store the value of the transactions; in some countries, like in Venezuela, people stop believing in the small pieces of paper that are printed there and change their labour store to the small pieces of paper printed in other countries :-)

    – MV

  11. kloplop321 says:

    Well–regarding denial-of-service attacks, wouldn’t the receiving server need to validate the hashcash? Sure, it might be a constant thing to check, and the requester will get a failure response on a bad hashcash, but since when do denial-of-service attackers care about the response?

  12. Terry A Davis says:

    Let’s say you want to make a list of unique words in a document. Make an array of linked lists about 1024. Go through each word. Add up tht letters. Use the sum as an index in the 1024 table. If you find a linked list, already, search the list for this word. If the word is not there, add it to the linked list.
    This is a hash table. It turns-out a use for hash tables is in security, also.

  13. Most of these schemes are designed so good actors are relatively unaffected. E.g. if you send roughly as many emails as you receive you are Bitcoin neutral.

  14. (btw stored hashcash=Bitcoin). I agree the chicken and egg problem is enormous. You need the kind of momentum Bitcoin currently has to overcome it.

  15. kloplop321 says:

    I feel like you missed my point entirely.

    Who’s to stop denial of service attackers from denying the service at the hashcash validation layer?

  16. Sounds to me like you are trying to find a use for Bitcoin. DoS and Spam are issues, but not to the point of requiring the added complexity Hashcash brings to the table.

  17. “spammers could use the transaction id repeatedly”

    You could embed a hash of the headers+body in the Bitcoin transaction script so that it would only be valid for a particular email.

    Additionally, if you don’t care about the actual recipient or SMTP provider receiving the funds, the SMTP server wouldn’t even need to publish an address at all: the sender could either give the funds to the miner (providing them with an incentive to mine it in the next block), or “burn” the funds by making them unspendable (effectively increasing the value of everyone else’s Bitcoins verrrrrry slightly)

    The bigger problem with this scheme is Bitcoin currently can’t handle more than 7 transactions per second. Putting a transaction on the blockchain for every email is untenable.

  18. ‘each email server needs to “buy” some credit in advance’

    Where would those “credits” be stored? A centralized email credit service? No thanks.

    The power of email (SMTP) is that it’s decentralized, and thus doesn’t require permission from anyone to participate. As soon as you want to transact with dollars (or euros or whatever) online you need to ask someone (PayPal, Stripe, etc) for permission, and trust them to move the dollars to the right place when you tell them to.

    Bitcoin solves exactly that problem. If you were to build a decentralized email credit system using algorithms known today you would end up with Bitcoin.

  19. I liked Hashcash so much I bought the scientist :) (well actually hired him in 1999 to implement & build anti-abuse, denial of service protections, electronic cash and private identity systems). Dr. Adam Back is one bright guy. One point that I think is worth pointing out is that although this is a great way to describe bitcoin, bitcoin itself may not be the answer to all the potential applications of stored hashcash.

    Bitcoin has created a global proof of work distributed consensus system that is powerful (the global hashrate). This year $200 million will be spent on hardware adding capacity to this infrastructure. While I hate alt.coins – there are many uses of this global capacity that may not be denominated in BTC. Understanding the cryptographic systems to leverage this capacity to allow applications beyond bitcoin as an asset class will be an interesting adventure for the industry.

  20. Adam Back says:

    Well in the specific case of hashcash (as opposed to stored or reusable hashcash aka bitcoin) the verification is local, and the protocol is fully scalable to email scale as it has no new network interaction, and is extremely efficient – a few thousand machine cycles, something like cost to process a tcp packet. So no you cant DoS the hashcash verification. You would probably use an interactive variant (described in the 2002 paper) where you can verify the stamp without consuming TCP connection slots, like syn-cookies.

    It turns out that bitcoin verification itself is more scalable than you would think with some newer stuff while retaining all bitcoin properties. Programmable trust is a very flexible thing, and I dont think people have scratched the surface of what will be buildable. Fortunately it can be made to scale also.

  21. kloplop321 says:

    I am ignorant when it comes to programmable trust.

    Perhaps I am missing something fundamental. Are you saying to verify it costs as much as processing a TCP packet, or creating the hashcash in the first place?

  22. The key property of proof-of-work is that it’s difficult to create the PoW (e.x. brute force a partial hash collision) but easy to verify (e.x. hash once, check for the partial collision).

  23. Doesn’t facebook already do this? They charge advertisers sending bulk messages, while offering the services for free to message neutral users and stop spammers by putting a captcha on the account creation process.

  24. dodgit says:

    the severely unstable value of bitcoin makes this a difficult application. perhaps some different crypto currency would work better, one designed more towards usage rather than hoarding.

    the theft aspect of bitcoin makes such a system enrich and empower thieves and criminals. is this really what we want our email system to do?

  25. I find the programmable trust application in BitMessage [if anyone wants to send me a message - BM-2cWdngMEsKaT8PMzyCK4zJJbCj2iDngSMo] particularly fascinating since settings like difficulty can be changed (1) by the receiver for sending to a particular address or requiring a total difficulty and (2) the sending setting a maximum difficulty willing to do to send.

    And I can only imagine what type of fascinating applications the brilliant minds like yourself will come up with when applying to systems like Maid Safe.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s