I have clearly underestimated this statement.

I see, yes I misunderstood the problem.

If a miner sees a block 1x the network average, it would have just cleared out the most profitable transactions. While waiting for the transaction pool to refill, miners should continue to mine those same transactions, ignoring the solved block. If they find a block that is slightly smaller, then they can reveal it to the network. The network will look at the second block, and because it leaves a larger pool of transactions, they would should all switch to the second block and ignore the first block, since their blocks will be more profitable mining on top of the second smaller block. Actually, after every block there would be a short time period where everyone would profit by trying to orphan the known block by producing one slightly smaller...

I started writing a simple simulation that generates a distribution of miners with differing efficiency. As I was programming the behavior of the miners, I started by assuming miners will act rationally and always try and maximize their profit, and from there I plan on trying to have individual miners behavior differently and exploit the network.

An interesting consequence of them action rationally is that if the expectation value of their profit per hash E<profit/hash> is less than the cost per hash, then they're better off powering down their hashing equipment until the transaction pool fills - assuming they can stop the clock on their ASIC and stop the dynamic power consumption of the ASIC.

I think it should be easy to prove that a rational miner will always mine the largest fee per kb transactions. I would think this proof already exists in a general form somewhere. Let S=[s1, s2, s3...] such that s(n) > s(n-1). Let P = S xor s1 so that P = [s2, s3, s4...] and take S-P you get s1, which means S is larger than P by s1.... errrrrrrrr, did I just prove the axiom of an ordered set? Anyway, someone could probably do this better than me, but the intuitive statement is that if you remove highest fee per kb transactions, you always lower the mean fee per transaction.

For proving a Nash equilibrium exists, I had to look this up, and it seems like an interesting problem. While I think I can say I have a conceptual understanding, the proof is probably beyond my expertise in game theory or my ability to generate rigorous proofs (which is like 5 lectures on open-courseware and what I gleam from my wife - she's a math teacher).

I agree that simplicity is always preferable. I mulled the concept of adding additional POW into the Merkel tree, or somewhere parallel to the header, and those all added complexity and in the end didn't add to the network security. I really didn't like the idea of changing the header structure.

That said, I don't think this is all that complex, and to the average user they shouldn't care. All they need to know is that miners need need to make a profit, and the higher fee they pay the sooner a miner can include it in a block. If they pay too low, a miner will need to wait until it's profitable, which may never happen if you pay far below market price.


I think you're right that there are an infinite number of polynomials that work. This is where it seems we cannot divorce the politics from the algorithm. Each polynomial is going to produce a slightly different outcome. I simply chose one as a starting point to illustrate the concept of difficulty vs. size (which I'm glad to find you've mulled also!). I think the key is that anything sub-linear will eventually cause most transactions to become profitable, but with a varying delay. For example, we could make a polynomial that is nearly linear, which would result in the time penalty for lower-fee transactions to be even longer. Linear would be the opposite extreme to what Satoshi chose. I'm not sure we can say that one is correct, but I would point out that Satoshi did chose one parameter, namely constant, and it's at the other extreme. I would also say that we have no reason to claim this one is any more correct, but we do know it has the potential to produce certain outcomes that we're not too excited about... so in other words, we cannot be neutral and say we just won't pick a polynomial, because one has already been picked.






I actually started down this path, then realized that with anything other than constant (Satoshi's parameters), the population and distribution in the unconfirmed transaction pool is always going to be changing, and therefore the profitability of mining will constantly be changing. As a result, I think you're going to see a whole array of mining strategies.

One of my concerns with this is if these complex strategies would lead to the expectation value for the block time to always remain 10 min, or if it would oscillate. It might produce undesirable oscillations if the natural frequency is too close to 2016 blocks, but perhaps this could be mitigated by calculating the average block size over a longer time span.




My bad, I copied the equation wrong from my code. I think the figures were correct. Are the labels confusing? Here is the axis with numbers instead (I was trying to make it more descriptive by adding the "x average"





Yep... I've revealed that I'm at best an informed hobbyist. I don't know the code, but I did do my best to read about the block structure and such to attempt to suggest minimal changes. I have done a tiny bit of embedded design, so I know how painful floating point can be.

Abstract— The current economic incentives of the Bitcoin network result in a tragedy-of-the-commons that could result in transaction fees eventually falling to zero. This is because the marginal cost of mining each transaction is zero for the individual miner (assuming O(1) block propagation), but non-zero for the network. If all miners are capable of externalizing the cost of mining ‘spam’ transactions, and if anyone can mine, then nothing within the consensus protocol today exists to establish a market price for transaction fees. As a result, miners must either rely on charity, or form cartels outside of the consensus protocol to enforce transaction fees. One solution to this problem is to require a local difficulty correction for each block based on the size of the block in bytes. Blocks that are larger or smaller than the network average would require a slightly more or less difficult proof-of-work respectively. The result would be that less efficient miners with a higher marginal cost of mining would be required to mine only the highest fee transactions in smaller than average blocks, and leaving lower fee transactions for more efficient miners. Those most efficient miners will be able to mine larger blocks at a net discount per byte when compared with their less efficient counterparts. If the difficulty correction per byte is sub-linear, then very large block will always become profitable eventually, so that even extremely low fee transactions will eventually be mined, although with significant delay. No-fee transactions will always cost miners in the form of increased difficulty, and therefore will only be mined as charity. A localized block difficulty does not need to change the block interval, the coinbase schedule, or alter any of the economic incentives that have made Bitcoin successful up to the present time, although attention must be given to the special (current) case where the coinbase is larger than the transaction fees. It would, however, require the addition of a block size field in the header. Localized block difficulty would be ideally suited for a sidechain where there is no block reward.

---

I.   INTRODUCTION

If proposals for O(1) block propagation are successful, then the cost of mining will be dominated by hashrate. However, there is no correlation between the amount of data published to the blockchain and the hashing required to publish it. As a result, a spam-miner can mine all transactions irrespective of their transaction fees with no additional cost to themselves. A small minority of miners could impose a situation where all transactions are mined, even no-fee transactions. If no-fee transactions are mined, then only charity remains as the motivation for including a transaction fee.

One possible solution to this is to keep the block size limit low enough to cause a market to form which causes users of the network to bid for space in each block. The difficulty with this approach is that it requires a central planner to correctly guess the growth rate of the network and determine the ‘correct’ size based on a subjective opinion of the legitimate uses of the blockchain (i.e. store of value vs. microtransactions).

Another possible solution is for the majority hashrate to form a cartel and censor spam-miners. This is undesirable because it encourages consensus outside of the consensus algorithm, which ultimately is not public and cannot be audited. The best solution to incentivizing the payment of transaction fees would conform to the following principles:

• The mechanism for creating a transaction fee market should be built into the consensus algorithm as much as possible so that it is public, auditable, and enforceable by all individual node (i.e. wallets and holders of bitcoin).
• The solution should not assume the growth rate of the network, and should work equally well regardless of the use cases of Bitcoin that develop.
• The solution should be as conservative as possible with respect to making changes to the protocol, and should not change any fundamental parameters of the inflation schedule or block time.

II.   INDIVIDUAL BLOCK DIFFICULTY

Let D be the global difficulty of the network, and d be the target difficulty for an individual block based on its normalized size in bytes (s) relative to the average size for the network, calculated every 2016 blocks. We can define d as

                    

In this case, the average difficulty (d) is equal to the global difficulty D, therefore the block rate remains constant at 10min on average. The function is well behaved and should not cause divergence away from the mean block time and size.

The validity of each block would be determined by the POW hash meeting d, not D. If computational resources are extremely limited, it may be desirable to create a lookup table every 2016 block for valid d values to avoid numerous floating point operations. In order to preserve self-validating headers, the header must contain a new field to capture s.

III.   ECONOMIC CONSEQUENCES OF VARYING BLOCK DIFFICULTY


          

The first thing to note is that if a block is smaller than average, the difficulty to mine this block is less than the average difficulty. For simplicity, the following discussion assumes minimal block reward, which is the condition under which a robust fee-market is required. However in the interim the implications of the block reward must be addressed. For this discussion see section IV.

In the absence of a block reward, a miner can mine small blocks at a reduced difficulty. The marginal cost per block (in hashrate) would be higher, so that only the highest paying transactions would be profitable to include in a small block. Assuming a roughly power-law distribution in fees paid, the cutoff for transactions included in the block will depend on the marginal costs of the miner. Efficient miners will be able to produce larger blocks profitably, while less efficient miners will need to be selective and will produce smaller blocks on average.

The pool of unconfirmed transactions is unlikely to follow any simple distribution because as blocks are mined, the highest fee transactions will be pulled from the pool first, causing the tail of low-fee transactions to grow relative to the high-fee transactions. Eventually, the pool of low-fee transactions will grow large enough that it will become profitable to mine a super block (i.e. 10x the normal network size) due to the decreasing difficulty per byte. As long as a transaction pays a fee greater than the marginal cost of the most efficient miners, it should always be picked up in a superblock.

Although it’s difficult to model the behavior of such a system, it seems reasonable that a natural frequency would start to emerge where a distribution of small and average sized blocks are mined continually until enough hashing power is incentivized to mine a super block, which might start to occur at roughly regular intervals. Individual behavior of wallet users might start to predict this and pay lower fees as the expected super block approaches. However, because the marginal cost per transactions is continually changing as the pool size changes, it is not clear that any one mining strategy will emerge as the only strategy.

Under no circumstances will it ever be more profitable to mine lower-fee transactions and not higher-fee transactions. However, if the miner experiences real costs associated with increasing the block size, their expenses measured in electricity and equipment will place an absolute floor on the minimum transaction fee that will not result in a loss for the miner.

IV.   VARIABLE BLOCK DIFFICULTY AND BLOCK REWARDS

In a setting such as a sidechain where there is no block reward, equation 1 would work well. However, if the block reward is much greater than the transaction fees, there is an incentive to mine the smallest block possible because of the reduced difficulty of blocks smaller than the network mean. This will create a race to zero block size. To prevent this, the block difficulty should be limited such that

                    

where m starts at 1. It may be wise to have m decrease by 0.1 every block reward halving so that there is a known schedule for the reduction in the minimum difficulty.

V.   BEHAVIORAL IMPACT TO VARIOUS PLAYERS

• The spam miner – The spam miner is a minority miner who wants to include all unpaid transaction in the blockchain. This miner could accomplish this by including only small amounts of spam, and would always do so at their own expense because their increased block size will result in increased difficulty for themselves only. The more spam they mine, the more uncompetitive they become at producing blocks.
• The greedy miner / cartel of miners – This miner or cartel of miners refuse to mine any transactions except for transactions above some artificially high price. In this case, the cost of mining the average-fee transaction decreases as the transaction pool grows, so that eventually the greedy miner will need to pass up a large number of profitable transactions to maintain his artificial requirement.
• The fake-transaction miner – This is the miner who pads his transaction with fake data to increase the block size. In this case, the miner will be hurting himself because he will artificially increase the difficulty of his own blocks.
• The cheapskate – This is the bitcoin holder who refuses to pay a fee comparable to his peers. If his fee is simply too low, the added difficulty/byte will never reach a profitable point for a miner to include it in a block. The cheapskate will need to rely on charity of a miner to get his transaction published.

VI.   ATTACKS

• Increased risk of 51% attack and double spends - If the polynomial chosen for block difficulty vs. size gives a discounted difficulty for blocks less than the mean size for the network, then an attacker wanting to perform a 51% attack could inflate their effective hash power by generating small blocks during the attack. For instance, if a double-spender controls 15% of the hash power, their effective hashing power with blocks 1/10th the network average size would be 1.82 times larger, making it appear for the attack purposes that they control 27.3% of the network hashrate. However, this behavior would be mitigated by the fact that the miner would need to perform this attack by mining smaller blocks, which would result  in them leaving profitable transaction fees un-mined for other miners. In the case where the dishonest miner can achieve an effective hashrate above 51%, they may be able to recoup this loss at the end of their chain. This attack would need to be mitigated by choosing a polynomial that does not provide significant discount for small blocks, or by a simple min(f(D),l) limit. [Credit to jonny1000 for this contribution to the discussion]

VII.   THE SLOW DRIFT PROBLEM

One scenario that isn’t solved is the slow drift problem. What happens if the average transaction fee slowly drifts lower and lower such that eventually the bitcoin network is no longer secure yet everyone is paying the average transaction fee? This seems like a rather hypothetical situation, and there is no obvious reason to insist this will necessarily happen. However, in the event that his happens, equation 1 can be generalized such that

                    

where i is the inflation rate of the hash power desired to maintain 10min block time. Adjusting i to 1.02 will require a 2% increase in the hash power such that D remains constant. If i were ever to be adjusted, it could be adjusted through some proof-of-holding mechanism, although such a process would need to be reserved for a case in which no other mechanism exists to secure the network. The meaning of this would essentially be the network demanding that “the hashrate might increase by 2% per 2016 blocks regardless of the fees paid.” The failure to meet this  imposed growth in hashrate would be that the block time would slowly drift slower and slower until more hashpower is added to restore the blocktime.

VIII.   Closing Thoughts

It is my belief that the block size must increase, and therefore something in the consensus algorithm must change. However, increasing the block size indefinitely could very likely remove the only existing incentive (except for charity) to pay a transaction fee. There is no relationship between the amount of data being securely stored on the block chain and the cost of securing it. This leads to a scenario where transaction fees could go lower than the marginal cost of mining, essentially destroying the security of the Bitcoin network.

As a user of the network, I should be purchasing security. If the addition of my transaction requires additional hash power, then the miner now has a need to require a fee of me. This need can be built into the consensus algorithm such that all participants in the network know the origin of nature of the mechanism that gives rise to the fees.


EDIT 02-16-2015: The equations were copied wrong. Pointed out by gmaxwell
EDIT 02-17-2015: Changed some title headings for clarity and added a comment about the risk of 51% attack.

I love my Trezor and it's use of HD wallets, but it would be really nice to have account names.

I was thinking that it would be useful to have a dictionary of account names, similar to the way private keys are translated to standard mnemonics through a published dictionary. An example category would be designating the n'th account/pocket as "3rd Child: College Savings" in some standardized and cross wallet dictionary. This could possibly allow for some added interoperability across HD wallets for their accounts/pockets, without any needed backup. I would imagine selecting from a few standard dictionaries which defines the a few hundred general account descriptions. Of course the use of any account dictionary would be entirely optional, and there could be optional packages for a users unique use pattern (i.e. multilingual dictionaries, business dictionaries, etc.).

Ok, so I think I understand. It lowers the barrier to entry for a block withholding attack...

My point was that there is no such thing is 'working' on a block, it is either solved or not solved. In the case where the greedy miner is forced to reveal the block before finding a second block secretly, there is no benefit. It would only have been realized as a benefit if he finds 2 consecutive blocks before the network forces him to reveal the first block.

3 questions:

1) Has anyone calculated the window for execution of such an attack? Either empirically, numerically, or both? My suspicion is that it's actually quite a bit smaller than most people would anticipate. (but I could be wrong!)

2) If the effect is small and doesn't present appreciable bias towards larger pools, would allowing block withholding be something that bitcoin could just be agnostic too?... as long as it doesn't effect the overall network, it's like allowing miners a little gambling with their blocks [again assuming the overall affect on the network is small and doesn't provide advantage to large pools]. My instinct is that it would have almost negligible effects on block frequency, and that if all miners played the same game, it would have almost no bias.

3) Is this something that's simply politically unworkable [assuming that the final decision is really up to the miners]? Even if the real benefit of withholding a block was smaller than anticipated, is this something miners would simply be too resistant to?

I'd be willing to find analytically/numerical solutions to how a potential attack could be executed, and quantify its potential effect on the overall network, but if this idea has already been put to rest...

By the way, this is the mind bending implications of statistics... I had to work through this myself to convince myself of the security implications of block frequencies (i.e. Litecoin vs. Bitcoin)...

I convinced myself quite strongly that mining is never deterministic, which has this tensions between 'gut feeling' and reality. At first, it made sense to me that once a miner begins mining with a set nonce pattern, the number of hashes to a solution becomes deterministic... however, after further reflection this is not the case.

A miner can hash x hashes, but is absolutely no hashes closer to a solution....

This is why a miner withholding a block gains no advantage.

Forgive me if this has already been discussed, but I believe [humbly] that you are appealing to the Monte Carlo fallacy (i.e. that probabilities are cumulative).

You are correct that a miner could withhold a block solution, but it would be of no advantage. I make this claim based on the assertion that mining is not deterministic, even if a miner set out with a given nonce increment pattern. I'm asserting that mining is only probabilistic, because until a solution is found, there is no guarantee that the solution exists, only a probability of it existing.

I think I could make a convincing argument for why the above scenario would be of no advantage, but this hinges on my understanding that mining is not deterministic. The basic argument goes that even if a selfish miner hashes x number of hashes secretly, he is still no closer to a solution than any other miner, therefore there is no advantage to the selfish miner if he excludes other miners for a period of time.

If this has been discussed, I'm be interested to read up on previous discussions. Is there consensus that mining is deterministic or probabilistic (i.e. do probabilities mature or are they independent)?

Again, I think I could put together a good argument, but I don't want to re-hash someone else's work!

Below is a proposal for reducing the penalty miners pay for larger block size by [I would argue] at least 6000%...


This leads to the condition where miners are incentivized to produce the smallest block size (minimum number of transactions) to minimize propagation of their blocks.

Is it possible to mitigate this effects by establishing the rule that, when the block chain forks and there are 2 blocks at the same block height, miners always choose the block with the lowest hash (both blocks would obviously have hash below the target).

In the event that 2 blocks are solved nearly simultaneously, the outcome of which block is accepted by the majority of other miners will be deterministic based on their headers, not on network propagation. From the perspective of the miner who just found a solution, they needn’t worry about the size of their block or how quickly it propagates through the network. They simply hope it’s header is less than any other possible competing block.

Could this lead to miners continuing to mine at a given block height, even if a solution has been broadcast? No, because the moment they become aware of a solution, their effective target has just been raised. If miners collectively agree to accept only the lowest hash, there is no incentive to attempt to compete below the highest known block height.

In the event that 2 blocks (a1 and a2) are solved at height n and n+1 respectively, before block b1 fully propagates, it raises the potential conflict if b1 would have orphaned a1. This would be the case if the hash of b1<a1. However, if a2 was found before b1 fully propagates through the network, then b1 will be orphaned due to propagation delays [which I’m trying to mitigate]. However, the chances of b1 being orphaned due to a2 are at least 60 times less likely than being orphaned due to a propagation race with a1, as calculated below.

To calculated the expected reduction in block orphanage due to network propagation, let’s assume 20s propagation time with a block solution following an exponential distribution with a mean time of 300sec (5 min) [note: this is towards a worst case scenario].

Integration the exponential PDF from 290sec to 310sec results in an orphan probability of 2.45%, this would correspond to a propagation time of 20sec while a competitors propagation time is 0sec, clearly an unacceptable disadvantage for miners.

However, let’s calculate the probability of the above scenario, where b1 and a1 are found simultaneously, but a2 is found while both are still propagating through the network. For sake of simplicity, let’s assume that a1 has negligible propagation time. With the whole network working on a2, the probability of a2 being solved in the first 20sec is 6.45%. Therefore the probability of both of these events occurring simultaneously is 0.158%.

To further refine this, let’s assume that block a1 actually propagates through the network at a linear speed, so only part of the network is working on a solution to extend a1 [the linear propagation rate is probably a bad assumption, I’m just schmooing lambda of the exponential distribution, but this would overestimate the probability of a2 being found]. Using linear propagation to half the network, then being overtaken by b1, the probability of a2 being solved before b1 fully propagates is 1.65%, which results in an orphan rate for b1 of less than 0.05%.

This would mitigate the effect of block size on orphanage by 6000%

(I’m a physicist, not a computer scientist, I hope this makes sense, and furthermore I hope this is a viable solution to the tx/sec limit being imposed by miners!)…

Danny, you're correct. This would reward exactly the negative behavior you've outlined. Thanks for the help!

Why would they have to work off a global pool?

Wouldn't this work fine if each miner evaluated according to their local pool? When calculating the size of the pool, you get an integer, not a list... no?

To incentivise inclusion of tx's in blocks, I propose the following (I work in hardware R&D, so I have only passing familiarity with the protocol, and so I may not know what I'm talking about!)

Solution: Miners switch to the longest chain (no change to protocol here), which leaves the smallest pool of unconfirmed transaction (addition to protocol - soft fork).

From my understanding, miners currently have an incentive to limit transactions because, in the rare event of 2 blocks being solved nearly simultaneously, the smaller block with propagate through the network more quickly. Larger blocks have a smaller risk associated with them.

So how do you incentivise including as many transactions as possible? My thinking here was that you cannot have miners give preferential treatment to the block with the largest number of transactions. This is because a deceptive miner could generate a large number of spam transactions without broadcasting them. Any block they solve could be padded with their secret tx's, artificially giving their blocks preference on the network.

Instead, if miners were to see 2 blocks solved nearly simultaneously, they could switch to whichever chain gave the smallest unconfirmed tx pool. Perhaps some details to prevent miners from toggling chains may be in place. For example, preference=mod(tx's,100) so that miners don't unsessisarly jump between preferred chains.

From my understanding, this would not require a hard fork, because no miners would not need to necessarily work on the preferred chain as I've described above. By participating in whichever chain they receive first, they simply risk other miners preferentially working on a different chain during the race duration.

---
P.s. I've been using bitcoin since beginning of 2013, but haven't gotten into the forums. Just wanted to thank everyone for such an awesome experiment! I know physics more than programming. Wish I could help more!