Governments have been doing this for centuries (see passports, identity documents, birth and death certificates). Witnessing attempts by private entities repeated attempts to "solve" this problem and make a profit has shown me the limitations of free markets. Despite the complexity and sophistication of the implementation, it boils down to a record that's looked up by a trusted entity who attests the validity of the subjects identity, or not.