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:Umm

[aardvarkjoe]

Does that mean that legitimate mailing-lists servers will have to wait 2 seconds for each e-mails they send?

This comes up every single time that someone talks about technical means of stopping spam. And every time, we have to remind you that whitelists can solve the problem trivially. (In this case, you have a system where the receiver [you] accept mail without proof of work from mailing lists.)

Windows 0wned machines computing hashes like a cluster...

Right now, cracked boxes are used for sending spam. If you slow down the rate that it's possible to send spam by 1000, then you get a thousandfold decrease in spam.

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

Obligatory Pun

[grunt107]

Given the inaccessibility of the site:
RPOW/rMIA (break out the black flags w/web server silhouette)...

Re:Obligatory Pun

[trb]

I was thinking, hashcrash-based server.

Anon posting, ARTICLE TEXT

[Anonymous Coward]

Reusable Proofs of Work
by Hal Finney
(hal at finney dot org)
What Is This? Theory Security Try It Out! FAQs Download

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. RPOW uses hashcash, which are values whose SHA-1 hashes have many high bits of zeros.

Normally POW tokens can't be reused because that would allow them to be double-spent. But RPOW allows for a limited form of reuse: sequential reuse. This lets a POW token be used once, then exchanged for a new one, which can again be used once, then once more exchanged, etc. This approach makes POW tokens more practical for many purposes and allows the effective cost of a POW token to be raised while still allowing systems to use them effectively.
Security

This is useful functionality, but the unique feature of the RPOW system is its approach to security. RPOW is the first public implementation of a server designed to allow users throughout the world to verify its correctness and integrity in real time.

Based on principles similar to those proposed for so-called "Trusted Computing", RPOW allows third parties to dynamically and remotely verify what program is running on the RPOW server. The RPOW server is implemented on a high-quality secure processor, the IBM 4758 PCI Cryptographic Coprocessor, which has been validated to the highest level of security publicly available, FIPS-140 level 4. The 4758 is a self-contained single-board computer which has its own device key, generated on-board, which never leaves the card. That key can issue cryptographically signed attestations which describe the software configuration running on the card, including the SHA-1 hash of the application program.

The source code to the RPOW server is available from the download page. Using publicly available tools, anyone can build from this source code a memory image identical to that running on the RPOW server. If the SHA-1 hash of this file matches that being reported by the 4758 device key, the user can conclude that the supplied source code is what is actually running on the 4758. By inspecting the source code he can then make sure there are no "back doors" or loopholes that would allow the owner/operator or designer of the system to defeat its security, for example by creating RPOW tokens without doing the required work.

Allowing clients to dynamically validate the security of a server turns the concept of Trusted Computing on its head. Rather than a threat to individual privacy, the technology becomes a boon to privacy and an empowering force for end users on the net.
Applications

Security researcher Nick Szabo has coined the term bit gold for information objects which are provably costly to create. He suggests that these could even serve as the foundation for a sort of payment system, playing the role in the informational world of gold in the physical world. RPOW would facilitate the use of POW tokens as a form of bit gold by allowing the tokens to be passed and exchanged from person to person.

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.
Transparent Servers
The RPOW system is just the first of what are planned as a series of systems which use this approach, which I call Transparent Servers. Such systems publish their source code for review and inspection, and use Trus

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

Easier Explanation of RPOW & RPOW Uses

[diagnosis]

From the web sites:

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. RPOW uses hashcash, which are values whose SHA-1 hashes have many high bits of zeros.

Possible uses for RPOW include anti-spam tokens, "play money" for use in online games and fun bets, an aid to load balancing in P2P and file-exchange systems, and more. Any system which would benefit from a form of token which can be cheaply passed from user to user, but which is expensive to create, might want to look into RPOW.

It's not clear to me that there is an obvious and immediate equivalent for RPOWs in existence. I'd be interested in hearing what people think this would be good for. It generally seems useful for making sure people do x amount of work before they are allowed to perform a task, but what can that be used for?

---------------------
Freedom or Evil: Freevil.net
G. W. Bush says, "You decide!"

Re:Huh?

[teemu.s]

my guess: cause its unfair if they would not be reuseable. you spent time/money/cputime for getting such a token - so if you spend them - you loose this. but if they are reuseable - and because its about pow tokens, where it can be proven, that you did that work - you just exchange your once made pow token against another and use it for e.g. outgoing email:

form the website:
"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."

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.

dude, that's so excellent...who's hungry?

[eufreka]

Until now, I always thought that "hashcash" was only related to Repeated Puffs of Weed (RPOWs).

And although the process of exchanging "toke'ns" was highly "cryptographic", ultimately not a lot of work got done...

Anyway, I got confused there for a minute, but I am better now. This might help others:

From http://www.hashcash.org/

Hashcash is a denial-of-service counter measure tool. Its main current use is to help hashcash users avoid losing email due to content based and blacklist based anti-spam systems. A hashcash stamp constitutes a proof-of-work which takes a parameterizable amount of work to compute for the sender. The recipient can verify received hashcash stamps efficiently.

Rock on!

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.

Calibration issues

[markh1967]

I'm not sure how well this technique would work in the real world when you have a huge range of systems trying to connect to you. If you set the number of bits in the token so a fast Pentium 4 based system will take two seconds to compute it how many hours would it take a 386, palm-pilot, or Internet enabled phone? Conversely, if you set the number of bits low so that slow systems can compute them in reasonable time then someone with a much faster computer will not be slowed by any noticeable rate and the system becomes useless. If this system is taken up surely it will do more to discriminate against people without state-of-the-art hardware. Surfing is annoying enough on a very slow machine without having to wait for 30 minutes to compute the RPOW before the site will let you connct.

Keeping honest folks honest

[vile8]

Great, I was just complaining the other day that my computer is a lazy, good for nothing document editor. Here I sit with 3ghz and a gig of ram and nothing to actually process other than ps streams.

Since its based on working your computers resources perhaps other names could possibly be "RPOW by Jake"? Or "RPOW's of steel"?

Seriously, what happens next year when its not computationally expensive to compute the tokens? Ew, or what if you are a clever spammer with a degree in electrical engineering and the time to make your own token generating card to sell to all the other spammers on ebay for a small fortune (or you could prove it works by spamming them with advertisements...)?

Well, its always good to have another device to keep honest folks honest I guess.

Let's make it do something useful

[kanweg]

Now, if this concept of having the sender do something is changed into having the sender do useful (Folding at home or another distributed computing project), it would be a nice twist.

Bert

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).

Reusable Tokens

[cbr2702]

If I recieve a token from someone else, can I copy it and attach it to multiple messages? If so, what's to stop spammers from calculating one token and attaching it to a large number of messages?