ICSE 2022 Paper #310 Reviews and Comments =========================================================================== Paper #310 Utilizing Parallelism in Smart Contracts on Decentralized Blockchains by Taming Application-Inherent Conflicts Review #310A =========================================================================== Overall merit ------------- 1. Reject Paper summary ------------- The paper explores techniques to enable the parallel execution of smart contracts and increase their run time performance. The authors observe that, in current smart contract applications, possible speedups are hindered mainly by conflicts that are inherent in the application logic. Thus, the proposed solutions are based on providing programming features to let developers avoid conflicts at the application level, e.g., through dedicated data structures or operations that can reduce conflicts or by distributing funds among different parties if possible. To encourage the use of such features in the future, blockchains would need to provide incentives for using them, e.g., in terms of gas cost. The evaluation suggests these features can achieve a speedup of up to 18x. Further, the authors introduce the notion of optimistic concurrency control with deterministic aborts, which allows for optimistically concurrent execution of smart contracts while satisfying the determinism requirements needed by current blockchain technology. Strengths --------- + The presented techniques have the potential to introduce significant speedups for executing smart contracts. They are therefore highly relevant for improving the applicability of blockchain applications that require high throughput, lifting the current low limits. + The evaluation is performed on real-world data of historical Ethereum transactions Weaknesses ---------- - The evaluation consists only of a simulation, which does not demonstrate that the approach can be applied to real contract code. The high-level description does not justify why a simulation is sufficient and how it faithfully models real code. - The evaluation does only cover one of three proposed techniques ("Partitioned Counters") Comments for authors -------------------- ## Soundness + The approaches presented in this paper are promising for increasing the parallelism in smart contract execution. + The results of the author's exploration of historical Ethereum transactions provide a sound basis for the proposed techniques. ## Significance + The gained insight that the main factors limiting parallelism in smart contracts are application-inherent conflicts is a significant discovery for improving the throughput of smart contract transactions. + Also, the definition of the novel optimistic concurrency control level "with deterministic aborts" might become important in the area of smart contracts. - Unclear whether the changes to the Ethereum Virtual Machine required for the "Commutative EVM Instructions" technique are worth the cost of changing the instruction set of the EVM and relying ong miners to run the updates VM; especially since the benefits of the technique are not evaluated. ## Novelty + The relevant new insight on which this work is based is that one of the main factors limiting parallelism are application-inherent conflicts. The authors then present multiple techniques that are suitable for increasing parallelism. ## Verifiability + The insight is plausibly explained and the authors define which excerpt from the history of Ethereum transactions they base their work on. - While it seems reasonable that the three techniques for avoiding application-inherent conflicts ("Conflict-Aware Token Distribution" L. 459, "Partitioned Counters" L. 508, "Commutative EVM Instructions" L. 568) may be effective in certain situations, only the "Partitioned Counters" technique is evaluated in Section 6. The authors do comment that they assume that partitioned counters can be applied to all storage conflicts (which seems reasonable based on the results of Section 3.2). However, this leaves the question about the effectiveness of the other two techniques unanswered. ## Presentation + The paper provides a comprehensive background section that motivates the problem of limited parallelism in current smart contracts. - The set of techniques proposed by the authors and their relation are initially somewhat vague ("In this paper, we propose a number of different approaches" L. 100). "One approach is ..." (L. 101) refers to partitioned counters and "Another approach ..." (L. 109) refers to commutative EVM instructions, but conflict-aware token distribution is not mentioned. The relation between these approaches and the optimistic concurrency control proposed by the authors is not clear at this point. - My impression after reading the complete paper is that the three techniques do not contribute to a coherent approach but are completely orthogonal. Any of them could potentially help the presented optimistic concurrency control with deterministic aborts to further increase parallelism. The presentation would be easier to follow if this was made clear upfront. ## Suggestions for improvement - I would recommend extending the evaluation to cover all three techniques. This is really important to assess whether the proposed techniques are successful in solving the problem tackled in this paper (i.e., increasing parallelism). I think that the evaluation as it stands does not adequately support the claims. - I also suggest to put the different techniques and the optimistic concurrency control with deterministic aborts in relation when you introduce them in the introduction instead of just describing them one after the other. # Minor comments - "sv_n,i is defined uniformly on all nodes" (L. 742) and "prior to #1's execution (sv_3,0 := 0), while the second execution can see the state after #2 (sv_3,1 := 2)" (L. 805) It's a bit of a mystery at this point how one should think to how these values are defined and where the exact values "sv_3,0 := 0" and "sv_3,1 := 2" come from. Maybe consider a forward reference to Section 5.5, which contains some further explanation. - "the first challenge is to [...] the next challenge would be to [...]" (L. 71) This sounds like the paper tackles the first challenge but not the second. - "a large portion of storage conflicts is associated with storage slots that belong to either counters or arrays" (L. 442) Aren't arrays negligible, i.e., "about 2% of the cases" (L. 395)? Questions for authors to respond to ----------------------------------- 1 - The evaluation is presented in a very high-level way. Could you elaborate a bit more on the methodology? I understand that no actual Ethereum code was run, is that correct? 2 - Is it realistic to modify the Ethereum Virtual Machine is there any compatibility issue with the current Ethereum infrastructure? 3 - I understand that that the impact of "Commutative EVM Instructions" is not evaluated, or did I misunderstand the evaluation section? Review #310B =========================================================================== Overall merit ------------- 4. Accept Paper summary ------------- The paper studied a large set of historical transaction execution traces in Ethereum and concluded that the major factor that limit the exploitable parallelism in smart contracts is due to application-inherent conflicts. To resolve the issue, the paper proposes to use partitioned counter and commutative instructions to maximize the potential speedup. It also proposes an OCC scheduler to ensure nodes to reach consensus when running concurrently. The main contributions are: * Distributing the locations from which transactions are sent, allowing for some more compact scheduling. * Breaking up certain counter writes into multiple sub-counters which do not conflict with each other and therefore can be further parallelized. * Propose a new system with less synchronization on the increments of the EVM by using a batching instruction _CADD_, which delays the increments/changes until later when it can be preformed all at once. These approaches were based on insight gained from analyzing results of past transaction data. They show that these approaches fulfill the determinism desired by public implementation, illustrating the usefulness and potential for real-world impact. Strengths --------- * Overall, I liked the paper. It contains many useful insights that are concluded from a wide range of transaction history. I believe the conclusion can potentially benefit future researchers. * Although the proposed solution, e.g., using partitioned counter to avoid conflict, is not new, the determined OCC on abort seems to be a promising direction to pursue for smart contract. * Thorough empirical study * Useful insights about the major reason that prevents concurrency in smart contract. * Throughout the paper the explanations are well done, able to clearly explain the content to someone with limited knowledge on the specifics of Ethereum without rereads. * I enjoy reading this paper. Well written paper. Figures and graphics are useful and clear, and not extraneous. Weaknesses ---------- - The studied transaction history is not recent - over three years old data between Jan-01-2018 and May-28-2018 (858, 236 blocks in total). Although the argument in Sec 3.3 with UniswapV2Pair is not unconvincing, I would have liked more on why the authors could not conduct a similar study on more recent data. - There already exist other high speed blockchains such as Solana with built-in mechanisms to avoid read/write conflicts, which natively allows better parallelism. The scope of impact here seems to be limited to Ethereum. This is not discussed in the paper. - The idea of commutativity has been explored in other papers such as sharding. This PLDI paper seems quite relevant but not cited or discussed: Practical Smart Contract Sharding with Ownership and Commutativity Analysis https://ilyasergey.net/assets/pdf/papers/cosplit-pldi21.pdf - The assumption that all the conflict counter access can be resolved by partitioned counter might be too strong for evaluation. Although I agree with the authors that the listed result still provides some useful insights on the maximum speedup that can potentially be archived, I do think a more careful discussion on the potential impact is desired. - It seems that the impact of applying communicative instructions are not discussed. Comments for authors -------------------- ## Soundness I felt that the discussion of the study, optimizations, implementation, and proof of determinism were extremely sound. This paper considers all involved concerns and topics very well. ## Significance This paper has definite impacts in the field and has done the work required to prove viability in public projects. ## Novely This paper is novel due to targeting a lesser investigated portion of Ethereum's transactions. The contributions, while impactful, are not based on all that novel concepts. This work applies and combines pre-existing ideas in a useful way to a specific task. ## Verifiability and Transparency This paper is very transparent on their process and design. Very strong in this aspect. ## Presentation The work is presented clearly and without obvious flaw or issue. Figures and tables are done well and assist the reader. Review #310C =========================================================================== Overall merit ------------- 3. Weak accept Paper summary ------------- This paper carries out an empirical study of conflicts on Ethereum logs, then proposes several techniques to address these. The authors re-run experiments with these to show significant improvement in performance via parallelisation and discuss implications, threats and key related work. Strengths --------- + work seems solid to me + inefficiencies of blockchain systems have become highly topical + empirical studies well explained and presented + solutions seem reasonable Weaknesses ---------- - implications and feasibility unclear i.e. will/can these approaches be adopted? - analysis done with simulations based on real-world data (surely a threat to validity?) Comments for authors -------------------- * Soundness: The problem analysis seems solid to me. This is a real problem on blockchain based systems and has causes various degrees of concern - limiting platform performance ; inefficiencies due to conflicts ; high energy consumption due to wasted resources ; lack of incentive for better smart contract writing. I think the background and first empirical study do a good job of describing and evidencing the problem and identifying some of the key bottleneck areas. I like the approach of focusing on bottleneck reduction / removal vs scheduler optimisation. I like the solutions proposed - the single increment operator seems a simple yet elegant solution and its surprising its not been identified/utilised. Which brings me to the query around implications of this work - will/can it be used? Is it feasible to modify the Solidity complier/Ethereum VM to incorporate this in real-world deployment? It would be good to discuss what might be challenges in doing this. Similarly, it would be good to discuss implications of the other proposes approaches in terms of how they might be realised in practice. I wondered how providing programming incentives in smart contracts to developers to avoid some of these common contention points might work, whether they would use them, and any sticking points to adoption. Again it would be good to discuss this issue. I did wonder about the dependency analysis solution in terms of real-world application - the analysis relies on, if I read correctly, full dependency analysis upfront to schedule the operations. In a situation where multiple transactions with dependencies are running but unknown order, will this still provide the same performance improvement / is it feasible? This problem occurs in grid scheduling approaches too where the transaction mix and hence their interdependencies are not known up front. One approach is to use historic transaction mixes for distribution to nodes, but this likely doesn't work in this scenario. The predefined serialisation order is good for optimistic processing but relies on knowing the transaction mix up front? Or do I miss something? There are other isolation levels databases use e.g. dirty reads etc (reading uncommitted transaction state from another concurrent transaction). It would be interesting to see if other solution methods could enhance OCC? I wondered about whether there might be other potential unified EVM/Solidity operations besides an SADD that might assist with handling concurrent transaction operations on shared data structures? I wondered why more recent EVM transaction log data couldn't be used in the experiments? Could you comment briefly on why the period chosen was used somewhere? You claim 3.3 and 7 explain this but I couldn't find any explanation there :-) Instead there is a claim its "unlikely to have changed" and "probably got worse", but these seem speculative vs factual (though I personally agree with your rationale about increase in NFTs and DeFi contracts likely to exacerbate the issues you identify). * Significance As above I would like you to discuss the implications of the work for both practice and research. For the former, what needs to be done to adopt this and why can't it be adopted? What would be the sticking point? Similarly what are the limitations of your work and what needs to be done in terms of further research to address? Could a Implications or Discussion section discussing these be added after Threats? * Novelty It seems quite novel work, in terms of the empirical evaluation demonstrating the problem and the proposed solutions. * Verifiability and Transparency Thanks for making data/code available! I wondered about a few threats: - I don't feel the 2018 data usage is sufficiently justified in the paper - seems a long time ago for a 2021 submission? - upfront dependency analysis assumes know transaction mix upfront - I wondered about gas cost of the unified SADD instruction - should it be SLOAD+SSTORE or maybe less? Might this impact usage/adoption too? * Presentation The paper is very well written and figures and diagrams well explained. Questions for authors to respond to ----------------------------------- 1. Why didn't you use more recent transaction log data? 2. What are the key blockers from having your proposal adopted? Comments on the author's response --------------------------------- Thanks for your responses. You addressed my direct questions as well as a few of my implicit ones in my view. Many thanks! I think answers overall to queries were helpful. Author-Comments Response by Péter Garamvölgyi (Author) (1457 words) --------------------------------------------------------------------------- We would like to thank the reviewers for taking the time to read our work and provide thoughtful comments and suggestions. We will add the suggested clarifications in the final version of the paper. Below, we address the most important questions in the first 750 words. Other answers below the line can be viewed as supplemental. **Reviewer A: Could you elaborate a bit more on the methodology? I understand that no actual Ethereum code was run?** **Reviewer C: Analysis done with simulations based on real-world data (surely a threat to validity?)** Methodology: We collected storage access traces from the Ethereum mainnet, as most transaction conflicts are storage-related. (1) For evaluating the proposed bottleneck-elimination techniques, we analyzed the best-case parallel execution time using the transaction dependency graph, with and without applying these techniques. This graph was derived from the state access traces. (2) For evaluating deterministic OCC, we simulated execution without prior knowledge about the transaction dependencies. Conflicting transactions are aborted and re-executed. In both experiments, no actual EVM bytecode was executed. (1) is an analysis of the upper bound on any parallel scheduler implementation. The potential overhead of the parallel VM is not considered because it depends heavily on the actual implementation. Our goal is to compare different techniques in a controlled and deterministic way without speculating about the VM implementation. The bottlenecks analyzed here remain the same and continue to put an upper bound on the potential speedup in a real-world implementation. The proposed techniques can eliminate these bottlenecks. In (2), we chose to simulate scheduling because currently there is no parallel EVM implementation. Our goal in this work is not to implement such a VM. Instead, we aim to move the state-of-the-art toward this goal by (a) making it feasible to implement parallel scheduling under a consensus setting ("OCC with det. aborts"), and (b) making it worth it to do so (bottleneck-elimination techniques). In (2), instead of evaluating the absolute scheduler performance, we focus on the relative difference between simple OCC and "OCC with det. aborts". This relative difference is likely to be similar in a real-world implementation. We use gas cost as a proxy for execution time. This, again, provides a controlled testing environment, and it follows previous work [0]. EVM opcode gas costs are roughly proportional to their execution time, e.g., opcodes that potentially read from disk have the highest gas cost. [0] Vikram Saraph and Maurice Herlihy. 2019. An Empirical Study of Speculative Concurrency in Ethereum Smart Contracts. arXiv preprint arXiv:1901.01376 (2019). **Reviewers A and C: Is it realistic to modify the EVM to incorporate this in a real-world deployment? Key blockers?** Implementing parallel execution of blockchain transactions requires further research and engineering effort. We see three interrelated milestones. First, we need further research on incentives that encourage parallelizability and discourage abusing the scheduler. Second, the EVM needs to be adjusted and extended with a parallel scheduler. "OCC with deterministic aborts" provides a foundation for these two milestones: it offers a framework for implementing a parallel scheduler that can fulfill the stringent determinism requirements of distributed consensus protocols. Third, we need techniques and tools to increase the parallelizability of the transaction workload. The proposed bottleneck-elimination techniques address this milestone. "Conflict-Aware Token Distribution" and "Partitioned Counters" are application-level techniques: they do not require modifying the underlying blockchain platform. The third technique ("Commutative EVM Instructions") relies on new EVM opcodes, and so it requires a protocol upgrade (hardfork), and an update to the Solidity compiler so that it produces EVM bytecode using these new opcodes. These changes are backward-compatible: old contracts and compiler versions can still be used, but new contracts can benefit from these added features. **Reviewers B and C: The studied transaction history is not recent. Why didn't you use more recent transaction log data?** Acquiring the entire Ethereum transaction history and generating storage access traces is extremely resource-consuming. Syncing an archive node requires over 9TB of storage [1] and months of time. Due to resource and time constraints, we were forced to make a trade-off in our evaluations. We believe the chosen period is representative of today's Ethereum workload and so our findings are generalizable. First, early 2018's peak transaction load is comparable to Ethereum's traffic these days [2]. Second, the application patterns we observed (DeFi, NFT, token distributions) are even more dominant today. As no parallel EVM is available, dapp developers have no reason to address the issues we pointed out. In fact, just by a cursory glance, we can spot storage conflicts in many recent popular applications: Uniswap exchanges that involve the same token will always conflict on token reserves; OpenSea trades will transfer tokens to the same `protocolFeeRecipient`, and we could continue. We believe this shows that the conflicts we identified are even more common today. [1] https://etherscan.io/chartsync/chainarchive [2] https://etherscan.io/chart/tx ---- **Reviewer A: I understand that that the impact of "Commutative EVM Instructions" is not evaluated.** The first two techniques work on the level of storage entries, while this third technique works on the level of EVM instructions. Unfortunately, the storage traces our evaluations rely on do not provide enough information about the series of instructions in each transaction. We expect the effect of the three techniques to be similar, as they all effectively remove edges from the transaction dependency graph in a similar way. In fact, "Commutative EVM Instructions" might be more effective: The first two techniques will still result in conflicts when the same sender account or the same partition is accessed, while this third technique could serialize all updates without conflict. **Reviewer B: The scope of impact here seems to be limited to Ethereum.** Our work focuses on Ethereum but our findings and solutions are applicable to other chains as well. (1) Many significant blockchains adopt Ethereum's execution logic (Ethereum Classic, BSC). Others are in the process of adding an EVM compatibility layer (Near, Solana). (2) Different chains share common use cases (DeFi swap platforms, NFT marketplaces). Popular Ethereum applications are often forked and redeployed on other chains (Uniswap and PancakeSwap). This results in similar transaction workloads on these chains. This similarity is supported by previous research as well [3]. [3] Daniël Reijsbergen and Tien Tuan Anh Dinh. 2020. On Exploiting Transaction Concurrency to Speed Up Blockchains. In 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS). IEEE, 1044–1054. (cited as [22] in the paper) **Reviewer C: The analysis relies on, if I read correctly, full dependency analysis upfront to schedule the operations [...] The predefined serialisation order is good for optimistic processing but relies on knowing the transaction mix up front?** We rely on upfront knowledge of transaction dependencies only when analyzing the upper bound on the potential parallel speedup. For the actual parallel execution, our assumption is that the scheduler has zero knowledge about the transaction dependencies. The predefined serialization order can be any order; as long as it is the same on all nodes, they can reach consensus on the execution results. In a blockchain setting, it seems natural to use the order of transactions in the block. However, other serial orders might be more optimal in terms of parallelizability. We believe a parallel scheduler should be able to fulfill its role with zero upfront knowledge about dependencies. However, if it does have some knowledge or informed guess about the dependencies, it will be able to (1) choose more accurate storage versions and thus avoid unnecessary aborts, and (2) choose a more optimal serialization order. We believe execution profiling and static analysis might assist the scheduler in effectively predicting the dependencies. **Reviewer C: There are other isolation levels databases use e.g. dirty reads etc (reading uncommitted transaction state from another concurrent transaction). It would be interesting to see if other solution methods could enhance OCC?** In our experiments implementing and optimizing an OCC scheduler (not discussed in this paper), we were mainly using a snapshot isolation model. We did consider dirty reads [4] but we believe further evaluation needs to be done to see the potential impact of cascading aborts. We agree that many techniques from traditional database systems could be applied to an OCC scheduler for blockchain transactions. Such optimizations to an OCC scheduler were not our focus in this work. [4] https://github.com/icse22-blockchain/supplementary-material/blob/26dd87e3e5ebc0d8ce4d7ad74cebfd6fe10b67b7/simulation/src/evm-trace-extract/occ.rs#L438 **Reviewer C: I wondered about whether there might be other potential unified EVM/Solidity operations besides an SADD that might assist with handling concurrent transaction operations on shared data structures?** That is an interesting question. One thing that comes to mind is batched reads, i.e., a version of SLOAD that retrieves multiple storage entries in parallel. It is a widely held view that the EVM could be improved in many ways. Once there is a working parallel EVM implementation, it will provide ground for more innovation in this space. Review #310D =========================================================================== Meta-Review ----------- Congratulations! The paper and the author response received extensive discussions among the reviewers. There were both significant strengths and weaknesses considered: Pros: Significant, novel insights gained from a substantial, large-scale empirical study of smart contract transaction history. In particular, the discovery that the main factors limiting parallelism in smart contracts are application-inherent conflicts is significant, and the definition of the novel optimistic concurrency control level "with deterministic aborts" might become important in the area of smart contracts. Cons: The paper proposes three optimizations techniques but it evaluates only two of them. The evaluation was done by simulation, not by implementing a real system. In the end, we favored the pros over the cons and decided to accept this paper. In the final version, we urge the authors to correct the following claims: (1) clearly state the limitation that the evaluation is based on simulation, not by implementing a real system (2) for the three optimization techniques, clearly state that what are evaluated, what are not, and explain why those optimizations could not be properly evaluated in the current work.