A Limitlessly Scalable Transaction System

We present Accept, a simple, asynchronous transaction system that achieves perfect horizontal scaling.

Usual blockchain-based transaction systems come with a fundamental throughput limitation as they require that all (potentially unrelated) transactions must be totally ordered. Such solutions thus require serious compromises or are outright unsuitable for large-scale applications, such as global retail payments.

Accept provides efficient horizontal scaling without any limitation. To that end, Accept satisfies a relaxed form of consensus and does not establish an ordering of unrelated transactions. Furthermore, Accept achieves instant finality and does not depend on a source of randomness.

Authors and Affiliations

1. ETH Zürich, Zürich, Switzerland

   Max Mathys, Roland Schmid, Jakub Sliwinski & Roger Wattenhofer

Corresponding author

Correspondence to Jakub Sliwinski .

Editors and Affiliations

1. Samovar, Télécom SudParis, Institut Polytechnique de Paris, Palaiseau, France

   Joaquin Garcia-Alfaro

2. Universitat Autonoma de Barcelona, Bellaterra, Spain

   Guillermo Navarro-Arribas

3. Technical University of Denmark, Lyngby, Denmark

   Nicola Dragoni

A Concepts

This section will clarify the concepts of Merkle signatures and hash maps. Merkle signatures are used in Sect. 3.4 to improve the efficiency of validators. A custom hash map is developed to improve the performance of the UTXO store, as described in Sect. 4.2.

1.1 A.1 Merkle Signatures

A signature scheme based on Merkle trees is used to optimize the performance of validators when creating and verifying signatures.

Signing. A validator \(S_i\) collects n hashes to sign where \(n=2^k, k \in \mathbb {N}\). The hashes are combined into a Merkle tree. The validator \(S_i\) signs the Merkle root m using EdDSA, denoted as \(m_{S_i}\). For each hash \(h_i, i \in \{1,..,n\}\), the validator calculates the Merkle path and outputs \(path_{h_i}\). \(path_{h_i}\) consists of the hashes and side (left or right) of the nodes from \(h_i\) to the Merkle root (in blue). The resulting signature for \(h_i\) by \(S_i\) is the tuple \((path_{h_i}, m_{S_i})\). An example can be seen in Fig. 2.

Signing n hashes using Merkle signatures is more efficient than signing n hashes separately: the cost of an EdDSA signing operation \(c_s\) is much higher than the cost of a hash operation \(c_h\). The cost of signing n hashes with Merkle signatures is \(2n\cdot c_h + c_v\) whereas the cost of signing n hashes separately (without Merkle signatures) is \(n \cdot c_v\).

Merkle tree and Merkle signature for hash \(h_3\). (Color figure online)

Full size image

Verifying. First, the Merkle root \(m'\) is reconstructed from the path \(path_{h_i}\). If \(path_{h_i}\) is a valid path, \(m'\) matches m. Finally, \(m_{S_i}\) is verified using EdDSA.

Verifying n hashes using Merkle signatures is also more efficient than verifying n hashes separately because the cost of an EdDSA verification operation is high, even higher than an EdDSA signing operation (and thus also higher than the cost of a hashing operation). The Merkle root can be reconstructed with a cost of \(\log _2(n) \cdot c_h\) where \(c_h\) is the cost of hashing. The Merkle root m only has to be verified for the first encountered Merkle signature, after that, the result of the verification can be cached, making this signature perform very well.

1.2 A.2 Hash Maps

Hash maps are used to efficiently calculate set membership in the context of spent UTXO identifiers. Elements \(e \in E\) (in our case \(id_i\)) are hashed into the hash range \(H = \{0,...,l\}\) and used as an index to an array of linked lists. A linked list at index \(i \in \{0, ..., l\}\) contains all items e where \(\textrm{hash}(e) = i\). The linked list is then traversed.

Hashing and indexing are implemented as a lock-free operation; traversing and modifying a linked list are protected by a mutex. If l is large enough, the probability of hash collisions is small, minimizing lock contention and the length of the linked list.

Reprints and permissions

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics