Very easy for governments.
Not really. Consider: old passports, multiple citizenship, emergency passports, identity cards which can be used as passports, etc.
With respect to the EU, as you know, there is to be a transition to biometric EU national ID cards, if countries have not already switched to them. The vast majority of countries already have. Some EU national ID cards are more useful than others, giving people online identities, for example.
Although I am culturally an American, I am also Croatian. I hold two citizenships. Croatia participates in the eID scheme [1]. Next time I go to Croatia, I am getting my eID, so I have an official identity on the internet. I am excited, as silly as it sounds.
[1] https://ec.europa.eu/cefdigital/wiki/display/CEFDIGITAL/eID
Bitcoin does this by forcing miners grind on a nonce to try to get a block hash below a certain value.
In this protocol, it appears that miners would do the same thing.
The difference is that the supply of passports is considered limited. A given person only gets one. That suggests that it might be possible to avoid the ever-increasing difficulty that Bitcoin has faced.
Bitcoin was intended as a one CPU, one vote system. This new one appears to be intended as a one passport, one vote system.
There are two main concerns with such a system:
1. security - how easy is it to forge passport identities?
2. privacy - how easy is it to link a signature to the original passport?
I suspect the actual utility of this protocol revolves around these two points.