Ethereum : About “A simple calculus theorem with implications to 51% attack analysis”

Ethereum update: About “A simple calculus theorem with implications to 51% attack analysis”

After reading Vitalik’s [post]( on how transactions cannot be censored for more than one cycle for <50% attackers, I was trying to come up with a discrete rather than integration-based proof. I’ll post the high-level argument here and would appreciate feedback (apologies in advance for any errors, I’m still trying to find my way around Casper research).

So we have a circular list of validators *z_1*, …, *z_n*. The list is *circular* because after *z_n* comes *z_1* again. For any given validator *i*, let *z_i* = 1 if the validator is honest; otherwise, if validator *i* is dishonest, let *z_i* = -1. We assume that there are more honest than dishonest validators, i.e. sum_{i=1}^(n) *z_i* > 0. The idea is to prove the following: There is at least one validator (let’s call it validator *k*) for which, if we take any sequence of validators starting with *k*, then the number of honest validators in that sequence will always be greater than the number of dishonest validators (am I correct here?)

So here is the argument: Given the full sequence of validators *z_1*, …, *z_n*, pick the longest subsequence that minimizes the corresponding validator sum. For instance, for validators (1, -1, -1, -1, 1, 1, 1), this subsequence would be (2–>4). Let’s call the *first* element of this sum-minimizing subsequence *j*, and the last element *k – 1*.

Now, we know that validator *k* is honest. If it were dishonest, then we could append it to our subsequence in order to make a larger one (by definition, we already started with the largest subsequence). In fact, we know that sum_{i=k}^(n) *z_i* is positive, because of that same reason. Using the same argument, we also know that validator j – 1 is honest. In fact, the sequence z_1, …, z_{j-1} has an honest majority.

What the above means is that if we take a sequence starting with validator *k*, we can go all the way up to validator *n* and have an honest majority. Then, we can wrap around the validator list and append the sequence *z_1*, …, *z_{j-1}* and still have an honest majority.

Notice that, using the above construction, the only validators that we haven’t yet included in our positive-sum sequence that starts with *k* are the validators included in the sum-minimizing sequence *z_j*, …, *z_{k-1}*. Since the overall sum across all validators is positive, we know that if we add validators from the sum-minimizing sequence, we will still have a positive sum. This concludes the argument.

This seems to me just a kind of “discrete restatement” of what Vitalik already mentioned, but I would like to confirm if the above is error-free as a way of making myself more familiar with Casper. Thanks in advance!

EDIT: Markdown.

View the link

About Ethereum

Ethereum is a decentralized platform that runs smart contracts: applications that run exactly as programmed without any possibility of downtime, censorship, fraud or third-party interference.

Author: jcaldas1984

Score: 5

Don’t forget to share the post if you love it !

Blockchain : JiBbit in A Blockchain

CryptoCurrency : The Market Cycle. Anyone who read/understood this pattern sold in January.