> because they do not rely on a private key - and thus everyone can verify work that has been claimed to be done.

Huh?

While, yes, it is necessary that everyone can verify that the work has been done, one can certainly check that a signature signed by a private key, is a valid signature corresponding to a given public key.

My understanding of the idea proposed, is that the mining here would consist of, instead of hashing (hash of previous block + transactions + nonce-for-which-many-values-are-tried), and succeeding if the hash is small enough, just the same thing except with signing instead of hashing.

Though, the public key would need to be specified, either along with or as part of the block, or maybe if it had been used before, just referenced, which, as public keys are iirc not all that small, might cause some issue? (Not sure how much data is in a typical block in existing chains.)

I agree with the other issues you mention (privacy, incentive to steal passports, wearing out the chip).

While I don’t think this is probably that great of an idea, I would like to describe some possible mitigations for some of the issues.

One person mentioned that, if one key was used substantially more frequently than others, which are also actively being used, that that could be taken as indication that they had extracted their private key and are running on alternate hardware, and could thus be penalized in some form (e.g. there could be a cap or on the rate at which a given private key’s blocks could be accepted. If each chip has a fixed maximum hash rate, then if they are producing blocks at a rate which would be statistically implausible at the given difficulty level, they can’t mine more blocks until it would be plausible).
(This countermeasure of course relies on the lack of privacy.)

As for wearing out the NFC chip, I imagine that it could be possible to mitigate this somewhat by limiting how frequently it is useful to call the chip.

How could this be done?
Suppose we make the hashing algorithm a little more complicated, in order to make it so that for each block, only a fraction of the miners are able to use their hashing power:
To mine a block, first sign (hash of previous block + the current time, but discretized to intervals a little shorter than the desired block time), with no nonce. If the value of this signature is small enough, only then can you proceed to the next step. (In case no one gets a signature small enough for this step, the difficulty for this step depends on the time since the previous block, such that for a sufficiently long time it is certain to succeed).
Then, if the previous step succeeded, make signatures of (the signature just mentioned + the transactions to include + a nonce).

(This part would be where the limit on rate of work would have to be applied)

The single check per block time would not contribute nearly as much wear to the chip, and if the fraction of miners which pass the first step were to be adjusted based on the number of active miners, the average number of attempts for the second stage could be kept relatively low.

It seems like this would keep the average rate of uses of the chip, while still much higher than was intended, still fairly low.

A possible exploit to what I just described!: if there are multiple latest blocks, then in the first stage, or generally if there is a fork (possibly from an attack), then if the block which you would ordinarily consider the current head of the chain, doesn’t result in you getting past the first stage, because you aren’t doing anything else with your hashpower, you may as well try signing on some alternative head! This appears to break the incentive to always attempt to mine on the true/main chain!

That’s a problem!

(Essentially “which head to use” ends up playing the role of the nonce.)

Two possible solutions to this:

1) because these are signatures, not hashes, if one does this, it is possible for others to prove on the main chain that one has done this, and therefore it can be punished.

2) Have the first check not involve the previous block at all, just include the time, and have the second check (the one which includes the nonce) be the one to include the hash of the previous block.

Notably, with the second case, one can compute far ahead of time what difficulty levels would result in being a candidate for the second check. This would, I suppose, make some things easier for miners to plan? It also might open up some attacks by giving people an incentive to alter the difficulty at different times?

But, I suspect that if we are to use an assumed-unique-per-person keypair system, I suspect we don’t even need PoW at all? Because it already solves Sibyl attacks, and in that context aren’t there already older solutions to reaching consensus on event orders? I could be wrong about that.

Also, yes, the incentive to steal passports is an issue.
However, is the incentive to steal mail-in-ballots or buy votes not also an issue? When we attempt to restrict the distribution of how much influence people have over something that people want to influence, it produces an incentive for people to transgress against that restriction in order to gain more influence.

General-purpose-influence-over-the-world has a kind of gravity, the more one has, generally, the easier it is to obtain more. Any substantial attempt to go against this tendency is likely to encounter difficulties.

That doesn’t mean it isn’t ever worth it.