LIP: 0015
Title: Enable transaction invalidation by using nonces instead of timestamps
Author: Andreas Kendziorra <[email protected]>
Discussions-To: https://research.lisk.com/t/enable-transaction-invalidation-by-using-nonces/
Status: Replaced
Type: Standards Track
Created: 2019-01-29
Updated: 2024-01-04
Requires: 0009
Superseded-By: 0041
This LIP proposes to replace timestamps by ordered nonces in transaction objects. This will allow to invalidate pending transactions by reusing the nonce.
This LIP is licensed under the Creative Commons Zero 1.0 Universal.
The current protocol requires that every transaction has a timestamp, and the timestamp is not allowed to be in the future during the transaction verification. There is, however, no proper reason why a timestamp has to be provided, and timestamps and their restrictions sometimes resulted in an unnecessarily bad user experience (rejected transactions) without providing any benefit (see the section Restrictions on Timestamps for more details). This motivates to remove timestamps from transactions. However, the reason to not completely remove the timestamp from transactions but to replace it by another property (nonces) is the requirement to have only distinct transactions in the blockchain to prevent transaction replay attacks (see the section Why Timestamps Are Currently Needed for more details).
Moreover, there is currently no way to invalidate pending transactions. Once dynamic fees are enabled, it could happen that a transaction with a low fee gets stuck in the transaction pool for a long time during busy moments of the network, and there is currently no possibility to replace this transaction by a transaction with a higher fee. This proposal enables a mechanism to invalidate transactions. The invalidation of transactions can be useful also in other situations. For example, when a user transmitted a transaction into the network without getting feedback, and the user is uncertain if this transaction gets eventually included in the blockchain or not. An invalidation mechanism ensures that such a transaction is not included at a later stage.
This section is divided into several subsections. First, we explain why timestamps are currently used in the Lisk protocol. Next, it is argued that restrictions on timestamps are not beneficial. In the subsequent subsection, the idea of removing restrictions on timestamps leads to the conclusion that one should rather consider arbitrary values without any meaning (nonces) instead of values that are considered to represent a certain time in order to achieve uniqueness. Then, it is explained how the nonces can be used for a transaction invalidation mechanism. The remaining subsections discuss some technical details of the proposal and some discarded alternatives.
Timestamps of transactions allow to make each transaction distinct by giving it a unique timestamp. This is needed because identical transactions are not allowed to be included in a blockchain. Otherwise, transaction replay attacks could easily be performed. In order to enforce that each transaction in the blockchain is distinct, unique transactionIDs for transactions included in the blockchain are currently enforced. The timestamp allows, for example, to create two balance transfer transactions with identical sender, receiver and amount to be included in the blockchain since different timestamps yield different transactionIDs.
The current protocol requires that the timestamp of a valid transaction is not in the future during the transaction verification. This allows to create a transaction that will be valid from a specified time point on. There is, however, little benefit from this for both the sender and the receiver (if there is one). A sender could simply issue the transaction at the time when it is desired to be accepted. For a receiver of a balance transfer transaction, such a transaction does not provide any guarantee to receive this payment, as the sender could transfer all funds to another account before the timestamp of the transaction becomes valid.
Moreover, the restriction sometimes resulted in unexpectedly rejected transactions because the system time of the transaction issuer was in the future. To create transactions that do not get rejected by nodes, an offset can be added to the system time. This is, however, rather a workaround instead of an elegant solution. For these reasons, an upper bound on the timestamp does not provide any proper benefit and rather leads to undesired problems.
Requiring a lower bound on the timestamp of a transaction (not done in the current protocol) would be even more harmful: A transaction pending for a long time in the transaction pool due to a low fee could become invalid after a certain time. Hence, neither an upper nor a lower bound on the timestamp value is beneficial.
As concluded in the previous subsection, restrictions on the value of the timestamp are not advantageous. Not having any restrictions on the timestamp allows, however, to choose arbitrary values. Consequently, the meaning of this value vanishes (the meaning of the timestamp value in the current protocol is already very little since arbitrarily small values are allowed). Therefore, associating any time related property to this value does not make sense. Instead, the value should be considered as a nonce. For this reason, we propose to replace the timestamp property of a transaction by a nonce property (we could also say that we rename the timestamp property to nonce property). The restrictions on the nonce property are discussed in separate subsections.
As mentioned in the motivation, there is currently no way to invalidate pending transactions. Therefore, we propose to enforce the uniqueness of nonces used for an account. More precisely, the combination of account and nonce has to be unique. This allows to invalidate pending transactions by reusing the nonce. This can be used, for example, in the case of pending low-fee transactions as mentioned above: Issuing the original transaction again with the same input, including the same nonce, but with a higher fee can replace the first transaction.
To invalidate a transaction without replacing it by a meaningful one, the sender could, for example, create a balance transfer transaction to his or herself where the nonce of the transaction that is supposed to be invalidated, is used. Once this new transaction has been included, it is guaranteed that the first transaction would not be included anymore. Of course, the original transaction may be included before the second one. In this case, the user has certainty about the original transaction (included in the blockchain) and it is guaranteed that the second one does not get included.
Both ordered nonces (i.e., to require that the nonce of a transaction has to be equal to the incremented nonce of the previously included transaction of the same sender) and unordered nonces (not enforcing any order) have their advantages and disadvantages and there is no perfect solution. Ordered nonces have more drawbacks regarding the user experience. For example:
- Each transaction in the transaction pool depends on the previous transaction. If several transactions originating from the same account are pending, and one of these transactions is pending for a long time due to a low fee, all following transactions are pending too, even if they have a very high fee. Moreover, it might be possible that one of the transactions is invalid. Consequently, the nonce of the invalid transaction has to be used again for a new (and valid) transaction before all following transactions get accepted.
- Keeping track of the used nonces may become difficult too when some transactions are pending and especially when several devices are used for a single account (this issue has been partially discussed for Ethereum for quite some time already). The same holds for generating transactions while having no connection to the network (offline transactions).
For these reasons, even a previous version of this LIP proposed to use unordered nonces.
However, unordered nonces have significant drawbacks regarding storage, performance and simplicity. Further considerations led to the decision that these drawbacks are too large and that ordered nonces should be preferred over unordered nonces. The main drawbacks are:
- The accounts state grows linearly with the number of transactions. Assuming a year of full blocks (~3.8*108 transactions), the unordered nonces would add ~3 GB to the accounts state. This impacts, for example, the accounts fetching performance for snapshooting mechanisms as desired by the roadmap objective "Introduce decentralized re-genesis". More generally, it lowers the performance, storage-wise and syncing-wise, of nodes that are not interested in the complete transaction history but only in transactions from a certain block height on and the corresponding accounts state.
- The account state of a single account can become very large. Hence, large data packages have to be transmitted when a client requests an account state from a node. This also reduces the possibility to develop light clients that are able to verify a single account state efficiently in the future.
- The global state becomes very large. To enable an efficient lookup for an existing (address, nonce)-pair, it seems to be unavoidable that an implementation requires to store these pair in an extra table. Assuming 20-byte addresses, the table would grow by at least 28 bytes per transaction. Assuming again a year of full blocks (~3.8*108 transactions), this sums up to ~10 GB extra. This results in a 20% larger blockchain growth as intended in LIP 0002.
Moreover, ordered nonces are widely used within the industry, whereas no project is known to us that uses non-ordered nonces without any further techniques, such as timeouts.
We propose to use unsigned integers for nonces. Using 32 bits to represent a nonce could theoretically result in an exhausted set of nonces in reasonable time: An account issuing permanently 10 transactions per second (which is possible with the intended changes for the block size) has an exhausted set of nonces after 13.6 years. Therefore, we propose to use 64 bits to represent a nonce, which requires more than 1010 years to exhaust the set of nonces with the mentioned frequency.
One purpose of the uniqueness requirement for transactionIDs in the current protocol is the prevention of transaction replay attacks. Due to the uniqueness requirement for the combination of address and nonce added in this proposal, one could drop the uniqueness requirement for transactionIDs without adding any risk for transaction replay attacks. However, transactionIDs are also used to uniquely identify transactions, for instance, in RPCs, the API of Lisk Core and frontend tools like Lisk Hub. Therefore, we keep the uniqueness requirement.
Unspent transaction outputs (UTXOs) as used in Bitcoin make it very easy to invalidate transactions: If the transaction tx should be invalidated, one simply has to reuse one UTXO used in tx in a new transaction. Using UTXOs in Lisk would, however, require drastic changes of the protocol and implementation. Therefore, UTXOs were disregarded.
Another possibility to invalidate transactions is to create a new transaction type in which one can specify a transactionID that shall be considered as invalid. Once the invalidation transaction is included in the blockchain, a transaction with the specified Id that originates from the same account as the invalidation transaction is considered to be invalid. This solution is however less convenient. Invalidating a transaction is easy, but replacing a transaction (e.g. by another transaction that has the same input but a higher fee) requires to first invalidate the original transaction and to issue another updated transaction. Hence, two transactions are needed and for each some fees have to paid. For the proposed mechanism, invalidating and replacing can be done with only one transaction. Therefore, the proposed mechanism of using ordered nonces is preferred.
Allowing to specify when a transaction becomes invalid provides little flexibility. Once a transaction was sent into the network, there is no way to update the provided timeout. Hence, quick invalidation is impossible. Therefore, this option was disregarded.
Each account has the property nonce. The value of this property is a 64-bit unsigned integer. When an account is initialized, the value is set to 0.
Each transaction needs the nonce property. The value must be a 64-bit unsigned integer.
When a transaction, tx, is included in a block, it must fufill
senderAccount.nonce == tx.nonce
where senderAccount is the account associated with tx.senderPublicKey. Otherwise, the transaction is invalid.
When tx is applied, then senderAccount.nonce is incremented by one.
The timestamp property gets removed from transaction objects.
In the serialization process for creating a byte array that serves as the input for SHA-256 whose output in turn is used as the input message for EdDSA, the nonce value follows the type value and gets followed by the senderPublicKey value. The nonce value uses 64 bits and shall be encoded big endian.
The same holds for the serialization process for creating a byte array that serves as the input for SHA-256 from which the reversed first 8 bytes are used as the transactionID.
This LIP introduces a hard fork. This is because:
- Transactions according to the current protocol get rejected by nodes following the proposed protocol because they do not have the
nonceproperty. - Transactions according to the proposed protocol get rejected by nodes following the current protocol because they do not have the
timestampproperty.
Due to the change in the serialization process for the byte array that serves as the input for the transaction signature, there is the possibility that the byte array BA of a transaction tx already included in the blockchain could represent a valid transaction according to the proposed protocol. If this were the case, the signature of tx would also be valid for the new transaction. In this case, an adversary could send this new valid transaction into the network without knowing the private key belonging to the signature.
This is however only possible if the network identifier does not change because the network identifier determines the first 256 bits of the byte array. Since the proposed change is causing a hard fork, the network identifier will change and it is guaranteed that BA does represent a valid transaction after the hard fork. Thus, the signature of tx cannot be valid for any transaction after the hard fork.