RPOW - Reusable Proofs of Work

mitd writes "Hal Finney is inviting folks to test drive his new hashcash-based server rpow.net. " The RPOW system provides for proof of work (POW) tokens to be reused. A POW token is something that takes a relatively long time to compute but which can be checked quickly." Hal's security model paper is well worth the read and his proof of concept code is available for download. "

Comments

Umm

[Anonymous Coward]

Can someone explain the concept behind this in a little uhh easier terms. I read parts on the website, but I think I need a bit of background before I can really understand what is going on. Thanks

Re:Umm

[Anonymous Coward]

Spammers send millions of email a second, imagine if for every email they had to do some sums that took 2 seconds, before the server would accept the email...suddenly the rate of emails per second falls.....

Re:Umm

[baywulf]

It is essentially a computer algorithm that is time consuming to calculate but fast to verify. It can be used to mitigate denial of service attacks for example. When a connection is made, the server will make a challenge which the client must compute. The server can quickly verify the response and reject the client if it is wrong. The extra computation means the client cannot succeed in an attempt to connect without doing the challenge thus slowing them down.

Re:Umm

[nova20]

Can someone explain the concept behind this in a little uhh easier terms.

Here's how I understand it:

Imagine you have to do a research paper. Though it takes a long time to write this research paper, what you turn in to your professor is (relatively) quickly checked. The paper itself is like a POW token -- It proves that you did the work without you having to redo the work while the teacher is watching.

-nova20

Re:Umm

[masoncooper]

I know you meant to be funny but in a sense, you're right. These reusable tokens can be, well, reused. So if someone were to send you an email with a token, you could use that token(or token based on the previous token) to send an email out without having to create a new token. Since spammers are primarily outbound senders they wouldn't accumulate the tokens that a normal corporation would with frequent two-way communication. In effect, this is a lot like currency.

Re: RPOW - Reusable Proofs of Work

[Anonymous Coward]

Hal's security model paper is well worth the read and his proof of concept code is available for download.

"I'm sorry Dave, but I can't let you download that..."

/.ed

[Dibblah]

Okaaay... So it's a server that's *meant* to serve computationally expensive 'tokens'. And you post it on ./ . Niiice.

Proofs Of Work are few and far between

[Anonymous Coward]

How about Proofs Of Not Working? Got plenty of those.

Cache

[Klar]

Google Cache after slashdotting... http://www.google.ca/search?q=cache:YHGDB5MH4e0J:r pow.net/+&hl=en

Isn't it obvious?

[BubbaThePirate]

A POW token is something that takes a relatively long time to compute but which can be slashdotted quickly.

But seriously, the server went down after two replies, but not before I managed to get this:

[Read this instead adding a load to a battered server]

"Overview

The RPOW server is designed to provide security and reliability through an unprecedented degree of visibility and transparency in its operations. For the first time it will be possible for any user of the system, anywhere in the world, to know what code is running on the server and to inspect that code for loopholes or back doors. I have done my best to make this system secure even against my efforts as the owner, operator and designer of the system to compromise its operations. I welcome public scrutiny of the code and of the design.

The RPOW system represents a new kind of security model, and is therefore unusually challenging to present and to review. RPOW combines an exceptional degree of physical security with an unprecedented level of transparency and visibility into the workings of the RPOW server. This combination implements the design goal of RPOW as a "Transparent Server", a system whose security properties can be analyzed and evaluated from any system on the internet.

In operation, the RPOW system consists of three parts: the server, the host process, and the client library with its associated demo driver. We will consider each part in turn. "

and this

"RPOW FAQs

Questions

1. What is the RPOW system?
2. How is RPOW pronounced?
3. How do I know the RPOW system is secure?
4. What is the difference between RPOW and Hashcash?
5. What is the difference between RPOW and Ecash?
6. What are some possible applications of the RPOW system?
7. How fast is the server?
8. If RPOW becomes popular, how could one server handle all the users?
9. Won't Moore's Law mean that tokens lose their value over time?
10. Why can't users pass RPOW tokens to each other without using a server?
11. Won't the RPOW server run out of disk space if it keeps track of all tokens it has ever seen?
12. Are you going to make changes to the RPOW system?
13. Why did you choose the IBM4758 Secure Cryptographic Coprocessor as the platform for the RPOW server?
14. Wasn't the IBM 4758 security broken a few years ago?

Answers

1. The RPOW system has three parts: client, host, and server. The client is a software library (plus a simple command-line driver for demonstration purposes) to allow generation and exchange of RPOW tokens. The host software runs on the PC which has the IBM 4758 cryptographic coprocessor card plugged into it. It acts as an intermediary, listening for connections from the net and passing data between client and server. It also assists the server with certain operations. The server runs on the IBM 4758 card and performs the secure cryptographic operations which implement the RPOW system.

2. RPOW is pronounced are-pow.

3. The security of the RPOW system ultimately depends on its design and its implementation. For the design, see the theory and security pages. For the implementation, see the source code available from the download page. The unique properties of the RPOW system design allow you to remotely verify that the program generated from the source code you download here is what is actually running on the RPOW server. If the design and implementation are sound, and that program is what is running on the server, you have a foundation for trust in the security of the system.

4. RPOW uses hashcash for its proof of work (POW) tokens. Hashcash tokens are evidence that a certain substantial amount of computer effort was expended to create them. RPOW allows hashcash tokens to be exchanged for RPOW tokens of an equivalent value, which can then be further exchanged for new RPOW tokens. The effect is similar to being able to pass

Proof-of-work tokens as an anti-spam measure?

[JaredOfEuropa]

For those asking what on earth (R)POW tokens are, here's one possible application (from rpow.com):

POW tokens have been proposed as a form of pseudo-payment in several applications. One example is email. An email message containing a POW token would be relatively costly to send in terms of computing power. A POW token could then be a sign that the message was not spam.

Using RPOW tokens for email would have advantages, as people could then reuse tokens from incoming email in outgoing email. Spammers will have no such advantages since almost all of their email is outgoing. Reuse allows the cost of the POW token to be much higher since most people won't have to generate them, making the system more effective as an anti spam measure.

An interesting scheme...

One potential problem I see with such an anti-spam measure is that I keep hearing about spam runs being done from many regular users' computers by means of a spamming worm infrection. Such a worm could also be adapted to generate the POW tokens... or even steal them from the users' incoming email and re-use them under this scheme! That'll be just great, having your computer not only hijacked to send out spam, but loaded down with the heavy burden of generating POW tokens.

Re:Proof-of-work tokens as an anti-spam measure?

[dpilot]

The RPOW website is really easier to understand if you first read the hashcash website it point to. So let's talk first about hashcash, since RPOW is mostly an extension.

With hashcash, I take a datestamp, the recipient's address, and some garbage characters, and put them in an X-hashcash header as part of the email. The garbage characters have been precalculated to give some number of '0's at the front of an SHA1 hash of the header. It's computationally expensive to force those '0's, the more '0's, the higher the expense. (The hashcash site mentioned 4 hours to produce 32 '0's on his system.) But it's cheap to verify that those '0's are there in the hash of the header. That's what makes the system work.

There is no challenge-response in hashcash. You publish a 'price', some number of hashcash '0's, to receive email. If the email is in you whitelist (and presumably has a good SPF) call it good. Call other mail without an X-hashcash header spam. You can then validate the X-hashcash headers on your system. Valid headers are stored, and since they contain a datestamp in cleartext, you can purge them after some interval. Note that you only store valid headers, and only for a limited time, so the database doesn't grow forever.

Hashcash requires no central server or database.

RPOW works off of hashcash. You make a hashcash 'stamp' and trade it in for a RPOW token. Since the RPOW lets that original computational effort be reused, it lets you up the 'price'. ie - require more '0's in the hash.

I haven't read the documentation thoroughly, but I suspect that RPOW is validated at the server, not by challenge/response. But remember that each RPOW ticket is used only once, and once shown secure, there wouldn't be a lot of attempts at spoofing. So the traffic volume (and server requirements) should remain reasonable. In other words, the server traffic would be related to the level of legitimate email, not the level of spam. Oh, when you check the RPOW with the server, it hands back a new RPOW that you can use to send email. As far as I can tell, there is no theoretical (only practical) lifetime limit to the tokens.

I'm less enthusiastic about RPOW than hashcash, simply because of the central server requirement. I also wonder/fear about the feasibility of building an SHA1 engine out of FPGAs that could precalculate stamps faster than any regular PC, and then distribute them to spambots for mailing.

Re:Verify

[3-State Bit]

No, I don't think so. The idea of proving you've done some work is that you have made an investment and so are not doing 100,000 such investments per second.

However this probably doesn't work (PDF) [or as html].

Background (from that paper):

It is often suggested that unsolicited bulk email ("spam") is such a problem on the Internet because the current economic framework for email handling does little to discourage it. If only, it is suggested, the senders of email could be made to pay for their messages. Spammers would then cease their indiscriminate distribution of messages and email volumes would reduce as the senders targeted more carefully or just gave up altogether. Nevertheless, almost no one (other than those hoping for a handling fee) thinks that using actual money is a good way to achieve this economic utopia and even the holders of patents for "e-money" systems have failed to generate any significant enthusiasm for their wares.
However, there is an alternative to real-world money, which was first proposed by Dwork and Naor in 1992 [8]. Their idea was to have the sender of an email perform a complex computation as evidence that they believe that an email is worth receiving. The sender then proves to the recipient that this processing work has been completed and the email will then be accepted. The processing time is "free", so there is a minimal burden upon legitimate senders, but it is a finite resource, so that the spammers will not have unlimited amounts of processing time at their disposal and so cannot continue to send in bulk.

Zombie farms

[Bronster]

What a crock of a system. Let's see:

a) to be useful for anything involving third parties where you don't already have a trust relationship, this would need to be common/easy enough to get that other people already have software to support these things. That's not going to happen any time soon - it's a big enough change you may as well come up with an already secure email infrastructure [insert boilerplate "why your solution to spam is stupid" here].

b) 8 tokens per second? Puhleaze. I get that many emails through just one small server with 5 domains on it.

c) as the subject says. Zombies. In a world where thousands of low TC0 machines are sitting around running malware, it's piss-easy for the blackhat spammers to collect their 8 tokens/second by running POWer@home on their zombie farm.

BZZZZt. Strike three and you're out. Nice idea, but not practical.

Spammers don't send their spam

[Albanach]

Spammers don't send spam, unpatched windows boxes do. Loads of folk here must be getting calls form folk saying "my net connection's slow" you take a look and the machine is infested.

All this means is that, as well as the net connection being slow, the processor will be running overtime calculating the checksums. The spammers will send as many emails as ever.

SPF has to be one of the easiest measures we can take to reduce spam. Spamassassin is about to hit 3.0 RC1 and many more of us will be able to easily associate scores with SPF records. As soon as mail has to originate from the correct domain we get better spam checking and a paper trail for the authorities to follow. If you don't have SPF records for your domain, head on over here or here and set them up.

Re:Huh?

[ifdef]

As I read through the comments on this article, there are a few that seem to indicate that the poster was completely clueless. And then, when I look more closely, I see that all of them were posted by the same person.

Yes, I know that I shouldn't post replies like this, but this is getting annoying. Quite a few people have posted explanations about what this technology could be useful for. Make an effort to understand it, instead of continuing to post "I don't understand" comments.

You said: "Noone's going to install dedicated IBM crypto hardware in their mailservers. No company is going to invest big bucks in a mailserver just so it can run 100% CPU utilization all the time for no good reason. That costs actual real world money, and continues to cost in power usage."

That's absolutely right, and that's the whole POINT of POW tokens. If you are going to send one or two emails, it won't bother you all that much that your computer has to perform a few seconds of computation before your email gets accepted. If you are a spammer and you want to send a MILLION emails, then your computer would have to perform a few million seconds of computation, which would either slow you down tremendously OR force you to pay real money to buy lots of fast computers and power them.

The problem with the CURRENT model of email is that the sender does not have to pay anything to send spam, so they can send millions of them, and it's still worthwhile if they get one reply in ten thousand attempts. But if they had to pay something to send each spam, they would send less.

Junk snail mail senders have to pay for postage, and so, even though they may be annoying, they are not the same kind of problem as spammers are. They tend to send out flyers only for things that they expect to get SOME response for.

You also said "So spammers spam each other (or themselves from a different host) and have an endless supply of RPOW tokens." Again, you've missed the point. If they spam each other, then yes, the recipient now has the ability to send out the same amount of spam, but the sender has used up his tokens by transferring them to the sender. No new POW tokens are created by this process. If I give you $10 and you give me $10, we're NOT both $10 dollars richer -- what I gave you, I no longer have. And if we pass the $10 bill back and forth 100 times, we haven't somehow created $1000 for each of us to spend; we still have the same amount of money that we started with.

And your point about us not wanting secure hardware on our machines is irrelevant. Nothing in this idea implies that you should have secure hardware on your machine. It can all be done in software, open source software (or any other kind).