Security Analysis Of Validator Subset Approach

In Electron Protocol, while verifying a blockheader using a Light Client, we postulate that instead of verifying 1000’s signatures from all validators, we can verify signatures from a subset of all validators containing just 19 validators, provided that the 19 validator subset is selected randomly.

Standard Setup — Verify all signatures. ⅔ should be valid.

Probabilistic Setup — Verify only 19 signatures. All should be valid.

Let us now show that both cases — standard setup and probabilistic setup, provide almost the same level of security. Let's dive in.

Consider that a blockchain has a total of N validators (we have tested our model for N between 100 and 1 Million). As assumed by most blockchains, we also assume that a max of N/3 validators could be malicious. As a worst-case scenario, we assume that all these N/3 malicious validators are colluding together to attack Electron Protocol.

In the standard setup, all validators’ signatures would be verified, and since we know that no more than N/3 are malicious, we know that at least two-thirds of total validators have signed correctly and that we can trust this block. This is the security provided by the blockchain itself.

Now, in the probabilistic setup, we are going to verify all signatures from x (x=19) randomly selected validators. As a source of randomness, we use the hash of some block (it could be previous block or current or some combination). We know that the crypto community at large believes that the hash of blocks is not a good source of randomness, since the hash can be manipulated, however, we shall show in a separate article that in our case (and in our case only), hash of block provides very good security. For the scope of this article, let us assume that hash of block is a good source of randomness.

So now, using the hash of block as randomness, we can calculate a random subset of x validators from the entire N validator set. Now, for Electron Protocol to be hacked, x must contain only malicious nodes. Even if one honest node is included in x, this honest node’s signature will not agree with the signatures from other x-1 validators, and the attack will be detected.

We can now state this as a maths problem:-

We must calculate the probability that when the x subset is calculated, the probability that all x are from the malicious N/3 validators show be very low. OR the probability that at least one honest validator (from ⅔ * N) is selected in the x subset should be very high.

We can restate this in simpler terms, removing all references to blockchain-specific things and reducing the above statement to the high school probability question. Here it goes:-

Consider a total of N balls. Out of this, N/3 balls are red, while the remaining ⅔ * N balls are blue. If you draw x balls at random, what is the probability that all x balls are red?

Solution:-

If all balls are drawn together:-

Probability that a given drawn ball is red = ⅓

Probability that all x drawn balls are red = ⅓ * ⅓ … x times = (⅓ )^x

For the network to be secure, the following condition must be met:-

i.e. there is less than 1 in a billion chance that all validators selected in the subset are malicious.

If balls are drawn one by one:-

Probability that 1st ball is red = ⅓

Probability that 2nd ball is red = (N/3–1)/(N-1)

Probability that 3rd ball is red = (N/3–2)/(N-2)

…

Probability that xth ball is red = (N/3 — (x-1))/(N — (x-1))

Multiple all these terms together, we can write:-

Now, for the network to be secure, the following condition must be met:-

For large enough values of N, say 1000, this equation becomes the same as the case when all balls are drawn together.

The smallest integer value of x that satisfies the above two equations is 19.

Now someone might argue that 1 in a billion is not secure enough, they might ask for 1 in a trillion. We can easily do that. If you see these equations, the probability of hack diminishes exponentially with the value of x. So, by increasing x in small amounts, we can increase security by large amounts. So if I make x = 26, the probability of hack falls well below 1 in a trillion.

Ending Note:-

Electron Labs is building an interoperability protocol to make cross-chain products possible. Our goal is to enable the developer to think in blockchain agnostic terms. We are hiring!

Website :- https://electronlabs.org/

Github :- https://github.com/Atom-Labs-one

Discord :- https://discord.gg/WWuCPw8QEB

Telegram :- https://t.me/joinchat/XUknutKGjyhiZTA9

Twitter :- https://twitter.com/labs_electron