Quote from: Daedelus on April 06, 2015, 10:42:00 PM

Vitalik may have just done the proof you were looking for for Nxt...

Thanks for the info and I applaud efforts like this to formalize the consensus problem. My take on what Vitalik has done is that he's defined a term "crypto-economically secure entropy source" and then provided what he claims is a proof that the Nxt algorithm¹ satisfies this. But note that even if the proof is correct, and even if the definition of "crypto-economically secure entropy source" is useful, it is still a far cry from convincingly showing that "Nxt is as secure as Bitcoin."

Let's take a closer look: Vitalik specifies that a "crypto-economically secure entropy source" should posses (a) unpredictability and (b) uninfluenceability. In plain words, his definition of "unpredictability" just means that, given enough time, the "state" of the currency system at some finite time in the future cannot be determined with information available in the present moment. Regardless of whether the system became fully unpredictable 10 minutes or 100 years in the future, his condition would be satisfied. Also note that his proof is only valid in the case where p0(60) is non zero, which is not true at least in the trivial case where an attacker is in control of 100% of the active accounts.

His definition for uninfluenceability (I) just says that there's a minimum cost for an attacker to influence the probability of some blockchain event. Even if the cost is very small, and even if the event he's influencing is very significant, his definition would still be satisfied.

His definition for uninfluenceability (II) is confusing to me. He says that an attacker controlling k of the stake should be unable to change the probability of some event to more than p' = p*(1+b) for some constant b. But there's always a constant value of b that would make p' = 100%. Perhaps I'm misinterpretting something, but if an attacker controlled 0.1% of the stake and could influence the outcome 100% of the time, his definition of uninfluenceability would still be satisfied [although such as system would be very influenceable].

Anyways, I'm not trying to be critical of Vitalik's efforts, I'm just pointing out that the results applied to Nxt may not be very significant in terms of Nxt's actual security properties.

¹Neglecting the algorithm for how nodes that were previously offline determine the best blockchain out of many valid candidate blockchains upon rejoining the network.