I think they're required to verify the entire chain from the beginning (the Genesis block). I.e. trace back the entire transaction history for the whole network and prove no coins have been double-spent.