1992, Rhythm is a Dancer and a new network
1992: Villetaneuse, France. I am 14. I start a very unusual day for a young teenager. My first day as an intern. I belong to the first generation or young French teenagers sent to the “working world” by the Ministry of Education so that we better anticipate what a job actually is, what will be my adult days as an entrepreneur, an employee or a civil servant. I am lucky enough to have my first experience in a research laboratory, the Laboratoire d’Ingénierie des Matériaux et des Hautes Pressions at University of Paris XIII in the city of Villetaneuse.
Back then, I precisely lived in Villetaneuse. It was a lower-class, crime-ridden city with as much unemployment as hopelessness. Low education was the rule, only challenged by the most pugnacious parents willing to offer their children a future out of that discouraging area. The only way out for teenagers: launch a Sonic adventure in our Genesis game console or listen to Rhythm is a Dancer by Snap.
The research laboratory was an island of hope in that sea of despair: polite high-class engineers, working for the scientific fame of France… and connected to the world.
One of the few things I learned in that 1-week internship was that there was an invisible telecom network, described to me as “a kind of phone network but different” that those researchers used in order to send electronic mails and research material to other scientists in the rest of the world:
- See that on my machine?
- Er… yeah… you typed a paragraph for your research report?
- Actually, it is a message. It’s a message I sent to a researcher in England… through that new network. We accelerate research by helping each other.
That was my first touchpoint with the Internet. That was an email.
Back then, French households did not have the Internet. They would get equipped a few years later. In the world, there was just a few emails exchanged each day by a few researchers or military intelligence.
Fast-forward to the beginning of the 21st century: the Internet has become accessible to everyone anywhere in the world and the use of emails is soaring. All the more as marketers around the world discover a free tool to reach millions of consumers in a click. Millions of emails, billions of emails, zillions of emails. Spam begins in our mailboxes… and traditional filtering through keywords is not completely efficient.
Introducing Hashcash, a proof-of-work system
A young cryptographer wants to change that. And free the world from spam emails while letting legit emails flow through: this programmer is Adam Back. He creates Hashcash, a system that requires each sender to spend a minimal amount of computation to be able to send an email in a system equipped with Hashcash. When this is achieved, legit emails are not hurt by the system because we consider it is ok to have our CPU spend a few seconds solving a puzzle to be entitled to send an email while spammers have to use a lot of CPU and electricity to send their millions of emails. With Hashcash, sending email costs a certain amount of electricity and CPU time. What’s more, Hashcash proves that your computer has spent time and computing power solving the puzzle: Hashcash provides a proof that your computer has “worked” on the puzzle, i.e. a proof-of-work.
How does that work more precisely ? Hashcash is a system through which a client willing to use Internet resources (e.g. send a message to a server) has to perform a computation task, that is either self-assigned or provided by the server, to mint a token. In order to mint the token, the client needs to brute force a cryptographic hash function i.e. to test multiple input of a cryptographic hash function until one output has a feature specified by the Hashcash puzzle (usually a certain number of zeros at the beginning of the output).
Wikipedia offers us the following example. In order to send an email with those features:
1:52:380119:[email protected]
The client needs to add a token, such as this one:
9B760005E92F0DAE
But how did the CPU find, or mint the token? By trying multiple inputs and checking their outputs (through cryptographic hash function SHA-1) until one output starts with the required number of zeros:
- CPU tries input 1:52:380119:[email protected]:::9B760005E92F0DAA
🡺 Output 38a082bcb2f9ca6bd908527f588700a4cba3b73b
🡺 Not the required number of zeros 🡺 new iteration - CPU tries input 1:52:380119:[email protected]:::9B760005E92F0DAB
🡺 Output efdef77f9999984cf6be916261b60cb75867f98c
🡺 Not the required number of zeros 🡺 new iteration - CPU tries input 1:52:380119:[email protected]:::9B760005E92F0DAC
🡺 Output 44966a0d4bab54197053ee3b45b8c310fb6d9cb9
🡺 Not the required number of zeros 🡺 new iteration - CPU tries input 1:52:380119:[email protected]:::9B760005E92F0DAD
🡺 Output 0358c7aadf223289a92a7818b3bf33e9941ec619
🡺 Not the required number of zeros 🡺 new iteration - …
- CPU tries input 1:52:380119:[email protected]:::9B760005E92F0DAE
🡺 Output 0000000000000756af69e2ffbdb930261873cd71
🡺 bingo ! The token has the required output format (with multiple zeros at the beginning) 🡺 the email client will send the mail with this token attached.
You can test SHA-1 with any message using open tools on the web.
A few comments about Hashcash:
- A cryptographic hash function f cannot be inverted: it is not possible to start from f(x) to infer x. Hashcash started with function SHA-1: the only way to find a relevant SHA-1(x) was to iteratively test multiple xi, and check whether SHA-1(xi) had the required number of zeros at start. One would start with x1 then iterate with x2, x3… Like testing and checking lottery combinations iteratively until you find the relevant one. It is not a game of intelligence, rather a series of trials until the right result is found. This is why we sometimes refer to it as “brute forcing”, since it is as trying to open a locked door through multiple foot hits when you don’t have the door key. This is why it uses CPU and time: the same task is performed iteratively by the CPU
- A cryptographic hash function should be easy to check, even if the token is hard to find. You need to think of the puzzle as a Sudoku grid : even if it is very hard to solve, it is very easy to check that the solution is compliant. This asymmetry keeps the CPU computation on the client side while using very limited resource on the server side
- The difficulty of the puzzle for the client can be adjusted based on the server load. This is called dynamic throttling. In periods of low server load, a short number of zeros would be required while as load is growing, the server would ask the client an increasing number of zeros, therefore reducing interaction frequency with clients.
With Hashcash, Adam Back invented a way to reduce spam by making it computationally expensive to create spam.
In 2009, secret cryptographer Satoshi Nakamoto invented a P2P electronic cash system: Bitcoin. Nakamoto needed a way to secure the Bitcoin system and a way to randomly select a member of the system to confirm each block of transactions. He implemented a proof-of-work system using Hashcash and cryptographic hash function SHA-256.
- Security: The Bitcoin proof-of-work is set to take an approximate time of 10 min to confirm each block. That means that Bitcoin automatically adjusts the difficulty of the proof-of-work puzzle for miners, based on their collective computing power. Doing so, Bitcoin adjusts the cost of network takeover by an attacker: the attacker needs to dedicate more computing power than all other participants to be able to take control of the system. Besides, the attacker needs to dedicate even more computing power if he wants to roll back transactions. Proof-of-work is a guarantee against attackers being able to go back in Bitcoin history and change past transactions.
- Random selection: proof-of-work is also useful for Bitcoin to randomly appoint the block miner. All miners would play the SHA-256 puzzle of Bitcoin, which consists of hashing a combination of elements (the Bitcoin version number, the hash of the previous block header, the hash of the Merkle root of transactions of the current block, the hash of the previous block, a timestamp, a difficulty target and a random number called nonce).
Each miner dedicates an important amount of computing power to be the first one to find a compliant hash (starting with a number of zeros defined by the target). The first one “raises its hand” and it only takes the blink of an eye for all others to check whether the proposal is compliant (remember the Sudoku). The winner earns transaction fees and a quantity of bitcoins the protocol allows him to issue. Then everybody rushes to mine the next block. And so all miners iterate, block after block.
Since mining is a race of 1 vs many, there is little chance one individual is able to win a proof-of-work race against all others. This is why you see mining pools, i.e. pools of individuals and companies that perform parallel proof-of-work actions and share the reward when the pool is able to confirm a Bitcoin block.
Video title : the best video to understand Bitcoin
In Bitcoin, proof-of-work also means big miners are always challenged by new comers, either because the latter find cheaper energy or because they build faster machines. Therefore, established positions can change rapidly and are purely based on proof-of-work capacity, not on simply owning capital. There is no ground rent in Bitcoin. If you stop working, you stop earning. A positive life message maybe.
In 1992, there was one proof-of-work system I already knew very well: class grades. An A was a proof of hard work. Damn it! I had everything at hand to understand the mail spamming problem and build the solution, and I had 5 years to invent Hashcash before Adam Back did. And I let him win this race. For “lack of work”. What a loser I am!
