I read a book from one of the first European explorers in the Americas, his name was Cabeza de vaca. He interacted with many native tribes, including in the southwest, and commented how this one tribe who lived barefoot had black colored soles that were thick and hardened, and they didn’t need shoes to walk/run on any surface.