Tenderstake: A ByRa SMR protocol

Conor McMenamin
4 min readJun 3, 2021

--

This post is a follow-up to a previous post where I continue to advocate for an immediate move towards game-theoretic security standards in cryptocurrencies. I outline the ByRa (Byzantine or Rational) model for player characterisation, and describe Tenderstake, an amendment to the Tendermint protocol, which achieves SMR in the ByRa model.

We provide Tenderstake, not only as a critical amendment to Tendermint, but as a template for the crucial work needed to ensure blockchains, and SMR protocols in general, achieve SMR when players are no longer honest-by-default. Photo by José Ignacio Pompé on Unsplash

Providing protocols which achieve ByRa SMR is of utmost importance. The cryptocurrency landscape has shifted dramatically from the warm fuzzy days of an honest majority, to Dark Forests where the majority of participants in cryptocurrency protocols are of a fickle, get-rich-quick nature, maximising immediate profits with no consideration for the longevity of protocols. This is in stark contrast to the idealistic nature of the legacy standards on which almost all cryptocurrencies are built.

Current cryptocurrencies are developed to only be secure when some players, often a majority/trusted third party, always act honestly. This is terrifying, and needs to change.

Note: If you weren’t terrified by that sentence, read it again.

In my previous post I address this shortcoming, outlining a new framework for protocols to achieve SMR in the ByRa (Byzantine/adversarial or Rational) player model, and provide a template protocol in FAIRSICAL for achieving ByRa SMR. Although there was positive feedback to our previous work, there was a glaring question which limited its credibility. Namely:

Can ByRa SMR be achieved outside of sandbox protocols like FAIRSICAL? In this post, I answer this question in the affirmative.

In a recent paper with my co-authors Vanesa Daza and Matteo Pontecorvi, we outline the Tenderstake protocol, an amendment to the popular Tendermint protocol as used in the COSMOS network, and formally prove that under the same network conditions, partial synchrony, Tenderstake achieves ByRa SMR. Given FAIRSICAL was, to the best of our knowledge, the first protocol to achieve ByRa SMR under any network conditions, Tenderstake stands as the first protocol which achieves ByRa SMR under real-world network conditions.

Before outlining the Tenderstake protocol, let’s recap what it means to achieve ByRa SMR. Consider a BFT-style SMR protocol, Π, where player voting power is in direct proportion to their share of stake within Π. Furthermore, let’s assume Π achieves SMR when players controlling any share greater than 1-α of the total stake follow the recommended Π protocol.

Achieving ByRa SMR

An SMR protocol Π achieves ByRa SMR if rational players always follow the recommended Π protocol, and for any starting adversarial share less than α (as defined above), adversarial share is bounded by the starting adversarial share.

Importantly, within this definition of ByRa SMR, we have the two necessary and sufficient properties of strong incentive compatibility in expectation (SINCE) and fairness (introduced in the previous post) for achieving ByRa SMR.

SINCE ensures that a rational player always believes that following the recommended protocol strictly maximises their utility (payoff). Fairness ensures that for any adversary with starting share less than α, there is no adversarial strategy that can increase that share. The sufficient and necessary nature of these two properties for achieving ByRa SMR is formally proved in our paper.

Tenderstake

The Tenderstake protocol is constructed in a similar vein to Tendermint, with two key additions, proof-of-transition and slashing functionalities. In Tenderstake, players must provide proofs that for every message sent, it was generated by following some protocol step, which is possible for every step in the protocol.

A high-level view of the Tenderstake state diagram.

All players in the system are then capable of providing a proof-of-deviation if any protocol rule is broken, such as invalid proofs-of-transition, invalid proposed values, conflicting messages at the same protocol step, as well as invalid proofs-of-deviation. Players collect proofs-of-deviation, and as per the protocol, add them to proposed values when they are elected as proposer. To ensure SINCE, there is a positive reward for identifying deviators, and a large punishment for being identified as deviating. Deciding on values results in rewards distributed to all players in direct proportion to their share.

In the paper we provide a full formal proof of SINCE, but provide a sketch here:

  • Through the slashing functionality, we are able to prove rational players do not send invalid messages.
  • As there is a positive reward for deciding on values, and messages are delivered arbitrarily in the partially synchronous network, the rate of rewards is increased by sending valid messages when possible.
  • There is also a necessity to prove players follow increasing, unbounded timeouts when decisions are not being made, similarly to the Tendermint protocol. The proof is a little tedious, but the intuition is that after sufficiently many rounds of not deciding on a value, the only variable preventing decisions given all other protocol rules are being followed is a timeout which is too small, thus incentivising an increasing, unbounded timeout.

As rewards in Tenderstake are paid in direct proportion to share, and no rational player will deviate from the protocol (and thus no rational player will be slashed), rational share of stake is lower bounded by its starting share, which upper bounds adversarially share by it starting share. This is precisely the definition of fairness.

By proving Tenderstake is SINCE and fair, by the sufficient nature of these two properties for ByRa SMR, we are able to state Tenderstake achieves ByRa SMR.

Any readers interested in the full protocol/proofs should consult the paper, or leave a comment below! I’d love to hear your feedback.

This article is part of a project that has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement number 814284

--

--

Conor McMenamin

PhD student in Formal Analysis of Blockchain Technology.