In this document I plan to outline what was discussed at the meeting on May 17th.
We discussed and came to the common conclusion that there will be the main L1 chain Undchain which:
- Works according to BFT principles
- Has a set of validators - known and unknown. This common set of validators rotates once per epoch and creates an active validators set and a passive validators set.
Active set - participate in consensus, create blocks and vote for them
Passive validators set - are idle and monitor the chain progress, help in network stability (against DDoS, etc.), but do not participate in consensus and do not generate blocks
- Clients and partners publish receipts in the blocks of this blockchain
- Through this blockchain, you can initiate transactions (address-address), call smart contracts, etc.
- Co-chains can interact with this L1
This blockchain serves as the main point of synchronization and sequencing for the entire system - having a clear sequence of blocks in this blockchain where each block has the correct timestamp, the system can progress consistently - block 0, block 1, block 2, ..., block N
Regardless of the node type (validator or regular node), 2 files are required:
- Genesis - a common entry point for all
In the genesis, you can specify: initial balances, first validators, known validators, configure tokenomics, etc.
- Configuration - an individual file for each
In the configuration, you can specify: network interfaces and ports, public/private key, other auxiliary options
In this section we'll look at how the system will work at a high level, and then move on to the necessary details.
A block is a collection of transactions. It is created by a validator at a given frequency. Then the sequence is as follows:
- The creator sends the block to validators for approval
- Waits for 2/3 of the responses
- Having received 2/3 of the signatures, aggregates them and uses them as proof of acceptance of the block
- The rest of the network can receive such a block and proof of its acceptance, get transactions from there and execute them, changing the local state
Visualization
State modification
There can be any types of transactions, recipes from clients & partners, etc. The main thing is that they change the state sequentially
An epoch is a fairly long period of time - several hours, one day, etc. within which:
- There is one selected active pool of validators (quorum for this epoch)
- There is a sequence of block generators
Let's see how the system will change from epoch to epoch:
In simple words, each new epoch we will have a large list of validators in the system. From this list we choose:
- A random subset for the active validators set
- A random subset for the block creators sequence
We start the epoch by selecting 2 sets from the entire available set of validators:
- Active validators set
- Sequence of block creators
Next, we divide the entire epoch into equal time periods - slots. Each slot is assigned a block creator
In reality, of course, it is worth making such slots small in time - for example, 1 minute, to avoid a situation of network downtime if the creator of the block is inactive or malicious
Within this timeframe, the block creator can generate blocks. Such blocks must be linked to each other - each subsequent block includes the hash of the previous one
The image below shows the process of generating blocks within epoch 5 (the index is taken as an example)
As you can see, each block creator starts their own sequence when it's their turn. It is worth saying that each subsequent block includes the hash of the previous block in the sequence, BUT ONLY IN ITS OWN
Rotation plays an important role because it allows the system to:
- Change active validators
- Change the order of block creators
Rotation must be pseudo-random so that third-party observers can recalculate everything in a deterministic way and get the same set of active validators and the sequence of block creators
We will use the hash of the first block as a source of pseudo-randomness. Therefore, we need a special function that takes as input the hash of the first block and the total set of available validators, and as output gives:
- A subset of active validators for a given epoch
- A sequence of block creators for a given epoch
We will do such a recalculation at the beginning of each epoch
So by now you should have some general understanding of the system. Let's look at the big picture - let's imagine that the network is ALREADY WORKING
Let's imagine that to begin with we have a genesis file that specifies the initial list of validators, as well as the physical servers of these validators
You can think of this as a list of known validators
Here is a detailed, but still GENERAL diagram of how the system might work
Initially - take the data from genesis. Using special function and zero_hash (for example 0x00000000) we can build 2 lists - active validators set and block creators sequence
During the next 1 hour the network will work like this:
- Sequence of block creators was set
- Each block creator has own timeframe to generate blocks
- Each block creator will send his own blocks to active validators set to confirm block and add to blockchain.
- To confirm block the block creator should get 2/3 proofs from active validators set
- The hash of first block in this epoch (violet block) will be used as a seed to calculate the active validators set and block creators sequence for next epoch
Take a look at this segment of picture
This shows how network will move from epoch 0 to epoch 1, so demonstrate the epoch rotation process
Here's how the process work (high level):
- Take the hash of first block on epoch 0 (violet block)
- Once the time is approximately 14:00 - the active validators set of epoch 0 (blue section - Node1, Node3, Node7, Node8, Node10) start exchanging special proofs to move to next epoch (omit this moment right now, will discuss it in next sections)
As you can see we use the hash of first block in epoch 0 to build all we need for epoch 1. Via this block we can also change the whole validators set
Take a look at the full list of validators in system
For epoch 0
For epoch 1
As you can see, for epoch 0 we take the initial validators from genesis. But for epoch 1 we can see new validators in system (Node 54, Node 19, Node 82) and lack of old validators (Node 5, Node 9, Node 8)
THIS IS SUPER IMPORTANT MOMENT WHICH SHOWS YOU HOW WE CAN UPDATE THE LIST OF ALL VALIDATORS
Once again:
- Green arrow shows that from special transactions in the first block in epoch 0 we'll extract operations to add/delete validators from the registry
- Red arrow shows that the hash of first block in epoch 0 will be used as a seed to calculate the active validators set and block creators sequence for epoch 1
This mechanism let us to add/delete new validators - known, unknown, doesn't matter. We can also regulate the perception score and modify it via this mechanism to make the system deterministic.
For example, during the epoch life the validators can ping each other to check if validator is online/offline and do useful work for system.
Then we can collect this votes, add to the first block and this data will be used for next epoch
We remember this general scheme
Let's imagine that we are in epoch 0 and we are the very first block generator. That is, we are discussing this - interval from 13:00 to 13:15 :
- Block creator sends his block to active validators set
- Each validator sign the block id + hash - to prevent forks
- Validator sends back the signature as a proof like "I am validator, I accept the block candidate and it's ok"
- Block creator (Node3 here) collects 2/3 signatures and get a proof that block is confirmed
- To send next block, block creator should include these 2/3 signatures as a proof that previous block was accepted. Only when block creators share his first block (with index 0) there is no such proof - it's should be obvious.
Let's take a look interaction for pair - block creator (Node3) and validator(Node1). Here you can see that the first block do not need 2/3 proof but the second one need it
Let's imagine the situation: let's say we have 3 validators [Node1, Node2, Node3] and Node1 was offline during voting for block 0, block 1 and block 2 so these blocks have proofs of confirmation like [signa2, signa3] (what is still 2/3 so enough to finalize block)
Then, during voting for block 3, Node1 is online again, but locally Node1 don't have any knowledge about previous blocks by block creator.
Therefore, when block creator sends block 3 and 2/3 proofs for block 2 - Node1 which has zero knowledge about blocks 0,1,2 - can still vote immediately for block 3. It's O(1) complexity thanks to 2/3 signatures which proofs that:
"Bro, the blocks sequence block0, block1, block2 is sequence and valid and confirmed by majority (2/3), so please, vote for this block (block 3)"
Let's now look at the moment of block creator rotation. The most important part here is that each subsequent block creator must include in their title
We need to somehow connect 2 such sequences of blocks from different creators in order to get a complete blockchain.
That is why we come to such a term as ALRP - Aggregated Leader Rotation Proof
ALRP is a proof that contains 2/3 of the signatures that the network has finished confirming blocks for the previous leader at height X and hash Y
This proof must be included in the first block. In our illustration, the first validator was Node3, and the second was Node5
Therefore, Node5 must include ALRP for Node3 in its first block
This is what it will look like:
- Once the time is 13:15 (so Node3 should stop block generation and Node5 should start) - Node5 sends message to active validators set and propose to sign ALRP
- Once Node5 get 2/3 signatures - add it with ALRP to his first block header
- Node5 continue to generate next blocks
Situation looks like this. Remember our sequence:
Node3, Node5, Node6 - now imagine that Node5 is AFK (offline, malicious, etc.)
This is what happens next:
- Node6 needs to get the ALRP for all the previous block creators untill the leader which created at least one block
- In our case Node5 didn't created blocks, so Node6 needs to include to his first block ALRPs for Node5 and Node3
- Since Node6 see that Node3 created at least one block - then it's ok and it's possible to generate next blocks - block 1, block 2 ....
- This helps us to make possible to have a clear understanding about blocks sequence
Now that we know about the process of block finalization, about the process of rotation of the block creator - we can move on to the final points. We will talk about the epoch rotation
We'll focus on this part because we only need to take a look a rotation from epoch 0 to epoch 1 - the following rotation will works absolutely the same way:
Here you can see that at the beginning of epoch 0 we will get the first block (violet block)
That's why approximately on 13:00 we'll know the hash of this block and based on this hash & block - we can calculate the active validators set and block creators sequence FOR NEXT EPOCH (WITH INDEX = 1)
This process is shown below with red and green arrows
Why it's important moment - because it shows that we can calculate the active validators set and block creators sequence for NEXT EPOCH (epoch index = 1) before THIS EPOCH (epoch index = 0) will be finished
Next we keep working untill the end of epoch - untill 14:00 here
Also, let's imagine a real world scenario that Node5 and Node1 was offline of malicious and created no blocks
So, from this picture it's easy to assump that the first block of epoch will be created by Node3 while epoch will be finished (de-facto) with blocks by Node6
Approximately in the end of epoch 0 - current validators set understand that it's time to finish it. They starts to exchange special data and once majority agree - this proof can be sent to next epoch active validators set.
This will be the signal for epoch 1 that it's time to start new epoch
The proof which active validators set will try to get in the end of epoch 0 called AEFP - Aggregated Epoch Finalization Proof
AEFP - Aggregated Epoch Finalization Proof - is a proof that 2/3 of validators set is agree to finish epoch N on block X with hash Y to move to epoch N+1
Don't worry if hard - I'll explain. When it's time to finish epoch (epoch 0 in our example) what should be done?
Remember that we decided to imagine situation like this:
So, imagine that our epoch will finish on Node6
For example, node8 sends proposition to node10. In case node10 is ok with AEFP verification - sign this message and send back the signature
There may be situations when, say, node8 was offline during voting for node3 and node5 (which created 0 blocks).
In this case:
-
The members of the active validators set (except node Node8) will have information that the last block was block index=4 from Node6
-
Node8 will have information that the last block was, say, index=2 from Node3
In this case, communication from Node8 to Node10 will look like this:
- Once Node10 receive WRONG proposition - it sends back the more actual info
- In UPGRADE message Node10 informs Node8 that network progressed more than Node8 thinks
- Everything in UPGRADE message can be proven - the first part (about last block) is proven by 2/3 of signatures by active set majority. We receive this data during [[#Voting for block in general]]
hashOfFirstBlockByLastCreator
also can be proven - using same principle (see [[#Voting for block in general]])
Just send the AEFP with 2/3 signatures to next active validators set
On this step new epoch should start - with new active validators set, new block creators sequence and so on
It's crucial moment because we need AEFP to connect epochs with each other
EACH BLOCK CREATOR NEEDS TO INCLUDE AEFP PROOFS TO HIS FIRST BLOCKS TO GET A 100% GUARANTEE OF SECURITY AND CHAIN INTEGRITY
Let's take a look at the block creators sequence for epoch 1
In this case we de-jure mark with orange color the first block but de-facto, remember the cases when nodes can be offline/malicious. In this case it's a rule - each block creator should include AEFP for previous epoch to own first block:
So, we have mentioned several types of proofs:
Proof that 2/3 of the active validators set agree with the block B created by block creator C. This block has index I and hash H
This is what we get during finalization of blocks
Proof that 2/3 of the active validators set agree to finish finalizing blocks creator C at index I and hash H and are ready to move on to finalizing blocks of the next block creator
This is what each next block creator includes to his first block.
Note: In case you're the first block creator in sequence - you shouldn't include something because there is no other block creators before you
For example in epoch 2, the Node2 shouldn't include any ALRP because it's the first block creator
In epoch 0 (below):
- Node3 - no ALRP
- Node6 - should include ALRP for Node5, Node3
BUT
If the Node5 created at least one block then:
In this case Node6 can include ALRP for Node5, but no need to include for Node3
Proof that 2/3 of the active validators set agree that it is time to end the epoch on block creator C, index of its last block I and hash H
This is what each block creator includes to their first block
Note: In case it's epoch 0 - no one should include AEFP to header - because it's the first epoch so no previous epoch exists
Take a look:
To know how to modify the state, we need to have a clear understanding which block is the first, the second, the third and so on.
Because of async, distributed, permissionless nature of L1 blockchain some specific algorithms should be used to use the blocks from block creators and majority proofs and based on this - build the traditional sequence of blocks.
In the previous chapters, we looked at the mechanism of block generation, rotation of block creators and changing the epoch.
All this perfectly shows how to keep block generation - from creator to creator and from epoch to epoch.
However, the question remains unclear:
How can we now have a clear understanding of the block sequence?
In the previous chapters, we got acquainted with different types of proofs - AFP, ALRP, AEFP.
It is on their basis that we will be able to apply special algorithms to resolve the sequence and have a clear idea of the first, second, third and so on blocks.
First, we should think of the block processing system as a black box that takes 2 things as input:
- Block itself
- Cryptographic proof that the block is indeed should be the next one in sequence.
Only with this pair we can extract the transactions inside the block and safely execute - this will change the local state.
The whole secret of the block ordering system will lie in this place
At first glance, it may seem that this is a simple AFP (Aggregated Finalization Proof) - just 2/3 of the signatures from the active set of validators approving this block.
However, this is not always the case - and we will discuss this further.
Let's recall our general scheme of network workflow
![[Intermediate_General.svg]]
So, since we have both block creator rotation and epoch rotation, we need to somehow organize the created blocks to simply get a sequence like this:
block 0
block 1
block 2
...
block N
Now let's pay attention to the right part of the image.
In an ideal world, the sequence of blocks would look like this:
But in reality, it is worth remembering that:
- Some block creators may be inactive
- The diagram CONDITIONALLY shows 4 blocks created by each creator, but in reality their number depends on the timeframe of the block creator and the block time.
For example, if a maximum per one creator is 100 blocks during a time interval (green timeframe in the figure), then there may be situations where someone creates 100 blocks, someone 74, someone 89, and so on.
For example, here is a situation that could be real
In this situation:
- In epoch 0, the creator of Node6 was malicious, and in epoch 1, Node4 and Node6 were offline so they did not create a single block
- In epoch 0, Node5 created only 3 blocks, and Node1 created six blocks.
- In epoch 1, Node7 created eight blocks, and in epoch 2, Node4 created two blocks.
To begin with, we will consider only single epoch. Let's assume (for simplicity) that it is infinite epoch and our only task is to understand how to resolve the sequence of blocks.
So we have this epoch
As long as your local clock shows the timeframe of the current block creator (in our case, it's Node3, so the time is about 13:00-13:15) - you can simply send requests to the network to get a block and AFP for it.
Remember that Node3 (current block creator) generates blocks and sends it to active validators set for finalization.
Remember the AFP structure (pseudocode - Golang):
type AggregatedFinalizationProof struct {
PrevBlockHash string `json:"prevBlockHash"`
BlockID string `json:"blockId"`
BlockHash string `json:"blockHash"`
Proofs map[string]string `json:"proofs"`
}
This is the example of AFP for block 0:Node3:0
afp0 := AggregatedFinalizationProof{
PrevBlockHash: "000000000000000000000000000000000000000000000000000000000000",
BlockID: "0:Node3:0",
BlockHash: "abcd1234efgh5678ijkl9012mnop3456qrst7890uvwx",
Proofs: map[string]string{
"validator1": "signature1",
"validator2": "signature2",
"validator3": "signature3",
},
}
And AFP for block 0:Node3:1
afp1 := AggregatedFinalizationProof{
PrevBlockHash: "abcd1234efgh5678ijkl9012mnop3456qrst7890uvwx",
BlockID: "0:Node3:1",
BlockHash: "ffff1111aaaa2222bbbb3333cccc4444dddd5555eeee",
Proofs: map[string]string{
"validator1": "signature1",
"validator2": "signature2",
"validator3": "signature3",
},
}
So, your local system will do the following:
- Quickly poll the network for new blocks and proof of finality (AFP)
- Once you receive a block and AFP for the next block, you can perform transactions inside and be 100% sure that the state is finalized
- Just get the hash of block
0:Node3:0
and compare with hash inside AFP for block0:Node3:1
Like this
if hash(Block("0:Node3:0")) == afp1.PrevBlockHash) {
// execute txs inside block
}
Due to some features of the consensus, we cannot know for sure on which block the set of active validators finished voting.
That is why, in order to know for sure which block of one of the creators was the last one, we must take this information from ALRP (Aggregated Leader Rotation Proof).
If you remember from the previous pictures, we indicated that:
In their first block in the epoch, each creator must include ALRPs for previous creators
Here is a picture to remind you this:
If the essence of ALRP was previously unclear to you, now its role is clear. It is needed to maintain the integrity of the chain
Let's say in our core source code, in a separate thread, there is a mechanism that constantly polls active validators about the next block creator.
For example, if we know that Node3 is currently creating blocks. But at the same time, we send requests to active validators to ask if they have switched to Node5
When the time is more than 13:15, then the next scenario is possible
Once we have received from the active validators set:
- The first block from Node5 (its ID will be
0:Node5:0
) - And AFP on block
0:Node5:1
- From block 0:Node5:0 - get ALRP for Node3
- From this ALRP we check that 2/3 really voted for it
- Take data about the last block and hash and compare with our local state
- Let's say we have already processed blocks up to 0:Node3:27 locally, while in reality the validator set confirmed up to block 0:Node3:30
- All that remains for us is to download blocks 28,29,30 from the network and process the transactions inside them
After that, already knowing that Node3 finished work in epoch 0 at height 30 - you can move on to searching for blocks from Node5
Sometimes a situation like this may occur on the network:
In this situation it becomes clear why each block creator should include ALRPs FOR ALL THE PREVIOUS BLOCK CREATORS UP TO THE CREATOR WHO CREATED AT LEAST ONE BLOCK
If we look at the figure above, using the ALRP proofs for Node5 and Node3 we can get the following sequence
Block 0 - 0:Node3:0
Block 1 - 0:Node3:1
Block 2 - 0:Node3:2
Block 3 - 0:Node3:3
Block 4 - 0:Node3:4
Block 5 - 0:Node6:0
Block 6 - 0:Node6:1
Block 7 - 0:Node6:2
Block 8 - 0:Node6:3
Block 9 - 0:Node6:4
In the first part we explained how to understand and verify the sequence of blocks within one epoch, but between rotations of block creators.
In general, the algorithm can be described as follows:
- While the timeframe for Node_X - look for AFP for the block and execute it
- When the timeframe for Node_X is finished - look for the first block of Node_X+1 (the next block creator), extract ALRP from there and based on this proof - complete the execution of the sequence for Node_X
- When finished - start looking for AFP for blocks created by the new creator (Node_X+1)
Now it's time to link blocks between different epochs. We will discuss this in the second part of the algorithm.
Now we need to look at how to resolve the block sequence between epochs. This is slightly different from what was shown earlier for one reason - in the next epoch, the active set of validators will be different. So we can't go the same way as in the first part of the algorithm where we discussed events within one epoch
Let's get started
Let's recall our previous images for epoch 0 and epoch 1
This is general scheme which shows how to use the hash of first block in epoch X to calculate required data for epoch X+1
Remember that we are working with the "real" scenario of epoch 0 which looks like this:
Using the algorithm mentioned in the previous part - we can use a chain of ALRPs to have a 100% guarantee of understanding which block was the first.
Because each ALRP also includes the hash of first block created by appropriate creator:
type AggregatedFinalizationProof struct {
PrevBlockHash string `json:"prevBlockHash"`
BlockID string `json:"blockId"`
BlockHash string `json:"blockHash"`
Proofs map[string]string `json:"proofs"`
}
So on this step we know that the first block on epoch 0 was violet block:
Based on this hash - get the active validators set and block creators sequence for next epoch:
Like this
As we discussed in previous chapters [[#So, what the sense of getting AEFP|here]] - every first block in a new epoch must contain an AEFP that will point to the previous epoch
Let's formalize the AEFP structure
type AggregatedEpochFinalizationProof struct {
LastCreator uint `json:"lastCreator"`
LastIndex uint `json:"lastIndex"`
LastHash string `json:"lastHash"`
HashOfFirstBlock string `json:"hashOfFirstBlockByLastCreator"`
Proofs map[string]string `json:"proofs"`
}
AEFP for epoch 1 might look like
aefp := AggregatedEpochFinalizationProof{
LastCreator: 3, // index of Node1 in block creators sequence in epoch 0
LastIndex: 5, // index of last block by Node1 in epoch 0
LastHash: "abcd1234efgh5678ijkl9012mnop3456qrst7890uvwx", // hash of block
HashOfFirstBlock: "aaadsaddfsdfdsfdfsdsfgdfgdfgdfgdfgdfgdf", // green block
// This proofs is signed by active validators set of epoch 0
Proofs: map[string]string{
"validator1": "signature1",
"validator2": "signature2",
"validator3": "signature3",
},
}
Now we just have to wait for the first block in the new epoch, as well as the proof of its finality (AFP). There are only 2 possible scenarios:
- The first block of the new epoch will be the block from the first creator (Node4 in epoch 1)
- The first block will be the first block of one of the next creators (let's say Node1 in epoch 1)
- We just take the
aefp.LastIndex
andaefp.LastCreator
to build the ID of last block - it's0:Node1:5
in this case - Then we fetch this block from network and compare hashes - must be the same as
aefp.LastHash
- In
aefp.HashOfFirstBlock
we also have the hash of first block by Node1 in epoch 0 - the ID of this block will be0:Node1:0
. Just compare hashes and extract the ALRP from this first block - this let you to understand were Node5 finished, from first block of Node5 - where Node3 finished and so on
If Node4 created no blocks - AEFP will be in the first blocks of next creators (Node1 or next creators)
- From block
1:Node1:0
(first block in epoch 1 by Node1) - take the ALRP, verify and understand that Node4 in epoch 1 created no blocks so we can ignore him - From the same block - we take the AEFP which points to latest block in previous epoch
- We now know the latest block in epoch 0 and from AEFP - have the hash to first block by last leader in epoch 0 (green block).
- From this block we can extract the ALRP for Node5 and understand the final block by it and from first block of Node5 (blue block) we can get the ALRP for Node3 and understand where it finished
In this large chapter we have shown a mechanism that using different types of proofs - AFP, ALRP and AEFP can unambiguously resolve a sequence of blocks so that each node in the network can precisely synchronize the sequence and obtain a local sequence of the form:
Block 0 - 0:Node3:0
Block 1 - 0:Node3:1
Block 2 - 0:Node3:2
Block 3 - 0:Node3:3
Block 4 - 0:Node3:4
Block 5 - 0:Node6:0
Block 6 - 0:Node6:1
Block 7 - 0:Node6:2
Block 8 - 0:Node6:3
Block 9 - 0:Node6:4
... (and so on)
In this large research was showed the process of creating an L1 chain that follows the principles of BFT consensus.
I tried to mention and visualize all the details necessary for understanding and creating a blockchain.
We went from the initial launch of epoch 0 and data in the genesis to the development of the chain up to epoch 2 - to show the rotation of epoches. Further development of the network (to the next epoches) follows the same principles
It was also mentioned:
- The process of calculating the active validators set and block creators sequence
- The process of collecting proofs for finalizing a block is demonstrated
- The process of rotating the block creator and the necessary proofs for this is shown
- The process of rotating the epoch, the process of collecting proofs and further work of the network in the next epoches is shown
Additionally, this document can be expanded with a section "Assembling the pieces" (like in OffSec manuals) in which to collect all the mentioned sections and simulate the process of network workflow along with visualization.