Oct. 27, 2018
Abstract
Hashcash is a mechanism for defending against spam and denial-of-service attacks in email and other decentralized systems. Implementors of systems using hashcash face the issue of how to set the proof-of-work difficulty. A general solution to this problem is given which can be used to predictably allocate resources in decentralized systems where individual nodes each contribute finite resources. Some emergent effects of this solution are explored.
Hashcash
Nodes in decentralized systems face two closely related issues around the use of their resources. The first problem is that of how to fairly allocate resourcess between connecting clients, and the second problem is that of how to protect themselves against resource depletion attacks. Some systems, like Bittorrent, largely sidestep these issues because the goals of participants (download the data quickly) are aligned. In other systems such as email, nodes are vulnerable to resource depletion attacks like spam and denial-of-service (DoS) attacks.
In 1997 Adam Back proposed an ingenious & practical scheme for countering DoS attacks and spam emails called hashcash. This scheme was famously referenced by, and used with some tweaks, in the software which launched the cryptocurrency revolution: Bitcoin.
As noted in the 2002 Hashcash paper the idea of using a proof-of-work in this way predates Hashcash in the work of Cynthia Dwork & Moni Naor, 1993 and later in the client-puzzles work of Ari Juels & John Brainard, 1999.
Adam Back's implementation is notable because it was based on a modern widely implemented cryptographic hash function, used a cleverly simple leading-zeroes hash collision mechanism which is verifiable with the naked eye, and most importantly of all it came with concise source code which anybody could compile and run ("cypherpunks write code").
The common idea behind these proof-of-work schemes is that you do not allocate resources to the processing or storage of incoming messages unless the sender has proven that they have done a certain amount of computational work. A spammer or DoS attacker is forced to multiply the work required by the number of attacking nodes they are utilising making it more expensive for them to attack. The key to the proof-of-work mechanism is that it is easier for the receiver to verify the proof than it is for the sender to construct the proof, and secondly, that the receiver can specify how much work the sender needs to perform in order to be considered. In Hashcash the construction of proofs-of-work and their more efficient verification is accomplished with a basic building block of cryptographic systems, a computational trapdoor: the hash function. The second key to proof-of-work, that of the receiver specifying the difficulty to require of clients, is not clearly addressed in this body of work. Here we'll describe a general solution to the problem of setting PoW difficulty and explore some emergent effects of the solution on decentralized systems.
The difficulty of calibrating hashcash difficulty
In Dwork & Naor (1993) they say:
There is a pricing authority who controls the selection of the pricing function and the setting of usage fees.
And later, in the section on the Fiat-Shamir signature scheme:
A reasonable choice is k = 10.
Where k here is equivalent to what we now call the difficulty in cryptocurrency proof-of-work contexts. Basically "here's a reasonable value to use on today's computers". This strategy is not tenable in many decentralized systems because a pricing authority, or "trusted third party" is an inherent security risk (Szabo, 2001).
In Adam Back's 2002 paper there is a section called "Dynamic Throttling":
With interactive hashcash it becomes possible to dynamically adjust the work factor required for the client based on server CPU load.
But it's not clear exactly how much difficulty should be assigned in proportion to the server CPU load.
Futher, on the "Bitcoin" page of hashcash.org:
Hashcash difficulty is static and eroded by Moore's law currently 20 bits.
Again we see a "reasonable value to use on today's computers".
In "How bitcoin uses hashcash":
Hashcash was expected to adjust difficulty every 6 months or year, manually based on observed moore's law estimates. It was proposed that this be measured against a benchmark machine by some vague/undefined human consensus process and broadcast via signed difficulty update headers, and/or long TTL DNS TXT records.
He further points out that Bitcoin's "automatic inflation control" innovation has solved this problem for the cryptocurrency case.
In the 2002 paper again we see the following in the section on mitigation of TCP connection-slot depletion, which concludes with:
Connections will be handed out to users collectively in rough proportion to their CPU resources, and so fairness is CPU resource based (presuming each user is trying to open as many connections as he can) so the result will be biased in favor of clients with fast processors as they can compute more interactive-hashcash challenge-response tokens per second.
The implementation detail of exactly how much difficulty to require per connection slot is again left as an exercise to the reader. Adam Back's original hashcash announcement on the Cypherpunks mailing list makes reference to a fixed difficulty of the first 20 bits of zeroes and as noted in the Wikipedia page on hashcash this becomes a sort of de-facto standard reference value.
Existing solutions
How high to set proof-of-work difficulty is of course not completely vague and unsolved. Bitcoin famously pits miners against each other using a hashcash difficulty that is adjusted every two weeks to a value computed from previously achieved hash difficulties. Referring back to the TCP connection slot depletion example in the 2002 paper, we can think of the Bitcoin miner hashcash use-case to be a slot of size 1 that is only available to be filled every 10 minutes. Hash rates are forced upwards by competition for that single slot between miners who will be rewarded under the incentive model of the Bitcoin system.
There is another mechanism in Bitcoin that we can also borrow from for decentralized systems (absent a fully functional and carefully engineered global store-of-value system called a Blockchain); the fixed block size. In Bitcoin the size of each block storing transaction data, and therefore ultimately the number of transactions, is fixed. This was a point of contention for some time amongst Bitcoin enthusiasts and stakeholders but in the end those supporting a fixed block size had their day and Bitcoin today retains a fixed block size into which transactions from the mempool must be squeezed.
Every Bitcoin transaction is accompanied by a fee paid to the miner who mines the block in which it is included. To decide which transactions should be accepted into the block they are minting miners naturally refer to these fees out of financial self-interest, to ensure they capture the highest aggregate fee possible. When a new block is minted a miner will sort the transactions from those with the highest fee paid to those with the lowest fee paid. Then they will insert into the block the top-N-by-fee transactions that will fit into the fixed block size.
So we have three models to build our solution on: the TCP connection slot example, Bitcoin's automatic inflation control, and Bitcoin's fixed block size.
Consider that in all three of these examples the fundamental resource being allocated is subject to fixed constraint, whether it is TCP slots, Bitcoin issued per 10 minutes, or the transaction-processing capacity of Bitcoin nodes. It is in fact always the case that there are resource limits placed on networked services even if that limit is sometimes so high as to give the illusion of being unlimited. Take for example the original use-case of hashcash, the email inbox: here the limited resource is your own time and attention. There is some practical upper bound on that resource such that you would be fundamentally unable to check your email if you were receiving e.g. 10,000 emails per hour. This is also true of the resources of nodes in any decentralized system.
We can use the fixed block size model in combination with hashcash to balance load and distribute resources efficiently in decentralised systems with automatic difficulty adjustment and without requiring a full cryptocurrency blockchain implementation or trusted central authority.
Fixed resource hashcash calibration
The "fixed block size" mechanism can be used more generally in decentralized systems to protect nodes from resource depletion and deterministically allocate resources by conducting a "hashcash auction" between clients over the available resources.
The hashcash auction works as follows:
- Each node specifies the number of clients they can comfortably serve as
R, given their resource limits on disk, bandwidth, CPU, etc. This can often be computed based on simple measurement of the resource(s) in question.
- Nodes issue HMAC'ed tokens ("symmetric key certificates" in the hashcash paper) to clients who request access which include a timestamp so that they can be expired.
- To use a node's resources, clients must bid for a slot by performing a PoW over these tokens.
- Nodes publish the upper, lower, and median PoW currently acheived by clients occupying the available resource slots
R.
- Connecting clients are added to the client pool, which is sorted by PoW difficulty-achieved, and only the top
R by difficulty are serviced.
- (Optionally, the lower-bound minimum PoW can be capped, to emulate the same basic DoS protection that hashcash provides.)
- (Optionally, dependent on use-case, clients are disconnected after some time and required to re-bid for a slot).
In short, you decide how many clients you can service at a time (R), then sort connecting clients by their PoW height, and then deny access to, or disconnect clients who fall outside the top R.
Note that the server is not required to store any information relating to the the tokens it gives out to prospective clients because it can use the HMAC to verify the tokens it has issued and the time at which they were issued. In this way the issuance of tokens and their expiry becomes very cheap for a service node.
The natural consequence of a system like this is that clients must compete for available slots to use the node's resources, and a node does not need to specify exactly how much PoW each client must perform. Instead clients arrive at this value through an emergent bottom-up bidding process. The node no longer has to guess at "20 bits" and can instead honestly say "look, here is how hard other clients are working, if you want to access my resources you'll have to do better".
The clients themselves determine the proof-of-work difficulty setting in an ongoing auction where they must make a higher bid than other clients in order to be allowed access to consume the fixed set of resources, or go elsewhere.
To cope with large numbers of clients and provide a higher level of granularity in the PoW ranking, a simple less-than operator can be used so that clients can bid for intermediate values. For example 0x01fe < 0x01ff so a client bidding with a hash of 0x01fe would beat a client bidding with a hash of 0x01ff.
Properties of this system
What this restricted-resources scheme gives us is a way to measure the sacrifice (Nick Szabo, 2002,2005) that a client is willing to make for the privilege of using a node's resources. As with the human measure of time sacrificed in Szabo's article, it is not an ideal way to measure the importance of incoming client connections, but it is better than existing systems which are essentially a lottery, or in some cases "let the bad guy win". It is not perfect but rather a "proxy measure" which gives a service a deterministic ranking system of roughly those clients who most badly want or need access.
At first this system seems unfair - those clients with the most CPU are able to dominate access to resources - but notice that it is much fairer in the worst case where a motivated legitimate client can still get access under DoS or spam attack by working hard to out-compete just a single instance of the attacker. Given enough motivated legitimate users there now also exists a way for them to collectively out-compete a spam or DoS attack. In other words, utilising this scheme has a better failure mode than the free-for-all which normally prevails in networked systems.
Another way of looking at this system is that we have inverted the security aims from "keep out the bad guys" to "keep in the good guys". By giving motivated users a way to express the strength of their need we are able to keep those clients connected who signal the most need to access to the resources. We are able to preference those users who will actually utilise the resource with a higher probability than those users who will waste it, because wasting it is now costly.
A further benefit is that the service utilising this scheme is protected from hard failure. In the worst case failure mode an attacker is only able to deplete resources up to the comfortable hard-limit R specified by the server, meaning the server is never placed under such high load that it entirely crashes and burns, so long as R is specified within serviceable bounds.
In the real world there is always a constraint upon resources, and it is often the case that those wanting to consume a resource must hustle harder to get access. This scheme has an honesty that mirrors the reality of constrained resources rather than pretending that resources are infinite, which is what many historically optimistic decentralized systems do to their detriment. A computer cannot consume more disk space than 100% of disk, and it cannot utilise more CPU time than 100% of CPU time. Modern network services are often deployed without acknowledging these real constraints and with vague hand-waving about "scaling" by adding more machines to accommodate load. That's fine for Silicon Valley backed ventures with money to burn but decentralized systems are often run by volunteers contributing their precious personal resources. Silicon Valley assumptions on volunteer run networks are likely to lead to ruin.
Finally, this scheme has additional emergent benefits in the case where clients have a choice of decentralized service providers. This case is common in decentralized systems where some subset of participants run their own "full nodes" which other clients may then utilize.
Bottom-up load balancing
The further interesting consequence of the hashcash auction scheme arises when we have many service nodes providing the same decentralized service. In the auction-determined proof-of-work difficulty setting, clients now have a clear signal about which nodes are under most heavy use and can freely choose those nodes where the PoW, and hence the resource usage, is lower. Given a choice between node X which requires a very high PoW and node Y which requires a lower PoW, a client will naturally try to connect to node Y first.
The result of clients seeking lower-difficulty service nodes is that they spread themselves more evenly across the available servers. This less clustered network graph can lead to a healthier more decentralized system without requiring any kind of central coordination to acheive it. This emergent effect is a sort of bottom-up load balancing system.
Expiry and time preference
Decentralized systems differ in the way in which resources are allocated over time. Sometimes the resource provided by nodes is small and fast, such as UDP packets in Bittorrent's DHT. Other times the resource may be longer lived and more expensive on a per-unit basis, for example disk space storage or a regularly run cron job.
In the situation where resources are long lived and expensive to maintain it makes sense to require clients to periodically re-bid for their access to the resources in question. For example, rather than storing a connecting client's data on disk indefinitely the service node could require that a client re-bids for the disk space once a month or once a year.
A variant on this would be to use a time-based weighting factor on the PoW submitted by connecting clients such that the PoW of more recent connections are weighted higher during bid sorting than older connections. For example if you wanted to preference more recent connections instead of sorting on PoW you could sort on some variant of PoW / (t + 1) where t is the time since connection.
In the parlance of economics this introduces a time preference into the system.
Example
Let's close with an example.
Imagine a decentralized social network where users are able to make posts and collect and publish replies to those posts. This can be accomplished in a decentralized way by representing users as key pairs and having every post and every reply signed by its owner's key pair to demonstrate authenticity rather than relying on a centralized trusted third party for authentication. While a user is online they can host their own set of cryptographically signed posts for others to download via a peer-to-peer network, and collect replies to those posts in the same way. However, what happens when the user goes offline, turns off their devices, goes to sleep etc.?
One solution is to have "followers" of the user automatically mirror their posts for other users to download while they are offline. This solution is better than nothing but falls short when a user has few followers or only has followers in the same timezone such that they will all be offline around the same time. Segments of the social network would go dark for periods of time leading to a lack of reliability of access and a form of accidental time-based self-censorship. Some audiences may be satisfied with such a constraint as a tradeoff for a higher degree of privacy and overall censorship resistance, but a mainstream audience is unlikely to accept this lack of reliability.
A more robust solution would be to back this up with a set of volunteer run "full nodes" which users could enlist to mirror data and collect replies in their absence. This architecture immediately begs a number of questions around allocation of the "full node" contributed resources of disk space and bandwidth. How do nodes protect themselves against greedy clients taking all bandwidth and disk space? How do clients protect against spammy replies? How do nodes protect against censorship via resource exhaustion and DoS?
Using the "hashcash auction" we can get a reasonable solution to these problems, bringing higher availability to the system. Those nodes which provide the service of replicating user posts would measure how many clients they are willing and able to serve based on system resources. They can each do this by measuring their disk space for example and allocating a fixed amount of disk per user to a fixed number of users R keeping this constraint within the disk space each has available. Each full node then requires connecting users to bid for a storage slot for the hosting of their posts while offline. Only those clients who are able to demonstrate their need the most strongly will be able to use the offline-replication service of a node. When new nodes are deployed clients will naturally tend towards them as they choose the lower PoW requirement relative to nodes which are serving many existing connections and therefore have higher PoW requirements.
Those users who might run a full node, and others interested in the health of the network, also have a clear signal as to the current load on the whole system and the relative need for more nodes by looking at the PoW they require in aggregate. People who might run a voluneer node are also provided an assurance that there is a fixed cost on the resource they will be donating, making it more likely that people will be willing to run full nodes to support the system. Finally, there is an incentive to running a full node as the user could white-list the cryptographic keys of their own devices and those of their friends and family, meaning that those accounts are always given preference over the accounts of strangers, bringing benefit to both sets of users.
Addenda
-
In the spirit of "cypherpunks code" I recently published scrypt-hashcash which provides a basis upon which to validate some of these ideas on the web. For example browser based clients could bid for resources by performing a hashcash PoW using this library and submit it via HTTP, WebSocket, or WebRTC connection to the service conducting the resource auction.
-
It is interesting that Hal Finney touched on a related idea in RPOW enabled BitTorrent and in true cypherpunk tradition offered code implementing his ideas:
Imagine a version of BitTorrent where nodes that have completed their downloading (called "seeders") could earn RPOWs by continuing to upload. And what could they do with those RPOWs? Imagine further that this version of BitTorrent allowed nodes to send RPOWs in order to get higher priority from other nodes which are downloading. Just such an experimental, RPOW-enhanced version of BitTorrent is now available for download.
Read more posts on the subject of cryptography & decentralized systems.
