In the Bitcoin system, transactions arrive continuously at miners' mempools and await inclusion in future blocks. Every non-coinbase transaction must spend one or more unspent outputs created by previous transactions, inducing dependency constraints among transactions in the mempool. At the same time, miners are economically incentivized to prioritize transactions with higher fee rates, measured as transaction fee per unit size. This paper formulates the mempool linearization problem: given a set of transactions with associated fees, sizes, and dependency relationships, compute a dependency-respecting transaction ordering that maximizes fee-rate efficiency while supporting efficient updates as the mempool evolves dynamically. The problem is characterized through a partition of transactions into disjoint dependency-respecting subsets ordered by decreasing aggregate fee rate, together with an equivalent LP formulation. Motivated by structural properties of basic feasible solutions in the simplex method, a new algorithm called spanning forest linearization (SFL) is developed. Operating directly on the transaction dependency graph, SFL iteratively merges and splits chunks of transactions to refine a global ordering, and is guaranteed to terminate at an optimal solution. Evaluation on both synthetic and real-world Bitcoin mempool data shows that SFL consistently computes optimal linearizations with substantially lower runtime than competing approaches, including a method based on the parametric preflow algorithm of Gallo, Grigoriadis, and Tarjan. These results indicate that SFL provides a practical and scalable framework for transaction prioritization by decentralized miners in large and rapidly evolving mempools. SFL has also been incorporated into the Bitcoin Core codebase for transaction cluster linearization.
Zero-knowledge proof (ZKP) provers remain costly because multi-scalar multiplication (MSM) and number-theoretic transforms (NTTs) dominate runtime as they need significant computation. AI ASICs such as TPUs provide massive matrix throughput and SotA energy efficiency. We present MORPH, the first framework that reformulates ZKP kernels to match AI-ASIC execution. We introduce Big-T complexity, a hardware-aware complexity model that exposes heterogeneous bottlenecks and layout-transformation costs ignored by Big-O. Guided by this analysis, (1) at arithmetic level, MORPH develops an MXU-centric extended-RNS lazy reduction that converts high-precision modular arithmetic into dense low-precision GEMMs, eliminating all carry chains, and (2) at dataflow level, MORPH constructs a unified-sharding layout-stationary TPU Pippenger MSM and optimized 3/5-step NTT that avoid on-TPU shuffles to minimize costly memory reorganization. Implemented in JAX, MORPH enables TPUv6e8 to achieve up-to 10x higher throughput on NTT and comparable throughput on MSM than GZKP. Our code: https://github.com/EfficientPPML/MORPH.
Arivarasan Karmegam, Lucianna Kiffer, Antonio Fernández Anta
Blockchain validators can reduce block processing time by exploiting multi-core CPUs, but deterministic execution must preserve a given total order while respecting transaction conflicts and per-block runtime limits. This paper systematically examines how validators can exploit multi-core parallelism during both block construction and execution without violating blockchain semantics. We formalize two validator-side optimization problems: (i) executing an already ordered block on \(p\) cores to minimize makespan while ensuring equivalence to sequential execution; and (ii) selecting and scheduling a subset of mempool transactions under a runtime limit \(B\) to maximize validator reward. For both, we develop exact Mixed-Integer Linear Programming (MILP) formulations that capture conflict, order, and capacity constraints, and propose fast deterministic heuristics that scale to realistic workloads. Using Ethereum mainnet traces and including a Solana-inspired declared-access baseline (Sol) for ordered-block scheduling and a simple reward-greedy baseline (RG) for block construction, we empirically quantify the trade-offs between optimality and runtime.
Alfonso Cevallos, Robert Hambrock, Alistair Stewart
Merkle structures are widely used as commitment schemes: they allow a prover to publish a compact commitment to an ordered list $X$ of items, and then efficiently prove to a verifier that $x_i\in X$ is the $i$-th item in it. We compare different Merkle structures and their corresponding properties as commitment schemes in the context of blockchain applications. Our primary goal is to speed up light client protocols so that, e.g., a user can verify a transaction efficiently from their smartphone. For instance, the Merkle Mountain Range (MMR) yields a succinct scheme: a light client synchronizing for the first time can do so with a complexity sublinear in $|X|$. On the other hand, the Merkle chain, traditionally used to commit to block headers, is not succinct, but it is incremental - a light client resynchronizing frequently can do so with constant complexity - and optimally additive - the structure can be updated in constant time when a new item is appended to list $X$. We introduce new Merkle structures, most notably the Merkle Mountain Belt (MMB), the first to be simultaneously succinct, incremental and optimally additive. A variant called UMMB is also asynchronous: a light client may continue to interact with the network even when out of sync with the public commitment. Our Merkle structures are slightly unbalanced, so that items recently appended to $X$ receive shorter membership proofs than older items. This feature reduces a light client's expected costs, in applications where queries are biased towards recently generated data.
Setchain has been proposed to increase blockchain scalability by relaxing the strict total order requirement among transactions. Setchain organizes elements into a sequence of sets, referred to as epochs, so that elements within each epoch are unordered. In this paper, we propose and evaluate three distinct Setchain algorithms, that leverage an underlying block-based ledger. Vanilla is a basic implementation that serves as a reference point. Compresschain aggregates elements into batches, and compresses these batches before appending them as epochs in the ledger. Hashchain converts batches into fixed-length hashes which are appended as epochs in the ledger. This requires Hashchain to use a distributed service to obtain the batch contents from its hash. To allow light clients to safely interact with only one server, the proposed algorithms maintain, as part of the Setchain, proofs for the epochs. An epoch-proof is the hash of the epoch, cryptographically signed by a server. A client can verify the correctness of an epoch with $f+1$ epoch-proofs (where $f$ is the maximum number of Byzantine servers assumed). All three Setchain algorithms are implemented on top of the CometBFT blockchain application platform. We conducted performance evaluations across various configurations, using clusters of four, seven, and ten servers. Our results show that the Setchain algorithms reach orders of magnitude higher throughput than the underlying blockchain, and achieve finality with latency below 4 seconds.
We consider the online algorithmic challenge that is faced by blockchains that have multidimensional block constraints and serve quasi-patient bidders. We first provide online approximation algorithms for the important special cases of small transactions or a small number of dimensions; this solves open problems left by [Babaioff and Nisan, EC 2025]. Second, we study multidimensional variants of Ethereum's EIP-1559 protocol. We show that if the block builders manage to approximately optimize each block's welfare myopically, then an approximation to the global offline optimal welfare is obtained. On the other hand, we show that, unlike in the single-dimensional case, EIP-1559 by itself does not guarantee any good approximation.
The so-called blockchain trilemma asserts the impossibility of simultaneously achieving scalability, security, and decentralisation within a single blockchain protocol. In this paper, we formally refute that proposition. Employing predicate logic, formal automata theory, computational complexity analysis, and graph-theoretic measures of relay topology--specifically Baran's model of network path redundancy--we demonstrate that the trilemma constitutes a category error, conflates distinct analytical domains, and relies upon unproven causal assumptions. We further expose its reliance on composition fallacies drawn from flawed system implementations. A constructive counterexample is presented: a blockchain protocol exhibiting unbounded transaction throughput, cryptographic security under adversarial load, and multipath decentralised propagation. This example is not hypothetical but grounded in protocol design enabled by compact block relay, SPV verification, and IPv6 multicast. The trilemma is revealed not as a law of protocol architecture, but as a heuristic fallacy sustained by imprecision and design defeatism.
We consider a revenue-optimizing auctioneer in single-dimensional environments with matroid feasibility constraints. Akbarpour and Li (2020) argue that any revenue-optimal, truthful, and credible mechanism requires unbounded communication. Recent works (Ferreira and Weinberg, 2020; Essaidi et al., 2022; Chitra et al., 2024) circumvent their impossibility for the single-item setting through the use of cryptographic commitments and blockchains. We extend their results to matroid feasibility constraints. At a high level, the two-round Deferred-Revelation Auction (DRA) discussed by Ferreira and Weinberg (2020) and Chitra et al., (2024) requires each bidder to submit a deposit, which is slashed upon presenting verifiable evidence indicating a deviation from the behaviour prescribed by the mechanism. We prove that the DRA satisfies truthfulness, credibility and revenue-optimality for all matroid environments when bidders' values are drawn from $α$-strongly regular distributions for $α> 0$. Further, we argue that the DRA is not credible for any feasibility constraint beyond matroids and for any smaller deposits than suggested by previous literature even in single-item environments. Finally, we modify the Ascending Deferred-Revelation Auction (ADRA) for single-item settings proposed by Essaidi et al., (2022) for arbitrary bidder value distributions. We implement a deferred-revelation variant of the deferred-acceptance auction for matroids due to Bikhchandani et al., (2011), which requires the same bounded communication as the ADRA.
Dankrad Feist, Gottfried Herold, Mark Simkin, Benedikt Wagner
Data Availability Sampling (DAS), a central component of Ethereum's roadmap, enables clients to verify data availability without requiring any single client to download the entire dataset. DAS operates by having clients randomly retrieve individual symbols of erasure-encoded data from a peer-to-peer network. While the cryptographic and encoding aspects of DAS have recently undergone formal analysis, the peer-to-peer networking layer remains underexplored, with a lack of security definitions and efficient, provably secure constructions. In this work, we address this gap by introducing a novel distributed data structure that can serve as the networking layer for DAS, which we call robust distributed arrays. That is, we rigorously define a robustness property of a distributed data structure in an open permissionless network, that mimics a collection of arrays. Then, we give a simple and efficient construction and formally prove its robustness. Notably, every individual node is required to store only small portions of the data, and accessing array positions incurs minimal latency. The robustness of our construction relies solely on the presence of a minimal absolute number of honest nodes in the network. In particular, we avoid any honest majority assumption. Beyond DAS, we anticipate that robust distributed arrays can have wider applications in distributed systems.
In this paper, we introduce the Sarv, a novel non-monolithic blockchain-based data structure designed to represent hierarchical relationships between digitally representable components. Sarv serves as an underlying infrastructure for a wide range of applications requiring hierarchical data management, such as supply chain tracking, asset management, and circular economy implementations. Our approach leverages a tree-based data structure to accurately reflect products and their sub-components, enabling functionalities such as modification, disassembly, borrowing, and refurbishment, mirroring real-world operations. The hierarchy within Sarv is embedded in the on-chain data structure through a smart contract-based design, utilizing Algorand Standard Assets (ASAs). The uniqueness of Sarv lies in its compact and non-monolithic architecture, its mutability, and a two-layer action authorization scheme that enhances security and delegation of asset management. We demonstrate that Sarv addresses real-world requirements by providing a scalable, mutable, and secure solution for managing hierarchical data on the blockchain.
Designing automated market makers (AMMs) for prediction markets on combinatorial securities over large outcome spaces poses significant computational challenges. Prior research has primarily focused on combinatorial prediction markets within specific set systems (e.g., intervals, permutations). We introduce a framework for designing AMMs on arbitrary set systems by building a novel connection to the range query problem in computational geometry. This connection enables the analysis of computational complexity and the design of efficient AMMs. We first demonstrate the equivalence between price queries and trade updates under the popular combinatorial logarithmic market scoring rule market and the range query and range update problem. Building on this equivalence, we construct sublinear time algorithms when the VC dimension of the set system is bounded and show the non-existence of such algorithms for unbounded VC dimension cases. We then extend this approach to AMMs for combinatorial prediction markets with quadratic and power scoring rules. Finally, we show that the multi-resolution market design can be naturally integrated into the partition-tree scheme. Additionally, we introduce the combinatorial swap operation problem for automated market makers in decentralized finance and show that it can be efficiently reduced to range update problems.
Yunjie Pan, Omkar Bhalerao, C. Seshadhri, Nishil Talati
Counting the number of small subgraphs, called motifs, is a fundamental problem in social network analysis and graph mining. Many real-world networks are directed and temporal, where edges have timestamps. Motif counting in directed, temporal graphs is especially challenging because there are a plethora of different kinds of patterns. Temporal motif counts reveal much richer information and there is a need for scalable algorithms for motif counting. A major challenge in counting is that there can be trillions of temporal motif matches even with a graph with only millions of vertices. Both the motifs and the input graphs can have multiple edges between two vertices, leading to a combinatorial explosion problem. Counting temporal motifs involving just four vertices is not feasible with current state-of-the-art algorithms. We design an algorithm, TEACUPS, that addresses this problem using a novel technique of temporal path sampling. We combine a path sampling method with carefully designed temporal data structures, to propose an efficient approximate algorithm for temporal motif counting. TEACUPS is an unbiased estimator with provable concentration behavior, which can be used to bound the estimation error. For a Bitcoin graph with hundreds of millions of edges, TEACUPS runs in less than 1 minute, while the exact counting algorithm takes more than a day. We empirically demonstrate the accuracy of TEACUPS on large datasets, showing an average of 30$\times$ speedup (up to 2000$\times$ speedup) compared to existing GPU-based exact counting methods while preserving high count estimation accuracy.
Layer-two blockchain protocols emerged to address scalability issues related to fees, storage cost, and confirmation delay of on-chain transactions. They aggregate off-chain transactions into a fewer on-chain ones, thus offering immediate settlement and reduced transaction fees. To preserve security of the underlying ledger, layer-two protocols often work in a collateralized model; resources are committed on-chain to backup off-chain activities. A fundamental challenge that arises in this setup is determining a policy for establishing, committing, and replenishing the collateral in a way that maximizes the value of settled transactions. In this paper, we study this problem under two settings that model collateralized layer-two protocols. The first is a general model in which a party has an on-chain collateral C with a policy to decide on whether to settle or discard each incoming transaction. The policy also specifies when to replenish C based on the remaining collateral value. The second model considers a discrete setup in which C is divided among k wallets, each of which is of size C/k, such that when a wallet is full, and so cannot settle any incoming transactions, it will be replenished. We devise several online policies for these models, and show how competitive they are compared to optimal (offline) policies that have full knowledge of the incoming transaction stream. To the best of our knowledge, we are the first to study and formulate online competitive policies for collateral and wallet management in the blockchain setting.
Emily Clark, Chloe Georgiou, Katelyn Poon, Marek Chrobak
In his 2018 paper, Herlihy introduced an atomic protocol for multi-party asset swaps across different blockchains. His model represents an asset swap by a directed graph whose nodes are the participating parties and edges represent asset transfers, and rational behavior of the participants is captured by a preference relation between a protocol's outcomes. Asset transfers between parties are achieved using smart contracts. These smart contracts are quite involved and they require storage and processing of a large number of paths in the swap digraph, limiting practical significance of his protocol. His paper also describes a different protocol that uses only standard hash time-lock contracts (HTLC's), but this simpler protocol applies only to some special types of digraphs. He left open the question whether there is a simple and efficient protocol for cross-chain asset swaps in arbitrary digraphs. Motivated by this open problem, we conducted a comprehensive study of \emph{HTLC-based protocols}, in which all asset transfers are implemented with HTLCs. Our main contribution is a full characterization of swap digraphs that have such protocols.
Marcell Dietl, Andre Gemünd, Daniel Oeltz, Felix M. Thiele · 5 authors
In this report, we introduce a novel approach to visualize extremely large graphs efficiently. Our method combines two force-directed algorithms, Kamada-Kawai and ForceAtlas2, to handle different graph components based on their node count. Additionally, we suggest utilizing the Fast Multipole method to enhance the speed of ForceAtlas2. Although initially designed for analyzing bitcoin transaction graphs, for which we present results here, this algorithm can also be applied to other crypto currency transaction graphs or graphs from diverse domains.
Leader Election (LE) is crucial in distributed systems and blockchain technology, ensuring one participant acts as the leader. Traditional LE methods often depend on distributed random number generation (RNG), facing issues like vulnerability to manipulation, lack of fairness, and the need for complex procedures such as verifiable delay functions (VDFs) and publicly-verifiable secret sharing (PVSS). This Bachelor's thesis presents a novel approach to randomized LE, leveraging a game-theoretic assumption that participants, aiming to be chosen as leaders, will naturally avoid actions that diminish their chances. This perspective simplifies LE by eliminating the need for decentralized RNG. Introducing PureLottery, inspired by single-elimination sports tournaments, this method offers a fair, bias-resistant, and efficient LE solution for blockchain environments. It operates on the principle of two participants competing in each match, rendering collusion efforts useless. PureLottery stands out for its low computational and communication complexity, suitable for smart contract implementation. It provides strong game-theoretic incentives for honesty and is robust against adversaries, ensuring no increase in election chances through dishonesty. The protocol guarantees that each honest player has at least a 1/n chance of winning, irrespective of adversary manipulation among the other n-1 participants. PureLottery can also address related problems like participant ranking, electing multiple leaders, and leader aversion, showcasing its versatility across various applications, including lotteries and blockchain protocols. An open-source implementation is made available for public use.
Popular blockchains today have hundreds of thousands of nodes and need to be able to support sophisticated scaling solutions$\unicode{x2013}$such as sharding, data availability sampling, and layer-2 methods. Designing secure and efficient peer-to-peer (p2p) networking protocols at these scales to support the tight demands of the upper layer crypto-economic primitives is a highly non-trivial endeavor. We identify decentralized, uniform random sampling of nodes as a fundamental capability necessary for building robust p2p networks in emerging blockchain networks. Sampling algorithms used in practice today (primarily for address discovery) rely on either distributed hash tables (e.g., Kademlia) or sharing addresses with neighbors (e.g., GossipSub), and are not secure in a Sybil setting. We present Honeybee, a decentralized algorithm for sampling nodes that uses verifiable random walks and table consistency checks. Honeybee is secure against attacks even in the presence of an overwhelming number of Byzantine nodes (e.g., $\geq50\%$ of the network). We evaluate Honeybee through experiments and show that the quality of sampling achieved by Honeybee is significantly better compared to the state-of-the-art. Our proposed algorithm has implications for network design in both full nodes and light nodes.
Conflict-free Replicated Data Types (CRDTs) are designed for replica convergence without global coordination or consensus. Recent work has achieved the same in a Byzantine environment, through DAG-like structures based on cryptographic hashes of content. The blocklace is a partially-ordered generalization of the blockchain in which each block has any finite number of signed hash pointers to preceding blocks. We show that the blocklace datatype, with the sole operation of adding a single block, is a CRDT: it is both a pure operation-based CRDT, with self-tagging; and a delta-state CRDT, under a slight generalization of the delta framework. Allowing arbitrary values as payload, the blocklace can also be seen as a universal Byzantine fault-tolerant implementation for arbitrary CRDTs, under the operation-based approach. Current approaches only care about CRDT convergence, being equivocation-tolerant (they do not detect or prevent equivocations), allowing a Byzantine node to cause an arbitrary amount of harm by polluting the CRDT state with an unbounded number of equivocations. We show that the blocklace can be used not only in an equivocation-tolerant way, but also so as to detect and eventually exclude Byzantine nodes, including equivocators, even under the presence of undetectable colluders. The blocklace CRDT protocol ensures that a Byzantine node may harm only a finite prefix of the computation.
Tariqul Islam, Faisal Haque Bappy, Md Nafis Ul Haque Shifat, Farhan Ahmad · 6 authors
An efficient, scalable, and provably secure dynamic auditing scheme is highly desirable in the cloud storage environment for verifying the integrity of the outsourced data. Most of the existing work on remote integrity checking focuses on static archival data and therefore cannot be applied to cases where dynamic data updates are more common. Additionally, existing auditing schemes suffer from performance bottlenecks and scalability issues. To address these issues, in this paper, we present a novel dynamic auditing scheme for centralized cloud environments leveraging an enhanced version of the B-tree. Our proposed scheme achieves the immutable characteristic of a decentralized system (i.e., blockchain technology) while effectively addressing the synchronization and performance challenges of such systems. Unlike other static auditing schemes, our scheme supports dynamic insert, update, and delete operations. Also, by leveraging an enhanced B-tree, our scheme maintains a balanced tree after any alteration to a certain file, improving performance significantly. Experimental results show that our scheme outperforms both traditional Merkle Hash Tree-based centralized auditing and decentralized blockchain-based auditing schemes in terms of block modifications (e.g., insert, delete, update), block retrieval, and data verification time.
Merkle trees have become a widely successful cryptographic data structure. Enabling a vast variety of applications from checking for inconsistencies in databases like Dynamo to essential tools like Git to large scale distributed systems like Bitcoin and other blockchains. There have also been various versions of Merkle trees like Jellyfish Merkle Trees and Sparse Merkle Trees designed for different applications. However, one key drawback of all these Merkle trees is that with a large data set the cost of computing the tree increases significantly, moreover insert operations on a single leaf require re-building the entire tree. For certain use cases building the tree this way is acceptable, however in environments where compute time needs to be as low as possible and where data is processed in parallel, we are presented with a need for asynchronous computation. This paper proposes a solution where given a batch of data that has to be processed concurrently, a Merkle Tree can be constructed from the batch asynchronously without needing to recalculate the tree for every insert.
Ryan Zarick, Bryan Pellegrino, Isaac Zhang, Thomas Kim · 5 authors
We present ColorFloat, a family of O(1) space complexity algorithms that solve the problem of attributing (coloring) fungible tokens to the entity that minted them (minter). Tagging fungible tokens with metadata is not a new problem and was first formalized in the Colored Coins protocol. In certain contexts, practical solutions to this challenge have been implemented and deployed such as NFT. We define the fungible token coloring problem, one specific aspect of the Colored Coins problem, to be the problem of retaining fungible characteristics of the underlying token while accurately tracking the attribution of fungible tokens to their respective minters. Fungible token coloring has a wide range of Web3 applications. One application which we highlight in this paper is the onchain yield-sharing collateral-based stablecoin.
Coin selection algorithms are a fundamental component of blockchain technology. In this paper, we present a comprehensive review of the existing coin selection algorithms utilized in unspent transaction output (UTXO)-based blockchains. We provide a list of the desired objectives and categorize existing algorithms into three types: primitive, basic, and advanced algorithms. This allows for a structured understanding of their functionalities and limitations. We also evaluate the performance of existing coin selection algorithms. The aim of this paper is to provide system researchers and developers with a concrete view of the current design landscape.
Boqian Ma, Vir Nath Pathak, Lanping Liu, Sushmita Ruj
A sparse Merkle tree is a Merkle tree with fixed height and indexed leaves given by a map from indices to leaf values. It allows for both efficient membership and non-membership proofs. It has been widely used as an authenticated data structure in various applications, such as layer-2 rollups for blockchains. zkSync Lite, a popular Ethereum layer-2 rollup solution, uses a sparse Merkle tree to represent the state of the layer-2 blockchain. The account information is recorded in the leaves of the tree. In this paper, we study the sparse Merkle tree algorithms presented in zkSync Lite, and propose an efficient batch update algorithm to calculate a new root hash given a list of account (leaf) operations. Using the construction in zkSync Lite as a benchmark, our algorithm 1) improves the account update time from $\mathcal{O}(\log n)$ to $\mathcal{O}(1)$ and 2) reduces the batch update cost by half using a one-pass traversal. Empirical analysis of real-world block data shows that our algorithm outperforms the benchmark by at most 14%.