Very simple:

Our proposal includes keeping the hashes of off-chain blocks in each block (new ones not included in any of the ancestors of the block). The chain, when read sequentially therefore contains all off-chain block hashes, and thus any node can know the entire tree (if a node is missing some block it simply requests it or its header).

It would work, in the sense that the 50% attack remains hard to carry out, but the number of transactions per second would be really low. Too low to be of any use.
We're working on an extension that would fix that issue as well. It's a bit too early to tell if we'll be able to close all the holes. I haven't thought of it as a solution for an interplanetary currency though 

This is actually required for GHOST, so that nodes have the same world-view and decide on the same leaf -- the off-chain blocks affect your choice of leaf. It is especially important for nodes that were offline for a while and want to catch up. You may in theory be able to do without it, but the convergence time to the same chain would take longer.

Regarding bloat: This is not a difficult issue. First, there is only potential bloat once propagation delays are significantly higher than block creation rates, but more importantly,
The contents of off-chain blocks can be discarded after a short while (e.g., after 1 day). Only the header is needed to verify the difficulty was met. If a switch is needed to some previously discarded subtree, then the node that triggers it, can supply the contents of the blocks as well.

You are right, it may not be as simple as just keeping the one number of "proof for the chain as if block was a leaf" but in principle the following approach works (and its refinement below is probably much more efficient):

Approach 1 (very naive):
1) For each block, save the total amount of work in its subtree. Let us denote this saved value by W(X)=total work of subtree rooted at block X.

In your example above: the subtree of block C includes blocks C,D. The subtree of block C' includes C',D',D''.
2) When a new block arrives, simply increment W(X) for all blocks X along the path to the genesis by the amount of work represented by this new block.
3) If the new block was off-chain, find its connection to the main chain and check if a change to the chain is needed.

(the 2nd step is computationally expensive so the following refinement can be done)

Approach 2 (Lazy evaluation):
The idea here is to still maintain values for total work in the subtree rooted at each block, but to do the updates only when required.
For each block on the main chain we maintain a lower bound on the work in its subtree, for each node off-chain we maintain an exact number. The idea being that off-chain branches die out after a relatively short while, and on-chain blocks that are sufficiently deep in the tree do not need to be examined often.

Invariants: W(X) for any block X that is off chain is exact, W(X) for any block X that is on the main chain is a lower-bound on the real value.

The updates:

When a new block is added:
1) If it extends the current chain, do not update W(X) for any block.
2) Otherwise, if it is off-chain then traverse its path (towards the genesis) until it meets the main chain, and increment the work W(X) of each subtree along the way accordingly. Also traverse the main chain up to this point and update W(X) for each node along the way.
3) check to see if a change of chain is needed. If it is, the off-chain values are exact and can be used to find the new best leaf by following the greedy path towards the leaves.

I hope I explained this well enough for you to at least get the basic idea... Please let me know if I didn't, or if you spot a mistake.

Hi, thanks for taking a look! I think it's a good idea to map out all the changes that need to take place.

Comments:

1) I might be wrong about this, because I haven't looked at the implementation too carefully, but in principle, I think forward and backward traversal of the chain should already be possible: as far as I'm aware, the unspent transaction output set needs to be rolled back if a recent part of the chain is replaced. If I'm not mistaken (and somebody please correct me if I am) the unspent outputs are only maintained for the "best block" and if this is replaced by an alternate chain, it isn't built from scratch.

2) There is also a need to add hashes (or other identifiers) of newly discovered off-chain blocks into each block ("newly discovered" here means: not included inside any other previously reachable block). Nodes must then request such blocks if they do not already have them, and the propagation mechanisms / inv messages need to be adjusted accordingly.


3) I'm not sure what you mean by "the code to invalidate and discard blocks". Can you explain in more detail?

We'd be happy to cooperate with anyone who wants to have a go at an implementation. While we have poked around in the bitcoin source code a bit, I'm afraid we're not familiar enough with the code to pull this off easily ourselves.

I'm also very interested in establishing a testnet that will be stress tested with many transactions per second. If you have an idea on how to do this, I'd be happy to know.

Feel free to email me directly regarding any of these projects.

maaku,

That's very interesting. Can you pinpoint the reason for this? Can you elaborate on your setup?

In theory(*), there shouldn't be a very high networking load at the moment.
Blocks are currently under 1MB, and there is less than one transaction per second. This implies sending 1MB once every 10 minutes, + around 1/2 KB per second for streaming transactions. All of this should be multiplied at most by the number of connections your client has, but in practice, most nodes should receive flooded messages and don't have to forward to others (Edit: in expectation, every node receives a message once, and so every node should in expectation only send each message out once). This shouldn't be too prohibitive...

There is additional load due to new nodes that come online and need to catch up and so may download many blocks at the same time. Perhaps this is the source of the trouble?
(Edit: I'm also ignoring inv messages and other small protocol messages above)

---

(*) as they say: in theory, there is no difference between theory and practice, in practice, there is.

maaku, how is this related to scalability? You could have 0 transactions going through Bitcoin and still the cost of running a node would be high. The reason for that is high competition in mining brought on by the costs of specialized hardware. I don't see the connection.

I don't think I understood your first point. I'll be happy if you could elaborate: are you referring to something regarding the re-targeting moment?

As for number 2: it seems like if there are two factions insisting on building split subtrees then one of these trees eventually grows larger than the other (even if they are evenly matched! See our analysis of "collapse" in the paper for this exact scenario) in this case one of those factions is not abiding by the protocol if it doesn't switch to the other tree -- this is a 50% attacker.

Nobody said that propagation delays are the *only* obstacle. We said they are currently the *primary* obstacle, because currently you will run into the trouble at much lower tps.



I agree with you that it is quite likely that BTC is less scalable than the dollar and other centralized systems, but it is worth it to try and get as close as possible. Plus, you still can't completely rule out the chance that someone will find a way to distribute the workload and not just distribute trust among the many nodes.

Iddo, a collapse has to occur. This is exactly the same reasoning as in Theorem 8.6 in the paper: block construction is stochastic, so the two forks are not synchronized perfectly even if they have exactly the same amount of hash power supporting them.  The differences in block creation times drift apart until they grow larger than the time it takes to send the message about the total weight in the branch. Thus, a collapse eventually occurs.

With anti-Dos it's highly unlikely that you get into these sort of forks in the first place: you do accept all blocks created, say, in the past month or so (difficulty is high enough that they are not really a DoS attack). A fork that breaks DoS rules will only form if 1) an attacker manages to keep up with the network's rate for a whole month (has to be a 50% attack) 2) the network is disconnected for over a month. Even in these cases, the forks resolve rather quickly.

Besides, another heuristic can also help here: accept alternative branches into the tree even if they have 80% of the total weight of your current branch. This is still enough to stop a DoS, and certainly enough to make DoS forks collapse instantly.

maaku, can you provide a link to how Bitcoin would prevent similar DoS attacks (without checkpoints that is)?

I'd like to address that critique, but I don't know how it's solved in Bitcoin.

Peter,

I keep trying to agree with you.

One last try before I give up:

Surely you must agree that if there were no block propagation delays, there would be no centralization associated with scaling up. Blocks go instantly to everyone, and there are no problems with miners getting more than their share of the blocks.

I guess the difference in our perspectives is that I don't think these are optional tradeoffs. If at some point bitcoin becomes mainstream, there will be an increased pressure to allow more transactions through (or alternatively, fees will soar higher than the money transmitters Bitcoin is trying to replace). You then run into several problems. One is a security problem against attackers. The other is a pull towards centralization. All I'm saying is that we claim to solve the first problem. The second clearly remains.

Peter, I agree with you that there is a big problem with high orphan rates, but this is not a symptom of GHOST, but rather a symptom of high transaction rates.

Whether you use GHOST or Longest-chain at high rates you must either resort to large blocks that propagate slowly or to high block creation rates. There is no getting around that. Both cause a high orphan rate (or perhaps the right term to use is high rate of off-chain blocks). we do not pretend GHOST solves this problem The only thing we claim is that GHOST makes the protocol secure at high rates -- the 50% attack can no longer be executed with less than 50% of the hash rate.

You are right, the chain is never really fixed.  But think of it this way: under the standard protocol, a chain only gets replaced by a longer one. We thus only look at the length of the longest chain (ignoring which one it actually is) and check the rate of events that make it grow (this could include a switch to a different chain).


Thanks! That's an interesting comment that we did not consider. I suppose you refer to issues related to stale shares?

The idea is to still accept transactions only from a single chain, but to allow blocks off the chain to also contribute confirmations to the part of the chain they reference.
Think of it this way:
Each block gives 1 confirmation to the block it references directly, and to all preceding blocks.
If there is a fork at level h, and you need to decide which one to consider as the right path to take, simply pick the block with the most confirmations (rather than the block that supports the longest chain).


RE altcoins based on this improvement:

1) I think it's more important to see a testnet that is stress-tested with large transaction loads. This is something worth doing that others have mentioned on countless occasions.

2) IMO, if crypto-currencies succeed as we hope they do (and Bitcoin is probably the most likely to grow to large sizes at this point) they will end up with high transaction rates. So we think eventually something will have to be done. Half of our paper is dedicated to what happens to Bitcoin without our protocol improvement. There is room for growth there, but we worry that after a while security becomes an issue (the 50% attack is easier, and you need to wait more blocks for the same level of certainty when facing weaker attackers).

You make a really good point. Decentralization is hurt at higher transaction rates, and better incentives are needed. We do mention it as a problem that remains at the very end of the paper (issues related to decentralization). The problem seems inherent to both our suggestion and to Bitcoin's current implementation.

Let me just say, that with small block sizes (i.e., when full bloom filters are implemented) it will be very hard to distribute blocks faster than the network does already. IMO, this is less of a problem than people think.

Solutions that have been proposed in the past like the mini-blockchain idea still work in this case as well.

stephwen: We've submitted it, but it is still unpublished.

trout: The protocol still ends up picking a main chain, and fees + rewards still go to these blocks.
It may be interesting to reward off-chain blocks as well, but we didn't find a nice way to do this without ruining the money creation schedule.

Hi all,

I'm a researcher at the Hebrew University in Israel, and I've been working with a student (Yonatan Sompolinsky) on a Bitcoin related paper. We have really exciting results that we are eager to share with the Bitcoin community. We would really like to get constructive feedback on our work from the many smart people in the community, which is why I am posting here.

Here is a link to the full paper: http://www.cs.huji.ac.il/~avivz/pubs/13/btc_scalability_full.pdf
Title: Accelerating Bitcoin's Transaction Processing (Fast Money Grows on Trees, Not Chains)

Edit: Thanks for all the good feedback! Recap of main issues and questions added below.

As the paper is quite lengthy, and is written for an academic audience (which, sadly, is not usually familiar with the protocol) we thought it best to also provide a quick explanation of our results aimed at Bitcoiners:

tl;dr:  We suggest a protocol modification to the block chain that securely allows blocks to be generated around once per second, can handle over 200 transactions per second at these rates, and consumes under 0.5 MBps in terms of bandwidth (less at lower rates than 200 TPS). All of this with no increased susceptability to 50% attacks. This essentially solves the problem that caused Satoshi to set the 10 minute target for the block creation rate. We also analyze the number of transactions per second Bitcoin can handle with and without our modification. We note that block propagation times are the primary obstacle for scalability.


A more detailed explanation follows bellow. The primary goal of our research is to address Bitcoin's ability to process transactions quickly, and in large volumes. Here are our main findings:

Scalibility, Delays & Security:


We begin our paper by examining the exact effects of high transaction rates on Bitcoin's security (Following in the footsteps of previous work by Decker and Wattenhofer). The number of transactions per second (TPS) that Bitcoin can handle is limited by two main things: 1) The block creation rate (of 1 block every 10 minutes) and 2) the block size limit (currently at a 1MB default). These two parameters combine to limit the number of transactions per second that Bitcoin can process. The straightforward way to increase the TPS is to either increase the block size, or to increase the block creation rate. Both of these changes are controversial, and for good reason: both may affect the security guarantees of the protocol. First, let us consider an increase in the number of blocks per second (e.g., Litecoin's blocks that are created every 2.5 minutes, or even Fastcoin with its extreme 12 second blocks). Because blocks are created quickly, many conflicting blocks are created. Most will end up off the blockchain. The same symptom occurs when the block size is increased: large blocks take longer to propagate through the network (due to bandwidth limitations) and blocks that are created in the meantime are likely built on top of older blocks, i.e., they will be wasted.

The fact that many blocks are wasted lowers the security of the network and makes it more susceptible to 50% attacks. For example, if half the blocks are wasted in this manner, the network essentially wastes half its hash power on blocks that do not contribute confirmations to transactions. An attacker which is centralized and has no delays, can execute a so-called 50% attack with only slightly more than 33% of the hash power. This is because it can easily create longer chains than the rest of the network (botnets that still suffer from the effect of internal delays are less effective than centralized attackers).
Using different techniques, we analyze how many blocks end up in the chain, and how many are discarded, and use this to estimate the change in security for different parameters. Among other results, we show that transmitting blocks that contain only transaction hashes (instead of full transaction records) will greatly help scalability (i.e., this is not just a 2-fold saving in bandwidth, but rather a 16-fold increase in the number of transactions per second!).

Our suggested protocol modification (which appears in section 8 of our paper):

Since high transaction rates imply many conflicting blocks are created, it would be quite useful if these blocks were not really lost. In fact, each block can be seen as supporting not just transactions inside it, but also those embedded in previous blocks. Even if a block is not in the main chain,  we can still count the confirmations it gives previous blocks as valid. This is the basis of our proposed modification, which we call the "Greedy Heaviest-Observed Sub-Tree" chain selection rule.

Roughly speaking, since each block contains a hash of its predecessor, all blocks form a tree structure, rooted at the Genesis Block. Bitcoin currently selects the accepted history as the longest (or rather heaviest) chain in the tree. We suggest another approach: At each fork, pick the sub-tree containing the most blocks (or rather the blocks with greatest combined difficulty). Do this repeatedly until reaching a leaf. The path traversed is the chain that nodes should accept. But how does this help? Notice now, that an attacker that wishes to change the main-chain selected by the algorithm needs to make us change our decision in one of the forks. To do so, he needs to build more blocks than are contained in the entire sub-tree (and not just more blocks than are contained in the longest chain!).

Here is the pseudo-code of the GHOST chain selection rule:

1. SET B <- Genesis Block.
2. IF B has no successors: RETURN(B).
   Else: SET B <- Child of B with heaviest sub-tree.
3. GOTO 2

The cost of such a modification: At low block creation rates, and small block sizes there is almost no difference between the longest-chain rule and the GHOST-rule. There is no cost. Both are almost identical since the longest chain in these cases is also the heaviest subtree. In high transaction rates, GHOST builds slightly less blocks in its main-chain (because it doesn't always extend the longest chain), thus slightly lowering the number of transactions accepted per second, but it does so more securely! Delays and many off-chain blocks no longer make it more susceptible to 50% attacks. This implies that we can increase the block creation rates and block size to levels that were previously too risky and easily make up for the loss in transaction volumes. In fact, we estimate that 1 second blocks can be easily combined with rates of over 200 TPS.  This implies quite fast authorization times, but much more importantly, an increased granularity in confirmations. Even 1 confirmation gives some level of certainty regarding irreversibly, and it comes almost instantly when blocks are generated every second.

Since Bitcoin's security relies primarily on the number of confirmations received instead of on elapsed time, we end up getting irreversibility of transactions with very high probability in far less than 10 minutes.  

Recap of main issues and questions raised:
I'd like to clarify one thing: We do not claim to be able to solve every problem one might think of with regards to Bitcoin's various aspects (incentives, mining centralization, etc.) so I think we are criticized for problems that are already there in the protocol. Our main claim is that security gets very bad if high transaction rates occur, and the GHOST modification fixes that (and that alone). If you are uncomfortable with 1 second blocks, the modification is equally valuable at lower block rates. The need to address high transaction rates is still there.

Some specific comments:

1) Advantage of nodes with low latency. Nodes that can reach the rest of the network quickly have more blocks on the main chain and less orphans.

Answer: This is a serious problem that the current bitcoin protocol will face if high transaction rates (i.e., large block sizes) are sent through the system. Strong miners will be able to get more than their proportional share of the blocks. We don't improve things, but the GHOST modification doesn't hurt either. The only improvement that we offer, is that the 50% attack does not get worse in these scenarios.

2) DDOS attack: Malicious nodes can mine blocks above the genesis block at difficulty 1 and spam the network

Answer: This too as a problem that the current bitcoin protocol faces. It's why checkpoints are constantly put in place. (anyone can currently claim to have a chain with harder proofs of work, and just start sending difficulty 1 blocks in a long chain that never ends. See here for gmaxwell's explanation:
https://bitcointalk.org/index.php?topic=194078.msg2014204#msg2014204.
Checkpoints can also be applied to our solution.

Edit: several people have noted that there are other solutions besides checkpoints (not currently implemented). We'll need to see if these can be adapted here as well. I currently have no reason to believe this won't be possible.

3) SPV clients need more bandwidth + storage if there are blocks every second (given that there will be 600 times as many block headers to download).

Answer: This is true. But the fix should probably be to find better mechanisms for the SPV nodes. For example, it should be possible to probabilistically verify a long chain of block headers without actually downloading all of them. Here's a basic idea: Have the full node build a merkle tree of all blocks +difficulties, and send it to the SPV client. The SPV client picks blocks at random from the chain (weighed by the difficulty the should have) and requests merkle branches to them (from the root it had sent) + checks their difficulty. just a few checks would be enough to verify that there is indeed enough work stored in the chain (with very high probability).

4) Implemenation: How would nodes know about orphaned blocks if they were offline for a while?

Answer: We suggest that each block will also contain hashes of off-chain (orphaned) blocks in its header (only those not written in blocks it built upon). This way, the main chain also contains a record of all off-chain blocks, so it knows what to ask for.  Another reason we think it is a good idea: We think difficulty should be retargeted according to the total number of blocks built per second (incl. orphans), not based on the length of the longest chain (retargetting for that is harder at high rates).

5) Storage issue: a lot of space will be needed

Answer: Solutions like the mini-blockchain are still applicable, and allow you to keep only a record of recent events. Still there is no getting around the fact that high transaction rates will require a lot of storage (It's not easy scaling to the size of Paypal / VISA). Again, this is not caused by our modification. You do not need to keep the contents of orphaned blocks -- only their headers to verify difficulty. Having more blocks in the chain per second merely implies each one of them will have fewer transactions inside it. The only added cost is keeping more headers.