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.

The Approach

Let’s start with the simplest approach. We will assume the adversary has a good media channel to reach out to many participants of the protocol, and also for simplicity assume the stake of each participant is equal and is exactly 32 tokens (the constant Ethereum 2.0 uses).

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

Unless some smart Algorand-style way of assigning validators is used, the public keys of the validators are known in advance. The adversary can create a smart contract in a chain that is different from the one they are trying to corrupt (without loss of generality, let’s say the chain being corrupted is NEAR, and the chain the smart contract is published on is Ethereum). In its simplest form, the smart contract includes all the public keys of the validators that will be assigned to the shard to be compromised at the time the adversary wants to attack it, and the smart contract would immediately send 40 tokens to any user who submits a private key that matches any of the public keys in the contract.

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

The approach above makes two major assumptions: that there exists a media channel that can reach out to a large percentage of the validators, and that many validators are easily corruptible. While both assumptions are somewhat strong, neither is completely unreasonable.

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 will be travelling to Prague for the DevCon4 next week. Many founders and engineers from recognized sharded blockchain projects such as Cosmos, Ethereum and PolkaDot will be there. The primary purpose of my trip will be to figure out what is their thinking on the adaptive and bribing adversaries and defending against them in the sharded blockchains. Any good insights I accumulate will be posted in our blog.

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:

• NEAR Twitter — https://twitter.com/nearprotocol,
• Discord — https://discord.gg/kRY6AFp, we have open conversations on tech, governance, and economics of blockchain on our discord.

https://upscri.be/633436/