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.

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.

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.

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.

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.

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.

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.

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.

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.

Distributed Ledger Technologies (DLTs) (the agnostic term for blockchain) are a potential solution for many pressing issues arising in the Internet of Things (IoT) domain. These issues include facilitating secure transactions between IoT devices and immutably recording data. Most DLT architectures were not designed with IoT in mind and consequentially do not satisfy the requirements of many IoT applications. However, the relatively new class of Directed Acyclic Graph (DAG) based DLTs show great promise for IoT networks. These DLTs require the rate at which transactions are issued and disseminated to be explicitly managed in order to ensure fairness among users. We present a congestion control algorithm for these DLTs, which optimises dissemination rate and guarantees that all nodes receive the same information and have fair access even in a dishonest environment, subject to the computing limitations of nodes. Our algorithm takes inspiration from well-known areas of networking research, such as QoS, and TCP. However, an important distinction between the DLT setting and traditional networks is the unique nature of traffic in DLT networks and the fact that nodes cannot trust familiar feedback measurements, such as packet acknowledgements or congestion notifications. Our solution realises a decentralised congestion control algorithm for DLTs without the need for trust among nodes.

Permissionless distributed ledgers provide a promising approach to deal with the Internet of Things (IoT) paradigm. Since IoT devices mostly generate data transactions and micropayments, distributed ledgers that use fees to regulate the network access are not an optimal choice. In this paper, we study a feeless architecture developed by IOTA and designed specifically for the IoT. Due to the lack of fees, malicious nodes can exploit this feature to generate an unbounded number of transactions and perform a denial of service attacks. We propose to mitigate these attacks through verifiable delay functions. These functions, which are non-parallelizable, hard to compute, and easy to verify, have been formulated only recently. In our work, we design a denial of service prevention mechanism which addresses network heterogeneity, limited node computational capabilities, and hardware-specific implementation optimizations. Verifiable delay functions have mostly been studied from a theoretical point of view, but little has been done in tangible applications. Hence, this paper can be considered as a pioneer work in the field, since it builds a bridge between this theoretical mathematical framework and a real-world problem.

We introduce a permissioned distributed ledger technology (DLT) design for crowdsourced smart mobility applications. This architecture is based on a directed acyclic graph architecture (similar to the IOTA tangle) and uses both Proof-of-Work and Proof-of-Position mechanisms to provide protection against spam attacks and malevolent actors. In addition to enabling individuals to retain ownership of their data and to monetize it, the architecture is also suitable for distributed privacy-preserving machine learning algorithms, is lightweight, and can be implemented in simple internet-of-things (IoT) devices. To demonstrate its efficacy, we apply this framework to reinforcement learning settings where a third party is interested in acquiring information from agents. In particular, one may be interested in sampling an unknown vehicular traffic flow in a city, using a DLT-type architecture and without perturbing the density, with the idea of realizing a set of virtual tokens as surrogates of real vehicles to explore geographical areas of interest. These tokens, whose authenticated position determines write access to the ledger, are thus used to emulate the probing actions of commanded (real) vehicles on a given planned route by ``jumping'' from a passing-by vehicle to another to complete the planned trajectory. Consequently, the environment stays unaffected (i.e., the autonomy of participating vehicles is not influenced by the algorithm), regardless of the number of emitted tokens. The design of such a DLT architecture is presented, and numerical results from large-scale simulations are provided to validate the proposed approach.

The link between transport related emissions and human health is a major issue for municipalities worldwide and one of the main challenges to address in the context of Smart Cities. Specifically, Particulate Matter (PM) emissions from exhaust and non-exhaust sources are one of the main worrying contributors to air-pollution. In this paper, we challenge the notion that a ban on internal combustion engine vehicles will result in clean and safe air in our cities, since emissions from tyres and other non-exhaust sources are expected to increase in the near future. We support this claim through simple calculations, based on publicly available data from the city of Dublin, and we present a high level solution to this problem, in the form of a control mechanism and ride-sharing scheme to limit the number of vehicles and therefore maintain the amount of transport-related PM to safe levels. Thanks to the use of Distributed Ledger Technology our proposal is entirely distributed, fair and privacy preserving, which makes it ideal for application in the Smart City domain.

Voting algorithms have been widely used as consensus protocols in the realization of fault-tolerant systems. These algorithms are best suited for distributed systems of nodes with low computational power or heterogeneous networks, where different nodes may have different levels of reputation or weight. Our main contribution is the construction of a fair voting protocol in the sense that the influence of the eventual outcome of a given participant is linear in its weight. Specifically, the fairness property guarantees that any node can actively participate in the consensus finding even with low resources or weight. We investigate effects that may arise from weighted voting, such as loss of anonymity, centralization, scalability, and discuss their relevance to protocol design and implementation.

The basic idea of voting protocols is that nodes query a sample of other nodes and adjust their own opinion throughout several rounds based on the proportion of the sampled opinions. In the classic model, it is assumed that all nodes have the same weight. We study voting protocols for heterogeneous weights with respect to fairness. A voting protocol is fair if the influence on the eventual outcome of a given participant is linear in its weight. Previous work used sampling with replacement to construct a fair voting scheme. However, it was shown that using greedy sampling, i.e., sampling with replacement until a given number of distinct elements is chosen, turns out to be more robust and performant. In this paper, we study fairness of voting protocols with greedy sampling and propose a voting scheme that is asymptotically fair for a broad class of weight distributions. We complement our theoretical findings with numerical results and present several open questions and conjectures.

In this paper, we propose several solutions to the committee selection problem among participants of a DAG distributed ledger. Our methods are based on a ledger intrinsic reputation model that serves as a selection criterion. The main difficulty arises from the fact that the DAG ledger is a priori not totally ordered and that the participants need to reach a consensus on participants' reputation. Furthermore, we outline applications of the proposed protocols, including: (i) self-contained decentralized random number beacon; (ii) selection of oracles in smart contracts; (iii) applications in consensus protocols and sharding solutions. We conclude with a discussion on the security and liveness of the proposed protocols by modeling reputation with a Zipf law.