Solving the Byzantine Generals Problem with Virtual Voting
PoW and PoS systems are designed to enable network users to vote on the current network state. This vote collation increases the time for the network to attain consensus. To solve this, Virtual Voting platforms like Hedera’s Hashgraph use a new consensus algorithm to attain the same consensus — but without the time delay the voting process causes.
It can achieve this as all nodes know both what their vote will be and also what the vote of other nodes would be. The community can come to a consensus on both the timing and the order without a formal vote and, as a result, the network can approve transactions in seconds and handle great volumes (hundreds of thousands of tps).
Virtual voting works by using a gossip protocol (which allows nodes to exchange data with other nodes) and amending it so that it becomes a “gossip about gossip” protocol. Through this, information about ‘events’ is shared so each node can create its own instance of a historical ledger, arranged using a Directed Acyclic Graph. Each event in the DAG consists of transactions, a timestamp (which allows events to be correctly ordered) and the parent event (akin to how blocks reference a previous block in blockchain). It is also signed by the node that created the event.
Nodes gossip by selecting another node at random to transmit event history to. The receiving node then adds any new information it has not yet seen to their DAG. They then sign any transactions they may intend to submit to the network. This creates a shared record of all communication between nodes and thus all nodes have not just a record of all transactions but also a ledger detailing how all nodes learned of those transactions. This means that a node does not need to be told by a neighboring node how they voted — they are able to check their local DAG and from that can determine how they would have voted.
Instead of a transaction being submitted for approval and a period of time elapsing whilst it is confirmed, this structure allows for a transaction to spread across the network via this gossip. Once a set number of nodes have seen it the transaction is considered confirmed and consensus reached. While not all members will have the exact version of new events, they will attain the same set of data by constantly gossiping amongst themselves until they all match.
Because all nodes have the same historical information then — as long as they can determine the majority of the network saw Event X happening at Time X — they will all come to the same conclusion of what has happened and what their own vote would be, as well as the vote of other nodes. This avoids the need for a formal vote.
Once a consensus is reached it cannot be retracted. All nodes on the network have a record of the event history that led to it being accepted — going back on this consensus would require editing all previous events too, which is not possible.
Accordingly, virtual voting solves the Byzantine Generals Problem in the following manner:
- The Generals have the ability to gossip between one another (for the sake of maintaining the example of medieval Generals, let us assume they have carrier pigeons able to convey a very narrow set of messages in a one on one manner)
- The Generals send their pigeons to random Generals with details of the other messages they have received from other Generals. They also send information of their own intentions. They each record the time of each message received so that between them they are able to construct a picture of when each General saw what
- By sending and receiving this information, the Generals build up a picture of what the other Generals are thinking and the time at which all Generals stated their intentions/shared information
- Any malicious actors attempting to block information being shared will find that the other Generals are able to share it between themselves anyway, and therefore the malicious General will be circumvented (as long as these malicious Generals make up less than 1/3 of the total). If said malicious General does not arrive at the same event history as the other Generals, they will know that the General is not honest or reliable
- Through this the Generals will come to a shared agreement on the correct information and can therefore simultaneously agree upon whether to attack or not and when to do so — without the need to take a formal vote on it
As a result, virtual voting is faster than either PoW or PoS. It also avoids the energy wastage of PoW networks as there is no mining. Nodes do not compete with one another to verify a block — instead all nodes on the network are producing all events at the same time through the gossip protocol. Events are not discarded, and the network runs by all nodes constantly communicating with each other.
The nature of the virtual voting and gossip protocol also means that malicious nodes cannot stop a transaction from being processed as it is broadcast to nodes all across the network. This also ensures that there is no single node charged with the responsibility of producing/verifying an event — it is the responsibility of all nodes on the network to generate the timestamp at which an event is seen which is what allows for the correct ordering and thus prevents double spending.
It is important to note, however, that there is currently no public ledger implementation of virtual voting. It exists solely as a private distributed ledger, an implementation not subject to the same rigours as public ledgers. Private ledgers are easier to scale as you can trust the actors operating on them and the network conditions; public distributed ledgers are a different proposition.
This switch from private to public leads, for one, to the need to prevent Sybil attacks. This is where a malicious actor attempts to take over the network by flooding it with nodes they control and is an attack vector both PoW and PoS are designed to protect against.
Current implementations of virtual voting can only circumvent this at present by emulating elements of DPoS and appointing trusted delegates as the only ones allowed to validate transactions. This concentrates power among a small number of users who must be trusted to act in the interests of the wider network. This therefore increases the likelihood of potential collusion and self-interests rising to the fore.
Current implementations of virtual voting also suffer from running on DAGs. While DAGs are able to process more transactions and in a faster manner than blockchains, they too suffer from scaling issues.
Unlike blockchains, where the global state is updated periodically, a DAG has no block time — the state is changing with every transaction. As the throughput requirements increase, eventually the transaction database becomes too large for all nodes to record. To address this the DAG can be sharded: split up into multiple different mini DAGs which each carry a small subset of transactions. This brings forth new issues:
- A DAG can only guard against double spends if it has visibility of all transactions — which it no longer has — or is told what to trust by a centralized authority
- Splitting the DAG into many smaller subsets means a malicious attacker needs to control substantially less of the total network power (hashing, or stake or delegated votes) to be able to attack the network
As with other implementations, decentralized security is traded for performance and there is as of yet no proof that the successful transition can be made to a decentralized public ledger. Whilst virtual voting can aid with scale, it remains constricted by the data structure it is currently operating on and its own inherent limitations.
Originally published at www.radixdlt.com.
Have questions about Radix? Join The Conversation …
1) Telegram: https://t.me/radixdlt
2) Discord: https://discord.gg/fS6F9NP
