Proposal: A Second Chain for Scalability

[BrightAnarchist]

Here is what I propose:

• Every block in the block chain only pays out 90% 99.9% of its block reward. The other 10% 0.1% is kept on reserve in the block.
• A second "balance" chain is created, which consists of transaction chain blocks hashed in a tree along with the usual nonce and a hash of the previous balance chain block.
• Each balance chain block holds the balance of every non-empty bitcoin address up to the point of the last transaction block included.
• The balance chain difficulty is 100X 1000X the transaction chain difficulty.
• The node that solves a balance chain block recieves all of the reserved block rewards from the included transaction blocks.
• In this manner, over time old transaction blocks can be forgotten since the most recent balance block plus the most recent transaction blocks are all that are needed to verify transactions. To keep the integrity of the network, of course, more history should be saved, but we probablly don't need more than a few thousand balance blocks while still being very secure.
  In this manner, the only data required for each full node would be: (1) block headers for all balance blocks (2) the most recent balance block (3) transaction blocks that occurred after the most recent balance block.
  

Do you think this scheme could work? I'm not even remotely an expert on this stuff, so forgive any glaring errors. Thanks!

[Andrew Bitcoiner]

That's pretty interesting. One thing that I see is that you would have to have people mining all the chains though and each one would still be vulnerable to the 51% attack unless say they confirm a merkle hash of each block in each chain.

[bfever]

Here is what I propose:

• In this manner, over time old transaction blocks can be forgotten since the most recent balance block plus the most recent transaction blocks are all that are needed to verify transactions. To keep the integrity of the network, of course, more history should be saved, but we probablly don't need more than a few thousand balance blocks while still being very secure.

Do you think this scheme could work? I'm not even remotely an expert on this stuff, so forgive any glaring errors. Thanks!

If you want to be able to verify transactions from "most recent balance block + transactions since this balance block", this "balance block" does not only need to record the balance of each bitcoin address, but in fact (the full details of) each "non-spent" transaction.
Some data around block height 181185: there are 659574 bitcoin addresses with a non-zero balance, and 1591739 "non-spent" transactions. This is at least 391 Mb of data you need to include in the balance block (at least 258 bytes per transaction), if my math is correct. Or at least a 1 hour download on a decent DSL line (not taking into account other nodes will want to get the data too).

So this can reduce storage space requirements (Mbytes instead of GBytes) and transaction lookup times, but network load will be higher (peers need also to relay the second chain).
At the current transaction volume (1100 transactions/h = 400 kb/h or 9.6Mb a day), it is definitely not a good solution: 1 balance block a day = 400 Mb a day (390Mb for that 1 block + 9.6Mb of new transactions), or an increase of 40 times the network load !

[BrightAnarchist]

Here is what I propose:

• In this manner, over time old transaction blocks can be forgotten since the most recent balance block plus the most recent transaction blocks are all that are needed to verify transactions. To keep the integrity of the network, of course, more history should be saved, but we probablly don't need more than a few thousand balance blocks while still being very secure.

Do you think this scheme could work? I'm not even remotely an expert on this stuff, so forgive any glaring errors. Thanks!

If you want to be able to verify transactions from "most recent balance block + transactions since this balance block", this "balance block" does not only need to record the balance of each bitcoin address, but in fact (the full details of) each "non-spent" transaction.
Some data around block height 181185: there are 659574 bitcoin addresses with a non-zero balance, and 1591739 "non-spent" transactions. This is at least 391 Mb of data you need to include in the balance block (at least 258 bytes per transaction), if my math is correct. Or at least a 1 hour download on a decent DSL line (not taking into account other nodes will want to get the data too).

So this can reduce storage space requirements (Mbytes instead of GBytes) and transaction lookup times, but network load will be higher (peers need also to relay the second chain).
At the current transaction volume (1100 transactions/h = 400 kb/h or 9.6Mb a day), it is definitely not a good solution: 1 balance block a day = 400 Mb a day (390Mb for that 1 block + 9.6Mb of new transactions), or an increase of 40 times the network load !

Why would the balance chain need to be shared on the network? It can easily be computed using the transaction chain, since each balance block specifically covers "up to" a certain transaction block. Only the nonce values would have to be shared on the network for the balance blocks.

[DeathAndTaxes]

Why would the balance chain need to be shared on the network? It can easily be computed using the transaction chain, since each balance block specifically covers "up to" a certain transaction block. Only the nonce values would have to be shared on the network for the balance blocks.

Hmm interesting.

So the node solving the balance block just broadcasts the balance block header and every node constructs and verifies the balance block locally.  Once a balance block is deep enough in the balance blockchain it for all intents and purposes can become the genesis block and data prior to it (both balance blocks and tx blocks) can be truncated to save space.

I would make the balance block more like tx block difficulty x 1000.  Since you need to record all unspent outputs having too many balance blocks simply increases the workload on the network.  At block difficulty x 1000 there would be a new balance block ~ once every week.

So the next question becomes how do you bootstrap a new node if not all nodes have blocks going back to the genesis block?

Boostraping a new node could be done something like this:
Node requests the oldest active balance block (say balance block 6** blocks deep.
Node downloads this block and considers it an unverified "genesis balance block".*
Node requests and downloads all tx blocks since the "genesis balance block".
Node requests headers for the newer balance blocks.
Node constructs and verifies the subsequent balance blocks.

Node now has a complete history from the balance block to now.  To spoof this would require work equal to (balance block depth)*(balance block difficulty)

* This new node will never have any tx history prior to this block.  From this node' point of view the network began here.
** 6 was chosen arbitrarily but some number would provide sufficient assurance that the block is legit.  If a BB is 100x harder than normal block then verifying a chain 6 deep represents 600 blocks worth of hashing power.  

A very interesting idea.

[BoardGameCoin]

Something along this line is necessary... In the design there's some talk of merkle-trees, which I think were supposed to perform a similar function, but I believe something like this is ultimately a better solution.

Changing the block reward seems a poor choice. I propose instead that we rate-limit the balance blocks, e.g. one per difficulty change, and then hash them into the same chain (e.g., have the solved block reference both the balance block and the parent block), and just wait something like 60 confirmations before relying on the balance block (an inconsistent balance block would cause the solved block to be rejected).

-bgc

[BoardGameCoin]

It might be necessary to require that the first block after a difficulty change be a balance block...

-bgc

[DeathAndTaxes]

It might be necessary to require that the first block after a difficulty change be a balance block...

-bgc

That won't work.

You wouldn't be able to make it higher difficulty.  If it was 100x normal difficulty then there would be no blocks for roughly a day.  If the balance block wasn't higher difficulty then it would be "weak".    An attacker could cheaply construct a false chain.

By making the balance blocks higher difficulty you make it computationally infeasible for the attacker to construct an entire false chain.  Remember if  some old balance block eventually become a new "genesis block" then we need to make sure it is not possible for an attacker to simply rewrite the chain. 


As an exmaple if balance blocks are not relied upon until they are 10 blocks deep into the chain AND balance block difficulty is 1000x normal then to create a false chain would require the attacker to have same hashing power as generating 10,000 normal blocks.

In your proposal it would be far too easy to construct a false chain that begins with a fake balance block (one low difficulty balance block and 60 more blocks).  An attacker could spoof new nodes into think that is the "reality".

[BoardGameCoin]

In my proposal, the balance block is validated for consistency by all nodes, and eliminated if its inconsistent, and there's no extra reward for this... but the block isn't USED until it has e.g. 60 or 600 blocks after it, essentially 'locking it in'. How does this not work?

-bgc

[BrightAnarchist]

FYI I made a few edits to the OP ( using strikethrough ) based on the suggestions made thus far

[DeathAndTaxes]

In my proposal, the balance block is validated for consistency by all nodes, and eliminated if its inconsistent, and there's no extra reward for this... but the block isn't USED until it has e.g. 60 or 600 blocks after it, essentially 'locking it in'. How does this not work?

-bgc

Then what is the point of even having a balance block?  The point of a balance block would to allow nodes to eventually forget older data.  New nodes won't have old data to rely upon.  By making the block cheap to construct you just made it trivially easy for an attacker to "spoof" new nodes and provide them with a "false history".  It is a modified version of an isolation attack except more devestating and much cheaper. 

If you never get rid of old data then yes new nodes can reduce the danger by downloading everything back to the genesis block however there is no point in even hashing all unspent tx into a balance block.

So you either can rely on an old balance block as canonical or you can't.   If it is cheap to construct then you can't.

[DeathAndTaxes]

FYI I made a few edits to the OP ( using strikethrough ) based on the suggestions made thus far

I think it needs to be analyze but it has merit.  The reality is Bitcoin will never change to that but it would be a good concept to test in an alt chain.  It puts a max limit on how "old" the block chain is.  Rather being  "from genesis to now" the blockchain becomes more a rolling 10,000 (or 50,000, or 100,000 ) blocks.  

[BrightAnarchist]

FYI I made a few edits to the OP ( using strikethrough ) based on the suggestions made thus far

I think it needs to be analyze but it has merit.  The reality is Bitcoin will never change to that but it would be a good concept to test in an alt chain.  It puts a max limit on how "old" the block chain is.  Rather than "from genesis" to now the blockchain becomes more a rolling 10,000 (or 50,000, or 100,000 ) blocks.  

True, it should be tested as an alt-chain. Maybe "rollcoin" or something.

I'm sure there are a million problems with this approach that just aren't immediately apparent

[BoardGameCoin]

Then what is the point of even having a balance block?  The point of a balance block would to allow nodes to eventually forget older data.  New nodes won't have old data to rely upon.  By making the block cheap to construct you just made it trivially easy for an attacker to "spoof" new nodes and provide them with a "false history".  It is a modified version of an isolation attack except more devestating and much cheaper. 

If you never get rid of old data then yes new nodes can reduce the danger by downloading everything back to the genesis block however there is no point in even hashing all unspent tx into a balance block.

So you either can rely on an old balance block as canonical or you can't.   If it is cheap to construct then you can't.

My suggestion is NOT cheap to construct. If you can isolate a node and it carries NO history, then you could generate a fake history just as long as the current blockchain with a few graphics cards: just imagine the difficulty staying constant from the genesis block. Currently this is prevented in two ways: the client software includes hashes of some known blocks, and the bootstrapping process connects you to what are supposed to be legitimate nodes. Clients would not trust a balance block until it has e.g. 600 blocks on top of it at the current difficulty.

Maybe I'm missing something obvious, can you link me a description of the kind of attack or limitation that is not present in the current network but would be present with a balance block extension?

-bgc

[d'aniel]

I'd say avoid any rule changes by forgetting about changing bitcoin's reward scheme to incentivise miners to hash away at the balance chain, since updating the ledger once a week is practically free, merged mining makes the hashing cost nothing extra, and by participating they'll be enabling significant disk space savings for themselves going forward.  Plenty of incentive there already IMO.

Then it can be gradually adopted by miners without controversy, and once enough of them are on board, as measured by the balance chain block rate, other clients can feel free to start trusting it.

Also, instead of having a simple tx tree, maybe use something like this structure instead: https://bitcointalk.org/index.php?topic=52859.msg885838#msg885838.

I'm an amateur here too, though, so maybe there are lots of problems with this we're not seeing.

[BrightAnarchist]

Hmm the more I think about this the more I think it could work.

In reality, you only need to store the most recent balance block and subsequent transaction blocks. As long as you have block headers for all previous balance blocks, you can be assured that noone can cheaply spoof a fake balance chain due to the high cost of each proof of work. You wouldn't even need old transaction block headers, and you could easily bootstrap a new node just by sending them (1) the balance block headers (2) the most recent balance block (3) all transaction blocks that occurred after the most recent balance block.

This would cut storage requirements massively.

I just need to find some free time so I can code this up

[etotheipi]

Hmm the more I think about this the more I think it could work.

In reality, you only need to store the most recent balance block and subsequent transaction blocks. As long as you have block headers for all previous balance blocks, you can be assured that noone can cheaply spoof a fake balance chain due to the high cost of each proof of work. You wouldn't even need old transaction block headers, and you could easily bootstrap a new node just by sending them (1) the balance block headers (2) the most recent balance block (3) all transaction blocks that occurred after the most recent balance block.

This would cut storage requirements massively.

I just need to find some free time so I can code this up

I had grand plans of pioneering ideas like this.  And this might be the other half of the solution to the other scalable-blockchain thread (which I expanded upon, and d'aniel linked above: https://bitcointalk.org/index.php?topic=52859.msg885838#msg885838).  Complexity is a problem though... creating a new blockchain with the networking, etc, is not a trivial task (or maybe it is, since there's so many other merged-mining chains to use as a template).  Also, I don't know what the compute-complexity of the balance trees are.  I'm going to have to spend some time with pencil&paper on this one...  At least the chain itself will be small once it's running...

On the upside, if it is feasible, it would be totally worth it.  It would completely enable lightweight nodes to get on the network and verify their own balances and unspent-output lists without downloading even the pruned blockchain -- they'd only need the headers of the main chain and balance chain, and one merkle branch per address (a few KB).  I had kind of looked past the idea because I assumed it was going to cause a hard fork, but using a second chain seems to solve that elegantly...

[Gavin Andresen]

So code up a prototype:

+ Implement code that computes and publishes 'balance blocks' and 'balance block hashes'. Convince a couple people with extra download bandwidth to run it.
+ Modify one of the bitcoin implementations to download the latest 'balance block' from some trusted place at startup, and use it if transactions/blocks can't be found in the traditional block database.
+ Extra credit/paranoia : query a couple of trusted places for the balance block hash, and make sure it matches the hash you got.
+ OR: randomly spot-check the balance block by requesting blocks in the traditional way, and make sure the balance block doesn't list any outputs as unspent that are actually spent.

You don't want bitcoin address balances, there are no addresses way down deep inside. You need to know which transaction outputs have not yet been spent, and the value of those outputs.

I'm not excited about this proposal, because I think it is solving a problem that doesn't need solving yet, and my priorities for bitcoin continue to be wallet security and network stability, not making it quicker for newbie solo miners to get a full blockchain so they can start validating transactions/blocks.

[etotheipi]

So code up a prototype:

+ Implement code that computes and publishes 'balance blocks' and 'balance block hashes'. Convince a couple people with extra download bandwidth to run it.
+ Modify one of the bitcoin implementations to download the latest 'balance block' from some trusted place at startup, and use it if transactions/blocks can't be found in the traditional block database.
+ Extra credit/paranoia : query a couple of trusted places for the balance block hash, and make sure it matches the hash you got.
+ OR: randomly spot-check the balance block by requesting blocks in the traditional way, and make sure the balance block doesn't list any outputs as unspent that are actually spent.

You don't want bitcoin address balances, there are no addresses way down deep inside. You need to know which transaction outputs have not yet been spent, and the value of those outputs.

I'm not excited about this proposal, because I think it is solving a problem that doesn't need solving yet, and my priorities for bitcoin continue to be wallet security and network stability, not making it quicker for newbie solo miners to get a full blockchain so they can start validating transactions/blocks.

Gavin,

If your re-read my proposal on the other thread, the proposal does enable you to get the entire unspent-txout-list for any address, with only a few kB from the network (after you have the headers).  This means that you only download a couple kB from the network for each script/address in your wallet and you can operate fully without trusting anyone or anything except for the headers.

Hash160 addresses used more than once will have the same script hash and thus be aggregated into a multi-node sub-merkle-tree.  BIP 16 and other creative scripts used once will be leaf nodes represented by only a single-node sub-merkle tree (well it would just be a single value, not a tree).

This isn't for miners... this is for lightweight users.  It means that I can import an address on my phone wallet and get a full list of unspent outputs with only the headers plus a few kB from the network -- you only need the master-merkle branch (which is O(log(N)) where N is the number of unique scripts/addresses in the blockchain) and the sub-merkle tree (which is the number of unspent txouts for that script/address).  That's a huge improvement for Bitcoin as a whole, when even crappy smartphones can be 99% fully operational, using only block headers and a few kB from the network.  (I say 99% because they can't do 100% of the verification needed for mining, but they can at least verify that the inputs of a zero-confirmation-tx are valid and unspent without relying on any other service).

It's always been an assumption in my mind that lightweight nodes will be second-class citizens in the BTC world.  But if this can be made to work, computationally, I believe even lightweight nodes can be as secure as full nodes.  And of course, you get the 90%+ compression.  And it's all opt-in -- client developers can just ignore the second chain if they want.

The remaining uncertainties are:  (1) How complex will it be to maintain a separate blockchain and all that stuff, and (2) what is the compute complexity/optimizations of building & updating such a blockchain?

[Gavin Andresen]

etotheipi:

Sorry, I was responding to the original proposal, not yours, I should have made that clear.

Better protocol support for lightweight clients is a Good Idea.