Hal Finney: RPOW - Reusable Proofs of Work
2004 Aug 15
See all posts
Hal Finney: RPOW - Reusable Proofs of Work @ Satoshi Nakamoto
- Author
-
Hal Finney
- Email
-
satoshinakamotonetwork@proton.me
- Site
-
https://satoshinakamoto.network
I'd like to invite members of this list to try out my new
hashcash-based server, rpow.net.
This system receives hashcash as a Proof of Work (POW) token, and in
exchange creates RSA-signed tokens which I call Reusable Proof of Work
(RPOW) tokens. RPOWs can then be transferred from person to person and
exchanged for new RPOWs at each step. Each RPOW or POW token can only be
used once but since it gives birth to a new one, it is as though the
same token can be handed from person to person.
Because RPOWs are only created from equal-value POWs or RPOWs, they
are as rare and "valuable" as the hashcash that was used to create them.
But they are reusable, unlike hashcash.
The new concept in the server is the security model. The RPOW server
is running on a high-security processor card, the IBM 4758 Secure
Cryptographic Coprocessor, validated to FIPS-140 level 4. This card has
the capability to deliver a signed attestation of the software
configuration on the board, which any (sufficiently motivated) user can
verify against the published source code of the system. This lets
everyone see that the system has no back doors and will only create RPOW
tokens when supplied with POW/RPOW tokens of equal value.
This is what creates trust in RPOWs as actually embodying their
claimed values, the knowledge that they were in fact created based on an
equal value POW (hashcash) token.
I have a lot more information about the system at rpow.net, along
with downloadable source code. There is also a crude web interface which
lets you exchange POWs for RPOWs without downloading the client.
This system is in early beta right now so I'd appreciate any feedback
if anyone has a chance to try it out. Please keep in mind that if there
are problems I may need to reload the server code, which will invalidate
any RPOW tokens which people have previously created. So don't go too
crazy hoarding up RPOWs quite yet.
Thanks very much -
Hal Finney
RPOW Theory
Tokens
Tokens in the RPOW system are of two types: proof of work (POW)
tokens, and reusable proof of work (RPOW) tokens. The POW tokens used in
the RPOW system are pieces of hashcash, invented by Adam Back and
well described at that link.
Hashcash
Hashcash is a textual string in a particular format which has a
special property: when run through the SHA-1 hash algorithm (the same
algorithm used in the sha1sum utility often used to validate downloaded
files) the result has the first N of its initial bits equal to zero,
where N is typically around 20-30. The terminology used for hashcash
describes the number of leading zero bits as the size of its
"collision". Because of SHA-1's properties, the only way to find a
string with a large collision size is by exhaustive search: trying one
variation after another, until you get lucky.
Here, for example, is a hashcash token with a 28 bit collision (or we
might say it is "worth 28 bits"):
1:28:040727:halmail1@finney.org::1c6a5020f5ef5c75:63cca52
And here is the SHA-1 hash of that text string:
0000000a86d41df172f177f4e7ec3907d4634b58
See? It starts with 7 digits of 0, which in this hexadecimal
representation means 7*4 or 28 bits.
The chance of any bit being a zero is 1/2, so the chance of finding
the first N bits being zero is one in two to the Nth power. This means
that you must try, on the average, about one million test strings before
finding one with a 20 bit collision; or about a billion test strings
before finding a 30 bit collision. These calculations can take from
seconds to hours on modern computers. In general, finding a one bit
longer collision will take twice as long.
This means that if you think of a piece of hashcash as having a
"value" which is the size of the bit collision, then a piece of hashcash
with a value one higher is in effect twice as rare and twice as
"valuable". A piece of hashcash with a value of 30 is actualy 1024 times
more valuable (in terms of difficulty of creation) as one of value 20,
because it is 10 bits higher value and 2 to the 10th power is 1024.
What makes hashcash useful is not just that it is relatively
time-consuming to produce, but that it is quick to verify. Once a
hashcash token is created, it can be verified by running the string
through the SHA-1 algorithm and counting the leading zeros. This is
almost instantaneous, despite the fact that it may have taken a long
time to produce the hashcash.
Hashcash therefore provides a means by which someone can prove very
easily and quickly that they spent (on average) some specified amount of
computer cycles to create the token. In particular, it can be used to
show that the sender spent a lot of time to create the token. Hashcash
therefore serves as evidence of effort, and in many contexts can be used
to demonstrate a level of importance or significance to a message or
some other kind of data.
Reuse
One of the problems with hashcash tokens is that they cannot be
reused. The risk is that someone could perform an extensive calculation
and produce a high-value hashcash token, one with a large collision of,
say, 36 bits. On my present-day laptop computer this would take about
one day. But if, having created the token, they could use it as many
times as they wanted, this would provide misleading evidence to the
recipient of the attention that they were receiving. That one-day effort
could be spread over thousands or millions of recipients, making the
per-message effort negligible. Under these circumstances, users would
have no way of knowing the true value of hashcash tokens, and they would
not be useful.
To avoid this, hashcash tokens have embedded within them a "resource
string". This is supposed to identify the particular use for which the
token is intended, and should be sufficient to allow the recipient to
make sure the token could not be used for any other purpose. For the
case of email, the resource might be the email address of the recipient.
When a hashcash token is received for such a purpose, the receiver
(i.e. his software) must check the hashcash resource string and make
sure it matches the expected value.
In addition, recipients of hashcash need to keep a local record of
all of the hashcash tokens they have received recently, so that they can
detect the case where someone tries to send them the same piece of
hashcash more than once. In order to keep this local hashcash database
from growing indefinitely, hashcash also embeds the time and date of its
creation within the text string that gets hashed. This allows hashcash
recipients to expire old values from their database and only keep the
hashcash tokens they have seen within recent days.
RPOW Tokens
Reusable proof of work (RPOW) tokens extend on hashcash to provide a
limited form of reuse. As explained above, allowing hashcash to be
freely reused would make the tokens effectively worthless, as there
would be no limits to how many times a given token could be shown. RPOW
tokens provide a limited form of reuse called sequential reuse. In
essence, once a POW token is created in the form of a piece of hashcash,
it can be exchanged at an RPOW server for an RPOW token of equal value.
The RPOW token can then be exchanged, sent, or otherwise used similarly
to a hashcash token. However, rather than being effectively discarded
after use, the RPOW token can be exchanged by the recipient at the RPOW
server for a new, equal-value, RPOW token. This token can be used
exactly like the first one. It can be sent to a recipient, who can
verify and exchange it at an RPOW server, just as they might do for a
POW token. And that new recipient can, after exchanging the RPOW token
at the server and receiving a new one in exchange, retain the new RPOW
token and use it again in the future.
In this way, a single POW token is the foundation for a chain of RPOW
tokens. The effect is the same as if the POW token could be handed from
person to person and retain its value at each step.
Security researcher Nick
Szabo has coined the term bit gold to refer to a
similar concept of tokens which inherently represent a certain level of
effort. Nick's concept is more complex than the simple RPOW system, but
his insight applies: in some ways, an RPOW token can be thought of as
having the properties of a rare substance like gold. It takes effort and
expense to mine and mint gold coins, making them inherently scarce. Gold
coins can then be passed from person to person, and each recipient can
verify the authenticity of the coinage.
In a similar way, RPOW tokens take a certain level of effort and
expense to be created. They all start with a hashcash collision which,
at the higher levels, will take hours or even days of computing time to
create. RPOW tokens can be validated and verified upon receipt by
exchanging them at the RPOW server for a new RPOW token. This allows
them to be passed from person to person much like coins.
Most importantly, the RPOW system is architected with one overriding
goal: to make it impossible for anyone, even the owner of the RPOW
server, even the developer of the RPOW software, to be able to violate
the system's rules and forge RPOW tokens. Without such a guarantee
against forgeability, RPOW tokens would not credibly represent the work
that was done to create them. Forgeable tokens would be more like paper
money than bit gold. My goal in this project was to bring to life a
simple realization which demonstrates the power of the bit gold concept.
This requires resistance to forgeability, and this goal has dominated
every part of the design.
See the security page
for more detail on how the system is designed to resist forgery, and
the World
of RPOW page for information on the potential for a worldwide
network of RPOW servers.
An RPOW token is composed of several parts:
The most important are the id and
the bignum. The id contains 20 random
bytes, along with some extra data to be described later.
The bignumis an RSA signature on a value created by
extending the id with repeated hashing to add
redundancy:
| 0 - 19 |
20 |
21 - 40 |
41 - 59 |
... 127 |
Byte numbers (MSB first)
This value is interpreted as a 1024 bit bignum value, and
exponentiated with the secret exponent of an RSA signing key. The result
is thebignum field of the RPOW. The RPOW can be
mathematically verified by raising the bignum value to
the appropriate public exponent, and comparing the result to the
extended id value, created using the pattern shown
above.
RPOWs can be of different values, just as POWs can. The value of an
RPOW is stored in its value field and is equivalent to
the number of bits in a POW collision. Each RPOW value corresponds to a
public exponent, according to the following rule. The lowest RPOW value,
which corresponds to a 20 bit POW collision, is mapped to an RSA public
exponent of 65537. Successively increasing values are then mapped to
consecutive primes above 65537, leading to the following table:
| 20 |
65537 |
| 21 |
65539 |
| 22 |
65543 |
| 23 |
65551 |
| 24 |
65557 |
| 25 |
65563 |
| 26 |
65579 |
| 27 |
65581 |
| 28 |
65587 |
| 29 |
65599 |
| 30 |
65609 |
| 31 |
65617 |
| 32 |
65629 |
| 33 |
65633 |
| 34 |
65647 |
| 35 |
65651 |
| 36 |
65657 |
| 37 |
65677 |
| 38 |
65687 |
| 39 |
65699 |
| 40 |
65701 |
| 41 |
65707 |
| 42 |
65713 |
| 43 |
65717 |
| 44 |
65719 |
| 45 |
65729 |
| 46 |
65731 |
| 47 |
65761 |
| 48 |
65777 |
| 49 |
65789 |
| 50 |
65809 |
The RSA key which signed the RPOW is indicated by
the keyid field. The keyid is a SHA-1
hash of the RSA modulus and exponent, each preceded by a four-byte byte
count field. Initially there is only one RPOW signing key and only
one keyid, but over time there may be more RPOW signing
keys created, as described on the World of
RPOW page. To verify an RPOW it is necessary to know which RSA key
signed it. The keyid implicitly identifies the RSA
modulus, and the value identifies the RSA exponent;
together they define the RSA verification key.
No Inflation Principle
Unlike with POWs, it takes no longer to create high valued RPOWs than
low valued ones. Nevertheless, RPOWs are considered to have the same
value as equivalent POWs. The reason is that the only way that an RPOW
server will sign a bignum with an exponent of a certain value, is if it
receives in exchange an equal-value POW or RPOW token. The RPOW server
thus enforces conservation of value, also called the no-inflation
principle. RPOWs will only be created when POWs or RPOWs of equal value
are exchanged for them.
To enforce the no-inflation rule, the RPOW server must make sure that
no POW or RPOW can be used more than once as part of an exchange. Each
one is created, and then exchanged at the server for a new RPOW, and
after that, the old one can never be used again. The RPOW server
enforces this rule primarily by keeping a record of all of the RPOWs and
POWs that it has seen in the past. Whenever one is offered for exchange,
the RPOW server compares it against this database of previously-seen
RPOWs. If it is on the list, this is an attempt to reuse the POW or
RPOW, and the exchange request is rejected. If the POW or RPOW is not on
the list, it is added to the list, and then the RPOW server will sign
the bignum value supplied as part of the exchange, creating a new
RPOW.
Initially, a POW is created of a certain value, represented by the
size of the hash collision (number of leading zeros in the hash value).
This can then be exchanged for an RPOW whose signing exponent represents
the same value. This RPOW can be transferred and further exchanged for
equal value RPOWs. Each RPOW can only be used at one step, but as it is
destroyed it allows a new RPOW of equal value to be created in the
exchange operation. The result is as though the original POW could be
handed from person to person while retaining its value.
Time to Split?
In addition to allowing straight one-for-one exchanges of equal
value, the RPOW server allows exchanges where tokens are split or
combined in various ways. The rule is that the combined value of the new
RPOWs must equal the combined value of the incoming POWs and RPOWs which
are being exchanged.
When calculating these values it is important to take into
consideration the property of POWs described above, that one with a
value of one greater is actually worth twice as much (in terms of
expense to create). This means that you can, for example, exchange a
single token worth 21 for two with values of 20. Or you could go the
other way and exchange two tokens worth 24 for a single one worth 25.
The general formula is to add two to the power of
the value field for each incoming POW and RPOW, and do
the same thing with the requested outgoing RPOWs. Only if the results
are equal will the RPOW server allow the exchange.
More examples of some legal exchanges would be two 24's, a 25, and
two 29's for a 26 and a 30; or a 32 exchanged for a 31, a 30, a 29 and
four 27's. Using these rules, an RPOW server will allow you to split or
combine your existing RPOW tokens in a variety of ways.
This creates a great deal of flexibility in how RPOWs are used, as
you don't have to calculate in advance the exact sizes or values you
will need. You could keep a few relatively large RPOWs around and then
split them into smaller values to give to someone else. Or if you
receive a large number of RPOWs, you can combine them and store just a
few higher valued ones.
It also means that you can generate large RPOWs in a more systematic
way than simply trying to find a really large POW hashcash collision.
You can create smaller collisions, exchange them for RPOWs, and combine
them. Suppose you wanted to create, say, a 36 bit RPOW and on your
machine that would take a day of compute time. Instead, you could create
30 bit RPOWs, each one taking only about half an hour on average, and
then combine 64 (2 to the 6th power) of those to create your 36 bit
RPOW. It's the same amount of compute time on average, but by splitting
it up into smaller pieces you decrease the randomness and make the time
to create a certain size RPOW more predictable.
More info
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
Trusted Computing-like features to prove that they are running the
program generated by that code. This will provide an unprecedented level
of transparency and visibility into the workings of network servers.
Perhaps most importantly, the use of transparency can actually increase
end-user privacy. For the first time, users will be able to verify how
network servers will handle sensitive information they provide. In the
case of the RPOW server, users can see that the program makes no record
of transactions and creates no linkage between the RPOW issued in one
exchange with the same RPOW when it is later deposited, thereby
protecting privacy. In addition, the basic security goal of the system,
that it will never issue RPOWs without receiving a POW or RPOW of equal
value, can be independently verified. Not even the owner of the RPOW
server can break these rules.
For more information on the techniques used to provide these new and
previously unavailable assurances, see the security page.
Hal Finney: RPOW - Reusable Proofs of Work
2004 Aug 15 See all postsHal Finney
satoshinakamotonetwork@proton.me
https://satoshinakamoto.network
I'd like to invite members of this list to try out my new hashcash-based server, rpow.net.
This system receives hashcash as a Proof of Work (POW) token, and in exchange creates RSA-signed tokens which I call Reusable Proof of Work (RPOW) tokens. RPOWs can then be transferred from person to person and exchanged for new RPOWs at each step. Each RPOW or POW token can only be used once but since it gives birth to a new one, it is as though the same token can be handed from person to person.
Because RPOWs are only created from equal-value POWs or RPOWs, they are as rare and "valuable" as the hashcash that was used to create them. But they are reusable, unlike hashcash.
The new concept in the server is the security model. The RPOW server is running on a high-security processor card, the IBM 4758 Secure Cryptographic Coprocessor, validated to FIPS-140 level 4. This card has the capability to deliver a signed attestation of the software configuration on the board, which any (sufficiently motivated) user can verify against the published source code of the system. This lets everyone see that the system has no back doors and will only create RPOW tokens when supplied with POW/RPOW tokens of equal value.
This is what creates trust in RPOWs as actually embodying their claimed values, the knowledge that they were in fact created based on an equal value POW (hashcash) token.
I have a lot more information about the system at rpow.net, along with downloadable source code. There is also a crude web interface which lets you exchange POWs for RPOWs without downloading the client.
This system is in early beta right now so I'd appreciate any feedback if anyone has a chance to try it out. Please keep in mind that if there are problems I may need to reload the server code, which will invalidate any RPOW tokens which people have previously created. So don't go too crazy hoarding up RPOWs quite yet.
Thanks very much -
Hal Finney
RPOW Theory
Tokens
Tokens in the RPOW system are of two types: proof of work (POW) tokens, and reusable proof of work (RPOW) tokens. The POW tokens used in the RPOW system are pieces of hashcash, invented by Adam Back and well described at that link.
Hashcash
Hashcash is a textual string in a particular format which has a special property: when run through the SHA-1 hash algorithm (the same algorithm used in the sha1sum utility often used to validate downloaded files) the result has the first N of its initial bits equal to zero, where N is typically around 20-30. The terminology used for hashcash describes the number of leading zero bits as the size of its "collision". Because of SHA-1's properties, the only way to find a string with a large collision size is by exhaustive search: trying one variation after another, until you get lucky.
Here, for example, is a hashcash token with a 28 bit collision (or we might say it is "worth 28 bits"):
And here is the SHA-1 hash of that text string:
See? It starts with 7 digits of 0, which in this hexadecimal representation means 7*4 or 28 bits.
The chance of any bit being a zero is 1/2, so the chance of finding the first N bits being zero is one in two to the Nth power. This means that you must try, on the average, about one million test strings before finding one with a 20 bit collision; or about a billion test strings before finding a 30 bit collision. These calculations can take from seconds to hours on modern computers. In general, finding a one bit longer collision will take twice as long.
This means that if you think of a piece of hashcash as having a "value" which is the size of the bit collision, then a piece of hashcash with a value one higher is in effect twice as rare and twice as "valuable". A piece of hashcash with a value of 30 is actualy 1024 times more valuable (in terms of difficulty of creation) as one of value 20, because it is 10 bits higher value and 2 to the 10th power is 1024.
What makes hashcash useful is not just that it is relatively time-consuming to produce, but that it is quick to verify. Once a hashcash token is created, it can be verified by running the string through the SHA-1 algorithm and counting the leading zeros. This is almost instantaneous, despite the fact that it may have taken a long time to produce the hashcash.
Hashcash therefore provides a means by which someone can prove very easily and quickly that they spent (on average) some specified amount of computer cycles to create the token. In particular, it can be used to show that the sender spent a lot of time to create the token. Hashcash therefore serves as evidence of effort, and in many contexts can be used to demonstrate a level of importance or significance to a message or some other kind of data.
Reuse
One of the problems with hashcash tokens is that they cannot be reused. The risk is that someone could perform an extensive calculation and produce a high-value hashcash token, one with a large collision of, say, 36 bits. On my present-day laptop computer this would take about one day. But if, having created the token, they could use it as many times as they wanted, this would provide misleading evidence to the recipient of the attention that they were receiving. That one-day effort could be spread over thousands or millions of recipients, making the per-message effort negligible. Under these circumstances, users would have no way of knowing the true value of hashcash tokens, and they would not be useful.
To avoid this, hashcash tokens have embedded within them a "resource string". This is supposed to identify the particular use for which the token is intended, and should be sufficient to allow the recipient to make sure the token could not be used for any other purpose. For the case of email, the resource might be the email address of the recipient. When a hashcash token is received for such a purpose, the receiver (i.e. his software) must check the hashcash resource string and make sure it matches the expected value.
In addition, recipients of hashcash need to keep a local record of all of the hashcash tokens they have received recently, so that they can detect the case where someone tries to send them the same piece of hashcash more than once. In order to keep this local hashcash database from growing indefinitely, hashcash also embeds the time and date of its creation within the text string that gets hashed. This allows hashcash recipients to expire old values from their database and only keep the hashcash tokens they have seen within recent days.
RPOW Tokens
Reusable proof of work (RPOW) tokens extend on hashcash to provide a limited form of reuse. As explained above, allowing hashcash to be freely reused would make the tokens effectively worthless, as there would be no limits to how many times a given token could be shown. RPOW tokens provide a limited form of reuse called sequential reuse. In essence, once a POW token is created in the form of a piece of hashcash, it can be exchanged at an RPOW server for an RPOW token of equal value. The RPOW token can then be exchanged, sent, or otherwise used similarly to a hashcash token. However, rather than being effectively discarded after use, the RPOW token can be exchanged by the recipient at the RPOW server for a new, equal-value, RPOW token. This token can be used exactly like the first one. It can be sent to a recipient, who can verify and exchange it at an RPOW server, just as they might do for a POW token. And that new recipient can, after exchanging the RPOW token at the server and receiving a new one in exchange, retain the new RPOW token and use it again in the future.
In this way, a single POW token is the foundation for a chain of RPOW tokens. The effect is the same as if the POW token could be handed from person to person and retain its value at each step.
Security researcher Nick Szabo has coined the term bit gold to refer to a similar concept of tokens which inherently represent a certain level of effort. Nick's concept is more complex than the simple RPOW system, but his insight applies: in some ways, an RPOW token can be thought of as having the properties of a rare substance like gold. It takes effort and expense to mine and mint gold coins, making them inherently scarce. Gold coins can then be passed from person to person, and each recipient can verify the authenticity of the coinage.
In a similar way, RPOW tokens take a certain level of effort and expense to be created. They all start with a hashcash collision which, at the higher levels, will take hours or even days of computing time to create. RPOW tokens can be validated and verified upon receipt by exchanging them at the RPOW server for a new RPOW token. This allows them to be passed from person to person much like coins.
Most importantly, the RPOW system is architected with one overriding goal: to make it impossible for anyone, even the owner of the RPOW server, even the developer of the RPOW software, to be able to violate the system's rules and forge RPOW tokens. Without such a guarantee against forgeability, RPOW tokens would not credibly represent the work that was done to create them. Forgeable tokens would be more like paper money than bit gold. My goal in this project was to bring to life a simple realization which demonstrates the power of the bit gold concept. This requires resistance to forgeability, and this goal has dominated every part of the design.
See the security page for more detail on how the system is designed to resist forgery, and the World of RPOW page for information on the potential for a worldwide network of RPOW servers.
RPOW Format
An RPOW token is composed of several parts:
The most important are the id and the bignum. The id contains 20 random bytes, along with some extra data to be described later. The bignumis an RSA signature on a value created by extending the id with repeated hashing to add redundancy:
Byte numbers (MSB first)This value is interpreted as a 1024 bit bignum value, and exponentiated with the secret exponent of an RSA signing key. The result is thebignum field of the RPOW. The RPOW can be mathematically verified by raising the bignum value to the appropriate public exponent, and comparing the result to the extended id value, created using the pattern shown above.
RPOWs can be of different values, just as POWs can. The value of an RPOW is stored in its value field and is equivalent to the number of bits in a POW collision. Each RPOW value corresponds to a public exponent, according to the following rule. The lowest RPOW value, which corresponds to a 20 bit POW collision, is mapped to an RSA public exponent of 65537. Successively increasing values are then mapped to consecutive primes above 65537, leading to the following table:
The RSA key which signed the RPOW is indicated by the keyid field. The keyid is a SHA-1 hash of the RSA modulus and exponent, each preceded by a four-byte byte count field. Initially there is only one RPOW signing key and only one keyid, but over time there may be more RPOW signing keys created, as described on the World of RPOW page. To verify an RPOW it is necessary to know which RSA key signed it. The keyid implicitly identifies the RSA modulus, and the value identifies the RSA exponent; together they define the RSA verification key.
No Inflation Principle
Unlike with POWs, it takes no longer to create high valued RPOWs than low valued ones. Nevertheless, RPOWs are considered to have the same value as equivalent POWs. The reason is that the only way that an RPOW server will sign a bignum with an exponent of a certain value, is if it receives in exchange an equal-value POW or RPOW token. The RPOW server thus enforces conservation of value, also called the no-inflation principle. RPOWs will only be created when POWs or RPOWs of equal value are exchanged for them.
To enforce the no-inflation rule, the RPOW server must make sure that no POW or RPOW can be used more than once as part of an exchange. Each one is created, and then exchanged at the server for a new RPOW, and after that, the old one can never be used again. The RPOW server enforces this rule primarily by keeping a record of all of the RPOWs and POWs that it has seen in the past. Whenever one is offered for exchange, the RPOW server compares it against this database of previously-seen RPOWs. If it is on the list, this is an attempt to reuse the POW or RPOW, and the exchange request is rejected. If the POW or RPOW is not on the list, it is added to the list, and then the RPOW server will sign the bignum value supplied as part of the exchange, creating a new RPOW.
Initially, a POW is created of a certain value, represented by the size of the hash collision (number of leading zeros in the hash value). This can then be exchanged for an RPOW whose signing exponent represents the same value. This RPOW can be transferred and further exchanged for equal value RPOWs. Each RPOW can only be used at one step, but as it is destroyed it allows a new RPOW of equal value to be created in the exchange operation. The result is as though the original POW could be handed from person to person while retaining its value.
Time to Split?
In addition to allowing straight one-for-one exchanges of equal value, the RPOW server allows exchanges where tokens are split or combined in various ways. The rule is that the combined value of the new RPOWs must equal the combined value of the incoming POWs and RPOWs which are being exchanged.
When calculating these values it is important to take into consideration the property of POWs described above, that one with a value of one greater is actually worth twice as much (in terms of expense to create). This means that you can, for example, exchange a single token worth 21 for two with values of 20. Or you could go the other way and exchange two tokens worth 24 for a single one worth 25. The general formula is to add two to the power of the value field for each incoming POW and RPOW, and do the same thing with the requested outgoing RPOWs. Only if the results are equal will the RPOW server allow the exchange.
More examples of some legal exchanges would be two 24's, a 25, and two 29's for a 26 and a 30; or a 32 exchanged for a 31, a 30, a 29 and four 27's. Using these rules, an RPOW server will allow you to split or combine your existing RPOW tokens in a variety of ways.
This creates a great deal of flexibility in how RPOWs are used, as you don't have to calculate in advance the exact sizes or values you will need. You could keep a few relatively large RPOWs around and then split them into smaller values to give to someone else. Or if you receive a large number of RPOWs, you can combine them and store just a few higher valued ones.
It also means that you can generate large RPOWs in a more systematic way than simply trying to find a really large POW hashcash collision. You can create smaller collisions, exchange them for RPOWs, and combine them. Suppose you wanted to create, say, a 36 bit RPOW and on your machine that would take a day of compute time. Instead, you could create 30 bit RPOWs, each one taking only about half an hour on average, and then combine 64 (2 to the 6th power) of those to create your 36 bit RPOW. It's the same amount of compute time on average, but by splitting it up into smaller pieces you decrease the randomness and make the time to create a certain size RPOW more predictable.
More info
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 Trusted Computing-like features to prove that they are running the program generated by that code. This will provide an unprecedented level of transparency and visibility into the workings of network servers. Perhaps most importantly, the use of transparency can actually increase end-user privacy. For the first time, users will be able to verify how network servers will handle sensitive information they provide. In the case of the RPOW server, users can see that the program makes no record of transactions and creates no linkage between the RPOW issued in one exchange with the same RPOW when it is later deposited, thereby protecting privacy. In addition, the basic security goal of the system, that it will never issue RPOWs without receiving a POW or RPOW of equal value, can be independently verified. Not even the owner of the RPOW server can break these rules.
For more information on the techniques used to provide these new and previously unavailable assurances, see the security page.