Understanding Input Endorsers

In the article, we will explain why the first-generation consensus algorithm of blockchain scales so little and what is the main cause of inefficiency. Next, we will show how Input Endorsers incorporate elements of parallelism and concurrency into the consensus while maintaining the linearity of the blockchain.

Efficient Use of Resources

The Cardano distributed network consists of nodes that provide their computing resources to the network. However, these resources are not effectively used in the current version of the Proof-of-Stake (PoS) consensus, as it is based on the algorithm that came with the first generation of blockchain.

The Cardano network mints a block on average every 20 seconds. In this time period, a single block producer is randomly drawn each time to mint a new block. All other nodes are block validators. Block validation takes roughly 50-100 milliseconds.

This algorithm can be seen as a waste of a lot of computational power and network bandwidth. This causes the nodes' CPUs to be idle for most of the time, except for a brief period when the node either mints or validates the block. Using available network resources in a 'spiky' fashion leaves them underutilized.

In the description, we neglected the resources needed to solve slot battles (multiple blocks are minted in one period) and the diffusion of transactions.

First-generation blockchain networks place valid transactions in mem-pools. Once per period, one randomly drawn block producer can only take a limited amount of transactions and put them into a block. Block size is limited, so it may not fit all available transactions. As soon as transactions start remaining in the mem-pool, users have to wait for settlement for a longer time.

The larger the block size, the longer the diffusion in the network. A block must reach all nodes in the network as quickly as possible to be available as an ancestor for a new block.

Simply put, with this simple consensus algorithm, the scalability of the blockchain is determined by the frequency of block production and its size. For example, 90 kilobytes every 20 seconds in the case of Cardano or one megabyte every 10 minutes in the case of Bitcoin.

In the image below you can see the time divided into slots (seconds). In the Cardano network, 1 new block is minted on average every 20 seconds. Nodes are idling most of the time (empty slots indicate idle nodes).

Network resources could be used in a parallel way, but the algorithm described above is sequential. The use of a sequential algorithm in a parallel system necessarily leads to inefficient use of resources.

Blockchain is linear, as each newly added block builds on the previous block. This is a consequence of the fact that data dependencies (especially transactions) are also linear in nature during validation. Let's show it with an example.

Once funds (UTxO) from address A are moved (thus spent) to address B in transaction 1, it is not possible for the same funds to be moved from address A to address C in transaction 2 a moment later. Only transaction 1 or transaction 2 must enter the ledger, but not both. In such a case, new funds would be created out of nothing.

A distributed network must prevent double-spend attacks (an attempt to spend funds twice) in a decentralized manner. This is currently achieved in many blockchain networks through a sequential algorithm described above. The inefficiency comes from the fact that as users use the network in parallel, i.e. transactions (and other data) appear on the network continuously and in parallel.

The main reason for the low scalability of blockchains is the use of a sequential algorithm in a network in which data is generated in parallel by users and in a relatively large amount (with a higher adoption, the amount of data is expected to grow). Sequentiality only applies to block production. Validation of new blocks can take place in parallel.

A distributed network can be perceived as a parallel system from the point of view of users (data generators), but also from the point of view of nodes that can work on mutual consensus to a certain extent independently of each other (they process data). In other words, achieving a unified global state requires synchronization and communication that takes place over a certain amount of data. If we increase the amount of data on which consensus is formed, we also increase scalability.

Cardano uses a UTxO-based accounting model. Transactions in UTxO ledgers explicitly identify all of their inputs and outputs up front, and those dependencies are complete. Finding transactions that conflict with each other is straightforward. Non-conflicting transactions in the block can be reordered, i.e. validated in a different order or in parallel, regardless of the validation result. It is relatively easy to create a provably secure algorithm using concurrency and parallelization in such a way as to simultaneously ensure the correctness of the data in the ledger.

It is therefore possible to create a distributed parallel algorithm that will process transactions concurrently. This means being able to process transactions and build the blockchain from the moment users send them to the network.

However, a certain linearity of the system must be maintained on the ledger level due to transaction dependencies. The algorithm must partly remain sequential because the structure of the blockchain must remain linear (protection against double-spend attacks).

Input Endorsers bring a novel distributed algorithm enabling parallel data validation. However, current algorithms can already do that. In addition, The Input Endorsers feature will allow the concurrent development of the blockchain structure at a lower level while ensuring that it remains linear at a higher level. The degree of concurrency in the blockchain structure is limited by transaction dependencies.

The Input Endorsers algorithm allows the network to achieve both parallelism and concurrency in processing transactions through the use of multiple types of blocks. Parallelism means that multiple tasks can run at the same time, while concurrency means that multiple tasks can make progress in an overlapping time period.

The Input endorsers feature enables parallelism by allowing multiple transactions to be validated and endorsed (will be explained later) simultaneously by different nodes. It also enables concurrency by allowing multiple blocks to be produced and propagated in each slot. Different types of blocks, such as ranking blocks and endorsement blocks (which will be explained later), can be minted in parallel by different nodes and then sent to the block producers for inclusion in the ledger. This can increase the throughput and performance of the Cardano network while maintaining robust security properties.

Changing the algorithm, i.e. using parallelization and concurrency, is the only option to increase the scalability of the blockchain. It is not possible to increase scalability by reducing the frequency of block production, or increasing the block size, as it will soon hit the limits (especially the current capabilities of the Internet). Partial adjustments are of course possible, but the quality impacts of all network attributes must always be carefully considered. In addition, these adjustments can achieve only a slight improvement in scalability compared to changing the algorithm.

Changing the algorithm will make it possible to make better use of the resources that are already available for the Cardano network (1200 active pools). More efficient use of resources will bring higher scalability.

The Input Endorsers Features Use Three Types of Blocks

The Input Endorsers feature uses 3 types of blocks: Input Blocks (IB), Endorsement Blocks (EB), and Ranking Blocks (RB). Since block minting is a random process in the Cardano network, it may happen that some block types will be minted in parallel in one slot. Each type of block will have a different minting frequency set.

Most often, input blocks will be minted in the range from 0.2 to 2 seconds. Endorsement blocks can be minted every 5 to 10 seconds. Ranking blocks will have a similar function to the current blocks and will be minted between 15 and 30 seconds. Exact minting frequencies are currently unknown and will probably be adjusted as needed. It can be expected that they will be set conservatively at the beginning.

In the image below you can see the possible minting frequency of all block types. Input Blocks (IB) are minted every second. Endorsement blocks (EB) are minted once every 5 seconds. Ranking blocks (RB) are minted once every 20 seconds.

A randomly drawn node can produce an input block in a given slot. A node takes a sequence of transactions from its mem-pool. These transactions must be valid with respect to the current state, i.e. with the recent ranking block (from the node perspective it should be the last one). As we will explain below, ranking blocks ensure the linearity of the blockchain. Input blocks are minted with respect to the current state of the ledger, i.e. with respect to the last ranking block.

Input blocks reference the last (or recent) ranking block. From the point of view of the correctness of the data in the ledger, it must be possible to add new transactions from input blocks.

The purpose of input blocks is to carry the blockchain payload, i.e. mainly transactions and certificates. Besides a sequence of transactions, each input block also contains references to a recent ranking block. The reference is included to make it explicit in which ledger state to use to validate the transactions in an input block. Transactions within an input block can depend on each other.

In the picture below you can see that the input blocks are minted with respect to the last ranking block.

Note that every second, one node in the network can empty its entire mem-pool, provided that the transactions fit into the Input block. The frequency of emptying the mem-pool is significantly faster than the first-generation consensus algorithm.

Once a node mints a new Input block it sends it to the network to other nodes.

As soon as other nodes in the network receive the input block, they can validate it (transaction, signature of the block producer, VRF proof, etc.). Validation takes place with respect to the current state ledger, which should be the same ranking block that references the Input block.

Input blocks are generated most often in the network (it can even be up to 5 times per second), so they are independent of each other. This means that nodes can validate them independently of each other.

Nodes can be randomly drawn to mint an endorsement block. The purpose of endorsement blocks is to speed up agreement in the network regarding the existence and validity of input blocks.

Endorser nodes take references to all recent input blocks that are valid and that were not already included in another endorsement block and create a new endorsement block. Endorser nodes can occasionally also reference other endorsement blocks if they have not yet been referenced in the ranking block. In order for referencing to be possible, both endorsement blocks must be compatible with each other.

Let's show it for example. At time T, endorsement block EB-1 is minted, which references input block IB-1. At time T+1, another endorsement block EB-2 is minted which references an input block IB-2. Both IB-1 and IB-2 have no conflicting transactions, so EB-2 can reference EB-1 as its parent block. This way, EB-2 becomes a child block of EB-1, and both EB-1 and EB-2 are compatible with each other. This allows for the creation of a tree-like structure of endorsement blocks, where each branch represents a different set of transactions that can be included in the ledger via the next ranking block.

In the image below you can see 3 endorsement blocks that reference several input blocks. The last endorsement block also references the previous endorsement block.

Like input blocks, endorsement blocks are distributed in the network in the same way as other blocks in order to reach nodes that validate them.

Other nodes store endorsement blocks as they can be randomly drawn to issue an endorsement report. The endorsement report must be issued within a certain number of slots from the minting of the endorsement block (it is a network parameter). If a node is drawn as a reporter, it must validate all input blocks (and, if applicable, referenced endorsement blocks). If the block is OK, the node issues a signed endorsement report.

Having the latest endorsement blocks is a prerequisite to issuing endorsement reports on the endorsement blocks. The reports indicate whether all the input blocks referenced by the endorsement block actually exist and are valid.

The purpose of endorsement reports is to demonstrate the agreement of the required amount of stake with the existence and validity of the bundle of input blocks which are referenced endorsement blocks. In aggregated form, the bundle of endorsement reports is called an endorsement certificate.

In the picture below you can see a randomly drawn node that validates the endorsement block including all input blocks that are referenced and issues an endorsement report.

Once a sufficient number of endorsement reports have been created for a given endorsement block, it is possible to consider them as an endorsement certificate.

In the image below, you can see a randomly selected node that has received a sufficient number of endorsement reports, so that it basically has an endorsement certificate for an endorsement block. This also means that a node can include an endorsement block in a ranking block.

From a scalability point of view, it is important to know that different endorsement blocks can be minted concurrently on different nodes and they can reference multiple of the same input blocks.

Finally, we get to the ranking blocks which are the basis for the network consensus. A randomly drawn node will take recent endorsement blocks (which have not yet been used in previous ranking blocks) if it also has endorsement certificates for them and insert them into a new ranking block.

It may happen that the node has endorsement blocks available and there is no endorsement certificate yet because not enough endorsement reports have been issued. In that case, the endorsement block will not get into the current ranking block that the node mints. That doesn't matter, because this endorsement block will very likely make it to the next ranking block (which will be minted by another node).

In the image below you can see a node that is mining a new Ranking block. Node has 3 Endorsement blocks available, but only 2 endorsement certificates. EB 3 is therefore not referenced by the Ranking block.

As we already explained, endorsement blocks can reference each other. When a set of endorsement blocks is included in a ranking block, only the last Endorsement block in a chain needs to be included with an endorsement certificate. The reason is simple. An endorsement certificate for an endorsement block that references previous endorsement blocks implicitly covers those previous endorsement blocks.

The new ranking block must refer to the previous ranking block. A ranking block is considered valid if it references a previous valid ranking block and contains references to endorsement blocks with corresponding valid endorsement certificates. A ranking block can reference zero or more endorsement blocks.

A node may not have all endorsement blocks and referenced input blocks available and still be able to immediately accept the new state of the ledger. Construction of the ledger state (downloading of all blocks) may slightly lag behind the acceptance of the state.

In the image below you can see the relationships between all block types. Black arrows indicate references between IBs and EBs and also between RBs and EBs. The red arrows indicate the references of IBs to the current ledger state, i.e. to RBs. The blue arrows indicate the linearity of the blockchain, i.e. the relationship between RBs when the new RB must follow the previous RB. As time passes, all transactions will enter the ledger through IBs. In the image, you can also see the blue rectangles behind the EBs, which represent endorsement certificates.

Separating Transaction Selection from Block Production

The main purpose of the Input Endorser feature is to separate transaction selection from block production.

In the first generation of the algorithm, a node did both, that is, it selected valid transactions from its own mem-pool and inserted them into a new candidate block. This is essentially a sequential process in which only one node participates in each round (in one time period). Subsequent validation of the candidate block by other nodes takes place in parallel.

In the image below, you can see the creation of new blocks that contain all transactions from the local mem-pool.

Is it possible to parallelize the preparation of a new block (ranking block)?

The Input Endorsers algorithm will make it possible to prepare a larger number of transactions in the transaction selection phase, as more nodes in the network can participate in this concurrently. Endorsers validate and pre-approve transactions which help to reduce the computational load and bandwidth requirements of the producers of ranking blocks, as well as to increase the transaction pool diversity and availability. They also enable faster confirmation of transactions that have not been included on the chain yet, by providing proof of endorsement that can be verified by anyone.

Ranking blocks are used to ensure the traditional linearity of the blockchain and to achieve consensus in the network but instead of containing transactions, they contain references to endorsement blocks. Input blocks and endorsement blocks allow parallel and concurrent processing of transactions.

In the figure below, you can see the distribution of the work of different types of blocks from the point of view of network consensus. Note that while the frequency of block minting in the block production section is the same as in the previous figure, there is more activity taking place in the transaction selection section.

Consensus is still about selecting the best chain of blocks that follows the Ouroboros protocol rules. The input endorsers actually only endorse transactions that are valid and consistent with the ledger state. The producers of ranking blocks take these endorsed transactions and include them in the blocks they mint. The consensus is made over a larger number of transactions, as they have already been pre-approved and the ranking blocks contain only a reference to a set of endorsement blocks that are compatible with each other.

Note that Input Endorsers (IE nodes) are not responsible for ordering the transactions into a linear sequence of blocks, but only for validating and endorsing them. Endorsed transactions are then propagated through the network in endorsed blocks using a gossip protocol.

Scalability Improvements

The most important thing to note is that input blocks can be minted (streamed) essentially constantly (every 0.2-2 seconds). This means that instead of creating one data block every 20 seconds, 10 to 100 input blocks can be minted during the same time. The high frequency of minting input blocks does not hinder network consensus.

From the point of view of data throughput, the scalability can be improved roughly 10x to 100x if the input blocks have the same size as the current Cardano blocks. Within 20 seconds, Cardano can process from 3,000 to 30,000 transactions. TPS can be from 150 to 1500 if we consider only simple (small) transactions.

Increasing the input blocks would have a direct effect on higher scalability. However, increasing the size of input blocks could fundamentally slow down their diffusion in the network. It is important to balance the size of input blocks and the frequency of their minting as best as possible. This is a relatively welcome problem, as it is largely separated from consensus, i.e. from ranking blocks. As the capabilities of the Internet improve, the scalability of Cardano can also increase.

The finality of transactions will also improve since endorsement reports basically represent the agreement of a large part of the stake with the content of endorsement blocks (which reference input blocks). Although the ranking block can be orphaned, there is a relatively high chance that as soon as the transaction is inserted into the input block that will be referenced from the endorsement blocks, the transaction will get into the blockchain.

Conclusion

The article was supposed to explain the basic concepts of Input Endorsers and there was no space for some edge cases and critical design points. We'll get to that next time.