Peer-to-Peer-based file replication is a proven approach to provide cooperative robust backup for data: if one peer does not have a specific datum, another one might. If enough peers participate, the overall system can survive isolated failures.

Applying this approach to distributed File Integrity Checking (or similar security-sensitive areas) requires that current and untampered information is distributed among the peers in such a way that a limited number of malicious peers cannot subvert or sabotage the overall system.

This paper presents a mechanism to provide such tamper-resistant replicated storage in a decentralised peerto- peer system where no component is trusted a priori. We present a system model for our mechanism, and discuss the threats and countermeasures used to detect tampering. We also give an analysis of various distribution strategies and their respective costs and benefits as observed in our research implementation.