We have implemented one of the consensus mechanisms in distributed network systems. This is one of the programming assignments from the Princeton University course, “Bitcoin and Cryptocurrency Technologies.”

Trust Graph Between Nodes

The task involves implementing a distributed consensus algorithm given a trust graph between nodes. This algorithm counteracts Sybil attacks^*1 and provides an alternative method for achieving consensus, offering the advantage of avoiding the significant energy “waste” associated with PoW.

*1 Sybil is derived from the name of a woman who suffered from dissociative identity disorder. In the blockchain industry, the term refers to an attack where malicious actors create multiple nodes to dominate the network.

Good and Malicious Nodes

First, the nodes in the network are classified into two types: Compliant (Good) and Malicious (Bad). “Trust” is represented by a directed random graph where each edge indicates a trust relationship between nodes. For example, if there is an edge \( A\ \rightarrow \ B \), it means node \( B \) listens to transactions propagated by node \( A \). Here, \( B \) is a follower of \( A \), and \( A \) is a followee of \( B \). Naturally, trust relationships do not exist between good nodes and malicious nodes.

Behavior of Malicious Nodes

Malicious nodes can perform actions such as the following:

• Being functionally inactive and not propagating transactions.
• Constantly propagating their own transactions while never accepting any transactions received from others.

Requirements for the Consensus Algorithm

Next, each node must succeed in achieving consensus within a network of peers executing the same code. It is designed so that a network of nodes that receive different sets of transactions can agree on the set that should be accepted. In addition, a certain number of simulations are set, and each time a node propagates a proposal to its follower, and at the end of the entire number of simulations, an agreement must be reached on the deal to be agreed upon.

Mechanism of Transaction Propagation

Each node is provided with a list of followees, and each followee is given a list of transactions (proposal list) to propagate to their followers. Here, all transactions are valid, and invalid transactions cannot be created.

Tolerance to Malicious Nodes

Finally, during testing, nodes executing the code may encounter malicious nodes (up to a maximum of \( 45\% \)). The nodes must withstand as many malicious nodes as possible while still achieving consensus.

Evaluation Criteria for Testing

Testing is evaluated based on the following criteria:

1. The size of the group of nodes that achieved consensus. Consensus is counted only if all nodes output the same transaction list.
2. The size of the group that reached consensus (aiming to maximize the set of agreed-upon transactions).

Class Specifications and Overview

The following table summarizes the classes used and their descriptions.

File	Description
Node.java	Interface for the CompliantNode and MaliciousNode classes. Includes the following methods: setFollowees() to set followees, setPendingTransaction() to initialize the transaction proposal list, sendToFollowers() to return the proposal list to followers, and receiveFromFollowees() to receive transaction candidates from other nodes.
CompliantNode.java	The CompliantNode class that implements the Node interface.
MaliciousNode.java	A class for malicious nodes that implements the Node interface.
Candidate.java	A class for describing transaction candidates received by nodes. Includes fields for the proposed transaction ID and the index of the proposing node.
Simulation.java	A class for testing consensus mechanisms. It generates graphs, modifies graph parameters, and allows testing of the CompliantNode class.
Transaction.java	A class for transactions. Includes a field for a unique transaction ID.

Overview of Simulation.java Process

The following outlines the process within Simulation.java:

1. Generate nodes, selecting which are malicious and which are good.
2. Initialize a random graph for the nodes generated in step 1.
3. Notify all nodes of their followees.
4. Initialize a set of valid transactions with random IDs (e.g., 500 transactions).
5. Distribute the transaction across the nodes in order to initialize the starting state of the transaction heard by each node. The distribution is randomized based on a defined probability for each transaction-node pair.
6. Aggregate the list of transactions each node proposes to its followers.
7. Propagate the proposal lists aggregated in step 6 to each node.
8. Repeat steps 6 and 7 for the specified number of simulation rounds.

Test Results

The test results are as follows:

Tests for this assignment involve your submitted miner competing with a number of different types of malicious miners.

Parameters	Results
numNodes = 100, p_graph = 0.1, p_malicious = 0.3, p_txDistribution = 0.01, numRounds = 10	On average, 44 out of 72 nodes reach consensus.
numNodes = 100, p_graph = 0.1, p_malicious = 0.3, p_txDistribution = 0.05, numRounds = 10	On average, 61 out of 72 nodes reach consensus.
numNodes = 100, p_graph = 0.1, p_malicious = 0.45, p_txDistribution = 0.01, numRounds = 10	On average, 33 out of 58 nodes reach consensus.
numNodes = 100, p_graph = 0.1, p_malicious = 0.45, p_txDistribution = 0.05, numRounds = 10	On average, 42 out of 58 nodes reach consensus.
numNodes = 100, p_graph = 0.2, p_malicious = 0.3, p_txDistribution = 0.01, numRounds = 10	On average, 69 out of 76 nodes reach consensus.
numNodes = 100, p_graph = 0.2, p_malicious = 0.3, p_txDistribution = 0.05, numRounds = 10	On average, 74 out of 76 nodes reach consensus.
numNodes = 100, p_graph = 0.2, p_malicious = 0.45, p_txDistribution = 0.01, numRounds = 10	On average, 41 out of 54 nodes reach consensus.
numNodes = 100, p_graph = 0.2, p_malicious = 0.45, p_txDistribution = 0.05, numRounds = 10	On average, 49 out of 54 nodes reach consensus.

Explanation of Parameters

• numNodes: Number of nodes.
• p_graph: Probability that an edge exists in the random graph.
• p_malicious: Probability of a node being set as malicious.
• p_txDistribution: Probability of assigning initial transactions to each node.
• numRounds: Number of simulation rounds executed by nodes.