You can efficiently verify that two replicas have identical data using a Merkle tree (Xu, p. 104; Kleppman, p. 829).