Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
137 lines (86 sloc) 12.3 KB
LIP: 0006
Title: Improve transaction processing efficiency
Author: Usman Khan <usman@lightcurve.io>
Discussions-To: https://lists.lisk.io/pipermail/lips_lists.lisk.io/2018-November/000001.html
Status: Draft
Type: Informational
Module: Transactions, Transactions Pool
Created: 2018-09-07
Updated: 2018-11-21

Abstract

This LIP proposes to improve the processing of transactions by optimizing the verification of transactions, applying transactions in memory, and consolidating database queries. Additionally, it suggests improvements for managing transactions in the transaction pool.

Motivation

In the current implementation, transactions are processed by performing application logic and database queries alternately. Furthermore, for transactions which are yet to be included in the blockchain, the database keeps track of the accounts state that would result if all these transactions were applied. This accounts state is called unconfirmed state. The unconfirmed state is calculated to ensure that transactions do not conflict with each other and it is calculated in the transaction pool and during block processing.

The current implementation is inefficient and does not scale. First of all, executing application logic and database queries alternately slows down transaction processing due to database round trips, serial execution of database queries and NodeJS context switching. Secondly, storing unconfirmed states in the database is unnecessary and maintaining it requires extraneous database writes.

This proposal suggests performance improvements by attempting to separate application logic from database logic, resulting in parallel database queries with fewer round trips. Furthermore, this proposal suggests the calculation of unconfirmed states to occur in memory during transaction verification, removing the need for unnecessary writes to the database.

Specification

The task of processing transactions can be divided into verifying transactions and saving the resulting state of transactions in the blockchain. This proposal separately details improvements in both of these tasks. Afterwards, it describes new improvements in the transaction pool and how the aforementioned improvements in transaction processing will affect the transaction pool.

Improvements in the verification of transactions

This proposal suggests to improve the performance of verification by splitting the verification process in the following steps:

  • Perform static validations
  • Fetch the blockchain state
  • Verify against the blockchain state
  • Calculate the resulting state in memory

During the verification process, transactions are examined by performing checks to ensure that they can be applied to the current state of the blockchain. Firstly, transactions are checked by performing static validation such as schema and signature validations. Secondly, the blockchain state required for verifying transactions is fetched from the database. Thirdly, transactions are checked against the blockchain state to ensure that every single transaction can be applied to the current state of the blockchain. Lastly, the resulting state of transactions is calculated in memory to ensure that transactions do not conflict with each other i.e., these transactions together can be applied to the current state of the blockchain.

Moreover, these individual steps can be performed on a group of transactions in parallel to further improve the performance of transactions verification.

Perform static validations

In this step, all schema and signature validations required for verifying transactions are performed. These validation checks are performed on the transaction body and do not depend on the blockchain state. Therefore, if transactions are validated once, they will always be valid.

Fetch blockchain state

In this step, the blockchain state required for verifying transactions is fetched from the database. Since each transaction type requires specific data for verification, there should be a getRequiredAttributes function for each type. This function returns the information required to fetch the state from the database for a particular transaction. For example, for a delegate registration transaction, this function returns:

{
  β€˜ACCOUNT’: <sender_account_id>,
  β€˜UNIQUE_USERNAME’: <username specified in the transaction>
}

In the case of a delegate registration transaction, as described above, the details of the sender account and information on whether the username already exists in the blockchain is required. Using the information returned from getRequiredAttributes, the database module executes the queries for all transactions in parallel and collects the data in memory.

Verify against the blockchain state

In this step, all verification checks for transactions, which require the blockchain state, are performed. Some examples of checks include confirming the sender account balances and checking for required signatures.

Calculate the resulting state in memory

In this step, a given set of transactions are applied on the accounts in memory to check that the resulting state is valid. This resulting state is called unconfirmed state. This step is performed to ensure that transactions do not conflict with other transactions when applied together. For example, if the balance of an account is 10 LSK and there were two transfer transactions of 10 LSK each, then after applying both of these transactions, the balance of the account would be less than 0 LSK. Therefore, these transactions are conflicting.

Improvements in saving the resulting state of transactions in the blockchain

Processing blocks includes saving the resulting account state affected by the transactions in the blocks. This task is similar to the Calculate resulting state in memory step in the verification process but with an extra step. The updated state of accounts are saved in the database. We improve the performance of saving the resulting state of transactions by applying all the transactions on accounts in memory, and later performing the database update for all accounts only once, at the end.

Changes in the transaction pool

The purpose of the transaction pool is to validate and store transactions efficiently and to provide a list of valid, verified and non-conflicting transactions when the node is forging a block. In order to reflect the changes made in transaction processing, the implementation of the transaction pool needs to be updated. Furthermore, we suggest to verify incoming transactions against existing transactions in the transaction pool and re-verify affected transactions on changes of the blockchain state. The details are explained in separate sections below.

Queues used in the transaction pool

Transactions in the transaction pool are managed in multiple queues. Transactions are placed in different queues based on the stage of verification. Therefore, in order to reflect the changes in the transaction verification process, the new transaction pool manages transactions in the following queues.

  • received: This queue contains newly received transactions from other peers.
  • validated: This queue contains transactions which are validated by performing schema and signature validations.
  • verified: This queue contains transactions which are independently verified against the blockchain state.
  • pending: This queue contains transactions which are independently verified against the blockchain state and are awaiting signatures to be processed.
  • ready: This queue contains transactions which are verified against the blockchain state and can be processed in the same block.

Verifying transactions against transactions in transaction pool

In order to check whether transactions are conflicting, the transactions are verified against existing transactions in the transaction pool. During this process, every transaction that leaves the validated queue will be checked against all transactions in the verified, pending and ready queues. In order to understand the verifications performed at this step, we look at how various transaction types affect the accounts and blockchain state.

As shown in the table below, second signature registration, delegate registration, and multi-signature registration transactions are only allowed once per account. Therefore, if an account sends two or more transactions of one of these types to the transaction pool, then all of these transactions following the first one will be rejected during the verification against the transaction pool. In the same way, delegate registration transactions and dapp registration transactions contain unique data. Therefore, if the transaction pool receives two or more transactions of these types with same unique data, then the transactions following the first one will be rejected. Furthermore, voting for the same delegate is only allowed once per account. Therefore, if an account sends two or more transactions which include vote for the same delegate, then all of these transactions following the first one will be rejected.

Transaction type Allowed once for an account Contains unique data
Transfer transaction
Second signature registration transaction X
Delegate registration transaction X X
Vote transaction X
Multi-signature registration transaction X
Dapp registration transaction X
In transfer transaction
Out transfer transaction

To perform these checks, there will be a function verifyAgainstOtherTransactions for every transaction type. This function will accept two parameters: the transaction that needs to be verified and an array of already verified transactions of the same type. It will check the transaction against the verified transactions and return an error if the transaction is invalid due to another transaction based on some constraints for that transaction type.

Verify transactions on blockchain state change

The transactions are verified against the blockchain state. Changes in the blockchain states may cause some transactions to become invalid. The following changes in the blockchain state may invalidate transactions in the transaction pool:

  1. A new block is added to the blockchain. Therefore, new transactions that affect the validity of transactions in the transaction pool may be added to the blockchain.
  2. A block is deleted from the blockchain. Therefore, transactions that affect the validity of transactions in the transaction pool may be removed from blockchain.
  3. The application rolls back to the previous round. Therefore, the balance of active delegates is updated.

A blockchain state change only affects a subset of accounts and transactions. Therefore, only the affected transactions in the transaction pool should be verified again.

In case of a new block, the transactions in the verified, the pending and the ready queues should be moved to the validated queue if:

  • The transaction is from an account which is included in the new block.
  • The transaction is of a type that requires unique data and this transaction type is included in the new block.

In case of a block deletion, the transactions in the verified, the pending and the ready queues should be moved to the validated queue if:

  • The transaction is from an account included in the deleted block.

Moreover, the transactions included in the deleted block are put back in the verified queue such that they can become part of the blockchain in a later block.

In case of round rollback, the transactions in the verified, the pending and the ready queues should be moved to the validated queue if:

  • The transaction is from an account which was part of the active delegates of the round.

Backwards Compatibility

This LIP is backwards compatible.

Reference Implementation

TBD