I guess, too, that depends on what they are testing.
So antique citizenship laws required paternity descent - if your father was a citizen, you are. (IIRC, wasn’t this the case with UK citizenship too?) If so, then what you need is to prove who is your father’s father. So does 23-and-Me or Ancestry, etc. do Y-chromosome testing? And can you identify other male relatives -Paternal uncle or his son, grandson, etc.?
I do recall reading that while these genealogy sites do tell you who is related, it is not the same tests as a forensic DNA. However, you could do these tests to establish that it is worth the expense of doing a forensic test - if this is what the authorities need. (and assuming there’s no “pedigree errors” (the polite term) for anyone involved. To be certain, it would help to test multiple family members, especially if you have two paternal uncles and they have sons.
DNA-101: You have 46 chromosomes, 23 pairs, one of each pair from each parent (hence, 23-and-Me). you get a random 23 from each parent, either from their father or mother. For a male, you got the Y from your father’s 23rd pair, which is XY; if female, and X from Dad and one from mom’s XX pair.).
So statistically, you should have roughly 12 of your 46 (25%) are the same chromosomes as your grandfather. (and same from grandma) Meanwhile, your uncle or aunt will have another random mix, from each pair they may get the same your parent got or the other - so 2 siblings will have a 50% match, statistically (half of those from father, and half from mother, so 25% from father). Two half-siblings, 25%. For the next generation - cousins - again, each gets randomly one of each pair of each parents’ chromosomes, and in each case 50-50 if it’s the same as the cousin got. So two full cousins should match 25%, half from grandfather (12.5%) and half from grandmother.
So theoretically statistics say there should be about 6 of your 46 chromosomes should match your full cousin, give or take. hence, test multiple relatives. If you are both male, both from sons of grandpa, the Y will definitely match. Of course, that Y doesn’t prove much by itself since even if you are both male line descendants from the same great-great grandpa it will match. Hence the same test, multiple relatives, will give a statistical likelihood of relational distance. If the only pair of ancestors going back quite a ways that you have in common are grandma and grandpa and you share about 12% genetic material, it’s a safe bet.
And after all that, sometimes the chromosomes will split up and crosslink during cell division, creating a fractional match.
In the end, birth certificates and marriage licenses are usually the way to go. If you can find relatives, especially still in the old country, they probably have an idea where grandpa and mom or dad were born.