A very simple "proof-of-structure" from me inspired by BitLattice, is to use labyrinth function and collaborative proof-of-work with labyrinth function as one-way hash function.
Background: In proof-of-work, you could trivially have the work (finding hash with n initial bits set to 0) also validate the ledger, proving that a node stores the ledger. What you do is use the ledger itself as a cryptographic key for a hash function, and let the pre-image encode coordinates for a "labyrinth" through the ledger. On a sharded system, shards can pass their "work" between one another, whenever coordinates extend outside a shard (which they should all the time). This could support multiple "miners" per shard.