New paper: Accelerating Bitcoin's Trasaction Processing

[molecular]

Hi Aviv,

Has your paper already been peer-reviewed?

We are peer-reviewing it now ;-). No better review mechanisms than a btctalk thread.

Firstly: it's awesome to see such research.

Now, is litecoin too conservative to try to incorporate this?

I think yes, so let's make TreeCoin?

One of the reasons none of the altcoins have ever appealed to me is their lame ass names. No offense, but I can't see the whole world using something called Treecoins.

Would it be possible to implement this directly from the Bitcoin blockchain, creating a split? Where the current holders of bitcoins now are also the holders of Bitcoin 2.0? And then people will be vested in both with a market between the two, eventually finding out which one "wins."

This is how I would go about it when making an altcoin, too. But for most altcoiners the appeal is that they can be early adopters with their new coin. You don't have that with the bitcoin 2.0 approach.

[1714791631]

1714791631

[1714791631]

1714791631

[1714791631]

1714791631

[1714791631]

1714791631

[1714791631]

1714791631

[1714791631]

1714791631

[Voodah]

Hi Aviv,

Has your paper already been peer-reviewed?

We are peer-reviewing it now ;-). No better review mechanisms than a btctalk thread.

Firstly: it's awesome to see such research.

Now, is litecoin too conservative to try to incorporate this?

I think yes, so let's make TreeCoin?

One of the reasons none of the altcoins have ever appealed to me is their lame ass names. No offense, but I can't see the whole world using something called Treecoins.

Would it be possible to implement this directly from the Bitcoin blockchain, creating a split? Where the current holders of bitcoins now are also the holders of Bitcoin 2.0? And then people will be vested in both with a market between the two, eventually finding out which one "wins."

This is how I would go about it when making an altcoin, too. But for most altcoiners the appeal is that they can be early adopters with their new coin. You don't have that with the bitcoin 2.0 approach.

Yeah, but this is for the good of Bitcoin, not for the altcoiners.

Still, I'm not so sure how good it would be to fragment the Bitcoin economy.

If the peer reviewing goes well, it seems to me that this is more of a candidate for the dev team to work on, than an alt-coin.

[hamiltino]

You guys have made the biggest contribution to the biggest problem with cryptocurrencies, transaction times.


Now we just need to implement it + zerocoin support. Ahh how i love open source.

If the bitcoin devs sit on their ass and don't look into it, you guys should make your own altcoin with the innovation, Prove it works to the world.

[amincd]

This is incredibly serendipitous. I began writing a paper in Google Docs this week, titled:

"Disposable, non-orphaning, merge-mined blockchains for rapid transaction confirmation"

The idea is to have a parallel merge-mined mini-block 'grove' (since there could be more than one tree) to determine which transaction is chosen in the event of a double spend.

I'll describe it in case it can contribute to the discussion.

Disposable, non-orphaning, merge-mined blockchains for rapid transaction confirmation

The proposal is to have parallel chains of mini-blocks (3 seconds) that begin at every new 'real block' (10 minutes), and rather than orphaning forks of these mini-block chains with lower difficulty, nodes save them along with the greatest difficulty chain.

This parallel 'tree' or 'grove' of mini-block chains would be merge-mined with the main blockchain, to conserve hashing power, and would give a higher resolution picture of when a transaction was first propagated into the network.

Upon the creation of a new 10-minute block, nodes would check if any of the transactions contained in it (in-block transactions) have a double spend in the parallel mini-block chains that has at least 10 more mini-blocks backing it than backing the in-block transaction. The mini-blocks counted toward this comparison can be in any of the chains, including in lower difficulty forks. If the block does contain such a transaction, then it is invalid and not accepted by other nodes.

Under this rule, a transaction could be confirmed in an average of 30 seconds. Once a particular transaction is in a mini-block with 10 mini-blocks (in any chain) built on top of it, with no double spends detected, a person can be confident that the transaction cannot be replaced by a double spent transaction.

There are two further rules required to make this work:

1) Require that a new real block contain all transactions with at least 10 mini-blocks backing them. Without such a rule, mining nodes can simply refuse to include any transactions into the main block they're hashing on, or refuse to include those transactions which they've detected a double spend attempt on, to avoid the risk of a block they generate being invalid according to the mini-blockchain rule and orphaned.

To avoid an attacker being able to take advantage of this rule to bloat the blockchain with zero or low-fee transactions, the rule can be qualified with the '>=10 mini-block backed transactions that blocks are required to include' being only those with a fee to kb ratio that is 10 percent greater than the median fee to kb ratio of all fee-containing transactions over the last 100 real blocks.

The list of transactions with fees that would be used to determine the median transaction fee to kb ratio would be weighed by the 'bitcoin days destroyed' of each transaction, to prevent manipulation of the median through generation of a large number of small value, low input age, transactions.

2) Nodes refuse to build on mini-block chains that contain a transaction that conflicts (contains a double spend) with any transaction that has at least 3 mini-blocks backing it. This would ensure that any double spend transaction that is generated more than an average of 9 seconds after the initial transaction will have very few mini-blocks built on top of it, virtually guaranteeing the first transaction will be included in the next real block if enough time transpires until the new block is generated for 7 more mini-blocks to be generated.

Edit, a couple more thoughts:

• Using these rules, there could be cases when there is a network split due to a block being accepted by some nodes, and rejected by others, due to it containing a double spend and there existing conflicting views of how many mini-blocks back the original transaction (one set of nodes could have a local view showing the first transaction out backs the second by 9 mini-blocks, and another could have a local view showing the first transaction out-backing the second by the required 10 mini-blocks to be secure from a double spend). In this case, an additional rule, of nodes accepting a new block, even if it contains an 'illegal' double spend, if the number of mini-blocks backing the new block exceeds the number of mini-blocks generated on top of the old block after the fork, by a particular number (e.g. 5 blocks), can be used to resolve network split
• An additional rule could be that new blocks must publish in their headers the 'median transaction fee to kb ratio' for the last 100 blocks. This would allow SPV clients to operate with lower trust requirements, since they would know just from the block headers what transaction fee they need to include with their transaction to guarantee it will be secure from a double spend attempt at/after 10 mini-blocks

The strengths of this proposal are:

Like the GHOST protocol additions proposed in the linked paper, this provides faster confirmations without a rise in orphans caused by propagation latency reducing the effective network hashrate, as results from simply shortening block times.

There would be no extra sets of block headers in the blockchain as would be required with more frequent blocks.

It's a soft-fork that is backward compatible with non-mining nodes that don't upgrade.

[karma9]

i will be carefully monitoring this technology; if it proves to be successful on paper and test runs, and bitcoin developers fail to implement this, i'll be investing in alt-coin which uses it.

[avivz78]

I didn't read the paper yet, but I have some problems even understanding the basic concept.

If the idea is to also accept transaction in orphaned blocks (or forks), then how can one even be sure all nodes are aware of the transactions contained in the orphans? With the current longest-chain scheme this is easy: I can just walk back through all the blocks and get a list of all transaction which is exactly the list of all valid transactions. With the proposed change I don't see how I can get a provably complete list of all valid transactions.

Please someone enlighten me.

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).

[hashman]

Thank you!

One thing that makes it a little hard for me to follow your notation is that I am unclear on the definitions of beta and lamda.  Beta is the rate of block additions to the "main chain" and lamda is the rate of block additions which have some potential to wind up in the main chain if they are accepted.  At least, that is my reading of it. 

However, there is no point in which a block becomes 100% canonized in the main chain (well, other than checkpointing).  It is therefore hard to make a rigorous definition of beta.  After all, the block chain is a probabilistic not a deterministic solution to the distributed consensus problem.  It seems that the difference between lamda and beta is also called the orphan rate, a term you choose to not use, possibly because you are afraid people will accuse you  of suggesting we put orphans to work in the mines  

Another comment is that some of the maths you develop could also be useful in analysis of shares in a mining pool.         

[avivz78]

Thank you!

One thing that makes it a little hard for me to follow your notation is that I am unclear on the definitions of beta and lamda.  Beta is the rate of block additions to the "main chain" and lamda is the rate of block additions which have some potential to wind up in the main chain if they are accepted.  At least, that is my reading of it.  

However, there is no point in which a block becomes 100% canonized in the main chain (well, other than checkpointing).  It is therefore hard to make a rigorous definition of beta.  After all, the block chain is a probabilistic not a deterministic solution to the distributed consensus problem.  It seems that the difference between lamda and beta is also called the orphan rate, a term you choose to not use, possibly because you are afraid people will accuse you  of suggesting we put orphans to work in the mines  

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).

Another comment is that some of the maths you develop could also be useful in analysis of shares in a mining pool.        

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

[jaked]

A typo in the paper caught my eye:
"As of November 2014, it is valued.."

You're obviously referring to 2013.

[Mike Hearn]

Copying my repsonse from an email thread:


I really like this paper. It's nice to see a strong theoretical grounding for what some of the rather arbitrary choices in Bitcoin could be.

One thing I note is that there are lots of ways to optimise block wire representations. Sending blocks as lists of hashes, for example, would use 32 byte hashes in our current code just because it's lazily reusing the Bloom filtering path. But 32 bytes is massive overkill for this. You only need to distinguish between transactions in the mempool. You could easily drop to 16, 8 or even 4 byte hashes (hash prefixes) and still be able to disambiguate what the peers block message contains very reliably. Indeed they could be varint encoded so the hash is only as long as it needs to be given current traffic loads. Malicious actors might try to create collisions to force block propagation times up, but if peers negotiate random byte subsets upon connect for relaying of block contents then such an attack becomes impossible.

Given the way the maths works out, fairly simple optimisations like that can keep block messages small even with very large amounts of traffic and a 10 minute propagation time. So the findings in this paper seem pretty reassuring to me. There is so much low hanging fruit for optimising block propagation.

Re: SPV wallets. I'm not sure what kind of probabilistic verification you have in mind. The cost of processing headers is primarily in downloading and storing them. Checking they are correct and the PoWs are correct isn't that expensive. So it's not really obvious to me how to do probabilistic verification. In fact it can be that again smarter encodings just make this problem go away. The prev block hash does not need to be written to the wire as 32 bytes. It can be simply however many bytes are required to disambiguate from the set of possible chain heads. When seeking forward using getheaders there is only ever one possible previous block header, so the largest component of the 80 bytes can be eliminated entirely. Likewise, given the rarity of block header version transitions, the redundant repetition of the version bytes can also be excluded in getheader responses. Those two optimisations together can nearly halve the header size for the most common wire cases, allowing a doubling of the block rate with no disk/bandwidth impact on SPV clients.

[trout]

There's something in the paper about SPV clients: "These nodes will face a
larger number of block headers to download."
Can you give an estimate of how much larger this would be?

[mission]

I love you!!!

[phelix]

Great idea. We need an altcoin implementing it. Bounty: I pledge 10BTM

edit: "Heaviest branch selection"

[michaelmclees]

For merchants wishing for nearly instant security, why not simply have all the large pools sign each valid transaction and send the batch of signatures out to the merchant?

The pools would be verifying that they will include the transaction in their next block, should they find it.  Suppose the merchant is basically OK with 0 confirm purchases for small things, but would like a little more security if he could get it.  He signs up with what we'll call "The Service" and The Service has contracted with the 10 largest pool operators.  For all incoming BTC to the merchants addresses, The Service sends a confirmation request to all the pools.

Will you be accepting this transaction in your next block?

They all say "YES" and depending on the threshold the merchant is willing to live with, perhaps he wants 8 of 10 to immediately say YES, he gets his verification in the form of signatures or no replies.  Double spends are prevented because all the pools already said YES to one or the other, so on merchant is getting perhaps 8 Yes, 1 No, and 1 No Reply.  The other merchant is getting 8 No, 1 Yes, and 1 No Reply.

All this happens before the next block is found.

If a pool says Yes but fails to include the transaction, or says No, but includes it anyway, the pool is either on the hook for the money OR they lose credibility and marketshare.

[amincd]

^ This is trust-based, when what's needed is a protocol rule that makes this determination automated.

[michaelmclees]

Fair enough.  People fear protocol changes though, so this may be a political issue.

[TierNolan]

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).

What is nice about this is that it is backwards compatible.

For blocks that are off the main chain, you only need to send the headers.  This could be made part of the headers first system.  Each node would download the entire header tree first and then download the full blocks.

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!

The difficulty update would have to be the main chain length, so the block rate would remain the same.

In fact, we estimate that 1 second blocks can be easily combined with rates of over 200 TPS.

A faster block rate mainly helps with confirmation time rather than transactions per second.  Your node still needs to process the entire block to make sure all the transactions are valid.

A much higher block rate (with lots of blocks thrown away) would mean that nodes would end up verifying multiple blocks.

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.  

It depends on the hash value too.  Your transaction needs to have hashing power built on it that is much more valuable than the transaction.  The block rate determines protection against random reversal.

[AsymmetricInformation]

The basic observation behind the protocol modification that we suggest, is that blocks that are off the main chain can still contribute to a chain’s irreversibility. Consider for example a block B, and two blocks that were created on top of it C1 and C2, i.e., parent(C1) =parent(C2)= B. The Bitcoin protocol, at its current form, will eventually adopt only one of the sub-chains rooted at C 1 and C 2, and will discard the other. Note however, that both blocks were created by nodes that have accepted block B and its entire history as correct. The heaviest sub-tree protocol we suggest makes use of this fact, and adds additional weight to block B, helping to ensure that it will be part of the main chain.

Cool!

[superresistant]

Yes please do something.

[gglon]

How about splitting the reward equally among all blocks at level h? The exact tx paying the miners would be just included x levels later.