Coordicide Papers

The Coordicide

Coordicide Team

Abstract

The Coordicide project is focused on the removal of the Coordinator through the implementation of several network components, as discussed in this working paper. Despite these additional components, all existing fundamental design features of the Tangle remain in-place.

FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures

Serguei Popov and William J Buchanan

Journal of Parallel and Distributed Computing, Volume 147, January 2021, pages 77-86. DOI: 10.1016/j.jpdc.2020.09.002

Abstract

This paper presents a novel leaderless protocol (FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures) with a low communicational complexity and which allows a set of nodes to come to a consensus on a value of a single bit. The paper makes the assumption that part of the nodes are Byzantine, and are thus controlled by an adversary who intends to either delay the consensus, or break it (this defines that at least a couple of honest nodes come to different conclusions). We prove that, nevertheless, the protocol works with high probability when its parameters are suitably chosen. Along this the paper also provides explicit estimates on the probability that the protocol finalizes in the consensus state in a given time. This protocol could be applied to reaching consensus in decentralized cryptocurrency systems. A special feature of it is that it makes use of a sequence of random numbers which are either provided by a trusted source or generated by the nodes themselves using some decentralized random number generating protocol. This increases the overall trustworthiness of the infrastructure. A core contribution of the paper is that it uses a very weak consensus to obtain a strong consensus on the value of a bit, and which can relate to the validity of a transaction.

Robustness and efficiency of leaderless probabilistic consensus protocols within Byzantine infrastructures

Angelo Capossele, Sebastian Müller and Andreas Penzkofer

Abstract

This paper investigates leaderless binary majority consensus protocols with low computational complexity in noisy Byzantine infrastructures. Using computer simulations, we show that explicit randomization of the consensus protocol can significantly increase the robustness towards faulty and malicious nodes. We identify the optimal amount of randomness for various Byzantine attack strategies on different kinds of network topologies.

Fast Probabilistic Consensus with Weighted Votes

Sebastian Müller, Andreas Penzkofer, Bartosz Kuśmierz, Darcy Camargo and William J Buchanan

Accepted at Future Technology Conference, 2020.

Abstract

The fast probabilistic consensus (FPC) is a voting consensus protocol that is robust and efficient in Byzantine infrastructure. We propose an adaption of the FPC to a setting where the voting power is proportional to the nodes reputations. We model the reputation using a Zipf law and show using simulations that the performance of the protocol in Byzantine infrastructure increases with the Zipf exponent. Moreover, we propose several improvements of the FPC that decrease the failure rates significantly and allow the protocol to withstand adversaries with higher weight. We distinguish between cautious and berserk strategies of the adversaries and propose an efficient method to detect the more harmful berserk strategies. Our study refers at several points to a specific implementation of the IOTA protocol, but the principal results hold for general implementations of reputation models.

IOTA: Feeless and Free

Serguei Popov

Published in IEEE Blockchain Technical Briefs, 2019.

Achieving Fairness in the Tangle through an Adaptive Rate Control Algorithm

Luigi Vigneri, Wolfgang Welz, Alon Gal and Vassil Dimitrov

Published in IEEE International Conference on Blockchain, 2019.

Abstract

Throughput is a key property for any distributed ledger technology. However, limited resources, such as bandwidth or node computational power, can lead to network congestion when nodes try to issue more transactions than the network can handle. Consequently, priority criteria are necessary to determine whether a transaction should be accepted or not. In this paper, we present a novel adaptive rate control algorithm for the Tangle, a new-generation distributed ledger allowing large throughput. Our approach combines various concepts, such as resource tests and Proof-of-Work with dynamic difficulty. Our algorithm not only serves as an anti-spam mechanism, but also achieves fair representation. This is to be contrasted with pure Proof-of-Work blockchains, which lead to wasteful mining races.

On the Fairness of Distributed Ledger Technologies for the Internet of Things

Luigi Vigneri and Wolfgang Welz

Published in IEEE International Conference on Blockchain, 2020.

Abstract

Distributed networks have been widely studied in literature. However, the blockchain paradigm has inspired to revisit some of the results under a different point of view. In this paper, we analyze the “classic” spam protection problem applied to the IOTA Tangle, a distributed ledger technology which addresses Bitcoin’s (monetary and energy) efficiency issues through the absence of mining pools. However, the lack of miners makes the network vulnerable to denial of service attacks. We propose an anti spam mechanism based on the solution of a cryptographic puzzle: When a node wants to generate a new transaction, it dynamically adapts the difficulty of the puzzle depending on its target throughput and on its reputation score. Specifically, the adaptive difficulty property guarantees that any node, even with low hashing power, can achieve similar throughput for a given reputation. In the paper, we prove this claim both analytically and through simulations, and we show that fairness between low- and high-power nodes is indeed reached.

Smooth Operator -- The Use of Smooth Integers in Fast Generation of RSA Keys

Vassil Dimitrov, Luigi Vigneri and Vidal Attias

Abstract

Primality generation is the cornerstone of several essential cryptographic system, most notably, the RSA cryptosystem. The problem has been a subject of deep investigations by the computational number theorists, but there is still room for improvement. Typically, the algorithms used have two parts - trial divisions aimed at eliminating numbers with small prime factors and primality tests based on an easy-to-compute statement that is valid for primes and invalid for composites. In this paper we will showcase a technique that will eliminate the first phase of the primality testing algorithms. It is particularly suitable for a decentralized RSA key generation. The computational simulations show reduction of the primality generation time for about 30% in the case of 1024-bit RSA private keys. We are also proposing one new one-way function that can be used either as a hash function or as cryptographic puzzle for mining purposes.

On the Decentralized Generation of the RSA Moduli in Multi-Party Settings

Vidal Attias, Luigi Vigneri and Vassil Dimitrov

Abstract

RSA cryptography is still widely used. Some of its applications (e.g., distributed signature schemes, cryptosystems) do not allow the RSA modulus to be generated by a centralized trusted entity. Instead, the factorization must remain unknown to all the network participants. To this date, the existing algorithms are either computationally expensive, or limited to two-party settings. In this work, we design a decentralized multi-party computation algorithm able to generate efficiently the RSA modulus.

Implementation Study of Two Verifiable Delay Functions

Vidal Attias, Luigi Vigneri and Vassil Dimitrov

Published in Tokenomics, 2020.

Abstract

Proof of Work is a prevalent mechanism to prove investmentof time in blockchain projects. However the use of massive parallelismand specialized hardware gives an unfair advantage to a small portion ofnodes and raises environmental and economical concerns. In this paperwe provide an implementation study of two Verifiable Delay Functions, anew cryptographic primitive achieving Proof of Work goals in an unpar-allelizable way. We provide simulation results and an optimization basedon a multiexponentiation algorithm.

Pre-Coordicide Papers

The Tangle

Serguei Popov

Abstract

This paper analyzes the mathematical foundations of IOTA, a cryptocurrency for the Internet-of-Things (IoT) industry. The main feature of this novel cryptocurrency is the tangle, a directed acyclic graph (DAG) for storing transactions. The tangle naturally succeeds the blockchain as its next evolutionary step, and offers features that are required to establish a machineto-machine micropayment system.

Equilibria in the Tangle

Serguei Popov, Olivia Saa and Paulo Finardi

Published in Computers & Industrial Engineering, 2019.

Abstract

We analyse the Tangle — a DAG-valued stochastic process where new vertices get attached to the graph at Poissonian times, and the attachment’s locations are chosen by means of random walks on that graph. These new vertices, also thought of as “transactions”, are issued by many players (which are the nodes of the network), independently. The main application of this model is that it is used as a base for the IOTA cryptocurrency system. We prove existence of “almost symmetric” Nash equilibria for the system where a part of players tries to optimize their attachment strategies. Then, we also present simulations that show that the “selfish” players will nevertheless cooperate with the network by choosing attachment strategies that are similar to the “recommended” one.

Properties of the Tangle for Uniform Random and Random Walk Tip Selection

Bartosz Kuśmierz, William Sanders, Andreas Penzkofer, Angelo Capossele and Alon Gal

Published in IEEE International Conference on Blockchain, 2019.

Abstract

The growing number of applications for distributed ledger technologies is driving both industry and academia to solve the limitations of blockchain, particularly its scalability issues. Recent distributed ledger technologies have replaced the blockchain linear structure with a more flexible directed acyclic graph in an attempt to accommodate a higher throughput. Despite the fast-growing diffusion of directed acyclic graph based distributed ledger technologies, researchers lack a basic understanding of their behavior. In this paper we analyze the Tangle, a directed acyclic graph that is used (with certain modifications) in various protocols such as IOTA, Byteball, Avalanche or SPECTRE. Our contribution is threefold. First, we run simulations in a continuous-time model to examine tip count stability and cumulative weight evolution while varying the rate of incoming transactions. In particular we confirm analytical predictions on the number of tips with uniform random tip selection strategy. Second, we show how different tip selection algorithms affect the growth of the Tangle. Moreover, we explain these differences by analyzing the spread of exit probabilities of random walks. Our findings confirm analytically derived predictions and provide novel insights on the different phases of growth of cumulative weight as well as on the average time difference for a transaction to receive its first approval when using distinct tip selection algorithms. Lastly, we analyze simulation overhead and performance as a function of Tangle size and compare results for different tip selection algorithms.

Extracting Tangle Properties in Continuous Time via Large-Scale Simulations

Bartosz Kuśmierz, Philip Staupe and Alon Gal

Abstract

This paper analyzes fundamental properties of the Tangle. We use computer simulations to analyze cumulative weight evolution and tip count stability using a continuous-time model. As a byproduct of our analysis of average tip count we derive analytical formulas for the average number of tips in the discrete-time model. The paper also introduces and analyses the influence of a non-constant number of directly-approved transactions and scaling-invariance properties of the Tangle.

Probability of Being Left Behind and Probability of Becoming Permanent Tip

Bartosz Kuśmierz and Alon Gal

Abstract

We formalize, analyze and numerically estimate probability that given transaction will be left
behind and probability that transaction will become permanent tip. Analyzed data are gathered for different values of λ and α. As a byproduct of our study, we provide properties of probability of leaving behind in the limit case of parameters.

Local Modifiers in the Tangle

Serguei Popov

Abstract

As of today, there are many cryptocurrency systems around. They mostly share one common feature: all participants of the network interpret the same ledger in the same way. In this paper, we introduce the idea of local modifiers: the nodes of the network can interact with the ledger in different ways, depending on various kinds of information locally available to them. We then argue that such an approach permits to increase the security and the scalability of
the Tangle.

The first glance at the simulation of the Tangle: discrete model

Bartosz Kuśmierz

Abstract

In this paper we present preliminary results obtained with the computer simulation of the
Tangle - directed acyclic graph adapted for decentralized information storage. The first scalable, permissionless distributed ledger to use this technology is IOTA. IOTA protocol is designed for Internet of Things, Web 3.0 and other applicable sectors where the standard blockchain architecture comes up short. We examine basic properties of the Tangle, this include analysis of cumulative weight and stability of tips number, for different tip selection mechanisms.

The Security and Stability of the Tangle

Quentin Bramas

Abstract

In this paper we study the stability and the security of the Tangle, which is the distributed data structure at the base of the IOTA protocol. The contribution of this paper is twofold. Firstly we present simple model to analyze the Tangle and give the first formal analyzes of the average number of unconfirmed transactions and the average confirmation time of a transaction. Secondly we define the notion of assiduous honest majority that captures the fact that the honest nodes have more hashing power than the adversarial nodes and that all this hashing power is constantly used to create transactions. This notion is important because we prove that it is a necessary assumption to protect the Tangle against double-spending attacks, and this is true for any tip selection algorithm (which is a fundamental building blocks of the protocol) that verifies some reasonable assumptions. In particular, the same is true with the Markov Chain Monte Carlo selection tip algorithm currently used in the IOTA protocol. Our work shows that either all the honest nodes must constantly use all their hashing power to validate the main chain (similarly to the bitcoin protocol) or some kind of authority must be provided to avoid this kind of attack (like in the current version of the IOTA where a coordinator is used). The work presented here constitute a theoretical analysis and cannot be used to attack the current IOTA implementation. The goal of this paper is to present a formalization of the protocol and, as a starting point, to prove that some assumptions are necessary in order to defend the system again double-spending attacks. We hope that it will be used to improve the current protocol with a more formal approach.

How to Choose Its Parents in the Tangle

Vidal Attias and Quentin Bramas

Published in The International Conference on Networked Systems (NETYS 2019)

Abstract

The Tangle is a data structure mainly used to store transactions in the IOTA cryptocurrency. It has similarities with the blockchain structure of Bitcoin but in the Tangle, a block contains only one transaction and has not one, but two parents. The security and the stability of this distributed data structure is highly dependent on the algorithm used to select the parents of a new block. Previous work showed that the current parents selection algorithms are insecure, not stable or have low performances. And we propose a new algorithm that combines all these properties.

Quasi-Analytic Parasite Chain Absorption Probabilities in the Tangle

Philip Staupe

Abstract

We analyse with which probability the MCMC random walk gets absorbed into a parasite chain and underpin our arguments with simulation-based numerical results.

Improving the Anonymity of the IOTA Cryptocurrency

Laurence Tennant

Abstract

IOTA differentiates itself from other cryptocurrencies by being based on a non-blockchain data structure with a highly scalable approach to transaction confirmation. In addition, it exclusively uses post-quantum cryptography. However, as with most cryptocurrencies, IOTA’s ledger is currently completely transparent. Constructing an acceptable privacy solution within these parameters is a considerable challenge.
The report begins with a brief introduction to IOTA, followed by a general overview of privacy and anonymity in cryptocurrency. This leads to a review of methods currently used to enhance anonymity in other cryptocurrencies, and an assessment of their effectiveness and
applicability to IOTA.
Ultimately, off-ledger mixing using payment channels is found to be the most promising long-term privacy solution. In the meantime, centralised mixing forms a practical way to perform anonymity-enhanced transactions over the IOTA network, and can build a foundation for trustless solutions in future.

On the timestamps in the tangle

Serguei Popov

Parasite Chain Detection in the IOTA Protocol

Andreas Penzkofer, Bartosz Kuśmierz, Angelo Capossele, William Sanders and Olivia Saa

Published in Tokenomics, 2020.

Abstract

In recent years several distributed ledger technologies based on directed acyclic graphs (DAGs) have appeared on the market. Similar to blockchain technologies, DAG-based systems aim to build an immutable ledger and are faced with security concerns regarding the irreversibility of the ledger state. However, due to their more complex nature and recent popularity, the study of adversarial actions has received little attention so far. In this paper we are concerned with a particular type of attack on the IOTA cryptocurrency, more specifically a Parasite Chain attack that attempts to revert the history stored in the DAG structure, also called the Tangle.
In order to improve the security of the Tangle, we present a detection mechanism for this type of attack. In this mechanism, we embrace the complexity of the DAG structure by sampling certain aspects of it, more particularly the distribution of the number of approvers. We initially describe models that predict the distribution that should be expected for a Tangle without any malicious actors. We then introduce metrics that compare this reference distribution with the measured distribution. Upon detection, measures can then be taken to render the attack unsuccessful. We show that due to a form of the Parasite Chain that is different from the main Tangle it is possible to detect certain types of malicious chains. We also show that although the attacker may change the structure of the Parasite Chain to avoid detection, this is done so at a significant cost since the attack is rendered less efficient.

On the stability of unverified transactions in a DAG-based Distributed Ledger

Pietro Ferraro, Christopher King and Robert Shorten

Published in IEEE Transactions on Automatic Control, 2020.

Abstract

Directed Acylic Graphs (DAGs) are emerging as an attractive alternative to traditional blockchain architectures for distributed ledger technology (DLT). In particular DAG ledgers with stochastic attachment mechanisms potentially offer many advantages over blockchain, including scalability and faster trans- action speeds. However, the random nature of the attachment mechanism coupled with the requirement of protection against double-spending transactions might result in an unstable system in which not all transactions get eventually validated. Such transactions are said to be orphaned, and will never be validated. Our principal contribution is to propose a simple modification to the attachment mechanism for the Tangle (the IOTA DAG architecture). This modification ensures that all transactions are validated in finite time, and preserves essential features of the popular Monte-Carlo selection algorithm. In order to demonstrate these results we derive a fluid approximation for the Tangle (in the limit of infinite arrival rate) and prove that this fluid model exhibits the desired behavior. We also present simulations which validate the results for finite arrival rates.

Distributed Ledger Technology for Smart Mobility: Variable Delay Models

Andrew Cullen, Pietro Ferraro, Christopher King and Robert Shorten

Abstract

Recently, Directed Acyclic Graph (DAG) based Distributed Ledgers have been proposed for various applications in the smart mobility domain [1]. While many application studies have been described in the literature, an open problem in the DLT community concerns the lack of mathematical models describing their behaviour, and their validation. Building on a previous work in [1], we present, in this paper, a fluid based approximation for the IOTA Foundation DAG based DLT that incorporates varying transaction delays. This extension, namely the inclusion of varying delays, is important for feedback control applications (such as transactive control [2]). Extensive simulations are presented to illustrate the efficacy of our approach.

IOTA-based Directed Acyclic Graphs without Orphans

Pietro Ferraro, Christopher King and Robert Shorten

Abstract

Directed Acylic Graphs (DAGs) are emerging as an attractive alternative to traditional blockchain architectures for distributed ledger technology (DLT). In particular DAG ledgers with stochastic attachment mechanisms potentially offer many advantages over blockchain, including scalability and faster transaction speeds. However, the random nature of the attachment mechanism coupled with the requirement of protection against double-spend transactions leaves open the possibility that not all transactions will be eventually validated. Such transactions are said to be orphaned, and will never be validated. Our principal contribution is to propose a simple modification to the attachment mechanism for the Tangle (the IOTA DAG architecture). This modification ensures that all transactions are validated in finite time, and preserves essential features of the popular Monte-Carlo selection algorithm. In order to demonstrate these results we derive a fluid approximation for the Tangle (in the limit of infinite arrival rate) and prove that this fluid model exhibits the desired behavior. We also present simulations which validate the results for finite arrival rates.

Distributed Ledger Technology for IoT: Parasite Chain Attacks

Andrew Cullen, Pietro Ferraro, Christopher King and Robert Shorten

Abstract

Directed Acyclic Graph (DAG) based Distributed Ledgers can be useful in a number of applications in the IoT domain. A distributed ledger should serve as an immutable and irreversible record of transactions, however, a DAG structure is a more complicated mathematical object than its blockchain counterparts, and as a result, providing guarantees of immutability and irreversibility is more involved. In this paper, we analyse a commonly discussed attack scenario known as a parasite chain attack for the IOTA Foundation DAG based ledger. We analyse the efficacy of IOTA core MCMC algorithm using a matrix model and present an extension which improves the ledger resistance to these attacks.

Distributed Ledger Technology, Cyber-Physical Systems, and Social Compliance

Pietro Ferraro, Christopher King and Robert Shorten

Abstract

This paper describes how Distributed Ledger Technologies can be used to design a class of cyber-physical systems, as well as to enforce social contracts and to orchestrate the behaviour of agents trying to access a shared resource. The first part of the paper analyses the advantages and disadvantages of using Distributed Ledger Technologies architectures to implement certain control systems in an Internet of Things (IoT) setting, and then focuses on a specific type of DLT based on a Directed Acyclic Graph. In this setting we propose a set of delay differential equations to describe the dynamical behaviour of the Tangle, an IoT-inspired Directed Acyclic Graph designed for the cryptocurrency IOTA. The second part proposes an application of Distributed Ledger Technologies as a mechanism for dynamic deposit pricing, wherein the deposit of digital currency is used to orchestrate access to a network of shared resources. The pricing signal is used as a mechanism to enforce the desired level of compliance according to a predetermined set of rules. After presenting an illustrative example, we analyze the control system and provide sufficient conditions for the stability of the network.

Direct Acyclic Graph-based Ledger for Internet of Things: Performance and Security Analysis

Yixin Li, Bin Cao, Mugen Peng, Long Zhang, Lei Zhang, Daquan Feng and Jihong Yu

Published in IEEE Transactions on Networking, 2020.

Abstract

Abstract—Direct Acyclic Graph (DAG)-based ledger and the corresponding consensus algorithm has been identified as a promising technology for Internet of Things (IoT). Compared with Proof-of-Work (PoW) and Proof-of-Stake (PoS) that have been widely used in blockchain, the consensus mechanism de-signed on DAG structure (simply called as DAG consensus) can overcome some shortcomings such as high resource consump-
tion, high transaction fee, low transaction throughput and long confirmation delay. However, the theoretic analysis on the DAG consensus is an untapped venue to be explored. To this end, based on one of the most typical DAG consensuses, Tangle, we investigate the impact of network load on the performance and security of the DAG-based ledger. Considering unsteady network load, we first propose a Markov chain model to capture the behavior of DAG consensus process under dynamic load conditions. The key performance metrics, i.e., cumulative weight and confirmation delay are analysed based on the proposed
model. Then, we leverage a stochastic model to analyse the probability of a successful double-spending attack in different network load regimes. The results can provide an insightful understanding of DAG consensus process, e.g., how the network load affects the confirmation delay and the probability of a successful attack. Meanwhile, we also demonstrate the trade-off between security level and confirmation delay, which can act as a guidance for practical deployment of DAG-based ledgers.

Contact us

Let's start a conversation.

*
*
*