Re: [Bitcoin-development] Distributing low POW headers
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
001e1c3393788031c4e427b67cfd1b5e90a3b0de4fff094b2894
signature.asc
Description: Digital signature
--
See everything from the browser to the database with AppDynamics
Get end-to-end visibility with application monitoring from AppDynamics
Isolate bottlenecks and diagnose root cause in seconds.
Start your free trial of AppDynamics Pro today!
http://pubads.g.doubleclick.net/gampad/clk?id=48808831iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Distributing low POW headers
On Wed, Jul 24, 2013 at 10:42 AM, Peter Todd p...@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. -- See everything from the browser to the database with AppDynamics Get end-to-end visibility with application monitoring from AppDynamics Isolate bottlenecks and diagnose root cause in seconds. Start your free trial of AppDynamics Pro today! http://pubads.g.doubleclick.net/gampad/clk?id=48808831iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Linux packaging letter
On Wed, Jul 24, 2013 at 4:28 AM, Mike Hearn m...@plan99.net wrote: Yeah, if anyone wants to make the letter more digestable please do propose an alternative, although by this point it's probably not worth it as people have already signed. I'm working on a more digestable alternative: https://gist.github.com/jgarzik/6065679 Should be ready in another ~24 hours, as its obviously incomplete right now. Alas the publishing of the lame version (which yes, I did ACK) didn't give me time to finish my version. I worked on Fedora packaging while at Red Hat, so hopefully, I have a bit of insight here. Was also thinking about publishing this on opensource.com. -- Jeff Garzik Senior Software Engineer and open source evangelist BitPay, Inc. https://bitpay.com/ -- See everything from the browser to the database with AppDynamics Get end-to-end visibility with application monitoring from AppDynamics Isolate bottlenecks and diagnose root cause in seconds. Start your free trial of AppDynamics Pro today! http://pubads.g.doubleclick.net/gampad/clk?id=48808831iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Linux packaging letter
On Wed, Jul 24, 2013 at 10:28:16AM +0200, Mike Hearn wrote: Yeah, if anyone wants to make the letter more digestable please do propose an alternative, although by this point it's probably not worth it as people have already signed. Okay, here's my attempt: https://docs.google.com/document/d/1m3wyBIjqwPQ3wxVT7P_wJtdWt9a9RXvt9NV7rggLAOs/edit# Please feel free to use any or all of it as you see fit. FWIW, Gregory is right that my original draft was much more brusque. The pain in the packaging relationship travels both ways. I have in the past wasted a lot of time due to bogus packaging applied by non-expert packagers that broke things. In fact the project I was a part of adopted a policy of automatically closing bug reports from people who were using distributor packages (any distro) because the quality was so inconsistent and so many subtle bugs were introduced. If packagers hear upstreams cry about packaging a lot, I think you should keep an open mind that some of them probably know what they're talking about. We really shouldn't have to beg and cajole here. Saying we have our reasons and we want you to stop should be enough. Yes, I know what you mean. Regards, Zooko -- See everything from the browser to the database with AppDynamics Get end-to-end visibility with application monitoring from AppDynamics Isolate bottlenecks and diagnose root cause in seconds. Start your free trial of AppDynamics Pro today! http://pubads.g.doubleclick.net/gampad/clk?id=48808831iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
