Proof of Useful Work
Background
When Satoshi designed Bitcoin, he wrestled with two primary problems. Firstly, he needed to find a way to prevent what is known as a "Sybil attack", which would allow an adversary (i.e. the bad guys) to add additional nodes to the decentralized network, until they could take control. Secondly, he needed to find a way to bring the network to consensus regarding changes to the ledger (i.e. what transactions were processed, and in which order).
His solution was proof-of-work (now sometimes shortened to PoW). Although often described as a decentralized consensus protocol, it is both a decentralized Sybil-resistance scheme, and a consensus protocol. In order to participate in "mining" bitcoin, it is necessary for miners to run special hardware that creates large numbers of cryptographic hashes of blocks they wish to propose, until a "winning" hash is found, whereupon they can submit the block to the network. In practice, the relative number of blocks that each miner produces, and the rewards they earn, is proportional to the amount of hashes that their hardware can perform.
Proof-of-work solves the Sybil problem because vast volumes of hashes have to be calculated to have a chance of producing a block, which involves the dedication of expensive mining hardware, and copious amounts of electricity. As participation in the Bitcoin network grew, it quickly became too expensive for any adversary to acquire and run sufficient hashing hardware that they could perform a large enough share of the network's hashing that they might gain control (for example to double-spend). By fortune, the Sybil-resistance scheme also helped solved consensus, since hashes are random numbers, and winning hashes are discovered randomly only through brute force, and thus a random miner is assigned the job of creating each block.
A great advantage of proof-of-work is that it results in a chain that is produced by relatively stable, dedicated hardware, creating a secure network. Essentially, the Bitcoin network that produces blocks can be thought of as a giant decentralized hashing factory. However, the downside is that the scheme essentially works as a hashing competition, in which the total money miners spend on hashing hardware, and the large amounts of electricity necessary to keep it running, tends towards the value of the block rewards that Bitcoin provides. Moreover, the scheme does not reach consensus quickly.
As a result of the expense, the blockchain industry worked on proof-of-stake (often shortened to PoS) schemes, in which individual network nodes would be joined to the network by staking ("locking") some amount of cryptocurrency, then producing blocks, and earning rewards, in proportion to the amount of cryptocurrency that they have staked. This replaced the expense of the dedicated hashing hardware, and the electricity used to run it, with the cost of capital involved in staking. Ethereum 2.0 migrated the network from a PoW architecture to a PoS architecture. Not only did this allow the network to run much faster, because it could use alternative consensus schemes, but it prevented the environmentally-costly expenditure of electricity to power the hashing hardware.
However, PoS has numerous challenges, which are becoming increasingly apparent. Firstly, once the need for dedicated hardware was removed, a block-producing network node (or "client") could simply be spun up anywhere, including the corporate cloud, and activated just by staking some cryptocurrency. As a result, the vast majority of nodes on PoS networks, run in the cloud. The dangers of running a blockchain in the cloud were recently brought into sharp relief – the Hetzner cloud, in Europe, recently suddenly banned Solana nodes, immediately causing 40% of its network to disappear in the blink of an eye. A PoS network running in the cloud is very different to a sovereign network, and the potential exists for cloud providers to interfere with nodes, as well as to close them down.
Another challenge with PoS is that cryptocurrency, by its nature, is highly liquid, raising the possibility of swift changes in network architecture and the distribution of power, which is something an attacker can potentially exploit. For example, clever manipulations of DeFi, or the catastrophic hack of an exchange, might provide an attacker with sufficient stake that they can break the network – allowing them to profit after suitably hedging their staked cryptocurrency. PoS networks often provide frameworks that make it easy to spin up new nodes on the cloud in an instant, allowing a suitably financed adversary to launch an attack by running a script.
Proof of useful work
Proof-of-useful-work (PoUW) is the Internet Computer's answer to these kinds of considerations, and is more complex than the foregoing schemes. It involves a blockchain being produced by dedicated hardware called "node machines" that are of very similar, standardized specification. On the Internet Computer, these run highly sophisticated consensus protocols that lean into the power of advanced cryptography, often referred to as Chain Key Crypto. PoUW is concerned with membership in the network.
Naturally, as per PoW, the purchase, hosting and operation of node machine hardware acts as the stake. However, these machines don't do hashing, and simply produce and process blocks of transactions that represent smart contract computations. The reason that combined node machines must be built to the same standardized specification, is that rather than compete to perform hashing, they must try not to "statistically deviate" by producing more or less blocks. In essence, rather than trying to perform more computation, they try to perform the same amount of computation, and can be punished for deviating from the group.
A key ingredient of the scheme is the Network Nervous System (or NNS), a sophisticated permissionless DAO that is integrated with the Internet Computer's protocols. This fully controls the network, configuring it, and upgrading the software run by node machines. Amoung its responsibilities, it combines node machines to create "subnet blockchains," which themselves are combined into a single blockchain using Chain Key Crypto. This achieves two important things. Firstly, expense aside, it is not possible for an adversary simply to add nodes to a subnet blockchain, since the NNS carefully selects nodes by looking at the node provider, the data center the node is installed within, and its geography and jurisdiction, in a scheme of "deterministic decentralization." Secondly, the NNS can remove (or "slash") nodes that statistically deviate.
By applying deterministic decentralization, the NNS creates a highly secure scheme in which the Internet Computer runs on a sovereign network of dedicated hardware, formed from node machines, which machinery can be tightly held to correct behavior in order to continue its participation in block production (through which its owners, the node providers, earn rewards). In PoUW, the repetitive hashing work of PoW, whose purpose relates primarily to network operation, has been replaced by useful smart contract computation. Since this is work that must be performed anyway, a supremely efficient network is produced.
Useful historical resources
Project founder Dominic Williams was an early pioneer in the study of crypto Sybil resistance and consensus. Here in May 2015 he gives a talk discussing Sybil resistance and consensus at San Francisco Bitcoin Devs, in which he discusses the "3 E's of Sybil Resistance." Other interesting historical material that provides insights into the development of PoUW, include a panel on scalability with Vitalik Buterin and Gavin Wood, and a talk introducing consensus theory, at Ethereum's DEVCON1 later that year.