Decentralized Objective Consensus without Proof-of-Work

Decentralization and objective consensus are two of the main challenges faced by today’s cryptocurrencies. While the lack of objectivity is commonly attributed to Proof-of-Stake blockchains, the actual degree of decentralization is questionable in any existing consensus algorithm whether based on financial stake or computational resources. We will analyse both difficulties and present a novel blockchain model that offers objective consensus along with a strong tendency of decentralization.

Decentralization of the consensus group

Although Bitcoin was designed in an attempt to decentralize control over the underlying currency, serious concerns have been raised whether Proof-of-Work (PoW) as its core mechanism can live up to this aim. Several factors indeed compromise Bitcoin’s main design goal:

1. Profitability of mining significantly depends on electricity costs and thus on the location of the mining equipment.
2. The unequal distribution of resources and economies of scale impacts on the consensus and gets reinforced by the mining rewards.
3. Current block hash difficulty makes it infeasible for private users to mine unless they take part in mining pools (which again leads to centralization).

Unfortunately, PoW’s main competitor, Proof-of-Stake (PoS), suffers from similar, even worse problems. It pays interests to stake holders and centralizes control in proportion to stake (coin ownership), which is an unevenly distributed, finite resource. As a result, numerous vulnerabilites impair the security of PoS coins. Attacking the currency is a one-time cost of stake that sustains forever, whereas for PoW the attacker must continue to expend resources on mining to maintain an attack. One might even profit from attacking the coin by shorting it while never needing to sell your stake. Attacks seems to be possible with much less than 50% of the stake.

Objective consensus

A consensus protocol is said to be objective if a new node joining the network can independently arrive to the same state as the rest of the network based solely on protocol rules (e.g., a definition of the genesis block) and messages propagated across the system (e.g., a set of all blocks). PoW consensus as used in Bitcoin is an example of an objective protocol; as long as a new node is connected to at least one “honest” user, it will always regard the blockchain with the highest computational difficulty as the valid chain. Forks pose no threat to newcomers.

Classical PoS, on the other hand, lacks this crucial property. Anyone who can build a fork longer than the actual chain will confuse new nodes which are not able recognize the canocial chain as such. It appears that PoS history has no verifiable longest chain. While long range forks can be rejected by existing users of the system who keep track of the chain’s history (e.g. by limiting the length of possible forks), newcomers must rely on additional information about the recent state of the blockchain. Such a consensus protocol is called “weakly subjective” since joining users need to have access to the current block from a trusted, reliable source. This compromises the blockchain’s trustlessness.

One entity, one vote

Sybil attack

In a Sybil attack, the attacker is creating a large number of pseudonymous identities to gain a disproportionately large influence over a peer-to-peer network. If decision making was for example based on one-IP-one-vote, it could be subverted by anyone able to allocate many IP addresses for his nodes. A system’s vulnerability to a Sybil attack ultimately depends on how cheaply identities can be generated and accumulated. In existing cryptocurrencies, creating an account (or address as it is called in Bitcoin) is a fairly easy process that only involves generating a private/public keypair. Therefore, any user could theoretically create an arbitrary number of accounts. PoW and PoS counter this problem by not basing voting power on the number of accounts or IP addresses a user possesses.

Paid and free accounts

The question arises if a cryptocurrency could nevertheless be built on the idea of one-account-one-vote. Such a scheme would require that the entities don’t use multiple accounts, fulfilling the principle one-entity-one-vote. As already said, Sybil attacks can occur if it’s cheap to generate identities. Conversely, we have to make sure that creating accounts is costly. One must assume, however, that not every user is able and willing to pay for an account. That’s why our proposal is based on two types of accounts, both of which can be used to make transactions to accounts of any type:

1. Free accounts with no minting power
2. Minter accounts who build the blockchain

Minter accounts as a rate-limited, non transferable second token

As people need an incentive to pay for minter accounts, the latter must possess a value of their own. To that end, we have to provide them with an advantage over free accounts and make them a limited resource. Minter accounts will in that case act as a second token with regard to the underlying currency. Such a system on its own cannot solve the problem of centralization however; a rich entity could still buy a significant portion or even the majority of all minter accounts in order to gain control over consensus. It is obvious that paid accounts aren’t sufficient for achieving decentralization. We additionally have to make sure that a single economic entity doesn’t get any benefit from using multiple accounts. So, rather than paying out a fixed reward to the minter accounts, we will pay them interests on their current account balances. As a result, the total interests will be the same, no matter how an entity splits up its stake among its accounts. Of course, this idea wouldn’t work if we just paid the interest to the creator of the current block since a stake holder could increase his chance of obtaining the reward by using several accounts for minting. Therefore, we will pay interests to every minter account, in proportion to its stake in the currency, every time a new block is created by anyone.

This leaves us with the question why stake holders would build blocks if they get their interests anyway. Also, a powerful attacker might try to obtain the majority of the accounts with the aim of launching a double-spending attack. Hence we must curtail the trade with accounts and make it hard to gain majority control over the coins. Fortunately, both problems can be solved if we turn minter accounts into a non transferable, limited resource.

Parent and child accounts

Instead of creating minter accounts “out of thin air”, let’s give the builder of the current block the right to create a new account which he can sell and transfer afterward. We will call the latter accounts “child” accounts, and the account of the creator will be called “parent” account. As a result, minter accounts will form a tree structure as shown in the picture below.

Diagram 1: Account tree structure

Now, it becomes clear that minter accounts will constitute a rate-limited resource as they cannot be created faster than blocks. An attacker seeking to obtain >50% of the minting power (being the sole buyer) would have to keep buying child accounts for a period of blocks t that (at least) corresponds to the number of blocks N that existed at the time when he started his plot.

Diagram 2: Required time to take control over 50% of the minter accounts

The longer the blockchain exists, the longer it will take for an attacker to build up a majority impact on consensus. The blockchain’s security will unceasingly increase over time. As time in the absolute sense is non-negotiable and naturally limited due the finiteness of life, it can secure the blockchain from attackers regardless of their wealth.

One problem remains to be solved. If existing accounts could be freely transferred to new owners, an attacker might easily bypass this security layer by accumulating existing accounts rather than child accounts. It is easy to see, though, that even without any special arrangement, buying existing accounts requires a transfer of the account’s private key, which makes the deal very risky for the buyer. The seller who will still know the key could use it to “steal” the account’s balance after the fact. We can leverage this risk for our purposes if we require that a minter account must possess a certain minimum account balance to build a block. We assume that such a requirement can effectively prevent attack scenarios based on accumulating existing accounts.

As a fortunate side effect, stake holders with minter accounts will have an incentive to build blocks thanks to the profits they can make by selling child accounts. While existing accounts remain non-fungible, the market will eventually decide on the price of child accounts.

Decentralized group of minters

As shown above, it doesn’t make sense for a (rational) entity to have more than one account since its actual interest does not depend on the number of accounts but on the stake. While a minter may decide to keep child accounts with the aim of selling “grand child” accounts later on, it isn’t rational to do so considering the capital lockup costs of holding an account until it gets the chance to mint a block. The average holding time will increase as the pool of minter accounts grows due to the decreasing probability for each account to create the next block. Therefore, the market price of a minter account will tend to be determined by the interest rate in the first place rather than by the outlook of creating and selling child accounts. Holding a child account in other words means that you cannot reinvest your gain into the currency and that you won’t receive interests for that sum for a long time.

Even if we assume that some minters will keep their child accounts for themselves, they won’t be able to increase their total minting power without buying new accounts since the minting pool grows as well. All they can achieve is retaining their relative impact on the consensus. Eventually, with more and more stakeholders selling their child accounts, the minting power will become increasingly decentralized.

To summarize, our blockchain design is based on a dual token scheme with interacting PoS relationships. Minter accounts act as a second token, which you need to build the blockchain and also to “mint” child accounts, and there’s an opposite PoS relationship in that you need coins (the first token) to “fill” the minter account so that they can produce more coins (interests).

Building the blockchain

Sybil proof accounts are an important building brick of a secure, decentralized blockchain, but they aren’t sufficient. We also need a method to select the minters in a random fashion which is safe from manipulation and DDoS attacks. Furthermore, the nodes must have appropriate rules to decide if a certain blockchain is valid and which of several blockchain candidates is the canonical one.

Selecting the next minter

In a PoW blockchain, a block B’s hash must not exceed a certain threshold and the miners thus have to iterate through the possible variables in the block header repeatedly to find a valid block:

By setting the difficulty threshold d one can regulate the expected creation rate of blocks (“block time”). In most blockchain designs, the difficulty is automatically adjusted by the protocol to ensure that the block time remains constant on average. For the sake of simplicity, we will omit this aspect in our design.

In a classical PoS algorithm like NXT, the inequality depends on the user’s stake in the currency or account balance bal(A). To make sure that a block can eventually be built in any situation, a timestamp is included in each block and the time elapsed since the creation of the previous block is added to the formula:

After a new block is propagated across the network, the chance to satisfy the condition for any given user is initially low and grows with time. Moreover, this formula allows to predict with reasonable accuracy the minter of the next block. Unfortunately, predictability facilitates DDoS attacks against the next minter. Also, we have to avoid that nodes can increase their chance of minting by manipulating the variables. That’s why we are not going to use this inequality as such but a more sophisticated scheme.

Hash chains as a source of randomness

To guarantee that the creator of the next block is selected randomly, we will resort to a technique called hash chain. Hash chains are built by taking a random value (or “nonce”) and hashing it n times in succession using a cryptographic hash function like SHA256:

Assuming that a verifier already knows the chain result for n, the creator of the chain can authenticate by giving the verifier the hash chain for n–1, who will then hash it and check if it equals the chain result. This process can be done repeatedly, by peeling off multiple layers from the chain and rehashing it several times for validation.

We will use the following notation for a function that removes k layers from a given hash value x:

Owing to the fact that a cryptographic hash function is a one-way function that cannot be inverted, it is clear that the “peeling off” function cannot be applied directly to a hash chain. On the contrary, it can only be determined by hashing the original nonce n-k times, which is only possible if you know the nonce:

Hash chains can be extended into a private random generation scheme where a person first publicly commits to a certain chain result and then subsequently reveals its inner layers, which will then serve as verifiable random pads. In case of a blockchain, the commitment can be done via a special transaction that records the hash chain’s result in the latest block. Once a person has committed to such a chain, she won’t be able to tamper with its layers. On the other hand, she might have influenced the outcome in advance by selecting the nonce accordingly, which makes the scheme prone to preliminary manipulation. Luckily, a combination of the hash chains of multiple entities can be used to prevent that any single person can manipulate the end result. To apply this idea to our blockchain, we first have to take a closer look at how minter accounts are created.

Creation of minter accounts

As stated above, new minter accounts are derived from existing parent accounts. Whenever a block is built, the parent account gets the right to give birth to a child account. To this end, the minter must issue a genesis transaction containing the public key pk of the child account. When selling the child account to someone else, the creator must use the public key provided by the buyer in order to make the account accessible through the latter’s secret key sk. Prior to first use, the child account must be activated by its new owner through an activation transaction, containing a commitment to a hash chain signed with sk that can be verified with pk from the genesis transaction. The account will be considered active once its activation gets confirmed in a certain number of blocks, which we call the activation period k.

Diagram 3: Account creation

We are now ready to tackle the actual minting inequality of our model.

Minting inequality

In our design, each block must contain 1. a timestamp ts, 2. the hash of a previous block and 3. the minter’s current hash chain value, i.e. the chain position for the i’th block created by the account A:

For convenience, let’s use the following simplified notation for the hash chain value recorded in the j’th block of the blockchain:

This allows us to write our basic minting inequality for the next block m+1 as follows:

So, we build the hash of all hash chain values in our blockchain of length m combined with the current minter’s hash value and check if the result is lower than a certain difficulty d multiplied by the elapsed time t since the previous block. The elapsed time is defined as the difference between two consecutive timestamps:

If the inequality holds for a block, it is considered formally valid, provided that its minter possesses the minimum account balance to mint. This formal check is done based solely on the information included in the blocks, without resorting to an external time source. A whole blockchain is considered valid if all of its blocks are formally valid, which can be checked by any node for every block at any time.

When a new block arrives, it is only accepted by the other nodes if its timestamp ts fulfills the following constraints:

1. ts is not lower than the current UTC time – offset o
2. ts is not bigger than the current UTC time

As a consequence, timestamps that are foredated or broadcast too late on the network won’t be accepted. Due to irregularities of network propagation, it may occur that a block arrives too late at certain nodes to be considered valid. However, as long as the majority of the minting nodes (accounts) receive the block in time, they will start minting on top of it, so that eventually a new block will probably be attached to it. Once this happens, the previous block will also be accepted by the late nodes, since the time constraints are only applied to the most recent block of the chain.

Chain selection rules

The validity check along with the time constraints does not allow to select between multiple valid chain forks. We need additional chain selection rules to determine the canonical chain. Assuming constant block difficulty d, we can apply a simplified version of Bitcoin’s longest chain rule (LCR) to our blockchain and consider the chain with the highest number of blocks as the canonical one. If two forks have the same length, the last block with the smallest timestamp verifying the time constraints wins the race. If both last blocks have the same timestamp, the account with the higher public key is accepted as the current minter. (An additional chain selection rule will be introduced in the Chapter “Heartbeat transactions to achieve objectivity”.)

Tamper-proof undercover minting

In contrast to PoS blockchains that make use of transparent forging, our algorithm is based on hash chains and thus enforces unpredictability of who becomes the next minter. All the minting is performed “undercover” which is a big advantage with regard to DDoS resilience as the attacker cannot focus his efforts on breaking the node that is currently minting. Furthermore, nobody is able to increase his chances of minting by choosing a specific nonce for his hash chain, even if he controls multiple accounts. The combination of the hash chain values of all past minters thwarts any attempt to influence the selection process given the fact that every minter has an unpredictable impact on the future minting order. This is also true with regard to the child accounts created by an existing account since the hash values contained in the blocks built during the mandatory activation period will also contribute to the randomness.

Attack scenarios and protective measures

Nothing-at-Stake problem

A well-known issue related to PoS is the so called Nothing-at-Stake (NaS) problem. As minting doesn’t involve a significant computational effort, a rational user may use a modified client that deviates from the protocol rules (e.g. LCR) and mints on multiple forks in order to increase the chances of creating the next block. The chain selection rules in other words don’t constitute a Nash equilibrium, i.e. a state in which no participant can gain by a unilateral change of strategy if the strategies of the others remain unchanged. It should be noted that NaS is not an attack vector by itself but rather a game-theoretic design weakness that can reinforce natural forks and facilitate certain attack scenarios.

Punishment schemes have been suggested to remedy the NaS issue. The schemes differ with regard to the “punishable offense” and the imposed penalty. One possibility is to punish double-minting per se. While it is obvious that minting blocks on conflicting chains of the same length is against the rules, it’s questionable if double-minting should be penalized as well if the blocks are created at different chain positions. For it may happen that an honest node mints a block on a chain that becomes orphaned and that the same node gets the chance to mint on a conflicting chain later on. Furthermore, instead of actually creating multiple blocks, a node may simply try to mine on top of every fork and broadcast one single block even in the rare case that it succeeds on both. A rational miner would thus compute the challenges for many different chains, and if one of them hits the target, add his block to the corresponding chain, no matter if it’s the best best chain he has seen so far. Such a behavior can destabilize the network and must be avoided. One way of achieving this is to make sure that the minting nodes are determined before a fork takes place. By pre-selecting the minters k blocks in advance, the target would be the same for both chains provided that the chains have forked no longer than k blocks ago.

Alternatively, one could punish accounts for creating blocks on the wrong chain. This comes with a problem of its own: Sometimes, minters are not certain which of two candidate blocks at a given position is ultimately going to win, so they may abstain from creating blocks entirely out of fear of being penalized. However, this problem can be tackled by selecting an appropriate punishment that is neither too weak nor too harsh. Hence, instead of e.g. destroying the account and its balance, we will opt for a less severe penalty: If an account is caught minting on the wrong chain (i.e. it attached its block to a block N that didn’t become part of the canonical chain), it loses its ability to mint and procreate, while it keeps earning interests on its stake. In our blockchain design, a single account rarely gets the chance to mint a block and the probability decreases as more and more accounts are created. Therefore, even in the presence of multiple chain forks, it seems unlikely that a user eligible for creating the next block would renounce to his chance given the low probability of becoming the minter in the foreseeable future again.

Compared to other punishment schemes, our mechanism doesn’t rely on security deposits with a limited duration but leverages the accounts as a permanent token of the system. This has the advantage that the incentive not to mint on the wrong fork will last forever, without locking up funds permanently. Having a penalty for minting on the wrong chain should effectively prevent short-range attacks where the attacker tries to fork the most recent blocks. To build a blockchain which is longer than the currently accepted one, an attacker must possess or control >50% of the minter accounts that are currently active. As shown above, the attacker would thus have to keep buying new child accounts for a period longer than the existing blockchain. This scenario gets increasingly unrealistic as time goes on.

Long-range attacks

Let’s consider that an attacker tries to rewrite history instead of taking over the blockchain as of now. This is where it gets serious for existing PoS blockchains, at least theoretically. One reason is that if someone had stake in the currency in the past, then this previously owned stake could, in principle, be used to create a fork of the block chain starting from that earlier time. An attacker could even buy old unused keys to carry out his attack. That’s why many PoS cryptocurrencies avoid a long range attack of this kind by preventing long reorganizations. For example, in NXT a user may not accept the alternative blockchain if it differs from the existing blockchain in more than the last 720 blocks. This restriction, however, does not solve the problem for new users. When a newcomer connects to the network, he sees multiple blockchains with no prior knowledge of their authenticity. One way to know which is the right blockchain is to download it from a trusted source; however, this makes the system semi-centralized and not completely trustless. Vitalik Buterin calls this “weakly subjective” in contrast to the “objective” criteria used by Bitcoin.

In practice, long-range attacks aren’t as easy to perform as they look in theory, since the attacker must overtake the canonical chain mined by the other nodes (i.e. also the nodes who sold their old keys and kept contributing to the main chain).

Stake and account grinding

Unfortunately, long-range history attacks are facilitated if the attacker can influence the block creation order in his forged chain by creating multiple accounts, shifting money back and forth or through other means. In our design, an attacker could, for example, choose the nonces of his child accounts so that one of his existing account gets the right to create the next block for a small timestamp. By stringing together blocks with low intervals he could eventually overtake the correct chain, while fulfilling the time constraints. Unpredictability and tamper resistence as mentioned above can thus only be guaranteed for the future, not for past blocks.

On the other hand, the mandatory account activation period makes it hard to build the first series of blocks starting from a branching point because child accounts cannot be used for minting before they get activated. If the activation period is long enough and the attacker controls only a minority of old accounts, his forged chain would show an unnatural slowdown (larger intervals between blocks) right after the branching point which might be detected statistically. Nevertheless, one shouldn’t rely on this as a defense, especially if we assume attack scenarios where the attacker may get hold of >50% of old accounts.

Heartbeat transactions to achieve objective consensus

To effectively prevent long-range attacks we introduce a novel defense mechanism which we will call heartbeat transactions. We require that every minter account issues transactions with a certain regularity to stay alive. If the last transaction is older than k blocks (heartbeat period), the account will be downgraded into a “free” account that isn’t able to mint blocks and to receive interests any longer. Similar to TaPoS, heartbeat transactions must contain a reference to a recent block of the chain, otherwise they won’t be accepted by other nodes. Apart from this, every transaction can count as a heartbeat transaction, so an account may simply send money back to itself. Like every other transaction, heartbeats must also include a small fee to avoid transaction spam. As a consequence, “double-heartbeating”, i.e. adding transactions to multiple chains becomes costly.

As the owner initially had to pay for his minter account, it is safe to assume that he will try to keep it alive as long as he has a stake in the underlying currency. In general, his incentive to make heartbeat transactions will persist for a much longer time than the heartbeat period, provided that the latter is set appropriately (it makes sense to use the same length as for the activation period of new accounts).

What is this all good for? Well, let’s take a random block B. By looking at the history of the chain starting from the genesis block, we can see which minter accounts are still alive at block B and which had been downgraded into free accounts up to that point. The k next blocks then allow us determine how many of the active accounts are still alive at the end of an additional interval equal to the heartbeat period. It can be expected that this will be a high percentage or in the best case the entirety of the accounts. Let’s assume the latter for now and consider that an attacker controlling >50% of the (active) accounts generated before block B wants to create a fork starting from this block. It is obvious that he can only include forged heartbeat transactions originating from the accounts that he controls (and from their child accounts if the activation period is shorter than the heartbeat period). In contrast, without knowing the corresponding private keys, the attacker isn’t able to reproduce heartbeat transactions from all the other accounts that were created before block B. Therefore, even a newcomer without prior knowledge could distinguish the fork from the authoritative blockchain by the fact that it has fewer unique heartbeat transactions (heartbeats of the same account aren’t counted if they are contained in multiple conflicting chains). In this best case scenario, it suffices that one single honest account didn’t sell its old key for being able to determine the right chain which will simply contain one more unique heartbeat.

Now assume that a total number of n accounts were present at block B and that a subset m didn’t make a heartbeat between B and B+k (either because they simply failed or because they were too new and hadn’t been activated yet). Let’s call this subset of accounts pivotal accounts.

It turns out that if the attacker controls c out of m pivotal accounts, then he must also control > n–m–c out of the n–m non-pivotal accounts to make his chain look canonical. Provided that m is much smaller than n, the attacker therefore needs to possess the keys for almost all historic accounts at a given time (regardless of c), which is a very strong property (see picture below).

With the presented mechanism, new nodes don’t need to get the canocial blockchain from a trusted source since they can recognize it as such all by themselves. Our blockchain model thus offers objectivity of consensus under the assumption that at least “some” of the accounts are honest, whereby the required percentage of honest accounts depends on the relation between their life expectancy and the heartbeat period. As the heartbeat period can theoretically be set arbitrarily low, the protocol can reach objectivity even in the presence of an extremely powerful attacker.