A logging service maintains an interdependent series of hash values for log entries submitted to the logging service by one or more clients. The logging service generates a hash value for each log entry based at least in part on the content of the log entry and a hash value of one or more previous log entries. The generated hash values are saved in an audit database by the clients. Clients may retain some, all, or none of the hash values based at least in part on the amount of auditing desired and the amount of storage space available in the audit database. The clients are able to verify the integrity of log entries submitted to the logging service retrieving the log entries from the logging service, recalculating the hash values, and comparing the recalculated hash values to the hash values in the audit database.