Parallel Execution of HSCS Transactions

[mshakeg]

Background

EIP-648 proposes a simple and optional mechanism for enabling the EVM to process transactions in parallel[1]. As of now, the EIP has not been implemented on Ethereum or any other EVM chain except potentially BSC, which has publicly disclosed its efforts in parallel transaction execution(however may have taken their own approach)[5]. However, multiple non-EVM chains such as Solana, Aptos, and Sui have implemented parallel transaction execution to increase the throughput of their smart contract services significantly. Both Sui and Solana enable this using an implementation similar to that proposed in EIP-648, i.e., either optional or mandatory specification of read and write access lists to state by a transaction[2][4]. On the other hand, Aptos uses a more novel mechanism called Block-STM that enables it to process 160k non-trivial Move transactions per second[3].

Proposal

This discussion proposes the implementation of parallel transaction execution for the Hedera Smart Contract Service (HSCS) in a manner similar to that proposed in EIP-648. However, unlike EIP-648, which uses RLP lists to determine the ranges of addresses a transaction can access to read and/or write, we propose specifying the exact Hedera entity ids/addresses (either account/contract/token ids). Since Hedera entity ids are not distributed pseudorandomly across the address/id space like Ethereum addresses, using RLP lists as EIP-648 proposes would not be practical, as all entity ids would fall into a single range. Therefore, specifying the entity id in the read and write dependency lists allows for transactions that share at least one entity dependency to be assigned to the same thread. Note as EIP-648 proposes this would be done on a per block level; see the Client Implementation algorithm in EIP-648.

To incentivize and disincentivize correct and incorrect entity ids in the read and write dependency lists, a reward and penalty mechanism is proposed. A correct entity id is an entity id that is indeed called in a given transaction's execution, and an incorrect entity id is an entity that is never called. A penalty gas is charged preemptively for each entity specified in the dependency lists, and for every entity that is called correctly, gas is awarded that is either equal to the penalty (in which case, it is an exact refund for the penalty charged) or slightly more to incentivize developers to specify correct entity dependencies. This allows for transactions to be optimally assigned to threads for parallel transaction execution, resulting in increased throughput, as opposed to developers simply not specifying dependency lists. Additionally, the mirror node can expose an endpoint to determine contracts that are invoked in the static execution of a transaction if the exact read&write lists of entity dependencies are not known in advance; similar reasoning for static eth_call or eth_estimateGas.

If a transaction calls the HTS precompile (0x167) to read and/or write from/to state, then instead of specifying the precompile address in the read and/or write entity dependency lists, the Hedera entity addresses that are being read and/or updated via the precompile contract can be specified. Since the HTS precompile contract is frequently called by many smart contracts, it makes more sense to specify the upstream entities that are being read from or written to, in order to enable parallelization across transactions that all call the HTS precompile contract but are not reading from or writing to the same entity.

Parallelization of such transactions that call the HTS precompile can be further optimised by considering dependency in HTS actions between transactions, though this will require explicit specification of the type of action and its entity dependencies. For example(Example 1), if Alice signs 2 contract calls to separate contracts within the same "block" that do a Fungible HTS transfer from her account to Bob's account but on 2 separate HTS tokens, then these 2 transactions can be executed in parallel. Or in another example(Example 2), if Alice signs a contract call to contract X that transfers TokenA to Bob and Carol signs a contract call to contract Y that also transfers TokenA but to Dave, then both Alice's and Carol's transactions can be executed in parallel.

Example 1 Write Dependency List:

Alice's 1st transaction's write dependency list:

[
  {
    "type": "ContractCall",
    "contract": "X" // if X is the target contract i.e. "to" then it does NOT need to be explicitly stated in the dependency list, but can be inferred from the transaction's "to" value
  },
  {
    "type": "FungibleTokenTransfer",
    "sender": "AliceId",
    "receiver": "BobId",
    "token": "TokenAId"
  }
]

Alice's 2nd transaction's write dependency list:

[
  {
    "type": "ContractCall",
    "contract": "Y"
  },
  {
    "type": "FungibleTokenTransfer",
    "sender": "AliceId",
    "receiver": "BobId",
    "token": "TokenBId"
  }
]

Example 2 Write Dependency List:

Alice's transaction's write dependency list:

[
  {
    "type": "ContractCall",
    "contract": "X"
  },
  {
    "type": "FungibleTokenTransfer",
    "sender": "AliceId",
    "receiver": "BobId",
    "token": "TokenAId"
  }
]

Carol's transaction's write dependency list:

[
  {
    "type": "ContractCall",
    "contract": "Y"
  },
  {
    "type": "FungibleTokenTransfer",
    "sender": "CarolId",
    "receiver": "DaveId",
    "token": "TokenAId"
  }
]

Potential Issues

• The bottleneck may be disk I/O operations, not CPU processing power, so parallel transaction execution would not necessarily increase smart contract throughput; this is supposedly the reason for EIP-648 not being implemented.
• It may increase the CPU requirements for consensus nodes.

Alternative Considerations

• Investigate whether the Block-STM approach would yield higher throughput on the EVM than the read & write dependency access lists approach.

References

[1] Easy parallelizability (EIP-648)
[2] Sealevel — Parallel Processing Thousands of Smart Contracts
[3] Block-STM: How We Execute Over 160k Transactions Per Second on the Aptos Blockchain
[4] How Sui Works
[5] BNB Chain New Milestone: The Implementation of Parallel EVM 2.0
[6] Monad Block-STM Parallel Execution

[mgarbs]

Cool idea! Always good to get these new discussions and I like exploring new innovations. A couple of questions for you:

• How will this implementation of parallel transaction execution improve the performance of HSCS over the current implementation? Can you give some examples for clarity?
• Can you provide more information about how the reward and penalty mechanism will work, and what specific incentives are in place for developers to specify correct entity dependencies? Diagrams are super useful with topics like these
• How will the proposed implementation of parallel transaction execution affect the security of HSCS, and what measures would be in place to ensure that transactions are still processed securely?
• Can you provide examples of specific scenarios in which parallel transaction execution would be useful for HSCS users?
• How will the implementation of parallel transaction execution for HSCS differ from other non-EVM chains like Solana, Aptos, and Sui?
• Could you also provide a flow diagram of how this could fit into our existing services?

What you have is great and I think more diagrams addressing the granularity of everything this touches will help drive this from an engineering perspective if they are to implement it.

[gregscullard]

Couple of points I would like to clarify:

• HCS, HTS, Crypto and HSCS transactions are all run in series, they don't operate in separate threads so there is no parallel execution across different services.
• Fairness is guaranteed, if a node maliciously changes the order they process transactions in, that node's signed state will differ from the majority and will no longer be trusted by the network. Furthermore, any tampering with an event's ordering of transactions will break the hash/signature for that event and it will be discarded by other nodes.
• I did discuss parallelisation with Engineering and while the idea is promising (not without its challenges), the feedback at the time was that there are lower hanging fruit that can achieve performance improvements. In other words, parallelising should be done when every other improvement opportunity is exhausted.
• I also understand that greater gas/s is currently possible, the throttles are set to a conservative (and sufficient) level for now and could be increased if/when the need arises.

[mshakeg]

@gregscullard thanks for the clarification.

---

HCS, HTS, Crypto and HSCS transactions are all run in series, they don't operate in separate threads so there is no parallel execution across different services.

Good to know, given that there are already throttles on those services, the throughput if and when parallelization is implemented could possibly be at least an order of magnitude of the current unthrottled throughput, though there may be other bottlenecks such as network bandwidth.

---

Fairness is guaranteed, if a node maliciously changes the order they process transactions in, that node's signed state will differ from the majority and will no longer be trusted by the network. Furthermore, any tampering with an event's ordering of transactions will break the hash/signature for that event and it will be discarded by other nodes.

I'm not referring to a node retroactively reordering transactions in a previously signed&processed event(which is what I understand from your reply), but re-ordering transactions in an event that is currently being populated/constructed(and that hasn't yet been signed and gossiped). So either the node delays/advances a transaction within the current event that is being populated or even delays the transaction to another of its future events.

---

I did discuss parallelisation with Engineering and while the idea is promising (not without its challenges), the feedback at the time was that there are lower hanging fruit that can achieve performance improvements. In other words, parallelising should be done when every other improvement opportunity is exhausted.

That's fair, I suspect parallelisation is possibly already being used for some aspects(maybe signature verification) as network nodes have high CPU requirements(minimum of 48 threads).

---

I also understand that greater gas/s is currently possible, the throttles are set to a conservative (and sufficient) level for now and could be increased if/when the need arises.

I suspected as much given that the Besu EVM is capable of 672m gas/block for 2 second blocks(i.e. 336m gas/s) in a 5 node network; though Hedera being a larger network will likely not be able to handle such a high single-thread gas limit.

---

[mgarbs]

@mgarbs the HSCS is currently capable of only ~100 TPS(assuming an average gas/tx of 150k and a 15m gas/s limit). Parallelization of the HSCS can result in a higher effective gas limit(a maximum of NUM_THREADS* GAS_LIMIT_PER_THREAD as previously explained)

Okay, I understand now, thank you @mshakeg. I do think this is a great idea and looks like it could help with throughput of smart contracts. Looking at metrika over the last 30 days, though, our smart contracts would have to grow a substantial amount to reach the point where it becomes a problem. It's definitely a good topic, thank you for posting it. For me it feels like a better thing to discuss as we approach this limit.

[mshakeg]

@mgarbs as @gregscullard mentioned there are other lower hanging fruits to enhance HSCS performance, but parallelization wouldn't be an optimisation limited to only the HSCS but to other services such as the HTS and HCS as well.

[mgarbs]

I agree that it can optimize other services too. When we reach our limits, let's take a closer look 👀

[mshakeg]

Sei Network employs a much simpler incentive for correctly specifying dependencies i.e. a 50% discount on the gas price. So if all specified dependencies are used then a 50% discount is applied to the tx, however, if at least one incorrect(i.e. unused) dependency is specified then no discount is provided.