Transactions involving multiple blockchains are implemented by cross-chain protocols. These protocols are based on smart contracts, programs that run on blockchains, executed by a network of computers. Because smart contracts can automatically transfer ownership of cryptocurrencies, electronic securities, and other valuable assets among untrusting parties, verifying the runtime correctness of smart contracts is a problem of compelling practical interest. Such verification is challenging since smart contract execution is time-sensitive, and the clocks on different blockchains may not be perfectly synchronized. This paper describes a method for runtime monitoring of blockchain executions. First, we propose a generalized runtime verification technique for verifying partially synchronous distributed computations for the metric temporal logic (MTL) by exploiting bounded-skew clock synchronization. Second, we introduce a progression-based formula rewriting scheme for monitoring \MTL specifications which employ SMT solving techniques and report experimental results.
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$ Byzantine processes, $d$ deceitful processes, and $q$ benign processes. In addition, 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. Each of these protocols is thus better suited for some applications depending on the predominance of benign or deceitful faults. Finally, we study the fault tolerance of the Basilic class of consensus protocols in the context of blockchains that need to solve the weaker problem of eventual consensus. We demonstrate that Basilic solves this problem with only $n > 2t+d+q$, hence demonstrating how it can strengthen blockchain security.
Despite numerous prior attempts to boost transaction per second (TPS) of blockchain systems, many sacrifice decentralization and security. This paper proposes a bodyless block propagation (BBP) scheme for which the blockbody is not validated and transmitted during block propagation, to increase TPS without compromising security. Nodes in the blockchain network anticipate the transactions and their ordering in the next upcoming block so that these transactions can be pre-executed and pre-validated before the block is born. For a network with $N$ nodes, our theoretical analysis reveals that BBP can improve TPS scalability from $O(1/log(N))$ to $O(1)$. Ensuring consensus on the next block's transaction content is crucial. We propose a transaction selection, ordering, and synchronization algorithm to drive this consensus. To address the undetermined Coinbase address issue, we further present an algorithm for such unresolvable transactions, ensuring a consistent and TPS-efficient scheme. With BBP, most transactions require neither validation nor transmission during block propagation, liberating system from transaction-block dependencies and rendering TPS scalable. Both theoretical analysis and experiments underscore BBP's potential for full TPS scalability. Experimental results reveal a 4x reduction in block propagation time compared to Ethereum blockchain, with TPS performance being limited by node hardware rather than block propagation.
Blockchain has widely been adopted to design accountable federated learning frameworks; however, the existing frameworks do not scale for distributed model training over multiple independent blockchain networks. For storing the pre-trained models over blockchain, current approaches primarily embed a model using its structural properties that are neither scalable for cross-chain exchange nor suitable for cross-chain verification. This paper proposes an architectural framework for cross-chain verifiable model training using federated learning, called Proof of Federated Training (PoFT), the first of its kind that enables a federated training procedure span across the clients over multiple blockchain networks. Instead of structural embedding, PoFT uses model parameters to embed the model over a blockchain and then applies a verifiable model exchange between two blockchain networks for cross-network model training. We implement and test PoFT over a large-scale setup using Amazon EC2 instances and observe that cross-chain training can significantly boosts up the model efficacy. In contrast, PoFT incurs marginal overhead for inter-chain model exchanges.
Kyle P. Michelson, Anjali Sridharan, Umut Can Çabuk, Ethan Reesor · 9 authors
The Accumulate Protocol ("Accumulate") is an identity-based, Delegated Proof of Stake (DPoS) blockchain designed to power the digital economy through interoperability with Layer-1 blockchains, integration with enterprise tech stacks, and interfacing with the World Wide Web. Accumulate bypasses the trilemma of security, scalability, and decentralization by implementing a chain-of-chains architecture in which digital identities with the ability to manage keys, tokens, data, and other identities are treated as their own independent blockchains. This architecture allows these identities, known as Accumulate Digital Identifiers (ADIs), to be processed and validated in parallel over the Accumulate network. Each ADI also possesses a hierarchical set of keys with different priority levels that allow users to manage their security over time and create complex signature authorization schemes that expand the utility of multi-signature transactions. A two token system provides predictable costs for enterprise users, while anchoring all transactions to Layer-1 blockchains provides enterprise-grade security to everyone.
Yan Huang, Yu Zhou, Tao Zhu, Yuzhuang Xu · 8 authors
This paper presents Balloon, a scalable blockchain consensus protocol which could dynamically adapt its performance to the overall computation power change. Balloon is based on a parallel chain architecture combined with a greedy heaviest sub-chain selection strategy. It adopts an inovative block sampling approach to assess the change of block generation rate in the network. By introducing view change mechanism, Balllon is able to dynamically adjust the number of parallel sub-chains. Balloon redefines the concept of block subtree weight with view change in consideration, so that a total order of blocks could be obtained safely. To deal with rapidly increasing block generation rate in the blockchain network, participants of previous Nakamoto-style protocols are required to continuously increase their mining difficulty so as to maintain an expected security gurantee. Balloon, however, could accomadate a fixed difficulty setup and assign superfluous block processing capability to new sub-chains, which makes it more open and also economical.
Jelle Hellings, Suyash Gupta, Sajjad Rahnama, Mohammad Sadoghi
The introduction of Bitcoin fueled the development of blockchain-based resilient data management systems that are resilient against failures, enable federated data management, and can support data provenance. The key factor determining the performance of such resilient data management systems is the consensus protocol used by the system to replicate client transactions among all participants. Unfortunately, existing high-throughput consensus protocols are costly and impose significant latencies on transaction processing, which rules out their usage in responsive high-performance data management systems. In this work, we improve on this situation by introducing the Proof-of-Execution consensus protocol (PoE), a consensus protocol designed for high-performance low-latency resilient data management. PoE introduces speculative execution, which minimizes latencies by starting execution before consensus is reached, and PoE introduces proof-of-executions to guarantee successful execution to clients. Furthermore, PoE introduces a single-round check-commit protocol to reduce the overall communication costs of consensus. Hence, we believe that PoE is a promising step towards flexible general-purpose low-latency resilient data management systems.
Huong Nguyen, Tri Nguyen, Teemu Leppänen, Juha Partala · 5 authors
Efficient Vehicle-to-Everything enabling cooperation and enhanced decision-making for autonomous vehicles is essential for optimized and safe traffic. Real-time decision-making based on vehicle sensor data, other traffic data, and environmental and contextual data becomes imperative. As a part of such Intelligent Traffic Systems, cooperation between different stakeholders needs to be facilitated rapidly, reliably, and securely. The Internet of Things provides the fabric to connect these stakeholders who share their data, refined information, and provided services with each other. However, these cloud-based systems struggle to meet the real-time requirements for smart traffic due to long distances across networks. Here, edge computing systems bring the data and services into the close proximity of fast-moving vehicles, reducing information delivery latencies and improving privacy as sensitive data is processed locally. To solve the issues of trust and latency in data sharing between these stakeholders, we propose a decentralized framework that enables smart contracts between traffic data producers and consumers based on blockchain. Autonomous vehicles connect to a local edge server, share their data, or use services based on agreements, for which the cooperating edge servers across the system provide a platform. We set up proof-of-concept experiments with Hyperledger Fabric and virtual cars to analyze the system throughput with secure unicast and multicast data transmissions. Our results show that multicast transmissions in such a scenario boost the throughput up to 2.5 times where the data packets of different sizes can be transmitted in less than one second.
Byzantine fault-tolerant (BFT) consensus algorithms are at the core of providing safety and liveness guarantees for distributed systems that must operate in the presence of arbitrary failures. Recently, numerous new BFT algorithms have been proposed, not least due to the traction blockchain technologies have garnered in the search for consensus solutions that offer high throughput, low latency, and robust system designs. In this paper, we conduct a systematic survey of selected and distinguished BFT algorithms that have received extensive attention in academia and industry alike. We perform a qualitative comparison among all algorithms we review considering message and time complexities. Furthermore, we decompose each consensus algorithm into its constituent subprotocols for replication and view change backed by intuitive figures to illustrate the message-passing pattern. We also elaborate on the strengths and weaknesses of each algorithm as compared to the state-of-the-art approaches.
Paolo Bottoni, Claudio Di Ciccio, Remo Pareschi, Nicola Gessa · 5 authors
Smart contracts show a high potential for ensuring that Supply Chain Management strategies make a qualitative leap toward higher levels of optimality, not only in terms of efficiency and profitability but also in the aggregation of skills aimed at creating the best products and services to bring to the market. In this article, we illustrate an architecture that employs smart contracts to implement various algorithmic versions of the Income Sharing principle between companies participating in a supply chain. We implement our approach on Hyperledger Fabric, the most widespread platform for private and consortium distributed ledgers, and discuss its suitability to our purposes by comparing this design choice with the alternative given by public blockchains, with particular attention to Ethereum.
Evan Madill, Ben Nguyen, Carson K. Leung, Sara Rouhani
Blockchain-based federated learning has gained significant interest over the last few years with the increasing concern for data privacy, advances in machine learning, and blockchain innovation. However, gaps in security and scalability hinder the development of real-world applications. In this study, we propose ScaleSFL, which is a scalable blockchain-based sharding solution for federated learning. ScaleSFL supports interoperability by separating the off-chain federated learning component in order to verify model updates instead of controlling the entire federated learning flow. We implemented ScaleSFL as a proof-of-concept prototype system using Hyperledger Fabric to demonstrate the feasibility of the solution. We present a performance evaluation of results collected through Hyperledger Caliper benchmarking tools conducted on model creation. Our evaluation results show that sharding can improve validation performance linearly while remaining efficient and secure.
Although blockchain, the supporting technology of various cryptocurrencies, has offered a potentially effective framework for numerous decentralized trust management systems, its performance is still sub-optimal in real-world networks. With limited bandwidth, the communication complexity for nodes to process a block scales with the growing network size and hence becomes the limiting factor of blockchain's performance. In this paper, we suggest a re-design of existing blockchain systems, which addresses the issue of the communication burden. First, by employing techniques from Coded Computation, our scheme guarantees correct verification of transactions while reducing the bit complexity dramatically such that it grows logarithmically with the number of nodes. Second, with the adoption of techniques from Information Dispersal and State Machine Replication, the system is resilient to Byzantine faults and achieves linear message complexity. Third, we propose a novel 2-dimensional sharding strategy, which inherently supports cross-shard transactions, alleviating the need for complicated communication protocols between shards, while keeping the computation and storage benefits of sharding.
Remote voting has become more critical in recent years, especially since the COVID-19 outbreak. Blockchain technology and its benefits such as decentralization, security, and transparency have given rise to proposals for blockchain-based voting systems. However, the traceability of blockchain transactions violates voter anonymity in existing proposals. Besides, transaction costs also need to be considered. Solutions that may cause repeated elections should be avoided for a low-cost scalable voting system. In this work, we propose ElectAnon, a blockchain-based, self-tallying, and ranked-choice voting protocol focusing on anonymity, robustness, and scalability. ElectAnon achieves anonymity by enabling voters to register with identity commitments and cast their votes via zero-knowledge proofs. Robustness is realized by removing the direct control of the authorities in the voting process by using timed-state machines. Each voter encodes the ballot into a single integer and blinds the vote off-chain while making the verification on-chain. This makes the protocol infinitely scalable in the number of voters. ElectAnon is also a solution for governance in Decentralized Autonomous Organizations (DAO): It includes a candidate proposal module and an algorithm-agnostic mechanism to plug-in different tallying methods easily. The Merkle forest extension is proposed for conducting even more trustless elections. ElectAnon is implemented with smart contracts based on Ethereum Virtual Machine (EVM) and a zero-knowledge gadget, Semaphore. The implementation also includes two different sophisticated tallying methods, Borda Count and Tideman. Experimental results show that a 40-voter and 10-candidate election can be implemented with the gas consumption reduced up to 89% compared to previous works. While other studies could not exceed a 25,000-voter setup, ElectAnon has been observed to run safely for 1,000,000 voters. The implementation can be found at https://github.com/ceyonur/electanon .
The sharing economy is centralizing services, leading to misuses of the Internet. We can list growing damages of data hacks, global outages and even the use of data to manipulate their owners. Unfortunately, there is no decentralized web where users can interact peer-to-peer in a secure way. Blockchains incentivize participants to individually validate every transaction and impose their block to the network. As a result, the validation of smart contract requests is computationally intensive while the agreement on a unique state does not make full use of the network. In this paper, we propose Collachain, a new byzantine fault tolerant blockchain compatible with the largest ecosystem of DApps that leverages collaboration. First, the pariticipants executing smart contracts collaborate to validate the transactions, hence halving the number of validations required by modern blockchains (e.g., Ethereum, Libra). Second, the participants in the consensus collaborate to combine their block proposal into a superblock, hence improving throughput as the system grows to hundreds of nodes. In addition, Collachain offers the possibility to its users to interact securely with each other without downloading the blockchain, hence allowing interactions via mobile devices. Collachain is effective at outperforming the Concord and Quorum blockchains and its throughput peaks at 4500 TPS under a Twitter DApp (Decentralized Application) workload. Finally, we demonstrate Collachain's scalability by deploying it on 200 nodes located in 10 countries over 5 continents.
User transactions on Ethereum's peer-to-peer network are at risk of being attacked. The smart contracts building decentralized finance (DeFi) have introduced a new transaction ordering dependency to the Ethereum blockchain. As a result, attackers can profit from front- and back-running transactions. Multiple approaches to mitigate transaction reordering manipulations have surfaced recently. However, the success of individual approaches in mitigating such attacks and their impact on the entire blockchain remains largely unstudied. In this systematization of knowledge (SoK), we categorize and analyze state-of-the-art transaction reordering manipulation mitigation schemes. Instead of restricting our analysis to a scheme's success at preventing transaction reordering attacks, we evaluate its full impact on the blockchain. Therefore, we are able to provide a complete picture of the strengths and weaknesses of current mitigation schemes. We find that currently no scheme fully meets all the demands of the blockchain ecosystem. In fact, all approaches demonstrate unsatisfactory performance in at least one area relevant to the blockchain ecosystem.
Andrew Cullen, Lianna Zhao, Luigi Vigneri, Robert Shorten
An outstanding problem in the design of distributed ledgers concerns policies that govern the manner in which users interact with the network. Network usability is crucial to the mainstream adoption of distributed ledgers, particularly for enterprise applications in which most users do not wish to operate full node. For DAG-based ledgers such as IOTA, we propose a user-node interaction mechanism that is designed to ensure the risk of a user experiencing a poor quality of service is low. Our mechanism involves users selecting nodes to issue their transactions to the ledger based on quality of service indicators advertised by the nodes. Simulation results are presented to illustrate the efficacy of the proposed policies.
Growing excitement around permissionless blockchains is uncovering its latent scalability concerns. Permissioned blockchains offer high transactional throughput and low latencies while compromising decentralization. In the quest for a decentralized, scalable blockchain fabric, i.e., to offer the scalability of permissioned blockchain in a permissionless setting, we present L4L to encourage decentralization over the permissioned Libra network without compromising its sustainability. L4L employs delay towers, -- puzzle towers that leverage verifiable delay functions -- for establishing identity in a permissionless setting. Delay towers cannot be parallelized due to their sequential execution, making them an eco-friendly alternative. We also discuss methodologies to replace validators participating in consensus to promote compliant behavior. Our evaluations found that the cost of enabling decentralization over permissioned networks is almost negligible. Furthermore, delay towers offer an alternative to existing permissionless consensus mechanisms without requiring airdrops or pre-sale of tokens.
Metaverse depicts a vista of constructing a virtual environment parallel to the real world so people can communicate with others and objects through digital entities. In the real world, communication relies on identities and addresses that are recognized by authorities, no matter the link is established via post, email, mobile phone, or landline. Metaverse, however, is different from the real world, which requires a single identity belongs to the individual. This identity can be an encrypted virtual address in the metaverse but no one can trace or verify it. In order to achieve such addresses to hide individuals in the metaverse, re-mapping the virtual address to the individual's identity and a specific spectrum to support the address-based communication for the metaverse are needed. Therefore, metaverse native or meta-native communications based on blockchain could be a promising solution to directly connect entities with their native encrypted addresses that gets rid of the existing network services based on IP, cellular, HTTP, etc. This paper proposes a vision of blockchain, encrypted address and address-based access model for all users, devices, services, etc. to contribute to the metaverse. Furthermore, the allocation architecture of a designated spectrum for the metaverse is proposed to remove the barrier to access to the metaverse/blockchain in response to the initiatives of metaverse and decentralized Internet.
Rati Gelashvili, Alexander Spiegelman, Zhuolun Xiang, George Danezis · 8 authors
Block-STM is a parallel execution engine for smart contracts, built around the principles of Software Transactional Memory. Transactions are grouped in blocks, and every execution of the block must yield the same deterministic outcome. Block-STM further enforces that the outcome is consistent with executing transactions according to a preset order, leveraging this order to dynamically detect dependencies and avoid conflicts during speculative transaction execution. At the core of Block-STM is a novel, low-overhead collaborative scheduler of execution and validation tasks. Block-STM is implemented on the main branch of the Diem Blockchain code-base and runs in production at Aptos. Our evaluation demonstrates that Block-STM is adaptive to workloads with different conflict rates and utilizes the inherent parallelism therein. Block-STM achieves up to $110k$ tps in the Diem benchmarks and up to $170k$ tps in the Aptos Benchmarks, which is a $20$x and $17$x improvement over the sequential baseline with $32$ threads, respectively. The throughput on a contended workload is up to $50k$ tps and $80k$ tps in Diem and Aptos benchmarks, respectively.
Simple closed-form upper and lower bounds are developed for the security of the Nakamoto consensus as a function of the confirmation depth, the honest and adversarial block mining rates, and an upper bound on the block propagation delay. The bounds are exponential in the confirmation depth and apply regardless of the adversary's attack strategy. The gap between the upper and lower bounds is small for Bitcoin's parameters. For example, assuming an average block interval of 10 minutes, a network delay bound of ten seconds, and 10% adversarial mining power, the widely used 6-block confirmation rule yields a safety violation between 0.11% and 0.35% probability.
Matthias Lohr, Kenneth Skiba, Marco Konersmann, Jan Jürjens · 5 authors
Existing fair exchange protocols usually neglect consideration of cost when assessing their fairness. However, in an environment with non-negligible transaction cost, e.g., public blockchains, high or unexpected transaction cost might be an obstacle for wide-spread adoption of fair exchange protocols in business applications. For example, as of 2021-12-17, the initialization of the FairSwap protocol on the Ethereum blockchain requires the selling party to pay a fee of approx. 349.20 USD per exchange. We address this issue by defining cost fairness, which can be used to assess two-party exchange protocols including implied transaction cost. We show that in an environment with non-negligible transaction cost where one party has to initialize the exchange protocol and the other party can leave the exchange at any time cost fairness cannot be achieved.
Blockchain has attracted much attention from both academia and industry since emerging in 2008. Due to the inconvenience of the deployment of large-scale blockchains, blockchain simulators are used to facilitate blockchain design and implementation. We evaluate state-of-the-art simulators applied to both Bitcoin and Ethereum and find that they suffer from low performance and scalability which are significant limitations. To build a more general and faster blockchain simulator, we extend an existing blockchain simulator, i.e. BlockSim. We add a network module integrated with a network topology generation algorithm and a block propagation algorithm to generate a realistic blockchain network and simulate the block propagation efficiently. We design a binary transaction pool structure and migrate BlockSim from Python to C++ so that bitwise operations can be used to accelerate the simulation and reduce memory usage. Moreover, we modularize the simulator based on five primary blockchain processes. Significant blockchain elements including consensus protocols (PoW and PoS), information propagation algorithms (Gossip) and finalization rules (Longest rule and GHOST rule) are implemented in individual modules and can be combined flexibly to simulate different types of blockchains. Experiments demonstrate that the new simulator reduces the simulation time by an order of magnitude and improves scalability, enabling us to simulate more than ten thousand nodes, roughly the size of the Bitcoin and Ethereum networks. Two typical use cases are proposed to investigate network-related issues which are not covered by most other simulators.
There is a resurgence of interest in Byzantine fault-tolerant (BFT) systems due to blockchains. However, leader-based BFT consensus protocols used by permissioned blockchains have limited scalability and robustness. To alleviate the leader bottleneck in BFT consensus, we introduce Stratus, a robust shared mempool protocol that decouples transaction distribution from consensus. Our idea is to have replicas disseminate transactions in a distributed manner and have the leader only propose transaction ids. Stratus uses a provably available broadcast (PAB) protocol to ensure the availability of the referenced transactions. We implemented and evaluated Stratus by integrating it with state-of-the-art BFT-based blockchain protocols and evaluated these protocols in both LAN and WAN settings. Our results show that Stratus-based protocols achieve up to $5\sim20\times$ more throughput than their native counterparts in a network with hundreds of replicas. In addition, the performance of Stratus degrades gracefully in the presence of network asynchrony, Byzantine attackers, and unbalanced workloads. Our design provides easy-to-use APIs so that other BFT systems suffering from leader bottlenecks can use Stratus.
The Philos Marketplace blockchain system is a proposed hierarchical blockchain architecture which allows a large number of individual blockchains to operate in parallel. These parallel chains achieve consensus among one another on a limited set of core operations, while allowing each on-chain application to manage its own data independently of others. This architecture addresses the scalability issues of traditional linear blockchains, but requires novel consensus mechanisms. A central feature of the Philos consensus mechanism is its trust algorithm, which assigns each network node a numerical trust value (or score) indicating the quality of recent past performance. This trust value is then used to determine a node's voting weight at the higher levels of consensus. In this paper, we formally define the Philos trust algorithm, and provide several illustrations of its operation, both theoretically and empirically. We also ask whether a misbehaving node can strategically exploit the algorithm for its personal gain, and show that this type of exploitation can be universally prevented simply by enforcing a mild limit on the number of participants in each of the parallel chains.