It is here that proof of work is a terribly BAD cryptographic security. You can't find worse. In as much as consensus FINDING can be done with just any sufficiently fair and random way, past consensus securing should be done with better cryptographic means than proof of work.
Options are limited when it comes to distributed consensus obviously. What's better?
In bitcoin, and in several other crypto, one has confused several different functions, to bring them together in one single thing, and I think it is quite obvious now, with hindsight, that this was a bad idea.
The different functions that PoW has been assigned to, are these:
1) burning seigniorage for new coins. The ability to print "money out of thin air and get its value" (seigniorage) has always seen as a bad trait of any monetary system ; in fact, it is the sole justification of "sound money doctrine", namely that NOBODY should be able to print money because of seigniorage. The Austrian school considered gold, that came from "long ago" as an acceptable sound money, because nobody could "print" gold - and mining gold was about as costly as what it was worth. If you make a new currency, of course you have to "print" it, and bitcoin's way of killing the seigniorage was exactly, mining with PoW: you got bitcoin's value, but you had wasted about the value you obtained in hardware and electricity.
==> this is a sensible use of PoW
2) allowing new users to compete for coins without being in the "old boys network". PoW allows just anyone to create coins, without permission or acceptance or whatever.
==> this is a sensible use of PoW
3) consensus formation. This is already somewhat more doubtful. NORMALLY, all transactions that are transmitted over the network, should simply be part of the consensus, apart from double spends, in which case, one has to decide "arbitrarily" which of the two double spends, if any, should be part of the consensus. One should also include, in the consensus, who had the right to win coins through PoW.
==> this has nothing to do with PoW a priori. In case there's a doubt, a random, but agreed-upon decision should simply be taken.
In fact, consensus formation is almost trivial apart from double spends close in time so that they arrive in different orders at different parts of the network, which is the "hard part" to solve, but which could in fact be solved easily: if ever there is a double spend in a relatively close interval of time, the spending address is blacklisted, and the coins are lost for ever, which would be a serious disincentive to double spend. Without double spends, the consensus formation is trivial: it is the full list of all transactions, and the order doesn't matter.
4) cryptographic securing of the consensus formation. In as much as the consensus is "the biggest set of transactions", there's in fact not much securing to do. It is the possibility of *excluding* transactions that needs cryptographic securing, so that nobody *excludes* old transactions. In as much as it would be "the biggest list", no cryptographic securing is in fact needed, but if the list has special requirements, it needs to be secured once the list is accepted generally.
In fact, it is the severe consensus mechanism, to put everything in a block chain, that needs cryptographic securing, and here, PoW is really bad. Just any digital signature scheme would be better because cryptographically more secure. The whole of bitcoin's drama comes from the fact that the PoW, which was meaningful for coin creation, was also used as a very severe consensus decision mechanism, and as a cryptographic securing of this very severs consensus decision, leading to the mining industry and the uselessness of network nodes.