I mean, we have that. It's called an imei and you can't change it.
All that would be needed is for anyone selling a phone to provide the imei and some id to a govt service to assert that they are the current owner and intend to sell it for x price on y day. If you don't do this check and buy a phone, you're held liable if it is stolen. If you do, and it passes but later turns out to be stolen, automatically reimburse the buyer when you return it to the owner and make the seller liable to cover all associated costs in addition to the handling stolen property.
Most of this is already implemented for cars via vin, and doesn't require that an unelected central power has carte blanche to do whatever they want to it at any time.