Changing the proof of work algorithm

[Mark Friedenbach 92]

I would like to gather community opinion regarding a possible change to freicoin's mining algorithm. Right now we use the same proof of work algorithm as bitcoin, non-merged mined double-SHA256. I have for some time been an advocate of switching to a newer proof of work algorithm that has better protections against mining industry centralization, and which avoids price- and difficulty-based swings in hash rate between bitcoin and freicoin.

However it has until now been thought that changing the proof of work for a chain is necessarily a hard-fork change, which I would be hesitant to support for a variety of reasons. But it turns out that's not the case! I recently invented a mechanism for phasing in a proof-of-work change as a soft-fork, with a transition between the two over months or more likely years that gives safety for the old clients during the transition, and is not too complex of a change either. So we now have the capability to change proof of work, to something slightly more ASIC resistant with better decentralization effects and less competition with bitcoin. Without getting lost in the weeds, I am specifically considering the Cuckoo Cycle proof of work, which you can read more about here:

https://github.com/tromp/cuckoo

Is this something the community could get behind? The parameters of the soft-fork transition would be set such that it would not invalidate any investment people have made into sha256d mining during the lifetime of the miners. I'm thinking 2-3 years for a full transition, during which time the reward does a linear transition from sha256d to cuckoo cycle. And it would probably take six months to implement anyway.

[fedde 311]

This is interesting as most gear has lifetime about 1-2 years so if it can be done over a time period I think it would be positive. 

As pool runner i assume we can run two pools, one for each algorithm? 

[Mark Friedenbach 92]

That's correct. There would be different sets of miners for the two algorithms. Pool services would run different pools for each.

The length of the transition period and the allocation of subsidy between the old miners and the new miners is arbitrary in a sense. There's no technical reason for the choice, just soft factors like making sure that nobody is wronged by the transition and the community split as a result. A straightforward choice is to have a linear transition so that the subsidy given to sha256d miners is slowly stepped down and given to cuckoo cycle miners, over the course of 2-3 years.

[fedde 311]

Sounds good to me. It similar I have seen on some coins that use Sha and scrypt to solve blocks. 

Will have pool ready for second also. 

[Arcurus 331]

having an own mining alg sounds good, because in the long run if there are Freicoin specific asics, they would have an incentive to stay helpful to the coin.

It could be even a good idea to have both algs running on the same time, therefore we should think about never fully abandon SHA256.

Having it asics resistant is no need, i think its good to have ascis mining the coin, otherwise again lot of general purpose mining power can switch to mine the coin and also botnets can mine the coin....

To miner centralisation, i think a mining alg change will not solve that long. Centralization will always happen in the industry. If asics are easy to produce for the alg the hope is, that competition will always be big enough that no monopoly happens.

If you ask me, to solve the centralization problem switching mining algs will never help, either you make it genera purpose, in this case the current companies like intel / asus / amd dominate, or you make it special, in this case asic manufactures dominate.

A true solution to the mining centralization problem would be to implement Freimining, in short give subsidies to decentralized community driven miners and or Freicoin related hardware producers

Or change to a combination of proof of work and proof of stake / proof of member / or something like stellar / ripple consensus

this can also be implemented as a soft fork as maaku described above.

 

By the way, if you switch the mining alg it would be good to switch also to a better difficulty alg.

 

Some ideas to that:

 

Why use a two way proof of work architecture?

The main reason why to use a two way architecture is to not be dependent on one mining hardware provider. In case if needed one mining algorithm can be replaced more easily. Another reason is to allow more people to have access to new coins. One alg could for example be an alg that is easy to use with general purpose computers and therefore allow a wide access to new coins. The other alg could be easy for asics, so that special asics are created that have an interest in the health of the coin.

 

Isn't a double spend more easy in a two way proof of work architecture?

In the end transactions are secured through the economic value given as reward o the miners. A two way proof of work architecture doesn't change that. Proof of work in layer 1 is used to make sure that is is economically expensive to undo transactions. A layer  2 can make sure that transactions can be treated as good as irreversible once confirmed in layer two.

Further by default blocks that are mined before the target blocktime is reached can be required to have a higher difficulty or be rejected by the network (see below)

 

How can a simple difficulty algorithm look like?

First of all it is good to clarify the two design goals a difficulty algorithm should fulfill. First it must make sure, that the difficulty adapts if the mining power increases or decreases. Second it must make sure that in the long run the blocks created per time period is ¨fixed¨.

The first goal could be reached through this:

- the difficulty is increased / decreased each block by up to 10% if the last 10 blocks have been in average faster / slower then target block time

 

The second goal could be reached through this:

- if 10 blocks more / less then the expected blocks are created the target block time is set to 0.8 / 1.2 the target blocktime.

 

A third optional goal could be to make fast block creation more difficult:

- a node only propagates a block if the difficulty is higher then: target difficulty * target block time / time since last block. At minimum a block must have still at least the target difficulty. With this a block that is double too fast would need double the difficulty to be propagated in the network. Four times to fast would need four times the difficulty. 

This would also reduce the problem of mining  centralization and therefore give an opportunity to reduce the block-time, because with the above alg miners would have in average  more time to receive the new block. On top of that through making the required difficulty time based this would allow a much more stable blocktime even if using the same mining alg like other coins. In short No more incentives for drastic hash increase or decrease.

 

For example, normally the difficulty does not change relative to the last blocktime. Therefore the difficulty is either that low that the coin is the most profitable to mine and therefore attracts the majority of the mining power or that high that the coin is not the most profitable coin to mine. This leads normally to sudden and drastical hash increase or decrease. A drastic decrease in hashpower is even more fatal, because this normally slows down the difficulty adoption. Economically no miner would have an economic incentive to mine such a coin to bring down the difficulty, which makes the coin dependent on good willing miners that make an economic lost.

In case the above alg is used if the last blocktime is too low and therefore the difficulty too high, miners will mine simple another coin (or stop mining). With time if the last blocktime becomes higher, the difficulty will decrease and therefore the coin becomes lucrative to mine until the next block is found.    

 

[Mark Friedenbach 92]

Regarding ASIC reistance, it's a goal that in its strongest form is impossible. You cannot have an ASIC-reistant proof of work, and if someone is trying to tell you otherwise that's a good indicator you're dealing with a crank (or they're trying to sell you something). Anything you can do with a general application-agnostic circuit you can do more efficiently in a specialized circuit. This follows straight from information theory.

HOWEVER, there is a weak form of ASIC-resistance which is interesting to note. With double-SHA256, GPUs are 100-1,000x more efficient than CPUs, FPGAs are 100-1,000x more efficient than GPUs, and ASICs are an additional 10-100x more efficient. Double-SHA256 ccould hardly be more ASCI-friendly. So the weak form of ASIC-resistance is an algorithm which, when implemented in specialized hardware, has the smallest possible advantage when when compared against consumer hardware like vector CPUs or GPUs. With Cuckoo Cycle, for example, the advantage gained by ASICs over GPUs is only an (estimated) 2-4x. Compare that with the more than thousand-fold improvement double-SHA256 sees.

Why does this matter? Because in the event of an attack on the network, a disadvantage of 2-4x can be overcome by a wide decentralized base of users, perhaps motivated by investors favoring the decentralized chain over the centralized one (e.g. look to the price difference between BTC and BCH). The decentralized chain can withstand an attack by retreating to a popular base of GPU miners. With double-SHA256 however this isn't possible. If non-ASIC bitcoin users wanted to revolt against the ASIC industry, they would find that even if everyone mined they'd only get a block on their chain once a month or so. It would take the better part of a century to see the first hash rate reduction. Even with freicoin's faster difficulty adjustment it would still take years. That's not even close to being a realistic alternative, and therefore any resistance to centralization forces all the problems that come with hard forks.

Weak ASIC resistance doesn't do anything to boost decentralization, in first order analysis. You'll still see creation of ASICs and their adoption within the mining industry. However it does enable fallback options whose very existance prevents the ills of centralization from happening. These are 2nd-order game theoretic effects.

We've discussed both proof of stake and paxos consensus models before. The claims of these systems are analagous to perpetual motion machines. I really have no interest in going that direction, and would spilt ways with freicoin if that's what the community wants.

> Why use a two way proof of work architecture?

It's a necessary fact of being a soft-fork. The old clients need to see progress being made on double-SHA256 blocks. That's the only reason.

> Isn't a double spend more easy in a two way proof of work architecture?

No.

> How can a simple difficulty algorithm look like?

That's a bit isomorphic, but the difficulty algorithm would probably look a lot like the one in Freicoin today. The parameters could probably be better optimized, but ultimately the choice of a linear filter was correct is justified by its performance.

[Skaro 129]

I suppose, in terms of a discussion, perhaps the choice of changing the mining algorithm is related to what people want for a Freicoin's future.  For example, if Freicoin were to become a sidechain coin, it should be merge minable (I assume). Or, if we are gonna have a transition period, will this prevent other upgrades during that time?

I don't think anyone actually financed buying an ASIC to mine Freicoin recently. Rather, they are just pointing old equipment to Freicoin. People could just literally point their CPUs or GPUs at Freicoin the next day after a hard fork. I'm not sure if the software is available for that, however.

If Mark wants to use Freicoin as a test bed for the technology, thats fine too and may give some advertising to the coin.

All that aside, I do generally think the cuckoo cycle is cool. If that's the only thing that changes about Freicoin, I do think it is a positive change because its silly that my 3 Ths ASIC is unprofitable on Freicoin.

 

 

 

[Mark Friedenbach 92]

Sidechains and merge mining have their own intractable problems, and in particular they do not mix together very well (merge mining makes the sidechain problems worse, and vice versa). If freicoin were to be sidechain to another chain, it would have to either (1) be a separate proof of work, or (2) have all full nodes of both chains validate each other, an idea more commonly known as extension blocks. Setting freicoin up as a separately mined chain with a different proof of work (and therefore different hardware distribution) prepares for the first possibility while not excluding the second. But in reality I expect that freicoin will remain different from bitcoin and other coins, and not an active sidechain, except perhaps via strong federations or higher level protocols using cross-chain payment channels.

There is at least one person I know who has made a recent ASIC purchase for freicoin mining, and I would hate to invalidate that investment. But the transition period also serves the purpose of having incentive for securing the sha256 portion of the network for some time to come, which helps protect other full nodes. In fact, current full nodes will be able to sync indefinitely into the future, even after the transition is complete, as the difficulty will have transitioned back down to diff-1, and all cuckoo cycle blocks will require a follow-up diff-1 sha256 block in order for the cuckoo cycle miners to actually collect their payment -- the trick which makes the soft-fork deployment possible.

[Darius1 5]

@ Mark Friedenbach      Thank you for your hard work and time spent on Freicoin

[Skaro 129]

@Mark Friedenbach  "via strong federations or higher level protocols using cross-chain payment channels". Is this a solution to crypto scaling problems in itself? 

Like the present world using different currencies and exchange, 1000 different alt-coins, 1000 different blockchains and miners etc. Thus 1000x more capacity. Then, when you need to pay in another coin, there is an atomic swap?

[Mark Friedenbach 92]

Yes and no, mostly no. “Sharding” is the term for splitting a single block chain into multiple chains sharing the same assets, which solves a latency problem fundamental to scaling and improves resistance to certain forms of adversarial attack. But a miner must still track all chains, or else forego the income involved. If we have so much activity across all the chains such that a single person cannot run a full node on ALL chains using the same PoW, then the whole system can no longer be decentralized.

But things like efficient atomic swaps using adapter signatures, HTLC payment channel updates, and submarine swaps mean that we don’t need to strive for direct interoperability so long as we have some level of crypto compatibility (same OP_HASH256 and same ECDSA or Schnorr signature algorithm).

[Skaro 129]

"If we have so much activity across allthe chains such that a single person cannot run a full node on ALL chains using the same PoW, then the whole system can no longer be decentralized."

Wouldn't that be more decentralized; ei, numerous small groups taking care of their own transactions, like serperate countries, banks, and credit cards today?

 

Why have seperate chains sharing the same asset? The whole point is to share the work load and only communicate when necessary?

 

I appreciate of course that you have looked into the details, where I am doing more... beer talk!