Can we benefit from Collatz conjecture proof of work to enhance bitcoin utility?

F Bocart 2018:"Inflation Propensity of Collatz Orbits: A New Proof-of-Work for Blockchain Application" argues that Collatz conjecture-based proof of work will provide a greater number of nonces than SHA256.

The paper also provides a python script example, based on the bitcoin Genesis block.

This script was the tested by H Mousa 2019 paper titled: "Performance Evaluation of Proof-of-Work and Collatz Conjecture Consensus Algorithms", the paper argues that the transaction using this method can "takes only (1/1000) th of the execution time that is required for PoW".

I think that a two-way pegged offchain utilising such a method can benefit the bitcoin network.

  • The second paper linked above seems to have a lot of inaccuracies/misunderstandings, and non-standard terminology. Its kind of tough to make sense of.
    – chytrik
    Oct 1 '21 at 1:06

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.

  • So far we have no optimizations due to Collatz sequences mathematical structure. But for sure we have documented mining optimization (“ASIC-BOOST”) that allowed to mine Bitcoin blocks faster than the network average by taking advantage of a technical flaw in SHA-256.
    – Tom
    Dec 22 '21 at 12:10

I see few advatages shown in cited papers:

  • PCC takes only (1/1000) th of the execution time that is required for PoW,
  • PCC has a nearly consistent execution time,
  • multiplication of proofs-of-work may help to mitigate some types of attack based on SHA-256,
  • algorithm is easy to implement in code since the underlying problem is made of simple arithmetic operations,
  • the geometric distribution allows a very convenient tailoring of the computational complexity.

In my opinion, this is an interesting and promising PoW method.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.