From Peanuts to Hashgraph
Every year, Charlie Brown has tried to kick a football many times, only to have Lucy van Pelt cruelly pull the football away at the last second. Here, we find them reasoning about each other’s knowledge in a way that is reminiscent of Hashgraph. Let’s have a closer look…
Lucy is always one step ahead!
Being “one step ahead” in this game means knowing just a little bit more than what the other knows; but for that, one needs to know what the other already knows.
So what is going through Charlie’s mind that makes him think it is OK to kick the ball this time?
At first, Charlie knew nothing of Lucy’s intentions, so he tried to kick the ball and fell when she moved it away.
But then, Charlie learned her intentions, so he figured it would be best to stop short of kicking the ball (or kick her ).
But then, Lucy knew that he knew; so she could trick him by NOT moving the ball. In which case Charlie would stop short and look like a fool.
But then, Charlie knew that she knew that he knew; so he would kick the ball normally, knowing that she wouldn’t move it.
And so on and so forth…
Ultimately, Charlie gets to a stage where he is reasoning about the common knowledge of the events in set A.
Charlie’s event in the blue set means: “Charlie knows that Lucy knows all the events in A”
Lucy’s event in the blue set means: “Lucy knows that Charlie knows all the events in A, and that Charlie knows that she knows all the events in A”
Charlie thinks he has an edge because Lucy will not go deeper than the blue events. But she does, and that’s why the cartoon is funny (or was funny).
It is inevitable to notice that the graphs we drew above look very much like Hashgraphs.
To explain the commonalities, we will juxtapose the steps of the Hashgraph consensus algorithm, as described in the patent document US 9,646,029, with the reasoning that might be going on in Lucy’s mind as she decides to trick Charlie.
Let us look at the first claim of this patent (the other claims are either dependent on it or virtually identical when it comes to the actual ordering algorithm).
A method, comprising:
receiving a first event from an instance of a distributed database at a first compute device from a plurality of compute devices that implement the distributed database via a network operatively coupled to the plurality of compute devices;
defining, based on the first event and a second event, a third event;
determining a first set of events based at least in part on the third event, each event from the first set of events is:
a) identified by a second set of events,
a collective stake value associated with the second set of events meeting a first stake value criterion,
each event from the second set of events
(1) being defined by a different instance of the distributed database and
(2) being identified by the third event,
and
b) associated with a first round number;
calculating a round number for the third event based on a determination that a sum of stake values associated with each event from the first set of events meets a second stake value criterion,
the round number for the third event corresponding to a second round number greater than the first round number;
determining a third set of events based on the third event, each event from the third set of events is:
a) identified by a fourth set of events including the third event, each event from the fourth set of events being defined by a different instance of the distributed database, a collective stake value associated with the fourth set of events meeting a third stake value criterion, and
b) from the first set of events;
defining an order value for a fourth event based on a collective stake value associated with the third set of events meeting a fourth stake value criterion; and
storing the order value in an instance of the distributed database at a second compute device from the plurality of compute devices.
Phew…
Let us go through it step by step.
“A method, comprising:
receiving a first event from an instance of a distributed database at a first compute device from a plurality of compute devices that implement the distributed database via a network operatively coupled to the plurality of compute devices;
defining, based on the first event and a second event, a third event; […]”
Here we labeled the 1st, 2nd and 3rd events as defined above.
The compute devices are Charlie’s and Lucy‘s respective brains.
The distributed database is the union of their respective knowledge.
Receiving an event means learning something from the other without an acknowledgement.
[…] determining a first set of events based at least in part on the third event, each event from the first set of events is:
a) identified by a second set of events,
a collective stake value associated with the second set of events meeting a first stake value criterion,
each event from the second set of events
(1) being defined by a different instance of the distributed database and
(2) being identified by the third event,
and
b) associated with a first round number; […]
Here we take the meaning of an event A being ‘identified’ by another B to signify that there is an upward path in the graph leading from A to B; or more simply that it is possible for A to causally affect B.
Lucy is trying to organise her knowledge into rounds, to make sure that she is one round above Charlie. This implies a notion of order.
She assumes that Charlie will not go deeper than the events in S1 (she has implicitly determined the set S1). S2 is the set of events from Charlie that last identified all events in S1.
We arbitrarily declare that the first round number associated with the events in S1 is R.
Let’s plough through..
[…] calculating a round number for the third event based on a determination that a sum of stake values associated with each event from the first set of events meets a second stake value criterion,
the round number for the third event corresponding to a second round number greater than the first round number;[…]
Lucy is saying to herself: “If I know enough events from a lower round, through events from Charlie, then I have reached a higher round of knowledge… I know more than Charlie”
If we define the stake value of each event of the first set of events to be 1, and the second stake value criterion to be that the sum of stake values be 2, the second round number corresponding to the 3rd event is R+1.
But she still needs to make sure that all the events from round R and below are known by her and Charlie, and that no new events will be added at those rounds. Otherwise she might be missing something…
So, based on her latest information, she tries to define S3, a subset of S1 that will never change order, even when new information is learned.
[…] determining a third set of events based on the third event, each event from the third set of events is:
a) identified by a fourth set of events including the third event, each event from the fourth set of events being defined by a different instance of the distributed database, a collective stake value associated with the fourth set of events meeting a third stake value criterion, and
b) from the first set of events; […]
The usefulness of this step is more apparent when there are more than 2 participants.
And finally…
[…] defining an order value for a fourth event based on a collective stake value associated with the third set of events meeting a fourth stake value criterion; and storing the order value in an instance of the distributed database at a second compute device from the plurality of compute devices.
Instead of defining an order value only for one “fourth event”, we can do so for all the events identified by S3.
The patent claim does not specify how to define the order or what the fourth stake value criterion is, but we can arbitrarily sort them in topological order.
Conclusion
We tried to make sense of the Hashgraph patents in light of a simple example which illustrates the importance of common knowledge in an agreement protocol.
References
A Characterization of Eventual Byzantine Agreement. Halpern, Moses, and Waarts
Convention, A Philosophical Study. Lewis
Time, Clocks, and the Ordering of Events in a Distributed System. Lamport
Martin Arrivets
