How does the ripple protocol consensus algorithm (RPCA) work?

Consensus algorithms are a set of protocols through which all nodes in a distributed system can reach a joint agreement on the current state of the network. One of these protocols is the ripple protocol consensus algorithm (RCPA).

How does RPCA work?

In RPCA, each node maintains a unique node list (UNL). It is a subset of trusted nodes that the server will consider when determining consensus.

The probability of a node colluding with other nodes is $p_{c}$ and $n$ is the total number of nodes, then $p^{*}$(the probability of correctness) is calculated using the following Binomial distribution:

Thus while choosing a UNL, nodes try to minimize $p_c$and a higher number of nodes can also somewhat compensate for higher values of $p_c$.

RPCA works as follows:

• A user publishes their transactions and sends them to all the nodes in the network.

• Each node publishes a candidate set (as a proposal), consisting of all valid transactions it has seen that are not yet part of the ledger.

• Each node stores the candidate sets sent to it by the nodes in the UNL. All the candidate sets sent by nodes, not in the UNL are discarded.

• Every node checks all the transactions in its own candidate set and compares it with all the candidate sets (in the proposals) sent to it by other nodes in the UNL.

• If a transaction is present in the proposals sent by at least $50\%$of nodes on the network, it is included in that node's new candidate set, which is then sent as a proposal to other nodes on the network.

• In the next round, the threshold is increased to $60\%$and the process is repeated until we reach a final threshold of $80\%$.

• All the transactions approved by at least $80\%$of the nodes in the UNL of that node are applied to the ledger.

• This updated ledger version now becomes the last-closed ledger (LCL).

Correctness of RPCA

Strong correctness is guaranteed if the number of faulty nodes (Byzantine failures) is less than $20\%$.

Where $f$is the number of faulty nodes, and $n$is the total number of nodes in the network.

Weak correctness is when the number of faulty nodes (Byzantine failures) is between $20\%$and $80\%$.

Where $f$is the number of faulty nodes, and $n$is the total number of nodes in the network.