Blockchain oracles are systems that connect blockchains with the outside world by interfacing with external data providers. They provide decentralized applications with the external information needed for smart contract execution. In this paper, we focus on decentralized price oracles, which are distributed systems that provide exchange rates of digital assets to smart contracts. They are the cornerstone of the safety of some decentralized finance applications such as stable coins or lending protocols. They consist of a network of nodes called oracles that gather information from off-chain sources such as an exchange market's API and feed it to smart contracts. Among the desired properties of a price oracle system are low latency, availability, and low operating cost. Moreover, they should overcome constraints such as having diverse data sources which is known as the freeloading problem or Byzantine failures. In this paper, we define the distributed price oracle problem and present PoWacle, the first asynchronous decentralized oracle protocol that copes with Byzantine behavior.
Liquidity is a liveness property of programs managing resources that pinpoints those programs not freezing any resource forever. We consider a simple stateful language whose resources are assets (digital currencies, non fungible tokens, etc.). Then we define a type system that tracks in a symbolic way the input-output behaviour of functions with respect to assets. These types and their composition, which define types of computations, allow us to design two algorithms for liquidity that have different precisions and costs. We also demonstrate the correctness of the algorithms.
We propose and study a new class of polynomial voting rules for a general decentralized decision/consensus system, and more specifically for the proof-of-stake protocol. The main idea, inspired by the Penrose square-root law and the more recent quadratic voting rule, is to differentiate a voter’s voting power and the voter’s share (fraction of the total in the system). We show that, whereas voter shares form a martingale process that converges to a Dirichlet distribution, their voting powers follow a supermartingale process that decays to zero over time. This prevents any voter from controlling the voting process and, thus, enhances security. For both limiting results, we also provide explicit rates of convergence. When the initial total volume of votes (or stakes) is large, we show a phase transition in share stability (or the lack thereof), corresponding to the voter’s initial share relative to the total. We also study the scenario in which trading (of votes/stakes) among the voters is allowed and quantify the level of risk sensitivity (or risk aversion) in three categories, corresponding to the voter’s utility being a supermartingale, a submartingale, and a martingale. For each category, we identify the voter’s best strategy in terms of participation and trading. Funding: W. Tang gratefully acknowledges financial support through the National Science Foundation [Grants DMS-2113779 and DMS-2206038] and through a start-up grant at Columbia University. D. D. Yao’s work is part of a Columbia–City University/Hong Kong collaborative project that is supported by InnoHK Initiative, the Government of Hong Kong Special Administrative Region, and the Laboratory for AI-Powered Financial Technologies.
Blockchain consensus is a state whereby each node in a network agrees on the current state of the blockchain. Existing protocols achieve consensus via a contest or voting procedure to select one node as a dictator to propose new blocks. However, this procedure can still lead to potential attacks that make consensus harder to achieve or lead to coordination issues if multiple, competing chains (i.e., forks) are created with the potential that an untruthful fork might be selected. We explore the potential for mechanisms to be used to achieve consensus that are triggered when there is a dispute impeding consensus. Using the feature that nodes stake tokens in proof of stake (POS) protocols, we construct revelation mechanisms in which the unique (subgame perfect) equilibrium involves validating nodes propose truthful blocks using only the information that exists amongst all nodes. We construct operationally and computationally simple mechanisms under both Byzantine Fault Tolerance and a Longest Chain Rule, and discuss their robustness to attacks. Our perspective is that the use of simple mechanisms is an unexplored area of blockchain consensus and has the potential to mitigate known trade-offs and enhance scalability.
Decentralized applications (DApps) gained traction in the context of the blockchain technology. Ethereum is currently the public blockchain that backs the largest amount of the existing DApps. Onboarding new users to Ethereum DApps is a notoriously hard issue to solve. This is mainly caused by lack of cryptocurrency ownership, needed for transaction fees. Several meta-transaction patterns emerged for decoupling users from paying these fees. However, such solutions are mostly offered via off-chain, often paid relayer services and do not fully address the security issues present in the meta-transaction path. In this paper, we introduce a new meta-transaction architecture that makes use of the Intel Software Guard Extensions (SGX). Unlike other solutions, our approach would offer the possibility to deploy a fee-free Ethereum DApp on a web server that can directly relay meta-transactions to the Ethereum network while having essential security guarantees integrated by design.
The Practical Byzantine Fault Tolerant (PBFT) consensus algorithm has many advantages, which makes PBFT utilized widely. Nonetheless, PBFT is not suitable for large-scale node scenarios due to its high communication complexity and it also has an apparent disadvantage of inadequate fault tolerance. The typically derived PBFT algorithms focus on reducing communication complexity at the cost of diminished system security or fault tolerance. In this paper, Dual-Primary-Node derived Practical Byzantine Fault Tolerance (DPNPBFT) is proposed to achieve the best balance of the above three performances. First, DPNPBFT selects dual master nodes based on the idea of power separation. The two master nodes check balance and supervise each other to avoid excessive centralization as a single master node system. It also reduces the communication complexity of the replica node, which only communicates with the master node. Furthermore, we designed the architecture of DPNPBFT to get a practical 49% fault tolerance rate, and it is close to the current mainstream Proof of Work and Proof of Stake algorithms. Experimental results demonstrate that DPNPBFT has O(N) level communication complexity and excellent anti-host node malicious performance. The Transactions Per Second of DPNPBFT is stable at 1700. It proves DPNPBFT has the best performance balance and excellent comprehensive performance for large-scale Internet of Things application scenarios.
Sebastian Müller, Andreas Penzkofer, Nikita Polyanskii, Jonas Theis · 6 authors
We introduce the theoretical foundations of the Tangle 2.0, a probabilistic leaderless consensus protocol based on a directed acyclic graph (DAG) called the Tangle. The Tangle naturally succeeds the blockchain as its next evolutionary step as it offers features suited to establish more efficient and scalable distributed ledger solutions. Consensus is no longer found in the longest chain but on the heaviest DAG, where PoW is replaced by a stake- or reputation-based weight function. The DAG structure and the underlying Reality-based UTXO Ledger allow parallel validation of transactions without the need for total ordering. Moreover, it enables the removal of the intermediary of miners and validators, allowing a pure two-step process that follows the \emph{propose-vote} paradigm at the node level and not at the validator level. We propose a framework to analyse liveness and safety under different communication and adversary models. This allows providing impossibility results in some edge cases and in the asynchronous communication model. We provide formal proof of the security of the protocol assuming a common random coin.
Blockchains are modern distributed systems that provide decentralized financial capabilities with trustable guarantees. Smart contracts are programs written in specialized programming languages running on a blockchain and govern how tokens and cryptocurrency are sent and received. Smart contracts can invoke other contracts during the execution of transactions initiated by external users. Once deployed, smart contracts cannot be modified and their pitfalls can cause malfunctions and losses, for example by attacks from malicious users. Runtime verification is a very appealing technique to improve the reliability of smart contracts. One approach consists of specifying undesired executions (never claims) and detecting violations of the specification on the fly. This can be done by extending smart contracts with additional instructions corresponding to monitor specified properties, resulting in an onchain monitoring approach. In this paper, we study transaction monitoring that consists of detecting violations of complete transaction executions and not of individual operations within transactions. Our main contributions are to show that transaction monitoring is not possible in most blockchains and propose different execution mechanisms that would enable transaction monitoring.
M.D. Khan, Dirk Schaefer, Jelena Milisavljevic-Syed
Blockchain Technology has gained prominence since 2008 with trust, reliability, speed, and transparency becoming major advantages. It has also been applied and researched within a multitude of industry applications ranging from manufacturing to financial transactions through to real estate. In addition to Artificial Intelligence (AI) and Internet of Things (IoT), Distributed Ledger Technology (DLT) such as blockchain serves as the backbone to the Machine Economy, which is a relatively recent concept in which machines can communicate and exchange data with each other autonomously, allowing manufacturing companies to become more competitive. However, using blockchain for exchanging large volumes of data requires significant fees and energy due to its use of miners to validate transactions which is a barrier for manufacturing companies to implement. Directed Acyclic Graph (DAG), which is a different type of DLT is an example of an alternative to blockchain which aims to overcome most of the problems currently on the blockchain and promises to enable fee-less transactions with much lower power requirements than blockchain. In this paper, the authors explore the DLT aspect of the machine economy within the manufacturing context. Firstly, the enabling DLT technical attributes of the machine economy are analysed. This is followed by an evaluation of all DLT’s, focusing on the challenges and benefits of each alternative. Following on from this, a cross comparison of each DLT type is done which leads into a discussion and future directions to be drawn.
Xin Wang, Sisi Duan, James R. Clavin, Haibin Zhang
A blockchain is a distributed system that achieves strong security guarantees in storing, managing, and processing data. All blockchains achieve a common goal: building a decentralized system that provides a trustworthy service in an untrustworthy environment. A blockchain builds a Byzantine fault-tolerant (BFT) system in which decentralized nodes run a protocol to reach an agreement on the common system state. In this article, we focus on the research of BFT protocols. In particular, we categorize BFT protocols according to both the system models and workflow. We seek to answer these important questions: How has the research in BFT evolved in the past four decades, especially with the rise of blockchains? What are the driven needs for BFT research in the future?
Christian Cachin, Jovana Mićić, Nathalie Steinhauer, Luca Zanolini
Leader-based protocols for consensus, i.e., atomic broadcast, allow some processes to unilaterally affect the final order of transactions. This has become a problem for blockchain networks and decentralized finance because it facilitates front-running and other attacks. To address this, order fairness for payload messages has been introduced recently as a new safety property for atomic broadcast complementing traditional agreement and liveness. We relate order fairness to the standard validity notions for consensus protocols and highlight some limitations with the existing formalization. Based on this, we introduce a new differential order fairness property that fixes these issues. We also present the quick order-fair atomic broadcast protocol that guarantees payload message delivery in a differentially fair order and is much more efficient than existing order-fair consensus protocols. It works for asynchronous and for eventually synchronous networks with optimal resilience, tolerating corruptions of up to one third of the processes. Previous solutions required there to be less than one fourth of faults. Furthermore, our protocol incurs only quadratic cost, in terms of amortized message complexity per delivered payload.
А. В. Богданов, Vladimir Korkhov, Nadezhda Shchegoleva, Vasilii M. Khvatov · 8 authors
Potential benefits of implementation of distributed ledger technology are widely discussedamong different business actors and governmental structures. Within the last decade, with growingpopularity of blockchain-based payment systems and cryptocurrencies, these discussions considerablysharpened. Therefore, an extensive body of research has emerged on this soil. The goal of this study isto attempt to make a comparative analysis of several existing blockchain-based distributed ledgerplatforms. Besides that, authors overview the most commonly used consensus algorithms and designapproaches, as for any blockchain product, consensus algorithm is a crucial part which determines theperformance of the overall system. Choosing the right algorithm would ensure high reliability andthroughput, while the wrong choice could cause fatal malfunctions for the application. A suitablealgorithm usually should be chosen according to the task in consideration, e.g. Nakamoto-styleprotocols could be considered better for public networks, while multiround voting protocols are moresuitable for private and secure systems. The highest attention is paid to consensus algorithms based onthe solution of the Byzantine Fault Tolerance problem (BFT).
Abstract We analyze the protocol of the bitcoin blockchain by using the PRISM probabilistic model checker. In particular, we (i) extend PRISM with the ledger data type , (ii) model the behavior of the key participants in the protocol—the miners —and (iii) describe the whole protocol as a parallel composition of processes. The probabilistic analysis of the model highlights how forks happen and how they depend on specific parameters of the protocol, such as the difficulty of the cryptopuzzle and the network communication delays. Our results confirm that considering transactions in blocks at depth larger than 5 as confirmed is reasonable because the majority of miners have consistent blockchains up‐to that depth with probability of almost 1. We also study the behavior of networks with churn miners, which may leave the network and rejoin afterwards, and with different topologies.
Seyed Hossein Haeri, Peter Thompson, Neil Davies, Peter Van Roy · 6 authors
This paper directly addresses a critical issue that affects the development of many complex distributed software systems: how to establish quickly, cheaply and reliably whether they will deliver their intended performance before expending significant time, effort and money on detailed design and implementation. We describe ΔQSD, a novel metrics-based and quality-centric paradigm that uses formalised outcome diagrams to explore the performance consequences of design decisions, as a performance blueprint of the system. The ΔQSD paradigm is both effective and generic: it allows values from various sources to be combined in a rigorous way, so that approximate results can be obtained quickly and subsequently refined. ΔQSD has been successfully used by Predictable Network Solutions for consultancy on large-scale applications in a number of industries, including telecommunications, avionics, and space and defence, resulting in cumulative savings of $Bs. The paper outlines the ΔQSD paradigm, describes its formal underpinnings, and illustrates its use via a topical real-world example taken from the blockchain/cryptocurrency domain, where application of this approach enabled an advanced distributed proof-of-stake system to meet challenging throughput targets.
In this paper, we present a plugin for visualising vote based consensus\nmechanisms primarily aimed to help engineers understand and debug blockchain\nand distributed ledger protocols. Both tools are built as Grafana plugins and\nmake no assumptions on the data storage implementation. The plugins can be\nconfigured via Grafana plugin configuration interface to fit the specifics of\nthe protocol implementation.\n
Joachim Neu, Srivatsan Sridhar, Lei Yang, David Tse · 5 authors
Spamming attacks are a serious concern for consensus protocols, as witnessed by recent outages of a major blockchain, Solana. They cause congestion and excessive message delays in a real network due to its bandwidth constraints. In contrast, longest chain (LC), an important family of consensus protocols, has previously only been proven secure assuming an idealized network model in which all messages are delivered within bounded delay. This model-reality mismatch is further aggravated for Proof-of-Stake (PoS) LC where the adversary can spam the network with equivocating blocks. Hence, we extend the network model to capture bandwidth constraints, under which nodes now need to choose carefully which blocks to spend their limited download budget on. To illustrate this point, we show that 'download along the longest header chain', a natural download rule for Proof-of-Work (PoW) LC, is insecure for PoS LC. We propose a simple rule 'download towards the freshest block', formalize two common heuristics 'not downloading equivocations' and 'blocklisting', and prove in a unified framework that PoS LC with any one of these download rules is secure in bandwidth-constrained networks. In experiments, we validate our claims and showcase the behavior of these download rules under attack. By composing multiple instances of a PoS LC protocol with a suitable download rule in parallel, we obtain a PoS consensus protocol that achieves a constant fraction of the network's throughput limit even under worst-case adversarial strategies.
Joachim Neu, Srivatsan Sridhar, Lei Yang, David Tse · 5 authors
Satoshi Nakamoto's Proof-of-Work (PoW) longest chain (LC) protocol was a breakthrough for Internet-scale open-participation consensus. Many Proof-of-Stake (PoS) variants of Nakamoto's protocol such as Ouroboros or Snow White aim to preserve the advantages of LC by mimicking PoW LC closely, while mitigating downsides of PoW by using PoS for Sybil resistance. Previous works have proven these PoS LC protocols secure assuming all network messages are delivered within a bounded delay. However, this assumption is not compatible with PoS when considering bandwidth constraints in the underlying communication network. This is because PoS enables the adversary to reuse block production opportunities and spam the network with equivocating blocks, which is impossible in PoW. The bandwidth constraint necessitates that nodes choose carefully which blocks to spend their limited download budget on. We show that 'download along the longest header chain', a natural download rule for PoW LC, emulated by PoS variants, is insecure for PoS LC. Instead, we propose 'download towards the freshest block' and prove that PoS LC with this download rule is secure in bandwidth constrained networks. Our result can be viewed as a first step towards the co-design of consensus and network layer protocols.
SATHISHKUMAR RANGANATHAN, Muralindran Mariappan, M. Karthigayan
Swarm robotics is an evolving realm that aims to achieve a common goal in coordinated way. But the current communication and control mechanism between the robots is not secure, efficient, capable, and it is more centralized. Blockchain, a decentralized, transparent, and immutable P2P communication technology, is the right fit to pair with swarm robotics. This paper discusses the current challenges in paring blockchain with swarm robotics and the applied methodology for the amalgamation of these futuristic technologies.
The Nervos CKB (Common Knowledge Base) is a public permissionless blockchain designed for the Nervos ecosystem. The CKB consensus protocol is the key protocol of the Nervos CKB, which improves the limit of the consensus’s performance for Bitcoin. In this paper, we developed the formal model of the CKB consensus protocol using timed automata. Based on the model, we formally verified various important properties of the Nervos CKB to provide a sufficient trustworthiness assurance. Especially, the security of the Nervos CKB against the selfish mining attacks to the protocol was investigated.
Eder J. Scheid, Pascal Kiechl, Muriel Figueredo Franco, Bruno Rodrigues · 6 authors
Over the past years, Blockchain (BC) interoperability became a crucial topic of research due to the fast development of new BC platforms for many use-cases, from supply-chain to voting. The need for interoperability can be attributed to the development of such platforms that did not follow any standard, leading to the creation of BC islands that do not exchange data, which hinders innovation. Hence, several BC interoperability solutions were proposed to tackle such problems. One of them is Bifröst, a Notary scheme-based BC interoperability Application Programming Interface (API) that allows the transparent interaction by users or legacy applications with several BCs. An initial prototype of Bifröst was developed, proving its feasibility; however, it did not provide native data encryption or an interaction standard. Thus, this paper presents the design and implementation of an encryption scheme for Bifröst and a JSON format proposal to interact with Bifröst, which also contributes to the state-of-the-art. Evaluations on the encryption scheme show an increase of the data size after the encryption but a constant performance overhead, and discussions on the standard prove that it can be applied to other Notary-based BC interoperability APIs due to its flexibility.
The existing Bitcoin security research has mainly followed the security models in [22, 35], which stipulate that an adversary controls some mining power in order to violate the blockchain consistency property (i.e., through a double-spend attack). These models, however, largely overlooked the impact of the realistic network synchronization, which can be manipulated given the permissionless nature of the network. In this paper, we revisit the security of Bitcoin blockchain by incorporating the network synchronization into the security model and evaluating that in practice. Towards this goal, we propose the ideal functionality for the Bitcoin network synchronization and specify bounds on the network outdegree and the block propagation delay in order to preserve the consistency property. By contrasting the ideal functionality against measurements, we find deteriorating network synchronization reported by Bitnodes and a notable churn rate with 10% of the nodes arriving and departing from the network daily.