Protocol Labs Research
2020-11-16 / Blog
A research perspective on Filecoin

The Filecoin network is launching in the middle of a revolution in internet architecture, where vulnerable centralized services dependent on trusted parties are being replaced with resilient decentralized solutions based on verifiable computation, and internet services are being relocated from inefficient central monoliths to the far reaches of the network by peer-to-peer markets.

Filecoin represents an evolution in protocols and services adapted to the needs of the revolution in internet architecture: an open-source decentralized storage network with built-in economic incentives to ensure that files are stored reliably over time. Filecoin and other blockchain networks like Bitcoin and Ethereum are pioneering examples of Open Services: decentralized platforms where commercial service providers —from the corporation to the individual— can compete in an open market.

Filecoin is a living project, and here we trace the evolutionary trajectory of a revolutionary technology in two parts: In Part One, we describe the technological and conceptual advances leading to the creation of the first modern networks based on distributed ledger technology. In Part Two, we focus on Filecoin’s development, from inception to implementation.

Part One: Standing on the shoulders of giants

It would be impossible to capture all of the advances in cryptography, distributed systems, cryptoeconomics, and related fields that have contributed to the development of Filecoin. Nevertheless, there are certain peaks in the technological landscape that stand out:

The era of modern cryptography may have begun in secret at the British Signals Intelligence Agency, with the development of public key cryptography by James Ellis in 1970 and the introduction of the factoring problem in an RSA-equivalent construction by Clifford Cocks in 1973. However, the public lineage leading to blockchain implementations like Bitcoin, Ethereum, and Filecoin began in a U.C. Berkeley undergraduate computer science class with Ralph Merkle’s 1974 CS 244 project proposal for establishing secure communications over insecure communication channels, eventually published in 1978 in the ACM. Merkle’s paper described a cryptosystem based on puzzle-solving, where the puzzles take the form of an encrypted message with an unknown key — an early construction for public-key cryptography. Merkle’s Puzzles, as the paper is commonly known, even contained an early concept of Proof-of-Work1 — the construction underlying Bitcoin, Ethereum, and most other permissionless blockchains today.

Merkle’s public-key cryptosystem, based on computations having quadratic complexity, was not secure enough for most practical implementations. In 1976, with the publication of New Directions in Cryptography, Whitfield Diffie and Martin Hellman built on Merkle’s ideas to devise the famous algorithm known as the Diffie-Hellman key exchange, which is based on a much more complex mathematical problem (the discrete logarithm). Their seminal paper also informally lays out the idea of a cryptographic hash function: a non-reversible algorithm that maps data of any size to a fixed-size bit string.

Shortly thereafter, in 1977, Ronald L Rivest, Adi Shamir, and Leonard Adleman at MIT developed the RSA cryptosystem, an asymmetric cryptographic algorithm based on the factorization of large primes. RSA became one of the first public-key encryption schemes to reach wide use, and is still used in e.g. TLS handshakes between VPN servers and clients to establish secure communications channels.

In 1979, Ralph Merkle submitted a Stanford PhD thesis informally sketching the idea of collision-resistance — a property of a hash function describing how difficult it is to find two inputs that hash to the same output — and a “recipe” for building a hash function using symmetric encryption. The invention of the cryptographic hash function and the development of the concept of collision resistance to measure the security of these one-way functions created a secure means to authenticate data without violating privacy.

By the early 1980s, cryptographers and cypherpunks were making significant progress on the problem of secure communication between trusted parties. But the problem of achieving consensus in multi-party communication including potentially faulty or corrupt parties remained unsolved. In their 1982 paper “Reaching agreement in the presence of faults”, Leslie Lamport, Robert Shostak, and Marshall Pease formally described the Byzantine Generals Problem, the dilemma plaguing distributed ledger implementations since antiquity: how does one create a trustless mechanism for enabling coordination in a system containing unreliable or untrustworthy components?

David Chaum’s 1982 UC Berkeley dissertation “Computer Systems Established, Maintained, and Trusted by Mutually Suspicious Groups” introduced the first known description of a blockchain protocol, including every element of the Bitcoin blockchain (except for proof-of-work), as well as the code necessary for its implementation2. The influence of this prescient but unpublished work is unclear. Though it lacks the robust consensus mechanism (the algorithm that lets users in a distributed system reach agreement without the need for a central arbiter) crucial to modern blockchain implementations, it anticipates many of the important features of current distributed ledger technology.

The 1980s saw further developments in cryptographic hashing: the criterion of collision-resistance for a hash function was formalized by Ivan Damgård, in his 1987 EUROCRYPT'87 paper. A few years later, in 1989, Damgård developed a cryptographic hash function “recipe” almost identical to Merkle’s, and proved in a CRYPTO'89 paper that it satisfied his previously-specified collision-resistance criterion. The idea became known as the Merkle-Damgård construction, and is part of the design of important hash functions like MD5 (designed by Ronald Rivest in 1991), SHA-1 (published as a US federal standard in 1995), and SHA-2. The SHA-2 family of hash functions is a NIST standard published in 2002, and is used in security protocols like TSL, SSL, SSH, and PGP. Closer to the heart of our story, the SHA-256 member of the SHA-2 family is used by Bitcoin and other blockchain protocols to verify transactions and calculate Proof-of Work and Proof-of-Stake.

The collision-resistant hash function was integral to Stuart Haber and W. Scott Stornetta’s 1991 method of certifying the creation and modification of digital documents while maintaining user privacy, published in “How to Time-Stamp a Digital Document” (and later expanded upon with D. Bayer in a 1993 publication and in a 1997 ACM paper; these three publications constitute three of the eight citations in the Bitcoin whitepaper. This method of relative timestamping — establishing the order of events in a decentralized system — was essential to the critical task of establishing transaction priority on the blockchain. Improvements in timestamping presented by H. Massias, X.S. Avila, and J.-J. Quisquater in their 1999 paper, “Design of a secure timestamping service with minimal trust requirement”, were directly incorporated into the Bitcoin proposal.

The Proof-of-Work concept underlying consensus mechanisms in many modern distributed ledger technologies was introduced in 1992 when Cynthia Dwork and Moni Naor published a pricing function based on difficult computation as a scheme for controlling access to a shared resource; the publication describes an implementation to fight junk mail. Dwork and Naor’s paper did not use the term “proof-of-work” — that was invented and formalized later in a 1999 paper by Markus Jakobssen and Ari Juels — but the paper establishes an asymmetrically costly defense mechanism whereby service requesters must perform work that service providers can easily check. This principle of requiring verifiable and computationally costly work as the basis of consensus later became a critical component of Bitcoin’s security assurances. The work of defending and regulating the use of un-metered internet resources continued in 1997 with Adam Back’s hashcash proposal to use partial SHA-1 collisions as a proof-of-work to fight spam (described in detail in his 2002 paper).

We might trace the roots of the modern cryptocurrency era to 1998, when Wei Dai published “b-money, an anonymous, distributed electronic cash system” to the cypherpunks mailing list, which described a protocol having many of the features shared by modern cryptocurrency systems, including transaction broadcast and proof-of-work. In the same year, Nick Szabo proposed a blockchain-based decentralized currency called “bit gold” based on public-key-linked proof-of-work chains and time-stamped block elements. When Hal Finney (later to become the first Bitcoin recipient) created the first reusable proof-of-work system in 2004, he proposed the use of proof-of-work tokens as a form of bit gold.

The growth of the internet spurred further work into hardening networks against faulty node behavior. In 1999, Miguel Castro and Barbara Liskov at MIT published an implementation of a Byzantine fault-tolerant distributed file system able to meet the performance demands of real-world asynchronous internet systems.

Work on problem specification relevant to distributed systems was also producing interesting results in the late 90s. In 1999, Henning Pagnia and Felix Gärtner formally defined the strong fair exchange problem, arguing that it is impossible for two parties to execute a guaranteed, perfectly fair exchange of digital goods without a trusted third party. This finding would later have important implications for the structure of Filecoin’s retrieval market, motivating the need to bootstrap trust between market participants via incremental deal performance.

A few years later, in the early 2000s, we can see the emergence of ideas directly and particularly relevant to Filecoin’s design. In 2002, David Mazières and Dennis Shasha described the features of a multi-user network filesystem in “Building secure file systems out of Byzantine storage”, demonstrating that a trusted network file system can be implemented on an untrusted server. Also in 2002, Sean Quinlan and Sean Dorward at Bell Labs developed the data model of content-addressable storage — a way of referring to data by its content rather than its location — as a Plan 9 service called Venti, using the SHA-1 hash function. This content-addressable data model using SHA-1 was adopted by Linus Torvalds in 2005, for the version-control system Git as a way to avoid centralized repositories, and independently by Bram Cohen at BitTorrent, as a way to avoid central “tracker” servers.

In 2008 Satoshi Nakamoto published Bitcoin, which uses SHA-256 both for content-addressable transaction storage and as part of a proof-of-work consensus scheme overcoming the main hurdle for building a distributed ledger on the internet, the Byzantine Generals Problem.

The release of Bitcoin was a mic drop moment: Bitcoin demonstrated that distributed ledger technology could function at scale in a modern computing environment. Stay tuned for the next installment of this series, where we’ll take a look at the novel development environment ushered in by the first Bitcoin release!

  1. A.T. Sherman et al. 2018. On the Origins and Variations of Blockchain Technologies. ↩︎

  2. A.T. Sherman et al. 2018. On the Origins and Variations of Blockchain Technologies. ↩︎