Pre-Bitcoin Cryptography

In the first three chapters we have analysed the concept of money, its origins, its properties, its evolution throughout history, and the problems inherent to the human condition that led to the centralisation of money issuance in the hands of states --- with certain limits on theft while it was backed by gold, and with no limits whatsoever once it became fiat money. And after all these centralising processes, we arrive at the worst money humanity has ever used.

I don’t believe we shall ever have a good money again before we take > the thing out of the hands of government, that is, we can’t take it > violently out of the hands of government, all we can do is by some sly > roundabout way introduce something that they can’t stop¹

— Friedrich A. Hayek

Hayek, one of the great economists of the Austrian school, made this statement in 1984, twenty-five years before the appearance of Bitcoin. He was fully aware that governments would never voluntarily relinquish the immense power that the fiat system grants them, and that this power could not be taken from them by force. But how does one convince other people that something new is money if nobody is yet using it as money? It seems an impossible mission, since money is essentially “what people use as money” --- a kind of circular definition from which there is no escape. Yet even though it might have seemed an impossible task, developments had been taking place since the 1970s that laid the groundwork for making it possible.

I’ve been working on a new electronic cash system that’s fully > peer-to-peer, with no trusted third party.

— Satoshi Nakamoto

On 31 October 2008, Satoshi Nakamoto sent an email[@SatoshiFirstemail] to the cryptography mailing list.² The email began by stating that he had been working on a new electronic cash system that was completely decentralised, with no trusted third party.

His very first sentence gave the key to the invention. Electronic money systems native to the internet had been created before, but all had failed. To Satoshi it was clear that they had failed because they were centralised and therefore had a single point of failure. This meant that if the status quo of the fiat system was threatened by something, they could simply cut off the head of the threat. But in his email Satoshi said fully peer-to-peer, with no trusted third party --- that is, with no head to cut off. And that is Satoshi’s great invention, which made possible the “something that they can’t stop” from Hayek’s statement.

For some time, certain people had been searching for decentralised electronic money. The Cypherpunk movement of the 1990s dreamed of it. Although all the cryptographic algorithms used in Bitcoin had already existed for years, Satoshi’s achievement was to put all the pieces together and bring to life what had until then seemed a pipe dream.

Classical Cryptography

The RAE defines cryptography as “the art of writing with a secret key or in an enigmatic manner”. And although this definition became obsolete more than seventy years ago, it is true that classical cryptography was more an art than a science. Since antiquity, humans have sought to communicate confidentially. For example, when a general sent a written message to another general, he wanted to prevent the enemy from being able to read it should it be intercepted. To this end, before sending it, the original message --- also called the plaintext --- had to be transformed into a ciphertext in such a way that if the enemy intercepted the encrypted message, they would understand nothing. The recipient, by applying the inverse of the encryption algorithm --- that is, by decrypting the ciphertext --- would recover the original message. The Caesar Cipher, so named because Julius Caesar used it to communicate with his generals, is one of the earliest encryption algorithms. It consists of replacing each letter of the message with the letter a certain number of positions further along in the alphabet, with this number of positions serving as the key. Today nobody uses it except for educational purposes, since knowing the algorithm makes it trivial to decrypt any message encoded this way, as it is sufficient to try all 26 possible keys (for a 26-letter alphabet).

The history of classical cryptography is the struggle between the designers of encryption algorithms and the cryptanalysts who tried to break them. One of the most famous episodes of cryptanalysis is that of the British team of mathematicians and cryptologists during the Second World War, who worked to break Enigma --- the encryption system used by the Nazis to keep their communications secret. Breaking Enigma (and keeping it secret) likely brought the end of the Second World War significantly closer.

In 1949, Claude Shannon³ published Communication Theory of Secrecy Systems[@CommunicationTheorySecrecySystems], a seminal work that marked a turning point in the history of cryptography by signalling the end of classical cryptography and the beginning of modern cryptography. Cryptography moved from being an art to being a science --- a branch of mathematics. But until 1976, both classical and modern cryptography dealt with symmetric-key or secret-key algorithms, in which the algorithm used to decrypt a message required the same secret key that had been used to encrypt it. Contrary to what some people think, there are no encrypted messages in Bitcoin. It makes extensive use of cryptography, but not of secret-key cryptography. The most significant cryptographic advances leading to the emergence of Bitcoin occurred from 1976 onwards, with the discovery of a new branch of cryptography: public-key cryptography.

Diffie-Hellman

In 1976, Whitfield Diffie and Martin Hellman, two American mathematicians and cryptographers, published the article New Directions in Cryptography[@DiffieHellman], in which they described a solution to the key exchange problem. Until then, all encryption systems⁴ were symmetric-key or secret-key algorithms --- that is, systems in which the key Alice uses to encrypt is the same key Bob needs to decrypt the ciphertext.

A fundamental problem with all secret-key algorithms is how to distribute the key before use. If Alice and Bob can meet in person, there is no great problem --- but if they cannot, how can they agree on a secret key over a communications channel that is not yet encrypted and is therefore public? If an attacker sees the key while Alice and Bob are agreeing on it, they can already decrypt all subsequent communications. This was one of the greatest cryptographic problems of the era, and many considered it unsolvable.

Thanks to the algorithm devised by Whitfield Diffie and Martin Hellman, Alice and Bob are able to agree on a shared secret key without having exchanged it over the channel. Over the public channel, Alice and Bob exchange certain information that both of them need in order to construct the shared secret key. But from the information they exchange over the public channel, nobody else is able to calculate the secret key. The Diffie-Hellman paper is the first to speak of key pairs --- a private key and a public key --- and represented a fundamental cryptographic advance, a milestone that gave rise to an entirely new branch of mathematics: public-key cryptography.

RSA

Although the Diffie-Hellman breakthrough solved the key exchange problem, something still remained to be resolved. If Alice wanted to send a message to Bob, she first had to carry out the key exchange process to find the shared secret key, which was an interactive process. If Alice wanted to send an email to Bob and Bob was not available at that moment, she had to wait.

In February 1978, Ronald Rivest, Adi Shamir, and Leonard Adleman, three researchers at MIT⁵, published the article A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[@RSA] in the journal Communications of the ACM. In the article they described a public-key cryptography system that uses the difficulty of factoring large integers to guarantee the security of communications, encrypting and decrypting messages without the need to exchange a key beforehand. The article also developed a method for digitally signing documents using private keys, allowing users to verify both the integrity and the origin of a message.

Each user independently generates a key --- their private key --- and from it calculates another key, the public key that corresponds to that private key. These keys have an essential characteristic for the functioning of the system: the public key can be easily calculated from the private key, but the reverse process is not possible.⁶ In this way, if Alice wants to send an email to Bob that nobody else can read, she simply looks up Bob’s public key from the public key directory and encrypts the message with it. Since decrypting the message requires Bob’s private key --- and this key is, as its name indicates, private --- only Bob can decrypt the message.

Furthermore, RSA is not only useful for encrypting and decrypting but also for digital signing. Digital signatures work in a similar way to encryption and decryption but using the keys in reverse. When Alice signs, she does so using her own private key. When Bob verifies, he does so using Alice’s public key. Anyone can verify the signature (if there is no encryption). What can be deduced from verification is that only Alice could have produced the signature --- which is precisely the purpose of a signature.

In Bitcoin, the foundation of a transaction is digital signatures. Although Bitcoin does not use the RSA signature scheme,⁷ the concept is the same. A Bitcoin address is, in simplified terms, a public key, and the corresponding private key is what is needed to move the bitcoin stored at that public key to one or more other addresses (i.e., to spend them). The transaction is “signed” with the private key, so that only the holder of the corresponding private key can authorise the transaction. All nodes on the network verify that the signature is correct for that public key.

Blind Signatures

In 1982, the CRYPTO 82 conference took place in Santa Barbara. At it, David Chaum⁸ presented his paper “Blind Signatures for Untraceable Payments”[@BlindSignatures]. In this work, Chaum proposed a new blind signature scheme in which the signer produces a digital signature for a message without having any knowledge of the message’s content. Using this new cryptographic tool, he proposed a system in which users could obtain digital money from a bank and spend it in a way that was impossible to trace by the bank or by a third party, since both the identities of the parties and the amount transferred were concealed. This was the first proposal for electronic cash.

In 1989 he founded the company DigiCash and created the first anonymous electronic money, called eCash --- a version of his own cryptographic digital payments system making use of blind signatures. However, the DigiCash system involved a centralised authority (the issuing bank) that had control over the issuance and distribution of eCash. Although DigiCash failed to establish itself as a viable digital currency solution and ultimately closed in 1998, Chaum’s work is widely recognised as one of the most important contributions in the history of modern cryptography, and it laid the foundations for the development of anonymous and secure online payment systems.

The Birth of Free Software

On 27 September 1983, Richard Stallman⁹ made the announcement that would mark the birth of free software[@GNUAnnouncement]. The email began by saying:

Starting this Thanksgiving I am going to write a complete > Unix-compatible software system called GNU (for Gnu’s Not Unix), and > give it away free to everyone who can use it.

— Richard Stallman

In the same email he also mentioned the reasons why he had to write GNU:

I consider that the Golden Rule requires that if I like a program I > must share it with other people who like it. Software sellers want to > divide the users and conquer them, making each user agree not to share > with others. I refuse to break solidarity with other users in this > way. I cannot in good conscience sign a nondisclosure agreement or a > software license agreement. So that I can continue to use computers > without dishonoring my principles, I have decided to put together a > sufficient body of free software so that I will be able to get along > without any software that is not free.

The free software movement is based on four fundamental principles: the freedom to run the program for any purpose, the freedom to study and modify its source code, the freedom to distribute exact copies, and the freedom to distribute modified versions. These four essential freedoms fostered a culture of collaboration and gave rise to highly influential projects such as the Linux operating system, begun by Linus Torvalds¹⁰ as a personal project in 1991. Since its origins, the movement has never stopped growing, and today the vast majority of services on the internet are provided by machines running free software.

Rather than creating a company and trying to exploit his invention to make money as others had done, Satoshi decided to make Bitcoin free software. He also chose one of the most permissive licences that exists: the MIT licence.¹¹ Under this licence, Satoshi allowed users to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the software.

Had Satoshi created Bitcoin as proprietary software rather than free software, its adoption would have been far more limited. Even with the same idea and the same initial software, without access to the source code, the developer community would not have been able to audit or improve the system, which would have generated distrust among potential users and impeded its growth. Bitcoin’s success is closely linked to the principles of free software, which have made its global adoption and its continuous improvement by a decentralised community possible.

The Crypto Anarchist Manifesto

In 1988, Tim May¹² wrote the Crypto Anarchist Manifesto, which, according to Tim himself, was distributed to some techno-anarchists at the Crypto 88 and Hackers Conference conferences of that same year.

Later, in 1992, he would read it at the founding meeting of the Cypherpunk movement in Silicon Valley and distribute it on the mailing list created for the movement. Here you can read it.

The Crypto Anarchist Manifesto

PGP: Pretty Good Privacy

Phil Zimmermann, an American software engineer, was concerned about the capacity that new technologies gave governments to surveil citizens in the style of Orwell’s Big Brother. In theory, RSA had solved part of the problem, but the encryption and decryption algorithms were computationally very costly, making it suitable only for the military, government, and large corporations that had powerful computers. Zimmermann wanted an algorithm suitable for everyone, and in 1991 he created PGP, the first email program accessible to the general public with which one could encrypt outgoing emails and decrypt received encrypted emails. The idea behind PGP was to use RSA only to encrypt a secret key, and then encrypt the body of the message with a symmetric encryption algorithm using this secret key --- a process that is far less computationally costly. Analogously, the recipient would first decrypt the secret key using RSA, and then decrypt the message with the secret key.

Although PGP used RSA, Zimmermann defended his decision not to pay a licence fee, arguing that PGP did not infringe the patent since it implemented the algorithm --- widely known in the computer security community --- independently, and did not use any specific code or implementation protected by the patent. RSA Data Security, the company that owned the patent and managed its licences, did not sue him, primarily because Zimmermann distributed PGP free of charge and also because, by focusing on protecting individual privacy and defending civil rights, he had generated public sympathy and support for his cause.

But although RSA Data Security did not sue Zimmermann for his use of RSA, at that time the encryption export laws in the United States prohibited the export of strong encryption technology,¹³ and the publication of PGP triggered a federal investigation for violating export laws. For five long years, Zimmermann faced the possibility of criminal charges.

In 1995, Zimmermann published a book entitled PGP: Source Code and Internals[@PGPSourceCode] containing the complete source code of the program. Since it was in the form of a physical, printed book, Zimmermann argued that he was exercising his right to freedom of expression, protected by the First Amendment of the United States Constitution. In this way, the text of the source code could be legally exported to other countries, and once outside the United States, the book could be scanned or retyped to recreate the software. In the end, he was never criminally charged, and in 1996 the United States Government allowed the international distribution of PGP without significant restrictions. The publicity generated by the case led to greater public awareness of the need for privacy on the internet and the importance of encryption.

It’s personal. It’s private. And it’s no one’s business but yours. > You may be planning a political campaign, discussing your taxes, or > having an illicit affair. Or you may be doing something perfectly > legal but you still don’t want it read by others. Whatever it is, you > don’t want your private electronic mail read by anyone else. There’s > nothing wrong with asserting your privacy.¹⁴

— Phil Zimmermann

The Cypherpunks

In late 1992, Tim May, Eric Hughes¹⁵ and John Gilmore,¹⁶ concerned about privacy, individual freedom, and government intrusion into the lives of citizens, began meeting at the offices of Cygnus Solutions, the company founded by Gilmore, in San Francisco. The gathering grew and the movement soon came to be called Cypherpunk, a portmanteau blending cypher (to encrypt) and cyberpunk,¹⁷ the science fiction subgenre about dystopian futures. At the founding meeting, Tim May read the Crypto Anarchist Manifesto he had written a few years earlier, and they soon created the Cypherpunk Mailing List (cypherpunks@toad.com), where they shared their thoughts. The movement was based on the idea that strong cryptography could be used to protect individual freedoms and create a more open and free society.

Phil Zimmermann (PGP), David Chaum (eCash), Wei Dai (b-money), Adam Back (Hashcash), Hal Finney (RPOW), Nick Szabo (Bit Gold), Jacob Appelbaum (Tor), Bram Cohen (BitTorrent), Tom Jennings (FIDOnet), and Julian Assange (WikiLeaks) are among those who soon joined the movement. In 1993, Eric Hughes wrote the Cypherpunk Manifesto. From that point on it became the founding text of the movement. Here you can read it.

A Cypherpunk’s Manifesto

The phrase “Cypherpunks write code” captures an important aspect of the movement. It was not a movement dedicated to making political arguments about the importance of privacy. It was not a movement dedicated to talking, to persuading people, but to creating the tools necessary so that each person individually --- whoever wished to --- would have the opportunity to exercise their privacy and freedom.

Hashcash

In 1997, Adam Back, a member of the Cypherpunk community, proposed a system based on “proof of work” as a way to combat spam and other types of denial-of-service attacks (DoS¹⁸). The central idea of Hashcash[@HashCash] is to require the sender of an email message to perform a small but significant computational calculation before sending the message. To send an email, the sender must generate a Hashcash stamp. This stamp includes information such as the recipient’s address, the date, and a number called a nonce,¹⁹ such that the hash of the stamp begins with a certain number of zeros. For an individual user the computational cost is reasonable (a few seconds), while for sending emails to millions of people the cost becomes prohibitively high, thereby discouraging the mass sending of emails, or spam.

Mining in Bitcoin is based on exactly the same concept as Adam Back’s proof of work. In Hashcash the hash function used is SHA-$1$ and the input message to the hash function is the stamp. In Bitcoin the function used is a double SHA-$256$, and the input message is the block header. Satoshi himself mentions this in the section of the white paper where he explains the Proof of Work for implementing the distributed timestamp server.

To implement a distributed timestamp server on a peer-to-peer basis, > we will need to use a proof-of-work system similar to Adam Back’s > Hashcash.

— Satoshi Nakamoto

Bit Gold

In 1993, Tim May invited Nick Szabo²⁰ to one of the in-person meetings the Cypherpunks held in San Francisco. Nick, a computer scientist whose parents had been forced to emigrate from Hungary due to Soviet repression, was concerned about the loss of online privacy and became part of the movement. In 1998, a year after Adam Back published Hashcash, he shared on the Libtech mailing list an initial design for a new form of money he called Bit Gold[@BitGold], though he would not publish the final version on his personal blog until 2005.

The idea behind Bit Gold was to create money through proof of work. The issuance of tokens begins with a public bit string, called the candidate string. From this string, a user creates a valid token by adding sufficient proof of work, in a manner analogous to Hashcash --- that is, by concatenating an arbitrary nonce, calculating the hash of the resulting string, and repeating the process until finding a hash that begins with a certain number of zeros. A timestamp is then added to the newly created PoW token via a sufficiently distributed series of timestamp servers. Finally, the user adds the timestamped PoW token to a public, also distributed, ownership “Registry”. The created and registered token serves as the candidate string for the creation of the next token.

Once issued, to transfer a Bit Gold token the owner digitally signs a message indicating the public key of the new owner, and sends this signed message to the “Registry”, which updates both balances accordingly. The “Registry” assigns tokens to public keys, not to physical identities, so that the transfer can be carried out anonymously.

Both the creation of coins through proof of work and their transfer using digital signatures would be ideas that Satoshi would later use in Bitcoin.

But in the document itself, Szabo identified two limits to the security of his proposal. On one hand, the difficulty of achieving a sufficiently distributed trust in the timestamp and registry servers. On the other hand, the fact that proof of work depends on the architecture (processing power) of the systems, given that there is no such thing as an abstract “unit of computation”. This implies that as technology advances, money can be created at an ever-increasing rate.

In relation to the first of these problems he himself had identified in Bit Gold, in 2001 he published Trusted Third Parties are Security Holes[@TrustedThirdParties]. In this essay he argued that trusted intermediaries (such as banks, credit card companies, and others) are weak points in the security of online financial transactions. He also noted that these trusted third parties represent not only a security risk but also a threat to the privacy and freedom of users. Although the essay does not indicate what the solution is, it does point in the direction that needed to be investigated. Rather than depending on trusted third parties, Szabo advocated the use of cryptography and mathematics.

b-money

The search for anonymous electronic money was one of the main topics of discussion in the Cypherpunk movement, and in 1998 another member of the movement, Wei Dai, an American computer engineer and cryptographer of Chinese origin, published b-money[@bMoney], an electronic cash system that, like Bit Gold, used Hashcash-based proof of work for the creation of coins. Also analogously to Bit Gold, the transfer of coins used digital signatures: the sender broadcast a message signed by them, indicating the recipient and the amount transmitted. The remaining peers verified that the signature was correct and updated both accounts accordingly.

Unlike Bit Gold, each proof-of-work solution created a certain quantity of coins proportional to the difficulty of creating them, which resolved one of the two problems that Nick Szabo himself had mentioned regarding Bit Gold. Quoting the b-money paper:

The number of monetary units created is equal to the cost of the > computing effort in terms of a standard basket of commodities.

— Wei Dai

Although it was an early idea of what Satoshi would later embody in his difficulty adjustment algorithm, Dai gave no details as to how a network of peers would independently arrive at the same number.

The proposal included two versions. In Dai’s own words, “the first is impractical because it makes heavy use of a synchronous, interference-free anonymous broadcast channel”. The second, in which special nodes on the network were responsible for verifying transactions and keeping accounts, meant the protocol was not completely decentralised.

Dai also never got around to writing the code implementing his idea, so it was never actually tested. Years later, Satoshi contacted him before publishing the Bitcoin white paper in order to cite his work. B-money is, in fact, the first of the eight bibliographic references in the white paper.

Reusable Proof of Work

Harold Thomas Finney, better known as Hal Finney, was an American software developer who was also concerned about the loss of privacy on the internet. He was aware that, without taking the necessary precautions, the internet could become a weapon of mass surveillance and a threat to freedom. But he also believed that the personal computer could be used to defend against this threat and preserve freedom.

The computer can be used as a tool to liberate and protect people, rather than to control them.²¹

— Hal Finney

It was also Tim May who invited Hal Finney in 1992 to one of the first meetings of the Cypherpunk movement. Hal was one of the earliest participants in the mailing list discussions and contributed significantly to the ideas and projects that emerged. He helped Eric Hughes code the first Chaumian remailer²² and helped Phil Zimmermann in the development of PGP. In 1996 he joined PGP Corporation, the company founded by Zimmermann, where he would work until 2011. Hal was also one of the most active participants in the Cypherpunks’ discussions about electronic money, as he considered anonymous electronic money to be fundamental for preserving privacy on the internet.

In 2004, Hal announced on the Cypherpunk mailing list the project “Reusable Proof of Work”[@RPOW], which he published on his website rpow.net.²³ As its name indicates, and like b-money and Bit Gold, the RPOW system is based on proof of work to create coins. But unlike both of those, the transfer is not made with digital signatures; instead, the RPOW token is sent directly to the recipient of the payment.

To avoid the double-spending problem, a server is used that is responsible for issuing the coins (RPOW tokens). The process is as follows: first, Alice creates a token with sufficient proof of work. She then registers that PoW token with the server, which, after verifying the proof of work, marks that token as spent and issues a new RPOW$_a$ token. This RPOW$_a$ token is the “coin”. When Alice wants to pay Bob, she simply sends him this RPOW$_a$ token, by whatever means she chooses. She must ensure that nobody else has access to the token, since a copy of the token is indistinguishable from the token itself and could be spent. When Bob receives the RPOW$_a$ token, he sends it to the server, which marks the RPOW$_a$ token as spent and generates a new RPOW$_b$ token that it sends to Bob. Bob can later proceed in the same way when he wants to spend his RPOW$_b$ token. In this way, Alice’s proof of work can continue to circulate, preventing double-spending by “reusing” the proof of work.

This design suffers from the centralisation of the RPOW server, and Hal was very much aware of this. The proposed mitigation was that the RPOW software would run on special hardware: the IBM 4758. This device was a high-security cryptographic processor designed to store cryptographic keys and perform operations with them securely. It was protected against physical tampering; if a tampering attempt was detected, the device would self-destruct to prevent any security compromise. The device was capable of signing with its own private key the software running on it, so that users could verify that the software running on the server was genuinely the open source software that everyone could inspect. In this way, nobody --- not even Hal himself --- could manipulate the system.

After the first version, Hal continued to improve the system and received the help of Gregory Maxwell.²⁴ Although he planned to include multiple servers so the system would have no single point of failure, RPOW still had the old problem that Nick Szabo had already mentioned years earlier in Bit Gold: the constant advance of technology makes it ever cheaper to create a token. This possibly made it unattractive for other users to start experimenting with the system, since there was no incentive to “get in early”. And at the end of the day, something is money only if it is accepted as a means of payment --- that is, only if it is money. A kind of circular definition that in practice makes it extremely difficult for any new invention to begin functioning as money. Although it never took off, it marked a milestone in the creation of electronic money, since Hal, unlike Bit Gold and b-money, actually implemented RPOW and got it to work.

Given Hal’s interest in electronic money, it is no surprise that he was also the first person to show interest in Satoshi’s project, the first person to run the Bitcoin software after Satoshi himself²⁵, and the recipient of the first Bitcoin transaction from Satoshi himself, on 12 January. He was also the first to help Satoshi in the early days by detecting bugs in the software, which Satoshi went on to fix. Sadly, that same year he was diagnosed with ALS and died in 2014. His last post on Bitcointalk, “Bitcoin and me”[@BitcoinAndMe], is a lesson in positivity in the face of life’s hardships that is well worth reading.

Conclusion

The birth of public-key cryptography (Diffie-Hellman) gave rise to digital signatures (Rivest, Shamir, Adleman). The Cypherpunk movement of May, Hughes, and Gilmore drove the creation of tools to preserve privacy, and the search for decentralised anonymous electronic money was a kind of Holy Grail for them. David Chaum had invented blind signatures and the first anonymous electronic money, Adam Back had created Hashcash, and both Hal Finney and Nick Szabo and Wei Dai used it to create money tokens in their respective systems.

Nevertheless, several things remained to be resolved. The problem of the decreasing difficulty of creating proof-of-work-based tokens still had no solution. But more important still was the elimination of trusted third parties --- those servers that had to be trusted and that represented security vulnerabilities, as Nick Szabo had pointed out years earlier. And last but not least, the question of the incentive to start using it.