Quote from: aliashraf on June 08, 2018, 02:37:57 PM

Proof of Collaborative Work

A proposal for eliminating the necessity of pool mining in bitcoin and other PoW blockchains

Motivation
For bitcoin and the altcoins which are based on common PoW principles, centralization of mining through using pools, is both inevitable and unfortunate and puts all the reasonings that support the security of PoW in a paradoxical, fragile situation.

A same problem does exist with PoS networks. Things can get even worse there because of the fact that most PoS based systems enforce long run deposit strategies for miners that is highly discouraging for them to migrate from one pool to another because of the costs involved.

The problem of solo mining becoming too risky and impractical for small mining facilities appeared in 2010, less than 2 years after bitcoin had been launched. It was the worst timing ever, although Satoshi Nakamoto made a comment on bitcointalk about first pool proposals, it was among the latest posts Satoshi made and he just disappeared few days later from this forum, forever, without making a serious contribution to the subject.

This way, the confused community came out with an unbelievable solution for such a critical problem, a second layer centralized protocol, named pooling, boosted by greed and ignorance, supported by junior hackers who as usual missed the forest.

Bitcoin was just 2 years old when pooling age began and eventually dominated almost all the hashpower of the network.

A quick review of Slush thread in which Satoshi has made the above referenced reply, could reveal how immature and naive this solution was and has been discussed and how it has been adopted: In a rush with an obvious greed.
Nobody ever mentioned the possibility of an algorithm tweak to keep PoW decentralized. Instead everybody was talking about how practical was such a centralized service while the answer was more than obvious:
Yes! you can always do everything with a centralized service, don't bother investigating.

Anyway, in the thread, one couldn't find any arguments about the centralization consequences or the possibility of alternative approaches including the core algorithm improvements Shocked

I think it is not fair. PoW is great and can easily be improved to eliminate such a paradoxically centralized second layer solution. This proposal, Proof of Collaborative Work (PoCW) is an example of inherent possibilities and capacities of PoW. I didn't find any similar proposal and it looks to be original but If there is a history, I'll be glad to be informed about.

The Idea is accepting and propagating works with hundreds of thousands times lower difficulties and accumulating them as a proof of work for a given transaction set, letting miners with a very low shares of hash power ( say of orders like 10^-6) to participate directly in the network and yet experience and monitor their performance on an hourly basis.

Imo, now, after almost a decade being passed, Moore law has done enough to make it feasible utilizing more bandwidth and storage resources and it seems to me kinda hypocritic to make arguments about 'poor miners' and pretending to be concerned about centralization threats and making excuses so for rejecting this very specific proposal that although increases the demand for such resources, can radically disrupt current situation with pools and centralized mining.

This proposal is mainly designed for bitcoin. For the sake of convenience and letting the readers to have a more specific perception of the idea, I have deliberately used constants instead of adjustable parameters.

Outlines

An immediate but not practically feasible approach can be reducing blocktime (along with proportional reduction in block reward). Although this approach, as mentioned, can not be applied because of network propagation problems involved, but a very excellent consequence would be its immediate impact on the scalability problem if employed, we will use it partially (reducing blocktime to 1 minute compared to current 10 minutes period).
As mentioned earlier (and with all due respects to Core team), I don't take objections about the storage and network requirements implications and consequences of reducing blocktime as a serious criticism. We should not leave mining in hands of 5 mining pools to support a hypothetical poor miner/full node owner who can not afford installing a 1 terabyte HD in next 2 years!.
Also note, blocktime reduction is not a necessary part of PoCW, the proposed algorithm, I'm just including it as one of my old ideas (adopted from another forum member who suggested it as an alternative to infamous block size debate and later has been developed a bit more by me) which I think deserves more investigation and discussion.
PoCW uses a series of mining relevant data structures to be preserved on the blockchain or transmitted as network messages
- Net Merkle Tree: It is an ordinary Merkle hash tree of transactions with the exception that its coinbase transaction shows no block reward (newly published coins) instead the miner charges all transaction fees to his account (supports SegWit)
- Collaboration Share: it is a completely new data structure composed of following fields:
  - 1- The root of a Net Merkle Tree
  - 2- Collaborating miner's wallet address
  - 3- A nonce
  - calculated difficulty using previous block hash padded with all previous fields, it is always assumed to be at least as hard as 0.0001 compared to current block difficulty
- Coinbase Share: it is new too and is composed of
  - 1- A Collaborating miner's wallet address
  - 2- A nonce
  - 3- A computed difficulty score using the hash of
    - previous block's hash padded with
    - current block's merkle root, padded with
    - Collaborating miner's address padded with the nonce field
  - 4- A reward amount field
- Shared Coinbase Transaction: It is a list of Coinbase Shares
  - First share's difficulty score field is fixed to be 2%
  - For each share difficulty score is at least as good as 0.0001
  - Sum of reward amount fields is equal to block reward and for each share is calculated proportional to its difficulty score
- Prepared Block: It is an ordinary bitcoin block with some exceptions
  - 1- Its merkle root points to a Net Merkle Tree
  - 2- It is fixed to yield a hash that is as difficult as target difficulty * 0.05
- Finalization Block: It is an ordinary bitcoin block with some exceptions
  - 1- Its merkle root points to a Net Merkle Tree
  - 2- It is fixed to yield a hash that is as difficult as target difficulty * 0.02
  - 3- It has a new field which is a pointer to (the hash of) a non empty Shared Coinbase Transaction
  - 4- The Shared CoinBase Transaction's sum of difficulty scores is greater than or equal to 0.95

Mining process goes through 3 phases for each block:
- Preparation Phase: It takes just few seconds for the miners to produce one or (barely) 2 or 3 Prepared Blocks typically. Note that the transaction fees are already transferred to miner's wallet through coinbase transaction committed to the Net Merkle Tree's root for each block.
- Contribution Phase: Miners start picking one valid Prepared Block's Merkle root, according to their speculations (which become more accurate as new shares are submitted to the network) about it to get enough shares eventually, and producing/relaying valid Contribution Shares for it.
  As the sum of the difficulty scores for a given Prepared Block's Merkle root grows we expect an exponential convergence rate for the most popular Merkle root to be included in Contribution Shares.
- Finalization Phase: After the total scores approaches the 0.93 limit, rational Miners would begin to produce a Finalized block
Verification process involves:
- Checking both the hash of the finalized block and all of its Shared Coinbase Transaction items to satisfy network difficulty target cumulatively
- Checking reward distribution in the shared coinbase transaction
- Checking Merkle tree to be Net
UTXO calculation is extended to include Shared Coinbase Transactions committed to finalized blocks on the blockchain as well
Attacks/forks brief analysis:
- Short range attacks/unintentional forks that try to change the Merkle root are as hard as they are in traditional PoW networks
- Short range attacks/unintentional forks that preserve the Merkle root but try to change the Shared CoinBase Transaction has zero side effects on the users (not the miners) and as of redistributing the shares in favor of the forking miner, they are poorly incentivized as gains won't go anything further than like %2-%10 redistribution ever.
- Long Range attacks with a total rewrite agenda will fail just like Traditional PoW
- Long Range attacks with partial coinbase rewrite are again poorly incentivized and the costs won't be justified

Implementation

This is a radical improvement to classical PoW, I admit, but the costs involved are fair for the huge impacts and benefits. I have reviewed the bitcoin Core's code and found it totally feasible and practical form the sole programming perspective. Wallets could easily be upgraded to support the new algorithm as well, but a series of more complicated issues, mostly political are extremely discouraging but it is just too soon to give up and go for a fresh start with a new coin, or just manage for an immature fork with little support, imo.

Before any further decisions, it would be of high value to have enough feedback from the community. Meanwhile I'll be busy coding canonical parts as a BIP for bitcoin blockchain, I think it takes like 2-3 weeks or even a bit more because I'm not part of the team and have to absorb a lot before producing anything useful, plus, I'm not full time, yet Wink

I have examined the proposed algorithm's feasibility as much as I could, yet I can imagine there might be some flaws overlooked, and the readers are welcome to improve it. Philosophical comments questioning the whole idea of eliminating pools don't look to be constructive tho. Thank you.

Major Edits and Protocol Improvements:

June 10, 2018 09:30 pm Inspired by a discussion with @ir.hn
- A Prepared Block should be saved in the fullnodes for a long period of time enough to mitigate any cheating attempt to avoid Preparation Phase and using non-prepared, trivially generated Net Merkle Roots.
  - Full nodes MAY respond to a query by peers asking for a block's respected Prepared Block if they have decided to save the required data long enough
  - For the latest 1000 blocks preserving such a data is mandatory.
  - For blocks with an accumulated difficulty harder than or equal to the respected network difficulty, it would be unnecessary to fulfil the above requirement.^*
  - Prepared Block and Preparation phase terms replaced the original Initiation Block and Initiation Phase terms respectively to avoid ambiguity
  Notes:
  ^* This is added to let miners with large enough hash powers choose not to participate in collaborative work.

reserved for future upgrades

This is a good technical proposal. Kudos!! All issues raised by commentators can be taken into account and addressed if not resolved already in the analytical model. More Grease to your elbow!

Quote from: anunymint on June 12, 2018, 04:27:57 PM

Quote from: aliashraf on June 12, 2018, 11:26:55 AM

The Shared Transaction Coinbase is not a part of the Header, its hash(id) is,

All the small proof-of-work solutions have to communicated and calculated before the winning block can be communicated. So that is up to 10,000 (if difficulty target is 0.0001) multiplied by the 64B size of a SHA256 hash, which is up to 625KB of data that must be communicated across the network for each 10 minute period. Thats not factoring in if the network is subdivided and miners are mining on two or more leader Prepared blocks, in which case the network load can be double or more of that.

Now I do understand that these proof-of-work share solutions are communicated continuously and not all at once at the Finalized block, but youve got at least four potential issues:

1. As I told you from the beginning of this time wasting discussion, the small miners have to validate all the small proof-of-work solutions otherwise theyre trusting the security to the large miner which prepares the Finalized block. If they trust, then you do have a problem about non-uniform hashrate which changes the security model of Bitcoin. And if they trust you also have a change to the security model of Bitcoin. And if the dont trust and attempt the validation, then theyre incurring more costs than they would in pools and be further marginalized.

2. All of these solutions still have to be validated in terms of Shared Transaction Coinbase, when the Finalized block is. Although the previously validated small proof-of-work solutions themselves do not have to be revalidated, the hash of all the small proof-of-work solutions has to be checked and the miner has to verify he already validated the solution for each one. This is also some overhead which can delay propagation because it adds up. Each node has to add this validation step before propagating to the next node in the P2P network. You ostensibly do not seem to fully appreciate how small verification steps add up in the propagation to form significant delays w.r.t. to lowering the effective block period to 10 and 30 seconds (as appears to me your design does) for the Final and Prepared block stages. Nodes do not propagate invalid block solutions (or any invalid data) because they would make the P2P network vulnerable to a DoS amplication attack.

3. Because the network can be subdivided on two or more leader blocks, the nodes no longer have an incentive validate and propagate the solutions on the block they are not contributing small proof-of-work solutions to. Presumably they have slightly better ROI if they always contribute to the Prepared block they received first, and not to every Prepared block they received.

4. This is for 0.0001 difficulty target for the small proof-of-work solutions. As I already stated up-thread, this will get worse over time as this target has be decreased as network hashrate grows faster than the hashrate and capital of the small miner.

Quote from: aliashraf on June 12, 2018, 11:21:12 AM

As of classical selfish attack itself, I personally disagree to call it an attack at all. I rather see it as a fallacy, a straw man fallacy.
My reasoning:
PoW has nothing to do with announcement. Once a miner prefers to keep his block secret it is his choice and his right as well, he is risking his block to become orphan in exchange for a possible advantage against the rest of the network in mining for the next block.

When you apparently do not understand the math and research paper on selfish mining (or youre just being disingenuous?), and you start arguing philosophically and handwaving, then the time wasting discussion is terminated.

Selfish mining is always profitable for the 33+% attacker. It isnt probably employed as an attack on Bitcoin because it increases the orphan rate and would tarnish the image of Bitcoin. So presumably the powers-that-be are not using it and they do not need to as they already have ASICBOOST and control over the 12/14/16nm ASIC fabs. So its not in their interest to deploy the attack on Bitcoin. But that doesnt mean it is not being deployed already on proof-of-work altcoins.

Quote from: aliashraf on June 12, 2018, 11:21:12 AM

Although Like PoW, this proposal is not about prohibiting people from selfish mining, there is a point to rephrase the above reasoning somehow different, this proposal is about reducing the pooling pressure and helping the network to become more decentralized by increasing the number of miners. How? By reducing the variance of mining rewards that is one of the 2 important factors for this pressure (I will come back to the second factor, soon).

My point which you seem to be trying your best to obfuscate is that, AFAICT I posit that your design makes selfish mining much worse. I posit that it lowers the 33+% that the miner needs to attack the network with selfish mining, thus further lowering the security. And will be more dubious to detect it because your design AFAICT drastically increases the orphan rate.

I am even wondering if your design will even reliably converge on a longest chain. And especially as the 10,000 factor is pushed to 1 milllion as the market capitalization of Bitcoin grows, then surely your design will fall flat on its face.

AFAICS, youre fighting a losing battle against the invariants of physics. The game theory flaws multiply as you attempt to put decentralization into a paradigm that is inherently centralizing.

All time expended trying to decentralize proof-of-work is time wasted thrown down a rathole. Proof-of-work is a centralization paradigm. There will be no escape.

Quote from: aliashraf on June 12, 2018, 11:21:12 AM

For a traditional winner-takes-all PoW network, like bitcoin there is just one pieces of information (the fresh block) that causes the problem, true, but the weight of this information and resulting premium is very high and it is focused in one spot, the lucky miner in the focal point and its neighbors in the hot zone.

For this proposal, this premium is distributed more evenly, tens of thousands times.

OOps! there is almost no proximity premium flaw in Proof of Contributive Work!

As I have posited with my incomplete list of concerns above, there will likely be game theory flaws lurking that you do not expect. I dont want to expend the effort do more than handwave about those I posited. Apology but Im very pessimistic about what more can be accomplished with proof-of-work.

Theres no way around the invariants of physics and economics that make proof-of-work inherently centralizing.

And I dont want to expend my time on this. Sorry. I already expended many months contemplating the variants of designs and realized theres no escape from the invariants. You can continue to invent new obfuscations for yourself over and over again until you finally come to realize the same. Good luck.

@anunymint Your technical evaluations and criticisms are highly valued. Two heads are better than one. Of course there are issues of centralization with PoW and already being exploited but there shouldn't be loss of hope in addressing them technically, from scratch or even with an additive/add-on. There is always a way around, an escape, and that has been driving new Physics and technological innovations. It's encouraging to let @aliashraf's codes be completed and reach a testing stage where unaddressed flaws in his analytical models will be discovered and solved. Don't lose hope in continuing your technical analysis of the proposal, even when you are feeling a sense of obfuscation.