P
α,rate
best
stat
(C,B):
parse B →(τ,m,d)
if |C
m
| > F
−1
(1 −α,dτ(rate
best
)):
output reject
else
output accept
Figure 2: P
α
stat
. F
−1
(·,λ ) is the quantile function for Poisson
distribution with rate λ.
4.2 The REM policy: P
stat
REM makes use of a statistical-testing-based policy that
we denote by P
stat
. P
stat
is compatible not just with
PoUW, but also with PoET and potentially other SGX-
based mining variants.
There are two parts to P
stat
. First, P
stat
estimates the
rate of the fastest honest miner(s) (fastest CPU type), de-
noted by rate
best
= max
m∈M−M
A
rate(m). There are var-
ious ways to accomplish this; a simple one would be to
have an authority (e.g., Intel) publish specs on its fastest
CPUs’ performance. (In PoET, mining times are uni-
form, so rate
best
is just a system parameter.) We describe
an empirical approach to estimating rate
best
in REM in
Appendix A.1.
Given an estimate of rate
best
, P
stat
tests submitted
blocks statistically to determine whether a miner is min-
ing blocks too quickly and may thus be compromised.
The basic principle is simple: On receiving a block B
from miner m, P
stat
tests the null hypothesis
H
0
= {rate(m) ≤ rate
best
}.
We use |C
m
(τ)|, the number of blocks mined by m at
time τ, as the test statistic. Under H
0
, |C
m
| should obey
a Poisson distribution with rate dτ(rate
best
), denoted as
Pois[dτ(rate
best
)]. P
stat
rejects H
0
if |C
m
| is greater than
the (1−α)-quantile of the Poisson distribution. The false
rejection rate for a single test is therefore at most α. We
specify P
stat
(for a given rate
best
) in Figure 2.
An important property that differentiates P
stat
from
canonical statistical tests is that P
stat
repeatedly applies
a given statistical test to an accumulating history of sam-
ples. The statistical dependency between samples makes
the analysis non-trivial, as we shall show.
4.3 Analysis of P
stat
We now analyze the average-case and worst-case waste
and adversarial advantage of P
stat
. We assume for sim-
plicity that rate
best
is accurately estimated. We remove
this assumption in the worst-case analysis below. We
also assume that the difficulty d(t) is stationary over the
period of observation.
Waste Under P
stat
, a miner generates blocks accord-
ing to a Poisson process; whether a block is accepted
or rejected depends on whether the miner has gener-
ated more blocks than a time-dependent threshold. This
process is obviously not memoryless and thus not di-
rectly representable as a Markov process. We can, how-
ever, achieve a close approximation using a discrete-time
Markov chain. Indeed, as we show, we can represent
waste in P
stat
using a discrete-time Markov chain that is
periodically identical to the process it models, meaning
that its expected waste is identical at any time nτ, for
n ∈ Z
+
and τ a model parameter specified below. This
Markov chain has a stationary distribution that yields
an expression upper-bounding waste in P
stat
. (We be-
lieve, and the periodic identical property suggests, that
this bound is very tight.)
To construct the Markov Chain, we partition time into
intervals of length τ; we regard each such interval as a
discrete timestep. Assuming that all honest miners mine
at rate rate, let λ = dτ(rate). Thus an honest miner gen-
erates an expected Pois[λ ] blocks in a given timestep i,
which we may represent as a random variable Y
i
. With-
out loss of generality, we may set τ = 1/(d ×rate) and
thus λ = 1 and E[Pois[λ ]] = 1.
We represent the state of an honest miner at timestep n
by a random variable X
n
=
∑
n
i=1
(Y
i
−E[Y
i
]) = (
∑
n
i=1
Y
i
)−
n. Thus X
n
∈ Z is simply difference between the miner’s
actually mined blocks and the expected number.
Our Markov chain consists of a set of states C = Z
representing possible values of X
n
(we use the notation C
here, as states represent |C
m
|for an honest miner m). Fig-
ure 3 gives a simple example of such a chain (truncated
to only four states).
Our statistical testing regime may be viewed as reject-
ing blocks when a transition is made to a state whose
value is above a certain threshold thresh. We denote the
set of such states C
rej
= {j | j ≥ thresh} ∈ C and depict
corresponding nodes visually in our example in Figure 3
as red. P
stat
sets thresh according to the statistical-testing
regime we describe above and a desired false-rejection
(Type-I) parameter α. Specifically,
C
rej
[α] = {j ∈ Z | j ≥F
−1
(1 −α,τ ×rate)}. (1)
The transition probabilities in our Markov chain are:
P[i → j |i ∈C \C
rej
[α]] =
P( j −i + 1) if j ≥ i −1
0 otherwise
(2)
P[i → j |i ∈C
rej
[α]] =
P( j + 1) if j ≤ −1
0 otherwise.
(3)
An example of transitions is given in Figure 3. For
instance, from state −1, the next state can be −2 if the
7