Parallel Hash-Mark-Set on the Ethereum Blockchain
Zachary Painter, Pradeep Kumar Gayam, Victor Cook, Damian Dechev · 2020
Popular blockchains such as Bitcoin or Ethereum provide a transaction isolation level of READ-COMMITTED. This provides difficulties when state changes many times per block interval. Hash-Mark-Set (HMS) alleviates this problem by enabling READ-UNCOMMITTED transactions for state variables. However, the current HMS implementation relies on a sequential algorithm and is susceptible to redundant calculations. As modern processors rely more heavily on parallel algorithms to leverage multiple cores for speedup, sequential algorithms see less benefit from hardware improvements. This paper proposes a lock-free HMS to make use of thread-safe techniques and other optimizations to improve the performance of the HMS algorithm and reduce the latency of read-uncommitted state variable accesses. In our experiments, the proposed algorithm experiences an average 6.4× increase in performance up to 128 go-routines, and a maximum 11.1× increase.