<?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 Trafim Lasy on Medium]]></title>
        <description><![CDATA[Stories by Trafim Lasy on Medium]]></description>
        <link>https://medium.com/@trafim.lasy?source=rss-755bf49f260f------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*zbsm_nBsmntj4UTkyDyz2g.png</url>
            <title>Stories by Trafim Lasy on Medium</title>
            <link>https://medium.com/@trafim.lasy?source=rss-755bf49f260f------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 23:53:58 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@trafim.lasy/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[Enhancing Hashgraph Consensus]]></title>
            <link>https://medium.com/@trafim.lasy/enhancing-hashgraph-consensus-85739614bbcb?source=rss-755bf49f260f------2</link>
            <guid isPermaLink="false">https://medium.com/p/85739614bbcb</guid>
            <category><![CDATA[proof-of-stake]]></category>
            <category><![CDATA[consensus]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[hashgraph]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Trafim Lasy]]></dc:creator>
            <pubDate>Fri, 13 Dec 2019 15:24:18 GMT</pubDate>
            <atom:updated>2019-12-13T15:24:18.357Z</atom:updated>
            <content:encoded><![CDATA[<h4>Starting from Hashgraph consensus a family of atomic broadcast algorithms is constructed</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/970/1*YdVvgtGhxGkU2aQYV8dang.jpeg" /><figcaption>Image by <a href="https://freerangestock.com/photographer/Jack-Moreh/2728">Jack Moreh</a> via <a href="http://thestocks.im/">thestocks</a></figcaption></figure><h3>Introduction</h3><p>Around the end of 2017 during the crypto hype peak an <a href="https://blog.springrole.com/what-is-hashgraph-is-it-the-blockchain-killer-3fabc603211">article</a> caught my eye. The author discussed whether Hashgraph consensus algorithm, described there, was the “Blockchain Killer” or not. Being intrigued by this article I quickly found a <a href="https://www.swirlds.com/downloads/SWIRLDS-TR-2016-02.pdf">good introduction</a> to Hashgraph consensus written by its creator Leemon Baird. After reading it I was fascinated by the simplicity, power and beauty of the algorithm.</p><p>One of emphasized Hashgraph consensus features was its speed. After emotions faded, being a mathematician, I started to ask questions like whether mathematical model behind Hashgraph algorithm was the best one in terms of speed and safety.</p><ul><li><strong>Safety is OK</strong>. The algorithm deals with N nodes and assumes that not more than ⅓ of them can be malicious. And this is well-known theoretical bound for asynchronous byzantine fault tolerant algorithms which Hashgraph consensus is a particular case.</li><li><strong>Speed is questionable</strong>. Hashgraph consensus is presented “as is’’ without demystifying why certain design choices were made.</li></ul><p>My questions and curiosity motivated me to deeply dive into the classic theory of distributed algorithms. During this journey I managed to answer most of my questions concerning Hashgraph consensus. Linking this algorithm to classic results I found that this consensus algorithm could be generalized and enhanced. This generalization is represented by a family of <a href="https://en.wikipedia.org/wiki/Atomic_broadcast">atomic broadcast</a> algorithms. I call it <strong>BVC Family</strong>. The most important thing is that some of its members appear to be almost <strong>1.5x times faster</strong> than Hashgraph consensus, as experiments have shown.</p><blockquote>I decided to describe my results as a mathematical article (<a href="https://arxiv.org/abs/1912.05895">arxiv link here</a>). Of course, as any such work, it contains lots of formal definitions and mathematical proofs and can be hard to read for anyone without math background :( And this is despite several beautiful images I added to facilitate understanding!</blockquote><p>The goal of this medium publication is to try to overcome this issue. I will briefly remind what Hashgraph consensus is and describe some notable members of BVC algorithm family.</p><h3>Hashgraph Consensus</h3><p>Here I won’t completely redo the nice introductory work done by Leemon Baird and strongly suggest the reader to at least scroll through the already mentioned <a href="https://www.swirlds.com/downloads/SWIRLDS-TR-2016-02.pdf">Hashgraph consensus presentation</a>. But I still need some definitions to continue..</p><p>In short, a family of nodes in a network exchange data (gossip to each other) and create events bearing transactions or any other useful information. These nodes want to reach a consensus on the total order of these events. Such a system of nodes can be used, for example, as a basis of distributed database or file storage. Hashgraph consensus (as any other BFT atomic broadcast algorithm) allows them to accomplish that even if part of these nodes are malicious and can do coordinated attack on the rest of the nodes in order to interrupt the correct work of the whole system.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/0*d1G0nREnHesk-bO2" /><figcaption>An example of gossip exchange scenario with 4 nodes. Circles represent events, arrows — gossips (or “parent” relation). Each vertical sequence of events consists of events by the same node and can be considered as node itself. We use color notation similar to that of <a href="https://www.swirlds.com/downloads/SWIRLDS-TR-2016-02.pdf">Hashgraph consensus examples</a>: light orange are witnesses with undecided fame; light green — famous witnesses, light gray — other events; darker colors mean that an event was added to the total order; last event is marked with purple color for convenience. One can check that an event is next round witness if it strongly sees 3 or more previous round witnesses.</figcaption></figure><p>The key notions presented on the image above are:</p><ul><li><strong>Event</strong>. Each node creates an event when it receives a gossip from another node with new information. This event contains the hashes of the last events of both sending and receiving gossip nodes (these events can be considered as event parents).</li><li><strong>Hashgraph</strong>. The events and the parent relation form a directed graph called Hashgraph. It plays a crucial role in Hashgraph consensus. Consensus is reached using mostly this graph structure. The image above can be considered as a particular case of hashgraph.</li><li><strong>Round</strong>. <strong>Witness. </strong>These notions can be considered as a way to synchronize and simplify asynchronous distributed system of nodes. Rounds are built inductively: next round events (or witnesses) are the earliest events which “strongly see” more than ⅔ previous round witnesses. Roughly, one event “strongly sees” another if downward paths from the first event to the second one pass through ⅔ nodes.</li><li><strong>Being famous</strong>. Not all witnesses can be seen by the majority of nodes. Some nodes can be malicious, slow, DDOSsed, or just crash. And to add an event to the consistent total order one has to ensure that this event will be known to each active node eventually. This requirement is the motivation for the following definition: a witness is famous if the hashgraph structure shows that most nodes received it fairly soon after it was created. And this is done through voting.</li><li><strong>Voting</strong>. Voting can be identified with BFT <a href="https://en.wikipedia.org/wiki/Consensus_(computer_science)#Binary_consensus">binary consensus</a> for whether a witness is famous or not. For a given round witness voting starts by checking whether next round witnesses “see” (roughly, there’s a downward path) it or not. If they see the vote is “YES” and “NO” otherwise. After next round witnesses, greater by two round witnesses start to vote by majority rule, and so on. We finish voting when some witness sees more than ⅔ witnesses with the same vote. This is when hashgraph tells us that we can decide on witness fame.</li><li><strong>Adding to total order</strong>. Having defined famous witnesses the procedure of totally ordering them is as follows: as soon as the next consecutive round witnesses have all their fame decided, the set of events seen by ALL famous witnesses of that round is ordered using timestamps and added to the total order. And this order is proven to be consistent among the nodes.</li></ul><p>Now we are ready to see how Hashgraph consensus can be generalized and enhanced.</p><h3>Generalizing and Enhancing</h3><p>I’ll explain things in a simplified form. Full details on Hashgraph consensus generalization and enhancement can be found in Section 3 of the already mentioned <a href="https://arxiv.org/abs/1912.05895">mathematical article</a> which I’ll further refer to as “main article”.</p><p>As one can see on the image above, same round witness sets can be regarded as consecutive event layers. This was the starting generalization point. It turned out that:</p><ul><li>Witness layers can be generalized to quite rich family of event layers, which I call <strong>base layers.</strong></li><li>Next layer witnesses, which vote for witness fame, can also be replaced by certain event layers, called <strong>voting layers</strong>.</li><li>Finally, binary BFT consensuses behind fame voting can also be tweaked in order to be more effective. They are built on layers, which I call <strong>consensus layers</strong>.</li></ul><p>It is <strong>base, voting </strong>and<strong> consensus </strong>words who gave rise to the algorithm <strong>BVC</strong> <strong>Family</strong> name. Of course the above layers cannot be arbitrarily in order to keep all the nice properties of atomic broadcast algorithms. They must satisfy certain “appropriateness” property, which ensures that:</p><ul><li>all honest nodes will have consistent layers</li><li>every event seen by enough number of nodes will be eventually added to the consistent total event order.</li></ul><p>The above layers not only generalize Hashgraph consensus but also give rise to some algorithms which can be considered as its enhancements. We provide one of them (more examples can be seen in the <a href="https://arxiv.org/abs/1912.05895">main article</a>):</p><ul><li>Base layers are constructed not as the earliest events which “strongly see” more than ⅔ of previous base layer events but those that just follow by downward paths in hashgraph more that ⅔ of previous base layer events. Of course, this is less strict condition and such base layers appear more often than witnesses (compare left and right witness creations on the comparative image below).</li><li>We also allow event to be in several consecutive base layers. E.g. on the right part of the image below an event belongs to both 5th and 6th base layers (this is marked as “5–6” tag).</li><li>Voting layer is constructed above base layers similarly to Hashgraph consensus: more than ⅔ of previous base layer should be “strongly seen” in order to be in voting layer.</li><li>Consensus layers are analogous to Hashgraph consensus voting, but more tied to the classical Bracha-Toueg results (details in the <a href="https://arxiv.org/abs/1912.05895">main article</a>).</li><li>Very important thing concerns adding to the total order. We add an event to the total order if it is followed by <strong>ANY</strong> of the famous events, and not necessarily by <strong>ALL</strong> of them as in Hashgraph consensus. This drastically increases the speed of the algorithm as the following table shows. This difference is shown in the following image: compare darker events on the left and center image parts.</li></ul><blockquote>We call the above algorithm “BVC example”.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/0*1fyngfzboXIuIXxT" /><figcaption>Left part — Hashgraph consensus witness creation, voting and total ordering, center — same as Hashgraph consensus, except that we totally order all events seen by ANY given layer famous witnesses and not all of them, right part — BVC example with frequent base layers.</figcaption></figure><p>It is straightforward to see that Hashgraph consensus added much less events to the total order that its modified version, which, in its turn, adds 2 events less that BVC example. Actually, this is not a pure coincidence. If one defines algorithm latency as an average time between event creation and the time when it is added to the total order, then experiments show that</p><p><strong>Hashgraph consensus &lt;&lt; Enhanced Hashgraph consensus &lt; BVC example</strong></p><p>The following plot represents average latency stats for these algorithms for node numbers 4, 5, … up to 50.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/608/0*XKa0WC-zk4t1Ixmm" /><figcaption>Plot represents node number &lt;-&gt; latency relation for 3 chosen algorithms. Latency is represented not in seconds but in units, which are the average gossip time. E.g. if gossip takes 100ms between any two nodes, then BVC example latency for 30 nodes is ~3 seconds, and ~4 seconds for 50 nodes.</figcaption></figure><blockquote>As one can see BVC example (which is not even the fastest in the BVC family) outperforms Hashgraph consensus by ~<strong>40%</strong> and Enhanced Hashgraph consensus by ~<strong>11%</strong>.</blockquote><p>In order to see the speed superiority even more clearly look at the following comparative video where Hashgraph consensus (on the left) and BVC example (on the right) process events and add them to the total order in real time for the same gossip exchange scenario:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FrcMajpjpucc%3Ffeature%3Doembed&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DrcMajpjpucc&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FrcMajpjpucc%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/156af147fc5252fe2d303f292874a32f/href">https://medium.com/media/156af147fc5252fe2d303f292874a32f/href</a></iframe><p>Video clearly shows the general pattern: BVC example confidently outperforms Hashgraph consensus.</p><blockquote>That’s it! I hope I gave the main ideas behind BVC family. The algorithms from this family can readily be used in practice! They can be a good basis for any distributed ledger or data storage project. Proof of stake ingredient can be added! At the same time one can try to continue this work and find out what are the best members of BCV family.</blockquote><p><em>I’m open to any suggestions, help and collaboration on the subject. Don’t hesitate to contact me via email: trafim.lasy@gmail.com.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=85739614bbcb" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>