Block re-orgs need some thought.
If I have chain A-B-C, and get IBLT's for an alternative chain A-B'-C'-D'...
... then the current memory pool won't work to try to reconstruct B' C' D'.
Using B and C to reconstruct B' and C' should work pretty well. Then the remaining memory pool transactions can be used to reconstruct D.
If any of the reconstructions fail, just fall back to fetching all of B' C' D'.
Then again, re-orgs are rare enough that always falling back to fetching full blocks would be OK.
Topic: O(1) block propagation - page 2. (Read 5542 times)
Will there be a transitional period, in which some users and miners do not attempt to reconstruct blocks and rely on the old block propagation method?
Yes. Read Gavin's gist.
Also what happens to new nodes. New nodes won’t have the memory pool data from say 12 months ago, how will they reconstruct those old blocks. Will the download of the historic blockchain work in the same way as it does now?
Older blocks are downloaded like now, newly mined blocks are propagated following this new mechanism. If mostly all transactions in the memory pool end up in a block, the pool starts (almost) empty every 10 minutes for everybody so "getting up to speed" isn't a problem.
Will there be a transitional period, in which some users and miners do not attempt to reconstruct blocks and rely on the old block propagation method? During this period wont it make sense for nodes to propagate the new “mini IBLT block” and the old style block? Miners who find a block will want to maximise their chance of being recognised as first, therefore will they not be incentivised to try to distribute the both the IBLT block and the old full block? Going forward, won’t there always be a minority of nodes that only download new blocks in the traditional way and do not attempt to reconstruct them?
Also what happens to new nodes. New nodes won’t have the memory pool data from say 12 months ago, how will they reconstruct those old blocks. Will the download of the historic blockchain work in the same way as it does now?
Also what happens to new nodes. New nodes won’t have the memory pool data from say 12 months ago, how will they reconstruct those old blocks. Will the download of the historic blockchain work in the same way as it does now?
Don't also miss https://en.bitcoin.it/wiki/User:Gmaxwell/block_network_coding
See also the PGP SKS keyserver, which uses efficient set reconciliation.
I'm a fan of fancy schemes to increase efficiency (see link) but that is a bit over the top.
The impact is much more modest than you're thinking, especially compared to the kind of forwarding that p2pool and bluematt's relay network already do (send blocks without repeating transactions that the far end already knows you have). The transactions still must be sent and validated. It does avoid the 2x bandwidth overhead of sending it again with the block, and the marginal latency that implies— but so do simpler tools e.g. matt's relay for me has a hitrate of "In total, skipped 140004 of 142773 (0.9806055766846673%)" since last restart.
Unlike some other technologies like fraud proofs these doesn't change the decentralization/scale tradeoff or the bandwidth usage (It's still O(n) with the number of transactions, they're just happening earlier). It's all awesome sauce and all and should be a great thing to have, but that I love this stuff makes it hurt all the more to see it exaggerated.
See also the PGP SKS keyserver, which uses efficient set reconciliation.
Quote
This change can launch Bitcoin from being a serious competitor to Western Union (today) to a serious competitor to VISA (later next year).
I'm a fan of fancy schemes to increase efficiency (see link) but that is a bit over the top.
The impact is much more modest than you're thinking, especially compared to the kind of forwarding that p2pool and bluematt's relay network already do (send blocks without repeating transactions that the far end already knows you have). The transactions still must be sent and validated. It does avoid the 2x bandwidth overhead of sending it again with the block, and the marginal latency that implies— but so do simpler tools e.g. matt's relay for me has a hitrate of "In total, skipped 140004 of 142773 (0.9806055766846673%)" since last restart.
Unlike some other technologies like fraud proofs these doesn't change the decentralization/scale tradeoff or the bandwidth usage (It's still O(n) with the number of transactions, they're just happening earlier). It's all awesome sauce and all and should be a great thing to have, but that I love this stuff makes it hurt all the more to see it exaggerated.
I think you somehow understated the implication of Gavin's proposal. Although the bandwidth or CPU usage are still O(n), the block propagation becomes O(1). Since the risk of block orphaning is positively correlated with block propagation time, this proposal will reduce the cost related to block orphaning and encourage miners to include more transactions in a block
Don't also miss https://en.bitcoin.it/wiki/User:Gmaxwell/block_network_coding
See also the PGP SKS keyserver, which uses efficient set reconciliation.
I'm a fan of fancy schemes to increase efficiency (see link) but that is a bit over the top.
The impact is much more modest than you're thinking, especially compared to the kind of forwarding that p2pool and bluematt's relay network already do (send blocks without repeating transactions that the far end already knows you have). The transactions still must be sent and validated. It does avoid the 2x bandwidth overhead of sending it again with the block, and the marginal latency that implies— but so do simpler tools e.g. matt's relay for me has a hitrate of "In total, skipped 140004 of 142773 (0.9806055766846673%)" since last restart.
Unlike some other technologies like fraud proofs these doesn't change the decentralization/scale tradeoff or the bandwidth usage (It's still O(n) with the number of transactions, they're just happening earlier). It's all awesome sauce and all and should be a great thing to have, but that I love this stuff makes it hurt all the more to see it exaggerated.
See also the PGP SKS keyserver, which uses efficient set reconciliation.
Quote
This change can launch Bitcoin from being a serious competitor to Western Union (today) to a serious competitor to VISA (later next year).
I'm a fan of fancy schemes to increase efficiency (see link) but that is a bit over the top.
The impact is much more modest than you're thinking, especially compared to the kind of forwarding that p2pool and bluematt's relay network already do (send blocks without repeating transactions that the far end already knows you have). The transactions still must be sent and validated. It does avoid the 2x bandwidth overhead of sending it again with the block, and the marginal latency that implies— but so do simpler tools e.g. matt's relay for me has a hitrate of "In total, skipped 140004 of 142773 (0.9806055766846673%)" since last restart.
Unlike some other technologies like fraud proofs these doesn't change the decentralization/scale tradeoff or the bandwidth usage (It's still O(n) with the number of transactions, they're just happening earlier). It's all awesome sauce and all and should be a great thing to have, but that I love this stuff makes it hurt all the more to see it exaggerated.
When a miner finds a block, they propagate both the actual block and this new “mini block” across the network.
No. That was my initial thought too when I saw Gavin's tweet, but the reality is far more amazing. The new IBLT block concept is absolute and total genius and deserves a lot of constructive input from this forum. This change can launch Bitcoin from being a serious competitor to Western Union (today) to a serious competitor to VISA (later next year).
The best way to think about this idea is to consider IBLT blocks as containing the instructions for how to construct the next block yourself, as well as differences, a bunch of needed transactions which you don't already know about.
If you look at the unconfirmed transactions on blockchain.info, you see their mempool displayed out. Your copy of Bitcoin Core which is running at home will have a very similar set of unconfirmed transactions, maybe less as BC.i has many more peer-to-peer connections.
By way of example, assuming the IBLT upgrade is in and running and a miner produces an IBLT block, you receive it and so does BC.i (and other nodes). The IBLT contains all the transactions to make up a block - but the transactions can't be read because (basically) they are overlaying each other. You, BC.i, others, take the IBLT and subtract out all the transactions you have that are likely to be in the new block and are left with the differences. Different differences for each! Then the subtracted ones and those extra transactions are used to build the same new block, and then regular validation begins.
IBLT blocks are equal size, but the block which goes into the blockchain could be smaller, or much larger, depending on the number of tx as usual.
Thanks for clearing this up for me, sorry about my misconceptions about the idea. I still need some time to think about this, however I think this sounds brilliant and could solve what I thought was one of Bitcoin’s biggest problems.
Please let me know if I have got it right now:
When a miner finds a block, they propagate both the actual block and this new “mini block” across the network. Then if another miner receives the mini block but can’t reconstruct the full block in time, they just wait until they receive the full block. This way miners are incentivised to send out both type of blocks.
What happens if miners start to get too far ahead, e.g. they reconstruct a block and find many new valid blocks before even one full block has propagated, could this be an issue? There could be two types of nodes, one type that reconstructs blocks and has a more up to date version of the network and a slower traditional node that only recognises full blocks.
Please let me know if I have got it right now:
When a miner finds a block, they propagate both the actual block and this new “mini block” across the network. Then if another miner receives the mini block but can’t reconstruct the full block in time, they just wait until they receive the full block. This way miners are incentivised to send out both type of blocks.
What happens if miners start to get too far ahead, e.g. they reconstruct a block and find many new valid blocks before even one full block has propagated, could this be an issue? There could be two types of nodes, one type that reconstructs blocks and has a more up to date version of the network and a slower traditional node that only recognises full blocks.
Dear all
I have read Gavin’s proposal on O(1) block propagation, available here:
https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2
If there is another thread on this I apologise, I couldn’t find it. I think the proposal is interesting and could be brilliant. However there are various basic aspects to it which I do not understand, if possible could some of you try to help explain these:
1. Is this a proposal for initial block propagation only, with the old style blocks still being propagated with a delay or will the blockchain only contain the new smaller style of blocks?
2. What is the incentive to propagate the old block format, with all the transactions, as this will presumably no longer be required for mining? Couldn’t this make the problem of a lack of full nodes worse?
3. If the blockchain now only contains only the new type of block, how does the client get the history of all bitcoin transactions? Will clients need to connect to the memory pool of other nodes and how will all historic transactions be reconstructed?
4. How will miners be incentivised once the block reward drops, as if there is no longer as much scarcity in the blockchain, the fees may be too low to incentivise miners?
Many thanks
I have read Gavin’s proposal on O(1) block propagation, available here:
https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2
If there is another thread on this I apologise, I couldn’t find it. I think the proposal is interesting and could be brilliant. However there are various basic aspects to it which I do not understand, if possible could some of you try to help explain these:
1. Is this a proposal for initial block propagation only, with the old style blocks still being propagated with a delay or will the blockchain only contain the new smaller style of blocks?
2. What is the incentive to propagate the old block format, with all the transactions, as this will presumably no longer be required for mining? Couldn’t this make the problem of a lack of full nodes worse?
3. If the blockchain now only contains only the new type of block, how does the client get the history of all bitcoin transactions? Will clients need to connect to the memory pool of other nodes and how will all historic transactions be reconstructed?
4. How will miners be incentivised once the block reward drops, as if there is no longer as much scarcity in the blockchain, the fees may be too low to incentivise miners?
Many thanks
This proposal does not change anything about the blockchain. To answer question 1, sort of. Since finding a block really just means finding a low enough hash to make the block valid, all the data except for the hash can be known to the entire network before the block is found.
Currently, when a miner finds a block, they have to send the entire block (all transactions in the block + header), to everyone else, which is harder the more transactions there are in the block.
The proposal is (oversimplified) to ensure each miner has all the transactions that will be included in the block beforehand. Then when a miner finds a block, they will only have to send the header and coinbase transaction (telling everyone who gets the block reward), and other miners will be able to reconstruct the block from this.
Since they will be able to reconstruct the block, the only difference is that the entire block isn't sent over the network.
Initial block propagation only. At the point immediately after a successful nonce has been found.
The block itself still contains all transactions in full form. It is simply transferred in a more efficient manner.
There is no 'new smaller style of block'.
Nodes will still relay full blocks. There is no (direct) financial incentive for anyone to run a full node and there never has been.
The block itself still contains all transactions in full form. It is simply transferred in a more efficient manner.
There is no 'new smaller style of block'.
Nodes will still relay full blocks. There is no (direct) financial incentive for anyone to run a full node and there never has been.
Dear all
I have read Gavin’s proposal on O(1) block propagation, available here:
https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2
If there is another thread on this I apologise, I couldn’t find it. I think the proposal is interesting and could be brilliant. However there are various basic aspects to it which I do not understand, if possible could some of you try to help explain these:
1. Is this a proposal for initial block propagation only, with the old style blocks still being propagated with a delay or will the blockchain only contain the new smaller style of blocks?
2. What is the incentive to propagate the old block format, with all the transactions, as this will presumably no longer be required for mining? Couldn’t this make the problem of a lack of full nodes worse?
3. If the blockchain now only contains only the new type of block, how does the client get the history of all bitcoin transactions? Will clients need to connect to the memory pool of other nodes and how will all historic transactions be reconstructed?
4. How will miners be incentivised once the block reward drops, as if there is no longer as much scarcity in the blockchain, the fees may be too low to incentivise miners?
Many thanks
I have read Gavin’s proposal on O(1) block propagation, available here:
https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2
If there is another thread on this I apologise, I couldn’t find it. I think the proposal is interesting and could be brilliant. However there are various basic aspects to it which I do not understand, if possible could some of you try to help explain these:
1. Is this a proposal for initial block propagation only, with the old style blocks still being propagated with a delay or will the blockchain only contain the new smaller style of blocks?
2. What is the incentive to propagate the old block format, with all the transactions, as this will presumably no longer be required for mining? Couldn’t this make the problem of a lack of full nodes worse?
3. If the blockchain now only contains only the new type of block, how does the client get the history of all bitcoin transactions? Will clients need to connect to the memory pool of other nodes and how will all historic transactions be reconstructed?
4. How will miners be incentivised once the block reward drops, as if there is no longer as much scarcity in the blockchain, the fees may be too low to incentivise miners?
Many thanks
Jump to: