Blockchain Papers

Majed Abdullah Alrowaily, Mansoor Alghamdi, Ibrahim S. Alkhazi, Ahmad B. Hassanat · 6 authors

Blockchain technology has a wide range of applicability in the fields of transportation infrastructure construction and maintenance, transportation big data analysis and application, expressway toll collection, and logistics. The core technology lies in the distributed, decentralized, immutable, and programmable features brought about by consensus. This paper studies the dynamic analytical modeling of Proof-Based Consensus (PBC) strategies in blockchain systems, focusing on basic strategies, including Proof of Work (PoW), Proof of Stake (PoS), Proof of Authority (PoA), and Proof of Luck (PoL), which can be extended to other PBC models. We focus on modeling these typical strategies and discuss their solution characteristics in terms of algorithmic mechanisms and principles. The relevant results can be used for quantitative analysis and evaluation of distributed consensus based on the model.

Martin Westerkamp, Axel Küpper

Most current cross-blockchain approaches focus on exchanging or transferring tokens between networks. While some concepts foster smart contract invocations across blockchains, they require multiple transactions and operate asynchronously. We present a concept enabling instant smart contract calls by creating synchronized client contracts on arbitrary blockchains. Other smart contracts can query these client contracts on the target blockchain for retrieving information without requiring cross-chain message queues. With this, we reduce the dependency of smart contracts on their host blockchain, as remote contracts become available as read-only instances. The synchronization process does not require trust in the executing intermediary since Merkle proofs based on shared state roots are utilized to guarantee correct execution. We propose a novel concept called transition proofs for efficiently proving the correctness of state updates. The prototypical implementation permits smart contract synchronization between EVM-compatible blockchains. Our evaluation shows the approach’s applicability regarding execution costs and delay. Further, we conduct a case study by synchronizing one of the largest decentralized exchanges deployed to the Ethereum network.

Jie Xu, Cong Wang, Xiaohua Jia

Blockchain consensus protocols have been a focus of attention since the advent of Bitcoin. Although classic distributed consensus algorithms made significant contributions to the development of blockchain consensus protocols, there are still many issues to be resolved due to the complexity and diversity of the blockchain. In this survey, we summarize the state-of-the-art blockchain consensus protocols. We first introduce the theoretical basis, models, and challenges of blockchain consensus protocols. Then, we present the existing blockchain protocols in the categories of proof-based protocols, committee-based protocols, and other miscellaneous protocols. Finally, we analyze their performance and discuss future research directions by comparing existing protocols.

Rui Morais, Paul Crocker, Valderi Reis Quietinho Leithardt

This paper presents the research undertaken with the goal of designing a consensus algorithm for cryptocurrencies with less latency than the current state-of-the-art while maintaining a level of throughput and scalability sufficient for real-world payments. The result is Nero, a new deterministic leaderless byzantine consensus algorithm in the partially synchronous model that is especially suited for Directed Acyclic Graph (DAG)-based cryptocurrencies. In fact, Nero has a communication complexity of O(n3) and terminates in two message delays in the good case (when there is synchrony). The algorithm is shown to be correct, and we also show that it can provide eventual order. Finally, some performance results are given based on a proof of concept implementation in the Rust language.

Chunyu Mao, Wojciech Golab

Blockchain is a distributed ledger that uses cryptography and consensus protocols to record a growing list of transactions in a tamper-resistant manner. Scalability is one of the main problems that limit its usage. This paper introduces a full sharding protocol, Geochain, for permissioned blockchains. We first clarify the limitations of state-of-the-art sharding protocols. Then, we propose a locality-based sharding protocol that achieves high scalability. We optimize inter-shard performance by clustering participants using their geographical properties, locality. In addition, the locality is also employed to decide the transaction placement which results in a low ratio of cross-shard transactions for applications, such as everyday banking, retail payments, and electric vehicle charging. We also propose a client-driven efficient mechanism to handle cross-shard transactions and present an analysis. This enables clients to manage their assets across different shards directly. A prototype is implemented on top of Hyperledger Fabric v2.3 and evaluated on Amazon EC2. The experiments show that our protocol doubles the peak throughput, even with a high ratio of cross-shard transactions, while minimizing the transaction latency.

Antonio Cruciani, Francesco Pasquale

The network formation process in the Bitcoin protocol is designed to hide the global network structure: while most of the nodes of the network can be easily discovered, the existence of an edge between two nodes is only known by the two endpoints. In [Becchetti et al., SODA2020] the authors propose a dynamic random graph model inspired by the network formation process in the Bitcoin protocol and they prove that the evolution of the graph quickly terminates and that the resulting graph is an expander, with high probability.

Santiago Cuéllar Gempeler, Bill Harris, James Parker, Stuart Pernsteiner · 6 authors

Currently, when a security analyst discovers a vulnerability in critical software system, they must navigate a fraught dilemma: immediately disclosing the vulnerability to the public could harm the system’s users; whereas disclosing the vulnerability only to the software’s vendor lets the vendor disregard or deprioritize the security risk, to the detriment of unwittingly-affected users. A compelling recent line of work aims to resolve this by using Zero Knowledge (ZK) protocols that let analysts prove that they know a vulnerability in a program, without revealing the details of the vulnerability or the inputs that exploit it. In principle, this could be achieved by generic ZK techniques. In practice, ZK vulnerability proofs to date have been restricted in scope and expressibility, due to challenges related to generating proof statements that model real-world software at scale and to directly formulating violated properties. This article presents Cheesecloth , a novel proof-statement compiler, which proves practical vulnerabilities in ZK by soundly-but-aggressively preprocessing programs on public inputs, selectively revealing information about executed control segments, and formalizing information leakage using a novel storage-labeling scheme. Cheesecloth ’s practicality is demonstrated by generating ZK proofs of well-known vulnerabilities in (previous versions of) critical software, including the Heartbleed information leakage in OpenSSL, a memory vulnerability in the FFmpeg multimedia encoding framework, a cryptographic implementation bug in the Secure Scuttlebutt decentralised social network, and a denial of service vulnerability in OpenSSL.

Philipp Hoenisch, Subhra Mazumdar, Pedro Moreno-Sánchez, Sushmita Ruj

No abstract is available for this record.

Eli Gafni, Giuliano Losa

In a permissionless system like Ethereum, participation may fluctuate dynamically as some participants unpredictably go offline and some others come back online. In such an environment, traditional Byzantine fault-tolerant consensus algorithms may stall - even in the absence of failures - because they rely on the availability of fixed-sized quorums. The sleepy model formally captures the main requirements for solving consensus under dynamic participation, and several algorithms solve consensus with probabilistic safety in this model assuming that, at any time, more than half of the online participants are well behaved. However, whether safety can be ensured deterministically under these assumptions, especially with constant latency, remained an open question. Assuming a constant adversary, we answer in the positive by presenting a consensus algorithm that achieves deterministic safety and constant latency in expectation. In the full version of this paper, we also present a second algorithm which obtains both deterministic safety and liveness, but is likely only of theoretical interest because of its high round and message complexity. Both algorithms are striking in their simplicity.

Michael F. Marchini

In the development of large-scale, integrated systems, the consistent clarity and distribution of knowledge and relevant status is crucial to success. There are many existing methods and commercial tools for providing context and traceability from requirements and specifications to a system's artifacts, but these tools are often vendor-locked and require access to cloud-based services and necessitate high licensing costs. Further, modern large-scale systems development involves multiple business partners, each of which needs to ensure their teams have granular, role-based access to all relevant information without impediment; centralized warehousing and gatekeeping should not be handled by a single entity if the information is to remain readily accessible. Instead, a permissioned, distributed knowledgebase that avoids vendor lock-in enables a consistent, real-time view of information that provides equivalent context for developers and other stakeholders. ChaordicLedger, a free and open source (FOSS) project joins the transparency and smart contract aspects of Distributed Ledger Technology with the storage capabilities of a Distributed File System to fulfill this industrial application while allowing for industry-specific customizations.

Fuchen Ma, Yuanliang Chen, Meng Ren, Yuanhang Zhou · 8 authors

Blockchain consensus protocols are responsible for coordinating the nodes to make agreements on the transaction results. Their implementation bugs, including memory-related and consensus logic vulnerabilities, may pose serious threats. Fuzzing is a promising technique for protocol vulnerability detection. However, existing fuzzers cannot deal with complex consensus states of distributed nodes, thus generating a large number of useless packets, inhibiting their effectiveness in reaching the deep logic of consensus protocols.

Siamak Solat

Cette thèse de doctorat se compose de 6 chapitres. Dans le premier chapitre, en guise d'introduction, nous donnons un aperçu des objectifs généraux et des motivations des réseaux décentralisés et permissionless, ainsi que des obstacles auxquels ils sont confrontés. Dans l'introduction, nous évoquons également la solution irrationnelle et illogique, connue sous le nom de « blockchain permissioned », qui a été proposée pour améliorer les performances des réseaux similaires à Bitcoin. Cette question a été détaillée au chapitre 5. Dans le chapitre 2, nous rendons clairs et intelligibles les systèmes que l'idée proposée, « Parallel Committees », est basée sur de tels réseaux. Nous détaillons les fonctionnalités indispensables et les défis essentiels des systèmes de réplication. Ensuite, dans le chapitre 3, nous discutons des limitations de scalabilité et du faible débit des systèmes de réplication qui utilisent des mécanismes de consensus pour traiter les transactions et comment ces problèmes peuvent être améliorés en utilisant des techniques de sharding. Nous décrivons les défis les plus importants dans le sharding des systèmes de réplication distribuée, une approche qui a déjà été mise en œuvre dans plusieurs systèmes de réplication basés sur la blockchain et, bien qu'elle ait montré un potentiel significatif pour améliorer les performances et la scalabilité, les techniques de sharding actuelles ont encore des limitations de scalabilité et des défis de sécurité. Nous expliquons pourquoi la plupart des protocoles de sharding actuels utilisent une approche d'allocation aléatoire pour distribuer les nœuds entre les shards pour des raisons de sécurité. Nous décrivons également comment traiter une transaction dans un système de réplication partitionné basé sur les protocoles de sharding actuels. Nous expliquons comment un « shared-ledger » partagé sur les shards impose des limitations de scalabilité et des défis de sécurité au réseau, et expliquons pourquoi les transactions « cross-shards » ou « inter-shards » sont indésirables et plus coûteuses en raison des problèmes qu'elles causent, y compris « atomicity failure » et les défis de « state transition », ainsi qu'une passe en revue des solutions proposées. Nous passons également en revue certains des travaux récents les plus remarquables qui utilisent des techniques de sharding pour les systèmes de réplication. Cette partie de l'ouvrage a été publiée sous la forme d'un chapitre de livre (peer-reviewed) in « Building Cybersecurity Applications with Blockchain Technology and Smart Contracts » (Springer, 2023). Dans le chapitre 4, nous proposons une nouvelle technique de sharding, « Parallel Committees », prenant en charge à la fois le « processing-sharding » et le « storage/state sharding », pour améliorer la scalabilité et les performances des systèmes de réplication distribués qui utilisent des mécanismes de consensus pour traiter les demandes des clients (client requests). Nous introduisons une approche innovante et originale pour répartir les nœuds entre les shards à l'aide d'un processus de génération de clé publique qui atténue simultanément l'attaque Sybil et sert de mécanisme de preuve de travail (proof-of-work). Notre approche réduit efficacement les transactions « inter-shards » indésirables, qui sont plus complexes et coûteuses à traiter que les transactions « intra-shards ». L'idée proposée a été publiée dans la conférence IEEE BCCA 2023. Nous expliquons ensuite pourquoi nous n'utilisons pas la structure de la blockchain dans l'idée proposée, un sujet abordé en détail au chapitre 5. Cette explication et clarification a été publiée dans le Journal of Software (JSW), Volume 16, Number 3, May 2021. Et dans le dernier chapitre de cette thèse, le chapitre 6, nous résumons les points importants et les conclusions de cette recherche.

Elvira Albert, Samir Genaim, Daniel Kirchner, Enrique Martin-Martin

Abstract The efficiency and the security of smart contracts are their two fundamental properties, but might come at odds: the use of optimizers to enhance efficiency may introduce bugs and compromise security. Our focus is on (Ethereum Virtual Machine) block-optimizations , which enhance the efficiency of jump-free blocks of opcodes by eliminating, reordering and even changing the original opcodes. We reconcile efficiency and security by providing the verification technology to formally prove the correctness of block-optimizations on smart contracts using the Coq proof assistant. This amounts to the challenging problem of proving semantic equivalence of two blocks of instructions, which is realized by means of three novel Coq components: a symbolic execution engine which can execute an block and produce a symbolic state; a number of simplification lemmas which transform a symbolic state into an equivalent one; and a checker of symbolic states to compare the symbolic states produced for the two blocks under comparison. Artifact: https://doi.org/10.5281/zenodo.7863483

Leonardo Mostarda, Andrea Pinna, Davide Sestili, Roberto Tonelli

No abstract is available for this record.

Babu Pillai, Zhé Hóu, Kamanashis Biswas, Vallipuram Muthukkumarasamy

This paper introduces an abstract blockchain model that employs the Burn-to-Claim cross-blockchain protocol [1]. This multi-level simulator models a virtual environment of nodes running on the Ethereum Virtual Machine (EVM). Developed using the $$CSP\#$$ language [2], it has undergone formal verification with the model checker PAT. Focusing on inter-network operations, our model ( https://github.com/b-pillai/Burn-to-Claim-formal-verification ) examines the properties of correctness, security, and atomicity using PAT. Surprisingly, atomicity, assumed to be inherent in the time-lock mechanism of the Burn-to-Claim protocol, does not always hold. We establish its validity under specific assumptions while confirming the protocol’s correctness and security under the added assumptions.

Anas Alsobeh, Aws A. Magableh

Blockchain systems are lauded for their security and reliability. Security is a cornerstone, as they employ cryptographic techniques to ensure the immutability of data, making it extremely resistant to tampering. With decentralized networks, they also reduce the risk of a single point of failure, enhancing reliability. Model checking plays a vital role in ensuring the security and reliability of blockchain systems. However, traditional model-checking approaches face challenges in handling the inherent dynamism exhibited in blockchain systems. To overcome this challenge, Aspect-Oriented programming (AOP) offers capabilities to enhance blockchain model checking through the modularization of cross-cutting concerns, enabling traceability and monitoring, facilitating dynamic instrumentation, and supporting fine-grained property specifications. The aim of this research is to enable more effective and efficient verification of dynamic behaviors in blockchain systems compared to conventional model-checking techniques using AOP. As a result, this research introducesBlockASP, a novel blockchain model verification method that leverages AOP to analyze and monitor dynamic behavior of the blockchain system.BlockASPintegrates the benefits of aspect-orientation and model checking into the blockchain architecture to strengthen security and reliability. This research has examined prior arts that are related to blockchain modeling using Object-oriented (OO) and those that are using AOP. Our research has proposed and discussed theBlockASPtechnique, the research provided a case study to demonstrate the validity and superiority in facilitating the monitoring of dynamic blockchain behavior using AOP compared to traditional approaches such as Model-Driven Architecture (MDA).

Carlos Núñez‐Gómez, Martijn de Vos, Jérémie Decouchant, Johan Pouwelse · 6 authors

With the proliferation of Internet of Things (IoT) ecosystems, traditional resource orchestration mechanisms, executed on fog devices, encounter significant scalability, reliability and security challenges. To tackle these challenges, recent decentralized algorithms in Fog-IoT use Distributed Ledger Technologies to orchestrate resources and payments between peers. However, while distributed ledgers provide many desirable properties, their consensus mechanism introduces a performance bottleneck. This paper introduces Light-HIDRA, a consensus-less and decentralized resource orchestration system for Fog-IoT environments. At its core, Light-HIDRA uses Byzantine Reliable Broadcast (BRB) to coordinate actions without centralized control, therefore drastically reducing communication overhead and latency compared to consensus-based solutions. Light-HIDRA coordinates the scheduling and execution of workloads, and securely manages the payments that peers receive for dedicating resources to workloads. Light-HIDRA further increases performance and reduces overhead by grouping peers into distinct domains. We conduct an in-depth analysis of the protocol’s security properties, investigating its efficiency and robustness in diverse situations. We evaluate the performance of Light-HIDRA, highlighting its performance over HIDRA, a state-of-the-art baseline that uses smart contracts. Our experiments demonstrate that Light-HIDRA reduces the bandwidth usage by up to 57x, the latency of workload offloading by up to 142x, and shows superior throughput compared to HIDRA.

Alex Kemloh Kouyem

Diese Arbeit präsentiert ein Protokoll für vertrauliche Transaktionen auf Ethereum, das auf einer kontenbasierten Struktur und Paillier-Verschlüsselung basiert. Die Integration von Non-Interactive Zero-Knowledge Range Proofs (NIZKRP) verbessert die Sicherheit. Die Implementierung und Tests auf Ethereum zeigen vergleichbare Transaktionskosten (Sicherheitsparameter 40) im Vergleich zu Protokollen mit Bulletproofs. Bei einem Sicherheitsparameter von 128 (NIZKRP-Empfehlung) ist das Protokoll jedoch nicht anwendbar. Die Arbeit betont die Effizienz und Wettbewerbsfähigkeit, hebt jedoch die Herausforderung bei höheren Sicherheitsparametern hervor. Das Protokoll bildet eine solide Grundlage, erfordert jedoch weitere Optimierungen für breitere Anwendbarkeit.

Bertalan Zoltán Péter, Imre Kocsis

In this paper, we propose the application of a well-known runtime fault-tolerance technique, N-Version Program-ming (NVP), as a new tool of smart contract software fault mitigation, especially for execute-order-validate blockchain systems, such as Hyperledger Fabric (HLF). Two patterns for aligning the NVP concept with the HLF architecture are proposed. A fully transparent solution where all peers have the same N versions installed and one we termed ‘O-Version Programming’ (where ‘O’ stands for ‘Organization’), which relies on the majority voting aspects of execute-order-validate consensus mechanisms.

Ramesh Adhikari, Costas Busch

Sharding is used to address the performance and scalability issues of the blockchain protocols, which divides the overall transaction processing costs among multiple clusters of nodes. Shards require less storage capacity and communication and computation cost per node than the existing whole blockchain networks, and they operate in parallel to maximize performance. However, existing sharding solutions use locks for transaction isolation which lowers the system throughput and may introduce deadlocks. In this paper, we propose a lockless transaction method for ensuring transaction isolation without using locks, which improves the concurrency and throughput of the transactions. In our method, transactions are split into subtransactions to enable parallel processing in multiple shards. We use versions for the transaction accounts to implement consistency among the shards. We provide formal proof for liveness and correctness. We also evaluate experimentally our proposed protocol and compare the execution time and throughput with lock-based approaches. The experiments show that the transaction execution time is considerably shorter than the lock-based time and near to the ideal (no-lock) execution time.

Ehud Shapiro

Informally, a distributed system is grassroots if it is permissionless and can have autonomous, independently-deployed instances - geographically and over time - that may interoperate voluntarily once interconnected. More formally, in a grassroots system the set of all correct behaviors of a set of agents P is strictly included in the set of the correct behaviors of P when they are embedded within a larger set of agents P' ⊃ P. Grassroots systems are potentially important as they may allow communities to conduct their social, economic, civic, and political lives in the digital realm solely using their members' networked computing devices (e.g., smartphones), free of third-party control, surveillance, manipulation, coercion, or rent seeking (e.g., by global digital platforms such as Facebook or Bitcoin). Client-server/cloud computing systems are not grassroots, and neither are systems designed to have a single global instance (Bitcoin/Ethereum with hardwired seed miners/bootnodes), and systems that rely on a single global data structure (IPFS, DHTs). An example grassroots system would be a serverless smartphone-based social network supporting multiple independently-budding communities that can merge when a member of one community becomes also a member of another. Here, we formalize the notion of grassroots distributed systems; describe a grassroots dissemination protocol for the model of asynchrony and argue its safety, liveness, and being grassroots; extend the implementation to mobile (address-changing) devices that communicate via an unreliable network (e.g. smartphones using UDP); and discuss how grassroots dissemination can realize grassroots social networking and grassroots cryptocurrencies. The mathematical construction employs distributed multiagent transition systems to define the notions of grassroots protocols, to specify the grassroots dissemination protocols, and to prove their correctness. The protocols use the blocklace - a distributed, partially-ordered counterpart of the replicated, totally-ordered blockchain.

John Stuart

Avec la montée en puissance des ordinateurs quantiques, il est plus important que jamais de démontrer que les protocoles cryptographiques sont sécuritaires contre des adversaires quantiques. De plus, l'objectif de tout cryptographe est d’assouplir certaines hypothèses, en particulier celles qui restreignent la capacité de l’adversaire à effectuer de longs calculs. Dans cette thèse, un système multi-parties est utilisé pour créer deux preuves Zéro-Knowledge (ZK), celles-ci opèrent en temps polynomial et sont sécurisées. De plus, elles n’ont aucune restriction calculatoire pour aucune partie, même pour les adversaires qui partagent une intrication quantique. Une preuve ZK permet à une partie de prouver à une autre partie d’un fait sans révéler aucune connaissance autre que la véracité du fait. Par exemple, une telle preuve pourrait être utilisée pour permettre à un client de prouver son identité à un guichet bancaire sans donner des renseignements confidentiels tel que son numéro d'identification personnel. Un des principaux outils utilisés lors d’une preuve ZK est le schéma de mise en gage. Celui-ci est essentiellement un outil numérique permettant à un expéditeur de sceller un message dans un coffre-fort et de l’envoyer à un destinataire. Ensuite, quand l'expéditeur veut que le destinataire lise le message, la clé du coffre fort lui est envoyée. Ceci permet au message de rester inconnu du receveur jusqu'à ce qu’il reçoive la clé de l'expéditeur. De plus, l'expéditeur ne peut pas changer le message une fois le coffre-fort envoyé. Au cours de cette thèse, les propriétés homomorphiques d’un schéma multi-parties de mise en gage sont utilisées pour permettre au destinataire d’effectuer des opérations sur le gage. Ceci donne ainsi des preuves ZK pour deux problèmes NP-complets, les problèmes de la somme de sous-ensembles et 3-SAT

Sangita Roy, R. K. Shyamasundar

No abstract is available for this record.

Ray Neiheiser, Gustavo Inácio, Luciana Rech, Carlos Montez · 6 authors

Most permissionless blockchains inherently suffer from throughput limitations. Layer-2 systems, such as side-chains or Rollups, have been proposed as a possible strategy to overcome this limitation. Layer-2 systems interact with the main-chain in two ways. First, users can move funds from/to the main-chain to/from the layer-2. Second, layer-2 systems periodically synchronize with the main-chain to keep some form of log of their activity on the main-chain - this log is key for security. Due to this interaction with the main-chain, which is necessary and recurrent, layer-2 systems impose some load on the main-chain. The impact of such load on the main-chain has been, so far, poorly understood. In addition to that, layer-2 approaches typically sacrifice decentralization and security in favor of higher throughput. This paper presents an experimental study that analyzes the current state of Ethereum layer-2 projects. Our goal is to assess the load they impose on Ethereum and to understand their scalability potential in the long-run. Our analysis shows that the impact of any given layer-2 on the main-chain is the result of both technical aspects (how state is logged on the main-chain) and user behavior (how often users decide to transfer funds between the layer-2 and the main-chain). Based on our observations, we infer that without efficient mechanisms that allow users to transfer funds in a secure and fast manner directly from one layer-2 project to another, current layer-2 systems will not be able to scale Ethereum effectively, regardless of their technical solutions. Furthermore, from our results, we conclude that the layer-2 systems that offer similar security guarantees as Ethereum have limited scalability potential, while approaches that offer better performance, sacrifice security and lead to an increase in centralization which runs against the end-goals of permissionless blockchains.