Enable transaction invalidation by using nonces

Dear community,

With this email, I would like to kickoff the discussion for a LIP regarding the roadmap objective “Enable transaction invalidation”.

The motivation for having a mechanism to invalidate transactions is the planned dynamic fee system. With a dynamic fee system, transactions could get stuck in the transaction pool for a long time if they have a too low fee. For these situations, it is desirable to have a mechanism to invalidate a transaction or replace it with another transaction with a higher fee.

The proposed solution is to replace timestamps by nonces in transaction objects, and to replace the uniqueness requirement for transactionIDs by a uniqueness requirement for the combination of sender account and nonce. With this, a pending transaction can be replaced by sending the same transaction, including the same nonce, again, but with a higher fee. Once the transaction with the higher fee is included, it is guaranteed that the original transaction will not be included. This also allows to invalidate a transaction, tx, without replacing it by a meaningful one. The sender of tx could simply issue a balance transfer transaction to themself where the nonce of tx is used.

If network identifiers are already used (see https://github.com/LiskHQ/lips/blob/master/proposals/lip-0009.md), the uniqueness requirement can be changed to enforcing uniqueness of the combination of sender account, nonce and network identifier. This allows nodes to forget about all used combinations every time the network identifier changes.

Some words about the motivation for this specific solution:

Timestamps of transactions are currently not very meaningful. This is because arbitrarily small values are allowed, even timestamps before the genesis block. Enforcing a lower bound on the timestamps could lead, however, to problems. If the lower bound is rather tight (e.g., if timestamps are not allowed to be older than 12 hours during inclusion time), transactions that are pending for a long time in the transaction pool could become invalid. If the lower bound is rather loose, the value becomes again rather meaningless.

On the other hand, the existing upper bound on timestamps (timestamps are not allowed to be in the future during verification) sometimes resulted in rejected transactions due to not matching system times (see https://github.com/LiskHQ/lisk-elements/issues/191). A workaround was provided for the client side by adding an offset to the system time. But manipulating the time provided by the system in order to get a transaction accepted is obviously not the right way. As this upper bound does also not provide any advantage, it should be removed.

Removing this upper bound eliminates the meaning of the timestamps completely. Thus, one should not interpret these values as any time related property if there are no restrictions on timestamps. Instead, the values should only be interpreted as a nonces. Therefore, we should remove the mentioned upper bound and rename the property “timestamp” to “nonce”.

Note that completely removing timestamps (or nonces) without replacing them by anything else would have a bad impact on usability. This is because it is not allowed to have two identical transactions included in the blockchain. Otherwise, one could easily perform transaction replay attacks. Therefore, we would like to have some way to make each transaction unique. So far we did this by using timestamps which results in unique transactionIDs. In this proposal, we use unique combinations of sender account and nonce (and network identifiers if they exist).

I’m looking forward to receiving your feedback.

Andreas

···
-- Andreas Kendziorra
Cryptographer, Lightcurve

andreas.kendziorra@lightcurve.iowww.lightcurve.io

Hello,

Would it not be easier to prevent any transaction with a too low fee from being broadcasted to the network?

You still need a method to determine if the fee is too low and then reject the tx.

This greatly improves the user experience, since no one likes to find out afterwards that his transaction is not being processed.

Regards,

Jacco <korben3>

···

Op 29 jan. 2019 om 18:00 heeft lips-request@lists.lisk.io het volgende geschreven:

Send LIPS mailing list submissions to
   lips@lists.lisk.io

To subscribe or unsubscribe via the World Wide Web, visit
   http://lists.lisk.io/mailman/listinfo/lips_lists.lisk.io
or, via email, send a message with subject or body 'help' to
   lips-request@lists.lisk.io

You can reach the person managing the list at
   lips-owner@lists.lisk.io

When replying, please edit your Subject line so it is more specific
than "Re: Contents of LIPS digest..."

Today's Topics:

  1. Enable transaction invalidation by using nonces
     (Andreas Kendziorra)

----------------------------------------------------------------------

Message: 1
Date: Tue, 29 Jan 2019 11:56:20 +0100
From: Andreas Kendziorra <andreas.kendziorra@lightcurve.io>
To: lips@lists.lisk.io
Subject: [LIPS] Enable transaction invalidation by using nonces
Message-ID: <e4571a0d-a781-0bad-7c0d-822543ad085f@lightcurve.io>
Content-Type: text/plain; charset="utf-8"; Format="flowed"

Dear community,

With this email, I would like to kickoff the discussion for a LIP
regarding the roadmap objective ?Enable transaction invalidation?.

The motivation for having a mechanism to invalidate transactions is the
planned dynamic fee system. With a dynamic fee system, transactions
could get stuck in the transaction pool for a long time if they have a
too low fee. For these situations, it is desirable to have a mechanism
to invalidate a transaction or replace it with another transaction with
a higher fee.

The proposed solution is to replace timestamps by nonces in transaction
objects, and to replace the uniqueness requirement for transactionIDs by
a uniqueness requirement for the combination of sender account and
nonce. With this, a pending transaction can be replaced by sending the
same transaction, including the same nonce, again, but with a higher
fee. Once the transaction with the higher fee is included, it is
guaranteed that the original transaction will not be included. This also
allows to invalidate a transaction, tx, without replacing it by a
meaningful one. The sender of tx could simply issue a balance transfer
transaction to themself where the nonce of tx is used.

If network identifiers are already used (see
https://github.com/LiskHQ/lips/blob/master/proposals/lip-0009.md), the
uniqueness requirement can be changed to enforcing uniqueness of the
combination of sender account, nonce and network identifier. This allows
nodes to forget about all used combinations every time the network
identifier changes.

Some words about the motivation for this specific solution:

Timestamps of transactions are currently not very meaningful. This is
because arbitrarily small values are allowed, even timestamps before the
genesis block. Enforcing a lower bound on the timestamps could lead,
however, to problems. If the lower bound is rather tight (e.g., if
timestamps are not allowed to be older than 12 hours during inclusion
time), transactions that are pending for a long time in the transaction
pool could become invalid. If the lower bound is rather loose, the value
becomes again rather meaningless.

On the other hand, the existing upper bound on timestamps (timestamps
are not allowed to be in the future during verification) sometimes
resulted in rejected transactions due to not matching system times (see
https://github.com/LiskHQ/lisk-elements/issues/191). A workaround was
provided for the client side by adding an offset to the system time. But
manipulating the time provided by the system in order to get a
transaction accepted is obviously not the right way. As this upper bound
does also not provide any advantage, it should be removed.

Removing this upper bound eliminates the meaning of the timestamps
completely. Thus, one should not interpret these values as any time
related property if there are no restrictions on timestamps. Instead,
the values should only be interpreted as a nonces. Therefore, we should
remove the mentioned upper bound and rename the property ?timestamp? to
?nonce?.

Note that completely removing timestamps (or nonces) without replacing
them by anything else would have a bad impact on usability. This is
because it is not allowed to have two identical transactions included in
the blockchain. Otherwise, one could easily perform transaction replay
attacks. Therefore, we would like to have some way to make each
transaction unique. So far we did this by using timestamps which results
in unique transactionIDs. In this proposal, we use unique combinations
of sender account and nonce (and network identifiers if they exist).

I?m looking forward to receiving your feedback.

Andreas

--
Andreas Kendziorra
Cryptographer, Lightcurve
andreas.kendziorra@lightcurve.io
www.lightcurve.io

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lisk.io/pipermail/lips_lists.lisk.io/attachments/20190129/14282043/attachment-0001.html>

------------------------------

Subject: Digest Footer

LIPS mailing list
LIPS@lists.lisk.io
http://lists.lisk.io/mailman/listinfo/lips_lists.lisk.io

------------------------------

End of LIPS Digest, Vol 3, Issue 2
**********************************

Hi Jacco,

Thanks for your answer!

Just to avoid any misunderstanding: When I say that a transaction with a low fee, say tx, gets stuck in the transaction pool for a long time, then I'm talking about the situation that tx has valid fee (above the minimum fee that will be defined in the dynamic fee system; otherwise the transaction is rejected by nodes) but the network is so busy such that every block is full, and every included transaction has a higher fee than the one from tx. Then, tx can eventually get included when there are less transactions (blocks are not full anymore), or the fees of the included transactions decrease (fee of tx is large enough such that delegates prefer tx over other transactions).

In this situation it is a subjective decision if a fee is "too low". For user A, a fee might be too low when the transaction does not get included within 1 minute. For user B, the fee might be too low when the transaction does not get included within 7 days. For this reason, we cannot make a general rule that prevents transactions being broadcast due a certain fee value (as long as the fee is valid).

There is also the objective on the roadmap to have a fee estimation algorithm. This algorithm is supposed to help the user to choose a fee according to its priority. This will help users to avoid sending transactions that have a "too low fee" from their personal perspective.

Does this answer your question?

Best regards

Andreas

···

On 29.01.19 20:38, Jacco via LIPS wrote:

Hello,

Would it not be easier to prevent any transaction with a too low fee from being broadcasted to the network?

You still need a method to determine if the fee is too low and then reject the tx.

This greatly improves the user experience, since no one likes to find out afterwards that his transaction is not being processed.

Regards,

Jacco <korben3>

Op 29 jan. 2019 om 18:00 heeft lips-request@lists.lisk.io het volgende geschreven:

Send LIPS mailing list submissions to
    lips@lists.lisk.io

To subscribe or unsubscribe via the World Wide Web, visit
    http://lists.lisk.io/mailman/listinfo/lips_lists.lisk.io
or, via email, send a message with subject or body 'help' to
    lips-request@lists.lisk.io

You can reach the person managing the list at
    lips-owner@lists.lisk.io

When replying, please edit your Subject line so it is more specific
than "Re: Contents of LIPS digest..."

Today's Topics:

   1. Enable transaction invalidation by using nonces
      (Andreas Kendziorra)

----------------------------------------------------------------------

Message: 1
Date: Tue, 29 Jan 2019 11:56:20 +0100
From: Andreas Kendziorra <andreas.kendziorra@lightcurve.io>
To: lips@lists.lisk.io
Subject: [LIPS] Enable transaction invalidation by using nonces
Message-ID: <e4571a0d-a781-0bad-7c0d-822543ad085f@lightcurve.io>
Content-Type: text/plain; charset="utf-8"; Format="flowed"

Dear community,

With this email, I would like to kickoff the discussion for a LIP
regarding the roadmap objective ?Enable transaction invalidation?.

The motivation for having a mechanism to invalidate transactions is the
planned dynamic fee system. With a dynamic fee system, transactions
could get stuck in the transaction pool for a long time if they have a
too low fee. For these situations, it is desirable to have a mechanism
to invalidate a transaction or replace it with another transaction with
a higher fee.

The proposed solution is to replace timestamps by nonces in transaction
objects, and to replace the uniqueness requirement for transactionIDs by
a uniqueness requirement for the combination of sender account and
nonce. With this, a pending transaction can be replaced by sending the
same transaction, including the same nonce, again, but with a higher
fee. Once the transaction with the higher fee is included, it is
guaranteed that the original transaction will not be included. This also
allows to invalidate a transaction, tx, without replacing it by a
meaningful one. The sender of tx could simply issue a balance transfer
transaction to themself where the nonce of tx is used.

If network identifiers are already used (see
https://github.com/LiskHQ/lips/blob/master/proposals/lip-0009.md), the
uniqueness requirement can be changed to enforcing uniqueness of the
combination of sender account, nonce and network identifier. This allows
nodes to forget about all used combinations every time the network
identifier changes.

Some words about the motivation for this specific solution:

Timestamps of transactions are currently not very meaningful. This is
because arbitrarily small values are allowed, even timestamps before the
genesis block. Enforcing a lower bound on the timestamps could lead,
however, to problems. If the lower bound is rather tight (e.g., if
timestamps are not allowed to be older than 12 hours during inclusion
time), transactions that are pending for a long time in the transaction
pool could become invalid. If the lower bound is rather loose, the value
becomes again rather meaningless.

On the other hand, the existing upper bound on timestamps (timestamps
are not allowed to be in the future during verification) sometimes
resulted in rejected transactions due to not matching system times (see
https://github.com/LiskHQ/lisk-elements/issues/191). A workaround was
provided for the client side by adding an offset to the system time. But
manipulating the time provided by the system in order to get a
transaction accepted is obviously not the right way. As this upper bound
does also not provide any advantage, it should be removed.

Removing this upper bound eliminates the meaning of the timestamps
completely. Thus, one should not interpret these values as any time
related property if there are no restrictions on timestamps. Instead,
the values should only be interpreted as a nonces. Therefore, we should
remove the mentioned upper bound and rename the property ?timestamp? to
?nonce?.

Note that completely removing timestamps (or nonces) without replacing
them by anything else would have a bad impact on usability. This is
because it is not allowed to have two identical transactions included in
the blockchain. Otherwise, one could easily perform transaction replay
attacks. Therefore, we would like to have some way to make each
transaction unique. So far we did this by using timestamps which results
in unique transactionIDs. In this proposal, we use unique combinations
of sender account and nonce (and network identifiers if they exist).

I?m looking forward to receiving your feedback.

Andreas

--
Andreas Kendziorra
Cryptographer, Lightcurve
andreas.kendziorra@lightcurve.io
www.lightcurve.io

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lisk.io/pipermail/lips_lists.lisk.io/attachments/20190129/14282043/attachment-0001.html>

------------------------------

Subject: Digest Footer

LIPS mailing list
LIPS@lists.lisk.io
http://lists.lisk.io/mailman/listinfo/lips_lists.lisk.io

------------------------------

End of LIPS Digest, Vol 3, Issue 2
**********************************

--
Andreas Kendziorra
Cryptographer, Lightcurve
andreas.kendziorra@lightcurve.io
www.lightcurve.io

Here is the full proposal:

LIP: <LIP number>
Title: Enable transaction invalidation by using nonces instead of timestamps
Author: Andreas Kendziorra <andreas.kendziorra@lightcurve.io>
Discussions-To: https://research.lisk.com/t/enable-transaction-invalidation-by-using-nonces/
Type: Standards Track
Created: <YYYY-MM-DD>
Updated: <YYYY-MM-DD>
Requires: 0009

Abstract

This LIP proposes to replace timestamps by nonces in transaction objects. No constraints on the order of nonces shall be used. Moreover, the requirement that the transactionID has to be unique is replaced by the requirement that the combination of address, nonce and network identifier has to be unique. This will allow to invalidate pending transactions by reusing the nonce while still preventing transaction replay attacks.

Copyright

This LIP is licensed under the Creative Commons Zero 1.0 Universal.

Motivation

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.

Rationale

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.

Why Timestamps Are Currently Needed

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.

Restrictions on Timestamps

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.

Timestamps vs. Nonces

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.

Enabling Invalidation of Transactions

As mentioned in the motivation, there is currently no way to invalidate pending transactions. Therefore, we propose to not enforce the uniqueness of transactionIDs, but rather of nonces used for an account. More precisely, the combination of address, nonce and network identifier (see LIP 0009) has to be unique. This prevents transaction replay attacks in the same way as unique transactionIDs do. But it also 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.

One may argue that enforcing uniqueness solely to the nonce value is sufficient too. That means, each nonce value would be allowed to be included in the blockchain only once. This is also prevents transaction replays and allows transaction invalidation, but increases the probability of rejected transactions due to already used nonces. This is especially the case when many users/clients tend to choose nonces not uniformly at random, for example, by choosing the operating system time as the nonce. Moreover, it allows users to invalidate pending transactions of other users.

Alternatively, one could also enforce the uniqueness of the combination of address and nonce. But this does not allow to delete the used combinations every time the network identifier changes. When enforcing the uniqueness of the combination of address, nonce and network identifier, all used combinations can be deleted when the network identifier changes. This is because transactions using the old network identifier are invalid and there is no need to check if the combination of address, nonce and network identifier was already used. See also the section Impact on Storage and Performance for more reasoning why this is advantageous.

Ordered vs. Unordered Nonces

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) have one obvious advantage over unordered nonces: One has to store only a single nonce per account. This requires less storage, enables faster verification and keeps the protocol and implementation simple (see also the discussion below).

There are however significant disadvantages for ordered nonces: 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).

Due to the mentioned disadvantages for the user experience, we propose to use unordered nonces. That means, there are no restrictions on the order of nonces.

Format of Nonces

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.

Choosing a Nonce

As discussed before, an arbitrary 64-bit unsigned integer has to be used for the nonce, with the restriction that the combination of sender address, nonce and network identifier has to be unique. Two obvious ways exist to choose a nonce during transaction creation: using a pseudo random number generator or the system time. For the latter option, care has to be taken when creating multiple transactions at the same time. Of course, any other way to choose a 64-bit unsigned integer that fulfills the mentioned uniqueness requirement is valid too.

Impact on Storage and Performance

To be able to quickly verify if a certain combination of sender address, nonce and network identifier was already used, it may be necessary to store these combinations in separate database tables for efficient querying. For example, there could be a table with two columns (one for the address and one for the nonce) for the current network identifier. Alternatively, one could use a table with a single column for the concatenation of address and nonce. This way, the single column coincides with the primary key which could speed up queries. Every time the network identifier changes, the table for the old network identifier can be deleted. One more alternative is to specify that the combination of address, nonce and network identifier is unique in the transaction table. That way, one does not need to create extra tables, but it also disallows to delete the combinations for network identifiers that are not valid anymore.

The currently used address format uses 64 bits. However, the address system is intended to be changed in the near future. For the following computations, we assume an address length of 192 bits. With this size, storing a combination of address and nonce requires 256 bits. Assuming the block size limit proposed in LIP 0002, approximately 120 transactions fit into one block. This can result in up to ~3.8*108 transactions per year. Hence, the required storage for the combinations of address and nonce could grow by up to ~12 GB per year.

An average PC should be able to perform a few thousand queries per second for combinations of address and nonce in a table of the size of 12 GB. Once the size of the table results in too large query times, the table could be split.

The impact on storage and performance will not be drastic in the near future because several hard forks are planned which every time results in a change of the network identifier. Hence, the previously used combinations can always be deleted. Once there is a long period without a hard fork, the impact on storage and performance could have a significant impact. In the appendix, some possibilities that could mitigate the impact are mentioned. This is, however, no complete research and no solution shall be specified in this LIP. If mitigation solutions are desired in the future, the solution shall be implemented in a separate step.

Discarded Alternatives

Unspent Transaction Outputs

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. At the same time, transaction replay attacks get prevented because a UTXO cannot be spent twice. Using UTXOs in Lisk would, however, require drastic changes of the protocol and implementation. Therefore, UTXOs were disregarded.

Invalidation Transaction

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 unordered nonces is preferred.

Timeout

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.

Specification

Transaction Objects

Timestamp

The timestamp property gets removed from transaction objects. Any transaction object having this property is considered to be invalid.

Nonce

Every transaction object needs a nonce property. The value of this property has to be a 64-bit unsigned integer. During the verification of a transaction, it has to be ensured that the combination of

  • sender address
  • nonce
  • network identifier (see LIP 0009)

was not used for any other transaction included in the blockchain before. If this combination was already used, the transaction has to be rejected. Note that the network identifier is not part of the transaction JSON object. It is only part of the input message of the transaction signature, and a signature is rejected if the message did not contain the correct network identifier (see LIP 0009 for more details).

TransactionID

The uniqueness of transactionIDs shall be dropped. That means, a transaction is not considered to be invalid just because there exists already another transaction in the blockchain with the same transactionID.

Serialization for Signature and TransactionID Generation

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.

Backwards Compatibility

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 nonce property.
  • Transactions according to the proposed protocol get rejected by nodes following the current protocol because they do not have the timestamp property.

Consequences of Serialization Process Change

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.

Appendix

Possibilities to Mitigate the Impact on Storage and Performance

Two ideas to mitigate the impact on storage and performance shall be mentioned in this section. Note that this does not pose a complete study, and more research may be required to find a good solution.

Incentivise Expiration Times

An optional transaction property that specifies an expiration time of a transaction could be added to the protocol. If a transaction contains an expiration time, then the combination of address and nonce could be allowed to be reused after the expiration time, because replaying the transaction after the expiration time is impossible (assuming that the expiration time is included in the input message of the transaction signature). Therefore, the combination of address and nonce does not need to be stored after the expiration time.

The usage of a low expiration time could be incentivized by enforcing a higher transaction fee for transaction without a low expiration time. This is very simple for static fees. In a dynamic fee system in which the fee is proportional to the transaction size (as, for instance, in this proposal), the size of a transaction could artificially be increased by adding some redundant data. For example, a hash value of some known data could be added to the transaction object. This way, the transaction object becomes larger without the need that nodes store this redundant data, because it is alway easily reproducible. If a transaction without a low expiration time does not contain the redundant data, it is rejected.

Artificially Change the Network Identifier

The network identifier could be changed, for example, by incrementing the version. This allows to delete all previously stored combinations, but introduces a hard fork.

I just created a pull request to merge the draft posted above into the lips repository: https://github.com/LiskHQ/lips/pull/14

The pull request was merged some days ago, and the LIP has now the status “Draft”: https://github.com/LiskHQ/lips/blob/master/proposals/lip-0015.md

There is one detail in the current LIP that I would like to change. It’s the removal of the uniqueness requirement for transactionIDs. Since transactionIDs are supposed to be unique identifiers for transactions, we need to keep the uniqueness requirement.
I’ll create a pull request to change this detail very soon.

Here is the pull request for this modification: https://github.com/LiskHQ/lips/pull/21

That’s an interesting direction. I did not find the time to read all of this in detail but let me add one thing: In our blockchain abstraction layer at IOV (https://github.com/iov-one/iov-core/blob/v0.17.3/packages/iov-bcp/src/connection.ts#L204-L216 and https://github.com/iov-one/iov-core/blob/v0.17.3/packages/iov-bcp/src/transactions.ts#L121-L125) we already hack the Lisk timestamp into the nonce field for the following reasons:

  1. a timestamp at transaction level is worthless, so the interface does not include it
  2. we need to put the Lisk timestamp somewhere
  3. there is non nonce at Lisk

So the nonces generator in the Lisk implementation works by using the n past timestamps: https://github.com/iov-one/iov-core/blob/v0.17.3/packages/iov-lisk/src/liskconnection.ts#L217-L225

I only checked your code very briefly. If you require that each transaction needs a unique nonce (I conclude this from here), then please be aware that this is not guaranteed by this LIP. This LIP only guarantees uniqueness of the triple (address, nonce, networkidentifier).

The pull request regarding the transactionID uniqueness was merged.

We reconsidered the impact of using unordered nonces and came to the conclusion that the drawbacks are unfortunately too large. These drawbacks are mainly:

  • the accounts state grows too much => low performance for snap-shooting mechanisms where one fetches only the accounts state without the complete transaction history
  • a single account state can become very large => querying an account state may require to transmit large data, which may also prevent efficient light clients that are able validate an account state
  • assuming full blocks, up to ~10 GB extra storage per year may be required for the blockchain

For these reason, we decided to use ordered nonces, which is an established solution within the industry.
I opened a pull request for this change: https://github.com/LiskHQ/lips/pull/47
In the section Ordered vs. Unordered Nonces, you can find more details about the rationale for this change.

The pull request was merged today.