How Transaction Order Finality Drives Blockchain State in Layer 2 Systems

Table of Links

Abstract and 1. Introduction

2. Key Concepts

   2.1 Append-Only Log and 2.2 Virtual Machine State

   2.3 Transactions As Curried Functions

   2.4 Natural Names of State

   2.5 Ground Truth

   2.6 Efficient Representations of State

   2.7 Checkpoints

   2.8 Execution Parameters: callData

   2.9 Execution Ordering

   2.10 Deciding on the Correct State

3. Ideal Layer 2 Design

   3.1 VM Job Queue and Transaction Order Finality

   3.2 Data Availability and Garbage Collection

   3.3 State Finality

   3.4 Checkpoint Finality

4. Conclusion and References

A. Discrepancy Detection Security Parameters

4 Conclusion

The main contribution of this paper is that transaction order finality should be viewed as the key for determining system state. Computing an efficient representation is just an optimization, since state can be reconstituted from a checkpoint state and those transactions that follows it. We identify the following shades of finality: log finality, transaction order finality, state finality, and checkpoint finality. These notions are useful for reasoning about blockchain design and the design space for error/fault handling, from independent faults due to Byzantine actors to common-mode faults due to zero-day software defects.

Based on considering how and when these finality properties should be achieved, we developed a preliminary design sketch for an “ideal” layer 2 system, and discussed some of the trade-offs.

References

[1] Al-Bassam, M. LazyLedger: A distributed data availability ledger with client-side smart contracts, 2019.

[2] Azouvi, S., Danezis, G., and Nikolaenko, V . Winkle: Foiling long-range attacks in proof-of-stake systems. In Proceedings of the 2nd ACM Conference on Advances in Financial Technologies (2020), pp. 189–201.

[3] Benet, J. IPFS-content addressed, versioned, P2P file system. arXiv preprint arXiv:1407.3561 (2014).

[4] Daian, P., Goldfeder, S., Kell, T., Li, Y., Zhao, X., Bentov, I., Breidenbach, L., and Juels, A. Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In 2020 IEEE Symposium on Security and Privacy (SP) (2020), pp. 910–927.

[5] Felton, E. The cheater checking problem: Why the verifier’s dilemma is harder than you think. Accessed 21/08/2021, https://medium.com/offchainlabs/thecheater-checking-problem-why-the-verifiersdilemma-is-harder-than-you-think-9c7156505ca1.

[6] Heilman, E., Kendler, A., Zohar, A., and Goldberg, S. Eclipse attacks on bitcoin’s peer-to-peer network. In 24th USENIX Security Symposium (USENIX Security 15) (Washington, D.C., Aug. 2015), USENIX Association, pp. 129–144.

[7] Hopwood, D., Bowe, S., Hornby, T., and Wilcox, N. Zcash protocol specification. GitHub: San Francisco, CA, USA (2016).

[8] Kalodner, H., Goldfeder, S., Chen, X., Weinberg, S. M., and Felten, E. W.Arbitrum: Scalable, private smart contracts. In 27th {USENIX} Security Symposium ({USENIX} Security 18) (2018), pp. 1353– 1370.

[9] Kelkar, M., Zhang, F., Goldfeder, S., and Juels, A. Order-fairness for byzantine consensus. In Annual International Cryptology Conference (2020), Springer, pp. 451–480.

[10] Luu, L., Teutsch, J., Kulkarni, R., and Saxena, P. Demystifying incentives in the consensus computer. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (2015), pp. 706–719.

[11] Matter Labs. zkSync 2.0: Hello ethereum! https://medium.com/matter-labs/zksync-2-0-helloethereum-ca48588de179.

[12] Mitchell, C. Front-running. https://www. investopedia.com/terms/f/frontrunning.asp. Accessed: 2021-09-01.

[13] Noyes, C. MEV and me. Accessed 08/09/2018, https: //research.paradigm.xyz/MEV.

[14] Teutsch, J., and Reitwießner , C . A scalable verification solution for blockchains. arXiv preprint arXiv:1908.04756 (2019).