How Unrealistic is Bribing Frequently Rotated Validators?

Alexander Skidanov
Oct 24, 2018 · 5 min read

View this post on the NEAR blog at https://nearprotocol.com/blog/how-unrealistic-is-bribing-frequently-rotated-validators/

Many proposed blockchain protocols today use some sorts of committees to propose and validate blocks. The committees are at the core of the Delegated Proof of Stake, and no sharding protocol is feasible without only a subset of nodes operating each shard.

Majority of the DPoS based protocols go as far as to claim that once the block is finalized by the committee, it is irreversible.

When analyzing the security of such committees it is often assumed that all the participants in the entire population can be separated into honest and malicious in advance, and those honest participants will remain honest after they become validators. For example, such an assumption is at the core of security analysis in the latest MultiVAC sharding yellowpaper.

In Ethereum Sharding FAQ multiple security models are analyzed, including a Bribing Attacker model. In this model, an attacker has a budget which it can use to arbitrarily corrupt validators in the network. According to the FAQ, some people claim the model is unrealistically adversarial.

In this short write-up, I will do some analysis on how unrealistically adversarial the bribing attacker model is, as well as how easy this model allows an adversary to corrupt a shard. Let’s consider such an adversary, with a budget proportional to the stakes in a single shard (which in a system with hundreds of shards is less than a percent of the total stake) that wants to compromise one shard and see how they go about it.

If you are an entrepreneur in web3 space, consider joining our accelerator with mentors from tier1 companies and investment firms in the space: http://openwebcollective.com/. We help with all the aspects of building the business, including identifying the market, BD, marketing and fundraising.

The Approach

The adversary then uses the media channel to advertise that they would pay 40 tokens in 15 minutes for any private key of any validator that will be at that time assigned to shard #7. For as long a validator trusts the adversary to actually pay the promised 40 tokens, it makes a lot of sense for them to take advantage of the offer. The assumption of trust, however, is rather strong.

Reducing Trust

While this makes the transaction involve no trust, it has a drawback that the private key will become known to everybody in the system, not just the attacker.

To get around it, we can improve the smart contract. The adversary now publishes their own public key pka, and any participant that wants to submit their private key for 40 tokens encrypts their private key with pka before submission. The contract then enters a 15-minute challenge period during which the adversary can submit their own private key ska to decrypt the message submitted by the participant and show that it is not encrypting a valid private key of a validator. If no challenge is submitted within 15 minutes, 40 tokens are released.

This way the private key of the validator is only known to the validator and the adversary, and the validator is guaranteed to get their 40 tokens. At this moment no reasonable validator that has no stake in the platform besides the 32 tokens they staked will miss on the opportunity to effectively get 8 tokens for free.

Footnote: A few further improvements are possible that would reduce spam, such as the adversary posting some message a validator needs to encrypt with their private key so that the smart contract can verify the validator has it, or validators staking some tokens that are released back to them unless the adversary challenges their submission.

Further Analysis

It is also worth noting that once a validator submits a private key to the adversary, the validator themselves still has access to the key. At this point, they can use it to exercise some malicious slashable behavior that somehow benefits them (since their stake at this point is doomed to be slashed no matter what, and the payment for the private key was already received). While a valid argument, it is worth pointing out that if the adversary’s goal is to compromise the shard, then a large set of validators simultaneously acting maliciously is not really against their interests.

Another important observation is that by advertising the exact time and shard that will be attacked, the adversary attracts significant attention to that shard at that time, so whatever malicious intent they plan to exercise will be immediately slashed with a proper system design, possibly before any benefit from such intent can be realized.

Outro

I write on different topics related to building distributed blockchains, and work full time on building NEAR Protocol, a decentralized distributed applications platform. If you are interested in what we build and write, follow our progress:

Lastly, please subscribe to our newsletter.

NEAR Protocol

NEAR is a fully scalable, developer-friendly blockchain

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store