Fast Signature Aggregation Protocol for Single Slot Finality

--- author: - Tapolcai János and Bence LadÃ³czki bibliography: - reference.bib date: February 2023 title: Fast Signature Aggregation Protocol for Single Slot Finality --- # Project Abstract The project proposes to solve the verification bottleneck of Casper. We aim to aggregate $\sim300K$ signatures issued by the $2/3$ of the validators to achieve single-slot finality. The proposed aggregation scheme uses state-of-the-art techniques in cryptography, network coding, and succinct data structures. # Objectives A system design, theoretical proofs of its performance and performance related measurements with large-scale simulations. We open-source our code and summarize our findings in a scientific paper submitted to IEEE INFOCOM 2024 or a similar high quality venue, e.g. NDSS or ACM CCS. # Outcomes We aim to deliver single slot (12 seconds) on-chain Casper finality loops. We see a space-time tradeoff in signature aggregation schemes. On one hand, the signatures stored on-chain must not occupy too much space. On the other hand, the time to achieve finality is also an important performance metric. We investigate a two-step solution. The primary objective of the first step is to achieve finality in the shortest time by sacrificing space, and once each validator has generated a proof on the votes from $2/3$ of the validators, a second step commences with the aim of finding a small proof of finality that will later be submitted to the chain through a lengthy process. # Grant Scope Currently, the aggregation schemes in Ethereum 2.0 use an aggregation tree (subcommittees) to collect votes from validators. Although the aggregated signature is small, storing the subset of validators who voted requires significant space. Right now, this is done using a binary array (called *bitlist*). With bitlists one can only aggregate disjunct sets of signatures. This is ensured through the rigid structure of the aggregation tree (validators are assigned to subcommittees), to avoid overlapping. Our high-level idea is the following intuition. When the task is to collect data quickly, it is usually worth sending more data such that the nodes rather share everything they know with each other than coordinate the data collection. And bitmaps in Ethereum 2.0 require a lot of coordination. In the project, we investigate the use of sophisticated data structures for storing the set of validators for each aggregated signature, allowing fully distributed P2P gossiping protocols to collect votes. The data structure we propose is a succinct representation of an integer array. This simplifies the signature aggregation process and makes it much faster to reach finality. To achieve this, we focus on solving the following four research problems. ## Task 1: Design of compressed data structure for faster signature aggregation Here the task is to store the set of validators who have already voted, along with an integer weight for each of them that should represent the number of times their vote is part of the aggregated signature. The compressed data structure should be capable of efficient union operation when two (already aggregated) signatures are aggregated into one. The list of validators is known (stored on-chain); thus, we can refer to them using their ID, which is an integer number in the range $[0,n]$ where $n$ is the maximum number of validators. In the Ethereum 2.0 specification $n\leq 2^{22}$. For efficient union operation, we store an ordered list of validator IDs. Moreover, instead of the IDs themselves, we store the difference between the adjacent elements in the array. Since the list is ordered, the differences are non-negative. It is zero if a validator's signature is part of the aggregated signature multiple times. We store the differences using prefix codes (variable-length codes), such as Huffman codes. Hufmann codes can attain the theoretical "compression" limit established by Shannon if the distribution of each symbol of the coding alphabet (the integer differences of the IDs) is known apriori. As a part of the project, we simulate such a signature aggregation scheme and suggest distributions for the coding alphabet that work well in actual implementations. ## Task 2: Investigate efficient signature aggregation schemes Signature schemes usually implement three functions: keygen, sign, verify, and aggregate. Here aggregate means for a given two (possibly already aggregated signatures) to generate a single aggregated signature. Today BLS signatures are ubiquitous in blockchains, mostly due to their convenient support for signature aggregation and, in general, better space efficiency. This comes at a price of slower operations than traditional ECDSA or Schnorr. However, Casper could do without the full flexibility of aggregation in BLS because the message that needs to be signed does not change. Therefore we invetigate t a simplified Schnorr signature scheme that allows simple aggregation while it is much faster than BLS in terms of signature verification. The idea is to compute the cryptographic hash function on the message (without concatenating it with the nonce commitment). This can achieve basically the same efficiency in aggregation as BLS. Because aggregating two such simplified Schnorr signatures only requires adding two points on an elliptic curve (and adding numbers in the prime field), even if the two simplified Schnorr signatures are aggregated. ## Task 3: Simulating gossiping in the P2P network to achieve finality Based on the outcome of Task 1 and Task 2, we can now design the gossiping protocol to collect the required amount of signatures to provide finality in a single slot. If downloading the previous block and generating the new block takes little time, thus we have almost 12 seconds to collect a proof of a sufficient number of votes (signatures) that can even be attached to the new block. This way, the nodes can immediately verify if finality is achieved when downloading the new block. It can simplify Casper's supermajority link mechanism. The idea is that the validators iteratively exchange the information they have about votes. Each message contains an aggregated signature (defined in Task 1) and a succinct representation of the list validators with their weights. In each iteration, a single aggregated signature is computed based on the (aggregated) signatures the validator has received. For example, in the first iteration, every validator signs the new block and sends its signature to its neighbors. Giant Ethereum validators (Binance, Lido Finance, Coinbase, Kraken, etc.) can send aggregated signatures in the first iteration. Second, the validator generates a single aggregated signature and sends it to all its neighbors with a list of validators involved in it. Third, each validator generates an aggregated signature of these, ideally signed by every validator in a two-hop distance and signed multiple times by its neighbors. This is repeated until the validator has a sufficient number of signatures. The P2P network of Ethereum is 3.7 hops wide on average (and at most 6 hops wide)[^1]. Therefore this will probably be achieved after 4 or 5 iterations. These messages becomes larger and larger as the compressed data structure stores more and information, i.e. more and more validators participating in the an aggregated signature. Once they reach the maximum message transmission unit (MTU) sizes ($\sim1500$bytes), there is no need to aggregate them further, and the protocol turns into a traditional gossiping protocol. Therefore the succinct data structure of Task 2 should be tailored to the outcome of Task 3 such that its size fits in a single IP packet (until the last iteration). In our preliminary estimate, each IP packet can store $50-100K$ aggregated signatures. ## Task 4: Collecting signatures to generate a space-efficient finality proof So far, our goal has been to optimize the speed of reaching finality, by generating a possibly larger off-chain proof. The next step is to generate a space-efficient proof of finality to add on-chain. In this second step, time is not an issue. An ideal solution would be to have an aggregated signature that is signed by every validator (single time) because then it is enough to add a single aggregated signature (64 bytes). Once we have a large aggregated signature reaching finality, the next task is to collect individual (or aggregated) signatures from the validators that are not part of this aggregated signature or they are part of them albeit multiple times. We call them *imperfect* validators. For this purpose, we will use a different data structure to store the list of these imperfect validators, in other words, the complementary set. The block proposal and the imperfect validators will be incentivized to cooperate in this process. In other words, the imperfect validators will be punished unless they provide a signature in this lengthy second step. # Project Team We plan to have three teams working on cryptography, data structures, and computer networm related tasks. Each team shall have one MSc student and one or two experts. János Tapolcai is an expert in computer science and computer networks; he would be working 80 hours per month for 6 months. Bence Ladóczki is an expert in algorithmic implementations; he would be working 80 hours per month for 6 months. Lajos Rónyai is an expert in theoretical computer science; he would be working 20 hours per month for 3 months. We plan to have 2 MSc students, each working 80 hours per month on implementing the algorithms for 4 months. # Background **János Tapolcai** He is a full professor at the Budapest University of Technology and Economics. He has received the prestigious *Lendulet* (Momentum) Grant (2012--2017), the Hungarian equivalent to the ERC Starting Grant, to establish his research group. He has published 16 papers at the IEEE Infocom conference. He is recognized for applied mathematical achievements in practically relevant problems of communication networks. He is active in international collaborations with highly recognized scholars. In 2013 he received Google Faculty Award for designing and implementing succinct data structures in routers. **Bence Ladóczki** He is an assistant research fellow at the Budapest University of Technology and Economics. e is the developer of the electron repulsion integral driver of the MRCC[^2] program suite. During his post graduate years he developed massively parallel algorithms for the K computer in Japan. Since 2021 he has been working on blockchain related problems, including atomic swaps[^3] and signature algorithms. As such he has several years of experience in implementations of algorithms and high performance computing. **Lajos Rónyai** is a Research Professor with the Institute of Computer Science and Control, Eötvös Loránd Research Network, Budapest, Hungary. He leads a research group there which focuses on theoretical computer science, number theory and discrete mathematics. He is also a Full Professor at the Mathematics Institute of the Budapest University of Technology and Economics. He received the Ph.D. degree in 1987 from the Eötvös Loránd University Budapest. His research interests include efficient algorithms, complexity of computation, algebra, and discrete mathematics.   # Methodology **Task 1:** We develop a succinct data structure to store the multi-set of validators. We deliver an implementation and evaluate its performance. **Task 2:** We survey the theory related to aggregated schemes. Many studies have slightly different definitions of signature aggregation. We define these primitives and survey these papers. We implement the simplified Schnorr signature scheme and evaluate its performance when singing, verifying, and aggregating signatures. Finally, we plan to compare its performance with BLS. **Task 3:** We develop a gossiping algorithm that can collect $300K$ signatures in 9 seconds. We evaluate it by simulating Ethereum's P2P network and bolster it with a scalability analysis. **Task 4:** We devise a methodology for the second step of the finality gadget and find a method to generate succint proofs of validity. We analyze different punishment strategies to disincentivise imperfect validators. **Dissemination Task:** Theoretical results of Tasks 1-4 will be summarized in a study and will be submitted to an IEEE Infocom conference. # Timeline ![](https://i.imgur.com/x1bebVK.jpg) # Budget We estimate 1040 hours of working time for the expert members of our team. An amount of 14.5 ETH shall cover the related labour costs. An additional 640 hours for MSc students accounts for 3.3 ETH according to our calculations. [^1]: T. Wang, C. Zhao, Q. Yang, S. Zhang, and S. C. Liew, "Ethna: Analyzing the underlying peer-to-peer network of ethereum blockchain",*IEEE Transactions on Network Science and Engineering*, vol.8, no.3, pp. 2131--2146, 2021. [^2]: https://www.mrcc.hu/index.php [^3]: B. Ladóczki, J. Bíró, and J. Tapolcai, `"Stochastic analysis of the success rate in atomic swaps between blockchains,"" in *International Conference on Blockchain Computing and Applications (BCCA)*, 2022, pp. 41--46.