Dynamic Membership
Dynamic membership is an extension of the KDAG protocol that enables peers to join or leave an active cluster by consensus. So far, we have only considered fixed sets of peers where the list of participants is predetermined and remains unchanged throughout the lifetime of the KDAG network. It is a limitation that hinders the formation of the instantaneous blockchain we envisioned. Here we present our solution and its implementation, which relies on previous work on hash map-to-blockchain projections and FastSync.
General Overview
The KDAG node loads the genesis peer set (genesis.peers.json) and the current peer set (peers.json) to start the run. If its public key does not belong to the current peer set, the node enters the Joining state where it tries to join the peer set. It reaches consensus by signing InternalTransaction and committing it to one of the current nodes via JoinRequest.
InternalTransaction will be added to EventEvent and go through KDAG consensus until it is added to a block and committed. But unlike regular transactions, KDAG will interpret the InternalTransaction to modify the peer set if the application layer accepts it. We will see that, according to Hashgraph dynamics, a received InternalTransactio, committed at round R, only affects its peer set at round R + 6 and above.
If the JoinRequest succeeds and the new node adds it to the peer set, it will either go directly to the Babbling state or the CatchingUp state, depending on whether the FastSync flag is provided or not. In the former case, the Node node will have to retrieve the entire history of the hash map and commit all missing blocks one by one. That is why having a genesis peer set is so important, as it allows joining nodes to validate consensus decisions and peer set changes from the beginning of the hash map.
Deleting peer sets will function almost identically, with the difference that there will be an automatic determination of when a node should get deleted based on a minimum activity level (e.g., Ten rounds without witnesses). Starting today, when the KDAG process terminates cleanly, the node will submit a leave request for it after capturing the SIGINT signal.
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).
type InternalTransactionBody struct {
Type TransactionType
Peer peers.Peer
}
type InternalTransaction struct {
Body InternalTransactionBody
Signature string
}
Therefore, the ProxyInterface between KDAG and the application layer has slightly extended to address InternalTransactions. It is an example of a CommitHandler that systematically accepts all InternalTransactions.
func (a *State) CommitHandler(block hashgraph.Block) (proxy.CommitResponse, error) {
a.logger.WithField(“block”, block).Debug(“CommitBlock”)
err := a.commit(block)
if err != nil {
return proxy.CommitResponse{}, err
}
receipts := []hashgraph.InternalTransactionReceipt{}
for _, it := range block.InternalTransactions() {
r := it.AsAccepted()
receipts = append(receipts, r)
}
response := proxy.CommitResponse{
StateHash: a.stateHash,
InternalTransactionReceipts: receipts,
}
return response, nil
}
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).
We will see in the next section how different peer sets are taking into consideration in the core consensus approach because they are allowed to change from one round to another, and peer sets must also be accountable for in the Frame and Block data structures. Indeed, when validating blocks, it is mandatory to know which peer set to count signatures on. Therefore, we extend the Frame and Block object to contain a PeerSetHash that uniquely identifies the peer set received in the corresponding round. In the future, we will need to include proof of peer set changes within the Block so that the client can track and verify the development of the peer set (i.e.) capture the content of the following information.
PS0 + InternalTransaction0 + PS0-signatures(InternalTransaction0) => PS1
PS1 + InternalTransaction1 + PS1-signatures(InternalTransaction1) => PS2
…
PSN + InternalTransactionN + PSN-signatures(InternalTransactionN) => PSN+1
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.
for each event x in order from earlier rounds to later
x . famous ← UNDECIDED
for each event y in order from earlier rounds to later
if x . witness and y . witness and y . round>x . round
d ← y . round — x . round
s ← the set of witness events in round y . round -1 that y can strongly see
** [based on y.round-1 peer-set]
v ← majority vote in s ( is TRUE for a tie )
t ← number of events in s with a vote of v
if d = 1 // first round of the election
y . vote ← can y see x ?
else
** [n ← number of peers in y.round peer-set]
if d mod c > 0 // this is a normal round
if t > 2* n /3 // if supermajority, then decide
x . famous ← v
y . vote ← v
break out of the y loop
else // else, just vote
y . vote ← v
else // this is a coin round
if t > 2* n /3 // if supermajority, then vote
y . vote ← v
else // else flip a coin
y . vote ← middle bit of y . signature
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.
We only need to determine the lower bound, since the goal is obviously to change peer-set as soon as possible.
The solution（https://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf）
Essentially contained in Lemmas 5.15 and 5.17 of the original hash table white paper.
Citation 5.15. if the hash diagram A and B are consistent and A decides the Byzantine agreement election by outcome v in round r and B does not decide before r, then B will decide v at or before r + 2.
Citation 5.17. for any number of rounds r, for any hash graph with at least one event in round r + 3, at least one witness in round r will be determined to be famous by the consensus algorithm, and that determination will be made by each witness in rounds r + 3 or earlier
When a hash table determines that RoundReceived = R, it will determine the vast majority of Round R witnesses, who, according to citation 5.17, must be determined by round R + 3 or earlier. So, any other consistent hash table would be determined by the round R + 5 or earlier according to citation 5.15. A new reciprocal set can be safely set for the round R + 6.
