solution for blockchain scalability problem

[killerstorm]

(I've previously posted it in 'Development & Technical Discussion', but Bitcoin people said that blockchain bloat is not a problem and they don't care. So I'm posting it here, perhaps alt-chain developers will find it interesting...)

tl;dr for pros: UTXO set is stored in "cloud database", special measures are taken so that "cloud database" can be trusted. No need to store UTXO set locally, no need to download whole blockchain to build local UTXO set.

To prove that coin is valid we need two things: 1) chain of signatures; 2) proof that it wasn't double-spent anywhere in blockchain.

With blockchain design used in Bitcoin one can confirm lack of double-spends only once he have downloaded whole blockchain (or a potentially large part of it). This doesn't scale so well and might be a problem in future when transaction volume grows. It creates barrier for entry for miners etc.

It doesn't need to be so expensive.

To confirm that TXO was not spent we need a list of all spent TXOs. However, we can organize this spend list into multiple independent bins. Basically, it's same strategy as used with hash tables.

E.g. suppose transaction spends outpoint 123456:1. We need to confirm that this outpoint isn't spent yet. If we have 10000 bins, we'll look in bin number 1234. So effectively we need to scan 1/10000 of transaction history instead of a whole transaction history.

This approach will allow 'thin miners' to exist: thin miners need to download only a tiny fraction of blockchain to be able to verify transactions.

Thin miners have to trust existing information contained in blockchain to some extent: they will be able to verify arbitrary parts of blockchain, but it's not possible to verify all blockchain without actually downloading it. But I believe that it is reasonable assumption that information deep in blockchain can be trusted: it would be incredibly expensive to insert fake info into it given that it CAN and WILL be detected sooner or later.

If anybody cares I can elaborate on protocols for thin miners and whatnot.

Why is this interesting/important?

I believe blockchain size is why we can't afford microtransactions, and if blockchain size problem gets solved we'll be able to afford them... and other things. Arbitrary data in blockchain, maybe.

[Sunny King]

E.g. suppose transaction spends outpoint 123456:1. We need to confirm that this outpoint isn't spent yet. If we have 10000 bins, we'll look in bin number 1234. So effectively we need to scan 1/10000 of transaction history instead of a whole transaction history.

Not sure I get your point, double spending of a specific txout is checked by an index lookup (via transaction index) not a block chain scan as you seem to think.

The pain is initial block chain download, but I think it's doable to retire old section of block chain via checkpoints (maybe need a hard-fork to relocate some old unspent transactions to the top of block chain).

Besides that somewhere bitcoin devs implied that a future option to only download unspent transactions although I could be wrong.

I've been thinking about this for a while because database use of a block chain most definitely need to deal with the bloat issues.

[killerstorm]

The pain is initial block chain download,

Yes, I was talking about initial blockchain download. It needs to be scanned by miner before he can verify any transaction.

but I think it's doable to retire old section of block chain via checkpoints (maybe need a hard-fork to relocate some old unspent transactions to the top of block chain).

It is an ugly solution and still in the end miner needs to download and scan a lot of data before he can mine.

Also it doesn't solve the problem that miners have to download all new blocks, lagging behind is not an option for miner.

But a 'thin miner' can simply follow block headers.

[Sunny King]

For miners thin client might be tough I think, but wasn't thin client long intended to emerge for end users?

[killerstorm]

For miners thin client might be tough I think, but wasn't thin client long intended to emerge for end users?

Thin miner is very different from thin client. Not possible without a different blockchain format, for example.

Thin clients already exist. MultiBit, for example. https://en.bitcoin.it/wiki/Thin_Client_Security

I don't think thin miners are discussed anywhere because they are (likely) first mentioned in my message above.

[Sunny King]

However I don't understand your proposal for thin miner there. Double spending is already checked via index lookup, however you need the index in the first place, then in order to trust the index you need the block chain as proof.

Could you describe your proposal for thin miner a bit more?

[gmaxwell]

E.g. suppose transaction spends outpoint 123456:1. We need to confirm that this outpoint isn't spent yet. If we have 10000 bins, we'll look in bin number 1234. So effectively we need to scan 1/10000 of transaction history instead of a whole transaction history.

You're confused. Unspent outputs are indexed. So a node only has to check ~log(n) places for N unspent transactions.

For example, at the moment there are 3,696,834 unspent outputs in at the tip of the Bitcoin chain right now (this is a tiny fraction of the number of outputs that ever was).  Validating a txin should thus require checking no more than 22 things.  The whole of the unspent outputs, much less the whole of the history, is never checked.

[killerstorm]

You're confused. Unspent outputs are indexed. So a node only has to check ~log(n) places for N unspent transactions.

I already replied to Sunny King: new miner needs to download and verify whole blockchain before you verify first transaction. Of course, you don't need to download it again for a second one

Right now miner needs to download ~5 GB. It isn't a problem.

But at some point he will need 5 TB, 5 PB and so on...

[killerstorm]

However I don't understand your proposal for thin miner there. Double spending is already checked via index lookup, however you need the index in the first place, then in order to trust the index you need the block chain as proof.

Could you describe your proposal for thin miner a bit more?

Sure... I'm kinda too bored to describe it completely, though, so a quick summary:

As you've noted, currently node builds UTXO database and looks it up when it checks transaction validity.

Potentially we could use "cloud database" (DHT, for example) instead of a local UTXO set, but there is a problem: we cannot trust this "cloud database".

So we are going to put some extra information into blocks, and that information will help us to verify data we get from "cloud database".

This information is simply a list of outpoints spend in current block arranged in a tree fashion so it can be easily searched.

When client receives new transaction it checks its validity: each outpoint mentioned in transaction inputs is looked up in DHT to check whether it even exists. If it does exist, we need to check that it isn't spend already. To do that, we identify a bin associated with this outpoint, find current top of that bin by doing search in last N blocks (which requires some information in block body, but not full blocks), then we fetch enough history for that bin from DHT to confirm non-existence of double-spend.

It is true that this process might be significantly more computationally expensive than lookup in a local UTXO database. However, storage requirements are drastically lower.

So effectively it is a trade-off: higher per-transaction computation and communication costs vs. high storage and initial blockchain processing costs.

However, it's not so simple: this approach potentially allows distributed processing where miner will include transactions it can verify inexpensively. E.g. suppose miners will pick a set of bins they specialize on, and we'll have small blocks touching only handful of bins instead of huge-ass blocks touching all bins.

[markm]

Good luck having small blocks at all, no matter how many bins they touch.

10,000 bins with blocks that touch only 1 bin is up to a 10,000 block wait for one confirmation, average of 5000 block wait.

-MarkM-

[killerstorm]

Good luck having small blocks at all, no matter how many bins they touch.

10,000 bins with blocks that touch only 1 bin is up to a 10,000 block wait for one confirmation, average of 5000 block wait.

I never said it would work as is without other modifications

Suppose block are created each 0.1 seconds, thus you get 6000 blocks in 10 minutes. (I know why it won't work, but let's consider it for the sake of argument.) In this case users need to wait about 10 minutes to get one confirmation, just as before.

However, difficulty is now 6000 times smaller, so we get different security properties.

Cost of double-spend via history rewrite is about as big as with a classic scheme: block would get same amount of proof-of-work on top of it after some time, so we can trust 'timestamping'.

However, cost of inclusion of invalid transaction into a block is 6000 times smaller, so simplified payment verification shouldn't be used.

Luckily wallet software can verify transactions themselves in same way miners do that (lookups in DHT and scan of spend information), so it can rely on proof-of-work just for timestamping.

If invalid block makes all blocks on top of it invalid too it would create a problem for miners: one can disrupt mining at 1/6000 of mining cost.

But if we do not rely on simplified block verification we can keep invalid blocks in blockchain: next block targeting same bin would mark that block as invalid and will re-do it. Thus invalid blocks are not a problem.

This obviously needs more work, for example, we might want to use block DAG instead of block chain. But I'm fairly certain that distributed transaction processing is possible and we can get away from "everybody must check every transaction" model.