A server system with one or more processors and memory sends a verification request, to a client device, to verify that the client device is storing a data block, where the verification request includes verification parameters. In response, the server system obtains from the client device a first verification value for the data block. The server system compares the first verification value with a second verification value for the data block, where the second verification value was previously computed, in accordance with the data block and the verification parameters, and stored by the server system. In accordance with a determination that the first verification value matches the second verification value, the server system confirms that the client device is storing the data block.