Skip to main content

HASHGRAPHLIKE CONSENSUS

Abstract​

This document specifies a scalable, decentralized, and Byzantine Fault Tolerant (BFT) consensus mechanism inspired by Hashgraph, designed for binary decision-making in P2P networks.

Motivation​

Consensus is one of the essential components of decentralization. In particular, in the decentralized group messaging application is used for binary decision-making to govern the group. Therefore, each user contributes to the decision-making process. Besides achieving decentralization, the consensus mechanism MUST be strong:

  • Under the assumption of at least 2/3 honest users in the network.

  • Each user MUST conclude the same decision and scalability: message propagation in the network MUST occur within O(log n) rounds, where n is the total number of peers, in order to preserve the scalability of the messaging application.

Format Specification​

The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and “OPTIONAL” in this document are to be interpreted as described in 2119.

Flow​

Any user in the group initializes the consensus by creating a proposal. Next, the user broadcasts the proposal to the whole network. Upon each user receives the proposal, validates the proposal, adds its vote as yes or no and with its signature and timestamp. The user then sends the proposal and vote to a random peer in a P2P setup, or to a subscribed gossipsub channel if gossip-based messaging is used. Therefore, each user first validates the signature and then adds its new vote. Each sending message counts as a round. After log(n) rounds all users in the network have the others vote if at least 2/3 number of users are honest where honesty follows the protocol.

In general, the voting-based consensus consists of the following phases:

  1. Initialization of voting
  2. Exchanging votes across the rounds
  3. Counting the votes

Assumptions​

  • The users in the P2P network can discover the nodes or they are subscribing same channel in a gossipsub.
  • We MAY have non-reliable (silent) nodes.
  • Proposal owners MUST know the number of voters.

1. Initialization of voting​

A user initializes the voting with the proposal payload which is implemented using protocol buffers v3 as follows:

syntax = "proto3";

package vac.voting;

message Proposal {
  string name = 10;                  // Proposal name
  string payload = 11;               // Proposal description
  uint32 proposal_id = 12;           // Unique identifier of the proposal
  bytes proposal_owner = 13;         // Public key of the creator 
  repeated Votes = 14;               // Vote list in the proposal
  uint32 expected_voters_count = 15; // Maximum number of distinct voters
  uint32 round = 16;                 // Number of Votes 
  uint64 timestamp = 17;             // Creation time of proposal
  uint64 expiration_time = 18;       // The time interval that the proposal is active.  
  bool liveness_criteria_yes = 19;   // Shows how managing the silent peers vote
}

message Vote {
  uint32 vote_id = 20;            // Unique identifier of the vote
  bytes vote_owner = 21;          // Voter's public key
  uint32 proposal_id = 22;        // Linking votes and proposals
  int64 timestamp = 23;           // Time when the vote was cast
  bool vote = 24;                 // Vote bool value (true/false)
  bytes parent_hash = 25;         // Hash of previous owner's Vote
  bytes received_hash = 26;       // Hash of previous received Vote
  bytes vote_hash = 27;           // Hash of all previously defined fields in Vote
  bytes signature = 28;           // Signature of vote_hash
}

To initiate a consensus for a proposal, a user MUST complete all the fields in the proposal, including attaching its vote and the payload that shows the purpose of the proposal. Notably, parent_hash and received_hash are empty strings because there is no previous or received hash. Then the initialization section ends when the user who creates the proposal sends it to the random peer from the network or sends it to the proposal to the specific channel.

2. Exchanging votes across the peers​

Once the peer receives the proposal message P_1 from a 1-1 or a gossipsub channel does the following checks:

  1. Check the signatures of the each votes in proposal, in particular for proposal P_1, verify the signature of V_1 where V_1 = P_1.votes[0] with V_1.signature and V_1.vote_owner

  2. Do parent_hash check: If there are repeated votes from the same sender, check that the hash of the former vote is equal to the parent_hash of the later vote.

  3. Do received_hash check: If there are multiple votes in a proposal, check that the hash of a vote is equal to the received_hash of the next one.

  4. After successful verification of the signature and hashes, the receiving peer proceeds to generate P_2 containing a new vote V_2 as following:

    4.1. Add its public key as P_2.vote_owner.

    4.2. Set timestamp.

    4.3. Set boolean vote.

    4.4. Define V_2.parent_hash = 0 if there is no previous peer's vote, otherwise hash of previous owner's vote.

    4.5. Set V_2.received_hash = hash(P_1.votes[0]).

    4.6. Set proposal_id for the vote.

    4.7. Calculate vote_hash by hash of all previously defined fields in Vote: V_2.vote_hash = hash(vote_id, owner, proposal_id, timestamp, vote, parent_hash, received_hash)

    4.8. Sign vote_hash with its private key corresponding the public key as vote_owner component then adds V_2.vote_hash.

  5. Create P_2 with by adding V_2 as follows:

    5.1. Assign P_2.name, P_2.proposal_id, and P_2.proposal_owner to be identical to those in P_1.

    5.2. Add the V_2 to the P_2.Votes list.

    5.3. Increase the round by one, namely P_2.round = P_1.round + 1.

    5.4. Verify that the proposal has not expired by checking that: P_2.timestamp - current_time < P_1.expiration_time. If this does not hold, other peers ignore the message.

After the peer creates the proposal P_2 with its vote V_2, sends it to the random peer from the network or sends it to the proposal to the specific channel.

3. Determining the result​

Because consensus depends on meeting a quorum threshold, each peer MUST verify the accumulated votes to determine whether the necessary conditions have been satisfied. The voting result is set YES if the majority of the 2n/3 from the distinct peers vote YES.

To verify, the findDistinctVoter method processes the proposal by traversing its Votes list to determine the number of unique voters.

If this method returns true, the peer proceeds with strong validation, which ensures that if any honest peer reaches a decision, no other honest peer can arrive at a conflicting result.

  1. Check each signature in the vote as shown in the Section 2.

  2. Check the parent_hash chain if there are multiple votes from the same owner namely vote_i and vote_i+1 respectively, the parent hash of vote_i+1 should be the hash of vote_i

  3. Check the previous_hash chain, each received hash of vote_i+1 should be equal to the hash of vote_i.

  4. Check the timestamp against the replay attack. In particular, the timestamp cannot be the old in the determined threshold.

  5. Check that the liveness criteria defined in the Liveness section are satisfied.

If a proposal is verified by all the checks, the countVote method counts each YES vote from the list of Votes.

4. Properties​

The consensus mechanism satisfies liveness and security properties as follows:

Liveness​

Liveness refers to the ability of the protocol to eventually reach a decision when sufficient honest participation is present. In this protocol, if n > 2 and more than n/2 of the votes among at least 2n/3 distinct peers are YES, then the consensus result is defined as YES; otherwise, when n ≤ 2, unanimous agreement (100% YES votes) is required.

The peer calculates the result locally as shown in the Section 3. From the hashgraph property, if a node could calculate the result of a proposal, it implies that no peer can calculate the opposite of the result. Still, reliability issues can cause some situations where peers cannot receive enough messages, so they cannot calculate the consensus result.

Rounds are incremented when a peer adds and sends the new proposal. Calculating the required number of rounds, 2n/3 from the distinct peers' votes is achieved in two ways:

  1. 2n/3 rounds in pure P2P networks
  2. 2 rounds in gossipsub

Since the message complexity is O(1) in the gossipsub channel, in case the network has reliability issues, the second round is used for the peers cannot receive all the messages from the first round.

If an honest and online peer has received at least one vote but not enough to reach consensus, it MAY continue to propagate its own vote — and any votes it has received — to support message dissemination. This process can continue beyond the expected round count, as long as it remains within the expiration time defined in the proposal. The expiration time acts as a soft upper bound to ensure that consensus is either reached or aborted within a bounded timeframe.

Equality of votes​

An equality of votes occurs when verifying at least 2n/3 distinct voters and applying liveness_criteria_yes the number of YES and NO votes is equal.

Handling ties is an application-level decision. The application MUST define a deterministic tie policy:

RETRY: re-run the vote with a new proposal_id, optionally adjusting parameters.

REJECT: abort the proposal and return voting result as NO.

The chosen policy SHOULD be consistent for all peers via proposal's payload to ensure convergence on the same outcome.

Silent Node Management​

Silent nodes are the nodes that not participate the voting as YES or NO. There are two possible counting votes for the silent peers.

  1. Silent peers means YES: Silent peers counted as YES vote, if the application prefer the strong rejection for NO votes.
  2. Silent peers means NO: Silent peers counted as NO vote, if the application prefer the strong acception for NO votes.

The proposal is set to default true, which means silent peers' votes are counted as YES namely liveness_criteria_yes is set true by default.

Security​

This RFC uses cryptographic primitives to prevent the malicious behaviours as follows:

  • Vote forgery attempt: creating unsigned invalid votes
  • Inconsistent voting: a malicious peer submits conflicting votes (e.g., YES to some peers and NO to others) in different stages of the protocol, violating vote consistency and attempting to undermine consensus.
  • Integrity breaking attempt: tampering history by changing previous votes.
  • Replay attack: storing the old votes to maliciously use in fresh voting.

Copyright and related rights waived via CC0

6. References​