* [Bitcoin-development] Distributing low POW headers
@ 2013-07-23 11:27 Tier Nolan
2013-07-24 9:42 ` Peter Todd
0 siblings, 1 reply; 5+ messages in thread
From: Tier Nolan @ 2013-07-23 11:27 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 2757 bytes --]
I was thinking about a change to the rules for distinguishing between forks
and maybe a BIP..
*Summary*
- Low POW headers should be broadcast by the network
If a header has more than 1/64 of the POW of a block, it should be
broadcast. This provides information on which fork is getting most of the
hashing power.
- Miners should use the header information to decide on longest chain
The fork selection rule for miners should be biased towards staying on the
fork that has the most hashing power.
This means that they might keep hashing on a fork that is 1-2 blocks
shorter.
If most miners follow the rule, then it is the best strategy for other
miners to also follow this rule.
- Advantages
This lowers the probability of natural and malicious reversals.
*Distributing low POW headers*
First block header messages that have more than 1/64 of the standard POW
requirements would be forwarded.
This means the client needs to maintain a short term view of the entire
header tree.
if (header extends header tree) {
if (header meets full POW) {
add to header tree;
forward to peers;
check if any blocks in storage now extend the header tree
} else {
if (header meets POW / 64) {
forward to peers;
}
} else {
if (header meets POW) {
add to orphan header storage
}
}
The storage could be limited and headers could be discarded after a while.
This has the extra advantage that it informs clients of forks that are
receiving hashing power.
This could be linked to a protocol version to prevent disconnects due to
invalid header messages.
*Determining the longest chain*
Each link would get extra credit for headers received.
Assume there are 2 forks starting at block A as the fork point.
A(63) <- B(72) <- C(37) <- D(58)
and
A(63) <- B'(6) <- C'(9) <- D'(4) <- E(7) <- F(6)
The numbers in brackets are the number of low POW headers received that
have those blocks as parent.
The new rule is that the POW for a block is equal to
POW * (1 + (headers / 16))
Only headers within <some threshold> of the end of the (shorter) chain
count. However, in most cases, that doesn't matter since the fork point
will act as the start point. As long as miners keep headers for 30-40
blocks, they will likely have all headers back to any reasonable fork point.
This means that the top fork is considered longer, since it has much more
headers, even though it has 2 less blocks.
If 75% of the miners follow this rule, then the top fork will eventually
catch up and win, so it is in the interests of the other 25% to follow the
rule too.
Even if there isn't complete agreement on headers received, the fork that
is getting the most hashing will naturally gain most of the headers, so
ties will be broken quickly.
[-- Attachment #2: Type: text/html, Size: 3572 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [Bitcoin-development] Distributing low POW headers 2013-07-23 11:27 [Bitcoin-development] Distributing low POW headers Tier Nolan @ 2013-07-24 9:42 ` Peter Todd 2013-07-24 11:55 ` Tier Nolan 0 siblings, 1 reply; 5+ messages in thread From: Peter Todd @ 2013-07-24 9:42 UTC (permalink / raw) To: Tier Nolan; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 3437 bytes --] On Tue, Jul 23, 2013 at 12:27:03PM +0100, Tier Nolan wrote: > I was thinking about a change to the rules for distinguishing between forks > and maybe a BIP.. Please provide equations and data justifying the 'magic constants' in this proposal. Currently we do not relay blocks to peers if they conflict with blocks in the best known chain. What changes exactly are you proposing to that behavior? > *Summary* > > - Low POW headers should be broadcast by the network > > If a header has more than 1/64 of the POW of a block, it should be > broadcast. This provides information on which fork is getting most of the > hashing power. > > - Miners should use the header information to decide on longest chain > > The fork selection rule for miners should be biased towards staying on the > fork that has the most hashing power. > > This means that they might keep hashing on a fork that is 1-2 blocks > shorter. > > If most miners follow the rule, then it is the best strategy for other > miners to also follow this rule. > > - Advantages > > This lowers the probability of natural and malicious reversals. > > *Distributing low POW headers* > > First block header messages that have more than 1/64 of the standard POW > requirements would be forwarded. > > This means the client needs to maintain a short term view of the entire > header tree. > > if (header extends header tree) { > if (header meets full POW) { > add to header tree; > forward to peers; > check if any blocks in storage now extend the header tree > } else { > if (header meets POW / 64) { > forward to peers; > } > } else { > if (header meets POW) { > add to orphan header storage > } > } > > The storage could be limited and headers could be discarded after a while. > > This has the extra advantage that it informs clients of forks that are > receiving hashing power. > > This could be linked to a protocol version to prevent disconnects due to > invalid header messages. > > *Determining the longest chain* > > Each link would get extra credit for headers received. > > Assume there are 2 forks starting at block A as the fork point. > > A(63) <- B(72) <- C(37) <- D(58) > > and > > A(63) <- B'(6) <- C'(9) <- D'(4) <- E(7) <- F(6) > > The numbers in brackets are the number of low POW headers received that > have those blocks as parent. > > The new rule is that the POW for a block is equal to > > POW * (1 + (headers / 16)) > > Only headers within <some threshold> of the end of the (shorter) chain > count. However, in most cases, that doesn't matter since the fork point > will act as the start point. As long as miners keep headers for 30-40 > blocks, they will likely have all headers back to any reasonable fork point. > > This means that the top fork is considered longer, since it has much more > headers, even though it has 2 less blocks. > > If 75% of the miners follow this rule, then the top fork will eventually > catch up and win, so it is in the interests of the other 25% to follow the > rule too. > > Even if there isn't complete agreement on headers received, the fork that > is getting the most hashing will naturally gain most of the headers, so > ties will be broken quickly. -- 'peter'[:-1]@petertodd.org 000000000000001e1c3393788031c4e427b67cfd1b5e90a3b0de4fff094b2894 [-- Attachment #2: Digital signature --] [-- Type: application/pgp-signature, Size: 490 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Bitcoin-development] Distributing low POW headers 2013-07-24 9:42 ` Peter Todd @ 2013-07-24 11:55 ` Tier Nolan 2013-07-28 18:42 ` John Dillon 0 siblings, 1 reply; 5+ messages in thread From: Tier Nolan @ 2013-07-24 11:55 UTC (permalink / raw) Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 3937 bytes --] On Wed, Jul 24, 2013 at 10:42 AM, Peter Todd <pete@petertodd•org> wrote: > Please provide equations and data justifying the 'magic constants' in > this proposal. > The are a range of workable values. Ideally, there would first need to be agreement on the general principle. Distributing headers with 1/64 of the standard POW means that a header would be broadcast approximately once every 9 seconds (assuming a 10 minute block time). This was picked because sending 80 byte headers every 9 seconds shouldn't represent much load on the network. The second magic number is how much credit to give for mini-headers. Setting it at 1/16 means that the headers will be worth around 4 times as much as a block (since there would be around 63 low POW headers for each full POW one). This creates an incentive for miners to take headers into account. If all the headers were worth less than a full block, then a fork which was losing would suddenly be winning if a block is found. A fork will only become the main chain due to a new block, if it is within 16 mini-confirms. Miners don't have to mine against the absolute best fork, but they do need to make sure they stay within 16 of the best one (so if they find a block, that block would be considered part of the main chain). Some hysteresis might be helpful. The rule could be to only switch unless the current fork is losing by at least 4 mini-confirms. In most cases, this won't be a problem, since orphans don't happen that often anyway. Since it isn't a chain, this doesn't give the full benefits of a 9 second block, but it should bring things to consensus faster. 6 full confirms would be much more secure against random and hostile reversals. It doesn't have the risks of 9 second blocks in causing network collapse, since it isn't a chain, the headers are short, and there is no confirmations of the required (other than checking the hash). Each "mini" confirms adds to the strength of leaf blocks of the tree. If there is a tie, and 20% of the network is mining one block and 80% is mining the other, the mining power of the network will be split until the next block arrives. With mini confirms, the entire network is aware of the 2 blocks (since the headers would be forwarded) and the mini-confirms would show which one has majority hashing power. The least risk option would be to make them purely advisory. The proposal takes it further than that. The proposal means that if the network is split 80/20, then miners should stick with the 80% fork, even if the 20% fork wins the race for the next block. Winning a few rounds is easier than wining many rounds worth of mini-confirms. The key is that as long as the honest miners stay on the main chain, they will eventually overwhelm any rewrite attack with less than 50% of the mining power. This is a system to agree on what is the main chain in the face of a re-write attack. > > Currently we do not relay blocks to peers if they conflict with blocks > in the best known chain. What changes exactly are you proposing to that > behavior? > The (sub) proposal is that headers would still be broadcast. The blocks would not be forwarded. If a header extends the header tree, meets full POW and is "near" the end of the chain, then it is broadcast. This means that all nodes will have the entire header tree, including orphans. The full blocks would only be sent if they extend the main chain. Second, if a header builds on a header that is in the header tree, then it is broadcast, even if it doesn't meet full POW (only 1/64 required). This gives information on which fork is getting the most power. It gives information about potential "consensus loss" forks, where a significant number of miners are following an alternative chain. In fact, this is probably worth doing as an initial step. A warning could be displayed on the client if a fork is getting more than 15% of the hashing power. [-- Attachment #2: Type: text/html, Size: 4929 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Bitcoin-development] Distributing low POW headers 2013-07-24 11:55 ` Tier Nolan @ 2013-07-28 18:42 ` John Dillon 2013-07-28 20:07 ` Tier Nolan 0 siblings, 1 reply; 5+ messages in thread From: John Dillon @ 2013-07-28 18:42 UTC (permalink / raw) To: Tier Nolan; +Cc: Bitcoin Dev -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 On Wed, Jul 24, 2013 at 11:55 AM, Tier Nolan <tier.nolan@gmail•com> wrote: > Distributing headers with 1/64 of the standard POW means that a header would > be broadcast approximately once every 9 seconds (assuming a 10 minute block > time). This was picked because sending 80 byte headers every 9 seconds > shouldn't represent much load on the network. As Peter said, "much" should be quantified. Remember that there is a statistical distribution here, what is the probability of how many seconds per headers? > This creates an incentive for miners to take headers into account. If all > the headers were worth less than a full block, then a fork which was losing > would suddenly be winning if a block is found. A fork will only become the > main chain due to a new block, if it is within 16 mini-confirms. Sounds like you are changing economics and requiring miners to have even better network connections. This is not a thing to do lightly and it probably a bad idea. > Second, if a header builds on a header that is in the header tree, then it > is broadcast, even if it doesn't meet full POW (only 1/64 required). This > gives information on which fork is getting the most power. > > It gives information about potential "consensus loss" forks, where a > significant number of miners are following an alternative chain. > > In fact, this is probably worth doing as an initial step. I understand Pieter Wuille is working on letting Bitcoin propagate and make use of pure block headers, a step towards SPV and partial UTXO mode. Orphan measurement would be very useful for a lot of reasons, how about you think about that first? It wouldn't have the potential data rate issues either and should be a very simple change. Just set some threshold relative to the height of the best block where you will not further propagate and orphan block(header) and prior to that limit do so freely. I believe the change would be 100% compatible with the P2P protocol as it is based on inventories. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) iQEcBAEBCAAGBQJR9WXdAAoJEEWCsU4mNhiPBUYIALgg3ylA5mkciT3W/kb+qXCp spYlPwAU/HVUrd/p6Ra6xAOOa224BE018FHRx7cJ31AQdVPsKhC1XiQCeYMv14Cj 5LstO2VTzxLovfs1lTVnekt+xVo6EHP47Qhmhdfo1AQWHS2njIp2lT9gAlNgMYoI Twu0FLfJFwg14HlueLhTNvGo3TeVpGhTV3HYTbjWGBuPeroaaPCKKQOy/jmA9mnZ 1x4MjQZ+AkGA3+vrinyRZ1FQsp1pOUZMZx5UFYDOOPS3TysxttiHF/Vkdmy9dNVf 5zbXrEDImlariRnyxCf6sn4Fpu9H9bt6yttCez6NHqAoZCwciXyo+UrZjFawSVg= =8gci -----END PGP SIGNATURE----- ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Bitcoin-development] Distributing low POW headers 2013-07-28 18:42 ` John Dillon @ 2013-07-28 20:07 ` Tier Nolan 0 siblings, 0 replies; 5+ messages in thread From: Tier Nolan @ 2013-07-28 20:07 UTC (permalink / raw) To: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 4020 bytes --] On Sun, Jul 28, 2013 at 7:42 PM, John Dillon <john.dillon892@googlemail•com>wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA256 > > On Wed, Jul 24, 2013 at 11:55 AM, Tier Nolan <tier.nolan@gmail•com> wrote: > > Distributing headers with 1/64 of the standard POW means that a header > would > > be broadcast approximately once every 9 seconds (assuming a 10 minute > block > > time). This was picked because sending 80 byte headers every 9 seconds > > shouldn't represent much load on the network. > > As Peter said, "much" should be quantified. > It has the same statistic properties as normal blocks just 64 times faster. Even if there is a new block 30 seconds after the previous one, that doesn't cause a burst of 64 low POW block headers in the 30 second window. They are all statistically independent hashing attempts. > Sounds like you are changing economics and requiring miners to have even > better > network connections. This is not a thing to do lightly and it probably a > bad > idea. > No, it just breaks ties. In most cases there would be only 1 contender block, so all miners are equal. If 10% of blocks were ties/orphans, then only 1% of blocks would be a 3-way tie. That probably overestimates the orphan rate. This means the miner has to download 2 blocks 10% of the time and 3 blocks 1% of the time. However, even then, half the network wouldn't have to download the 2nd block of the tie, since they happened to get the winner first. This means 5% extra bandwidth on average. 16 low POW headers at 9 seconds per header is more than 2 minutes for a miner to switch to the other contender. A miner would only lose out if he doesn't notice that block he is mining against is not getting built on by anyone else. He needs to download both tied blocks so that he can switch, but he has 2 minutes to actually switch. I understand Pieter Wuille is working on letting Bitcoin propagate and make > use > of pure block headers, a step towards SPV and partial UTXO mode. > That would need to happen before low POW ones are broadcast. There is a basic set of rules in the first post. At the moment, the client only provides headers when asked, but never broadcasts them. > Orphan measurement would be very useful for a lot of reasons, how about you > think about that first? I think distributing the low POW headers on an advisory basis a reasonable first step. However, just broadcasting the headers is a zeroth step. Miners would probably break ties towards the block that seems to be getting the most hashing anyway. I think for orphan rate, the best is to have a system to link to orphans. This would add the POW of the orphan to the main chain's total. Unfortunately adding fields to the header is hard. It could be done as a coinbase extra-nonce thing. A better option would be if the merkle tree could include non-transactions. The merkle root could be replaced by hash(auxiliary header). This has the advantage of not impacting ASIC miners. Broadcasting all headers would at least allow clients to count orphans, even if they aren't integrated into the block chain. It wouldn't have the potential data rate issues either > and should be a very simple change. I don't think the data rate is really that high. It would be 80 bytes every 9 seconds, or 9 bytes per second. Blocks are 500kB every 10 minutes, or 853 bytes per second. > Just set some threshold relative to the > height of the best block where you will not further propagate and orphan > block(header) and prior to that limit do so freely. I believe the change > would > be 100% compatible with the P2P protocol as it is based on inventories. > Right absolutely. Headers of blocks that add to the block tree within recent history should be forwarded. The inv system would need to be tweaked, since it can only say block and transaction. A block header field would allow the node to say that it only has the header. Alternatively, it would reply with a header message to the getblocks message. [-- Attachment #2: Type: text/html, Size: 5673 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2013-07-28 20:07 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2013-07-23 11:27 [Bitcoin-development] Distributing low POW headers Tier Nolan 2013-07-24 9:42 ` Peter Todd 2013-07-24 11:55 ` Tier Nolan 2013-07-28 18:42 ` John Dillon 2013-07-28 20:07 ` Tier Nolan
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox