DAG ALGORITHM LOGIC
DAG algorithm are 4 nodes in the network (A,B,C,D), each node send a transaction, the transaction is included in an event gossip to other nodes, and a gossip will know the peer of this node maintains a complete graph. Through a voting algorithm, each event is time stamped. Before explaining the specific logic, let’s take a look at the event data structure:
type Event struct
{
Transactions [][]byte //the payload
selfParent string
otherParent string
Creator []byte //creator’s public key
Timestamp time.Time //creator’s claimed timestamp of the event’s creation
roundReceived *int
consensusTimestamp time.Time
}
The transactions field is all the transactions contained in the Event, selfParent and otherParent are the hash of the Event parent Event, including the parent Event created by itself and the parent Event created by other nodes, Creator is the creator’s public key, and Timestamp is the time when the Event was created Timestamp. RoundRecevied is the consensus of the event by the famous witnesses in several layers of round.
Let’s take a look at the specific consensus process:
1) A,B,C and D each create a root Event during initialization, and then B randomly selects a node(assuming D is selected), and then B sends to D all the events that it knows that D does not know (here only the rootEvent created by B at the beginning), D creates a new Event (the SelfParent of the Event is the root Event of D, the otherParent is the rootEvent of B), and then D sends all the events (including the newly created) that it knows randomly. Create a new event for B, B, so B knows 4 events (two created by himself and two created by D), and D knows 3 events (not including B’s last creation).
2) B then selects A randomly, and then sends 4 events that he knows to A, and A creates a new Event, Which keeps growing and forms a graph structure.
3) Famous witnesses are determined. First of all, let’s take a look at several concepts, see and strongly sees. See means that there is an ancestral relationship between Events. Suppose there are Events (B2) and Event (A3). Assuming that B2 is the ancestor of A3 and A3 is the descendant of B2, then A3 can see B2.
Strongly sees is an ancestor-grandchild relationship between two events, and all the nodes in all paths connected by these two events and more than 2/3 of the nodes are regarded as one event strongly seeing the other event.
Witness is the first Event in a round(the rootEvents are all witnesses). The method for determining a round is that an Event can strongly see more than two-thirds of the witness in the current round, then the round of the event is increased by one.
The determining mechanism of famous witness is that the witness in the next round is voted on the visible witness in the previous layer, and the witness in the next round is used to count votes. The specific rule is that if a witness (A3) Visibility (B2) is visible, then vote YES. When all voted performance (A3, B3, C3, D3) voted YES for voted performance (B2), then voted performance (B2) is declared as famous, and then Next level
If witness (B4) is strongly visible to participating witness (A3,B3,C3,D3), then the vote is YES, then the vote is valid. When the number of valid votes exceeds 2/3, then the voted witness (B2) is selected as a famous witness.
4) When the famous witnesses are determined, we can find a consensus Timestamp and a roundRecevied for events. The rule is that when an event (X) can be seen by all the famous witnesses in the next round, then the roundRecevied of the event (X) Is to see its round value of all famous witnesses, the event (X) consensus Timestamp determination rule is to find all the ancestor event (X), and timestamp these events Sort, then find the middle timestamp as the consensus Timestamp of the event(X).
The events that are marked with consensus Timestamp are the consensus events, and then the events are sorted according to roundRecevied.
