Tendermint 2019 — Criticize by Creation, Not by Finding Fault
Intro
I wanted this piece to be everything that you’ve read on Tendermint is not. This is not a Hitchhiker’s Guide to Tendermint, we have Blockgeeks for that. This is not a pump and dump signal, we have Reddit for that. This is not a shameless plug, we have Twitter for that. What this piece is, is me revisiting what I fell in love with, learning about its growth and development, and finally having a heart-to-heart discussion with it. Someone is going to call this an indirect form of self-boasting. But in this world where we get ruined by praise and saved by criticism, I’d say I’m just pointing out the flaws behind the virtues. Now if you’ve made thus far and are interested in proceeding, I’d like to invite you to come take this walk with me.
In the following sections, I will be talking from my personal perspective about some of the open questions that are left to explore in the Tendermint consensus engine. Any and all criticisms are welcome.
Committee Reconfigurability
Tendermint is a modernized, classical BFT consensus engine where the protocol solely relies on counting sufficiently many votes to make progress. This means the consensus protocol could get stuck if less than a threshold of votes are received (i.e. >2/3n). In other words, the protocol needs to be parameterized with an a-priori fixed number of committee members (i.e. validators) that must show up to vote. This is generally not a major concern since consistency and liveness are guaranteed as long as the majority of online instances are honest. Though as the scale of the system grows to where instances join the network at irregular and scattered intervals, anticipating the number of instances that will be online participating in consensus at any given time becomes exceedingly difficult.
A challenge we see in Tendermint today is the lack of reconfigurability of its consensus committee (i.e. validator set). As stake switches hands in the system, the consensus committee should be kept up-to-date in tracking the latest stake distribution. Committee reconfiguration typically goes hand in hand with the randomness of the protocol’s block proposer selection mechanism. Note that the current implementation of Tendermint selects leaders (i.e. block proposers) deterministically in a Round-Robin fashion. This opens up the possibilities for attackers to predict the next block proposer and carry out targeted Denial-of-Service (DoS) attacks. Introducing randomness to Tendermint is being actively worked on by several different projects, most notably Randomized Leader Election Using VRF by CodeChain and A Tendermint Variant with Built-In Random Beacon by Corestar. These projects aim to obtain randomness in Tendermint while providing security guarantee even when the random source has an adversarial bias.
A well-designed random leader selection mechanism addresses the challenge of Randomness-Biasing attacks (e.g. Grinding Attacks), but does not necessarily protect against adaptive security attacks such as Adaptive Chosen-Key attacks and Nothing-at-Stake attacks. For instance, assuming a randomized variant of Tendermint where 1) the random oracle is chosen before network start; and 2) all nodes participating in consensus know each other’s public keys, malicious actors can freely and adaptively choose public keys to achieve a higher chance of being elected as block proposer by:
- Embed arbitrary seeds in the blocks they contribute to in order to influence the nonce that’s used to seed the hash function
- Make arbitrary queries to the random oracle so that they can gather information about which honest nodes are elected in which time steps
- Set up malicious nodes and seed them with the chosen public keys so that whenever an honest node is elected, one of their malicious node is too
Unless each nonce is used to elect sufficiently many leaders, attackers can sustain such attacks by continuously putting up corrupt nodes and ultimately break the protocol’s consistency with constant probability (i.e. X malicious nodes break the consistency of X blocks).
Unlike epoch-based consensus protocols such as Snow White[1] where committee reconfiguration is performed each epoch in a separate phase from that of the random seed, a randomized variant of Tendermint without committee reconfiguration is more prone to adaptive security attacks due to the lack of an application-specific mechanism that examines an extracted state from a node’s local chain, and outputs a new committee over time. Though some might argue that not performing committee reconfiguration could be a worthy trade-off as it decreases the possibility of stake distribution lagging behind committee election.
(un)Fair Reward Mechanism
Unlike a Proof-of-Work blockchain in which a block is created by only one instance and that instance gets all the rewards of that block, in Tendermint a block is created by a subset of the instances in the entire system, namely the validators. To enforce incentive compatibility all honest validators that contribute to a given block should be rewarded for that block. Here we define fairness in a blockchain protocol as the following:
A blockchain protocol is fair if any correct process that wield φ fraction of the total merit in the system will get more or less φ fraction of the total reward that is given in the system. [2]
Assume in Tendermint’s current implementation, validator v_i is a contributor for height H-1 and validator v_jis the proposer for current height H. v_j proposes a block and includes the set of validators where he delivered a commit message from for height H in a variable calledto_reward. It is possible that before proposing his block v_j did not receive a commit message from v_i due to network asynchrony (e.g. message delay). Finally when the block for height H is finalized, all validators wait a time period of timeout_commit for other validators to send in their decisions, and then include in their to_reward the validators v_j proposed in his to_reward. Note that as timeout_commit in Tendermint does not currently increment each round, consensus instances that fail to deliver all their commits for the previous round will not be able to catch up to message delay. In addition, commit messages in Tendermint do not keep track of consensus participation in the network for each time step. This could allow for malicious actors to skip on Propose and/or Prevote and send only a Precommit as long as he has knowledge of the block being produced. As a result, because in the to_reward v_j proposed it didn't include v_i's commit message for H-1, v_i lost his reward for height H-1 despite being a contributor for that block. A proposed solution by Amoussou-Guenou, Pozzo, Potop-Butucaru & Tucci-Piergiovanni to improving the fairness in Tendermint's reward mechanism can be found here.
Interest Compounding
The “rich get richer”, or “wealth compounding” problem has been a major concern for Proof-of-Stake systems for as long as the idea has been around. By default wealthier nodes get elected more as block proposers and hence get more block rewards, making them even richer in the long run. This ultimately leads to poor decentralization. In recent years we have seen various attempts on combating the “stake centralization” problem, notably the Effective Proof-of-Stake by Harmony and Galaxy Consensus by Wanchain. The specific implementations vary from project to project, but the general theme usually falls in one of the followings:
- Randomize leader selection in consensus leveraging binomial distribution or the alike
- Regulate return/stake ratio with an equalizer
- A combination of both
Stake centralization in PoS can be challenging and subtle due to the fact that existing methods of distributing block rewards tend to solely focus on how adequately any given validator is compensated for their contribution and neglect how a validator is rewarded comparing to his peers. Informally, making sure validators are properly rewarded for their contribution is not adequate enough to ensure eventual fairness in the protocol; the variance of stake distribution also plays a big part in that. Though it could be argued that “rich get richer” is not less of a problem in PoW than in PoS considering mining pool centralization, interest compounding does not emerge in PoW. Assume a mining pool Cypher Core contributing 1/3 of the total hash power in a PoW system at the initialization of network start, after indefinitely many blocks the network would see a stake distribution concentrated at around 1/3 of the total hash power, with Cypher Core getting 1/3 of the total rewards. On the other hand, under the same parameters an equivalent staking pool in a PoS system such as Tendermint would have a much higher chance of reaping rewards as the staking pool’s fractional stake ratio approaches 0 and 1. In other words, in PoS systems the probability m% of a staking party with large initial fractional stake ratio n% being rewarded is larger than the party's initial fractional stake ratio (i.e. m% > n%), rather than equal as in PoW.
Tendermint implements a Constant Block Reward model [3] (i.e. value measured in tokens) for compensating consensus nodes’ cost of proposing blocks. This model follows the principle that “On short timescales, each block should yield the same block reward”[3]. Specifically, in Tendermint a staking party contributing 20% of the total stake pool at network start will on average get 20% of the total rewards in the long run. Formally by the Law of Total Expectation, a staking party’s expected reward earning is equal to his initial fractional stake ratio. Assume a closed Tendermint-powered system where the stakes only change due to block rewards and interest compounding, as the total rewards R to be dispensed over time period T do not grow proportionally to the overall stake pool the effect of a single block reward does not remain bounded during T. The variance of stake distribution in such systems decays with T, and rises if R is increased even mildly faster than T (i.e. more aggressive rewards per time slot). Mathematically variance of stake distribution under a Constant Block Reward model can be described as monotonically non-decreasing in R and non-increasing in T. Informally, we can say that the current reward model Tendermint employs is dependent on a staking party's initial stake, and is not universally fair for all parties in the system. If you are interested in learning about methods on improving variance of stake distribution in PoS systems through a maximally-equatable reward function, check out the paper here.
Outro
Thank you for making it to the end and I hope that was at least informative for you. Let me know what you disagree with, or if you spot any factual errors. Last but not least, as the year end is approaching, I wish you peace, joy, and all the best this wonderful holiday has to offer. May this incredible time of giving and spending time with family bring you the joy that lasts throughout the year.
References
[1] Daian, P., Pass, R., & Shi, E. (2019). Snow White: Robustly Reconfigurable Consensus and Applications to Provably Secure Proof of Stake [PDF].
[2] Amoussou-Guenou, Y., Del Pozzo, A., Potop-Butucaru, M., & Tucci-Piergiovanni, S. (2019). Correctness and Fairness of Tendermint-core Blockchains [PDF] (3rd ed.). Retrieved from https://arxiv.org/pdf/1805.08429.pdf
[3] Fanti G., Kogan L., Oh S., Ruan K., Viswanath P., Wang G. (2018). Compounding of Wealth in Proof-of-Stake Cryptocurrencies [PDF] (2nd ed.) Retrieved from https://arxiv.org/pdf/1809.07468.pdf
