Bitcoin Forum
December 04, 2016, 10:23:49 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: scalability/divide and conquer  (Read 1787 times)
killerstorm
Legendary
*
Offline Offline

Activity: 994



View Profile
June 02, 2011, 12:47:22 AM
 #1

I've noticed that one of main concerns about long-term viability of Bitcoin is scalability: when all transactions are broadcast to all nodes it is simply ...way too much.

Wiki article on the topic (https://en.bitcoin.it/wiki/Scalability) essentially says that in future we will have faster computers, but many would say that it is not an acceptable solution because in this case Bitcoin won't be truly P2P anymore because only large, expensive nodes will be able to handle the load. And so there are talks about 'collusion problem'.

Another voiced concern is that http://blog.ezyang.com/2011/06/bitcoin-is-not-decentralized/ there is no straightforward update mechanism for the case when something goes awry...

As I'm generally curious about distributed/p2p protocols/algorithms I've tried to think of a possible solution for this problem(s), and I've got an idea which at least on surface looks viable. Here is it (or, rather, a thought process):

While block chain structure is a 'difficult' object from scalability perspective, it is best we have now (unless somebody will find a method to prevent double spending with DHTs, for example), so let's consider more scalable bitcoin-like systems which still use block chains.

There are two possibilities: 1) somehow make blocks smaller; 2) apply divide&conquer strategy.

First option was discussed in the wiki article on scalability and it looks like possible improvements are limited.

So let's consider possible divide & conquer opportunities.

If we could somehow split block chain among nodes... that probably won't solve anything because we still need blocks to verify transactions. (Although, maybe, some blocks are very rarely used? Then there is a possible improvement, but probably a relatively small one.)

The only other possibility is to have many chains each of which incorporates a disjoin set of transactions. Then size of each individual chain will be smaller than of a large chain and this solves the problem: if nodes are overloaded then we just need to spawn more chains.

There is a problem, though: interoperability. Multiple independent chains are much less useful than one chain.

Can we achieve interoperability while still having many chains?

One solution is to allow transactions between addresses belonging to different chains. Let's say we have address foo123 belonging to chain foo and bar456 belonging to chain bar. When money is sent from foo123 to bar456 it is recorded in both foo123 and bar456 block chains. Chain foo can verify transaction on its own. Chain bar can use a simplified verification mechanism on chain foo to make sure that transaction is valid (foo123 has money).

This means that nodes of each chain need to be able to run simple verification on transactions of each other chain. This is better than nothing as it reduces amount of information required by each not, but still doesn't scale very well.

It looks like "each to each" part causes problem. What if chains would not exchange directly but instead would use a 'hub' chain?

This is my idea. More detailed description:

Let's say we have arbitrary number of 'numbered' chains (chain1, chain2 ... chainN, collectively known as chainZ) and one 'hub' chain. Each individual block chain has a distinct address space (e.g. an addresses are prefixed by chain name, e.g. chain1-XXX) and can do transactions just like Bitcoin chain does it now.

Chains cannot exchange between each other, but they can exchange with hub. So transactions chain1-XXX -> hub-YYY and hub-YYY->chain1-XXX are allowed.

Of course both hub and chainZ need to be able to verify these interop transactions.

For chainZ it is simple: each node of chainZ needs to keep track of a hub's block chain. Then it can verify transactions coming from hub addresses directly. Presumable size of chainZ + hub << size of all chainZ.

For hub it is more complex. Ideally each hub's node needs to keep track of ALL chainZ, at least in 'simple verification' form. But if it is not feasible it can track only some chainZ (or none of them, only hub).

In this case if miner tracks chain1 and chain2 but not chain3 he can include only transactions from chain1 and chain2 addresses but not from chain3 in blocks he mines. So there is an incentive to track as many chains as possible.

I'm not quite sure this 'optional verification' is sound, let's for simplicity assume that each hub node tracks all chainZ at least in scope of simplified verification.

Obviously, hub's nodes are much more strained than chainZ nodes. Then they can justify higher transaction fees.

And thus users have incentive to keep their money in one of chainZ but not in hub to keep fees low. This also means that they need to trade within a single chain.

This shouldn't be a problem because client software can easily work with multiple chains. For example, if customer has money in chain3 merchant can allocate a new address in chain3 and handle transaction. Then he will create address in a different chain for a different customer. He only needs to move money between chains only if he needs collect a large sum in a single address.

As for 'chain strength', miners can include hashes of blocks in other chains in their blocks: chainZ will include hub's block's hashes and hub will include hashes of all blocks. This cross-signing will make it about as strong as one single chain.

And, finally, this solves a problem with protocol updates: each chain can run a somewhat different protocol! If, say, chain5 has some undesirable properties people will move their money off chain5 via hub, so eventually it will be fully abandoned. Then, maybe, some super-secure chain15 will appear and people will move their money to this new chain. Upgrading hub is more problematic, but not impossible. (It would mean a short-term disruption of interoperability.)

Oh, and chains can be added dynamically through consensus of hub's miners. (Likewise, hub can be upgraded through consensus of chainZ.)

Thoughts?

colored coins proof-of-concept: private currencies, stock/bond p2p exchange

Tips and donations: 16v13Fa9cPmfFzpm9mmbWwAkXY4gyY6uh4
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480890229
Hero Member
*
Offline Offline

Posts: 1480890229

View Profile Personal Message (Offline)

Ignore
1480890229
Reply with quote  #2

1480890229
Report to moderator
1480890229
Hero Member
*
Offline Offline

Posts: 1480890229

View Profile Personal Message (Offline)

Ignore
1480890229
Reply with quote  #2

1480890229
Report to moderator
1480890229
Hero Member
*
Offline Offline

Posts: 1480890229

View Profile Personal Message (Offline)

Ignore
1480890229
Reply with quote  #2

1480890229
Report to moderator
adrian33
Member
**
Offline Offline

Activity: 119


View Profile
June 02, 2011, 11:04:07 AM
 #2

There was a similar criticism here 14 days ago:

http://news.ycombinator.com/item?id=2561403

Quote
Bitcoin uses a distributed timestamping server. The paper literally states that "new transactions are broadcast to all nodes". This effectively means that they need a global broadcast to the majority of nodes for every bit coin transfer.

This doesn't scale in terms of number of nodes, and it doesn't scale in number of transactions. They can not compensate for an increase in the number of transactions by adding more nodes because instead of distributing the work load over the nodes, they are in fact replicating it.

The rationale seems to be that as long as you have more honest nodes than malicious ones the system will not be hijacked. Of course, the chance that a Russian botnet has more CPU power than you do is quite real. They go on to say that if an attacker has more computational power than everyone else they would do better to use it mining coins than to break the system, and they seem to leave it at that. Counting on the rational behavior of potential attackers does not seem like a good strategy to me.

Maybe I'm missing something here, but I'm pretty sure this thing will simply not scale. It reminds me of Gnutella, which implemented search through scoped flooding and somehow promised both scalability and coverage. I have the same feeling here. Scalability _and_ security in a peer-to-peer network? Surely you jest.

When something sounds too good to be true it probably is.

I'm not in the position to comment but it does sound like a real problem.

adrian33
Member
**
Offline Offline

Activity: 119


View Profile
June 02, 2011, 12:04:01 PM
 #3

There was a similar criticism here 14 days ago:

http://news.ycombinator.com/item?id=2561403

I'm just trying to be helpful. Here's the follow up comment to that criticism just posted:

http://news.ycombinator.com/item?id=2611570

I'd start thinking about Bitcoin 2.0

Meni Rosenfeld
Donator
Legendary
*
expert
Offline Offline

Activity: 1890



View Profile WWW
June 02, 2011, 12:39:31 PM
 #4

Bitcoin is first and foremost a currency. The fact that it also has built-in most of the features of banks and payment processors is good, but it doesn't mean that a world with Bitcoin as the global currency will not have those. They will probably still exist, store and transfer value denominated in bitcoins, and use their centralization advantage to allow scalability. The minority who insist on using raw Bitcoin will be able to do so. Also, since those services will need to compete with raw Bitcoin, their fees will probably be lower than they are now.

Also, I have some ideas for a semi-p2p trust-based payment-processing network that can be built on top of any currency, which may be a better solution than centralized services. I think it will be a good match for Bitcoin and allow it to scale.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
killerstorm
Legendary
*
Offline Offline

Activity: 994



View Profile
June 02, 2011, 01:01:27 PM
 #5

There are many possible approaches, of course. Purely technical 'multi-chain' approach is one of them. Maybe not the best, but you never know until it is implemented...

Now I think it can be done as an alternative chain, let's call it HubCoin which will have one-side interop with the main BitCoin chain: you can send coins to HubCoin by making a certain transaction which will 'burn' coins in the main BitCoin chain and then HubCoin nodes will pick them. Mike Hearn outlined a possible interaction process in his htp://forum.bitcoin.org/index.php?topic=7219.0 post, I can't say I understood all of it but it seems to be doable.

Then when HubCoin is implemented (as a patched BitCoin client) we can see if the idea is viable: if it is people will start converting their BitCoins to HubCoins.

colored coins proof-of-concept: private currencies, stock/bond p2p exchange

Tips and donations: 16v13Fa9cPmfFzpm9mmbWwAkXY4gyY6uh4
adrian33
Member
**
Offline Offline

Activity: 119


View Profile
June 02, 2011, 01:24:31 PM
 #6

Then when HubCoin is implemented (as a patched BitCoin client) we can see if the idea is viable: if it is people will start converting their BitCoins to HubCoins.

Bitcoin hasn't encountered scalability problems yet, but does have limits to growth. Was Nakamoto more of a cryptography expert than a p2p one? Possibly. Time is on our side, but I'd start thinking ahead so some competing network doesn't come and steal bitcoin's thunder.

What is the best p2p network today? Could someone be brought in to work on bitcoin who had a hand at developing it? I'm sure there'd be people willing to make contributions for that to happen.

killerstorm
Legendary
*
Offline Offline

Activity: 994



View Profile
June 02, 2011, 01:46:24 PM
 #7

Bitcoin hasn't encountered scalability problems yet, but does have limits to growth. Was Nakamoto more of a cryptography expert than a p2p one? Possibly. Time is on our side, but I'd start thinking ahead so some competing network doesn't come and steal bitcoin's thunder.

My thoughts exactly! While making alternative block chains might seem hostile towards the main block chains, it is better for it to be done by people who are close to Bitcoin community. This way different assumptions can be tested... Otherwise without internal competition it might be too late when some external threat comes...

What is the best p2p network today? Could someone be brought in to work on bitcoin who had a hand at developing it? I'm sure there'd be people willing to make contributions for that to happen.

A problem is that there are very different P2P networks: e.g. ones for file sharing are very different from ones for messaging or networking, and, of course, p2p currencies are different from all of them.

I'm not a big P2P expert but I'm quite familiar with file sharing ones, as I've implemented a ed2k client from scratch, for example. (Well, looking into source code of other ed2k clients.)

DHTs (distributed hash tables) are used in a wide range of P2P applications, there is good theory and robust implementations, but they provide no guarantees and thus are probably not useful for currency applications.

Maybe DHTs can be used to optimize some things, for example, instead of strong a full block chain on each node they can be stored in DHT, and so nodes will query the DHT if they need a block.

But relying _solely_ on DHT to store blocks is a bad idea, as a some colluding (or attacked) nodes can simply forget a number of blocks, then information will be lost and you won't know if coins were spent or not.

One good thing about multiple interoperable chains is that once system is set up it will be easier to experiment with different approaches as it would provide a clear upgrade path from one protocol to another.

Quote
Was Nakamoto more of a cryptography expert than a p2p one? Possibly.

Programmers say that premature optimization is the root of all evil Smiley. It doesn't make sense to design a program to be able to handle billions of nodes and transactions until you know that there will be billions of nodes and transactions.

colored coins proof-of-concept: private currencies, stock/bond p2p exchange

Tips and donations: 16v13Fa9cPmfFzpm9mmbWwAkXY4gyY6uh4
killerstorm
Legendary
*
Offline Offline

Activity: 994



View Profile
June 02, 2011, 01:48:45 PM
 #8

I've outlined concrete plan here: http://www.reddit.com/r/Bitcoin/comments/hpvh3/solving_scalability_and_upgrade_path_problems/

colored coins proof-of-concept: private currencies, stock/bond p2p exchange

Tips and donations: 16v13Fa9cPmfFzpm9mmbWwAkXY4gyY6uh4
ben-abuya
Sr. Member
****
Offline Offline

Activity: 323



View Profile WWW
June 02, 2011, 02:15:57 PM
 #9


Very cool idea. Something like this almost certainly has to happen. I've got to read up more about the details.

http://lamassubtc.com/
Lamassu Bitcoin Ventures
adrian33
Member
**
Offline Offline

Activity: 119


View Profile
June 02, 2011, 02:22:04 PM
 #10

I've outlined concrete plan here:

I just tweeted it: http://goo.gl/D2Cx4

bitcool
Legendary
*
Offline Offline

Activity: 1441

Live and enjoy experiments


View Profile
June 02, 2011, 08:33:13 PM
 #11

Very interesting discussion.

As most p2p client can reliably handle the sharing of gigabyte movie files without gobbling up HD space, files exist as fragments within the network, I would think there will be a way to securely and efficiently share the btc database/block chain. I have no idea how though.
2_Thumbs_Up
Sr. Member
****
Offline Offline

Activity: 323


View Profile
June 02, 2011, 08:59:54 PM
 #12

What about the bandwith optimization that is mentioned at the bottom of the wiki page? That seem to reduce the bandwith needed drastically. Any problem with this not mentioned in the wiki?

Edit: I think I can answer my own question. While this does reduce the bandwith for block broadcasts, we still have a problem because the transactions themselves need to be propagated to the entire network first. Correct?
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
June 06, 2011, 12:02:48 PM
 #13

I don't think scalability in the long term will be a problem. In the short/medium term there'll be bumps along the way because not all the scalability techniques discussed in the wiki page are implemented yet.

Perhaps I'm a bit blasé about this because I've worked with a lot of systems that scaled to very high traffic levels, far higher than anything Bitcoin will likely ever see (unless it becomes the one world currency and replaces everything, but let's be realistic). Using a rack of machines in a datacenter for a node really isn't a big deal, as most users will be using simplified payment verification eventually, the requirements for which don't have to scale in the number of transactions.

I didn't fully read the original post, but it sounded like a very complicated way to try and shard the currency. There's no need for that. People who want to run nodes will just upgrade their hardware. The requirements even at VISA scale are far smaller than many websites. That's plenty of scope for decentralization.

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!