With respect to reconciling data between a source system and one or more destination systems, a source agent obtains data from the source system. A destination agent obtains data from the destination system. The source and destination agents generate digests of the data obtained from the source and destination systems, respectively. The digests are provided to a consistency service for storage. The digests of the data stored at the source system are stored in a first tree data structure, such as a variant of a Merckle tree. The digests of the data stored at the destination system are stored in a second tree data structure, which might also be a variant of a Merckle tree. A comparison of the trees may be made in order to determine the consistency level of the data stored at the source system and the destination systems.