I came up with this quick idea for verifying the free space of vaults. It is inspired by the Chia thing @mav mentioned in the first post in this thread.
Let’s fill the space with pseudorandom data (seeded by the section id) in a way that the placeholder data for each storage block depends on some data from all previous blocks, or at least a sufficiently long pseudorandom list of such blocks. This makes it impossible to quickly recalculate a storage block without actually having all the free space before it.
Chunks are always stored in the last free storage blocks so as to not overwrite data required to regenerate the placeholder data for later blocks. Similarly, newly released blocks are moved to the end of the free space and then their placeholder data is recalculated from their preceding free blocks. (None of this requires actual copying, just a linked list of free blocks.)
Checking for free space is done by asking for the values of a list of positions within the free space the vault claims, and then comparing the answer to what the asking vault knows as the correct value.
It is a spot-check so vaults can cache a long list of positions and their correct values at initialization so as to allow for checks about blocks that the asking vault already uses for storage. The vault will then slowly “eat away” on this cached list during its lifetime. The cache will contain samples biased towards the end of the storage space because it’s expected that more of the earlier values (not yet used for storage) will be available for sampling directly, thus saving the more valuable cached samples.
The downside to this idea is that only vaults that are at least the size of the claimed free space of the target vault can verify that claim. This may not be such a show stopper as it may sound as I expect that even the largest vault won’t have more free space available than the total storage space of the smallest vault.
Potential attack: If someone owns multiple vaults in the same section, they can use a shared copy of the pseudorandom fill and thus pretend to have a multiple of the space they actually have. This attack probably applies to all free-space checking methods though.