Blockchains are decentralized; are they genuinely? We analyze blockchain decentralization's often-overlooked but quantifiable dimension: geospatial distribution of transaction processing. Blockchains bring with them the potential for geospatially distributed transaction processing. They enable validators from geospatially distant locations to partake in consensus protocols; we refer to them as minority validators. Based on our observations, in practice, most validators are often geographically concentrated in close proximity. Furthermore, we observed that minority validators tend not to meet the performance requirements, often misidentified as crash failures. Consequently, they are subject to punishment by jailing (removal from the validator set) and/or slashing (penalty in native tokens). Our emulations, under controlled conditions, demonstrate the same results, raising serious concerns about the potential for the geospatial centralization of validators. To address this, we developed a solution that easily integrates with consensus protocols, and we demonstrated its effectiveness.
Collin Meese, Hang Chen, Syed Ali Asif, Wanxin Li · 6 authors
Accurate real-time traffic flow prediction can be leveraged to relieve traffic congestion and associated negative impacts. The existing centralized deep learning methodologies have demonstrated high prediction accuracy, but suffer from privacy concerns due to the sensitive nature of transportation data. Moreover, the emerging literature on traffic prediction by distributed learning approaches, including federated learning, primarily focuses on offline learning. This paper proposes BFRT, a blockchained federated learning architecture for online traffic flow prediction using real-time data and edge computing. The proposed approach provides privacy for the underlying data, while enabling decentralized model training in real-time at the Internet of Vehicles edge. We federate GRU and LSTM models and conduct extensive experiments with dynamically collected arterial traffic data shards. We prototype the proposed permissioned blockchain network on Hyperledger Fabric and perform extensive tests using virtual machines to simulate the edge nodes. Experimental results outperform the centralized models, highlighting the feasibility of our approach for facilitating privacy-preserving and decentralized real-time traffic flow prediction.
Conventional blockchains use consensus algorithms that totally order updates across all accounts, which is stronger than necessary to implement a replicated ledger. This makes updates slower and more expensive than necessary. More recent consensus-free replicated ledgers forego consensus algorithms, with significant increase in performance and decrease in infrastructure costs. However, current designs are based around reliable broadcast of update operations to all replicas which require reliable message delivery and reasoning over operation histories to establish convergence and safety. In this paper, we present a replicated ledger as a state-based conflict-free replicated data type (CRDT) based on grow-only counters. This design provides two major benefits: 1) it requires a weaker eventual transitive delivery of the latest state rather than reliable broadcast of all update operations to all replicas; 2) eventual convergence and safety properties can be proven easily without having to reason over operation histories: convergence comes from the composition of grow-only counters, themselves CRDTs, and safety properties can be expressed over the state of counters, locally and globally. In addition, applications that tolerate temporary negative balances require no additional mechanisms and applications that require strictly non-negative balances can be supported by enforcing sequential updates to the same account across replicas. Our design is sufficient when executing on replicas that might crash and recover, as common in deployments in which all replicas are managed by trusted entities. It may also provide a good foundation to explore new mechanisms for tolerating adversarial replicas.
Consensus algorithms play a critical role in blockchains and directly impact their performance. During consensus processing, nodes need to validate and order the pending transactions into a new block, which requires verifying the application-specific data encapsulated within a transaction. This exposes the underlying data to the consensus nodes, presenting privacy concerns. Existing consensus algorithms focus on realizing application security and performance goals, but lack privacy-by-design properties or are resource-heavy and intended for securing permissionless blockchain networks. In this paper, we propose P-CFT, a zero-knowledge and crash fault tolerant consensus algorithm for permissioned blockchains. The proposed consensus algorithm provides inherent data privacy directly to the consensus layer, while still providing guarantees of crash fault tolerance. We conduct experiments using the Hyperledger Ursa cryptographic library, and the results show promise for integrating P-CFT into existing permissioned blockchain systems requiring privacy-preserving and crash fault tolerant features.
Ivan Homoliak, Martin PereÅ¡Ãni, Patrik Holop, Jakub HandzuÅ¡ · 5 authors
The adoption of decentralized, tamper-proof ledger systems is paving the way for new applications and opportunities in different contexts. While most research aims to improve their scalability, privacy, and governance issues, interoperability has received less attention. Executing transactions across various blockchains is notably instrumental in unlocking the potential of novel applications, particularly in the financial sector, where their potential would otherwise be significantly diminished. Therefore, interoperable ledgers are crucial to ensure the expansion and further adoption of such a technology in various contexts. In this paper, we present a protocol that uses a combination of trusted execution environment (TEE) and blockchains to enable interoperability over independent semi-centralized CBDC ledgers, guaranteeing the atomicity of inter-bank transfers. Our interoperability protocol uses a custom adaptation of atomic swap protocol and is executed by any pair of CBDC instances to realize a one-way transfer. It ensures features such as atomicity, verifiability, correctness, censorship resistance, and privacy while offering high scalability in terms of the number of CBDC instances. Our approach enables to possible deployment scenarios that can be combined: (1) CBDC instances represent central banks of multiple countries, and (2) CBDC instances represent the set of retail banks and a paramount central bank of a single country. We provide a detailed description of our protocol as well as an extensive analysis of its benefits, features, and security. In this WIP paper, we made a proof-of-concept implementation and made a partial evaluation, while the more extensive evaluation will be made in our future work.
Christian Berger, LÃvio Rodrigues, Hans P. Reiser, Vinicius Cogo · 5 authors
Blockchain technology sparked renewed interest in planetary-scale Byzantine fault-tolerant (BFT) state machine replication (SMR). While recent works predominantly focused on improving the scalability and throughput of these protocols, few of them addressed latency. We present Mercury, a novel transformation to autonomously optimize the latency of quorum-based BFT consensus. Mercury employs a dual resilience threshold that enables faster transaction ordering when the system contains few faulty replicas. Mercury allows forming compact quorums that substantially accelerate consensus using a smaller resilience threshold. Nevertheless, Mercury upholds standard SMR safety and liveness guarantees with optimal resilience, thanks to its judicious use of a dual operation mode and BFT forensics techniques. Our experiments spread tens of replicas across continents and reveal that Mercury can order transactions with finality in less than 0.4 seconds, half the time of a PBFT-like protocol (optimal in terms of number of communication steps and resilience) in the same network. Furthermore, Mercury matches the latency of running its base protocol on theoretically optimal internet links (transmitting at 67% of the speed of light).
This article will take you on a journey to the core of blockchains, their Byzantine consensus engine, where HotStuff emerged as a new algorithmic foundation for the classical Byzantine generals consensus problem. The first part of the article underscores the theoretical advances HotStuff enabled, including several models in which HotStuff-based solutions closed problems which were opened for decades. The second part focuses on HotStuff performance in real life setting, where its simplicity drove adoption of HotStuff as the golden standard for blockchain design, and many variants and improvements built on top of it. Both parts of this document are meant to describe lessons drawn from HotStuff as well as dispel certain myths.
Jiseong Noh, Donghwan Kwon, S.M. Cho, Neo C. K. Yiu
The comparative analysis examined eleven Proof-of-Stake (PoS) consensus-based blockchain networks to assess their openness based on five indicative metrics. These metrics include those of decentralization-related aspects, such as the number of validators and capital concentration, and participation-related aspects, including entry capital requirements and economic network stability. This is to assess and characterize the openness of Proof-of-Stake blockchain networks. The analysis suggested that networks with higher openness included Solana and Avalanche, while BNB Chain, Klaytn, and Polygon measured with lower levels of openness. According to the comparative analysis, Ethereum scored high on network openness in terms of the number of participants and the cost of running the chain, but scored relatively low on capital concentration and staking ratio, which is likely due to the low ratio of staked ether (ETH) to circulating supply and the significant stakes in staking pools like Lido. Permissioned blockchains such as Klaytn and Polygon have limited openness, which suggests the need to take the level of openness into account when transitioning into a permissionless blockchain architecture with a more decentralized setting.
Relay Mining presents a scalable solution employing probabilistic mechanisms, crypto-economic incentives, and new cryptographic primitives to estimate and prove the volume of Remote Procedure Calls (RPCs) made from a client to a server. Distributed ledgers are designed to secure permissionless state transitions (writes), highlighting a gap for incentivizing full non-validating nodes to service non-transactional (read) RPCs. This leads applications to have a dependency on altruistic or centralized off-chain Node RPC Providers. We present a solution that enables multiple RPC providers to service requests from independent applications on a permissionless network. We leverage digital signatures, commit-and-reveal schemes, and Sparse Merkle Sum Tries (SMSTs) to prove the amount of work done. This is enabled through the introduction of a novel ClosestMerkleProof proof-of-inclusion scheme. A native cryptocurrency on a distributed ledger is used to rate limit applications and disincentivize over-usage. Building upon established research in token bucket algorithms and distributed rate-limiting penalty models, our approach harnesses a feedback loop control mechanism to adjust the difficulty of mining relay rewards, dynamically scaling with network usage growth. By leveraging crypto-economic incentives, we reduce coordination overhead costs and introduce a mechanism for providing RPC services that are both geopolitically and geographically distributed. We use common formulations from rate limiting research to demonstrate how this solution in the Web3 ecosystem translates to distributed verifiable multi-tenant rate limiting in Web2.
Marco Marcozzi, Orhan Gemikonakli, Eser Gemikonakli, Enver Ever · 5 authors
Byzantine fault-tolerant (BFT) systems are able to maintain the availability and integrity of IoT systems, in presence of failure of individual components, random data corruption or malicious attacks. Fault-tolerant systems in general are essential in assuring continuity of service for mission critical applications. However, their implementation may be challenging and expensive. In this study, IoT Systems with Byzantine Fault-Tolerance are considered. Analytical models and solutions are presented as well as a detailed analysis for the evaluation of the availability. Byzantine Fault Tolerance is particularly important for blockchain mechanisms, and in turn for IoT, since it can provide a secure, reliable and decentralized infrastructure for IoT devices to communicate and transact with each other. The proposed model is based on continuous-time Markov chains, and it analyses the availability of Byzantine Fault-Tolerant systems. While the availability model is based on a continuous-time Markov chain where the breakdown and repair times follow exponential distributions, the number of the Byzantine nodes in the network studied follows various distributions. The numerical results presented report availability as a function of the number of participants and the relative number of honest actors in the system. It can be concluded from the model that there is a non-linear relationship between the number of servers and network availability; i.e. the availability is inversely proportional to the number of nodes in the system. This relationship is further strengthened as the ratio of break-down rate over repair rate increases.
What are the optimal times for an Internet of Things (IoT) device to act as a blockchain miner? The aim is to minimize the energy consumed by low-power IoT devices that log their data into a secure (tamper-proof) distributed ledger. We formulate a multiple stopping time Bayesian sequential detection problem to address energy-efficient blockchain mining for IoT devices. The objective is to identify $L$ optimal stops for mining, thereby maximizing the probability of successfully adding a block to the blockchain; we also present a model to optimize the number of stops (mining instants). The formulation is equivalent to a multiple stopping time POMDP. Since POMDPs are in general computationally intractable to solve, we show mathematically using submodularity arguments that the optimal mining policy has a useful structure: 1) it is monotone in belief space, and 2) it exhibits a threshold structure, which divides the belief space into two connected sets. Exploiting the structural results, we formulate a computationally-efficient linear mining policy for the blockchain-enabled IoT device. We present a policy gradient technique to optimize the parameters of the linear mining policy. Finally, we use synthetic and real Bitcoin datasets to study the performance of our proposed mining policy. We demonstrate the energy efficiency achieved by the optimal linear mining policy in contrast to other heuristic strategies.
Andrei Constantinescu, Diana Ghinea, Lioba Heimbach, Zilin Wang · 5 authors
Traditional blockchain design gives miners or validators full control over transaction ordering, i.e., they can freely choose which transactions to include or exclude, as well as in which order. While not an issue initially, the emergence of decentralized finance has introduced new transaction order dependencies allowing parties in control of the ordering to make a profit by front-running others' transactions. In this work, we present the Decentralized Clock Network, a new approach for achieving fair transaction ordering. Users submit their transactions to the network's clocks, which run an agreement protocol that provides each transaction with a timestamp of receipt which is then used to define the transactions' order. By separating agreement from ordering, our protocol is efficient and has a simpler design compared to other available solutions. Moreover, our protocol brings to the blockchain world the paradigm of asynchronous fallback, where the algorithm operates with stronger fairness guarantees during periods of synchronous use, switching to an asynchronous mode only during times of increased network delay.
As artificial intelligence (AI) continues to permeate various domains, concerns surrounding trust and transparency in AI-driven inference and training processes have emerged, particularly with respect to potential biases and traceability challenges. Decentralized solutions such as blockchain have been proposed to tackle these issues, but they often struggle when dealing with large-scale models, leading to time-consuming inference and inefficient training verification. To overcome these limitations, we introduce BRAIN, a Blockchain-based Reliable AI Network, a novel platform specifically designed to ensure reliable inference and training of large models. BRAIN harnesses a unique two-phase transaction mechanism, allowing real-time processing via pipelining by separating request and response transactions. Each randomly-selected inference committee commits and reveals the inference results, and upon reaching an agreement through a smart contract, then the requested operation is executed using the consensus result. Additionally, BRAIN carries out training by employing a randomly-selected training committee. They submit commit and reveal transactions along with their respective scores, enabling local model aggregation based on the median value of the scores. Experimental results demonstrate that BRAIN delivers considerably higher inference throughput at reasonable gas fees. In particular, BRAIN's tasks-per-second performance is 454.4293 times greater than that of a naive single-phase implementation.
Oracle networks feeding off-chain information to a blockchain are required to solve a distributed agreement problem since these networks receive information from multiple sources and at different times. We make a key observation that in most cases, the value obtained by oracle network nodes from multiple information sources are in close proximity. We define a notion of agreement distance and leverage the availability of a state machine replication (SMR) service to solve this distributed agreement problem with an honest simple majority of nodes instead of the conventional requirement of an honest super majority of nodes. Values from multiple nodes being in close proximity, therefore, forming a coherent cluster, is one of the keys to its efficiency. Our asynchronous protocol also embeds a fallback mechanism if the coherent cluster formation fails. Through simulations using real-world exchange data from seven prominent exchanges, we show that even for very small agreement distance values, the protocol would be able to form coherent clusters and therefore, can safely tolerate up to $1/2$ fraction of Byzantine nodes. We also show that, for a small statistical error, it is possible to choose the size of the oracle network to be significantly smaller than the entire system tolerating up to a $1/3$ fraction of Byzantine failures. This allows the oracle network to operate much more efficiently and horizontally scale much better.
A key constraint that limits the implementation of blockchain in Internet of Things (IoT) is its large storage requirement resulting from the fact that each blockchain node has to store the entire blockchain. This increases the burden on blockchain nodes, and increases the communication overhead for new nodes joining the network since they have to copy the entire blockchain. In order to reduce storage requirements without compromising on system security and integrity, coded blockchains, based on error correcting codes with fixed rates and lengths, have been recently proposed. This approach, however, does not fit well with dynamic IoT networks in which nodes actively leave and join. In such dynamic blockchains, the existing coded blockchain approaches lead to high communication overheads for new joining nodes and may have high decoding failure probability. This paper proposes a rateless coded blockchain with coding parameters adjusted to network conditions. Our goals are to minimize both the storage requirement at each blockchain node and the communication overhead for each new joining node, subject to a target decoding failure probability. We evaluate the proposed scheme in the context of real-world Bitcoin blockchain and show that both storage and communication overhead are reduced by 99.6\% with a maximum $10^{-12}$ decoding failure probability.
Jakob Svennevik Notland, Mariusz Nowostawski, Jingyue Li
Blockchain systems run consensus rules as code to agree on the state of the distributed ledger and secure the network. Changing these rules can be risky and challenging. In addition, it can often be controversial and take much effort to make all the necessary participants agree to adopt a change. Arguably, Bitcoin has seen centralisation tendencies in pools and in development. However, how these tendencies influence blockchain governance has received minimal community and academic attention. Our study analyses the governmental structures in a blockchain by looking into the history of Bitcoin. We investigate the process of changing consensus rules through a grounded theory analysis comprising quantitative and qualitative data from 34 consensus forks in Bitcoin and Bitcoin Cash. The results reveal the decentralised behaviour in Bitcoin and blockchain. Our results are in contrast to related work, emphasising centralisation among miners and developers. Furthermore, our results show how the consensus-driven deployment techniques and governance of consensus rules are intertwined.
While the original purpose of blockchains was to realize a payment system, it has been shown that, in fact, such systems do not require consensus and can be implemented deterministically in asynchronous networks. State-of-the-art payment systems employ Reliable Broadcast to disseminate payments and prevent double spending, which entails O(n^2) communication complexity per payment even if Byzantine behavior is scarce or non-existent. Here we present Flash, the first payment system to achieve $O(n)$ communication complexity per payment in the good case and $O(n^2)$ complexity in the worst-case, matching the lower bound. This is made possible by sidestepping Reliable Broadcast and instead using the blocklace -- a DAG-like partially-ordered generalization of the blockchain -- for the tasks of recording transaction dependencies, block dissemination, and equivocation exclusion, which in turn prevents doublespending. Flash has two variants: for high congestion when multiple blocks that contain multiple payments are issued concurrently; and for low congestion when payments are infrequent.
The problem of Byzantine consensus has been key to designing secure distributed systems. However, it is particularly difficult, mainly due to the presence of Byzantine processes that act arbitrarily and the unknown message delays in general networks. Although it is well known that both safety and liveness are at risk as soon as n/3 Byzantine processes fail, very few works attempted to characterize precisely the faults that produce safety violations from the faults that produce termination violations. In this paper, we present a new lower bound on the solvability of the consensus problem by distinguishing deceitful faults violating safety and benign faults violating termination from the more general Byzantine faults, in what we call the Byzantine-deceitful-benign fault model. We show that one cannot solve consensus if $n \leq 3t + d + 2q$ with t, d, and q are Byzantine, deceitful, and benign processes. We show that this bound is tight by presenting the Basilic class of consensus protocols that solve consensus when $n > 3t + d + 2q$. These protocols differ in the number of processes from which they wait to receive messages before progressing. Then, we build upon the Basilic class in order to present Zero-Loss Blockchain (ZLB), the first blockchain that tolerates an adversary controlling more than half of the system, with up to less than a third of them Byzantine. ZLB is an open blockchain that combines recent theoretical advances in accountable Byzantine agreement to exclude undeniably faulty processes. Interestingly, ZLB does not need a known bound on the delay of messages but progressively reduces the portion of faulty processes below 13 , and reaches consensus. Geo-distributed experiments show that ZLB outperforms HotStuff and is almost as fast as the scalable Red Belly Blockchain that cannot tolerate n/3 faults.
Darcy Camargo, Andreas Penzkofer, Sebastian Müller, William H. Sanders
The robust construction of the ledger data structure is an essential ingredient for the safe operation of a distributed ledger. While in traditional linear blockchain systems, permission to append to the structure is leader-based, in Directed Acyclic Graph-based ledgers, the writing access can be organised leaderless. However, this leaderless approach relies on fair treatment of non-referenced blocks, i.e. tips, by honest block issuers. We study the impact of a deviation from the standard tip selection by a subset of block issuers with the aim of halting the confirmation of honest blocks entirely. W e provide models on this so-called orphanage of blocks and validate these through open-sourced simulation studies. A critical threshold for the adversary issuance rate is shown to exist, above which the tip pool becomes unstable, while for values below the orphanage decrease exponentially. We study the robustness of the protocol with an expiration time on tips, also called garbage collection, and modification of the parent references per block.
Konstantin D. Pandl, Chun-Yin Huang, Ivan Beschastnikh, Xiaoxiao Li · 6 authors
Existing research on data valuation in federated and swarm learning focuses on valuing client contributions and works best when data across clients is independent and identically distributed (IID). In practice, data is rarely distributed IID. We develop an approach called DDVal for decentralized data valuation, capable of valuing individual data points in federated and swarm learning. DDVal is based on sharing deep features and approximating Shapley values through a k-nearest neighbor approximation method. This allows for novel applications, for example, to simultaneously reward institutions and individuals for providing data to a decentralized machine learning task. The valuation of data points through DDVal allows to also draw hierarchical conclusions on the contribution of institutions, and we empirically show that the accuracy of DDVal in estimating institutional contributions is higher than existing Shapley value approximation methods for federated learning. Specifically, it reaches a cosine similarity in approximating Shapley values of 99.969 % in both, IID and non-IID data distributions across institutions, compared with 99.301 % and 97.250 % for the best state of the art methods. DDVal scales with the number of data points instead of the number of clients, and has a loglinear complexity. This scales more favorably than existing approaches with an exponential complexity. We show that DDVal is especially efficient in data distribution scenarios with many clients that have few data points - for example, more than 16 clients with 8,000 data points each. By integrating DDVal into a decentralized system, we show that it is not only suitable for centralized federated learning, but also decentralized swarm learning, which aligns well with the research on emerging internet technologies such as web3 to reward users for providing data to algorithms.
Bing-Yang Lin, Daria Dziubałtowska, Piotr Macek, Andreas Penzkofer · 5 authors
DAG-based DLTs allow for parallel, asynchronous writing access to a ledger. Consequently, the perception of the most recent blocks may differ considerably between nodes, and the underlying network properties of the P2P layer have a direct impact on the performance of the protocol. Moreover, the stronger inter-dependencies of several core components demand a more complex and complete approach to studying such DLTs. This paper presents an agent-based, open-sourced simulator for large-scale networks that implement the leaderless Tangle 2.0 consensus protocol. Its scope includes modelling the underlying peer-to-peer communication with network topology, package loss, heterogeneous latency, the gossip protocol with reliable broadcast qualities, the underlying DAG-based data structure, and the consensus protocol. The simulator allows us to explore the performance of the protocol in different network environments, as well as different attack scenarios.
Anwar Sadad, Muazzam A. Khan, Baraq Ghaleb, Fadia Ali Khan · 7 authors
Blockchain (BC) and Information for Operational and Tactical Analysis (IOTA) are distributed ledgers that record a huge number of transactions in multiple places at the same time using decentralized databases. Both BC and IOTA facilitate Internet-of-Things (IoT) by overcoming the issues related to traditional centralized systems, such as privacy, security, resources cost, performance, and transparency. Still, IoT faces the potential challenges of real-time processing, resource management, and storage services. Edge computing (EC) has been introduced to tackle the underlying challenges of IoT by providing real-time processing, resource management, and storage services nearer to IoT devices on the network's edge. To make EC more efficient and effective, solutions using BC and IOTA have been devoted to this area. However, BC and IOTA came with their pitfalls. This survey outlines the pitfalls of BC and IOTA in EC and provides research directions to be investigated further.
This research article presents various design patterns for improving interoperability in Polkadot, a blockchain platform. These patterns include chain bridges, interoperability standards, common asset identifiers, governance agreements, oracle chains, and a hypothetical design pattern called Zero Trust Chain. Implementation of these design patterns can help improve security and confidence in transactions between different chains on the Polkadot network, allowing for faster and more efficient communication. The article also emphasizes the importance of interoperability in blockchain technology and highlights Polkadot's flexibility in creating customized specialized chains that can further improve interoperability on the network. Overall, this article highlights how design patterns can improve interoperability in Polkadot, which could lead to greater adoption of blockchain technology in various industries.
Blockchain protocols typically aspire to run in the permissionless setting, in which nodes are owned and operated by a large number of diverse and unknown entities, with each node free to start or stop running the protocol at any time. This setting is more challenging than the traditional permissioned setting, in which the set of nodes that will be running the protocol is fixed and known at the time of protocol deployment. The goal of this paper is to provide a framework for reasoning about the rich design space of blockchain protocols and their capabilities and limitations in the permissionless setting. We propose a hierarchy of settings with different "degrees of permissionlessness", specified by the amount of knowledge that a protocol has about the current participants: These are the fully permissionless, dynamically available and quasi-permissionless settings. The paper also proves several results illustrating the utility of our analysis framework for reasoning about blockchain protocols in these settings. For example: (1) In the fully permissionless setting, even with synchronous communication and with severe restrictions on the total size of the Byzantine players, every deterministic protocol for Byzantine agreement has a non-terminating execution. (2) In the dynamically available and partially synchronous setting, no protocol can solve the Byzantine agreement problem with high probability, even if there are no Byzantine players at all. (3) In the quasi-permissionless and partially synchronous setting, by contrast, assuming a bound on the total size of the Byzantine players, there is a deterministic protocol solving state machine replication. (4) In the quasi-permissionless and synchronous setting, every proof-of-stake state machine replication protocol that uses only time-malleable cryptographic primitives is vulnerable to long-range attacks.