My proposal for GHOST protocol

[King Lear]

Hi all,

Recently Yonatan Sompolinsky and Aviv Zohar have published an important paper in which they suggest a protocol change for Bitcoin, named GHOST:  Greedy Heaviest Observed Sub-Tree. Basically the paper shows that the mining rate (or equivalently, the expected interval between consecutive blocks in the chain, which is 10 minutes in Bitcoin) can be much accelerated without compromising the security of the system, by simply accepting the blocks that form the heaviest sub-tree instead of always accepting those who form the longest/heaviest chain. Here is a link to the paper: http://www.cs.huji.ac.il/~avivz/pubs/13/btc_scalability_full.pdf.

On this thread I would like to propose a different implementation for GHOST than the one described in the paper. My proposal arguably solves a major potential weakness of GHOST that is decently noted in the paper, as well as two other known weaknesses of Bitcoin which are magnified by GHOST: vulnerability to Block Discarding Attacks (like "selfish mining"), and the expected mining tragedy of the commons that might cause the honest hash-power to decrease in case the fees won't be able to compensate the decreased basic block rewards.
 
Basically, although the accelerated mining rate doesn’t (directly) increase the vulnerability to 50% hash-power attacks when using GHOST, it does theoretically increase the decentralization of the system: as there are more forks to the chain, the probability of a miner to get an eventually confirmed block within a certain period of time, is the probability of succeeding to form a valid block within that period, times the probability of a valid block to get eventually confirmed. The first probability is linear as a function of the miner's computational power, while the second isn’t constant as it depends upon the miner's network connectivity.

Thus, 1000 small miners are expected to collectively gain less confirmed blocks than one strong miner with the same total hash-power, simply because the strong miner would be faster informed of any new mined block and faster propagate her/his blocks, in order to improve her/his blocks confirmation probability. Moreover, since Block Discarding Attacks can be much amplified by network superiority (meaning, the connectivity advantage of the attacker over the average miner), the accelerated mining rate might increases the system vulnerability to those attacks.
 
I therefore propose to reward (almost) all orphan blocks just a bit less than the confirmed block's reward. In order to do so I suggest having a mandatory tax on transactions, founding the "Bitcoin security reserve" account. Both confirmed and orphaned blocks get rewarded by the security reserve, while miners of the confirmed blocks may collect fees in addition. Since block mining is accelerated, each block contains less transaction, so the income from fees is supposedly negligible compared to the reward.

The specific proposed implementation goes as follows:

Mining rate
6 seconds per (confirmed) block, at least. Difficulty is smoothly adjusted according to the formula
Dif_n+1 = dif_n * ( 1  +  (time_n – time_n-1) / two weeks  -   (6 seconds / two weeks) )
where dif_k  and time_k are correspondingly the difficulty and the timestamp of the k-th block.

Mandatory security tax
The tax on transaction transferring X Bitcoins is \alpha + x*\beta, meaning a constant minimal tax plus a very small percentage of the transaction. \alpha and \beta should be chosen such that the expected total taxes sum within 10 minutes is about 25 BTC, or some other security parameter.

Blocks rewarding
With respect to a certain chain, we say a block is of 0-degree if it is a member of the chain; of 1-degree if its parent is a member of the chain, of 2-degree if its parent's parent is a member of the chain, etc. I suggest rewarding the 0-3 degree blocks with 100%, 90%, 75% and 50% (correspondingly) of the average reward of a confirmed block. Blocks of degree 4 or more should not be rewarded at all.

Inspired by the fork-punishment mechanism of http://eprint.iacr.org/2013/868.pdf, block headers of 1-3 degree blocks will be included, using a special syntax, within confirmed blocks. Block headers should be changed to include their miners' addresses, and a (confirmed) block is extra rewarded with 1% of the average reward for any valid block header it includes. An orphaned block header might be included only within the 10 consecutive blocks following its 0-degree ancestor.  

The average (basic) reward for confirmed blocks is smoothly adjusted as follows: The 100% reward of the k-th block is given by
((Bitcoin security reserve at time_k) / ratio_k )* ((6 seconds) / 4 months)
Where ratio_k, which is the average ratio between the block-chain growth rate and the block-tree growth rate, is recursively calculated by  
ratio_n+1 = (1 – (6 seconds / two weeks)) * ratio_n + (6 seconds / two weeks) * q_n
Where q_n is the total percentages of the average confirmed block reward that is rewarded on time time_n (say 100% + 90% + 50%, in case the n-th blocks contains headers of a single 1-degree block and a single 3-degree block).


Protected GHOST
Extending the current chain is done according to regular GHOST, meaning that the next chosen block is the one having the heaviest known subtree out of all the blocks that are mined on top of the current last block of the chain.

As for replacing a chain-block by an off-chain block that forms heavier subtree, I suggest a slight modification named "Protected GHOST": in calculating the size of a subtree, we shall ignore all blocks that were received suspiciously later than one could have expected. Specifically, when considering a competitive chain that is allegedly heavier, we ignore all off-chain blocks whose headers are not included within blocks of the competitive chain unless their (on-chain) predecessor has been mined during the last hour, or some other security parameter.

And that's it. Quite simple, huh?

 
Advantages and disadvantages:

The tragedy of the commons problem is solved as the total honest network is rewarded about 25BTC per 10 minutes, as it is now. Assuming the market is competitive, the total honest investment in hash-power is just a bit less than 25 BTC per 10 minutes, so the 50% attacker should be *very* rich in order to succeeds.

Smaller miners, whose probability of their valid blocks get eventually confirmed is smaller, will be rewarded just a bit less than the strong miners per a hash-power unite, Thus the network is not about to become more centralized.

The Block Discarding Attack / "Selfish Mining" is conceptually based on artificially forking the chain in order to get higher portion of the block-chain than the attacker's portion of total hash-power (which is equivalent to the attacker's portion of the block-tree). As we reward (almost) all blocks of the tree and not only those of 0-degree, this kind of attacks becomes much harder and less profitable.

We maintain a strong incentive to mine on top of the "right" chain, despite rewarding blocks that are off-chain, as their reward is slightly reduced. Moreover, we provide a strong incentive for miners to report other off-chain blocks by extra rewarding them for doing so. This is helpful not only for rewarding the 1-3 degree blocks, but also for providing the necessary information needed to choose the "right" chain.  

The main disadvantage of my proposal is the mandatory tax, which in a sense contradicts the libertarian spirit of Bitcoin. Yet I believe there is no such a thing as ideal currency, and in particular, for security you have to pay. This payment might be explicit as in my proposal, or implicit as currently it is in Bitcoin (the inflation caused by the 25 BTC rewards per block form an implicit tax), but it must somehow exist - or else we shall all suffer lower security because somebody isn’t willing to pay his/her share.

Lear.
P.S. let me just link my paper few more times, in case someone have somehow missed it: http://eprint.iacr.org/2013/868.pdf.
 

[1715205874]

1715205874

[1715205874]

1715205874

[1715205874]

1715205874

[King Lear]

It should be noted that theoretically there is a bug in my rewarding mechanism: if all miners unite to form as many blocks as they can on top of one single block, and after 4 months or so include all blocks' headers within a single block, then they might be rewarded more money than the total sum of taxes (i.e. making the Bitcoin Security Reserve in overdraft).

This obviously is really unlikely, yet if someone is nevertheless interested in a solution, we can simply limit the number of block headers included in a single block to be at most 10 for say…

[coinrevo]

My longer post got lost.  The problem is GHOST changes the protocol completely, without really much thought in terms of how information propagates through the network. Just as an example you find this in the paper:

If every node’s bandwidth is at least 0.427 MB per second, then the network is able to maintain a rate of lambda = 1 blocks per second and b= 320 KB per block, with 10000 transaction hashes per block, achieving a TPS of more than 214.0.

0.5 MB/sec. seriously. and these guys want to prove certain properties about network delays, and build the payment protocol on that. My suggestion would be to try this code in the real world. The blocktime was very carefully chosen for good reasons, most of which seem to escape the ghost authors.

[King Lear]

Well, Bitcoin was designed 6 years ago by a mysterious individual and before there have been any such similar system. Since then there have been so many progressions, new ideas and new coins, and we now have so much knowledge that Satoshi hadn’t while designing the original protocol. So I don’t think that any arbitrary choice made by Satoshi is neither the only possibility nor the best one…

 What the authors are basically saying is that there is no need to make the average interval so long that there will almost be no natural occurring forks, meaning this interval doesn’t have to be much bigger than the network delay. So you may think that 1block per second is too optimistic, but you must agree with the authors that GHOST can get the interval significantly shorter…

Indeed I agree with you that this novel idea should be checked in reality before we make any change to Bitcoin (perhaps by building a new crypto-coin), yet I am very optimistic about that! The authors based their claims on empirical results of the Bitcoin network and their work seems very reasonably to me (not like many other academic paper that have some unrealistic claims).

Lear

[coinrevo]

What the blockchain does is creating a pulse. The pulse lets every node have the same information. The earth's circumference is close to 40'000 km and the speed of light close to 300'000 km/sec. So the roundtrip time for a packet is roughly 1/2 sec, minimum. However TCP/IP is not directly routed and so you have 5-10x that with high degree of variance, especially if you are not in US or Europe. satoshi made this highly interesting comments about proof of work in this context: " Proof-of-work is essentially one-CPU-one-vote. " This is very profound. But basically it means that location shouldn't matter, and the ideal form would be perfect distribution. With the the stamp time below one minute, you are going to have serious side effects. It might mean that certain places are better for mining than others. In fact having this specific length of block time is one part of the real genius of satoshi. Frankly I don't see how the changed block acceptance rules can make any sense. I've spend enough time in academia to know it's basically all a waste of time. The real work is going to be done somewhere else.

[King Lear]

Let me put it this way: currently, reducing the time intervals between blocks harms both security of the system and mining fairness (having the profits depends only on the hash-power and not on network connectivity). The GHOST proposal enables reducing the average interval without harming security while unfortunately harming mining fairness. My proposal enables to do so also without harming much mining fairness.

So I agree with you that making this interval about a second might be just too much despite GHOST (and my improvements), yet I don’t quite see why are you thinking 10 minutes is the right interval… we already have functioning alt-coins that works pretty well with 2.5 minutes and without GHOST!

As for the academia, I think it is quite diverse: sometimes (and I believe this paper is such an example) the border between the "real world" and academy is really unclear, while sometimes the theory is so different that the practice and might only be relevant long time into the future.   

[coinrevo]

well, the system works pretty well. the reason is that satoshi was on this for basically a lifetime. you don't get to make the most important invention of a generation, without putting everything into it.

a lot depends on assumptions of bandwith, latency, hashing power, and so on. as I said if you don't even bandwith by order of magnitude right and want to use that as a static treshold or otherwise the system breaks down, well the payment network wouldn't last a minute.

I didn't understand the selection GHOST selection rule at first, but I think I now get it. I'm really stunned, because it overthrows all the reasons that bitcoin does work. The definition of the Ghost algorithm is basically: "The algorithm follows a path from the root of the tree (the genesis block) and chooses at each fork the block leading to the heaviest subtree." Well, first of all there are only nodes in the P2P network. The blockchain exists because of proof of work. No "algorithm" selects a path. One node doesn't even have information which is the heaviest subtree between block 1 and block 2. That's the whole point. That is really the core of the algorithm. You create blocks, so that information can be distributed. Then proof of work is an offset from that point on. The idea of proof of work and timestamp servers existed 10 years before, but it combines those to, to make it work. If chain selection would depend on other node's proof of work as long as its working on the current block, you get an infinite loop. You can't transmit information instantly. So everything depends on creating a pulse, i.e. the timestamp server, so that all nodes operate on the same basis. As I noted the reference to proof of work, as a kind of CPU vote, indicate equal distribution is key here. Which is why mining pools and ASIC's are the big problems. TPS will be probably easily to solve in other ways.

[King Lear]

Well, you could have said exactly the same things about Bitcoin back then when it was just a paper: how nodes in the Bitcoin network are forced to select the longest chain? No one force them. Preferring the longest chain is just a convention, yet if everybody else act according to this convention, you better follow them or else your mining becomes meaningless. The same is true for GHOST.

You asked how nodes will be informed of all tree blocks, and is done simply by propagating valid blocks like today. As there are more blocks to propagate indeed there is a higher chance for someone to miss a block. I think that the standard protocol solves that continuously comparing the list of recent block hashes with the node's neighbors, yet this can be further improved by including previous off-chain blocks' headers within each block (those blocks are off-chain with respect to the chain forms by the block that contains their headers). In my suggested implementation blocks are actually incentive to inform about competitive chains!
 
No one doubts that the original Bitcoin creation is genius, yet even Gavin Andresen is saying that it will not last forever without modifications. So we better be open-minded to look for the next genius creation  

Lear

[FrictionlessCoin]

Thanks for your contribution on coming up with a fair schedule for miner fees.

[coinrevo]

You asked how nodes will be informed of all tree blocks, and is done simply by propagating valid blocks like today.

As indicated above information travels at the speed of light. And with TCP/IP it's 5-10 that. So you need some mechanism to communicate in coordination. The timestamp mechanisms solves that. And GHOST removes the basic communication channel. With such rules there wouldn't be even communication/coordination. The longest chain represents the majority decision. From the bitcoin paper "Nodes express their acceptance of the block by working on creating the next block in the chain, using the hash of the accepted block as the previous hash." If you want to invent a new CC be my guest, but then you have to get all the primitives right. You can't just wave a bunch of equations around and hope it works. Everything in the GHOST paper just doesn't make any sense if you think about it. I mean it just claims it "proves" it solves the 50% attack, without really defining the procedure. It doesn't use even the right terms for node and chain. Anyway, all the best in these efforts.

[FrictionlessCoin]

You asked how nodes will be informed of all tree blocks, and is done simply by propagating valid blocks like today.

As indicated above information travels at the speed of light. And with TCP/IP it's 5-10 that. So you need some mechanism to communicate in coordination. The timestamp mechanisms solves that. And GHOST removes the basic communication channel. With such rules there wouldn't be even communication/coordination. The longest chain represents the majority decision. From the bitcoin paper "Nodes express their acceptance of the block by working on creating the next block in the chain, using the hash of the accepted block as the previous hash." If you want to invent a new CC be my guest, but then you have to get all the primitives right. You can't just wave a bunch of equations around and hope it works. Everything in the GHOST paper just doesn't make any sense if you think about it. I mean it just claims it "proves" it solves the 50% attack, without really defining the procedure. It doesn't use even the right terms for node and chain. Anyway, all the best in these efforts.

Yes,  I'm curious,  how is that supposed to work when you have a subtree?

If you have block C1 and C2 that have B as its parent, then what will the child be of C1 and C2?  Are we combining some kind of hash?

[King Lear]

Hi,

I think that one possible alternative to (securely) accelerate blocks creation is to combine the following proposals: http://www.tik.ee.ethz.ch/file/49318d3f56c1d525aabf7fda78b23fc0/P2P2013_041.pdf and http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03307.html. Basically, the information-propagation paper propose to introduce special kind of messages, that deliver only the block header (including the nonce) so that it will still be possible to validate the PoW (and therefore DoS attacking the system by spamming fake headers is not possible), in order to make blocks propagate faster. Peter Todd suggests allowing blocks to contain invalid transactions, e.g. double spending of money that was already spent in some earlier block. Adopting the first spending transaction and ignoring all letter attempts is enough to maintain security.

So if a miner founds a new block and separately propagates the block header and the block itself (or even only a list of the transactions' hashes), propagation of the block header will quickly inform all the network of the new founded block, and miners can start mining on top of that block even if they have not received yet the block itself. In the worst case, the second miner might include transactions that were already included in the previous block or other invalid transactions (of whom he/she we get no fees).

Yet a possible problem with that solution is regarding the Bloom filter technique, which doesn’t work well if invalid transactions are included in the blocks. So I would like to propose here a possible solution for that, by punishing double spenders: each transaction must include a minimal deposit that is unlocked only after a few blocks (for example, 10) and only in case no earlier double spending transaction have been found. However if there has been such an earlier transaction, the deposit money will be destroyed (may be part of it can be used to compensate the miner who mined the block that contains this invalid transaction). Obviously, if the same exact transaction has been included twice within different blocks in the chain, it will not be regarded as a double-spending transaction.

I personally much prefer the GHOST proposal, and think it will be more efficient.

Lear.

[justusranvier]

I didn't understand the selection GHOST selection rule at first, but I think I now get it. I'm really stunned, because it overthrows all the reasons that bitcoin does work. The definition of the Ghost algorithm is basically: "The algorithm follows a path from the root of the tree (the genesis block) and chooses at each fork the block leading to the heaviest subtree." Well, first of all there are only nodes in the P2P network. The blockchain exists because of proof of work. No "algorithm" selects a path. One node doesn't even have information which is the heaviest subtree between block 1 and block 2. That's the whole point. That is really the core of the algorithm. You create blocks, so that information can be distributed. Then proof of work is an offset from that point on. The idea of proof of work and timestamp servers existed 10 years before, but it combines those to, to make it work. If chain selection would depend on other node's proof of work as long as its working on the current block, you get an infinite loop. You can't transmit information instantly. So everything depends on creating a pulse, i.e. the timestamp server, so that all nodes operate on the same basis. As I noted the reference to proof of work, as a kind of CPU vote, indicate equal distribution is key here. Which is why mining pools and ASIC's are the big problems. TPS will be probably easily to solve in other ways.

OP does not understand the fundamental problems Bitcoin is designed to solve.

OP thinks it's a good idea to ad hard-coded fee rules to the protocol definition.

Yeah, this proposal is going to go far. 

[iddo]

If chain selection would depend on other node's proof of work as long as its working on the current block, you get an infinite loop. You can't transmit information instantly.

Huh? GHOST isn't different from Bitcoin in this regard. Each miner node that follows the Bitcoin protocol tries to extend the heaviest continuation of the blocks history that it is aware of (by using PoW to generate a valid continuation block), and if another node transmitted to it an even heavier continuation of the history, then this miner node switches and tries to extend this heavier continuation. With GHOST it's exactly the same, except that it uses another rule to determine which continuation is the heaviest. Intuitively you can think of GHOST as exploiting orphans PoW that other hopefully honest miners generated (instead of giving zero weight i.e. eliminating this orphans PoW data), but it's true that GHOST nodes need to maintain more complex data structures than Bitcoin nodes. Your objections are incoherent, could you please be more clear?

Edit:
I see that you received answers in the other thread too: https://bitcointalk.org/index.php?topic=359582.msg4333993#msg4333993
Maybe your objection is that orphan solved blocks wouldn't be broadcasted? Honest nodes who follow the GHOST protocol will broadcast the orphan solved blocks to their peers, and rational self-interested miners will also broadcast orphan solved block in the heaviest subtree that they're working on, to increase the probability that their PoW will not go to waste.

Everything in the GHOST paper just doesn't make any sense if you think about it. I mean it just claims it "proves" it solves the 50% attack,

That isn't what it claims, it claims that GHOST can support a higher transaction volume and remain secure against attackers that have less than 50% of the hashpower.

[coinrevo]

see the ghost thread.