My understanding is that in a private blockchain, the participating nodes verify and agree that the block is valid and only then add it to the blockchain.In this scenario, are consensus protocols (such as RAFT, PAXOS, etc.) needed? Am I missing anything here?
TL;DR Yes, consensus protocols are always needed in distributed systems where there could be multiple writers to the same data. When it is possible for multiple participants to simultaneously update their local state, it can result in two inconsistent versions which can't be merged together into a globally consistent state.
In the context of a blockchain, publishing a block is analogous to reading and writing to balances, and we wish to enforce the constraint that every account
balance >= 0 to prevent double spending.
Imagine that in the ledger state of block 4, I had 10 coins. Then in Branch A, I sent Alice 8 coins, but in Branch B I sent Bob 8 coins. If we tried to reconcile these two updates into one state then either I would have a balance of -6 coins, violating the
balance >= 0 constraint, or coins would have to be illegally created.
Consensus algorithms are designed to ensure that each node has a valid state consistent with other nodes. As explained by CAP theorem, during a network partition a consensus algorithm must either make the service unavailable (Read Only) or allow for the two partitions to potentially become inconsistant. This means that when designing or choosing a consensus algorithm, one must decide between either consistency of the data (e.g. preventing double spend) or availability (e.g. making a transaction).
Nakamoto consensus prioritizes availability such that during a network partition it will continue to process transactions, and after a network partition, the global state will eventually be consistent. It quantifies each state's total proof of work to decide which state is the correct state. If our node had previously only observed branch A but then received the blocks from branch B, it would calculate the amount of work done in each state to decide which branch to accept. This means that during a network partition, the state is still available to be updated at the expense of it becoming inconsistent. After the network partition is resolved, the inconsistent states are resolved by reverting some of the updates and applying the ones that lead to a state with more proof of work.
Other consensus protocols such as the proof of stake variant used in Tendermint will prioritize consistency, meaning that during a network partition attempts to update the state may fail, making the service unavailable. To ensure consistent updates to the state (i.e. creating a block) nodes that controll at least 2/3 of the stake, must agree to a proposed block within a timeout period. If too little stake agrees to the proposed update, it will fail and revert and a new proposal will begin. This is somewhat comparable to a 2 phase commit, but differs in that it can tolerate the failure of nodes controlling up to 1/3 of the stake.
Even in a trusted environment where all machines are behaving correctly, inconsistent states can arise due to network latency, as asynchronous messaging is comparable to short-lived network partitions. Keeping state consistent becomes somewhat more difficult where we have more complex constraints to uphold (e.g. ensuring consistent smart contract execution)
Other non-blockchain private distributed systems, must make the same trade-off between Consistency and Availability, Google's BigTable maintains availability and replicates updates to other nodes making it eventually consistent throughout their data centers, for coordination within a BigTable cluster it relies on a fault tolerance lock distributed service named Chubby which uses paxos during leader elections. However, It seems that due to the reliability of Google's private WAN (>99.9995% availability) and very accurate time-keeping, they have also built Spanner, the accuracy of their timestamps allow for updates to be ordered (or delayed if there is uncertainty about the order) such that an application's view of the data is consistent with the application's constraints and other invariants.
I highlight CAP theorem to explain how Nakamoto Consensus will always be available but subject to the eventual consistency, potentially allowing for a 51% attack. Other consensus protocols can provide finalization, but may not always be available opening them up to a system-halting DDoS attack. In the context of a private system, control of the hardware means that the distributed system can be virtually always available and shielded from DoS attacks, leading companies like Google to prefer the provision of consistency.