The Great Wall of China was built by labourers making and laying blocks, many of them providing their labour to meet regional tax quotas. They marked sections showing who built which section. This makes it the first proof of work block chain.
More temporary structures used palisade fences of wooden posts, the remains of these posts giving us the first proof of stake.