On 05/01/2014 12:16 AM, Jan Kasiak wrote:
Is there a design/technical reason behind btrfs using checksums separately per block, versus checksumming into a merkle tree?
We're using crc32c, which isn't suitable for detecting malicious data in general. The goal was just to find blocks that were not correctly returned by the storage. But, more below:
Where I'm coming from: there's a Linux kernel device mapper module called dm-verity, which let's you verify the contents of a block device using a merkle tree (at mount time you provide the root hash). For my project, I'm modifying the module to enable write support, but in order to maintain consistency in the event of a power failure, I have to do the equivalent of data journaling to a circular log (so I end up writing data twice). Where I'm going with this: I've been looking into what improvements could be made if this were implemented at the filesystem level, and btrfs looks like a good candidate. But it already has a checksumming scheme, which is incompatible with a merkle tree, and would be redundant if a merkle tree would be implemented as well. (zfs has a merkle tree, but from what I can tell, it doesn't expose the root hash to the user) What the example use case is: you want to detect malicious data tampering across the entire file system, so at mount time you provide the merkle tree root hash. You get back an updated version of the root hash when you unmount, which you store in a secure place until the next time you mount the filesystem. You can detect if anyone modifies your data in between mounts, and also if they modify the underlying storage while the filesystem is mounted.
We're actively looking into schemes to detect malicious changes to the FS data. A merkle tree could actually work fairly well. The part I was missing the last time I thought about this was the data blocks.
I was thinking that we'd have to include the checksum of the data blocks in the combined crc of the leaves in the filesystem tree.
But if we keep the crc tree (using stronger crcs instead), we can just do the merkle on the crc tree and the regular metadata blocks separately.
I think the biggest problem is that we wouldn't be allowed to write a tree node until all of its children had been crc'd. We've avoided these kinds of write ordering rules in the past because they tend to make things very difficult under memory pressure.
-chris -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
