Translation of Official Chia Blockchain Documentation

Target audience: technical audience familiar with blockchain, but not familiar with Proofs of Space (PoS), Proofs of Time/Verifiable Delay Functions (VDF) and Chia.

If you are new to Bitcoin/ blockchain, first read the tutorial: Bitcoin and Cryptocurrency Technologies.

Goal: The Chia Consensus algorithm is aimed at creating an environmentally friendly, safe and decentralized alternative to Proof of Work (PoW).

The Proof-of-Work (PoW) algorithm of cryptocurrencies burns a huge amount of electricity. In addition, it tends to become centralized due to the concentration of production and equipment ownership, as well as due to the concentration of cheap energy, which makes PoW inaccessible to ordinary users and vulnerable to various attacks.

The concept of Proof of stake or PoS (proof of ownership) has many forms, each of which has its pros and cons. Some common disadvantages: concentrated control of stock exchanges; concentration of delegation;
the use of checkpoints and subjectivity (the requirement to be online regularly); unavailability for ordinary users; various risks; clock synchronization, network bandwidth and other assumptions about
security.

Introduction

Decentralized consensus algorithms require Sybel stability with limited (not infinite) cryptographically verifiable resources. In previous blockchain systems, computing power and
rates were limited resources. Proof of space is an alternative that is much closer to Bitcoin’s original ideal of « one processor — one vote », since storage capacity is used as a limited resource. For example, a person who stores 500 GB has 5 « votes », a person who stores 100 GB has 1 « vote », where voting means an opportunity to win and confirm a block, and not an actual vote along the chain. However, using only the
storage capacity is not safe. Another part of the cryptographic puzzle is used to protect the system: namely, a verifiable delay function, which is a cryptographic proof that real time has passed. An honest system
can be created by combining the proofs of space and time. In such a system, users store random data on their hard drives for a certain period of time, and their chances of winning Chia are proportional to the space they have allocated. In addition, such a system scales up to billions of participants, similar to a proof-of-work lottery. No funds, special equipment, registration or authorization are required to join, only a hard disk. The system is completely transparent and deterministic — anyone can effectively and objectively check which chain is canonical.

Proofs of Space

A Proof—of-space protocol is a protocol in which:

1. The verifier can send a call to the tester, and

2. The tester can demonstrate to the verifier that the tester reserves a certain amount of disk space at that particular time.

The Proof-of-Space protocol consists of three elements: tracking, testing/farming, and verification.

Figure 1: First, the provider « rafts » or allocates part of the disk space (1). Then the provider « farms », respond to calls with Proof of space (2,3,4). The verifier verifies that the proof is valid for this
call.

Plotting is the process by which a tester, whom we call a farmer, initializes a certain amount of space. A farmer can be anyone who has at least 100 GiB to reserve on his laptop, or an enterprise that is ready to allocate a large amount of unused disk space. There is no upper limit. Plotting takes several hours or days and is performed only once. The initialized space is occupied by a file named
Raft. The raft dimensions are determined by the parameter k, where Space = 780 * k * pow (2, k — 10), with a minimum k equal to 32 (101.4 GiB). Starting with Chia 1.0, a k32 graph can be created in about six hours using a fast commodity machine and in 24 hours on a slow machine using a single processor core and several GB of memory. There are opportunities for huge acceleration. The PosSpace construction is based on BeyondHellman, but nested 6 times and contains others
heuristic elements.

The result is a raft file of size, for example, 100 GiB. The file contains seven tables with random data. There are 2^k records in each table. Each entry in table i contains two indicators for table i-1 (table above). Finally, each entry in table 1 contains a pair of integers from 0 to 2^k, called « x values ». The proof of the existence of a space is a set of 64 values of x that have a certain mathematical relationship.

In the diagram above, once the Prover initializes 100 GiB, they are ready to accept the challenge and create a proof. One of the attractive properties of this scheme is that it is not interactive: no registration or Internet connection is required to create a plot. Nothing gets into the blockchain until a reward is earned, as in PoW.

Farming is a process by which a farmer is given a number of tasks to demonstrate that he has legitimately reserved a certain amount of storage. In response to each challenge, the farmer checks his rafts, generates proofs and sends all the winning proofs to the network for verification.

Each iteration of this process is a table lookup. The search accepts a 256-bit query as input and output proofs. The farmer responds to the query by reading the values in Table 7. They point to two entries in table 6 and so on.
As a result, the farmer gets a complete tree of values-x. This requires one reading for table 7, two for table 6, four for table 5, etc. The whole process will take about 640 ms, assuming that the hard drive is slow then the search time is 10 ms. The amount of data being read is small and does not depend on the size of the raft.

Since most of the proofs generated by this process are not good enough (we will explain later) to be sent to the network for verification, we can optimize this process by checking only one branch of the tree, which gives two x values, depending on the task. Then we hash the x values generated in this way into a 256-bit string to determine if the test is good. Hashing these x values gives us a quality string, a 256-bit random value.
This is combined with the complexity and size of the raft to create the necessary repetitions. If the required repetitions are less than a certain number (we can enter the blockchain), we search for all PoSpace. It takes only about 7
disk search and read operations to find a single branch, or about 70 ms on a slow hard disk.

Figure 2: Graph file structure. 64 red x — values represent proof, 2 green x— values represent qualification.

Another optimization is to disqualify a certain part (for example, 511/512) of the eligibility rafts for each test. This is called a raft filter. For example, it is required that the hash of the task and the raft ID start with
9 zeros. This harms everyone equally (except replenishing attackers) and is therefore fair. This makes farming practically resource-free and requires a very small number of disk reads every few minutes.
Chia users have successfully used multiple PiB storages on a single Raspberry Pi. We assume that farmers still use hard drives because they are cheap and there is no reason to use SSDs since speed has nothing to do with farming. However, SSD/RAM disks can be used for faster scanning.

A raft key is a private key that is stored in a raft file. The raft ID is generated by hashing the public raft key and the public key of the pool. Creating a proof-of-space block requires signatures from both the raft key and the pool key. Therefore, the pool cannot be changed after the raft is created. In practice, a raft key is a cumulative 2/2 BLS public key between the local key stored in the raft and the key stored in the farmer’s software. For security and efficiency reasons, a farmer can run a centralized server using this key and signature scheme. The server can be connected to many harverster machines on which the rafts are stored. Farming requires a farmer’s key and a local key, but not a pool key, since the pool signature can be cached and reused for many blocks.

Verification: After farmer has successfully created a proof of the space, it can be verified by performing some hashing and comparing the x-values of the test. Remember that the proof is a list of 64 values of x, where
each value of x has lengthexcommunicated).

Farmer calculates the necessary iterations for each proof of the existence of a space. If the required iterations <span the iteration interval, the proof of space availability can be included in the blockchain, so the farmer extracts the entire proof of space from disk (which takes more time than just getting quality), creates an incomplete sub block and broadcasts it to the network. Note that the vast majority of required iterations will be too large,
since an average of 32 will meet the requirements for the entire network for each auxiliary slot. This is a random process, so a large amount of evidence can be qualified, but is very unlikely. The iterations of the pointer point are the number of iterations from the beginning of the sub-slot to the pointer point.

The infusion iterations are the number of iterations from the beginning of the sub-slot at which a block with the above quality can be included in the blockchain. This is calculated as:

infusion iterations =( signage point iterations + 3 * sp interval iterations + required iterations) % sub slot iterations

Thus, the infusion iterations will be between 3 and 4 signal points after the signal point. Farmers must submit their evidence and blocks before reaching the infusion point. The module is designed to allow overflow
into the next sub-slot if the alarm point is near the end of the sub-slot. This will be discussed in more detail later.

At the infusion point, the farmer block is combined with the VDF output of the infusion point to create a new input for the VDF from this point, that is, we pour the farmer block into the VDF. The block is fully valid only after the infusion iterations have been achieved and the VDF proof has been attached to the block.

In order for block b1 to be valid/complete, two VDF proofs must be included: one from r1 to the pointer point and one from r1 to b1. (actually more, since there are three VDF lines that will be explained later). In
Figure 5, the farmer creates at the time of placing the pointer (let’s call it B1 ’). However, B1’ is not finished yet, as it needs a VDF infusion point. After the VDF of the infusion iterations is released, it is added to B1’to form a
finished block in B1.

Figure 5: Timelords of time create evidence for both the signage point and the infusion point. But they only infuse (modify the VDF class group) for the latter. Square symbols denote infusions at which a new
VDF is started. Sp interval iterations = 3.125 million

Consider the example in Figure 5. The iterations of the sub-slot are 200 million, and the iterations with the interval sp are 3.125 million. Let’s say a farmer has only 1000 rafts.

For each of the 64 pointer points, since they are transmitted to the network every 9 seconds or every 3.125 million iterations, the farmer calculates the raft filter and sees how many rafts have passed. For each raft that has passed the filter for each pointer, the farmer calculates the necessary iterations. In this example, the farmer receives only the requested iteration <3.125 million once for the entire sub-slot (say 2.2879 million). In Figure 5, this is the 14th pointer point. The infusion iterations are calculated as:

infusion iterations = signage point iterations + 3 * sp interval iterations + required iterations

= 14*3.125M + 3 * 3.125M + 2.2879M

= 55.4129M

Realizing that they have won (at the infusion point 14), the farmer extracts the full proof of the space, sets a lock that does not necessarily include transactions, and transmits it to the network. They have a few seconds (before the infusion iterations) to reach the timelords that infuse the block, creating the infusion point VDF. With these VDF, a block can be completed and added to the blockchain.

Interval iterations Sp: defined as the lower limit (iterations of the sub-slot / 64).

Designation points: 64 intermediate points in time in the sub-slot in the test chains for which VDF are periodically released. At each point of the designation, a VDF output signal is created, which is broadcast over the network. The first pointer in the
sub-slot is the call itself. Each block has a pointer, so the proof of free space in the block must meet the criteria for that pointer.

Required iterations: a number calculated using a quality string, used to select proofs of the presence of space suitable for creating blocks. For the vast majority of proofs of the existence of space, too many iterations will be required, which cannot be included in the chain. This number is used to calculate the infusion point.

Infusion points: time point on infusion iterations from the call point toevidence of the presence of a space with a specific task and infusion iterations. At this stage, the farmer’s block joins the VDF reward chain. The infusion point of the block
is always between 3 and 4 pointer points after the pointer point of this block. Calculated as pointer point iterations + 3 * interval iterations sp + required iterations.

The delay between the designation point and the infusion point has many advantages, including protection from orphanhood and selfish farming, reducing the number of branches and the absence of VDF pauses. This delay of about 30 seconds is given so that farmers have enough time to sign without delaying the VDF slot. Good farmers sign only one notation point with each proof of space, which means that attackers cannot easily reorganize the chain.

Multiple blocks

Figure 7: Multiple blocks. Sp1 = pointers 1

As you can see in Figure 7, multiple blocks can be inserted into the same sub slot. The Chia system focuses on 32 blocks for the sub-slot and this is regulated by an algorithm of the complexity of the work. The VDF moves from the previous infusion point to the current designation point and from the previous infusion point to the current infusion point. Note that the VDF proofs required for each block, they may overlap. For example, B2 contains a proof of VDF from B1 to sp2 and from B1 to B2. B3 contains a proof from B1 to sp3 and from B2 to B3. B2 does not depend on B3 at all, but B3 depends on B2, since its VDF comes from the infusion point B2. Again, blocks are created at the points of
pointers, but there is no VDF infusion point in them; as soon as this VDF is added, the block is completed and forms part of the blockchain. There are no signatures at the infusion point; the only thing that is added to the infusion point is VDF.

Three VDF chains

If we used only one VDF (for the reward chain), including or excluding blocks would allow us to control the task for the next slot. This means that an attacker can try many different combinations
and choose the most suitable task for him. These types of attacks are called grinding attacks, and they are one of the main difficulties of moving from Proof of Work to Proof of Space or PoStake. More detailed
information is provided in the section « Attacks and counteraction measures ».

To mitigate this, the problems will be based only on the first block to be added to the slot.

Figure 8: Three VDF chains. An attacker can manipulate the results of the reward chain, but this does not affect c2 and therefore does not affect the PoSpace lottery. cc = task chain, rc = reward chain, sp = pointer point. B = block.

There’s a lot going on in this diagram. First of all, as you can see, there are 4 blocks: B1, B2, B3, B4, these are blocks created by farmers that contain all the data they point to. We assume that more than 5 blocks have been created in this sub-slot, but we don’t draw them all due to lack of space.

In addition, both the task chain and the reward chain create 64 pointer points. The blocks must include VDF point designations for both chains. The blocks should also include VDF infusion points for all three chains.

As you can see, the call chain executes VDF from the beginning of the sub-slot to the end without adding anything to it (circles — proofs of VDF, but they do not interrupt VDF). The reward chain permeates each included block. The chain in the middle is called the chain of added calls, and it starts with the first block entered for each task and continues until the end of the slot.

Slot — is a list of sub-slots that contain at least 16 blocks of the reward chain based on the task of the first sub-slot or later sub-slots. For example, we can have only 10 blocks in a sub-slot, and then 3, and then 7, which means that these three sub-slots form one slot. Usually each sub-slot is also a slot, since on average much more than 16 blocks are included. The deficit is the number of blocks that is still needed to complete the slot: this
will be described in more detail below.

At the end of the time interval, the call chain is merged with the embedded chainoops calls to generate a new c2 call, which is used to start the call chain for the next sub-slot.

The only block that affects the call chain is the first block, which in this case is B1, and only the deterministic part of B1, cc B1, which depends only on the data of the call chain. An attacker who wants to be ground cannot change the task by holding B2, B3 or any other block except the first one.

Assuming that the attacker has the fastest block (B1), he has three options: hold it, postpone it, or let it go. To find out if a new task will benefit them, they will need to complete the VDF all the way to c2. By that time, they no longer have a chance to get into the reward chain, since honest farmers sign only one block for each proof of space. Holding B1 does not give the attacker much benefit, since he must release it
before sp2 in order to include farmers in his chain. Farmers will choose the heaviest chain, which will have the most (heaviest) blocks of the reward chain.

Why do we commit to any blocks in the task chain at all? Well, if we didn’t, the attacker could look to the future with a faster VDF, since they wouldn’t need the help of honest participants
to calculate the call chain in the future. The call chain will be completely deterministic. This would give some advantage by re-plotting the graph. In addition, the task chain can be used to probabilistically prove the weight of the reward chains for simple clients without separating all the blocks of the reward chain (since the call chain depends on the « best » block in the slot, you can calculate the number of rewards of the chain blocks).

Task chain: A VDF chain based on each task for each sub-slot, which does not pour anything into the middle of each sub-slot. Calls are also used to prove the space. Pointers in this chain are used
for the SP filter.

Reward Chain: A VDF chain that contains infusions of all blocks. This chain pulls in a chain of calls and possibly a built-in call chain at the end of each sub-slot.

Filling the task chain: a VDF chain that starts with the first block inserted into the slot (which is not based on calling the previous slot, this is called a call block) and ends at the end of the slot.

Slot: a list of sub-slots that contain at least 16 blocks of the reward chain based on the task of the first sub-slot or later sub-slots. At the end of the slot, the chain of entered calls stops, the call chain pulls the result of the entered call chain, and the deficit is reset to 16.

Block: block — is a set of data entered into the reward chain, which contains: proof of the existence of a hash space for a task with fewer iterations than slot iterations, VDF sp and ip for both chains, optional IP VDF
for the embedded call chain, and address rewards. Some blocks are also transaction blocks. Maximum of 128 blocks per slot.

Transaction block: a block that has the right to create transactions together with a linked list of transactions.

Call block: the first block to be added to each slot that is not based on the call of the previous slot. The call block always has a deficit of 15, and always starts with a chain of entered calls.

Peak: the peak of the blockchain from the point of view of the node is the block with the highest weight. The weight is the sum of the complexity of the block and all its ancestors, which is similar to the height, but a shorter chain may have more weight due to the complexity of the setup.

In order for a block to be considered valid, it must provide a VDF for the call chain and reward chain and, optionally, for the embedded call chain, if present. Forcing all VDF to be enabled means that all three chains will move forward at the same speed.

Overflow blocks

In order for the farmer to create a block, their required iterations must be less than 3.125M, or the number of iterations of the sub-slot / 64, as described above. This means that there may be more infusion iterations than sub-slot iterations, and therefore the infusion
should occur in the next sub-slot.

Overflow block: a block whose infusion point is in a different sub-slot, unlike its pointer point.

The task of the current slot: with respect to a certain block B, the tasks of the current slot B include all tests starting with the first task in the slot and ending with the end of the slot (not inclusive). This is relevant because sometimes a slot
spans multiple sub-slots and hence multiple problems.

Figure 9: B4 in this diagram represents an overflow block as the infusion is in the next slot. B4 is not based on calling the current slot and thus does not reduce the deficit or create a call block. TODO:
there should be 16 diagrams, not 5.

Overflow blocks cannot exist in the first sub-slot of the epoch (since the iterations of the sub-slot change).

In addition, overflow blocks do not change the deficit unless they are based on a call to the current slot, since overflow blocks are responses to a call to the previous sub-slot. Overflow blocks are not request blocks unless they are
based on the current request slot. Note that overflow blocks rarely reduce the deficit, as the deficit will almost always decrease to zero, and a new slot will be started in each sub-slot.

Minimum requirements for the block

At least 16 task blocks of the current slot must be added to the reward chain in order for the slot to be completed.

The deficit is a number from 0 to 16, which is present at the beginning of the sub-slot. This is defined as the number of reward chain blocks that we need to add to finish the slot. It resets to 16 whenever we
start a slot (so there must be at least 16 total blocks per call chain injection). The deficit decreases for each infusion of the reward chain based on the task of the current slot.