The Chia Network Blockchain

Bram Cohen1 and Krzysztof Pietrzak2

1
Chia Network bram@chia.net
2
IST Austria pietrzak@ist.ac.at

July 9, 2019

Abstract
This document outlines the basic design principles of the consensus
layer (the blockchain) of the Chia network. It is inspired by and similar
to the Bitcoin blockchain, which achieves consensus when a majority of
the computing power dedicated towards securing it is controlled by honest
parties. In Chia the resource is not computing power, but disk space.
To achieve this, the proofs of work used in Bitcoin are replaced by
proofs of space. To get a mining dynamic like in the Bitcoin blockchain,
Chia alternates proofs of space with verifiable delay functions.
We provide an initial security analysis of the Chia backbone, showing
that as long as at least ≈ 61.5% of the space is controlled by honest parties
Chia satisfies basic blockchain security properties.

Glossary
We reserve the following letters throughout this writeup:
w ∈ Z+ a security parameter that we use for various things, such as the output
of H below or the size of a challenge: w = 256 is sufficient for all cases.

H : {0, 1}∗ → {0, 1}w a cryptographic hash function, modelled as a random

oracle for proofs.
T ∈ Z+ : Chia difficulty parameter (has a function similar to the difficulty
parameter in Bitcoin).
κ ∈ Z+ : honest farmers work on the κ best paths (presumably κ = 3 in Chia).

θi ∈ [0, 1]: speedup factor one gets by using κ = i compared to κ = 1 (illus-

trated in Figure 2).
1
ιi = 1 − 1+e·θ i
∈ [0, 1] fraction of space honest farmers must hold if they use
κ = i (illustrated in Figure 2).

1
 η ∈ R+ : seconds required to compute one step (a squaring in a group of
unknown order) of the verifiable delay function (VDF).
ξ ∈ R+ : max. fluctuation of T allowed in consecutive epochs (in Bitcoin the
corresponding parameter is 4, and this will be adapted in Chia).

Contents
0 Outline 3

1 Introduction 4
1.1 Bitcoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Replacing PoW with PoSpace . . . . . . . . . . . . . . . . . . . . 5
1.4 Digging attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Splitting the chain . . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 Unique primitives . . . . . . . . . . . . . . . . . . . . . . 7
1.4.3 Careful with difficulty resets . . . . . . . . . . . . . . . . . 7
1.5 Double dipping attacks . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.1 Punishment is not a solution . . . . . . . . . . . . . . . . 8
1.5.2 Smoothing out grinding advantage . . . . . . . . . . . . . 8
1.5.3 How Chia adresses double dipping . . . . . . . . . . . . . 8
1.6 Chain Quality of Chia. . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6.1 Chain quality . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6.2 The underlying probabilistic experiment . . . . . . . . . . 10
1.7 Long range attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.1 Long range attacks on PoStake using old money . . . . . 14
1.7.2 Long range attack on PoSpace using resource variation . . 14
1.7.3 Solving long range attacks using VDFs . . . . . . . . . . . 14

2 Building Blocks: PoSpace, VDFs and Signatures 15

2.1 (Unique) Digital Signatures . . . . . . . . . . . . . . . . . . . . . 15
2.2 (Unique) Proofs Of Space . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Algorithms for PoSpace . . . . . . . . . . . . . . . . . . . 15
2.2.2 Security of PoSpace . . . . . . . . . . . . . . . . . . . . . 16
2.2.3 Unique PoSpace . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.4 The [AAC+ 17] PoSpace . . . . . . . . . . . . . . . . . . . 17
2.3 Verifiable Delay Functions . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 The [Wes18, Pie18] VDFs . . . . . . . . . . . . . . . . . . 19

3 The Blockchain 19
3.1 Trunk and Foliage . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Block Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2
4 Algorithms for Farmers and Time Lords 21
4.1 Chain Management . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Space Farmer Algorithms . . . . . . . . . . . . . . . . . . . . . . 23
4.3 Time Lord Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 25

5 Difficulty Adjustment 27
5.1 Difficulty adjustment in Bitcoin . . . . . . . . . . . . . . . . . . . 28
5.2 A grinding attack using difficulty resets . . . . . . . . . . . . . . 29
5.3 Difficulty adjustment in Chia . . . . . . . . . . . . . . . . . . . . 30
5.4 On the importance of 4 . . . . . . . . . . . . . . . . . . . . . . . 31
5.4.1 An attack if ξ < e . . . . . . . . . . . . . . . . . . . . . . 32
5.4.2 Optimality of the attack . . . . . . . . . . . . . . . . . . . 34

6 Chain Growth and κ 34

6.1 Our idealized setting . . . . . . . . . . . . . . . . . . . . . . . . . 35
`
6.2 The random variable Cκ,h modelling chain growth . . . . . . . . 35
`
6.3 Analytical bounds on Cκ,h . . . . . . . . . . . . . . . . . . . . . . 36
6.4 ιi and θi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.5 The Chia Backbone . . . . . . . . . . . . . . . . . . . . . . . . . . 39

A Missing Proofs for Chain Quality 42

0 Outline
In Section §1 we discuss the main challenges one encounters when designing a
blockchain without relying of proofs of work, and how they are solved in Chia.
In §2 we introduce the main building blocks of Chia. Apart from standard
primitives like unique signatures and cryptographic hash functions, these include
new proof systems which have been developed more recently, namely, proofs of
space (PoSpace) and verifiable delay functions (VDF).
In §3 we specify the blockchain format of Chia which differs in some cru-
cial points from the Bitcoin blockchain. Instead of using proofs of work, Chia
alternates proofs of space with verifiable delay functions. This results in a chain
than in many aspects is similar to Bitcoin, in particular, as in Bitcoin no syn-
chronisation is needed and we can prove rigorous security guarantees assuming
a sufficient fraction of the resource (space in Chia, computation in Bitcoin) is
controlled by honest parties.
To prevent grinding attacks (as discussed in §1) the Chia chain is split into
two chains, one “ungrindable” chain called the trunk, which only contains the
PoSpace and VDF outputs, and another chain called foliage, which contains
everything else.
Section §4 contains the (pseudo)code for the algorithms used by the farm-
ers, who compute the proofs of space, and the time lords who compute the VDF
outputs.

3
 In §5 we discuss the difficulty adjustment in Chia. It differs from the
way difficulty adjustment work in Bitcoin as a subtle grinding attack would be
possible if one would naı̈vely adapt it.
We also make an observation which seems not be generally known, but
Nakamoto – the anonymous Bitcoin designer(s) – might have been aware of
as it explains why the factor by which the difficulty can vary in consecutive
epochs (an epoch refers to a sequence of blocks using the same difficulty pa-
rameter, in Bitcoin that’s 2016 blocks) is set to the rather large value of 4. We
show an attack that is possible if that factor was less than e ≈ 2.718.
In §6 we provide an initial security analysis for Chia. We discuss this
in more detail below in §1.1, but in a nutshell, for the most basic design we
prove security as long as the honest farmers control at least ≈ 73.1% of the
total space. This can be improved by having the honest farmers extending not
just the first, but the first κ > 1 chains for every depth. Which value of κ to
use is a “social convention” rather than a protocol parameter. By using κ = 3
the honest farmers just need to control ≈ 61.5% of the space.

1 Introduction
1.1 Bitcoin
We assume the reader has some familiarity with Bitcoin, and just mention the
aspects and results that are relevant for discussing Chia. Recall that in the
Bitcoin blockchain, to extend a block β, the miner must provide a proof of work
for a challenge c = H(β, data) derived by hashing the block β to be extended
and the payload data (transactions and a timestamp) of the block to be added.
The proof is a nonce ν such that1

0.H(c, ν) < 1/D

where D is the difficulty parameter and H is a cryptographic hash function

(SHA256). If H is modelled as a random function, in expectation D invocations
of H are necessary and required to find such a proof.
Bitcoin specifies that miners should always work towards extending the
longest chain they are aware of.2 A malicious miner controlling more than
half of the hashing power has full control over the chain. He can ignore blocks
contributed by other parties so only his blocks appear in the chain, and thus
get all the rewards and censor transactions. Even worse, such a 51% adversary
can double spend.
Presumably it was assumed by Nakamoto that a malicious miner who con-
trols less than half of the total hashing power can’t gain anything by deviating
from the honest mining strategy. This intuition was shown to be wrong due
to subtle selfish mining attacks [ES14]: a miner controlling α < 1 times the
1 Here,for X ∈ {0, 1}w we denote with 0.X a binary value, thus 0.X = w −X[i] ∈ [0, 1).
P
i=1 2
2 Technically, it is the chain that accumulates proofs of work of highest total difficulty,

typically (but not necessarily) that will be the chain with the largest number of blocks.

4
hashing power of the honest miners (i.e., less than half of the total) can add an
α
α fraction of the blocks to the chain (compared to the 1+α fraction they would
get by following the rules). On the positive side, [GKL15] show that there is
no better attack. They define the chain quality as the fraction of blocks an
adversarial miner can push into the chain, and show that for an adversary as
α
above, this fraction is at most 1+α .

1.2 Attacks
Grinding attacks. Unfortunately, the simple analysis of the Bitcoin back-
bone from [GKL15] does not extend to blockchains that use proof systems other
than proofs of work, like proofs of stake (PoStake) or proofs of space (PoSpace).
The reason is that in a PoW-based blockchain one can use the mining resource
(the hardware and electricity required for doing the computation) only towards
extending one particular block for one particular challenge. On the other hand,
proof systems like proofs of space (or stake) are very cheap to compute, so a
malicious miner can potentially launch a grinding attack by deviating from the
honest mining rules and computing many more proofs than specified by the
protocol (in the context of proofs of stake these attacks are called “nothing at
stake” problems). We distinguish two types of grinding attacks.
digging refers to grinding attacks where the adversary tries to extend one par-
ticular block in many different ways.3

double dipping refers to grinding attacks where the adversary tries to extend
many different blocks, not just the one(s) specified by the protocol.
We discuss digging and double dipping, and how they are handled in Chia, in
more detail in §1.4 and §1.5 below.

Short and long-range attacks. Grinding attacks are not the only security
problems that come up once we replace proofs of work with proofs of space (or
stake) in a Bitcoin like blockchain. Another issue is long-range attacks, which
refer to attacks where an adversary tries to generate a chain that forked from
the chain the honest farmers saw a long time ago. We will discuss long range
attacks and how Chia avoids these using verifiable delay functions (on top of
PoSpace) in §1.7.

1.3 Replacing PoW with PoSpace

In this section we discuss what it means to replace PoW with PoSpace4 in a
blockchain, which (even ignoring security issues) is not obvious as PoW and
3 In Bitcoin the honest mining strategy is basically digging: miners hash different nonces

until a lucky miner finds a nonce whose hash is below the difficulty. In Chia a farmer should
just get a single shot at extending a block, thus one can think of digging as “illegal mining”.
4 or proofs of stake, or any other proof system where proofs can be efficiently computed

and where the proof systems is a one round public-coin challenge response protocol.

5
PoSpace are syntactically different: In Bitcoin the miners race to find a PoW,
the miner who finds it announces a new block to the network, the block gets
attached, the miner gets its reward, and the miners switch to extending this
new block. Using a proof system like PoSpace, every miner can immediately
compute a PoSpace, so we somehow need to specify who “wins” and when to
continue with the next block.
The PoSpace-based Spacemint [PPK+ 15] blockchain assigns a quality to
each PoSpace (this quality is simply the hash of the proof), and the protocol
specifies that the PoSpace of best quality announced should be considered as
the extension of the chain. In Chia this basic idea is developed further. We also
assign a quality to each PoSpace, but to finalize the block one must augment this
PoSpace with the output of a verifiable delay function. The time parameter for
the VDF – which specifies how many sequential computational steps are required
to compute the output – is linear in the quality of the PoSpace, which means
the PoSpace with best quality (best meaning lowest value) can be finalized
first. Alternating PoSpace with VDFs like this gives the Chia blockchain a
farming dynamic similar to mining in Bitcoin. In particular, we don’t need any
synchronisation like Spacemint or PoStake-based blockchains like Ourborors.

1.4 Digging attacks

As already outlined, when a Bitcoin miner wants to extend a block β, they
prepare the payload data and must then find a PoW for challenge c = H(β, data)
and difficulty D, i.e., a nonce ν such that 0.H(c, ν) < 1/D. As the miner
chooses data, they can actually compute many different challenges c1 , c2 , . . .
(e.g. by taking various subsets of the available transactions or slightly changing
the timestamp). In principle, a Bitcoin miner could now choose to search for
a PoW for two (or more) challenges simultaneously, but that would require
splitting the resource (hardware and electricity) amongst those challenges, and
thus they gain no advantage by doing so.
In sharp contrast to this, if we naı̈vely used a proof system like PoSpace in a
Bitcoin-like design, a malicious miner could generate proofs for many different
challenges c1 , c2 , . . ., and then cherry pick the one that is most promising (say,
the best one as outlined above). By trying out X challenges, the miner would
increase his chances of winning (as compared to honest mining) by a factor of
X. Thus in some sense we’re back to a PoW-based scheme as rational miners
would not follow the honest mining rule, but race to compute as many PoSpace
as possible. We refer to such grinding attacks – where an adversary tries to
extend a block in many different ways – as digging.
In §1.4.1 to §1.4.3 we outline how digging attacks are prevented in Chia.

1.4.1 Splitting the chain

To prevent digging by grinding through different values for data as outlined
above, Chia adapts an idea from Spacemint. The chain is composed of two
chains as illustrated in Figure 1; one chain is called the trunk and contains just

6
 Foliage αi−1 signature
αi αi+1

signature
βi−1 challenge βi βi+1
Trunk σi−1 τi−1 σi time
τi σi+1 τi+1
challenge
parameter

Figure 1: Illustration of the Chia blockchain that will be explained in §3. A block
β = (σ, τ ) in the (ungrindable) trunk chain contains a proof of space σ followed
by a VDF output τ . A block α in the foliage contains the payload (transactions,
timestamp), a signature of the previous block in foliage (to chain these blocks),
and a signature of the proof of space (to bind the foliage to the trunk). This
figure just illustrates the three deepest blocks of a chain, Figure 5 on page 20
illustrates a “richer” view that contains forks and non-finalized blocks.

the proofs (PoSpace and VDF outputs), the other chain is called the foliage
and contains the payload data (and some signatures to bind the foliage to the
trunk). All the challenges (for PoSpace and VDF) come from previous values
in the trunk, and thus are not susceptible to grinding attacks where one tries
out various values of data in the foliage (if we take difficulty resets into account,
that’s not quite true, as we’ll discuss in §1.4.3).

1.4.2 Unique primitives

To prevent digging it is also crucial that the cryptographic primitives used in
the trunk are unique. In particular, Chia uses a unique signature scheme, where
uniqueness means that for every public-key/message pair there exits exactly one
valid signature. The PoSpace we use are unique and a verifiable delay function
is unique by definition.5

1.4.3 Careful with difficulty resets

Even after outsourcing the payload data to the foliage and make sure all prim-
itives in the trunk are unique, it turns out that there is still a possible digging
attack if the difficulty reset mechanism is directly adapted from Bitcoin. We
discuss this in §5, but in a nutshell, the attack is possible because the difficulty
parameter depends on the timestamps, which are (as part of data) in the foliage
and thus can be ground. As a VDF output depends on the difficulty parameter,
the VDF outputs can be indirectly ground via this connection. For this attack to
work, the difficulty reset must apply to blocks immediately following the block
whose timestamp was used to recompute the difficulty parameter (as is the case
5 The definition of a VDF basically matches the definition of a unique proof of sequential

work; the reason we cannot use simple proofs of sequential work like [CP18] in Chia is precisely
because they’re not uinque.

7
in Bitcoin). This can be easily prevented by specifying that the difficulty reset
only applies after sufficiently many blocks have passed.

1.5 Double dipping attacks

In the previous section we outlined how Chia prevents digging attacks. We now
discuss the other type of grinding attacks called double dipping. Recall that
digging refers to attacks where an adversary tries to extend a particular block
in many different ways, whereas double dipping refers to attacks where they try
to extend different blocks, not just the one(s) specified by the protocol.

1.5.1 Punishment is not a solution

Penalties were suggested6 as a means to disincentivize double dipping in 2014.
Spacemint [PPK+ 15] also specified a form of penalties7 . Unfortunately, penal-
ties don’t really solve the issue. In particular, penalties can only be a deterrent
against attacks where the potential gain is less than the potential penalty, so
they might disincentivize things like selfish mining, but not double spending.
Penalties are also no deterrent against long range attacks (discussed in §1.7)
where an adversary tries to generate a long chain in private, simply because
then there is no one around to trigger the penalty.

1.5.2 Smoothing out grinding advantage

One idea to countering double dipping and also digging attacks that was in-
troduced in Spacemint (and later used e.g. in Ourborors Praos) is to deviate
from a blockchain-like design by using the same challenge for several consecu-
tive blocks. The reason this makes grinding attacks less attractive is that it is
unlikely that a challenge will be good for many consecutive blocks. To get back
to the cherry picking analogy: you can choose the best cherries going through
them one by one, but if you must pick one entire bucket out of many buckets
full of cherries, then the quality of the cherries in the best bucket will only be
slightly better than the average.

1.5.3 How Chia adresses double dipping

The specification of the Chia blockchain has no built-in mechanism to prevent
double dipping at all, instead we first quantify the advantage one gets from
double dipping. Then we show how to decrease this advantage by changing the
farming rules and having the honest farmers extend more than just one block
at every depth.
We explain the result in more detail in §1.6 below, but in a nutshell, we show
that the basic design is secure (in the sense of having non-zero chain quality) as
6 https://blog.ethereum.org/2014/01/15/slasher-a-punitive-proof-of-stake-algorithm/
7 In Spacemint, whenever a space miner publishes two blocks for the same block position but

extending different blocks, this pair of blocks can be used (within a special type of transactions)
to steal half the block reward of the cheating miner while the other half is destroyed.

8
long as at least 73.1% of the space8 is controlled by honest farmers. As proofs
of work are not susceptible to double dipping, Bitcoin only requires the honest
miners to control > 50% of the hashing power to be secure. To narrow this
gap, we also let honest farmers double dip to some extent: a parameter κ ∈ Z+
specifies that the honest farmers should compute a PoSpace for the first κ (not
just the first) blocks at every depth. Setting κ = 3 seems like a good choice;
this doesn’t increase the work for farmers by too much, and now the honest
farmers just need to control ≈ 61.5%. Figure 2 shows how this fraction drops
as κ increases.
Remark 1 (Social convention of choosing κ). Let us stress that the value of κ
is not part of the specification of Chia. Rather, it is a social convention by the
honest farmers and thus can easily be adapted the future, in particular, this will
not need a fork. One might chose to lower κ to speed up consensus, or increase
it to improve security (this not only means raising the fraction of space required
for double spending, but also e.g. making selfish mining less profitable).

1.6 Chain Quality of Chia.

We provide an initial security analysis for Chia in an idealized setting so we can
focus on the core problems. Concretely, we assume that
i. we have no network delays,

ii. an adversary can compute the VDF no faster than the honest parties (but
they can compute an unlimited amount of VDF outputs in parallel),
iii. the proofs of space are ideal (i.e., allow for absolutely no time-memory
trade-offs) and

iv. we have no difficulty resets.

1.6.1 Chain quality

Chain quality for κ = 1. In this idealized setting we prove for the most
basic κ = 1 case – where the honest farmers compute a PoSpace only for the
first block they see at each depth – the following
1
(Corollary of Lemma 2) An adversary who controls less than a 1+e ≈
0.269 fraction of the total space cannot (in private) grow a chain
faster than the honest parties.
As illustrated in Figure 1, in Chia the challenge to compute the PoSpace σi is
derived from the last VDF output τi−1 . This challenge is not simply the hash
of τi−1 , but the hash of a signature of τi−1 . This means a potential adversary
will not be able to predict the challenge for a farmer, which in turn allows us
to prove the following
8 This number is 1 − (1/e)(1 + 1/e) ≈ 0.731 where e ≈ 2.718 is Euler’s number.

9
 (Informal statement of the “no slowdown” Lemma 4) An adversary
who cannot break the security of the signature scheme (but otherwise
can be unbounded, in particular, has unlimited space and even can
compute VDF outputs in zero time) cannot slow down the rate at
which the honest farmers grow the chain.
As a corollary of Lemmas 2 and 4 we get the following statement
1
As long as the honest farmers control at least a 1 − 1+e ≈ 0.731
fraction of the total space, the blockchain is secure in the sense that
a non-zero fraction of the blocks in the chain were provided by honest
farmers (chain quality property), and a block that is sufficiently deep
in the chain will almost certainly remain there forever (common
prefix property).
It is clear that as the fraction of the space controlled by the honest farmers
increases beyond the minimal 0.731 fraction, the chain quality – i.e., the fraction
of blocks in the chain contributed by honest farmers – will also increase, but at
this point we can’t prove any non-trivial quantitive bounds for this.

Chain quality for κ > 1. The reason for the gap between the ≈ 0.731 fraction
(of space) we need to be under honest control in Chia and the 0.5 fraction (of
computing power) in Bitcoin is due to double dipping attacks. If we specify that
honest farmers must extend every block they see, then we’d also only require a
0.5 fraction, as the most extreme double dipping attack would then coincide with
the honest farming strategy. Of course that would be completely impractical.
We will consider settings in between the two extreme cases where a parameter
κ ∈ Z+ specifies that the honest farmers should compute a PoSpace for the first
κ blocks they see at every depth. At the same time, every time lord should
work towards finalizing κ blocks at every depth (so the extreme cases above
correspond to κ = 1 and κ = ∞).
Setting a value for κ is a trade-off: higher values of κ give better security
guarantees, but increase the work required of the farmers as they must compute
κ proofs for every depth. To set a value for κ in Chia it helps to know how fast
the fraction of space required to be controlled by honest farmers approaches 0.5
as we increase κ, and we denote these values by ικ . We can only analytically
compute this fraction for κ = 1, where it is ι1 = 1 − (1/e)(1 + 1/e) ≈ 0.731, and
it follows from the definition that ι∞ is 0.5. To determine the other values we
ran simulations (which will be discussed in §6.2). As one would expect the ιi
converge very quickly towards 0.5 as illustrated in Figure 2. Chia will use κ = 3,
which corresponds to ι3 ≈ 0.615.

1.6.2 The underlying probabilistic experiment

The technical statement of Lemma 2 considers the following simple probabilistic
experiment. For positive integers h, `, consider an h-ary tree of depth `. Assign
each edge of the tree a weight sampled uniformly iid in [0, 1]. We then consider
the following random variables (also illustrated in Figure 4).

10
 1

0.8

0.6

0.4

1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 100

κ: 1 2 3 4 5 6 7 8 9 10
θκ : 1.00107 0.68468 0.58789 0.54136 0.51296 0.49626 0.48197 0.47395 0.46567 0.45830
ικ : 0.73127 0.65049 0.61510 0.59540 0.58235 0.57428 0.56712 0.56300 0.55866 0.55472
κ : 10 20 30 40 50 60 70 80 90 100
θκ : 0.45830 0.43062 0.41910 0.41282 0.40913 0.40607 0.40377 0.40252 0.40030 0.39992
ικ : 0.55472 0.53929 0.53254 0.52878 0.52655 0.52468 0.52326 0.52249 0.52110 0.52087

Figure 2: The red values shows (simulated values for) ι1 . . . ι100 , the neces-
sary fraction of space that honest farmers must hold to outpace a malicious
farmer who has an infinite number of VDF servers. It approaches 0.5 (red
dotted line) as κ (on x-axis, note the step size increases from 1 to 10 at
κ = 10) increases. The blue values show (simulated values for) θ1 . . . θ100 , where
` `
θi = lim`→∞,h→∞ E[Cκ,h ]/E[C1,h ] specifies what speedup can be achieved by ex-
tending the κ (as opposed to just one) blocks at every depth; it approaches 1/e
`
as κ → ∞. To simulate θi we sampled Cκ,h (cf. §1.6.2) for h = 999, ` = 100000
` `
and approximated θκ ≈ Cκ,h /E[C1,h ]. The ικ were computed from the θκ as
1
ικ = 1 − 1+e·θ κ
.

11
 0 0.367879 1

Figure 3: Visualization of chain growths for κ = 1 (bottom) to κ = 4 (top),

simulated with h = 29, ` = 30. x-axis is time, the green line connects the κ
blocks (red dots) at the same level. The chain (or for κ > 1 tree) is in blue.

` = 3, h = 2 .09
.87 .40
`
.46 .11 C1,h = .80
.23
.81
.41
.33
.37 .95

.15 .39
`
.06 C∞,h = .54

Figure 4: Illustration of the probabilistic experiment outlined in §1.6.2. The

globally shortest path has weight 0.54; the path we get by greedily following the
best edge at every node has weight 0.80.

12
 `
• (greedy path) Let C1,h be the total edge weight of the path we get by
starting at the root, following the edge with lowest weight at every node,
and ending at a leaf.
`
• (globally shortest path) Let C∞,h be the minimum of the total edge weight
`
of all h paths from the root to the leaves.
`
C1,h basically captures the time honest miners with total space h need to grow
`
a path of length `, whereas C∞,h captures the time an adversary who tries to
extend all possible paths needs (i.e., an adversary launching the most extreme
double dipping attack). It follows from simple order statistics (cf. Lemma 1)
that
` `
E[C1,h ]=
1+h
and Lemma 2 states that
` `
E[C1,h ] ≤ E[C∞,h ]·e . (1)

We derive eq.(1) analytically, and simulations indicate that it is tight as h, ` go

to infinity.
`
We also define random variables Cκ,h for any κ ∈ Z+ , where Cκ,h`
captures
the time h honest farmers need to grow a path of length ` assuming they try to
extend the first κ blocks they see at every depth.
We define θκ as the factor by which one can speed up chain growth by
extending κ chains instead just one chain

` ` 1+h `
θκ = lim E[Cκ,h ]/E[C1,h ]= · lim E[Cκ,h ]
`→∞,h→∞ ` `→∞,h→∞

Although we define this value in the limit for large ` and h, this value converges
`
very fast so we can get good approximations by sampling Cκ,h for fairly small
finite `, h. We will show that the fraction ικ discussed in the previous section
can be computed from θκ as
1
ικ = 1 − .
1 + e · θκ
θκ and ικ are illustrated in Figure 2.

1.7 Long range attacks

Most attacks on blockchains can be roughly classified as short range or long
range attacks. Short range attacks refer to attacks which only involve the last
few blocks, whereas long range attacks are attacks where an adversary tries to
generate a chain that forked (from the chain seen by the honest parties) many
blocks in the past.
Short range attacks against Bitcoin include selfish mining [ES14] – where
the adversary strategically withholds blocks to get an unfair share of the block

13
rewards – or double spending – where the adversary tries to generate a chain in
private that is sufficiently long to double spend. As Bitcoin specifies that a block
at depth 6 can be considered confirmed, even an adversary with significantly less
than 50% of the hashing power has a good chance is succeeding in this attack
(which requires growing a chain of length 6 faster than the honest miners).
Long range attacks are not an issue for Bitcoin,9 but they are a major prob-
lem for blockchains based on efficient proof systems like proofs of space or proofs
of stake.

1.7.1 Long range attacks on PoStake using old money

A particularly annoying longe range attack against proof of stake blockchains
uses the observation that it is sufficient to hold a large stake (i.e., the secret
keys allowing to spend coins) that was valid at some point in the past (but
given the current chain can be worthless). Such old keys can be used to fork
the chain at the point where the coins where valid, and then one can bootstrap
a chain that looks valid in the present. An adversary could potentially acquire
such a stake at low cost, e.g. by buying a large fraction of the coins and then
immediately selling them. There doesn’t seem to be a solution to this attack
unless one assumes trusted parties or requires parties to come online sufficiently
frequently so one can acquire check-points at sufficiently short intervals.

1.7.2 Long range attack on PoSpace using resource variation

Recall that in Bitcoin the “longest chain” does not really mean the chain with
most blocks, but rather it is the “heaviest chain”, the one that required most
hashing power to generate (this can be computed by summing up the difficulty
parameter over each block). We can adapt this rule to a PoSpace-based chain
by saying that the “heaviest chain” is the one whose sum of qualities of the
PoSpace (the quality of a block reflects the amount of space that was used
to generate the block) over all blocks is maximal. This is delicate for various
reasons, but the most serious is that now it is possible to generate a chain
that is heavier than the honestly generated chain using space that is only the
average of the space that was used for farming the honest chain, which can be
much lower than the current amount of space dedicated towards mining (e.g.
because mining became much more lucrative over time or disk space became
much cheaper). Spacemint [PPK+ 15] addresses this problem in an ad-hoc way
by putting more weight on more recent blocks when calculating the weight of a
chain.

1.7.3 Solving long range attacks using VDFs

The two long range attacks outlined above make crucial use of the property
that PoStake and PoSpace can be computed quickly, so one can bootstrap a
9 A 51% adversary can generate an arbitrary long fork, but against this adversary everything

is lost anyways.

14
heavy chain in very short time once one has sufficient (old) stake or space. For
PoW-based blockchains like Bitcoin this is not possible: one can generate a
chain that is heavier than the current Bitcoin blockchain using hashing power
that is slightly higher than the average hashing power that was dedicated since
genesis, but this will (in 2019) require a decade, at which point it is useless as
the honest chain will also have advanced by a decade.
Chia achieves this desirable property (i.e., that a chain cannot be boot-
strapped quickly) without relying on wasting massive computing power as re-
quired by PoW. Instead, Chia alternates PoSpace with VDFs. This way, the
main resource is space, while the VDFs guarantee that one cannot bootstrap a
chain much faster than honestly farming it.

2 Building Blocks: PoSpace, VDFs and Signa-

tures
In this section we sketch the main building blocks used in the Chia blockchain:
unique digital signatures, proofs of space [DFKP15] and verifiable delay func-
tions [BBBF18, Wes18, Pie18, BBF18]. The definitions are not fully general,
but instead tailored to the particular constructions of PoSpace from [AAC+ 17]
and the VDFs [Wes18, Pie18, BBF18] based on sequential squaring.

2.1 (Unique) Digital Signatures

A digital signature scheme is specified by three algorithms; a (probabilistic)
key-generation algorithm Sig.keygen, a signing algorithm µ ← Sig.sign(sk, m)
and a verification algorithm Sig.verify. We assume the standard security notion
(unforgeability under chosen message attacks) and perfect completeness, that
is, a correctly generated signature will always verify:

∀m, Pr[Sig.verify(pk, m, µ) = accept] = 1

where (pk, sk) ← Sig.keygen ; µ ← Sig.sign(sk, m) .

Chia uses signatures in the foliage (to chain foliage blocks and to bind them to
the trunk) and also in the trunk (so only the farmer can compute the challenge).
To avoid grinding attacks, the signatures used in the trunk must be unique, that
is for every pk (this includes maliciously generated public keys) and message m
there can be at most one accepting signature

∀pk, m, (Sig.verify(pk, m, µ) = accept) ∧ (Sig.verify(pk, m, µ0 ) = accept) ⇒ (µ = µ0 ) .

2.2 (Unique) Proofs Of Space

2.2.1 Algorithms for PoSpace
A proof of space is specified by the four algorithms given below

15
 PoSpace.init on input a space parameter N ∈ N (where N ⊂ Z+ is some
set of valid parameters) and a unique identifier pk (we use pk to denote
the identifier as in Chia it will be the public key of a signature scheme)
outputs10

S = ( S.Λ , S.N = N , S.pk = pk) ← PoSpace.init(N, pk)

Here S.Λ is the large file of size |S.Λ| ≈ N the prover needs to store. We
also keep N, pk as part of S as it will be convenient.

PoSpace.prove on input S and a challenge c ∈ {0, 1}w outputs a proof

σ = ( σ.π , σ = σ.N = S.N , σ.pk = S.pk , σ.c = c ) ← PoSpace.prove(S, c)

Here σ.π is the actual proof, the other entries in σ are just convenient to
keep around.
PoSpace.verify on input a proof σ outputs accept or reject

PoSpace.verify(σ) ∈ {reject, accept} .

We assume perfect completeness

∀N ∈ N , c ∈ {0, 1}w , Pr[PoSpace.verify(σ) = accept] = 1 where

S ← PoSpace.init(N, pk) and σ ← PoSpace.prove(S, c)

2.2.2 Security of PoSpace

We will not give the formal security definition for PoSpace here, but informally
it states that an adversary who stores a file of size significantly less than N bits
should not be able to produce a valid proof for a random challenge unless he
invests a significant amount of computation (ideally close to what it costs to
run the full initialization PoSpace.init(N, pk)). Moreover it must be impossible
to amortize space, that is, initalizing space for m > 1 different identities must
require m times as much space.
To prevent grinding attacks, we need our PoSpace to be unique as defined
below.
10 The first constructions of PoSpace from [DFKP15] were based on depth-robust graphs.

The initialization phase in these PoSpace was not just a function as it is here, but an in-
teractive protocol. The definition we give here captures the [AAC+ 17] PoSpace (which was
developed for Chia) where the initialization phase is non-interactive, this makes its use in
a blockchain design much simpler. The Spacemint [PPK+ 15] proposal is using graph-based
PoSpace and because of that must bootstrap the blockchain itself to make initialization non-
interactive: farmers must post a commitment to their space to the blockchain via a special
type of transaction before it can be used for farming. Without this, Spacemint would succumb
to grinding attacks (on the message send to the verifier during the initialization phase).

16
2.2.3 Unique PoSpace
A PoSpace is unique if for any identity pk and any challenge c there is exactly
one proof, i.e.,

∀N, pk, c,
|{σ : (PoSpace.verify(σ) = accept) ∧ ((σ.N, σ.pk, σ.c) = (N, pk, c))}| = 1

We call a PoSpace weakly unique if the expected number of proofs is close to 1,

i.e.,

∀N, pk, c,
Ec←{0,1}w [|{σ : (PoSpace.verify(σ) = accept}) ∧ ((σ.N, σ.pk, σ.c) = (N, pk, c)) |]
≈1

For weakly unique PoSpace we assume that whenever there is more than one
proof for a given challenge which passes verification, PoSpace.prove(S, c) outputs
all of them.
The [AAC+ 17] PoSpace used in Chia is only weakly unique. To be able to
focus on the main challenges, we will nonetheless assume a unique PoSpace when
analyzing Chia but our analysis can be extended without major difficulties to
handle weakly unique PoSpace, things just get a bit more messy.

2.2.4 The [AAC+ 17] PoSpace

We give a very high level outline of the PoSpace from [AAC+ 17]. The space
parameter is given implicitly by a value ` ∈ Z+ , the actual space required is
approximately N ≈ ` · 2 · 2` bits (e.g. for ` = 40 that’s 10 terabytes). Let
L := {0, 1}` denote the set of ` bit strings. Below we denote with X|` the ` bit
prefix of a string X.
The identity id := pk together with a hash function H defines two functions
f : L → L, g : L × L → L as

f (x) = H(id, x)|` and g(x, x0 ) = H(id, x, x0 )|` .

Note that if we model H as a random function, then f, g are also random func-
tions. On a challenge y ∈ L the prover must answer with a tuple

id, (x, x0 ) where x 6= x0 , f (x) = f (x0 ), g(x, x0 ) = y

if it exists. In this construction, for roughly a (1 − 1/e) ≈ 0.632 fraction of the

challenges y ∈ L there will be at least one proof, and the expected number of
proofs is 1 (so it is a weakly unique PoSpace).
The prover will generate and store two tables so they can efficiently generate
proofs. They first compute and store a table with the values (x, f (x)) sorted
by the 2nd entry. With this table, the prover can now efficiently enumerate
all tuples (x, x0 ) where x 6= x0 and f (x) = f (x0 ) to generate a table containing

17
all triples (x, x0 , y = g(x, x0 )); the expected number of such triples is |L| = 2` .
This table is then sorted by the thrid value. Now given a challenge y one can
efficiently look up proofs in the second table as it is sorted by the y values.
Storing the second table requires ≈ 3|L| log(|L|) = 2`+1 ` bits, and this can be
brought down to ≈ 2|L| log(|L|) bits by encoding it in a more clever way.
Chia is based on this PoSpace, but to further minimize the effect of time/space
trade-offs (where a malicious farmer tries to save on space at the cost of doing
more computations), a nested version of this construction is used. We omit the
details in this writeup.

2.3 Verifiable Delay Functions

A VDF is specified by the two algorithms given below.
VDF.solve on input a challenge c ∈ {0, 1}w and time parameter t ∈ Z+ outputs
a proof

τ = ( τ.y , τ.π , τ.c = c , τ.t = t ) ← VDF.solve(c, t)

and runs in (not much more than) t sequential steps (what a step is de-
pends on the particular VDF). Here τ.y is the output and τ.π is a proof
that τ.y has been correctly computed. For convenience we also keep (c, t)
as part of τ .

VDF.verify on input τ outputs accept or reject.

VDF.verify(τ ) ∈ {reject, accept}

Verifying must be possible in  t steps, for existing VDFs verification just

takes log(t) [Pie18] or even constant [Wes18] time.

We have perfect completeness

∀t, c : VDF.verify(VDF.solve(c, t)) = accept

The two security properties we require are

uniqueness: It is hard to come up with any statement and an accepting proof

for a wrong output. More precisely, it is computationally difficult to find
any τ 0 where for τ ← VDF.solve(τ 0 .c, τ 0 .t) we have

VDF.verify(τ 0 ) = accept and τ.y 6= τ 0 .y .

Note that we only need τ.y (but not τ.π) to be unique, i.e., the proof
τ.π showing that τ.y is the correct value can be malleable. This seems
sufficient for all applications of VDFs, but let us mention that in the
[Pie18, Wes18] VDFs discussed below also τ.π is unique.

18
sequentialitiy: Informally, sequentiality states that for any t, an adversary A
who makes less than t sequential steps will notfind an accepting proof on
a random challenge. I.e., for some tiny 
rand
Pr[VDF.verify(τ ) = accept ∧ τ.c = c ∧ τ.t = t : c ← {0, 1}w , τ ← A(c, t)] ≤ 

Let us stress that A is only bounded by the number of sequential steps, but
they can use high parallelism. Thus the VDF output cannot be computed
faster by adding parallelism beyond what can be used to speed up a single
step of the VDF computation.

2.3.1 The [Wes18, Pie18] VDFs

The VDFs proposed in [Wes18, Pie18] (see [BBF18] for an overview of those
constructions) are both based on squaring in a group of unknown order, for
concreteness let the group be Z∗N where N = pq is the product of two large
primes p, q. On input (c ∈ Z∗N , t) the ouput of VDF.solve(c, t) is (y, π) with
t
y = c2 mod N . This y can be computed by squaring c sequentially t times
2 t
c → c2 → c2 → · · · → c2 , and it is conjectured that there is no shortcut to
this computation if one doesn’t know the factorization of N .
The VDFs from [Wes18, Pie18] differ in how the proof π that certifies that
t
y = c2 mod N is defined. The proof in [Wes18] is shorter (1 vs. log(T ) el-
ements), but soundness of the proof requires an additional assumption (that
taking random roots is hard).
If one uses an RSA group as above, a trusted setup or a multiparty com-
putation is needed to sample the modulus N in a way that nobody learns its
factorization. [Wes18, BBF18] suggest using the class group of an imaginary
quadratic field as the underlying group of unknown order. These groups can
be obliviously sampled – this means given random bits one can sample a group
without learning its order – and thus there is no need for a trusted setup.

3 The Blockchain
3.1 Trunk and Foliage
In this section we specify the blockchain format using the building blocks we
introduced in §2. As outlined in the introduction, Chia uses two separate chains
called the trunk and the foliage to prevent grinding attacks. Blocks in the
trunk β0 , β1 , . . . contain the proofs (the PoSpace and the VDF outputs required
to finalize the block). The foliage contains a block αi for every block βi in the
trunk. This block contains the payload (transactions and timestamps) of the
blockchain and a signature to bind the foliage to the trunk and at the same time
chain the blocks in the foliage.

19
 ∗
αi+1
γi−1 γi γi+1 γi+2
Foliage αi−1 signature
αi αi+1 αi+2

signature
βi−1 challenge βi βi+1 βi+2
Trunk σi−1 τi−1 σi time
τi σi+1 τi+1 σi+2 τi+2
challenge
parameter

γi0 0
0
γi+1
αi0 αi+1

βi0
0
σi0 τi0 σi+1

Figure 5: Illustration of a possible view of the blockchain (as stored in C in

§4.1). The longest path has i + 2 blocks and its head is the finalized block γi+2 .
0
There is a fork at block γi−1 ; the block γi+1 is non-finalized. The (presumably
malicious) farmer who generated the PoSpace σi+1 signed off two distinct foliage
∗
blocks αi+1 and αi+1 . The farmer of σi+2 extended the foliage block αi+1 .

3.2 Block Format

A block γi = (βi , αi ) contains a block from the trunk

βi = (i, σi , τi )

where σi = (σi .π, σi .N, σi .pk, σi .c, σi .µ) is a proof of space with an extra entry
σi .µ (explained below) and τi = (τi .y, τi .π, τ.c, τ.t) is a VDF output. Moreover,
γi must contain a block from the foliage

αi = (φi , datai ) .

We call a block γi as just described finalized, and if the VDF output τi is missing
we say the block is non-finalized.
A (finalized or non-finalized) block γi = (βi , αi ) extends a previous block
γi−1 = (βi−1 , αi−1 ) if the following conditions are satisfied (if the block is non-
finalized point 2 below is omitted).
1. σi is a valid PoSpace

PoSpace.verify(σi ) = accept

where the challenge is the hash σi .c = H(σi .µ) of the unique signature
σi .µ of the previous VDF output τi−1 , so we also check (see also Remark 2
below)

Sig.verify(σi .pk, σi .µ, τi−1 ) = accept and σi .c = H(σi .µ) . (2)

20
 2. τi is a valid VDF output
VDF.verify(τi ) = accept
where the challenge is the (hash of the) previous trunk block (see also
Remark 3 below) and the time parameter is the hash of the previous
PoSpace multiplied by the current difficulty parameter T .
τi .c = H(βi−1 ) and τi .t = 0.H(σi ) · T (3)

3. φi is a signature (under the pk used in the current PoSpace) of (the hash

of) the previous block in the foliage, the proof of space in the trunk and
the data.
Sig.verify(σi .pk, H(αi−1 , σi , datai ), φi ) = accept

4. datai is the actual data contained in the block. In this document we just
discuss the consensus layer of Chia, and for this it is not relevant how this is
specified exactly. But, like in Bitcion, it is essentially a list of transactions
that must be consistent with the transactions data0 , . . . , datai−1 in the
previous blocks.
Remark 2 (Why the PoSpace challenge is a signature). The reason the PoSpace
challenge in eq.(2) is defined as the hash of a signature instead simply the hash
of the VDF output, i.e., σi .c = H(τi−1 ), is so that only the farmer (who knows
the secret key for σi .pk) can compute the challenge. This will be crucial later to
prove the “no slowdown” Lemma 4.
Remark 3 (Why the VDF challenge comes from the previous block). The
reason the VDF challenge in eq.(3) is defined as the hash of the previous trunk
block instead of simply using the previous PoSpace to derive the challenge, i.e.,
τi .c = H(σi ), is so a time lord who has finished computing τi−1 can release it and
immediately start computing τi . The farmers can now compute the PoSpace σi
for this block, and if the time lord receives a σi before it made τi .t = 0.H(σi ) · T
sequential steps it can finalize this block and continue with τi+1 right away.
This way the honest parties will notget slowed down because there is a network
delay. This is important as an adversary who has his VDF servers and storage
physically close would not have this disadvantage. In rare cases where the best
PoSpace has extremely good quality (and thus can be finalized in just a few
seconds) there is a chance the time lord will not receive the PoSpace in time.
To avoid this the time parameter in Chia will have an additive term to enforce a
lower bound on the running time of the VDF so the network delay should never
slow down the honest parties.

4 Algorithms for Farmers and Time Lords

In this section we provide the pseudocode for the farmers, who dedicate space
towards securing the chain, and the time lords, who compute the VDF outputs
to finalize blocks.

21
4.1 Chain Management
Space farmers and time lords keep their local view on the chain stored in a data
structure C, Figure 5 illustrates the highest blocks in a possible view.
Chain.init takes no input and outputs a current view C of the chain as received
from the network.
Chain.update is invoked whenever new blocks are received from the network
or a proof is locally generated (this proof is a VDF output for time lords
and a PoSpace for farmers). It expects as inputs either a finalized or non-
finalized block γ (it is convenient to also allow an index/VDF output pair
(i, τ ) as input, in which case it checks if this input finalizes some known
non-finalized block, and continues as if its input were this finalized block).
It updates the local view C and sometimes further disseminates these
blocks – e.g. using a gossip protocol like Bitcoin – to make sure all honest
farmers will ultimately get it.
The output are two (possibly both empty) sets (Γf , Γn ), where Γf (Γn )
contains all the valid, fresh and finalized (non-finalized) blocks (as defined
below) that were just attached to C. For every block in Γn we also add
the hash of the trunk block before it as it will be required to compute the
next VDF challenge.

We will not fully specify the pseudocode of the Chain.update functionalitiy as

it is not particular to Chia. It will be convenient to define the following three
predicates that a block (which is given as input to Chain.update) can have
(non-)finalized: (as already defined in §3.2) a block γ = (β = (i, σ, τ )), α =
(φ, data)) is called finalized; if the VDF output τ is missing it is called
non-finalized.
valid: a (finalized or non-finalized) block is valid if it extends (as defined in
§3.2) a block already in C.
fresh: a block is fresh if it is valid and not already in C (we also consider it
fresh if it is finalized, but only its non-finalized version was already in C).

Remark 4 (Multiple foliage blocks). An honest farmer will sign exactly one
foliage block for each PoSpace they find (cf. line 13 in Algorithm 3 below),
but a malicious farmer might sign and gossip more than one foliage block for
the same PoSpace. We specify that Chain.update will usually consider the first
foliage block it sees for any given PoSpace as the valid one, but one must deviate
from this rule if the PoSpace gets finalized and extended with a new block, and
this new block extends a different foliage block than the one we saw first. E.g.
in the view in Figure 5 we’d consider αi+1 to be the correct foliage block even if
∗
we saw αi+1 first.

22
4.2 Space Farmer Algorithms
To simplify the exposition, we assume that all parties who want to dedicate
space dedicate the same amount of N bits, but this is not necessary, as we’ll
discuss in Remark 8. A party that wants to act as a space farmer first initializes
their space S (and some other variables) running the SpaceFarmer.init algorithm
below.

Algorithm 1 SpaceFarmer.init
1: Global Parameters: N
2: C ← Chain.init . extract view from network
3: (pk, sk) ← Sig.keygen . sample public/secret signature key pair
4: S ← PoSpace.init(N, pk) . initialize space of size N with identity pk
5: S.sk := sk . add sk to the stored file
6: Initalize a vector pos count to all 0 . see Remark 5
7: Output:
8: S = (S.Λ, S.N, S.pk, S.sk), pos count . State for SpaceFarmer.farm
9: C . State for Chain.update

Remark 5 (Storing “infinite” vectors). The i’th entry of the vector pos count
stores how many proofs were generated at depth i. We think of pos count as
infinite, but it will always only have a tiny active window j, . . . , j + δ such that
∀i < j, pos count[j] = κ, and ∀i > j, pos count[j] = 0, so it can be efficiently
stored. The same holds for the finalized and running vectors used by time lords
in the pseudocode below.
After initializing, the space farmer runs the infinite loop SpaceFarmer.loop.
In this loop, on every valid, fresh and finalized block that was received from the
network, SpaceFarmer.farm is invoked, which decides whether to compute a proof
of space to extend this block. The parts of the SpaceFarmer.farm pseudocode
that only affect the foliage are shown in purple.

Algorithm 2 SpaceFarmer.loop
1: loop
2: Wait for block(s) Γ to be received from the network
3: (Γf , Γn ) ← Chain.update(Γ)
4: ∀γ ∈ Γf : SpaceFarmer.farm(γ) . Algorithm 3
5: end loop

Remark 6 (Taking difficulty resets into account). The SpaceFarmer.farm Al-

gorithm 3 as well as the TimeLord.finalize Algorithm 6 below become more com-
plicated if we take difficulty resets into account. Concretely, these algorithms
might then have to extend/finalize a block at depth i even if they have already
extended/seen κ blocks at this depth if this new block is the head of a chain
that has a higher “cumulative work” than the κ chains we’ve seen so far at this

23
Algorithm 3 SpaceFarmer.farm
1: Global Parameters: κ . # of proofs per slot (κ = 3 in Chia)
2: Input: γi = (βi = (i, σi , τi ), αi ). . finalized, fresh & valid block at depth i
3: State: S = (S.Λ, S.N, S.pk, S.sk), pos count
4: if pos count(i + 1) = κ then . if already generated κ PoSpace
5: return without output . at depth i + 1 ignore this block
6: end if
7: pos count(i + 1) ← pos count(i + 1) + 1
8: µ ← Sig.sign(S.sk, τi ) . compute signature of last VDF output
9: c ← H(µ) . challenge is hash of this signature
10: σi+1 ← PoSpace.prove(S, c) . compute PoSpace
11: σi+1 .µ := µ . keep signature as part of the proof
12: Generate datai+1 . create payload for this block
13: φi+1 ← Sig.sign(S.sk, (αi , σi+1 , datai+1 ) . signature for foliage
14: Chain.update(i + 1, σi+1 , αi+1 = (φi+1 , datai+1 )) . Cf. Remark 7

depth. This could happen if, for example, we had a network split, the farmer
landed in the part of the network controlling a smaller fraction of the space, and
as the split is over we want them to switch back to the heavier chain generated
in the other partition. We omit the details in this writeup.
Remark 7 (Keeping the network load small). If SpaceFarmer.farm generated a
fresh (non-finalized) block, it will invoke Chain.update to update C and dissemi-
nate this fresh block. Disseminating every block created by a space farmer would
generate substantial network load.
To avoid this, we can specify Chain.update so it does not disseminate blocks
(finalized or not, locally generated or received from the network) which have
basically no chance of ending up in the blockchain. This brings down the network
load from quadratic (in the number of farmers) to linear (and the communication
for each individual farmer from linear to constant).
Remark 8 (Dealing with non-equal space). We assume that each space farmer
dedicates exactly N bits of space, but in practice farmers will have vastly different
amounts of space that they want to contribute. A simple solution to deal with
this is by letting N be some arbitrary unit of space (1 bit, or 100GB) and now a
farmer with k·N, k > 1 bits of space can emulate k space farmers, each having N
space. This solution incurs a computational cost during farming which is linear
in the dedicated space.11 A better solution to allow space farmers to initialize
just one proof of space of size N · k (that is, replace line 4 in SpaceFarmer.init
“S ← PoSpace.init(N )” with “S ← PoSpace.init(N ·k)”).
If the space farmer now generates a proof of space σ, the time to finalize
the block is not just given by a value t that is uniform in [0, T ] (computed as
t := 0.H(µ) · T in line 8 of Algorithm 6 below), but instead we let the farmer
sample k random values t1 := 0.H(σ, 1) · T, . . . , tk := 0.H(σ, k) · T and they can
11 But note that using Remark 7, the communication cost remains unchanged.

24
then use the smallest of these values. From the farmer’s view, having k proofs
and getting one random value for each is as good as having one proof that gives
k random values, but the latter is more efficient, as in only requires to compute
one – not k – proofs of space.
The cost of the above solution is still in some sense linear in k, as one has
to evaluate H k times to find the smallest ti . In Spacemint [PPK+ 15] a solution
is described whose asymptotic cost is really just ploylogarithmic. In a nutshell,
one uses H(σ) as random coins to sample from a distribution which corresponds
to the minimum of k iid values sampled uniformly from [0, 1]. This way the
farmer is efficient even if the granularity N of the space is just a bit, or even
goes to 0.

4.3 Time Lord Algorithms

Besides space farmers, sustaining the blockchain requires at least one time lord
participating to finalize blocks. Recall that to finalize a block with PoSpace σ
requires computing a VDF on challenge H(σ) running for sequential time 0.H(σ)·
T . To participate as a time lord, the party first runs the simple initialization
below which retrieves the current blockchain from the network and initializes
two vectors used to keep track of how many VDF outputs have already been
computed and are currently being computed at every depth.

Algorithm 4 TimeLord.init
1: C ← Chain.init . extract view from network
2: Initalize vectors running and finalized where for every i running[i] = 0 and
finalized[i] is the number of finalized blocks in C at depth i.
3: Output:
4: finalized, running . State for TimeLord.finalize/startVDF/restore
5: C . State for Chain.update

After initializing, the time lord runs the infinite loop TimeLord.loop.

Algorithm 5 TimeLord.loop
1: loop
2: Wait for block(s) Γ to be received from the network
3: (Γf , Γn ) ← Chain.update(Γ)
4: ∀((i, σ), α, c) ∈ Γn : TimeLord.finalize(i, σ, c) . Algorithm 6
5: ∀((i, σ, τ ), α) ∈ Γf : TimeLord.restore(i) . Algorithm 8
6: end loop

In this loop, whenever a valid, fresh and non-finalized block is received, TimeLord.finalize
is invoked. This algorithm then decides whether to start a thread to compute a
VDF output to finalize this block. In addition, for every valid, fresh and final-
ized block received, TimeLord.restore is invoked, which adapts the local view to
take this block into account.

25
 The time lord’s state contains two vectors, finalize and running, where at any
timepoint, for any i ∈ Z
finalized[i] ∈ {0, 1, . . . , κ} contains the number of finalized (either by the time
lord itself, or received from the network) blocks at depth i (once this
counter reaches κ it is no longer increased).

running[i] ∈ {0, 1, . . . , κ} contains the number of threads currently running that

compute a VDF which will finalize a block at depth i.
In a nutshell, the goal of the time lord algorithms is to generate κ finalized
blocks at every depth i as fast as possible. As we just want κ blocks, for any
depth i at any timepoint it holds that

0 ≤ finalized[i] + running[i] ≤ κ

and moreover for every i, the running[i] VDF threads are the ones which –
given the view of the time lord – are the ones which can be finalized earliest.
Concretely, this means that after receiving a finalized block from the network,
the time lord might have abort the VDF thread scheduled to finish last because
this thread would create the (κ + 1)th block at this depth. After receiving a
non-finalized block, the time lord might have to start finalizing this block, and
in this case might also have to abort the VDF thread scheduled to finish last.

Algorithm 6 TimeLord.finalize
1: Global Parameters: T , κ
2: Input: βi = (i, σi ) . non-finalized, fresh & valid block for depth i received
3: c (= H(βi−1 )) . hash of previous trunk block
4: State: finalized, running
5: if finalize[i] = κ then . already finalized κ blocks for this slot
6: return with no output
7: end if
8: t := 0.H(σi ) · T . VDF time parameter required to finalize this block
9: if finalize[i] + running[i] < κ then . less than κ proofs finalized or running
10: start thread TimeLord.startVDF(i, c, t) . to finish at time now + t
11: running[i] := running[i] + 1
12: end if
13: if finalize[i] + running[i] = κ then . exactly κ proofs finalized or running
14: if the slowest VDF thread for slot i will finish at time > t + now then
15: abort the thread of this VDF
16: start thread TimeLord.startVDF(i, c, t)
17: end if
18: end if

Remark 9 (Time lord parallelism). If κ = 1, a time lord will never have more
than one VDF thread running at once. If κ > 1, then in theory there is no upper

26
Algorithm 7 TimeLord.startVDF
1: State: finalized, running
2: Input: i, (c, t)
3: τi ← VDF.solve(c, t) . start thread computing VDF, if this thread does not
get aborted it will output τi in time required for t sequential steps
4: finalized[i] := finalized[i] + 1
5: running[i] := running[i] − 1
6: Chain.update(i, τi )

Algorithm 8 TimeLord.restore
1: State: finalized, running
2: Input: i . fresh, valid & finalized block for depth i was received
3: if running[i] > 0 and running[i]+finalized[i] = κ then
4: abort the thread TimeLord.startVDF for slot i scheduled to finish last
5: running[i] := running[i] − 1
6: end if
7: finalized[i] := min{finalized[i] + 1, κ}

bound on the number of threads. If κ = 2, then we can have many threads, if

at many consecutive depths the second best proof of space is much worse than
the best one, as illustrated in Figure 6. Such a constellation with p  τ parallel
threads is unlikely (its probability drops exponentially in p), and in practice being
able to run, say, 2κ VDFs in parallel will be sufficient most of the time. In the
rare cases where it is not, one just pauses the VDF scheduled to finish last
(this will decrease the chance of this block ending up in the final chain, but in
this particular configuration this block would have an extremely low chance of
catching up and not getting orphaned anyways).

Remark 10 (Same κ for space and time). Note that we use the same parameter
κ for the number of PoSpace generated by space farmers at every depth and the
number of VDF outputs generated by time lords at every depth. This way we’re
guaranteed that – if there is at least one honest space farmer – a time lord will
always have enough (i.e., κ) blocks to finalize at every depth. And – if there is
at least one honest time lord – every space farmer will always get enough (i.e.,
κ) finalized blocks to extend. But it is of course possible (due to network latency
or adversarial behavior) to see more than κ finalized blocks at some depth.

5 Difficulty Adjustment
In this section we will discuss how the difficulty parameter T is adjusted to
ensure blocks appear at roughly the same intervals even as the space dedicated
towards securing Chia or the speed of the VDF computation varies over time.
Recall that this parameter is used in the TimeLord.finalize Algorithm 6 where
the time parameter for the VDF required to finalize a block with a PoSpace σ

27
 t time
7
6
5 70
4 60
3 50
2 40
1 30
20

best and 2nd best PoSpace at depth 2

Figure 6: Illustration of a configuration as discussed in Remark 9 where at time
t as many as 7 VDF threads (shown in red) are running in parallel.

is computed as t := 0.H(σ) · T .

5.1 Difficulty adjustment in Bitcoin

The parameter T plays a role similar to the difficulty parameter D in Bitcoin.
There D specifies how hard it is to solve the proof of work required to extend
a block: to attach a block β, one needs to find a nonce ν such that 0.H(β, ν) <
1/D. Assuming H behaves like a random function, an expected D evaluations
of H are necessary and sufficient to find such a proof. To keep the rate at which
new blocks are attached to the blockchain at around 600 seconds (= 10 minutes)
on average – despite the fact that the hashing power dedicated towards mining
varies greatly over time – the parameter D is adjusted every 2016 blocks (≈
every two weeks) as follows: Every block in Bitcoin contains a timestamp (an
integer stating the number of seconds since January 1, 1970). Consider a chain
of length i, where i is a multiple of 2016. Let χj denote the timestamp in the
jth block and Dc the current difficulty (which was used for blocks i − 2015 to
i). The difficulty Dn for the next 2016 blocks is computed as follows. Let

target time for 2016 blocks (10min per block)

D0 := · Dc
time required for the last 2016 blocks (according to timestamps)
2016 · 600
= · Dc
χi − χi−2016

If we set the new difficulty to Dn := D0 , this would change the block arrival time
for the next blocks to 10 minutes (in expectation) assuming the hashing power
is the same as it was (on average) for the last 2016 blocks. That’s basically how
Bitcoin difficulty adjustment works,12 except that there is an additional rule
that does not allow the difficulty to vary by more than a factor of 4 in every
12 Bitcoin only takes the time used for the last 2015 blocks (not 2016 as above) into account.

This seems to be a bug in the original implementation.

28
 difficulty reset (using time stamps in αij )
1 1
γi1 αi+1 γi+1 αi+2 γi+2
αi1

βi
σi τi σi+1 1 1 1
t1 τi+1 c1 σi+2 t01 τi+2
γi−1 γi2 2
γi+1 2
γi+2
αi−1 signature αi2 αi+1 αi+2

signature
βi−1 challenge βi
σi−1 τi−1 σi τi σi+1 2 2 2
challenge time
parameter
t2 τi+1 c2 σi+2 t02 τi+2

γi3 αi+1
3
γi+1 αi+2
3
γi+2
αi3

βi
σi τi σi+1 3 3 3
t3 τi+1 c3 σi+2 t03 τi+2

Figure 7: Illustration of the grinding attack on the difficulty parameter discussed

in §5.2, where slightly different timestamps in the foliage blocks αi1 , αi2 , αi3 right
before the difficulty reset at depth i lead to different PoSpace challenges c1 , c2 , c3
for the blocks at depth i + 2.

adjustment, so the actual difficulty is set to

min{D0 , 4 · Dc } if D0 ≥ Dc

Dn := (4)
max{D0 , Dc /4} if D0 < Dc

As we’ll explain in §5.4 below setting this value to 4 seems to have a specific
reason that is not generally known.

5.2 A grinding attack using difficulty resets

As we discussed in §1.4, by splitting the chain into trunk and foliage and only
using unique primitives in the trunk we prevent any kind of digging attacks
(recall these refer to grinding attacks where an adversary tries to extend a block
in many different ways) as the blocks in the trunk cannot be ground in any way.
This simple argument ignores the difficulty parameter T , and we observe that
using the same difficulty reset mechanism as in Bitcoin would allow for a subtle
digging attack on Chia. On a high level, the reason is that the (ungrindable)
trunk is not completely independent from the (grindable) foliage because the
time parameter for the VDF depends on the difficulty parameter T , which itself
is computed from the timestamps in the foliage.
Using this connection one can launch a digging attack as illustrated in Fig-
ure 7. Concretely, consider a chain of depth i − 1 (with head block γi−1 =
(βi−1 , αi−1 )) for an i that is a multiple of 2016, so after the ith block we’ll have
a difficulty reset. A malicious farmer with space S now
1. Generates a trunk block βi = (σi , τi ) at depth i that extends γi−1 .

29
 time (as indicated by timestamps)
Bitcoin difficulty adjustment
target
Dc Dn = χi −χi−2016 · Dc

χi−2016 χi χi+2016

Chia difficulty adjustment

Tp Tc Tn

χi−3528 χi−1512 χi χi+504 χi+2016

χi−2016 χi+2528
0.75·target 0.25·target
Tn = χi −χi−1512 · Tc + χi−1512 −χi−2016 · Tp

Figure 8: Illustration of the difficulty adjustment in Bitcoin and Chia. In Bitcoin

the difficulty for the new epoch Dn (in red) is computed using the timestamps
of the epoch Dc right before it (in orange). In Chia the period to compute the
new difficulty Tn is shifted one fourth of an epoch backwards.

2. Generates many foliage blocks (say 3, as illustrated in Figure 7) αi1 , αi2 , αi3
which differ by containing slightly different timestamps. The farmer now
has three chains with head blocks γij = (βi , αij ), j ∈ {1, 2, 3} at depth i.
3. Each chain defines a slightly different difficulty parameter T1 , . . . , T3 to be
used for blocks at depth i + 1, . . . , i + 2016 as each Tj is computed using
a different timestamp.
4. Extends each block γij , j ∈ {1, 2, 3} with a block γi+1
j j
= ((σi+1 , τi+1 ), αi+1 ).
As we use different time parameters tj = 0.H(σi+1 ) · Tj , the VDF outputs
j j
τi+1 will be different, and then also the challenges cj = H(τi+1 ) for the
PoSpace at depth i + 2 will be distinct.
The above constitutes a grinding attack where the malicious farmer can get
arbitrary many challenges (the number is only limited by the number of VDFs
he can compute in parallel) for blocks that are one block after a difficulty ad-
justment. Being able to grind one block every 2016 blocks might not seem like
a serious threat, but a malicious farmer with a small fraction of the space who
can compute many VDFs in parallel could create fairly long forks that outrun
the honest chain and thus allow for double spending.13 In the next section we
outline Chia’s adjustment procedure, which prevents this grinding attack.

5.3 Difficulty adjustment in Chia

The adjustment for the difficulty T in Chia works similarly to the adjustment in
Bitcoin discussed in §5.1, but to avoid the grinding attack outlined in §5.2 the
13 Consider a malicious farmer who controls 10% of the space and can compute 1000 VDFs

in parallel. Then with probability ≈ (0.1)2 = 0.01 he’ll be able to finalize the two blocks at
depth i and i + 1 required for the grinding attack as quickly as the honest farmers, but he now
has 1000 challenges for the block at depth i + 2. The malicious farmer can now compute the
blocks at depth i + 2, i + 3, . . . as quickly as the honest chain if at every depth he discards the
≈ 90% of the blocks that need longest to finalize. This way he can outrun the honest chain
for ≈ log10 (1000) = 4 blocks before no blocks are left. At this point he has generated a fork
of depth 6 that is longer than the honest chain.

30
adjustment does not kick in right after the timestamp used to compute it has
been published, but is delayed by a few blocks.
For concreteness, we discuss below the setting where an epoch in Chia has
2016 blocks (i.e., as in Bitcoin), the target arrival time is 200 seconds (in Bitcoin
it is 600), and we set the delay before the difficulty reset applies to one fourth
of an epoch, or 504 blocks.
Assume we have a chain of length i where 2016 divides i, and let Tc be the
current difficulty parameter (used for blocks i − 1511 to i + 504), let Tp be the
previous difficulty parameter (used for blocks i − 3527 to i − 1512). Recall that
χj denotes the timestamp in the jth block, let

1512 · 200 504 · 200

T 0 := · Tc + · Tp
χi − χi−1512 χi−1512 − χi−2016

Setting the next difficulty parameter Tn (for blocks i + 505 to i + 2520) to T 0

would result in an (expected) block-arrival time of 200 seconds assuming the
space dedicated towards farming and the speed of the VDF is on average what
it was for the last 2016 blocks. We basically set Tn to T 0 , but as in Bitcoin we
don’t allow for a fluctuation larger than a factor of 4 in consecutive difficulty
parameters
min{T 0 , 4 · Tc } if T 0 ≥ Tc

Tn :=
max{T 0 , Tc /4} if T 0 < Tc
Let us give the intuition why this adjustment prevents the attack from §5.2. A
malicious farmer can theoretically still launch a grinding attack as in §5.2, but
now it is not sufficient to compute a (trunk) chain that is two blocks deep (i.e.,
the blocks at depth i and i + 1 in Figure 7) before they get distinct challenges
for the PoSpace (at depth i + 2). But now, they need to compute a chain of
length two plus the 504 blocks one must wait before the difficulty adjustment
kicks in, which is up to depth i + 505. If this 506-block fork lags way behind the
honest chain, then the fact that the adversary gets many challenges at depth
i + 505 will not be enough for the adversary to catch up. If, on the other hand,
the adversary is powerful enough to compute a very long (506 blocks) fork at
a speed close to the honest chain then this adversary will already be able to
generate shorter chains (but still long enough for double spending) faster than
the honest parties with good probability due to variance in block generation
times.

5.4 On the importance of 4

As outlined in §5.1, Bitcoin does not allow the difficulty parameter in adjacent
epochs to vary by more than a factor of 4, and we adapt this rule in Chia.
The choice of 4 might seem arbitrary, but in this section we’ll outline an
attack against Bitcoin that would be possible if Nakamoto had bounded the
fluctuation in-between epochs not by 4, but some value ξ less than e ≈ 2.718.
The attack is mostly theoretical for several reasons: it requires a 51% ad-
versary, the gain to the adversary is rather marginal and the attack generates a

31
chain with very unbalanced timestamps and is thus easy to detect. We nonethe-
less explain the attack in more detail as it is surprising that the value of the
fluctuation bound opens an attack vector and it should guide the choice of this
seemingly rather irrelevant parameter.
As mentioned, in this attack we consider an adversary who controls the
majority of the hashing power, called a 51% adversary. Such an adversary can
double spend, but they might choose not to do so in order to not undermine
the trust in the currency, but instead use their resources to squeeze as much
profit from block rewards and transaction fees as possible. A 51% adversary
can make sure 100% of the blocks in the longest chain are his (and thus get
all the rewards) by simply ignoring all blocks generated by other miners, this
way generating a block every 10 minutes in expectation. The adversary can
increase this frequency by adding more hashing power, but this will only increase
the frequency for one epoch as the next difficulty adjustment will bring the
time down to the target frequency of 10 minutes again. If the adversary later
decreases the hashing power again to the original level, they will pay for the
previous increase by creating blocks at a rate slower than 10 minutes for an
entire epoch. A simple calculation shows that the best strategy is to just keep
the hashing power constant.14 This argument ignores the fluctuation bound ξ.
In the next section we show that it is possible for a 51% adversary to publish
blocks at a rate faster than the target time of 10 min while keeping the difficulty
constant if and only if the fluctuation bound ξ is less than e ≈ 2.718.

5.4.1 An attack if ξ < e

Assume Bitcoin used a fluctuation bound ξ < e ≈ 2.718 instead of ξ = 4. Then
for a positive constant δ = δ(ξ) > 0 and some c = c(ξ) ∈ Z+ , there exists a
chain of epochs (each of length c blocks) where the difficulty for the first epoch is
Dstart and after the last epoch the difficulty (as computed from the timestamps
contained in the chain) is Dend such that
1) The difficulty drops by a constant factor Dend = Dstart · (1 − δ).
2) The average block arrival time (as indicated by the timestamps) of the
chain is at most 10 minutes.
By the two points above a 51% adversary can generate a chain with an average
block arrival time strictly below 10 minutes while not increasing the difficulty
parameter as follows: They generate and publish the chain as above, and then
attach an epoch with an average block-arrival time
Dend
· 10 minutes = (1 − δ) · 10 minutes
Dstart
14 E.g. consider an adversary who first generates blocks every 10/2 = 5 min for one epoch.

This will double the hardness parameter, and to get it down to the original value they will
have to generate blocks at a 10 · 2 = 20 minute frequency for one epoch. This gives an average
time of 5+20
2
= 12.5 minutes over those two epochs and thus is slower than just sticking with
the 10 minute frequency.

32
 2
1.5
1
0.5
0.1 1.2 2.3 3.4 4.5 5.6 6.7 7.8 8.9 10 11
Figure 9: Illustration of the attack from §5.4.1 for ξ = 2,  = 0.1. One unit
on the x-axis is the target time for one epoch, the y-axis shows the difficulty
(normalized so it starts with 1). We have 10 epochs in blue, the first of length
 = 0.1 which increases the difficulty by a factor of ξ = max{1/, ξ}, followed
by 9 epochs of length (1 + ) = 1.1, each decreasing the difficulty by a factor
(1 + ). These 10 epochs take exactly 10 units of time (one unit being the target
time for an epoch), and the difficulty at the end is strictly below the difficulty
at the start (in this example Dend = Dstart · 0.84820). We then add an eleventh
epoch shown in red which takes time Dend /Dstart = 0.84820 and thus brings the
difficulty back to Dstart . So we fit 11 epochs in 10.84820 target times without
changing the difficulty.

which is strictly less than 10 minutes. After this epoch the difficulty becomes
Dend · DDstart
end
= Dstart , so it is back to the initial difficulty, while the block-
arrival time of the last epoch – and thus also the entire chain – is strictly below
10 minutes.
We will now explain how to construct a chain that satisfies points 1) and 2)
above. An illustration is given in Figure 9. Let ξ < e ≈ 2.718 and  > 0 be some
small constant. Let Z := 2016 · 600 denote the target time (in seconds) for an
epoch in Bitcoin. We will consider a chain that contains 1/ epochs, and let Xi
denote the time for the ith epoch divided by Z (here time means the difference
between the timestamp in the last block of this and the previous epoch), so e.g.
Xi = 1 means the average block arrival time is exactly 10 minutes in the ith
epoch. We set the timestamps in the blocks so the first epoch passes extremely
quickly, while the others need slightly longer than the target. Concretely, we
set the Xi to
X1 =  , Xi = (1 + ) for i = 2, . . . , 1/
The total time for this chain of 1/ epochs is
1 1
 + ( − 1)(1 + ) =
 
We assume 1/ > ξ, then the difficulty grows by (the maximum allowed factor
of) ξ after the first epoch. After that it decreases by a factor 1/(1+) for 1/−1
epochs, and thus at the end is
 1/−1
1
Dend = Dstart · ξ ·
1+
As  goes to 0, the last term above goes to 1/e, i.e.,
 1/−1
1
lim Dend = lim Dstart · ξ · = Dstart · ξ/e
→0 →0 1+

33
0 0.367879 1

`
Figure 10: Illustration of simulated samples of Cκ,h as computed by Algorithm 9
for ` = 100, h = 99 and κ = 1 to 10 (bottom κ = 1, top κ = 10). We see how the
time to grow a chain (of length ` by h honest farmers) drops from 1 (= `/(h+1))
towards 1/e ≈ 0.3678 as κ increases.

Thus, for any ξ < e, we can choose an  > 0 such that Dend is strictly smaller
than Dstart as claimed.

5.4.2 Optimality of the attack

The particular attack we described only works if ξ < e, but it is not hard to see
that this is not only sufficient, but also necessary. That is, a chain with average
block arrival times below the target and where the difficulty at the end is no
larger than at the beginning exists if and only if ξ < e.

6 Chain Growth and κ

In this section we provide an initial security analysis of the Chia blockchain. We
take inspiration from [GKL15] who introduce and analyze the Bitcoin backbone.

34
6.1 Our idealized setting
As discussed in the introduction our analysis is in an idealized setting where
i. we have no network delays,

ii. we have no difficulty resets,

iii. an adversary can compute the VDF no faster than the honest parties,
iv. and the PoSpace are ideal, i.e., they allow for absolutely no time-memory
trade-offs.

We consider this idealized setting so we can focus on the actual challenges.

The analysis of Chia is non-trivial even with the above restrictions. This is
in contrast to Bitcoin, where showing basic security properties (non-zero chain
quality, liveliness and persistence) is trivial once we make assumptions i., ii. and
the analog of assumption iv. which for Bitcoin means the PoW are ideal.
We are confident – but haven’t worked out the details – that removing the
above restrictions in our current analysis can be done using existing or straight-
forward techniques (at the price of achieving weaker quantitative bounds and
having more technical proofs).
More concretely, the Bitcoin backbone paper [GKL15] takes network delays
into account, and their follow-up work [GKL17] also considers difficulty resets.
Removing restrictions i. and ii. should be possible along the same lines for Chia.
As outlined in Remark 3, in Chia we can actually tolerate significant network
delays without any degradation in security. As for iii., allowing the adversary
to compute the VDF a factor ζ > 1 faster than the honest parties has the same
effect as increasing the adversarial space by a factor of ζ, so this can easily be
taken into account.
Let us also recall that we assume that every farmer dedicates exactly the
same amount (N bits) of space, and we discussed in Remark 8 how to drop this
assumption.
Apart from the assumption discussed above, we of course always assume
that the cryptographic building blocks are secure. In particular, we assume
that the signature scheme satisfies the standard security notion of unforgeability
under chosen message attacks, and that the hash function is collision resistant
(whenever used for chaining) or (the stronger assumption) that it behaves like a
random function (when used to map unpredictable values to uniform challenges).

`
6.2 The random variable Cκ,h modelling chain growth
To formally argue and simulate the security of Chia we define – for κ, h, ` ∈ Z+
`
– a random variable Cκ,h whose distribution is the time required for the first
path of length ` to appear in our idealized setting where h honest farmers grow
a chain using parameters κ, T = 1, η = 1 (and there is at least one honest time
lord to finalize blocks).

35
 We fix the difficulty T and the time η required to compute one step of the
VDF to 1 simply because the time to grow a chain is linear in T and η, so those
parameters are uninteresting and we can keep the number of parameters low by
fixing them (though, as outlined in Remark 6, the fact that difficulty can be
reset complicates things).
We will denote the expected value of this variable by
def
c`κ,h = E[Cκ,h
`
].
`
The pseudocode of sampling Cκ,h is given in Algorithm 9.
`
Remark 11 (How to start sampling Cκ,h if κ > 1?). One difficulty we encounter
`
when defining Cκ,h for κ > 1 is how to define the “starting configuration” for
sampling. We could assume that there is just one block to extend at the begin-
ning, but (except for the genesis block) the honest farmers have κ > 1 blocks to
extend at every depth, so this would overestimate the time required to grow the
chain. We can assume there are κ blocks at the starting time, but this would
underestimate the time, as in an actual chain those κ blocks at a given depth
`
will be finalized at different times. When defining Cκ,h we nevertheless opt for
this option (i.e., in Algorithm 9 at line 2 we start with κ blocks at time 0), but
as the chain starts to behave in a “typical” way almost immediately after we
`
start sampling it (this can be seen in Figure 3) Cκ,h is a good approximation
for the actual time required to grow a chain no matter what the actual starting
configuration is. Looking ahead, the reason we define θκ in §6.4 for large ` (in
fact for lim`→∞ ) is just so the exact starting configuration doesn’t matter.

`
Algorithm 9 sample Cκ,h
1: Input: κ, `, h
2: s[1, . . . , κ] = 0 . initially we have κ paths of length 0
3: for i = 1 to ` do . sample ` steps
4: for j = 1 to κ do . extend each of the κ states...
5: for k = 1 to h do . by h values...
6: p[j, k] = s[j] + rand([0, 1]) . each chosen uniformly from [0, 1]
7: end for
8: end for
9: z = sort(p[1, 1], . . . , p[κ, h]) . sort the κ · h values
10: s = z[1, . . . , κ] . new state in the κ shortest paths
11: end for
12: Return min(s)

`
6.3 Analytical bounds on Cκ,h
`
For κ = 1 it is not hard to determine the exact expectation of C1,h using the
following fact

36
Proposition 1 (kth order statistics for uniform random variables). Let X1 , . . . , Xn
be iid each uniform in [0, 1]. Then the expectation of the kth smallest value of
those Xi is
k
n+1

Lemma 1 (κ = 1 chain growth).

def `
c`1,h = E[Cκ,h
`
]= (5)
1+h
Proof. Let Zi be sampled by sampling h random P` variables X1 , . . . , Xh iid with
`
uniform distribution in [0, 1], then C1,h = i Zi . By Proposition 1 we have
1
E[Zi ] = h+1 , and by linearity of expectation
" `
# `
X X `
c`1,h = `
E[C1,h ] =E Zi = E[Zi ] = .
i i=1
1+h

As following a strictly larger number paths will always increase the growth
speed, for any `, κ, h we have

c`κ+1,h > c`κ,h . (6)

Fortunately, this speedup is not unbounded. Even as κ goes to infinity, it can

speed up chain growth by at most a factor e ≈ 2.718
Lemma 2 (upper bound on chain growth). For any `, h

`
lim c`κ,h ≥ e−1 e−1 c`1,h .
= |{z}
κ→∞ 1+h
≈0.3678

The proof is in Appendix A

6.4 ιi and θi
It is crucial to understand how c`κ,h behaves as a function of κ for two reasons.
First, we need to know what happens in the limit κ → ∞ to understand how fast
a potential adversary (who can run an unlimited number of VDF servers) can
grow the chain. Second, we would like to understand what happens for small κ
so we can set a good value for the honest farmers. Looking ahead, setting κ = 3
seems to offer the best trade-off.
As we only have analytical bounds for the extreme cases κ = 1 and κ = ∞,
we’ll rely on simulations for the values in between. Figure 3 on page 12 illustrates
simulations for chain growth for 1 ≤ κ ≤ 4. This figure might lead us to believe
that, in contrast to the case κ = 1, the chain does grow faster by an unbounded
factor as κ goes to ∞. Fortunately, by Lemma 2 this is not the case, and the

37
maximum speedup one can get by using a larger κ is e ≈ 2.718. In Figure 10 we
show a simulation up to a larger κ = 10 where this convergence becomes visible.
We define θκ ∈ [0, 1] as the factor by which one can speed up chain growth
by extending κ instead of just one chain:

` ` 1+h `
θκ = lim E[Cκ,h ]/E[C1,h ]= · lim E[Cκ,h ]
`→∞,h→∞ ` `→∞,h→∞

We define this value in the limit for large ` and h, but it converges very fast
`
so we can get good approximations by sampling Cκ,h for fairly small finite `, h.
The reason we consider the limit in ` is the issue with the starting configuration
for sampling outlined in Remark 11. We have
• θ1 = 1 by definition.

• θ∞ ≥ 1/e ≈ 0.367 (by Lemma 1 and 2).

• ∀i : θi+1 < θi (as following more paths always gives strictly more advan-
tage).
Simulated values for θi , i = 1, . . . , 100 are shown (by the blue line) in Figure 2
on page 11.
We define ιi as the fraction of the space honest farmers following a κ = i
strategy must control so they can grow a chain faster than a malicious farmer
who controls the remaining 1 − ιi fraction of the space and follows a κ = ∞
strategy. We will use this value in the next section to state interesting security
properties of Chia. We claim that
1
ιi ≤ 1 − . (7)
1 + e · θi
Before we prove this simple claim, let us observe as a sanity check that for i = ∞
we get ι∞ ≤ 1/2 (using θ∞ ≥ 1/e) which makes sense as here the honest and
malicious farmer do exactly the same thing, so having half the space (i.e., as
much as the malicious farmer) is sufficient. In the remainder of this section we
will derive eq.(7). Farmers following a κ = i strategy with space s can grow a
chain at the same speed as an adversary (who follows a κ = ∞ strategy) with
space s0 if s/θi = s0 /θ∞ . Using θ∞ ≥ 1/e this gives

s/θi = s0 /θ∞ ≤ e · s0 .
s0
Using this in the last step below, we can give a lower bound of the fraction s0 +s
of the total space the malicious farmer can control as

s0 1 1
1 − ιi = = ≥ .
s0 +s 1 + s/s0 1 + e · θi

38
 ρ

Fair share ρ = ι

κ=∞
Bitcoin upper and κ=1
lower bound
ρ = 1 − 1−ι κ=3
ι

Figure 11: This figure illustrates the achieved chain quality – i.e., the fraction
ρ of blocks (y-axis) that are guaranteed to come from honest miners/farmers –
assuming they hold a ι fraction (x-axis) of the total hashing power/space. The
green line shows the wishful ideal bound ρ = ι where no strategy is better than
the honest mining strategy. The blue line illustrates the Bitcoin chain quality
ρ = 1 − 1−ιι , which is matched by selfish mining attacks [ES14]. For Chia we
show that ρ > 0 if ι > ιi whenever the honest farmers follow a κ = i strategy.
The figure shows ι1 = e/(1 + e) ≈ 0.73106 (proven analytically), ι3 ≈ 0.6151
(by simulations, Chia will use κ = 3) and ι∞ = 0.5 (trivially). In all cases we
don’t know exactly how ρ goes from 0 to 1 as ι increases from ιi to 1 (the dotted
lines).

6.5 The Chia Backbone

In §6.4 we established that honest farmers following a κ = i strategy can grow
a chain faster than a malicious farmer who can compute an unlimited number
of VDFs in parallel (and thus follow a κ = ∞ strategy) if the honest farmers
control at least a ιi fraction of the total space. We proved analytically that
ι1 ≈ 0.731 and, using simulations, that ι3 ≈ 0.615. In Chia the honest farmers
will follow a κ = 3 strategy for farming.
Thus, it is necessary to assume the honest farmers following a κ strategy
control at least a ικ fraction of the space, as otherwise attacks like double
spending would be possible. In this section we show that assuming this is also
sufficient to guarantee a meaningful security property for Chia.
Concretely, we consider the notion of chain quality which was introduced
for Bitcoin in [GKL15] : the chain quality is ρ ∈ [0, 1] if in any sufficiently long
part of the chain (as seen by honest parties) at least a ρ fraction of the blocks

39
must have been contributed by honest miners. If the miners control a ι ∈ [0, 1]
fraction of the hashing power, we ideally want them to contribute a ρ = ι fraction
of the blocks so their share of block rewards corresponds to their share of the
contributed resource, this is illustrated by the green line in Figure 11. Chain
quality might not seem like the most important property of a blockchain, but
it implies natural properties like persistence (once a block is sufficiently deep in
the chain it will stay there forever) and liveness (all transactions will ultimately
be added to the chain and end up sufficiently deep so they can be considered
confirmed).
[GKL15] show that Bitcoin achieves a chain quality of ρ = 1 − 1−ι ι , as
illustrated by the blue line in Figure 11. Although this is much worse than the
“fair” ρ = ι, it is the best one can hope for as this upper bound is matched by
selfish mining attacks [ES14]. For Chia we prove that if the honest farmers use
a κ = i strategy, then the chain quality is non-zero whenever ι > ιi (where ιi is
the fraction of space required to grow a chain faster than the malicious farmers
introduced in the previous section). Unlike for Bitcoin, we currently don’t know
how exactly the chain quality ρ improves as the fraction ι of space controlled by
the honest farmers increases from ιi to 1, that is, how exactly the dotted lines
between the (ιi , 0) and (1, 1) points behave in Figure 11.15
Lemma 3 (Chain Quality of Chia). In the idealized setting from §6.1, the fol-
lowing holds for any i ∈ Z+ : if the honest farmers follow a κ = i strategy and
control more than a ιi fraction of the space (that is, we have h honest farmers
each controlling N bits of space, and one malicious farmer with m · N bits of
h
space where m+h > ιi ) then the chain quality is non-zero.
Before we can prove this lemma we first need to prove the following
Lemma 4 (No Slowdown Lemma). In the idealized setting from §6.1, an ad-
versary cannot slow down chain growth. That is, no matter what the adversary
does, the honest parties will see a chain that (in expectation) is at least as long
as if the adversary were not present. This even holds if the adversary has a
much larger amount of space and can compute the VDFs much faster than the
honest farmers (but we need to assume the signature scheme is secure).
Note that this lemma by itself gives no meaningful security guarantee, it
only says there always will be a chain in the view of the honest parties that is
at least as long as if the adversary was not present, but this chain could contain
only adversarially generated blocks (0 chain quality) and the adversary might
even replace the entire chain (no persistence).
Proof of Lemma 4. We do assume that the adversary knows the identities, that
is the public keys pk of all the honest farmers, but does not know the corre-
sponding secret keys. As already discussed in Remark 2, because of this an
adversary will not be able to predict the quality of the PoSpace of the honest
farmers.
15 (1, 1) is on this curve as for ι = 1 we trivially have ρ = 1 because the honest miners/farmers

will trivially get all the blocks if the malicious miner/farmer has no resources whatsoever.

40
 We claim that because of this, whenever the adversary publishes a block, this
can (in expectation) only increase the speed at which the chain grows. If this
block is ignored by the honest farmers (because it is not within the first κ blocks
at this depth) this is clear. Otherwise the honest farmers will extend this block
instead of some other block they would have extended. But from the viewpoint
of the adversary, who does not know the secret keys, the distribution of qualities
those blocks will have is exactly the same for the new and the kicked-out block.
Because the new block must be finalized before the kicked-out block, this can
only increase the speed at which the chain grows.
Proof of Lemma 3. Assume for contradiction that the chain quality is zero. This
means the entire chain as viewed by the honest parties only contains blocks
farmed by the adversary. By Lemma 4, this chain is at least as long as the
chain the honest farmers would have mined if the adversary were not there.
This is a contradiction as by definition, an adversary controlling less than a
1 − ιi fraction of the space cannot grow a chain faster than honest farmers
following a i = κ strategy.

References
[AAC+ 17] Hamza Abusalah, Joël Alwen, Bram Cohen, Danylo Khilko,
Krzysztof Pietrzak, and Leonid Reyzin. Beyond hellman’s time-
memory trade-offs with applications to proofs of space. In Tsuyoshi
Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part II, vol-
ume 10625 of LNCS, pages 357–379. Springer, Heidelberg, December
2017.
[BBBF18] Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. Veri-
fiable delay functions. In Hovav Shacham and Alexandra Boldyreva,
editors, CRYPTO 2018, Part I, volume 10991 of LNCS, pages 757–
788. Springer, Heidelberg, August 2018.
[BBF18] Dan Boneh, Benedikt Bünz, and Ben Fisch. A survey of two verifi-
able delay functions. Cryptology ePrint Archive, Report 2018/712,
2018. https://eprint.iacr.org/2018/712.

[CP18] Bram Cohen and Krzysztof Pietrzak. Simple proofs of sequential

work. In Jesper Buus Nielsen and Vincent Rijmen, editors, EU-
ROCRYPT 2018, Part II, volume 10821 of LNCS, pages 451–467.
Springer, Heidelberg, April / May 2018.
[DFKP15] Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and
Krzysztof Pietrzak. Proofs of space. In Rosario Gennaro and
Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume
9216 of LNCS, pages 585–605. Springer, Heidelberg, August 2015.

41
[ES14] Ittay Eyal and Emin Gün Sirer. Majority is not enough: Bitcoin
mining is vulnerable. In Nicolas Christin and Reihaneh Safavi-Naini,
editors, FC 2014, volume 8437 of LNCS, pages 436–454. Springer,
Heidelberg, March 2014.
[GKL15] Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin
backbone protocol: Analysis and applications. In Elisabeth Oswald
and Marc Fischlin, editors, EUROCRYPT 2015, Part II, volume
9057 of LNCS, pages 281–310. Springer, Heidelberg, April 2015.
[GKL17] Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin
backbone protocol with chains of variable difficulty. In Jonathan
Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume
10401 of LNCS, pages 291–323. Springer, Heidelberg, August 2017.
[Pie18] Krzysztof Pietrzak. Simple verifiable delay functions. Cryptology
ePrint Archive, Report 2018/627, 2018. https://eprint.iacr.
org/2018/627.
[PPK+ 15] Sunoo Park, Krzysztof Pietrzak, Albert Kwon, Joël Alwen, Georg
Fuchsbauer, and Peter Gaži. Spacemint: A cryptocurrency based on
proofs of space. Cryptology ePrint Archive, Report 2015/528, 2015.
http://eprint.iacr.org/2015/528.
[Wes18] Benjamin Wesolowski. Efficient verifiable delay functions. Cryptol-
ogy ePrint Archive, Report 2018/623, 2018. https://eprint.iacr.
org/2018/623.

A Missing Proofs for Chain Quality

In this section we prove state and prove Theorem 1, Lemma 2 follows as a
corollary of this lemma.
For h, ` ∈ Z+ , let Th,` denote the full h-ary tree of depth ` where each edge
is labelled with a value iid chosen from [0, 1]. The weight of a path in this tree
is the sum of the labels of the edges on this path. We consider the following
random variables:
`
Cκ,h : As sampled by Algorithm 9. That is, given Th,` , we consider the paths
from the root to the leaves, where we start at the root, and in every level
keep track of the κ paths with lowest weight (if κ ≤ h, there are h` of
them). For the important special cases where we just keep track of one or
all paths we introduce the following variables.
def
Hh` = C1,h
`
: is the weight of the path (of length `) starting at the root of Th,` ,
where at each node we follow the edge with smallest value (until we reach
a leaf).
def
A`h = C∞,h
`
: is the minimum weight of any path from the root to a leaf in Th,` .

42
Figure 12: Illustration of outcomes of the variables Th` , Hh` , A`h , Zh` for h = 2 and
` = 3.

Y ` : is the sum of ` iid values chosen uniformly from [0, 1].

Zh` : is min{Y ` [1], . . . , Y ` [h` ]} where each Y ` [i] is iid as above.
We use the corresponding small letters to denote the expected values of those
variables, e.g., h`h denotes E[Hh` ].
Note that for ` = 1 we have16 Hh1 ∼ A1h ∼ Zh1 , and in particular h1h = a1h =
1
zh .
Hh` corresponds to the time required to farm a path of length ` using h space
by the honest farmers, who always extend the best proof found. A`h corresponds
to adversarial (or rational) farming where one extends every possible chain. Zh`
is just introduced for technical reasons, it is much easier to analyze than A`h ,
and by Lemma 5 it is a lower bound for A`h .
Lemma 5. For any h, `, the following holds for all x ∈ [0, `]
Pr[Zh` ≤ x] ≥ Pr[A`h ≤ x]
and thus also
zh` ≤ a`h .
Proof sketch. Pr[Zh` ≤ x] as well as Pr[A`h ≤ x] both consider the event that at
least one of h` paths, each of length ` and each edge assigned a weight that is
a uniform value in [0, 1], has weight at most x. The only difference is that the
in the latter, the edge weights are correlated (as many paths in the tree share
edges). The expected number of paths of length ≤ x (or any other predicate) is
exactly the same in Zh` as in A`h . But intuitively in Zh` the probability of at least
one path being short can be larger because the lengths are positively correlated
in A`h . We omit making this argument formal.
We proved Lemma 1 which states
def `
h`h = c`1,h = E[Cκ,h
`
]= .
1+h
16 A ∼ B means the random variables are identically distributed.

43
 By definition c`∞,h = a`h ≤ h`h = c`1,h , and to prove Lemma 2 we have to
bound how much smaller a`h can be than h`h .
The concrete question we ask is, if honest farmers have space h, what’s an
upper bound on the space M = M (h) we can give an adversary (that expands
all paths) such that they can’t grow a chain faster than the honest guys. By
the following theorem, setting M = h/e is sufficient.

Theorem 1. With h = eM (where e ≈ 2.718) and `/h < 1

Pr A`M > h`h > 1 − 1/e > 0.632

 

Proof. The cumulative distribution function of Y ` is17

bxc  
` 1X k `
Pr[Y ≤ x] = (−1) (x − k)` .
`! k
k=0

We will consider the case x = `/eM = `/h, as `/h < 1, the above sum just has
one term. Using `` /e`−1 ≤ `!, we get
0
x` ``
   
` 1X ` 1
Pr Y ` ≤ = (−1)k (x − k)` = = < .
eM `! k `! `!e` M ` e · M`
k=0

Thus, by the union bound

   
` ` ` `
Pr ZM ≤ ≤ Pr Y ≤ M ` ≤ 1/e
eM eM

Using Lemma 5 in the first step and h`h = `/(eM + 1) together with the above
equation in the second step

Pr A`M ≤ h`h ≤ Pr ZM
 `
≤ h`h ≤ 1/e .
  

Equivalently,
Pr A`M > h`h > 1 − 1/e ≥ 0.63 .
 

17 https://en.wikipedia.org/wiki/Irwin-Hall_distribution

44