Dynamic Membership

General Overview

InternalTransaction

InternalTransactions are inside KDAG as opposed to regular transactions that only affect the application layer. KDAG modifies a portion of its state, the peer set, based on InternalTransactions, rather than modifying the application’s state. However, during the block commit phase, the application layer plays a role in accepting or rejecting changes to the peer set. For example, the application can stop all InternalTransactions (thus preventing any changes to the peer set) or accept up to N participants. Or ultimately, the decision can be based on a predefined whitelist; as long as the rules are deterministic, everything proceeds (all nodes make the same decision).

PeerSet

Until now, peer set sets have been static lists of peer sets. Now, we associate each hash map round with a potentially different peer set. We maintain the peer set associated ranked table so that all rounds between two subsequent entries in that table are associated with the leftmost peer set. For example, if the peer set table is [{0, PS1}, {5, PS2}, {12, PS3}], then rounds 0 through 4 will be associated with the peer set PS1, rounds 5 through 11 will be associated with PS2, and rounds 12 and above will be associated with PS3 (until the peer set changes again).

Algorithm Updates

There is no better documentation than the code itself, but here is an advanced overview of what has been changed. This section assumes that you are familiar with KDAG and the Hashgraph.

StronglySee

Informally, StronglySee is the function used to determine if there is a path connecting two events in the hash graph so that it includes events from the vast majority of participants. It begs the question, “Which set of participants is the overwhelming majority of the participants?”. Therefore, we extend the StronglySee method with the PeerSet parameter.

Round

The number of rounds for an activity depends on the maximum number of parents participating in that activity. And add ONE if and only if that activity can strongly see the largest number of witnesses (maximum parents) in that round. Thus, in the call to StronglySee, we pass the set of peers corresponding to the maximum parent peer and count the supermajority based on the maximum parent peer set.

Witness

An activity is a Witness, if and only if it is the first activity of that creator in its turn and its creator belongs to a companion in that turn.

Fame

Dynamic membership allows for different sets of peers to be involved in determining the Fame of a single witness. Although KDAG’s implementation of the Hashgraph algorithm is slightly different, this is a change introduced in the algorithm by dynamic membership, as described in the original Hashgraph white paper.

R+6

After committing InternalTransaction, when should we start calculating the new peer set to ensure that all the correct nodes will perform the same operation? The answer is R + 6, where R is the receiving round that contains the InternalTransaction event.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store