Network structure

To begin, let’s review the overall structure of the network.

There are two types of entities in the network:

• Nodes are the active components of a network. They are usually physical devices that communicate through radio signals. Nodes are permanent elements that join the network through a decentralized registration process.
• Addresses, on the other hand, are passive components. They are typically logical entities that facilitate money transfers by connecting to the nodes via a local network or any custom protocol. An address can be usedimmediately upon creation, and no registration is required.

The primary reason for this separation is the differing trade-offs in how we manage these entities.

Pros and cons of nodes:

• Only nodes have the ability to create blocks and collect fees and mining rewards from the network.
• Transactions between nodes are cheaper.
• All money transfers between nodes are transparent and visible to anyone, meaning there is no privacy.
• The network doesn’t count custodian fees for nodes.

Pros and cons of addresses:

• A simple user can use multiple addresses, allowing for different addresses to be used for each transaction. This approach enhances privacy for transactions between addresses.
• Transactions are more expensive between addresses. This is because the size of the transaction determines transaction fees, and addresses tend to be longer than node identifiers. Users who wish to maintain their privacy must pay an additional fee. While this may seem unfair, ensuring privacy requires extra resources from the network. In MoonBlokz, I adjust the pricing to reflect the resources needed for each action.
• The network applies custodian fees for money stored in addresses.

Blockchain

It’s time to outline the working model of our blockchain. First, let’s define what a blockchain is:

A blockchain is a shared, immutable, and distributed digital ledger that records transactions across multiple computers.

When we examine the structure of blockchains, we can see that each blockchain consists of blocks, as illustrated in the following chart:

Blocks in the chain are assigned an increasing sequence number that uniquely identifies each block. Each block contains a payload representing its content (such as transactions). Every block is digitally signed to ensure protection against tampering. Additionally, all blocks include the hash of the parent block, making it impossible to alter any previous blocks in the chain.

When new information needs to be added to the blockchain, a selected node creates a new block and distributes it throughout the network. However, because every node operates separately, unreliable communication quickly transformed our blockchain into a “blocktree.” Let’s look at an example:

The network has five nodes: Anna, Bob, Cecil, David, and Eve. All of them received block #100. Bob then created a new block (#101) and tried distributing it across the network. Anna received this block, but Cecil, David, and Eve did not.
Subsequently, Cecil created her version of block #101, which was only received by David. This situation led to Anna, Bob, and Eve independently creating parallel blocks #102 and #103. Later, David received Eve’s block and made his own block, #105, based on it.

This situation creates chaos because each end of the chain represents different network states. The nodes perceive the network as being in various actual states. While all nodes share the same past (each has the same version of block #100), they exist in different parallel present states. This scenario resembles a kind of multiverse. To bring order to this chaos, our goal is to develop an algorithm that accomplishes two tasks:

• Ensuring that the network can eventually achieve a consistent state
• Managing the transition when a node must switch between parallel states.

How to reach a consistent state?

Nodes cannot achieve a consistent state if they do not have the same or nearly identical blocks. We use broadcast radio communication with dynamic nodes in a mesh network, which means the sender cannot track who has received the message. As a result, we need to manage this on the receiver’s side, which is also problematic.

If we have not received anything, how can we know if a message was sent at all?

Fortunately, a blockchain (or blocktree) is not made up of independent blocks. If a block arrives and we do not have its parent block, we can deduce that we missed a message and can ask the network for it using its sequence number and hash, which we know from the child block.

We need to store the entire tree rather than just a single chain. This is essential because we cannot predict which fork will win when we receive a message, though we can limit the possible forks (I will explain this later). Additionally, we must retain disconnected blocks, as they may eventually connect to the tree if we query their ancestors.

With this approach, the nodes will attempt to construct the same tree. However, some discontinued leaves may be permanently lost if they have no successors, and there is no indication of their absence. Still, if the network remains largely connected, the active branches will synchronize across the nodes.
At this step, we don’t have a consistent state, but we have the same multiverse on each node.

Making consensus

The next part is crucial. The most fascinating aspect of blockchains is how nodes establish a common state. Given our specific conditions, we have certain requirements for our consensus algorithm:

• Since our communication may be unreliable and bandwidth and communication time are also bottlenecks, we should base our selection on the blockchain stored by each node without needing additional communication.
• Our nodes have limited hardware capabilities, so we cannot use algorithms that demand high processing power, such as Proof-of-Work.
• Our consensus algorithm must prevent double spending, like all blockchain consensus algorithms (or at least make it hard).

Double spending is the risk that a digital currency can be spent more than once, undermining the system’s integrity. This situation can occur when a blockchain forks and two separate transactions in each fork attempt to use the same balance. The receiving node may initially believe it has received the funds, but the transaction can vanish if the blockchain reverts to an alternate path. To prevent double spending, the chain should avoid forking.

Choosing a common state also determines which nodes can create the next block in the chain. We aim to reward the creators of the blocks and incentivize their efforts in maintaining the network.

How can we reward block creators (also known as miners)?

The sender includes a fee with each transaction. When miners create a block, they prioritize transactions with higher fees from their mempool (a temporary transaction storage space). When miners successfully mine a block, they receive all the transaction fees included in that block.

Additionally, the network can fund miners, which is how new currency is generated. In MoonBlokz, the operational model can be customized through chain-level configurations. Transaction fees can be set at minimal, maximal, or exact amounts. Furthermore, the additional currency created or consumed can be determined by a function that takes into account various parameters, such as the total amount of money in the network, the total number of nodes, and the average transaction fees.

To select block creators, we must first identify what holds value for our blockchain. For a node, it is valuable to receive messages from other nodes in the chain. We will use the following algorithm to select miners based on this metric:

• Every message on the network includes the identifier of the sender node.
• Nodes keep track of how many messages they receive from each other.
• When a node makes a transaction, it votes for the node that has sent it the most valid messages.
• When it’s time to create a block — either because there are enough transactions to fill it or enough time has passed — the node with the most votes gets to make the block. After this, that node’s vote count resets to zero.
• If two nodes have the same number of votes, the tie is broken using the node’s identifier, ensuring the selection process is deterministic. This means there is always one node selected.

This algorithm is extremely fast, straightforward, and prevents any forking. It works effectively as long as we have knowledge of all the node identifiers and all the miners. Since we have this information (there is no privacy for nodes), we can utilize this algorithm. But it fails in some cases. We must address situations where the selected node cannot create a block, such as when it is removed from the network. We use an additional mechanism called “approval” where the majority of the nodes approve the deviance from the basic algorithm. Approval is a time-consuming process, but it is rare during normal work.

State diagram of the approval process:

Once a new block is ready to be created — due to a sufficient number of available transactions or the passage of enough time — the node with the most votes has a “grace period.” The network will only accept a block from this node during this period. If the grace period passes without a block created, the approval process begins:

• First, the network accepts blocks from the node with the second-most votes and the first node. If double the grace period passes without a block being produced, the top three nodes will be allowed to create new blocks, and this pattern continues thereafter.
• Next, the network decides whether to accept the block. Nodes submit digitally signed support messages for the proposed block.
• When the block creator collects a pre-determined number of these support messages, it creates another block that serves as evidence of majority support.

If the node with the most votes fails to produce the block, it incurs a penalty, resetting its votes to zero. This penalty effectively eliminates the waiting delay for subsequent blocks. However, to optimize data, only the first node’s vote score is reset; the scores of all other nodes that missed the chance to produce the block remain unchanged. The grace period duration is a configurable parameter at the chain level based on factors like the average time between blocks.

This process can lead to multiple approvals happening simultaneously. If evidence of majority support cannot be submitted before the approval period ends, the next highest-voted node can initiate a new approval. Furthermore, if the initiating node fails to post the evidence, another node may do so after a grace period, initiating a new approval process.

When a node needs to determine the actual blockchain within the block tree, it performs a calculation: The value of each block is equal to the spent vote score associated with that block, except for the approval blocks. The score of an approval block consists of the vote score of the node with the most votes (which has been paid as a penalty) plus the vote scores of every supporter in the evidence block. After the approval process concludes, this resulting chain will hold a higher value than the one initially created by the first node, ensuring that the network follows the new chain even if the original block is added later.

A later article will discuss the details of the approval process and the entire communication model. First, we must discuss the cryptographic algorithm because special multi-signature constructions are required to create evidence efficiently.

Limitations of the approval process

To approve any deviation, the majority of active nodes (from the previous n block) or at least the majority of a randomly selected subgroup (we will talk about it later) must send their support. If a network permanently and quickly loses more than 50% of its nodes, it could become stuck indefinitely. While this scenario presents a challenge, it is not a realistic concern for any actively operating network.

How secure is this system?

We must first examine threats that algorithms cannot mitigate to assess the system’s security. As we utilize radio communication, a rogue node equipped with a powerful antenna could flood the entire network. In such cases, we can physically deactivate the rogue node. Additionally, we cannot address the scenario where someone places a node inside a Faraday cage, which blocks all communication and allows the node only to receive false messages. We operate under the assumption that many connected nodes exist within the network, with each node within several other nodes’ range.

There are two types of attacks that we aim to mitigate with the previously described working model:

• A small group of nodes can take control of the network by adding numerous transactions to become the sole creators of every new block. To prevent this attack, we introduce an interest mechanism to the vote counts. A node with x votes receives an additional x*y (where y is a small number) votes with every new block added to the chain. This means that even if a node has only a single vote, it will eventually accumulate enough votes to create the next block. If an attacker attempts to generate all blocks, they can only do so if their group initiates all transactions, effectively turning this attack into a denial of service situation.
• An attacker may attempt to create a fork after spending their currency to cancel the transaction after its acceptance. This is only feasible during the approval process. Once the approval process is in progress, there is no way for the attacker to control it without blocking communication between the nodes.

In summary, while there are vulnerabilities to physical attacks to undermine the network, our model incorporates mechanisms to reduce the risk of algorithmic threats.

So far, we have selected our technology, defined the high-level architecture, and outlined the framework of our consensus algorithm. Everything seems to be going well, or does it?

Initially, we stated that our blockchain should operate with only a few megabytes of persistent storage on each node. However, we also want to store the entire blockchain on every node. As the blockchain grows, we will eventually run out of storage space. Therefore, we need to find a way to maintain a constant size for our blockchain. I have named this working model “snake_chain”. We will discuss it further in the following article. You can read it here.

Author: Péter Sallai
Source: https://medium.com/@peter.sallai/moonblokz-series-part-iii-basic-algorithms-76ca1215efc4