<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Sebastian Mueller on Medium]]></title>
        <description><![CDATA[Stories by Sebastian Mueller on Medium]]></description>
        <link>https://medium.com/@naitsabesMue?source=rss-221b6b48653a------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*k7dsedATD_IqsLkBH3CHAw.png</url>
            <title>Stories by Sebastian Mueller on Medium</title>
            <link>https://medium.com/@naitsabesMue?source=rss-221b6b48653a------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 03:30:13 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@naitsabesMue/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Simulation study of FPC]]></title>
            <link>https://medium.com/@naitsabesMue/simulation-study-of-fpc-5b9e8b5a6910?source=rss-221b6b48653a------2</link>
            <guid isPermaLink="false">https://medium.com/p/5b9e8b5a6910</guid>
            <category><![CDATA[research-and-development]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[distributed-ledgers]]></category>
            <category><![CDATA[consensus]]></category>
            <category><![CDATA[iota]]></category>
            <dc:creator><![CDATA[Sebastian Mueller]]></dc:creator>
            <pubDate>Fri, 22 Nov 2019 13:08:26 GMT</pubDate>
            <atom:updated>2019-11-22T13:08:26.651Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_v8Cb6VJjfjLsZKaWo_3-w.png" /></figure><p>The IOTA Research Department recently published the <a href="https://blog.iota.org/the-fast-probabilistic-consensus-simulator-d5963c558b6e">Fast Probabilistic Consensus Simulator</a>.</p><p>Today, we are excited to share with you the corresponding research paper on <a href="https://arxiv.org/abs/1911.08787">arxiv</a> that studies various properties of the <a href="https://arxiv.org/pdf/1905.10895.pdf">FPC</a>. We invite you to take a look at this research paper. We also want to give you a short overview of what kind of results we have obtained.</p><p>The abstract tells us:</p><blockquote>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. <strong>We identify the optimal amount of randomness for various Byzantine attack strategies on different kinds of network topologies.</strong></blockquote><p>Let’s see what all these “fancy” terms mean. In the current IOTA tangle consensus is achieved by the coordinator. One core module of C<a href="https://coordicide.iota.org/">oordicide</a> is FPC, a distributed <a href="https://en.wikipedia.org/wiki/Consensus_(computer_science)">consensus protocol</a><em>. </em>Distributed consensus protocols allow networked systems to agree on a common opinion in situations in which centralized decision making is difficult, impossible or unwanted.</p><p>As distributed computing is inherently unreliable, it is necessary to reach consensus in noisy or <a href="https://en.wikipedia.org/wiki/Byzantine_fault">Byzantine</a> infrastructures. The latter is equivalent to the presence of malicious nodes that try to attack the protocol. The word noisy refers to nodes that may be faulty or to possible message loss.</p><p>The FPC is leaderless since it does not require a (elected) leader. An advantage of this is that every node can update its opinion locally without having to wait for the coordination of the leader. In FPC every node queries a <a href="https://en.wikipedia.org/wiki/Simple_random_sample">random sample</a> of other nodes and adopts the opinion of the majority. In the basic version there are only two possible opinions so we speak of binary majority consensus.</p><p>Previous protocols in the class of leaderless binary majority consensus protocols are: the simple majority consensus and the random majority consensus.</p><p>These protocols, however, can rarely guarantee the eventual agreement of the nodes in Byzantine infrastructure. For this reason, FPC proposes an additional randomness that serves as “<a href="https://en.wikipedia.org/wiki/Fog_of_war">fog of war</a>” for potential malicious attackers, making it at best impossible for the attacker to effectively influence the honest nodes.</p><p>The additional randomness is the key element that allows overcoming Byzantine failure. The randomness is parameterized by a parameter β; the larger β the less random the protocol. One main interest was to identify the β’s that allow the maximal proportion of adversary nodes. In the following graph, we plot the agreement rate as a function of β and the proportion of adversary nodes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/617/0*i0hBAZGkN0u7EfAv" /></figure><p>An agreement rate of 1 means that in 100% of the simulations all honest nodes eventually shared the same opinion. An agreement rate of 0.9 signifies that in 90% of the simulations all honest nodes had the same opinion and that in 10% of the cases at least two honest nodes terminated the protocol with different opinions. We see that, in the above situation, the protocol with β=0.3 allows the highest proportion of adversary nodes.</p><p>Our focus lies in the performances of the FPC in Byzantine infrastructures. For this purpose, we propose explicit adversarial strategies, which either target the integrity of the resulting opinion, the agreement of the nodes on the opinion, or the termination of the protocol altogether. Some of these strategies are also described in<a href="https://blog.iota.org/consensus-in-the-iota-tangle-fpc-b98e0f1e8fa"> Consensus in the iota tangle — FPC</a>. The performances are measured using integrity rate, agreement rate, and termination rate.</p><p>Moreover, we investigated the dynamics of the protocol during an attack. The next graph shows the evolution of undecided nodes under several attack scenarios. We see in a) that the FPC is robust against certain malicious attackers even without the additional randomness (β=0.5). To overcome Berserk attackers, however, the additional randomness is crucial, as the comparison of b) and c) shows.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*P2FBykAmga_F4iJL" /></figure><p>In the <a href="https://arxiv.org/pdf/1905.10895.pdf">FPC paper</a>, it is assumed that every node has a complete view of the network. We weaken this assumption in considering several <a href="https://en.wikipedia.org/wiki/Network_topology">network topologies</a> and analyze how the lack of complete knowledge about all other nodes affects the ability to reach consensus. You may also take a look at the previous post <a href="https://blog.iota.org/the-fast-probabilistic-consensus-simulator-d5963c558b6e">Fast Probabilistic Consensus Simulator</a> for more details.</p><p>One of our main results is, therefore, well summarized in the last sentence of the abstract:</p><blockquote><strong><em>We identify the optimal amount of randomness for various Byzantine attack strategies on different kinds of network topologies.</em></strong></blockquote><p>As always, we welcome your comments and questions either here in the comments, in #tanglemath on our <a href="https://discord.iota.org/">Discord server</a>, or in the <a href="https://iota.cafe/">IOTA.cafe</a>. You can also engage in more intense scientific collaborations with us and apply for a <a href="https://coordicide.iota.org/grants">grant</a>.</p><p><strong>The author is not a member of the IOTA foundation. He wrote this blog post in collaboration with the members of the IOTA research group.</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5b9e8b5a6910" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Consensus in the IOTA Tangle — FPC]]></title>
            <link>https://medium.com/@naitsabesMue/consensus-in-the-iota-tangle-fpc-b98e0f1e8fa?source=rss-221b6b48653a------2</link>
            <guid isPermaLink="false">https://medium.com/p/b98e0f1e8fa</guid>
            <category><![CDATA[consensus]]></category>
            <category><![CDATA[distributed-ledgers]]></category>
            <category><![CDATA[iota]]></category>
            <category><![CDATA[research-and-development]]></category>
            <category><![CDATA[iot]]></category>
            <dc:creator><![CDATA[Sebastian Mueller]]></dc:creator>
            <pubDate>Tue, 20 Aug 2019 13:24:42 GMT</pubDate>
            <atom:updated>2019-08-20T13:24:42.384Z</atom:updated>
            <content:encoded><![CDATA[<h3>Consensus in the IOTA Tangle — FPC</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*v3uFfw2Egx0M8prAvvW1YA.png" /></figure><p>This is the first in a series of posts that explain the consensus protocols described in IOTA<a href="https://coordicide.iota.org/"> Coordicide</a>.</p><p>The main objective of this series is to keep the community updated on recent research results and also to explain interesting research questions having good chances to be funded by<a href="https://blog.iota.org/iota-announces-5-million-in-grants-for-coordicide-related-research-e586547cc948"> Coordicide grants</a>. As you will see, the topic is quite vast and there are a lot of connections and dependencies on other parts of the Coordicide project.</p><p>Faced with this complexity, we’ll try to explain only a few points at a time and focus on questions that are currently being researched. That said, let us note that IOTA already has all the key ingredients for an efficient and secure solution for Coordicide.</p><p>The remaining questions are about optimality of the solution, for instance:</p><ol><li>Increasing safety</li><li>Increasing sustainability (e.g. decreasing message complexity, decreasing PoW)</li><li>Increasing TPS</li><li>Decreasing time to finality</li><li>Increasing the flexibility of the implementation for challenges in the future</li></ol><p>Now, let’s get down to it and understand what this “consensus” is all about.</p><p><strong>Why consensus?</strong></p><p>Distributed consensus algorithms allow networked systems to agree on a required state or opinion in situations in which decentralized decision making is difficult or even impossible.</p><p>Distributed computing is inherently unreliable. Achieving consensus enables a distributed system to work as one entity. The importance of this challenge stems from its omnipresence in which fault tolerance is one of the most fundamental aspects.</p><p>Common examples include: replicated file systems, clock synchronization, resource allocation, task scheduling and last, but not least, distributed ledgers.</p><p>Distributed systems form a vast and classic topic in computer science and the same is true for associated consensus protocols: see <a href="https://medium.com/s/story/lets-take-a-crack-at-understanding-distributed-consensus-dad23d0dc95">How does distributed consensus work</a> for an elegant introduction to this topic.</p><p>The existing consensus protocols are essentially the classical protocols — e.g. those based on PAXOS — and the recent game-changer:<strong> </strong>the Nakamoto consensus. Both protocols have serious restrictions.</p><p>The classical protocols have quadratic message complexity, they require precise membership knowledge and are rather fragile against disturbances. The Nakamoto protocol, on the other hand, is robust and does not require precise memberships. However, it relies on PoW, leading to well-known problems such as mining races and non-scalability.</p><p><strong>So how is consensus achieved in the IOTA Tangle?</strong></p><p>Let us first look back at the Nakamoto consensus. One brilliant idea of the Nakamoto consensus is to make the consensus non-deterministic or probabilistic. Instead of all nodes of the (distributed) system agreeing on the correctness of a value, they agree on the “probability” of that value being correct.</p><p>The role of the leader in traditional consensus protocols is taken by the node that solves a given computational puzzle the fastest; this winner adds a new block to the blockchain. This way, the (distributed) network is building the ever-growing blockchain and agrees on the validity of the longest chain or the chain with most cumulative difficulty.</p><p>So why is this consensus probabilistic? In order to know that a certain transaction will be considered valid, in say 100 days, we have to know that the longest chain in 100 days will contain this given transaction.</p><p>In other words, we are interested in the probability that the longest chain in 100 days will contain this transaction. The probability that a transaction will not be reverted increases as the block which contains this transaction sinks “deeper” into the chain.</p><p>In the bitcoin blockchain, for example, it is recommended to wait until a transaction is six blocks deep in the blockchain. After this depth, the probability that a transaction is reverted is very low.</p><p>This effect also applies to the Tangle. The deeper — or more “enveloped” by the Tangle — a transaction gets the more final it becomes. In the following picture, the dark green transaction is validated by all light green transactions. As the number of light green transactions grows, the probability of the dark green transaction being in the future Tangle converges to 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/753/1*px68VKz5EbcWikOxHFyyCw.png" /></figure><p>But wait, <strong>the Tangle is different to a blockchain!</strong> While the blockchain is not allowed to contain two conflicting transactions, the Tangle may temporarily contain such transactions. Therefore, it may be that a malicious player attaches two conflicting transactions at different parts of the Tangle, like the dark green and the orange squares in the above picture.</p><p>These transactions may “survive” in the Tangle for a short time until honest nodes detect the conflict. Once such a conflict is detected, the nodes decide on which transaction to choose. In the example above, the darker green transaction is “more enveloped” by the Tangle and should eventually be approved by all nodes.</p><p>For the Tangle to become a real consensus protocol we have to decide on conflicting transactions. That decision should be taken by using a consensus protocol.</p><p>Did we walk in circles here?? Fortunately no: Coordicide proposes two other consensus protocols:</p><ul><li>the<a href="https://coordicide.iota.org/module5.1.2"> fast probabilistic consensus</a> (FPC) and</li><li>the<a href="https://coordicide.iota.org/module5.1.1"> cellular consensus</a> (CC)</li></ul><p>The rest of this post will be devoted to a short introduction to FPC and to explain how to reach consensus when it comes to deciding whether a single transaction is valid or not.</p><p>In a future blog post, we will address why this is sufficient in order to reach consensus on Tangle level and we will discuss the finality of transactions in the Tangle.</p><p><strong>What is FPC?</strong></p><p>In fancy terms, the FPC is a leaderless probabilistic binary consensus protocol of low communicational complexity that is robust in a Byzantine infrastructure — check the original <a href="https://arxiv.org/abs/1905.10895">article</a> by<a href="https://medium.com/@serguei.popov"> Serguei Popov</a> and<a href="https://medium.com/@billatnapier"> Bill Buchanan</a>.</p><p>Let us see, as we proceed what all these terms really mean and start by presenting a lighter version of the FPC that is easy to implement and contains most of the important features.</p><p>We assume the network to have <em>n </em>nodes indexed by <em>1,2,…,n</em>. Every node <em>i </em>has an opinion or state. We denote <em>s_i(t)</em> for the opinion of the node <em>i </em>at time <em>t. </em>Opinions take value in <em>{0,1}</em>; being the reason we speak of a binary consensus.</p><p>The basic idea is majority voting. At every round, every node queries <em>k</em> random nodes and sets its opinion equal to the majority of the queried nodes. Simple as that! However, this simple majority voting turns out to be fragile against faulty nodes and malicious attackers. It needs an additional ingredient, in fact an additional randomness, to make it robust.</p><p>More formally, at each step, each node chooses <em>k</em> random nodes <em>C_i</em>, queries their opinions and calculates the mean opinion</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/199/0*LAiG55HlrkbCsdo-" /></figure><p>We denote <em>𝝉 ∊ [0,1]</em> the first threshold that allows some asymmetric nature of the protocol, another topic we’ll address in the near future. Furthermore, we introduce an “additional randomness”; let <em>U_{t}, i=1, 2,…</em> be <a href="https://en.wikipedia.org/wiki/Independent_and_identically_distributed_random_variables">i.i.d. random variables</a> with law <a href="https://en.wikipedia.org/wiki/Uniform_distribution_(continuous)"><em>Unif</em></a><em>(𝜷, 1- 𝜷)</em> for some parameter <em>𝜷 ∊ [0,1/2]</em>.</p><p>At each time, each node <em>i</em> uses the opinions from <em>k</em> random nodes to update its own opinion:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/226/0*VvlDKtlJmLa-RjKG" /></figure><p>and for<em> t&gt;0</em>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/292/0*m5xImloJCX-sq6v9" /></figure><p>It is important that at each round a node queries a different random set of nodes and that the random variables <em>U_t</em> are updated in each round as well.</p><p>We introduce a local termination rule to reduce the communication complexity of the protocol. Every node keeps a counter variable <em>cnt</em> that is incremented by <em>1</em> if there is no change in its opinion and that is set to <em>0</em> if there is a change of opinion.</p><p>Once the counter reaches a certain threshold <em>l</em>, i.e. <em>cnt≥1</em>, the node considers the current state as final. The node will therefore no longer send any queries, but will still answer incoming queries. The next graphs show typical evolutions of the variable <em>cnt</em> for each node with <em>l=5, k=10</em> and initial opinions of 90% of <em>1</em>`s and 10% of <em>0</em>`s.</p><p>In the left picture the protocol is not disturbed, but in the right picture 20% of the nodes are maliciously trying to turn the majority of the honest nodes. In both cases, eventually all honest nodes agree on the initial majority.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*X4xPOSIF97NGVsae" /></figure><p>We want to highlight the feature of the common random thresholds of the FPC and refer to <a href="http://datatreker.com/simulations-of-the-fast-probabilistic-consensus-protocol-fpc">Simulation of the FPC</a> for a first analysis of the FPC for various different kinds of parameter settings and attack strategies.</p><h3>Effect of the random thresholds</h3><p>The importance of uncertainty in war was introduced by Carl von Clausewitz:</p><blockquote><em>War is the realm of uncertainty; three quarters of the factors on which action in war is based are wrapped in a fog of greater or lesser uncertainty. A sensitive and discriminating judgment is called for; a skilled intelligence to scent out the truth.</em></blockquote><p><em>- Carl von Clausewitz, 1873</em></p><p>What does this have to do with the random thresholds in the FPC? In simple majority, voting these thresholds would just be equal to<em> 0.5</em>. A fruitful attack strategy could be to keep the <em>η’</em>s of the honest nodes around <em>0.5</em> preventing a convergence of the protocol (we will see such a successful attack later on). The idea of Popov and Buchanan was to add “noise” or “fog” to the system to increase the uncertainty of information for the potential attackers.</p><p>Why is all of this important? In a situation without malicious nodes, the distribution of the <em>η</em>’s will be close to a normal distribution:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*f8wE-z5XTKGQuy21toJ6nQ.png" /></figure><p>Already in a non-disturbed situation, the opinions of the honest nodes can stay close to a 50:50 situations. However, random effects, caused by the random voting, finally lead to convergence of the protocol. This situation is completely different in a Byzantine infrastructure.</p><p>Let’s consider an adversary strategy that subdivides the honest nodes into two equally sized groups of different opinions leading to a distribution of the <em>η</em>’s among honest nodes like:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*IGGs7Xz91a--N_7DR6-3zg.png" /></figure><p>So how can an adversary achieve this?</p><p>The adversary waits until all honest nodes have received opinions from all other honest nodes. The adversary then calculates the <a href="https://en.wikipedia.org/wiki/Median">median</a> of these intermediate <em>η’s</em>. Now, the adversary tries to keep the median of the <em>η</em>’s close to <em>0.5</em> by trying to maximize the variances of the <em>η’</em>s.</p><p>How can the FPC prevent such an attack? By replacing the deterministic threshold (red, dashed) by random thresholds (blue, dashed). In the following graph, each blue line stands for a random threshold of a given round. As these thresholds are random the adversary cannot foresee how to split the honest nodes in order to keep the 50:50 situation. The best way is to still split them around the value <em>0.5</em>.</p><p>However, once a blue line (in r3 in the picture below) is far enough away from the red line, the adversary loses control of the honest nodes and the protocol terminates.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*QvQRaZLIm1eu4aOUwQnpUw.png" /></figure><p>In the following animation you can see the behaviour and outcome of the protocol when this adversarial strategy is applied with no randomness (<em>threshold=0.5</em>) and after the randomness is added. As you can see, the adversary manages to keep the nodes in limbo for an extensive amount of time. But even worse, the network is split in its opinion — leading to an agreement failure. However, after the additional randomness is introduced, the protocol concludes quickly and in unity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*6EbVUhKo6YJrMl5YzzOdZQ.gif" /></figure><p><strong>Ongoing work and next steps</strong></p><p>Last — but not least — let’s come back to some of the points IOTA is currently working on and point out some examples of future collaborations:</p><ol><li>At the moment we are running thorough <strong>simulations to study various attack strategies on different kinds of network topologies</strong>. The results will allow us to identify the optimal amount of randomness and choice of the protocol parameters. We are also investigating robustness of the FPC against failures and disturbances of the random threshold.</li><li>The <strong>bounds on the convergence of the FPC</strong> obtained in simulations are far better than the ones obtained theoretically by Popov and Buchanan. Various parameter setting simulations <a href="http://datatreker.com/simulations-of-the-fast-probabilistic-consensus-protocol-fpc">show</a> that there is a so-called<a href="https://www.pnas.org/content/pnas/93/4/1659.full.pdf"> “cut off phenomenon”</a>. Informally, this essentially means that the protocol needs, say <em>m </em>steps, with high probability to reach consensus and that it is very unlikely that the protocol needs more than <em>m </em>steps. Theoretical results in this direction would be much appreciated.</li><li>The actual implementation of the FPC will depend on the <strong>reputation of the nodes</strong>. As the reputation or mana of the node plays a prominent part in other parts of the Coordicide project, we will write more about this in a future blog post. Anyway, this additional feature will make the protocol safer against various kinds of attacks.</li><li>The parameters studied above in the FPC were set in stone at the beginning of the protocol. However, in order to increase safety and, at the same time, reduce message complexity (which sounds like a miracle), we are investigating <strong>adapted versions of the FPC</strong>. For instance, if a node’s <em>η </em>is close to<em> 0.5</em>, the node might decide to increase the number of queries while, if it is close to <em>1</em>, it may decide to either reduce the number of queries of the next step or immediately stop querying at all.</li><li>Nowadays, machine learning is adopted in a wide range of domains where it shows its superiority over traditional rule-based algorithms. We are planning to use <strong>machine learning</strong>, not only for the detection of faulty and malicious nodes, but also to identify the most harmful attack strategies using reinforcement learning.</li></ol><p>We look forward to taking you with us on the exciting journey of Coordicide through the eyes of the research department and we hope you will enjoy the development on this project as we do.</p><p>As always, we welcome your comments and questions either here in the comments or in #tanglemath on our Discord. You can also engage in a more intense scientific collaborations with us and apply for a <a href="https://coordicide.iota.org/grants">grant</a>.</p><p><strong>The author is not a member of the IOTA foundation. He wrote this blogpost in collaboration with the members of the IOTA research group.</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b98e0f1e8fa" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>