txselector

Documentation

Overview

Package txselector is responsible to choose the transactions from the pool that will be forged in the next batch. The main goal is to come with the most profitable selection, always respecting the constrains of the protocol. This constrains can be splitted in two categories:

Batch constrains (this information is passed to the txselector as `selectionConfig txprocessor.Config`): - NLevels: limit the amount of accounts that can be created by NLevels^2 -1. Note that this constraint is not properly checked, if this situation is reached the entire selection will fail - MaxFeeTx: maximum amount of different coordinator accounts (idx) that can be used to collect fees. Note that this constraint is not checked right now, if this situation is reached the `txprocessor` will fail later on preparing the `zki` - MaxTx: maximum amount of transactions that can fit in a batch, in other words: len(l1UserTxs) + len(l1CoordinatorTxs) + len(l2Txs) <= MaxTx - MaxL1Tx: maximum amount of L1 transactions that can fit in a batch, in other words: len(l1UserTxs) + len(l1CoordinatorTxs) <= MaxL1Tx

Transaction constrains (this takes into consideration the txs fetched from the pool and the current state stored in StateDB): - Sender account exists: `FromIdx` must exist in the `StateDB`, and `tx.TokenID == account.TokenID` has to be respected - Sender account has enough balance: tx.Amount + fee <= account.Balance - Sender account has correct nonce: `tx.Nonce == account.Nonce` - Recipient account exists or can be created:

• In case of transfer to Idx: account MUST already exist on StateDB, and match the `tx.TokenID`
• In case of transfer to Ethereum address: if the account doesn't exists, it can be created through a `l1CoordinatorTx` IF there is a valid `AccountCreationAuthorization`
• In case of transfer to BJJ: if the account doesn't exists, it can be created through a `l1CoordinatorTx` (no need for `AccountCreationAuthorization`)

- Atomic transactions: requested transaction exist and can be linked, according to the `RqOffset` spec: https://docs.hermez.io/#/developers/protocol/hermez-protocol/circuits/circuits?id=rq-tx-verifier

Important considerations: - It's assumed that signatures are correct, since they're checked before inserting txs to the pool - The state is processed sequentially meaning that each tx that is selected affects the state, in other words: the order in which txs are selected can make other txs became valid or invalid. This specially relevant for the constrains `Sender account has enough balance` and `Sender account has correct nonce` - The creation of accounts using `l1CoordinatorTxs` increments the amount of used L1 transactions. This has to be taken into consideration for the constrain `MaxL1Tx`

Current implementation:

The current approach is simple but effective, specially in a scenario of not having a lot of transactions in the pool most of the time: 0. Process L1UserTxs (this transactions come from the Blockchain and it's mandatory by protocol to forge them) 1. Get transactions from the pool 2. Order transactions by (nonce, fee in USD) 3. Selection loop: iterate over the sorted transactions and split in selected and non selected. Repeat this process with the non-selected of each iteration until one iteration doesn't return any selected txs Note that this step is the one that ensures that the constrains are respected. 4. Choose coordinator idxs to collect the fees. Note that `MaxFeeTx` constrain is ignored in this step. 5. Return the selected L2 txs as well as the necessary `l1CoordinatorTxs` the `l1UserTxs` (this is redundant as the return will always be the same as the input) and the coordinator idxs used to collect fees

The previous flow description doesn't take in consideration the constrain `Atomic transactions`. This constrain alters the previous step as follow: - Atomic transactions are grouped into `AtomicGroups`, and each group has an average fee that is used to sort the transactions together with the non atomic transactions, in a way that all the atomic transactions from the same group preserve the relative order as found in the pool. This is done in this way because it's assumed that transactions from the same `AtomicGroup` have the same `AtomicGroupID`, and are ordered with valid `RqOffset` in the pool. - If one atomic transaction fails to be processed in the `Selection loop`, the group will be marked as invalid and the entire process will reboot from the beginning with the only difference being that txs belonging to failed atomic groups will be discarded before reaching the `Selection loop`. This is done this way because the state is altered sequentially, so if a transaction belonging to an atomic group is selected, but later on a transaction from the same group can't be selected, the selection will be invalid since there will be a selected tx that depends on a tx that doesn't exist in the selection. Right now the mechanism that the StateDB has to revert changes is to go back to a previous checkpoint (checkpoints are created per batch). This limitation forces the txselector to restart from the beginning of the batch selection. This should be improved once the StateDB has more granular mechanisms to revert the effects of processed txs.

Index

• Constants
• type CoordAccount
• type TxSelector
  • func NewTxSelector(coordAccount *CoordAccount, dbpath string, ...) (*TxSelector, error)
  • func (txsel *TxSelector) GetL1L2TxSelection(selectionConfig txprocessor.Config, l1UserTxs, l1UserFutureTxs []common.L1Tx) ([]common.Idx, [][]byte, []common.L1Tx, []common.L1Tx, []common.PoolL2Tx, ...)
  • func (txsel *TxSelector) GetL2TxSelection(selectionConfig txprocessor.Config, l1UserFutureTxs []common.L1Tx) ([]common.Idx, [][]byte, []common.L1Tx, []common.PoolL2Tx, []common.PoolL2Tx, ...)
  • func (txsel *TxSelector) LocalAccountsDB() *statedb.LocalStateDB
  • func (txsel *TxSelector) Reset(batchNum common.BatchNum, fromSynchronizer bool) error

Constants

const (

	// ErrExitAmount error message returned when an exit with amount 0 is received
	ErrExitAmount = "Exits with amount 0 make no sense, not accepting to prevent unintended transactions"
	// ErrExitAmountCode error code
	ErrExitAmountCode int = 1
	// ErrExitAmountType error type
	ErrExitAmountType string = "ErrExit0Amount"

	// ErrUnsupportedMaxNumBatch error message returned when the maximum batch number is exceeded
	ErrUnsupportedMaxNumBatch = "MaxNumBatch exceeded"
	// ErrUnsupportedMaxNumBatchCode error code
	ErrUnsupportedMaxNumBatchCode int = 2
	// ErrUnsupportedMaxNumBatchType error type
	ErrUnsupportedMaxNumBatchType string = "ErrUnsupportedMaxNumBatch"

	// ErrSenderNotEnoughBalance error message returned if the sender doesn't have enough balance to send the tx
	ErrSenderNotEnoughBalance = "Tx not selected due to not enough Balance at the sender. "
	// ErrSenderNotEnoughBalanceCode error code
	ErrSenderNotEnoughBalanceCode int = 11
	// ErrSenderNotEnoughBalanceType error type
	ErrSenderNotEnoughBalanceType string = "ErrSenderNotEnoughBalance"

	// ErrNoCurrentNonce error message returned if the sender doesn't use the current nonce
	ErrNoCurrentNonce = "Tx not selected due to not current Nonce. "
	// ErrNoCurrentNonceCode error code
	ErrNoCurrentNonceCode int = 12
	// ErrNoCurrentNonceType error type
	ErrNoCurrentNonceType string = "ErrNoCurrentNonce"

	// ErrNotEnoughSpaceL1Coordinator error message returned if L2Tx depends on a L1CoordinatorTx and there is not enough space for L1Coordinator
	ErrNotEnoughSpaceL1Coordinator = "Tx not selected because the L2Tx depends on a L1CoordinatorTx and there is not enough space for L1Coordinator"
	// ErrNotEnoughSpaceL1CoordinatorCode error code
	ErrNotEnoughSpaceL1CoordinatorCode int = 13
	// ErrNotEnoughSpaceL1CoordinatorType error type
	ErrNotEnoughSpaceL1CoordinatorType string = "ErrNotEnoughSpaceL1Coordinator"

	// ErrTxDiscartedInProcessTxToEthAddrBJJ error message returned if tx is discarted in processTxToEthAddrBJJ
	ErrTxDiscartedInProcessTxToEthAddrBJJ = "Tx not selected (in processTxToEthAddrBJJ)"
	// ErrTxDiscartedInProcessTxToEthAddrBJJCode error code
	ErrTxDiscartedInProcessTxToEthAddrBJJCode int = 14
	// ErrTxDiscartedInProcessTxToEthAddrBJJType error type
	ErrTxDiscartedInProcessTxToEthAddrBJJType string = "ErrTxDiscartedInProcessTxToEthAddrBJJ"

	// ErrToIdxNotFound error message returned if the toIdx is not found in the stateDB
	ErrToIdxNotFound = "Tx not selected due to tx.ToIdx not found in StateDB. "
	// ErrToIdxNotFoundCode error code
	ErrToIdxNotFoundCode int = 15
	// ErrToIdxNotFoundType error type
	ErrToIdxNotFoundType string = "ErrToIdxNotFound"

	// ErrTxDiscartedInProcessL2Tx error message returned if tx is discarted in ProcessL2Tx
	ErrTxDiscartedInProcessL2Tx = "Tx not selected (in ProcessL2Tx)"
	// ErrTxDiscartedInProcessL2TxCode error code
	ErrTxDiscartedInProcessL2TxCode int = 16
	// ErrTxDiscartedInProcessL2TxType error type
	ErrTxDiscartedInProcessL2TxType string = "ErrTxDiscartedInProcessL2Tx"

	// ErrNoAvailableSlots error message returned if there is no available slots for L2Txs
	ErrNoAvailableSlots = "Tx not selected due not available slots for L2Txs"
	// ErrNoAvailableSlotsCode error code
	ErrNoAvailableSlotsCode int = 17
	// ErrNoAvailableSlotsType error type
	ErrNoAvailableSlotsType string = "ErrNoAvailableSlots"

	// ErrInvalidAtomicGroup error message returned if an atomic group is malformed
	ErrInvalidAtomicGroup = "Tx not selected because it belongs to an atomic group with missing transactions or bad requested transaction"
	// ErrInvalidAtomicGroupCode error code
	ErrInvalidAtomicGroupCode int = 18
	// ErrInvalidAtomicGroupType error type
	ErrInvalidAtomicGroupType string = "ErrInvalidAtomicGroup"
)

Types

type CoordAccount

type CoordAccount struct {
	Addr                ethCommon.Address
	BJJ                 babyjub.PublicKeyComp
	AccountCreationAuth []byte // signature in byte array format
}

CoordAccount contains the data of the Coordinator account, that will be used to create new transactions of CreateAccountDeposit type to add new TokenID accounts for the Coordinator to receive the fees.

type TxSelector

type TxSelector struct {
	// contains filtered or unexported fields
}

TxSelector implements all the functionalities to select the txs for the next batch

func NewTxSelector

func NewTxSelector(coordAccount *CoordAccount, dbpath string,
	synchronizerStateDB *statedb.StateDB, l2 *l2db.L2DB) (*TxSelector, error)

NewTxSelector returns a *TxSelector

func (*TxSelector) GetL1L2TxSelection

func (txsel *TxSelector) GetL1L2TxSelection(selectionConfig txprocessor.Config,
	l1UserTxs, l1UserFutureTxs []common.L1Tx) ([]common.Idx, [][]byte, []common.L1Tx,
	[]common.L1Tx, []common.PoolL2Tx, []common.PoolL2Tx, error)

GetL1L2TxSelection returns the selection of L1 + L2 txs. It returns: the CoordinatorIdxs used to receive the fees of the selected L2Txs. An array of bytearrays with the signatures of the AccountCreationAuthorization of the accounts of the users created by the Coordinator with L1CoordinatorTxs of those accounts that does not exist yet but there is a transactions to them and the authorization of account creation exists. The L1UserTxs, L1CoordinatorTxs, PoolL2Txs that will be included in the next batch.

func (*TxSelector) GetL2TxSelection

func (txsel *TxSelector) GetL2TxSelection(selectionConfig txprocessor.Config, l1UserFutureTxs []common.L1Tx) ([]common.Idx,
	[][]byte, []common.L1Tx, []common.PoolL2Tx, []common.PoolL2Tx, error)

GetL2TxSelection returns the L1CoordinatorTxs and a selection of the L2Txs for the next batch, from the L2DB pool. It returns: the CoordinatorIdxs used to receive the fees of the selected L2Txs. An array of bytearrays with the signatures of the AccountCreationAuthorization of the accounts of the users created by the Coordinator with L1CoordinatorTxs of those accounts that does not exist yet but there is a transactions to them and the authorization of account creation exists. The L1UserTxs, L1CoordinatorTxs, PoolL2Txs that will be included in the next batch.

func (*TxSelector) LocalAccountsDB

func (txsel *TxSelector) LocalAccountsDB() *statedb.LocalStateDB

LocalAccountsDB returns the LocalStateDB of the TxSelector

func (*TxSelector) Reset

func (txsel *TxSelector) Reset(batchNum common.BatchNum, fromSynchronizer bool) error

Reset tells the TxSelector to get it's internal AccountsDB from the required `batchNum`