Stone is a block first encountered at about 1600 feet of depth and becomes increasingly common as one gets deeper. It is impossible to dig through a stone (unless you completed challenge mode before starting and got the multidrill reward); instead you have to find a way around it, or use explosives to destroy it. 

A stone.