Weak Subjectivity Not Required

Proof-of-Approval provides an objective defense against History or Costless Simulation attacks

6 min readMay 20, 2018

Satoshi Nakamoto’s famous Bitcoin [2] uses Proof-of-Work to distinguish the “real” chains from the “attack” chains. Proof-of-Work’s physical resource requirement limits how fast blocks can be added to any chain. It is not possible for an attacker to add blocks faster than the “real” chain without acquiring a very large amount of physical resources. Because of Proof-of-Work, the normal operation of Bitcoin consumes a very large amount of physical resources.

Proof-of-Work provides an extrinsic opportunity cost function to Bitcoin protocol, i.e., Proof-of-Work is completely independent of the contents of the chain. In order to remove the physical resource consumption requirement, intrinsic opportunity cost functions, using the blockchain itself (typically the stakes of the parties), have been proposed [3]. Various Proof-of-Stake protocols and their derivatives are examples of protocols using such intrinsic opportunity cost functions.

It has been argued that protocols using the intrinsic opportunity cost functions are inherently flawed and cannot be made to work [3] [4]. Furthermore, such protocols suffer from many attacks [5] [6], the most debilitating of them being History attack which is also known as Costless Simulation or Long Range attack.

History or Costless Simulation Attack

In this attack, an attacker acquires account information (private keys) of one ore more parties that held a large amount of stake in the past (but may not hold any at present). Using these accounts, the attacker creates blocks from some time in the past to rewrite the blockchain history in his favor. In Proof-of-Stake protocol and derivatives, unlike Proof-of-Work, creating blocks does not consume resources. An attacker, using newly acquired old account information, can create a large number of blocks very quickly from a time in past and successfully overtake the “real” chain.

Depending upon the consensus protocol, such an attack typically requires accounts representing a majority stake in the network at some point in time. If the accounts presently hold none or little stake in the network, their owners may have little incentive to keep those keys private and an attacker may be able to acquire them relatively inexpensively. As a result, an attacker may be able to mount a History attack rather inexpensively.

The solution to History attack adopted by the current Proof-of-Stake systems is called Weak Subjectivity [7] [8], where a newcomer to the protocol, or someone joining backing after a hiatus, must trust some parties to provide them with the valid state of the blockchain before they can participate. In other words, one may be able to detect the correct state of the blockchain purely by objective means in the short timespans but not in the long timespans. For long timespans, objective means are unable to determine the correct state and the newcomer must trust a party to provide them with the correct state.

The protocol being introduce here, Proof-of-Approval, provides a fully objective defense agains History attack. With this protocol, purely objective means can determine the correct state of the blockchain for short as well as long timespans and, therefore, a newcomer does not need to trust anyone to provide them with the correct state.

Proof-of-Approval Defense

Considerations

Just like wealth, the ownership of the stake among parties is expected to be distributed in the Pareto Distribution [9] where where a large
portion of the stake is held by a small portion of the parties. In a typical situation, the number of parties together holding majority of the stake may be hundreds of times smaller than the number of all stakeholders.

The parties are expected to have varying network connection speeds, from high-speed (>1Gbps) cloud connectivity to low-speed (<1Mbps download/100Kbps upload) connections. Computation capabilities of parties are also expected to vary, from high performance servers to low performance mobile systems.

“Real” chain (as opposed to attack chain), is expected to have missing blocks due to real world network and systems issues. An attacker, on the other hand, can easily create a perfect chain since they are likely to be building the attack chain in a single data center in a very short time.

Chain Length Rule

Most stake based protocols count the chain length to be the number of blocks contained in it. This method puts the “real” chain at a disadvantage since it is likely to miss blocks while attack chains may not miss any. Proof-of-Approval defines the chain length to be the number of slots spanned by a chain, thus putting the “real” chain on an equal footing.

Recording Approvals Explicitly

Most stake based protocols record implicit approvals of the parties when they build on top of an existing block. Unfortunately it records a single party’s approval at a time although many other parties may actually agree with it. Their approval of the block is not recorded and is lost in the long timespan.

Proof-of-Approval explicitly records approvals in the blockchain which is its main defense agains History or Costless Simulation attack.

Block Approvals

Each block, in Proof-of-Approval, must get explicit approvals from a quorum stake before it can be placed in the chain. These explicit approvals are stored in the subsequent blocks that are build on top of the block being approved. Block approvals defend agains short term attacks like Nothing at Stake and Bribe attack.

To maintain high transaction throughput of the blockchain, blocks are created at a high frequency. In addition, block approval requires computation intensive block validation procedure. As a result, parties on slower connections or with less computational power are not likely to participate in block approvals.

Epoch Approvals

An epoch is a larger time period defined by Proof-of-Approval protocol that contains many (~1000) slots. Due to the large period, epoch approvals can record explicit approvals even from parties on slow or intermittent connections. Epoch approvals are not intended to validate blocks and require no computation. An epoch approval is simply an acceptance by a party that the chain being signed is the “real” chain. Epoch approvers are paid in proportion to their network stake. Epoch approvals are non-competitive, i.e., all signers are paid their expected amount irrespective of anyone else signing it.

Blockchain State Determination

Blockchain state determination is the determination of which fork, among many provided by the network, is the “real” fork. For Proof-of-Approval, this procedure, for each pair of forks, is:

Rejecting all future slots, choose the longer fork (spanning more slots).
Otherwise, if the forks share all the blocks of the last epoch, choose the fork with the most approval stake stored in the head block.
Otherwise, determine all the parties that created or approved one or more blocks or approved any epochs in each fork or transferred any stake. We call these parties “signing” parties for that fork.
Determine the total stake of the signing parties in each fork in the very first separating block. Choose the fork with the larger signing stake.

With Proof-of-Approval Attacker Requires Nearly the Entire Stake

Proof-of-Stake defends against History attack by making the attacker require nearly the entire stake at some point in the network history. In “real” fork, all rational parties with any stake would sign epochs and get their rewards. Depending upon how far back in time the attack fork is created, the set of signing parties in the “real” fork may include nearly all stakeholders. An attack fork can only win by exceeding this signing stake.

If a simple majority of stake were sufficient, the attacker would need to acquire account information of only a few accounts. But in the entire stake scenario, due to Pareto distribution, an attacker may have to acquire account information of hundreds of times more accounts. In addition, an account even with a tiny stake is as valuable to the attacker as another account, possibly resulting in high asking price for accounts’ information.

On the other hand, an honest stakeholder, holding even a small overall stake for perpetuity, successfully prevents a History attack on a Proof-of-Approval chain.

Conclusion

Proof-of-Approval protocol provides the strongest defense against History or Costless Simulation attacks among any stake based protocols. This defense is even stronger than the Proof-of-Work defense where an attacker needs only 25% of the resources to be able to overtake the “real” blockchain.

Proof-of-Approval also proves [3] [4] wrong which claim that an intrinsic cost function (e.g. stake in the network) cannot be made to work or defend against attacks. It also obviates the need for trust in another party — the so-called Weak Subjectivity.