Topic: A mathematical approach to economics of pools (Read 176 times)

Yes, I thought that if joining shares would be possible, then miners would have an incentive to add their shares to the previous block, instead of mining the next block. But situation seems to be different: if shares could be joined, then the minimal amount of work will be added to the previous block, and the rest will be taken by the next block. Why? Because it is not that easy to add your share to already combined set of shares without going under the target if you are not powerful enough.

For example:

firstBlockHash: 00000000000000000000bd6828839c032c75fa996f509ce9f15b09866751081c
secondBlockHash: 00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb6048
sumOfHashes: 00000000839a8e6886ac16b9fff2dd17a1b88595ffe51bcd11712545803c6864 (always divisible by four)
finalBlockHash: 0000000020e6a39a21ab05ae7ffcb745e86e21657ff946f3445c4951600f1a19 (sumOfHashes divided by four)

As you can see, adding some share is not that easy, because you can quickly get bigger number than the target, and then your block will be invalid. Replacing someone else's hash is also not that easy, because your hash not only has to start with some number of zeroes, it also has to produce sums divisible by four in all additions when shares are joined.

To better understand, how hashes are added, imagine a merkle tree with block hashes, but instead of hashing, there is a sum. And for each two branches, the value above is simply their sum divided by four. To replace someone else's hash with your hash, you need to produce lower hash, that is obvious. But: all sums up to the root of the tree also have to be divisible by four. And that means that building the tree from scratch is easy, but kicking one miner to add another one is hard, because all sums have to still be divisible by four.

Edit: as you can calculate, when using division by four, any hash has to be at least less than three times the other hash. If that is not the case, then using that hash directly without adding to the other hash is just more profitable and bring us closer to the target. For example, we have two hashes, firstHash and secondHash:

( firstHash + secondHash ) / 4 < firstHash
firstHash + secondHash < firstHash * 4
secondHash < firstHash * 3

So, if the first hash is 000000001000...000, the second hash has to be lower than 000000003000...000, if it is higher, then the final result will be bigger than the first hash, and then there is no point in adding them. Also, if that second hash is lower than 000000000555...555, then using that second hash alone is more profitable than adding it to the first hash. And that means that hashes will form a tree, where only hashes close to each other will be summed. And because joining them also require last two bits to be zero in each and every sum (up to the root of the tree), it should give enough incentive to start working on the next block and not modify the previous one endlessly.

Edit: If a coin is worth proportionally to the inverse of the hash, then for hash "a" that coin is worth "1/a". Then, the sum of the two coins should be "(1/a)+(1/b)", which can be simplified to "(a+b)/(a*b)" and then inverted. I tried that approach for some hashes and the results sounds promising, for example:

nonce=7c2bac1d, extraNonce=4, hash=000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f, coins=50.00
multiplier=5000, hashCoin=00000001f8a3ab27832f0246a8ed2d31d7d2e3d398c8f2484a88eb7e0fa687f8, minCoins=0.01
multiplier=5000000000, hashOneSatoshi=001e142f625ba9740c7aaf1d06ddcb75acdb761032ef934fbb544a4ed037ee00, minSatoshi=0.00000001
nonce=aa0945e0, extraNonce=0, firstHash=000000004fdffa39618d747f198d716e42d9b0081de468295d8c460316900de3, coins=(hashCoin/firstHash)*minCoins=0.06, satoshis=(hashOneSatoshi/firstHash)*minSatoshi=0.06317870
nonce=f17ed232, extraNonce=0, secondHash=00000000305f4d0a1a63c3fc231f7bcad88909ac6d4146f1b0453a2144316a15, coins=(hashCoin/secondHash)*minCoins=0.10, satoshis=(hashOneSatoshi/secondHash)*minSatoshi=0.10432409

a=000000004fdffa39618d747f198d716e42d9b0081de468295d8c460316900de3, satoshis=0.06317870
b=00000000305f4d0a1a63c3fc231f7bcad88909ac6d4146f1b0453a2144316a15, satoshis=0.10432409
a*b=00000000000000000f17bb1222d4a2194aa857b118a0dc364ffeb1d87361ad982afc8b6cc7fc5baf318f4bb7df2dd5e24916c5fa97f7d32853fad31e7404219f
a+b=00000000803f47437bf1387b3caced391b62b9b48b25af1b0dd180245ac177f8
result=(a*b)/(a+b)=000000001e209156ca1b80d9d174c491280ee9ad1bf9aa533c392cdbf07c5d84, satoshis=(hashOneSatoshi/result)*minSatoshi=0.16750279
0.06317870+0.10432409=0.16750279 (it works!)

I noticed dividing by four does not work as well, because the result is 00000000200fd1d0defc4e1ecf2b3b4e46d8ae6d22c96bc6c374600916b05dfe in this case. That means 0.15739584 reward instead of 0.16750279, so 0.01010695 coins lost when joining shares! It has its advantages, for example the calculations are simpler and there is an incentive for having as many hashes as possible, but I think any hashes should be joined as long as previous block hash and difficulty matches and each header passes standard checks.

So, in this way any shares could be joined and after testing it with some values it seems that the order of the operations does not matter. To sum up, I think we could start by including 5,000 hashes. It means 80 bytes per hash, so up to around 400 kB per block. Starting with 0.01 minimum reward seems to be a good option, it can be decreased with every halving, and after the last one, that limit should be skipped. It is still far from being complete and still does not scale up to millions of miners, but I think it is a good start point. Also, as old hashes will be deeper and deeper in the chain, that rewards should be decreased and removed after reaching zero satoshis. Currently, we have 6.25 block reward, so in that case the minimum payout would be 0.00125000.

Actually the variable difficulty idea might have some ground. After someone finds a block, make it unlikely for it to find a second consecutive block by introducing a multiplier (like 10x) for its difficulty. The multiplier decays upto a certain threshold like 0.1x (so that mining is still competitive and things like GPUs and CPUs and solo ASICs still can't mine - because that doesn't make any sense anymore), so that medium-sized mining farms actually have a chance of finding a block.

Mining will always be a zero-sum game where all the "players" (the miners) will work to maximize their own reward in one direction (call it a vector for the sake of argument). By elementary game theory, all of these directions add up to zero - so that means for every miner you have reaping 6.25BTC block rewards, you have a hundred more that get out of the race because their expenses are too high with little to no rewards.

Well, if you want to do it in a soft-fork way, then you have to make it compatible with currently existing "winner takes all" scheme. So, all miners should still produce shares as today. And then, you can quickly notice that sending rewards to one million miners on-chain is impossible, because of 1 MB block size limit (20 byte per miner would take at least 20 MB, so it is clearly impossible to do in every block). If you take 6.25 BTC reward and divide it by one million, you would get 0.00000625 BTC per miner (if all of them have the same power). The dust limit is around few hundred satoshis, so if you take into account that some miners have more power and other miners have less, then there will be a lot of miners with rewards below the dust limit.

And since distributing rewards on-chain directly in every block is impossible, it should be done off-chain. So, it could be done for example in LN channels. Each miner would have some channel with some mining pool and would send shares. And then, for each share that miner would get single satoshis (or millisatoshis, maybe even smaller amounts) as a reward.

So far, that is the only soft-fork compatible way I can think about. If doing such things on-chain is impossible, then the only way is some kind of off-chain solution. Unless you introduce some kind of "joining shares on-chain", as I described above.

It falls to the first category of solutions: hard-fork/altcoin proposals. Basically "combining" works of multiple miners is a right direction to follow in this category, my PoCW proposal, referenced above, does something like yours, let's say, in a bit more sophisticated way, though in this topic I'm more interested in decentralization of pools rather than making changes to the consensus.

I think the main problem is difficulty. There is one, single, global difficulty for the whole network. It is convenient when it comes to validation, but it is very inconvenient if we take mining into account. Because if we have one million miners and the whole difficulty is one million, then (assuming that all miners have the same power) each miner can produce one block with difficulty one per ten minutes (on average). So, my idea is using more than one difficulty and combining all of them to get the whole network difficulty.

So: each miner will start with difficulty equal to one. In this way, even CPU miners can start mining in this system if they really want. Then, each miner will calculate its own difficulty just by competing with itself. Each miner will know, which target should be used to produce one block per ten minutes (on average). And then, each miner will produce single block header per ten minutes that meets that miner's target.

Finally, hashes will be added in a way that respect their difficulties. So that any two hashes could be added if (and only if) their sum is divisible by four. Then, it can be divided to produce block hash that respect the difficulty and is equally probable to some other miner working alone.

Some example:

firstMinerBlockHash: 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f
secondMinerBlockHash: 000000006a625f06636b8bb6ac7b960a8d03705d1ace08b1a19da3fdcc99ddbd
sumOfHashes: 000000006a7c356eff73e69811feb49ddcfad40b6170af73145195b3d726c02c (always divisible by four)
finalBlockHash: 000000001a9f0d5bbfdcf9a6047fad27773eb502d85c2bdcc514656cf5c9b00b (sumOfHashes divided by four)

In this way, shares could be combined in a decentralized way. It is the best I came up with so far, but I think it is a good start.

Bitcoin mining scene has been dominated by pools since 2011 as a result of the infamous pooling pressure flaw which is a direct result of winner-take-all approach to PoW, adopted by Satoshi Nakamoto, from the first beginning.

Although there are some arguable facts, Bitcoin's implementation of winner-take-all makes it a fair gamble for miners, but fairness is not enough for gamblers to participate in the game because nobody can afford unlimited resources and time needed for a guaranteed break-even/win status. It is why pools are necessary for bitcoin mining; they eliminate/hide the gambling nature of the original bitcoin mining scheme almost completely, letting the industry to grow just like a normal business: tell me how much hash rate you got, so I would tell you how your business looks like in terms of costs and revenues

Many people, including myself, do not like pools, they are centralized entities that introduce a series of risk factors to the Bitcoin ecosystem compromising the most basic decentralization assumptions for the least, but the most serious consequence is what I call it miner alienation. As a matter of fact miners are not just being abstracted from the gambling nature of mining, they are also abstracted from the whole network.

For a pooling scheme to do anything useful in terms of hiding the variance and risks, it needs to give a substantial difficulty leverage, hence a considerable number of blocks should be submitted to the pool operator/server (typically thousands per second for large pools) which makes it absolutely impossible to fetch/validate all of them as long as they are supposed to be conventional Bitcoin blocks. It is why they've adopted a top-down block generation method in which the Pool operator builds a block template then relays its header to its clients, i.e. miners, waiting for them to find a nonce; add a few tricks to this model, and you have Stratum the current de facto standard for pooling in PoW world.

Suddenly, there was left no reason for miners to be aware of the Bitcoin network, e.g. by running a full node, and,  except for a few very large mining farms, overnight, bitcoin miners turned to zombies, alienated from the actual bitcoin protocol, unconsciously and exhaustively searching for a meaningless nonce that makes a meaningless 80 bytes long string look pretty enough to be claimed as a share. Indisputably, this situation MUST change, but how?  

Although I've been trying to find a way for fixing the situation with pools, it was just a while ago that I realized how ignorant I am about the economics of the subject, and it took not more than a few days for me to realize that I'm not an exception as there is no model available (well, AFAIK) to describe the economics behind PoW pooling business.

By economic model I mean a mathematical cost vs benefit analysis of pooling as a business. Many authors have shown interest in reward distribution mechanisms used by pools from a game theoretic point of view mainly for mitigating adversarial behaviors such as block/share withholding.

Although reward distribution model is an important topic and one can find interesting mathematical material here to play with, by no means it can be categorized as a mathematical model for the core pooling business as it doesn't cover the most important question:

I was even more surprised when after applying naive probability techniques and failing to approach anywhere close to the answer, I find out myself dealing with a decades old problem in mathematics known as the utility of gambling.

I'm wondering if there is any related previous work that I was not able to spot, it is why I started this thread, asking members to share any resources/thoughts about the question I bolded above.

Why and how is this important?
Like it or not, pooling is an abnormal phenomenon for PoW and the pressure toward it is nothing less than a flaw, a flaw that is a consequence of winner-take-all approach that historically dominated PoW starting with Nakamoto and Bitcoin, nevertheless any reasonable advocate would agree that this should be addressed somehow.

There can be two different approaches to this problem:

1- Designing a winners-take-share model of PoW,
Initially, I tried this approach a couple of years ago, and I believe my PoCW proposal was a good start, but it needs a hard fork or a project for a brand-new coin, neither is my primary target now.

2- Improving/replacing Stratum and how miners of winner-take-all PoW coins, specially Bitcoin, deal with their variance nightmare.
It is the way to go, I believe, but a closer examination of the current projects is not encouraging for the least to say.

Stratum 2.0 project:
It is a total disappointment in spite of the hype and the advertisement. No fundamental redefinition of roles and a desperate attempt to give miners a right to negotiate the block contents they are mining without any creative idea for justifying and realizing such an attempt and all of it wrapped in an ugly and complicated set of protocols.

P2Pool and decentralized pooling:
Not scalable! P2Pool utilizes a 20 to 1 leverage while it can't improve too much and a closer look reveals that you can't use this protocol recursively because of the reward distribution complexities involved.

I conclude that the true solution to the pooling problem is the one which is not tried or even proposed yet, and all we can do is giving a general sketch of it:

1- It should be decentralized as much as possible and this property should improve through time instead of declining.

2- It should be an open and permission-less ecosystem, people should be able to join or leave deliberately while they can choose their role with minimum requirement.

3- Roles and relationships of the parties involved, miners, pool operators, and the network, should be redefined radically.

4- The costs and revenues of each party should be economically justifiable.

Taking features 2,3,and 4  into account, I think it is not that hard to understand the importance of an economic model for the future of pooling in Bitcoin and PoW coins generally.