The Journal - a proposed syslog replacement

Actually, you're on the right track!

Make a central PUBLIC server that simply accepts and stores triples of form: <host_id, timestamp, hash> (host_id is UUID).

That's it. You can use this public server to periodically send your hashes. You lose (almost) no privacy, since log messages themselves need not to be replicated.