This is a common misconception. In order for a Proof-of-Work algorithm to be useful, there must be an opportunity cost (penalty) to mining on the wrong chain. If the mining algorithm pays off anyway it cannot be used.
Unless the miners themselves benefit from the work, there would still be an opportunity cost to them, no? If it happens to be useful to someone else that shouldn't matter, right?
If it is useful enough that someone is willing to pay for it as a service, then it fundamentally changes the incentive model and voids the security it provides.
Whether or not there's an opportunity cost does matter, but why should this mean that the mining algorithm "paying off anyway" mean it can't be used? If the mining algorithm has an independent payoff whether or not you mine on the main chain, then there's still the same opportunity cost of the mining rewards.
With a PoW that has "external rewards", the cost of attacking the chain falls in proportion to the external reward. You are correct that it does not fall to zero.
Patents allow mathematical research to be excludable and thus not a public good.
Now one can argue that mathematical patents provide more costs than benefits, which is a line of debate I am certainly open to. End that, and math research would be a public good.
But in the system we have now, a huge amount of mathematical research has generated a significant amount of money for very many people, from the RSA algorithm to Penrose patenting his tilings (and getting money from toilet paper makers that used his aperiodic tilings to make their TP more fluffy [1])
What I think you mean to say is that the market consistently undervalues mathematical research. Unfortunately it's not so easy to actually demonstrate, because given the huge amount of math research produced, only a very small amount of that ends up being useful in the future and often the original discoverer is long dead. This is similar to the situation with other arts and sciences. A small number of people drive the field forward and the vast majority of scientific publications are basically filler. Certainly the world would be better with more effective funding mechanisms that we have on offer, which is basically a game of capture-the-grant.
The penalty is still there you pay the electric bill and it consumes time, but you would donate some cycles for useful scientific computational tasks without any benefit for yourself. If such an algorithm exist, then I don't see why this couldn't be used as Proof-of-Work algorithm.
PoW works because showing a correctly mined block, ie one with a nonce that satisfies the many-initial-zeroes hash, proves that you on average (you can be short term lucky) have a used a certain amount of computing power.
It proves it because with the selected algorithm, there's no known shortcut to just doing a load of hashes, so if you found one it means you did a lot of hashing.
What problem would you insert instead that had the same properties?
We should also not forget that it gets harder and harder for the same benefit. Any amount of energy can be poured into a PoW system. Invent fusion, use it all in crypto.
"Rent computational resource" could work with a verification of resource(s) step at the end of a set duration (block) and all of the computations performed using fully homomorphic encryption. If after the beginning of a block a random start time up to some max (~10 min) was selected for which the proving nodes would perform an operation to verify the resources were available and calculate the block hash instead of continuously burning, then at that starting time and for a set proving duration the verification algo would run and at the end the block would be distributed. Given the FHE was either running a paying program utilizing rented resources or the verification algo continuously, then it should not be possible to tell when the verification algo starts and stops. The non-FHE "gas" alternative that incentivizes performing program results to include in the hash has to have enough of an expected value that it would be prioritized over using the time to further calculate a minimal hash and the associated expected value for finding it without those gas incentivized transactions. The question is the FHE option more efficient than gas?
PoW algo could be Hashcash, which has not been "exhausted"? Not sure what "usage varied" means? To further elaborate on the proposal, from the block start time to verification start time x the miner would run say Mersenne solver, then from x to block end the miner would run verification algo, i.e. Hashcash. The Mersenne solver would have to run with less than or equal to the resource usage of the PoW algo, and if unable to equal then the PoW could also for example run in background. The computation is encrypted and the network traffic is encrypted. So, no way to determine that the verification algo time allocation is being "varied". Gas could still be used to prioritize work, but the idea is that most of the time the PoW algo is not running, and some other more economic algo is running. The PoW is being used for Proof of Capacity, unlike the claimed Chia coin PoC that continuously uses the capacity in a PoW manner rather than proving it and then offering or allowing it to be used for some other purpose in an interim. If the issue is the desire for the economic algo to be able to run continuously, then the nodes could be split into 2 or more groups. For two groups, one would run from time 0 to x and the other from 0 to y with x < y with y including the block from the x group in the block y produces. The x group would continue from x+verify duration to x_2+verify duration and including the y block in the x_2 block output, and so forth.
Sorry, I thought you meant the machines would be doing "real" work on behalf of some person renting it, rather than making Mersenne primes. If you have a fixed problem like that then of course it won't run out.
The problem then is more economics, who has an incentive to discover more Mersenne primes?
PoW is a closed feedback loop system. Doing PoW yields you a reward, that reward pays for energy, that energy runs your PoW. If PoW yields you anything other in addition to normal reward - for you as a miner the only rational thing is to run more PoW with it to get more rewards. That in turn will simply bump the difficulty such that any additional benefit yielded will match the additional required energy expenditure to get the reward.
