A method performed by a processing system includes reconstructing a metadata tree of a patient from a metadata tree journal, the metadata tree including a plurality of references to a corresponding plurality of encrypted electronic health records of the patient in an encrypted data store, and validating the metadata tree by comparing first integrity information of the metadata tree to second integrity information corresponding to the metadata tree journal provided by a metadata integrity validator.