Just an update on my recent calculations.
I'm assuming that the algorithm currently used may be roughly approximated by the following model. Let
gi be the balance of
ith account expressed in billions of NXT (so the sum of all balances equals 1). To decide who will generate the next block, take i.i.d. Uniform[0,1] random variables
U1,...,Un (
n is the total number of accounts; I'm assuming also that they are all forging), and calculate
Wi=gi/Ui. The account for which
W. is maximized, will forge, and the corresponding weight is called the weight of the block.
As noted before, this approach slightly favors bigger accounts; in order to make the forging power exactly (up to computational errors) proportional to the balance, one must use
Wi=gi/|ln Ui| instead. CfB told me that BCNext preferred not to use logs in order to discourage splitting of big accounts (what for - anybody knows?). Anyhow, if all
gi s are small (compared to total amount), then the two approaches are almost indistinguishable, and it's easy to justify it mathematically (will do it in the paper).
In the case of concurrent blockchains, wins the one for which the sum of inverse weights is minimal. (Currently wins the longest one, but these two approaches are, in fact, equivalent.)
Now, we consider the following situation: one big bad guy has
b billions-of-NXT, and the others are poor, honest, and many. The bad guy (with his minions) "accidentally" disconnects from the network, and secretly forges a branch of length
m. Let us consider the (future) situation with one-block-per-minute, and estimate the probability that this "bad" branch wins over the "good" one.
In the "ideal" situation (when the forging power is exactly proportional to the balance, the above approach with logarithms), the probability of this event will be of order
(4b(1-b))m for
b<0.5.
Observe that
4b(1-b)<1 for
b<0.5, so the probability decreases rather fast.
On the other hand, with the current setup (when one divides by uniform r.v. instead of dividing by
log of it), this probability only tends to 0 for
b<1/3 (I'll write the formula in the paper, since it's much more complicated). The reason for this is easy to explain: the inverse weight produced by good guys has Exponential(
1-b) distribution, and so its expectation is
1/(1-b). Now, the inverse weight produced by the bad guy has Uniform[
0,1/b] distribution, with expectation
1/(2b). Solving
1/(1-b)<1/(2b), we arrive to
b<1/3.
Now, I'm not sure if there is a
mathematical solution about how to fence off an attack of someone with
b>1/3 (or
b>0.5 in the other setting)...
In the next couple of weeks I'll go to a conference in Ulm and then receive an important visitor, so, most probably, I won't be able to read this thread in full (though, of course, I'll check PMs and read Damelon's summaries). Sure, I promise to type all these calculations in an organized way (style of modern math paper; will try to speed it up). Please, discuss it at
https://forums.nxtcrypto.org/, this topic:
https://forums.nxtcrypto.org/viewtopic.php?f=17&t=836
Show Posts
) are welcome! 
