Design

Most consensus algorithms are blamed for their inefficiency. It is mainly caused by the fact that any single block of transactions requires a consensus to be reached among a huge number of “stranger” voting nodes. As the voting nodes do not have pre-exist trust relationship, any consensus is in fact a trust building process from scratch for an extensive large amount of entities. This incurs significant network latency and computation complexity.

Instead of layering consensus acceleration techniques above the consensus layer, such as the Layer 1 or Layer 2 improvements, Leviatom targets at the performance issues by digging 1 layer “below” the consensus layer: a Layer -1 enhancement. Layer -1 focuses at constructing trust relationship among the voting nodes. Its main goal is to identify the set of nodes who possess the greatest difficulties to “tell a lie”, i.e. the difficulties to execute unexpected programs without being identified.

With the trustworthiness of the voting nodes modelled and calculated, the consensus layer will no longer need any one particular transaction be examined by all nodes, but only by the nodes whose trustworthiness are endorsed by most other nodes. As less nodes are required to vote, the consensus will reach much faster. As any voting node is endorsed by a large number of other nodes, the difficulty in breaching the consensus still remains high.

One way to implement the Layer -1 enhancement is to enforce remote attestation techniques among the voting nodes. Remote attestation is a critical procedure implemented by the Trusted Execution Environment (TEE) technologies. It genuinely reports the status of the loaded applications on a target node with the help from an embedded security chip, such as the TPM (Trusted Platform Module), the Intel CPU’s SGX extension, or the ARM’s TrustZone extensions. With remote attestations, any voting node will examine whether its connecting peer is running only the correctly installed and configured software stack. Therefore, as long as any node has the intention to “tell a lie”, it will be identified immediately, because the changed applications or configurations will be spotted by remote attestations. With the Layer -1 enhancement, a voting node will ensure that it is communicating with a correct peer.

However, one critical difficulty in applying the TEE technologies is to effectively manage the scale of redundant attestations. Remote attestations only ensure the target node’s confirmation of expected behaviours up to the time when the attestations are taken. Therefore, a target voting node is required to get attested frequently. For a large network of nodes, frequent attestations among communicating nodes may incur significant computation and networking overheads, as the complexity for maintaining the mutual attestation relationship among n nodes is exponential O(n2).

Leviatom solves this issue by introducing the transitive trust relationship. Transitive trust allows one node to deduce the trustworthiness of a remote node without initiating direct remote attestations: as long as there exists an iterative attestation path to the target node. Therefore, in a network of partially mutual attesting nodes, as long as a node has the largest number of attestation paths led to it, it is regarded the hardest one to “tell a lie”.

To further accelerate this path-finding procedure, the mathematical multifaction operation is applied iteratively on this transitive trust relationship matrix. This process will final construct a matrix, with each value representing the “Conspiracy Breaching” for each associated node. It indicates the number of nodes a target malicious node has to “bribe” in order to “tell a lie”.

With this matrix defined, Leviatom only need to choose a small number of nodes with the highest values as the voting node to enforce the consensus procedure on a target transaction. This procedure significantly increases the consensus efficiency. Meanwhile, when each node’s “Conspiracy Breaching” remains high, the consensus still remains hard to breach.

Leviatom can further implement a trustworthy node selection mechanism to support the upper layer service, such as the consensus layer services of third-party public blockchains, in which case the public chains run as a Dapp on Leviatom’s Layer -1 network. More importantly, it supports the MagCarta smart contract’s “consensus” call, which distributes Prometh Applications on the chosen Leviatom nodes. This will be discussed in Chapter 3 and 4. Leviatom’s core algorithm is called the Heterogeneous Consensus Graph (HCGraph), which is described and evaluated in the following sections.