Back when the Constitution was chipped into stone, I doubt there were birth certificates in large scale useage.
Mostly it was a Family Bible that kept the family tree?
Since that was a religious thing? The Church and State thingy applied.
(Granted time travel may have been involved at this point)
Most people wore a large stone around thier necks back then with thier birth information.
(A fact the Government denies today)
This created 'Stoners' or document forgers as we now call them.
When the Stoners got really going doing thier thing?
The Gov started useing paper.
(Roughly around the time Gold was grabbed and paper was the new currence)
At this same time, mis-information was sent to all foreign countries so anyone NOT born here would look like fools.
If you were born here? You weren't told as it was eyes only information.
(Did I mention I have 'Warped' tattooed on my wrist?)