Topic: Proposal to solve bitcoin scaling problem (Read 4494 times)

Yes. This is exactly what I meant to accomplish with this proposed addition to the inventory types that can be requested with getdata: only the relevant branches and relevant transactions instead of the full tree and all transactions.

I meant to indirectly impliy this by mentioning "according to the paper", so i did not go into the detail. After all its just a proposal and a lot of other combinations of new protocol messages might be possible to serve the exact same purpose, important is that there is at least *some* way to do it and that it is designed to really be able to remove all traffic that is not absolutely needed.

This forum isn't /dev/null, the maintainers do read it. But for discussion of specific changes rather than higher level discussions the mailing list is better. And yes there should be notification that there is a mailing list. It's still very new.

You need to be precise with your terms though - a merkle tree is not the same thing as a merkle branch.

What I meant is you haven't defined the format of the pruned block. I think it makes more sense to think about this in terms of transactions rather than blocks. The protocols existing design means you can request thousands of headers in one go. You then want to find out about transactions that apply to you, along with the merkle branches associated with those transactions.

I think this is exactly was what the OP wanted from post #1 on. Nobody wanted to leave away the merkle tree, where do you have this idea from? This thread is about simplified verification strictly accordig to the paper. A properly pruned block is also what I am suggesting should be answered to a getdata with the (still hypothetical) inventory type MSG_BLOCK_PRUNED.


It would have been nice to mention in a sticky post at the top of this forum that this forum is (despite its name) not meant to discuss development questions or this forum should be renamed or deleted to avoid people putting their energy into writing posts that basically go to /dev/null.

I am still hoping the bitcoin community is seeing the need for completing the mising half of the protocol because I would like to start implementing my client ASAP, but this would only be possible if the protocol were extended with the missing functionality. I am basically in waiting position, ready to fire up my IDE any moment and start coding, as soon as I see the protocol allows for such clients.

It might make more sense to think about this as a case of a new block structure version.

For pruning it's not enough to just provide the block header and then a list of transactions. You need to provide the merkle branches as well.

If you're serious about implementing this, I suggest posting to the bitcoin-development mailing list about it (maybe with a patch). We can discuss it further there.

If you have something useful to add to the discussion, please do so.

The issue is a real problem, but you lost me at "the only niche I see for bitcoin". You must have all your ducks in a row. Not in the path of a single shit distributing fan. I wish I could envy your hallucination.

I have proposed 2 new messages and one new inventory type in the wiki on the protocol specification talk page:
https://en.bitcoin.it/wiki/Talk:Protocol_specification#Proposing_additional_protocol_messages

(further explanation in the wiki)

Messages:

• setfilter
• getblocksfiltered

inventory types for getdata:

• 0x03 MSG_BLOCK_PRUNED

These messages need to be built into the standard client to allow light clients to be written. Additionally this should be announced in the services field of the version message with the following new flags:

• 0x02 NODE_CAN_FILTER
• 0x04 NODE_CAN_PRUNE

and the light client would advertise that it does not have a copy of the block chain and does not do verification on its own, and that it also won't relay messages to others.

• 0x08 NODE_NO_VERIFY
• 0x10 NODE_NO_BLOCKS
• 0x20 NODE_NO_RELAY

Checkpoints are orthogonal, I don't think anyone argued that they're enough on their own. I'm not sure what part you thought was an argument against it - AFAIK using transactions linked via branches to the root is uncontroversial.

From my reading, the proposal in that thread was more or less the same as mine, and an argument against it were that nobody has to download the entire block chain because they can just rely on the compiled-in "checkpoints".  Of course, 'supernodes', i.e. miners, would always need the entire chain to be able to validate transactions.

But even if my client has a checkpoint, if the size of blocks is 1 MB or more (which it will be eventually), it's still not practical to expect clients to ever have to download full blocks on an ongoing manner; end-user network bandwidth does not support that.  They will need elided (pre-pruned) blocks.

Of course, it's possible that there never will be enough transactions on the bitcoin network to make blocks this big; I strongly suspect that bitcoin will never gain foothold except as a currency for pseudoanonymously buying illegal goods or making untraceable payments for legal goods that the end-user doesn't want associated with them (it is the only monetary niche that I can see that bitcoin has advantages over other forms of payment), and maybe the number of transactions per second in that niche market will never exceed 10 or so ...

It is inevitable.  Absolutely INEVITABLE.  There is no way that all peers are going to be able to suck down all of the blocks all of the time when the block chain gets large enough (I predict this will happen within a year).  Thus, there is going to have to be some kind of alternate block delivery mechanism, and there will be a definite cost to being a provider of the block chain, and those bearing that cost will have to charge for it.  Maybe people will just use bitcoin 'banks' that they keep their wallet in, in which case they're going to go far beyond the minimal loss of pseudoanonymity that you have pointed out.  Or maybe they will keep their wallet private but will pay a proxy to deliver blocks of interest to them, which is basically my proposal already, except using a proprietary and likely closed protocol, and I cannot see the advantage of closed protocols over open ones.

Hi,

This topic was already discussed back in May. There's no need for payment schemes or other complexity.

   http://forum.bitcoin.org/index.php?topic=7972.0

I will add something to the scalability page about this.

I might misunderstand, but it sounds like there's a leak of pseudoanonymity at this stage. The peers would not only be able to associate IPs with specific addresses but also which addresses [likely] belong to the same wallet/user.

Bitcoin users shouldn't trust their peers

Keep in mind that what I call an 'elided' block is exactly the same thing as a 'pruned' block as described in the white paper.  The only difference is that a peer 'prunes' it before delivering it to the interested client, instead of the client pruning it itself.

As the white paper describes, an 'elided' (pre-pruned) block would have the block header as normal, but would simply not have transactions not of interest in it.  The data structure would be very similar but would have a way to indicate that some entire branches of the Merkle tree are pruned.  The block would still have enough of the Merkle tree in it to allow the client to verify the hashing at every level of the Merkle tree, and finally, of the block as a whole.

The protocol request that I would expect end-user clients to make is 'please give me all transactions for this set of bitcoin addresses beginning at this block hash and ending at this block hash'.  This would imply that the end-user's client already knows the entire block chain headers but these are easy and cheap to acquire ahead of time, so that it could verify that the elided block thus delivered does indeed have the correct block hash.  The peer's response would be a set of blocks that it detected had transactions relevant to the bitcoin address (maybe only the most recent one would be necessary in most cases) and return them in the elided form I have described.

In this way, clients would on-demand use network bandwidth, and only a small amount at that, instead of using a continuous and ever-growing amount of network bandwidth to monitor blocks for transactions of interest.

The load put onto a peer to satisfy elided block requests (both looking up the blocks that contain transactions of interest, and composing the elided form of the block for delivery to the client) would not be insignificant, which is why I propose a built-in mechanism for identifying the client such that the peer could, outside of the scope of the bitcoin protocol, charge the client for this service.

I could start actually implementing this if the consensus is that it is a good idea.  Of course I would expect some bitcoin to come my way at 14PtQ2dHfjftuDuRkx5jnUgGrvgYCGaVh5 before I'd invest the effort   Not being an early adopter, i.e. loaded with bitcoins (I have all of 3, and I paid nearly $100 for them), I don't have alot of incentive to go much further beyond talking about this ...

How would the client verify the hash on the elided block, given that the hash of a block is a function of all the whole transactions contained within?

Will

Exactly right.  The protocol does not scale for all clients (maybe for super nodes that can download and process dozes of GiB per day), and a major change is needed.  I wouldn't even propose a destructive change, just an addition:

Add a new 'service', number 2, called 'NODE_ELIDED' (or NODE_PRUNED if others prefer).  This service would enable the client to send queries for elided (pruned) blocks - specify a set of bitcoin address of interest, and a start and end block hash, and get back a new message called 'elided_block' that is like 'block' but has uninteresting transactions, and subtrees of the Merkle tree, elided out.

Also, add a mechanism whereby clients can specify a bitcoin address (or public key or whatever works) and sign the request so that peers can identify who to 'charge' for servicing the request should that be what the server wants to do.  This would be optional but it is absolutely inevitable that the distribution of blocks will eventually cost money as there is so much bandwidth (and CPU) involved in creating and distributing elided blocks.  Supporting that in the protocol would empower end users to easily switch between elided block providers instead of being tied into something proprietary.

The current blocks are 10K because the transaction limit is set to 7 per second (at least according to the wiki) and even then the number of transactions per second is far lower than this on average.  If there were even 100 transactions per second on average, then the block size would then be 22.397 MiB.  Is it really practical to have every client sucking down 23 MiB every 10 minutes?  That's 3.29 GiB per day.  What about periods of really heavy activity - what if, during the holiday season, the number of transactions averages 500 per second?   That's over 16 GiB every day - for every single client, including cell phones.  This just does not scale.  Even 10 transactions per second is 345 MB every day.  I don't think that every client should be expected to download that much.

I don't think the pathetically low mobile data allowances will keep up with the popularity of Bitcoin - if it becomes popular, which it isn't at the moment.   I mean, let's face it, if PayPal is Visa's baby cousin, Bitcoin is an amoeba.

The question is, does Bitcoin scale to 1,000,000 times the transactions it has today?  Clearly not, as a retailer who has been waiting now 20 hours for his first purchase of Bitcoin currency to come through, the current system has to be improved let alone the future version. 

Whether or not the OP's suggestions require a "major change" to the protocol or not, the reality is that it improvements need to be made and that Moore's Law does not apply to bandwidth - especially on mobile devices.

The difference is that your 'elided blocks' ate fundamentally different from the existing bitcoin blocks and would be a major change. However just restructuring the existing tree structures in memory are a natural extension of the existing protocol and are even mentioned in the bitcoin paper. I think by the time this is an issue most devices even smartphones wil be able to afford the 1 block every ten minutes for 6 blocks to verify a transaction from zero knowledge, with the longest chain potentially kept in a rolling buffer of linked blocks.

Even with your 25k blocks... That's less than 50 bytes/s required.

Will

I agree that the proper solution is tree pruning (which I am calling eliding, but we're talking about the same thing).  I'm just proposing that a standardized mechanism be built for allowing a peer with access to the entire blocks to do the pruning on behalf of another peer, instead of expecting each peer to download all of the blocks and do their own pruning, because the latter simply does not scale.

Yours are the first encouraging words I have gotten about my idea though, and thanks for that.  Maybe I will try to take this to a better forum when/if I lose my newbie status.

That document only addresses network requirements for future 'supernodes'.  It already implicitly acknowledges that most future peers will not be able to listen to the entire block stream due to bandwidth restrictions.  So there has to be some way for clients to get the transactions, Merkle tree nodes, and block headers that they need to validate transactions of interest to them.  The document you linked to does not in any way address this problem.

What I am suggesting is a solution to the problem that would be built into the bitcoin protocol and allow end users to get the data that they need to continue to be an independent bitcoin 'node' (and end-user node, not a 'supernode') without leaning on any service except one which provides more targeted data for their needs.

An alternative is to not have something like this and then end users will simply not be able to run bitcoin nodes as we know them - they'll have to lean on a 'bank' to act as a proxy for them, and have to trust the bank to verify transactions because the client itself will not have access to the blocks.

I don't know why anyone would prefer to relegate normal users to second-class bitcoin citizens, rather than building into the protocol mechanisms that allow every user to validate and verify their own transactions as seems to have been intended by the bitcoin designer(s).   What I propose allows the latter.

Of course, this could all not be standardized either and end-users would just have to use a different client other than the standard client in order to use a more intelligent service and not have to download gigabytes of data.  But I think it would be better to standardize it in the client and protocol now for the benefit of everyone.