I believe that paper to be misguided.
The properties a good proof-of-work function needs are:
- Committing to blocks. The contents of a block should be a parameter that goes into the PoW, in such a way that altering the blocks invalidates the PoW.
- Cheap to verify. Just for performance of validators/nodes.
- Configurable difficulty to create. The rate of blocks should be possible to regulate.
- Progress-free. You want the rate of block finding to scale proportionally with the hashrate a miner has; if the fastest miner always wins, you introduce a centralization pressure. Any operation that consists of trying many inputs to a fast hash function and finding one whose outputs satisfies a condition is fine. However, if that hash function is slow (say, multiple seconds), a more than proportional benefit for faster miners is present.
- Not dependent on a central entity. Obviously.
- Not economically valuable. Proof of work only works when the work performed doesn't have monetary value beyond its function as PoW; if someone could be paid for their PoW (beyond subsidy/fee income from the chain it relates to) would alter the incentives. PoW is supposed to be an economic loss if no block is found/accepted; that is what drives miners to collaborate on the same chain, rather than trying to each work on their own fork.
- No non-obvious optimizations. This is the hardest one. To have a playing field that is as level as possible, ideally no non-obvious optimizations to the mining algorithm are possible, as this might benefit only larger miners/manufacturers that are able to afford the research. Worse, inventors of such optimizations (if substantial) may try to patent their ideas, and sell exclusive access to them (e.g. see ASICBOOST). Such optimizations may come in many forms; for example, it may be sufficient that blocks with a certain structure (say, certain 0 bits in certain places) are faster to hash; if 50% of blocks are 3x faster to hash, a smart miner would only search those.
If you take all these properties together, you find that all PoW that consists of a simple, fast, hash function whose output must be below a certain controllable value, is basically ideal. Ultimately, PoW is about proving you have burned a real-world resource (energy) in order to bet on a certain block being included in the chain. It doesn't matter what that function is, apart from being obvious and simple.
I don't see any advantage of a PoW based on Collatz orbits. It's likely full of non-obvious optimizations due to its mathematical structure. I also don't really see how a two-way peg could make use of it, or what it would accomplish.
