BF skip indexes for Ethereum

<p><strong>General information</strong></p> <p>This repository includes all data needed to reproduce the experiments presented in [1].<br>The paper describes the<em> BF skip index,</em> a data structure based on Bloom filters [2] that can be used for answering inter-block queries on blockchains efficiently. The article also includes a historical analysis of <code>logsBloom</code> filters included in the Ethereum block headers, as well as an experimental analysis of the proposed data structure. The latter was conducted using the data set of events generated by the <a href="https://etherscan.io/address/0x06012c8cf97bead5deae237070f9587f8e7a266d">CryptoKitties Core</a> contract, a popular decentralized application launched in 2017 (and also one of the first applications based on NFTs).</p> <p>In this description, we use the following abbreviations (also adopted throughout the paper) to denote two different sets of Ethereum blocks.</p> <ol> <li>D1: set of all Ethereum blocks between height 0 and 14999999.</li> <li>D2: set of all Ethereum blocks between height 14000000 and 14999999.</li> </ol> <p>Moreover, in accordance with the terminology adopted in the paper, we define the set of <em>keys </em>of a block as the set of all contract addresses and log topics of the transactions in the block. As defined in [3], log topics comprise event signature digests and the indexed parameters associated with the event occurrence.</p> <p><strong>Data set description</strong></p> <table> <tbody> <tr> <td>File</td> <td>Description</td> </tr> <tr> <td>filters_ones_0-14999999.csv.xz</td> <td>Compressed CSV file containing the number of ones for each logsBloom filter in D1.</td> </tr> <tr> <td>receipt_stats_0-14999999.csv.xz</td> <td>Compressed CSV file containing statistics about all transaction receipts in D1.</td> </tr> <tr> <td>Approval.csv</td> <td>CSV file containing the Approval event occurrences for the CryptoKitties Core contract in D2.</td> </tr> <tr> <td>Birth.csv</td> <td>CSV file containing the Birth event occurrences for the CryptoKitties Core contract in D2.</td> </tr> <tr> <td>Pregnant.csv</td> <td>CSV file containing the Pregnant event occurrences for the CryptoKitties Core contract in D2.</td> </tr> <tr> <td>Transfer.csv</td> <td>CSV file containing the Transfer event occurrences for the CryptoKitties Core contract in D2.</td> </tr> <tr> <td>events.xz</td> <td>Compressed binary file containing information about all contract events in D2.</td> </tr> <tr> <td>keys.xz</td> <td>Compressed binary file containing information about all keys in D2.</td> </tr> </tbody> </table> <p><strong>File structure</strong></p> <p>We now describe the structure of the files included in this repository.</p> <ul> <li>filters_ones_0-14999999.csv.xz is a compressed CSV file with 15 million rows (one for each block in D1) and 3 columns. Note that it is not necessary to decompress this file, as the provided code is capable of processing it directly in its compressed form. The columns have the following meaning. <ol> <li><code>blockId</code>: the identifier of the block.</li> <li><code>timestamp</code>: timestamp of the block.</li> <li><code>numOnes</code>: number of bits set to 1 in the <code>logsBloom</code> filter of the block.</li> </ol> </li> <li>receipt_stats_0-14999999.csv.xz is a compressed CSV file with 15 million rows (one for each block in D1) and 5 columns. As for the previous file, it is not necessary to decompress this file. <ol> <li><code>blockId</code>: the identifier of the block.</li> <li><code>txCount</code>: number of transactions included in the block.</li> <li><code>numLogs</code>: number of event logs included in the block.</li> <li><code>numKeys</code>: number of keys included in the block.</li> <li><code>numUniqueKeys</code>: number of distinct keys in the block (useful as the same key may appear multiple times).</li> </ol> </li> <li>All CSV files related to the CryptoKitties Core events (i.e., Approval.csv, Birth.csv, Pregnant.csv, Transfer.csv) have the same structure. They consist of 1 million rows (one for each block in D2) and 2 columns, namely: <ol> <li><code>blockId</code>: identifier of the block.</li> <li><code>numOcc</code>: number of event occurrences in the block.</li> </ol> </li> <li>events.xz is a compressed binary file describing all <em>unique</em> event occurrences in the blocks of D2. The file contains 1 million data chunks (i.e., one for each Ethereum block). Each chunk includes the following information. Do note that this file only records <em>unique</em> event occurrences in each block, meaning that if an event from a contract is triggered more than once within the same block, there will be only one sequence within the corresponding chunk. <ol> <li><code>blockId</code>: identifier of the block (4 bytes).</li> <li><code>numEvents</code>: number of event occurrences in the block (4 bytes).</li> <li>A list of <code>numEvent</code> sequences, each made up of 52 bytes. A sequence represents an event occurrence and is indeed the concatenation of two fields, namely: <ol> <li>Address of the contract triggering the event (20 bytes).</li> <li>Event signature digest (32 bytes).</li> </ol> </li> </ol> </li> <li>keys.xz is a compressed binary file describing all unique keys in the blocks of D2. As for the previous file, duplicate keys only appear once. The file contains 1 million data chunks, each representing an Ethereum block and including the following information. <ol> <li><code>blockId</code>: identifier of the block (4 bytes)</li> <li><code>numAddr</code>: number of unique contract addresses (4 bytes).</li> <li><code>numTopics</code>: number of unique topics (4 bytes).</li> <li>A sequence of <code>numAddr</code> addresses, each represented using 20 bytes.</li> <li>A sequence of <code>numTopics</code> topics, each represented using 32 bytes.</li> </ol> </li> </ul> <p><strong>Notes</strong></p> <p>For space reasons, some of the files in this repository have been compressed using the XZ compression utility. Unless otherwise specified, these files need to be decompressed before they can be read. Please make sure you have an application installed on your system that is capable of decompressing such files.</p> <p><strong>Cite this work<br></strong></p> <p>If the data included in this repository have been useful, please cite the following article in your work.</p> <pre><code>@article{loporchio2025skip, title={Skip index: Supporting efficient inter-block queries and query authentication on the blockchain}, author={Loporchio, Matteo and Bernasconi, Anna and Di Francesco Maesa, Damiano and Ricci, Laura}, journal={Future Generation Computer Systems}, volume={164}, pages={107556}, year={2025}, publisher={Elsevier} }</code></pre> <p><strong>References</strong></p> <ol> <li>Loporchio, Matteo et al. "Skip index: supporting efficient inter-block queries and query authentication on the blockchain". Future Generation Computer Systems 164 (2025): 107556. <a href="https://doi.org/10.1016/j.future.2024.107556" target="_blank" rel="noopener">https://doi.org/10.1016/j.future.2024.107556</a></li> <li>Bloom, Burton H. "Space/time trade-offs in hash coding with allowable errors." <em>Communications of the ACM</em> 13.7 (1970): 422-426.</li> <li>Wood, Gavin. "Ethereum: A secure decentralised generalised transaction ledger." <em>Ethereum project yellow paper</em> 151.2014 (2014): 1-32.</li> </ol>