Sounds like a great way to "treasure hunt" ! I like it. Probably a fairly advanced concept / late-stage content tho
Maybe fossils can simply be superimposed on existing textures (as in, make a fossil texture that's transparent where you don't have bone, then make the game paint that on top of an existing block). The implementation of something like that is probably what would be a "down the road" kind of feature
