The math of Nxt forging

mthcl

March 14, 2014. Version 0.2.1

Abstract

We discuss the forging algorithm of Nxt from the probabilistic

point of view, and obtain explicit formulas and estimates for several
important quantities, such as the probability that an account gener-
ates a block, the length of the longest sequence of consecutive blocks
generated by one account, and the probability that one concurrent
blockchain wins over another one.

1

Forging algorithm

In this article we concentrate on the 1-block-per-minute regime, which is
not implemented yet. Assume that there are N forging accounts at a given
(discrete) time, B

1

, . . . , B

N

are the corresponding effective balances, and we

denote by

b

k

=

B

k

B

1

+ · · · + B

N

,

k = 1, . . . , N

the proportion of total forging power that the kth account has. Then, to
determine which account will generate the next block, we take i.i.d. random
variables with Uniform distribution on interval (0, 1), and the account which
maximizes b

k

/U

k

generates the block; i.e., the label k

0

of the generating

account is determined by

k

0

= arg max

j∈{1,...,N }

b

j

U

j

.

(1)

NXT: 5978778981551971141; author’s contact information: e.monetki@gmail.com,

or send a PM at bitcointalk.org or forums.nxtcrypto.org

1

We refer to the quantity b

k

/U

k

as the weight of the kth account, and to

b

k

0

/U

k

0

as the weight of the block. This procedure is called the main al-

gorithm (because it is actually implemented in Nxt at this time), or the
U-algorithm (because the inverse weights have Uniform distribution).

As a general rule, it is assumed that the probability that an account

generates a block is proportional to the effective balance, but, in fact, this is
only approximately true (as we shall see in Section 2). For comparison, we
consider also the following rule of choosing the generating account: instead
of (1), we use

k

0

= arg max

j∈{1,...,N }

b

j

| ln U

j

|

.

(2)

The corresponding algorithm is referred to as Exp-algorithm (since the inverse
weights now have Exponential probability distribution).

2

Probability of block generation

Observe that (see e.g.

Example 2a of Section 10.2.1 of [2]) the random

variable | ln U

j

|/b

j

has Exponential distribution with rate b

j

. Since, obviously,

for the Exp-algorithm we can rewrite (2) as

k

0

= arg min

j∈{1,...,N }

| ln U

j

|

b

j

,

the inverse weight of the generated block is also an Exponential random
variable with rate b

1

+ · · · + b

N

= 1 (cf. (5.6) of [3]), and the probability that

the kth account generates the block is exactly b

k

(this follows e.g. from (5.5)

of [3]).

However, for U-algorithm the calculation in the general case is not so

easy. We concentrate on the following situation, which seems to be critical
for accessing the security of the system: N is large, the accounts 2, . . . , N
belong to “poor honest guys” (so b

2

, . . . , b

N

are small), and the account 1

belongs to a “bad guy”, who is not necessarily poor (i.e., b := b

1

need not be

very small).

We first calculate the probability distribution of the biggest weight among

2

the good guys: for x

max

k≥2

b

k

let us write

P max

k≥2

b

k

U

k

< x =

k≥2

P U

k

>

b

k

x

=

k≥2

1 −

b

k

x

= exp

k≥2

ln 1 −

b

k

x

≈ e

1−b

x

,

(3)

since ln(1 − y) ∼ −y as y → 0 and b

2

+ . . . + b

N

= 1 − b. We calculate now the

probability f (b) that the bad guy generates the block, in the following way.
Let Y be a random variable with distribution (3) and independent of U

1

, and

we write (conditioning on U

1

)

f (b) := P

b

U

1

> Y

=

1

0

P Y <

b

z

dz

=

1

0

e

1−b

b

z

dz

=

b

1 − b

1 − e

1−b

b

.

(4)

It is elementary to show that f (b) > b for all b ∈ (0, 1) (see also Figure 1),
and (using the Taylor expansion) f (b) = b + b

2

+ O(b

3

) as b → 0.

Conclusions:

• If an account has proportion b of the total effective balance and the

forging powers of other accounts are relatively small, then the proba-
bility that it generates the next block is given by (4).

• With small b, this is approximately b + b

2

, i.e., the block generat-

ing probability is roughly proportional to the effective balance with a
quadratic correction.

• It is also straightforward to obtain that the probability that a good

guy k generates a block is b

k

(1 − f (b)), up to terms of smaller order.

3

Figure 1: The plot of f (b) (black curve)

4

3

Longest run

We consider a “static” situation here: there are no transactions (so that the
effective balances are equal to full balances and do not change over time).
The goal is to be able to find out, how many blocks in a row can be typically
generated by a given account over a long period n of time.

So, assume that the probability that an account generates the next block

is p (see in Section 2 an explanation about how p can be calculated). It is
enough to consider the following question: let R

n

be the maximal number of

consecutive 1’s in the sequence of n Bernoulli trials with success probability p;
what can be said about the properties of the random variable R

n

?

The probability distribution of R

n

has no tractable closed form, but is

nevertheless quite well studied, see e.g. [4] (this article is freely available in
the internet). The following results are taken from [1]: we have

ER

n

= log

1/p

qn +

γ

ln 1/p

1

2

+ r

1

(n) + ε

1

(n),

(5)

VarR

n

=

π

2

6 ln

2

1/p

+

1

12

+ r

2

(n) + ε

2

(n),

(6)

where q = 1 − p, γ ≈ 0.577 . . . is the Euler-Mascheroni constant, ε

1,2

(n) → 0

as n → ∞, and r

1,2

(n) are uniformly bounded in n and very small (so, in

practice, r

1,2

and ε

1,2

can be neglected).

In the same work, one can also find results on the distribution itself.

Let W

p

be a random variable with Gumbel-type distribution: for y ∈ R

P[W

p

≤ y] = exp(−p

y+1

).

Then, for x = 0, 1, 2, . . . it holds that

P[R

n

= x] ≈ P[x − log

1/p

qn < W

p

≤ x + 1 − log

1/p

qn],

(7)

with the error decreasing to 0 as n → ∞. So, in particular, one can obtain
that

P[R

n

≥ x] ≈ 1 − exp(−p

x+1

qn)

≈ p

x+1

qn

(8)

if p

x+1

qn is small (the last approximation follows from the Taylor expansion

for the exponent).

5

For example, consider the situation when one account has 10% of all

forging power, and the others are relatively small. Then, according to (4),
the probability that this account generates a block is p ≈ 0.111125. Take
n = 1000000, then, according to (5)–(7), we have

ER

n

≈ 6.00273,

VarR

n

≈ 0.424,

P[R

n

≥ 7] ≈ 0.009 .

Conclusions:

• The distribution of the longest run of blocks generated by one particular

account (or group of accounts) is easily accessible, even though there is
no exact closed form. Its expectation and variance are given by (5)–(6),
and the one-sided estimates are available using (8).

4

Weight of the blockchain and concurrent
blockchains

First, let us look at the distribution of the inverse weight of a block. In
the case of Exp-algorithm, everything is simple: as observed in Section 2, it
has the Exponential distribution with rate 1. This readily implies that the
expectation of the sum of inverse weights of n blocks equals n.

As for the U-algorithm, we begin by considering the situation when all

relative balances are small. Analogously to (3), being W the weight of the
block, for x

(max

k

b

k

)

−1

we calculate

P

1

W

> x = P max

k

b

k

U

k

<

1

x

=

k

P U

k

> xb

k

=

k

(1 − xb

k

)

= exp

k≥2

ln(1 − xb

k

)

≈ e

−x

,

(9)

6

so also in this case the distribution of the inverse weight is approximately
Exponential with rate 1.

We consider now the situation when all balances except the first one are

small, and b := b

1

need not be small. For the case of U-algorithm, similarly

to the above we obtain for x ∈ (0, 1/b)

P

1

W

> x ≈ (1 − bx)e

−(1−b)x

,

(10)

so

E

1

W

1/b

0

(1 − bx)e

−(1−b)x

dx

=

be

1−b

b

+ 1 − 2b

(1 − b)

2

.

(11)

One can observe (see Figure 2) that the right-hand side of (11) is strictly

between 1/2 and 1 for b ∈ (0, 1).

Let us consider now the following attack scenario: account 1 (the “bad

guy”, with balance b) temporarily disconnects from the network and forges
its own blockchain; he then reconnects hoping that his blockchain would be
“better” (i.e., has smaller sum of inverse weights). Then, while the account 1
is disconnected, the “good” part of the network produces blocks with inverse
weights having Exponential distribution with rate 1−b, and thus each inverse
weight has expected value

1

1−b

.

Let X

1

, X

2

, X

3

, . . . be the inverse weights of the blocks produced by the

“good part” of the network (after the bad guy disconnects), and we denote
by Y

1

, Y

2

, Y

3

, . . . the inverse weights of the blocks produced by the bad guy.

We are interested in controlling the probability of the following event (which
means that the blockchain produced by the bad guy is better)

H

m

= {X

1

+ · · · + X

m

− Y

1

− · · · − Y

m

≥ 0}

for “reasonably large” m (e.g., m = 10 or so). If the probability of H

m

is small, this means that the bad guy just does not have enough power to
attack the network; on the other hand, if this probability is not small, then
the system should be able to fence off the attack by other means, which we
shall not discuss in this note.

We obtain an upper bound on the probability of the event H

m

using the

so-called Chernoff theorem (see e.g. Proposition 5.2 of Chapter 8 of [2]): we

7

Figure 2: Expectation of the inverse weight (as a function of b)

8

have

P[H

m

] ≤ δ

m

,

where

δ = inf

t>0

Ee

t(X

1

−Y

1

)

.

(12)

It is important to observe that this bound is nontrivial (i.e., δ < 1) only in
the case EX

1

< EY

1

.

For U-algorithm, X

1

is Exponentially distributed with rate 1 − b, and Y

1

has Uniform(0, b

−1

) distribution. So, the condition EX

1

< EY

1

is equivalent

to (1 − b)

−1

< (2b)

−1

, that is, b < 1/3. Then, for b < 1/3, the parameter δ

from (12) is determined by

δ = δ(b) = b(1 − b)

inf

0

1 − e

−t/b

t(1 − b − t)

(13)

(see the plot of δ(b) on Figure 3), so we have

P[H

m

] ≤ δ(b)

m

.

(14)

For example, for b = 0.1 we have δ(b) ≈ 0.439. We have, however, δ(b) ≈
0.991 for b = 0.3, which means that means that one has to take very large m
in order to make the right-hand side of (14) small in this case.

For the Exp-algorithm, the bad guy would produce blocks with inverse

weights having Exponential distribution with rate b, so each inverse weight
has expected value

1

b

. Similarly to the above, one obtains that the condition

EX

1

< EY

1

is equivalent to b < 1/2, and

P[H

m

] ≤ (4b(1 − b))

m

(15)

(that is, δ can be explicitly calculated in this case and equals 4b(1 − b);
observe that 4b(1 − b) < 1 for b < 1/2).

Conclusions:

• We analyse an attack strategy when one account (or a group of ac-

counts) temporarily disconnects from the main network and tries to
forge a “better” blockchain than the one forged by other accounts, in
the situation when one bad rich guy has proportion b of total amount
of NXT, and the stakes of the others are relatively small.

9

Figure 3: The plot of δ(b)

10