Problem

  1. We need to guarantee certain order of transaction execution
  2. Transactions could be sent in arbitrary order
  3. Transactions that depend on each other might be either valid or invalid

In theory if we could guarantee that Iroha clients have all transactions that depend on each other at hand, then they would be able to utilize batch approach. Otherwise another solution is needed.

Proposal – Transaction tags

Tags

Tags are optional fields in transactions. Tags are arbitrary byte arrays that could be of two kinds:

  1. `requires` – tags that current transaction require to be further sent into transaction pipeline
  2. `provides` – tags that current transaction provide

Requires tags

If transaction A submitted into transaction queue has `requires` tags, then it is stored in some `waiting_txs` collection (makes sense to implement this collection as Multimap<Tag, Transaction> for a quick look up by tag). Otherwise if `requires` tags are empty, transaction is put into the `ready_txs` collection.

Provides tags

If transaction B received by transaction queue has `provides` tags, then all transactions that require that tags are removed from `waiting_txs` collection and are put into the ready collection (assuming these transactions do not depend on other tags). The transaction B itself is included into the ready collection, assuming it does not depend on other tags.

Getting ready transactions

Whenever peer is selected as the leader and creates a block from the transactions stored in ready collection.

Important: ready transactions collection should be returned in topological order defined by the tags, to guarantee in-order execution.

Transaction longevity

Transactions that never receive required tags should not be stored forever. Iroha can define some default longevity for every transaction (either in maximum amount of blocks transaction will remain valid for (eg 100 blocks), or in maximum time duration (eg 24 hours)). However, it also makes sense to be able to specify custom longevity for any transaction by Iroha clients.

Therefore we can introduce another optional transaction field: longevity

Transaction should stay in `waiting_txs` for the longevity period starting from the moment of transactions submission to the queue unless it is removed due to transaction being invalid or included into the finalized block. 

Removal

There are two kinds of removal: removeInvalid and removeValid

removeInvalid

If some transaction is considered invalid during stateful validation it is removed from the transaction queue completely. All transactions from the same block that depend on removed transactions should be removed from the block and queue's `ready_txs` collection and moved back to the `waiting_txs` (assuming they do not have enough `requires` tags anymore). Removed invalid transactions should not provide any tags after removal from the queue.

removeValid

When some block is finalized all transactions from that block are removed from the queue's `waiting_txs`. Valid transactions being removed that way can still provide some tags for a period defined by transaction longevity (described above). This is because if we have dependency A←B (B depends on A), then if A is applied and is not in the `ready_txs` anymore, transaction B submitted later should have all required tags (assuming B was submitted within A's longevity period).



  • No labels

15 Comments

  1. Nikita Puzankov

    Hi Salakhiev Kamil- thanks for the RFC. I'll put some comments below:

    • `Whenever peer is selected as the leader and creates a block from the transactions stored in ready collection.` - the only order guarantee as I see that transactions with `requires` flag should be put after transactions without tags and before transactions with `provides` flag?
    • `All transactions that depend on removed transactions should be removed from the `ready_txs` collection and moved back to the `waiting_txs` (assuming they do not have enough `requires` tags anymore)` does it mean that instead of processing transactions with `requires` tags should be after transacations with `provides` tag and not in the same but in a next block?
    • ` Valid transactions being removed that way can still provide some tags for a period defined by transaction longevity (described above)` what if the period is longer than time this transactions stay in our queue? How should we track them?

    In general, it looks more like "delayed" transactions processing or event listening rather than transactions ordering and have a quite complex logic behind it which definitely will be hard to maintain with other scenarios.

    I would like to wait for Iurii Vinogradov review and check the possibility to use some sort of batching instead.

    1. Salakhiev Kamil

      Whenever peer is selected as the leader and creates a block from the transactions stored in ready collection. - the only order guarantee as I see that transactions with requires flag should be put after transactions without tags and before transactions with provides flag?

      Yes, this is how we define an order. Tags are arbitrary byte arrays. Clients will decide what to define in tags. Simple case is just putting transactions indices as tags. For example if B depends on A, A can have `provides` tag "1" and B can have the same `requires` tag. Then we guarantee that B will be executed after A

      All transactions that depend on removed transactions should be removed from the ready_txscollection and moved back to thewaiting_txs(assuming they do not have enoughrequires tags anymore) does it mean that instead of processing transactions with requires tags should be after transacations with provides tag and not in the same but in a next block?

      That means that if transaction that provides some tags is invalid, we should remove it completely from the queue. Transactions that were in the same block and had `requires` tags from removed transaction should be removed from block and put into the `waiting_txs`.

      Anyway, I noted that in document I didn't mention that this logic applies to transactions from the same block. Added this information to the document.

      Valid transactions being removed that way can still provide some tags for a period defined by transaction longevity (described above) what if the period is longer than time this transactions stay in our queue? How should we track them?

      Period cannot be longer than the duration of staying this transaction in queue. 

      It transaction was submitted to the queue at the moment t1, then it will be removed at the moment t1 + longevity.

      Alternatively, we can define longevity by the number of blocks transactions should remain in the queue. For example, if transaction was submitted to the queue when the lates finalized block had number N then, it will be removed when block number N+longevity is finalized.

      It is implementation details how to track that. Possible (but not necessary the best) way is to maintain map<Hash, TimePoint>, where Hash corresponds to the Hash of transaction in the queue and TimePoint is the moment when transaction should be removed. We can define a method `maintain_pool` that will remove transactions with passed longevity period. `maintain_pool` can be invoked whenever new transaction is submitted or new block is finalized. 


      As I said in the beginning of the document, this is an alternative solution to transaction batches. If client has all transactions at hand to create a batch, then we can implement order using batches. This solution does not have such requirement.

      1. Iurii Vinogradov

        While it is not clear which transaction with which trade from Polkaswap will be added in which block, I think we should support some solutions which work between blocks. 

  2. Iurii Vinogradov

    Nikita Puzankov Batch solution seems does not work in the case of Polkaswap. We need ordering for trades. And trades transactions can be sent by different accounts and with different time intervals. We can combine some transactions in batches but we will need to order batches than.

    1. Iurii Vinogradov

      Collection with Tag as a key should have the ability to store multiple transactions under one tag. For example, if we created multiple spend transactions with tag to wait credit transaction. When credit transaction happend, all spend transactions will be processed.

    2. Iurii Vinogradov

      In polkaswap case, we need that both committed and rejected transactions with provided tag A should make possible to process transactions with required tag A. Because it is just a sequence of orders. In other cases (described in the message above case with spend and credit transactions) Only successfully committed transactions should release depended on transactions. We don't have this case in Polkaswap, but it might be very useful for banks to acquire loans, etc.

    3. Iurii Vinogradov

      For now, Polkaswap we need only one tag to define a sequence.

      Question: What will happen if tag was committed a long time ago? Will Iroha search it in Blockcstore? Can it create a significant load and reduce performance if there are many such searches? For Polkaswap there might be a significant delay between two trades for the first time.

      1. Salakhiev Kamil

        If transaction was committed a long time ago it will not provide any tags. If Iroha client needs some transaction to provide tag for a long period of time, then client should set big longevity period of transaction

    4. Iurii Vinogradov

      Question: If I need to know the last value of a Tag committed in Iroha by Polkaswap, how can I do it? It might be useful if some transactions with a tag not reach Iorha2 for some reason(or was marked as invalid), but I need to proceed with a sequence of transactions that reach Iroha2 otherwise all new transactions will not be committed.

      Polkaswap itself is Iroha2 module, so this situation should not happen, so we can not think about it too much, but for external clients it is valuable.

      1. Salakhiev Kamil

        I think such issues should be resolved by the transaction status query. So that if you want to know what happened with some transaction that should provide some tag, then you need to query status of that transaction. However, for that you need to know the hash of this transaction.

        If there is no way to obtain this hash, then we need to think about introducing some query into the transaction pool

  3. Nikita Puzankov

    As I see RFC also not cover requirements from Iurii Vinogradov, we have a situation when clients want to define long term ordering of some transactions execution without knowing anything about other transactions.

    Tags will not provide an ability to do so, also distributed ledger can not guarantee such a thing.

    I think clients will need to make some sort of two phase commits in this case - locking all assets needed for the operation before sending request for execution. But we need to wait Makoto Takemiyacomments.

    1. Nikita Puzankov

      As commented by Makoto Takemiya:

      ```

      I actually don't think any of these are problems and this is how pretty much any other blockchain works. For order-critical applications, Iroha2 has batches, which are atomic sets of transactions that are executed in order.

      ```

      So we need to define a "Problem" before discussing "Solution".

      1. Salakhiev Kamil

        I disagree with cited statement. Explained above why

      2. Iurii Vinogradov

        Finally, as I see problem exists, but blockchain generally did not found solution for the decentralized ordering of transactions. All proposed solutions has some amount of centralization for ordering, what does not much our case when any trading transaction from any user sent to any node should be ordered comparing to some 'ideal' time. 

        So blockchain works how it works not because it should work this way, but because a better solution for the current task is difficult on the blockchain.

        This topic was also discussed in chat including Makoto:

        Iurii:
        So, as I understand, the order has no relationships to time of transaction submission by the user, but has a relationship to time of submission of the transaction by the node to the leader. If it is so then it will not work for Polkaswap. Yep, mostly, blockchains work something like this.

        Makoto:
        Correct. The leader of the consensus round orders the transactions. Because transaction fees in Sora network are all the same, everyone has an equal likelihood

    2. Salakhiev Kamil

      Yes, if transactions are created by users then it is hard to force them add tags. In Polkadot tags are added to transactions during validation when transaction is received. It is possible to implement something like that in Iroha, but probably it would complicate architecture too much