Overview of the Byteball witness system
Quote from the Byteball white paper explaining the witness system :
Looking for a “reality test”, observe that some of the participants of our network are non-anonymous reputable people or companies who might have a long established reputation, or they are businesses interested in keeping the network healthy. We’ll call them witnesses. While it is reasonable to expect them to behave honestly, it is also unreasonable to totally trust any single witness. If we know the Byteball addresses of several witnesses, and also expect them to post frequently enough, then to measure the reality of a candidate MC one might travel along the MC back in time and count the witness-authored units (if the same witness is encountered more than once, he is not counted again). We would stop traveling as soon as we had encountered the majority of witnesses. We would then measure the length of the longest path on the graph from the point at which we stopped to the genesis. We’ll call this length the level of the unit where we stopped, and the witnessed level of the parent whose MC we are testing. The candidate MC that yields the greater witnessed level is considered more “real”, and the parent bearing this MC is selected as best parent. In case there are several contenders with a maximum witnessed level, we would select the parent whose own level is the lowest. If the tie persists, we would select the parent with the smallest unit hash (in base64 encoding).
This algorithm allows the selection of the MC that gravitates to units authored by witnesses, and the witnesses are considered to be representative of reality. If, for example, an attacker forks from the honest part of the network and secretly builds a long chain of his own units (shadow chain), one of them containing a double-spend, and later merges his fork back into the honest DAG, the best parent selection algorithm at the merger point will choose the parent that drives the MC into the honest DAG, as this is where the witnesses were active. The witnesses were not able to post into the shadow chain simply because they didn’t see it before the merger. This selection of MC reflects the order of events as seen by the witnesses and the user who appointed them. After the attack is over, the entire shadow chain will land on the MC at one point, and the double-spend contained in the shadow chain will be deemed invalid because its valid counterpart comes earlier, before the merger point.
Figure 4. When an attacker rejoins his shadow DAG into the lit DAG, his units lose competition to become best parent as the choice favors those paths that have more witnesses (marked with w).
This example shows why the majority of witnesses has to be trusted to post only serially. The majority should not collude with the attacker and post on his shadow chain. Note that we trust the witnesses only to be signs of reality and to not post nonserial units on any shadow chains. We are not giving any of them control over the network or any part thereof. Even for this small duty, it is users who appoint the witnesses and they can change their decisions at any time.
The idea of looking at some known entity as a sign of reality is not new. It has long been known, and some companies have engaged in such activity, that to prove that some data existed before a specific date, one can hash the data and publish the hash in some hard-to-modify and widely witnessed media, like printed newspaper . Witnesses in Byteball serve the same function as the newspaper. Like newspapers, they are well known and trusted. As for newspapers where trust is limited to trusting them to publish the data they are given, witnesses in Byteball are only trusted to post serially, and not much more. Like newspapers, witnesses don’t know what’s behind the hashes they are witnessing and have few reasons to care. Newspapers are hard to modify (but possible, and in 1984 they do it), while everything produced by witnesses is protected by digital signatures, which makes any modifications impossible. For reliability, we have several witnesses, not just one, and for speed and convenience, these are online.