An examination of proof-of-work and how it solves the mass coordination problem

by Robert ClarkNovember 12th, 2018

Too Long; Didn't Read

Bitcoin itself is a marvel of modern engineering. As technology typically evolves, we are much farther ahead in our development of Bitcoin and other blockchain technologies than we are with our fundamental understanding of them. This post is an attempt to understand the underlying machinations that allow Bitcoin to be the tour de force that it is. I see the proof-of-work mechanism as the most significant contributor to this reality, but the question of why is a little more complicated. Let’s start with the basics.

Company Mentioned

Coins Mentioned

featured image - An examination of proof-of-work and how it solves the mass coordination problem

What problem is proof-of-work solving?

The purpose of the proof-of-work algorithm in the context of Bitcoin is to solve the coordination problem in processing transactions. A somewhat applicable analogy is the Git versioning system. How do you create a system where many people can edit the same data and end up with the same copy of said data when all is said and done? Git solves the minutiae of this problem literally, by allowing all of its participants to push and pull data from a repository, and automatically adjusting only the specific lines of code that were edited from each person’s edits. A system like this would never work with a distributed money, however. With money, you have to deal with the fact that everyone wants to steal it. It would be like if people were rewarded for the number of git commits they successfully pushed through with no regard to quality. Sure everyone could edit it and maintain changes across versions, but at the end of the day your code base would be absolutely useless. This gets at what proof-of-work is designed to solve; how to create a standalone mass coordination network without the crutch of authority.

How does proof-of-work solve issues with mass coordination networks?

The crypto space is flooded with new ideas about how to use blockchain to solve existing problems in new ways. The issue with most of them is that computation is far and away the best application of the technology. To truly understand why this is the case we have to think about the typical problems with internet based mass cooperation systems and how proof-of-work solves them. These issues make up a hierarchy similar in structure to Maslow’s hierarchy of needs, in which one can only be achieved once its respective base layer has been achieved. The issues are, from bottom to top; creating mass participation, agreeing on correct participation, and unlocking additional value of mass coordination.

Proof-of-work has three main principles that allow it to succeed in this endeavor:

Physiological

People are rewarded for creating proofs — This is the underlying reason that anybody cares about creating proofs. In Bitcoin this was achieved intrinsically, as Bitcoin itself was designed to be a system of value allocation so it had no trouble rewarding value to those who create proofs.

Social

Proof verification is orders of magnitude easier than proof creation — This allows time for Schelling points to disseminate across the network, specifically the addition of new blocks. Were verification harder and block creation easier, forks would become far more common and nodes would have a much harder time converging on a single chain, despite the fact that the correct chain in Bitcoin is always the longest. Ultimately this allows the rewards for proofs to be judged as ‘fair’ or at the very least systematic.

Proof is just as costly to fake as it is to create honestly — In essence this means that there are no advantages that can be gained in creating fake proofs instead of true ones. Again, this is slightly inaccurate due to the existence of methods such as ASICBoost, and the cost advantages of mining at scale, (which aren’t exactly fake per se but fake in the sense of outsized rewards per work) but for the most part these risks have been mitigated by the sheer magnitude of mining on the network. The reason this principle exists is that the design of the protocol requires brute forcing computations, so that you can’t simply work backwards from the answer (which is a relatively simple specification).

Can proof-of-work (or just ‘proofs’) do anything other than Bitcoin?

The answer to this question is undoubtedly yes, but the real question that matters is can it do anything else well enough to base a mass coordination network on. My argument is that the farther away from strict validation of computation you get, the harder it is to use proofs. In Bitcoin you can easily validate transactions because all you have to know is if the person has enough money to send, and if they properly signed their transaction. Ethereum is slightly harder because you have to execute code, but something like supply chain management would be totally impossible (which is why they should be built on top of blockchains, not as blockchains). To answer this question lets take a look at some of the industries that proponents of blockchain have claimed will be violently disrupted by this technology, and how each of them solves the hierarchy of mass coordination networks needs. Each of these examples will show differing degrees of physical requirements to understand the extent to which non-computional truth can be mass verified.

Example 1: Blockchain Voting

For each of these theoretical systems we have to consider how proof-of-work principles apply to solve traditional problems, and what aspects of the proof-of-work system have to be slightly adapted to fit the needs of the problem. In the case of voting, these are the problems we need to solve: how to get people to vote (already largely solved), how to get people to agree on the correct voting procedures (identification required, preventing double-voting, etc.), and how this solution would be an improvement on the current system. Let’s look at the second and third problems more in-depth:

Defining voting rules — There are a number of problems with voting that are unique to identity based blockchain solutions. Among these are proof of life, proof of identity, and proof of intent. Each voter has to prove that they are a valid voter, that they are still alive, and that they intend to vote for the candidate they are voting for. You can see how each of these problems are solved almost trivially with physical voting. You walk into the voting location (proof of life), display your credentials (proof of identity), and cast your ballot (a poor but acceptable proof of intent). You can also see how this may be a bit more of a challenge when this process is digitized. The charts below show how each type of proof meets the various requirements for secure coordination (admittedly at a low level of analysis).

This chart gets a little ridiculous when you start breaking down these concepts as though they were computer science constructs, but it is useful at understanding the requirements of porting ‘hardware’ (physical identity, cost of time) to a blockchain for verification. As you can see, falsification of records becomes a much more significant issue when voting moves to the blockchain. This makes sense as attacking a physical network is far more resource-intensive than attacking an internet network, with added costs of time and human capital. Another interesting thought on this is the difficulty of tethering accounts to identity. In Bitcoin the network doesn’t care about who you are as a person, it only ever has to interact with account numbers. The problem of creating a true identity-account tether is one that is currently insurmountable, and is why any idea for blockchain that relies on it is dead on arrival.

Achieving self-actualization— A blockchain-based system would easily satisfy this with additional transparency, accountability, and accuracy. The issue here is that it is ridiculously difficult to complete the base layers of this network, including problems such as the creation of private keys tagged to identity, private key management, and cost of attack for Byzantine parties. This doesn’t even begin to address the issues (inherent in both strategies) of trusting the federal government to manage identity. At the end of the day, the best part about physical voting is kind of like the best part of Bitcoin; it’s not efficient, but it is ridiculously difficult to attack.

Example 2: Supply Chain Logistics

Supply chain is another heavily-touted use case for blockchain technology, that really misses the point of what a blockchain is supposed to be used for. The crucial ingredient that is missing here is the lack of thought around ‘proofs’ being posted to the blockchain. One of the core innovations of Bitcoin was that it was entirely intrinsically verifiable, that only the data on Bitcoin mattered to determine the validity of edits to Bitcoin. While we discussed potential solutions to this in the previous example, supply chain logistics needs radically more outside information ported than even a blockchain voting system. If we take the example of Walmart’s produce supply chain we can see that all of the information that was previously provable becomes garbage, and as such all insights generated from the garbage also become garbage. This isn’t even to say that the system Walmart has created won’t generate value for them, but it is absolutely to say that it is in no way computationally secure.

The analysis in this chart is almost totally pointless except to point out that unless Walmart is doing all of the verification here, or has somehow devised an ingenious cryptographic algorithm to port vegetables and transportation of said vegetables into data, this “proof-of-work” will mean absolutely nothing. What this means is that Walmart is creating a so-called private blockchain, which in reality is just an append-only database. If let into the wild, this blockchain would be attacked viciously. Walmart in this case is almost certainly going to restrict access to it, and be a source of authority for it as well. Proof-of-work has almost no use case here, as there is no real way to prove any type of work has been done except for asking Walmart.

Example 3: Token-curated Registries

This example shys away from the concept of proof-of-work slightly, and requires a little bit of prior knowledge (see here), but is very relevant to question of what it means to be a proof. I’ll start off with this tweet from Vitalik Buterin.

body[data-twttr-rendered="true"] {background-color: transparent;}.twitter-tweet {margin: auto !important;}

The wonderful @ATabarrok on token curated registries: https://t.co/O7j9TyEQn8 TLDR: it's hard, and most realistic to apply to data that is easy to independently verify. Also, TCR designs should take more care to accommodate the value of specialists in information gathering.

— @VitalikButerin

What Vitalik is saying in this post is that TCRs work best when the information you are porting to the blockchain can be easily proven despite the fact that it can’t be computationally proven with information already verified by the blockchain. Moving back to the Walmart example, if it were relatively easy to figure out who grew what vegetables (i.e. if farmers were required to submit to government checks on how many vegetables they grew) then it wouldn’t be such a stretch to say that this information could be proven on-chain (at least to the degree with which it could create a functioning coordination network). Unfortunately, this example requires trust of the government, which is why I personally disagree with Vitalik’s take on TCRs. I believe TCR voting should create reality, not prove it.

To elaborate, let’s take the example of Messari’s TCR on compliant token projects. The goal here is to require a certain level of disclosure for token projects and their token distributions, and then to decide whether or not they should be included on a whitelist of honest projects. In a traditional proof-of-work system this would mean defining some characteristic of a compliant token project, optimally based on data proven on other blockchains and some timestamp to show when the data was compliant or not. This could function well as a proof, except for the fact that reading today’s blockchains is quite expensive and it would not satisfy the “More costly to create than to verify” requirement. This is what Vitalik is getting at; unless the data is proven elsewhere and easy to get to, you can’t use proofs for it. TCRs, however, can actually create intrinsic proofs in the same way Bitcoin does. As Bitcoin needs nothing more than signatures and UTXOs, so do TCRs need nothing but signatures and votes. In the example of Messari, you could try to use Ethereum blockchain data and submitted compliance data to create proofs that there is a data mismatch, or you could simply assume the voting mechanism creates proofs. These would still be costly to create as they require a significant portion of tokens; and also much cheaper to verify than to create as you could verify them by simply counting votes. The problem here is that this is almost a semantic argument, what’s the point of a proof if it isn’t proving anything but itself? My answer to that is simply that it satisfies all the requirements for creating a mass coordination network. You can still get all the benefits of a coordination network despite the fact that an attack may be more complicated to define.

Conclusion

What I hope you got out of this piece is why proof-of-work is a significant innovation, and why porting it out of strict computational math must be done understanding the risks. While this may dampen the hopes of many a blockchain enthusiast, it also brings credence to use of blockchain as a primitive for electronic money. While it may be exceedingly difficult to create true proof systems for ultimately subjective or costly to verify questions, it can still be used effectively as an incentive and value distribution layer for participants to answer these questions correctly.