Bitcoin Forum
May 09, 2024, 08:53:26 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Reducing the chance of random reversal  (Read 838 times)
TierNolan (OP)
Legendary
*
Offline Offline

Activity: 1232
Merit: 1083


View Profile
June 27, 2013, 02:00:44 PM
 #1

I was thinking about a simplification of a proposal I made a while back to speed up confirmations.

The idea was to create a sub-chain using waste headers from the normal mining process.  A lot of the benefit can be obtained by just broadcasting the headers without actually forming a sub-chain.

A block header that doesn't meet the full POW can be used as a mini-confirm and is created automatically when trying to find blocks that meet the full POW.

The rules would be

Block headers should be propagated if

- they have a prev link to a block within N of the end of the chain (say 100)
- they meet POW of 1/64 of the target difficulty

These block headers count as a mini-confirm for the prev block.

The POW for a block is equal to (1 + mini-confirms/16) of the normal POW amount

This allows the network settle on which block to orphan much faster.

For example, assuming there has been a fork and some miners receive E* first and others receive E'.  The chain is

A <- B <- C <- D <- (E* or E')

Under the current system, the network will remain split until a block is built on top of E* or E' and then a re-org will happen for the other half of the network.

Under the proposed system, all the miners who think E* is the earlier block will also be trying to find mini-confirms for E* (and vice versa for E').

After 10 mins / 64 = 9.4 seconds, some miner will find a mini-confirm and broadcast it.  If this is for E*, then the E* chain now has a small amount of POW more than the E' chain and so most miners will switch to it.  This means the re-org happens after 10 seconds instead of 10 mins.

On average each block will have 1 confirm and 64 mini-confirms.  The mini confirms represent most of the POW.  A miner with 10% of the network would have a much harder time reversing 384 mini confirms than reversing 6 blocks.

Merchants would still have to wait for 1 confirm though, but once the transaction is in 1 block, every 10 seconds afterwards, they get an additional confirm.

Large transactions would still need to wait until the total transactions fees are greater than the value of the transaction.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
1715244806
Hero Member
*
Offline Offline

Posts: 1715244806

View Profile Personal Message (Offline)

Ignore
1715244806
Reply with quote  #2

1715244806
Report to moderator
1715244806
Hero Member
*
Offline Offline

Posts: 1715244806

View Profile Personal Message (Offline)

Ignore
1715244806
Reply with quote  #2

1715244806
Report to moderator
1715244806
Hero Member
*
Offline Offline

Posts: 1715244806

View Profile Personal Message (Offline)

Ignore
1715244806
Reply with quote  #2

1715244806
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1715244806
Hero Member
*
Offline Offline

Posts: 1715244806

View Profile Personal Message (Offline)

Ignore
1715244806
Reply with quote  #2

1715244806
Report to moderator
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428
Merit: 1093


Core Armory Developer


View Profile WWW
June 27, 2013, 10:10:37 PM
 #2

I haven't fully thought it through, but don't forget that although a fork only takes 10 seconds to resolve in your scheme, forks happen a whole ton more often.  I don't know what all the terms add up to, but it wouldn't surprise me if this turned out to cause miners to spend more time mining on forks than less.  Especially as you lower that average-time-between-blocks closer to the average header propagation time.  I don't know what propagation times are, but if they were on average 30s to reach 99% of the network, you could have X% (X>10) of the network always mining on [soon-to-be] dead chains.    

At the very least it would lower the effective hashrate, making the network more vulnerable.  If you have 100 units of hashing power building one blockchain, an attacker needs 101 to outpace it.  If you have 4 groups of 25 units each mining on different forks, an attacker only need 26 to outpace it, even though the total network hashrate is the same.

Satoshi picked 10 minutes, because he was concerned about the network dynamics of slow block propagation and what dragons it would create.  He picked 10 minutes to be conservative, knowing that if it's long enough to absolutely be sure that propagation can happen reliably and consistently.  Though I don't have any links off-hand to previous discussions about that.  I'd be curious to re-read it myself.

Though, I'm going off on a tangent: your idea doesn't rely on 10s... it can be calibrated to whatever is "safe."  I do like the gist of the idea, since we already know that safety is basically a asymptotically increasing as the number of confirmations goes up, so if you can get the first couple confirmations out the door immediately 64 mini-confirmations would most definitely be better than 1 regular confirmation.

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
TierNolan (OP)
Legendary
*
Offline Offline

Activity: 1232
Merit: 1083


View Profile
June 27, 2013, 11:07:40 PM
 #3

I haven't fully thought it through, but don't forget that although a fork only takes 10 seconds to resolve in your scheme, forks happen a whole ton more often.  I don't know what all the terms add up to, but it wouldn't surprise me if this turned out to cause miners to spend more time mining on forks than less.  Especially as you lower that average-time-between-blocks closer to the average header propagation time.  I don't know what propagation times are, but if they were on average 30s to reach 99% of the network, you could have X% (X>10) of the network always mining on [soon-to-be] dead chains.  

They aren't actually chains.  They are just counters for all potential orphans.  If there is a tie, mine against the block with the most mini-confirms (though 16 mini-confirms is equal to 1 full block).

Propagation of the block headers should be very fast.  All you need to do is verify that the prev hash link points to a header within the last 100 blocks (including side chains) and then check that it meets 1/64 of the POW.  That is a hashmap lookup and a hash, and then send 80 bytes to all peers.

If there is a 5% orphan rate now, then this would only have an effect 5% of the time.  In that 5% of the time, you are just recording the number of mini-confirms for the 2 potential blocks.

Quote
At the very least it would lower the effective hashrate, making the network more vulnerable.

I don't see why.  If 100% of the network agrees on the next block, then this has no effect. 

If it is split 2-1, then it should move the 33% over to the 67% side more quickly.

Having said that, there isn't that massive an incentive to switch.  Unless you are 16 mini-confirms behind, your next full block will still break the tie.

Quote
If you have 4 groups of 25 units each mining on different forks, an attacker only need 26 to outpace it, even though the total network hashrate is the same.

This is about having those 4 groups agree on which of the 4 to all mine on.  The mini-confirms are a notification to the rest of the network that that block is being mined against.

Quote
Satoshi picked 10 minutes, because he was concerned about the network dynamics of slow block propagation and what dragons it would create.  He picked 10 minutes to be conservative, knowing that if it's long enough to absolutely be sure that propagation can happen reliably and consistently.  Though I don't have any links off-hand to previous discussions about that.  I'd be curious to re-read it myself.

This is not about reducing the block time to 10 seconds.  This is having headers being sent (not forming chains) to indicate where the rest of the network is mining, when two blocks are found close enough to split the network hashing power.

There is no verification of signatures or anything, just an 80 byte header.

Quote
Though, I'm going off on a tangent: your idea doesn't rely on 10s... it can be calibrated to whatever is "safe."

I don't see any issue with going even lower than 10.  However, the benefits are limited, since you still need 1 full block confirmation. 

Quote
I do like the gist of the idea, since we already know that safety is basically a asymptotically increasing as the number of confirmations goes up, so if you can get the first couple confirmations out the door immediately 64 mini-confirmations would most definitely be better than 1 regular confirmation.

Well, it doesn't speed up the first confirm, since the mini-confirms aren't actually blocks.  It just makes it much less likely that a block would be randomly reversed.

1 full confirm and then 20-30 mini-confirms would be highly unlikely to be reversed.

Miners have an incentive to always mine on a block that is within 16 mini-confirms of the block with the most mini-confirms.

This means that a block that is more than 16 mini-confirms ahead of any other block is likely to have 100% of the hashing power on that block.

The recommendation could be 1 full block + 32 mini-confirms to give a high safety margin.  That is 15 minutes instead of 1 hour to get a high degrees of safety.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428
Merit: 1093


Core Armory Developer


View Profile WWW
June 27, 2013, 11:18:17 PM
 #4

Oh I missed the part about no tx on each mini block.  So all this does is effectively eliminates the probability of one-block reversals.  Hmm, I'm not so much in favor of this direction.

My only point was that as your average confirm time moves closer to the header propagation time, you're dramatically increasing time spent by miners mining on forks.  Sure you don't get one-regular-confirmation reversals, but you'll end up with a totally fragmented network all working on different chains because most of the network can't get the longest chain in time to switch to it.    It may be that the header propagation times are, in fact, much smaller than 10s, in which case it wouldn't be so bad for the majority of the network. 

But consider a miner on a slow, high-latency connection.  If they have 10s latency to receive data, they would probably spend >50% of their time mining on forks.  Basically, they wouldn't be able to mine. 

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
jl2012
Legendary
*
Offline Offline

Activity: 1792
Merit: 1097


View Profile
June 28, 2013, 07:25:21 AM
 #5

Oh I missed the part about no tx on each mini block.  So all this does is effectively eliminates the probability of one-block reversals.  Hmm, I'm not so much in favor of this direction.

This does not only eliminate the probability of block reversal, but also reduces the average full confirmation time from 60 mins to 15-20 mins.


My only point was that as your average confirm time moves closer to the header propagation time, you're dramatically increasing time spent by miners mining on forks.  Sure you don't get one-regular-confirmation reversals, but you'll end up with a totally fragmented network all working on different chains because most of the network can't get the longest chain in time to switch to it.    It may be that the header propagation times are, in fact, much smaller than 10s, in which case it wouldn't be so bad for the majority of the network. 

But consider a miner on a slow, high-latency connection.  If they have 10s latency to receive data, they would probably spend >50% of their time mining on forks.  Basically, they wouldn't be able to mine. 

They would probably spend 50% of their time mining on forks ONLY WHEN THERE IS A FORK. If the fork rate is 5%, they would spend only 2.5% of their total mining on forks

Also, we may first try 1min instead of 10s. Mining with 1min latency is not possible anyway.

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3 (Bitcoin ONLY)
LRDGENPLYrcTRssGoZrsCT1hngaH3BVkM4 (LTC)
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
jl2012
Legendary
*
Offline Offline

Activity: 1792
Merit: 1097


View Profile
June 28, 2013, 07:25:53 AM
 #6


The POW for a block is equal to (1 + mini-confirms/16) of the normal POW amount



Why 16 instead of 64?

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3 (Bitcoin ONLY)
LRDGENPLYrcTRssGoZrsCT1hngaH3BVkM4 (LTC)
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
TierNolan (OP)
Legendary
*
Offline Offline

Activity: 1232
Merit: 1083


View Profile
June 28, 2013, 07:43:41 AM
 #7

Oh I missed the part about no tx on each mini block.  So all this does is effectively eliminates the probability of one-block reversals.  Hmm, I'm not so much in favor of this direction.

What this is is that miners broadcast the headers of failed hash attempts (if the header meets 1/64 of the required POW but not the full POW).

Quote
But consider a miner on a slow, high-latency connection.  If they have 10s latency to receive data, they would probably spend >50% of their time mining on forks.  Basically, they wouldn't be able to mine. 

There is no sub-chain formed.  Miners only mine against full blocks.  It is just extra information to move mining power to break a tie more quickly.

When you receive a mini-confirm, you just add one to that block.  Normally, that will be the block you were working on anyway.

If you have 2 blocks that have the same height you would normally only work on the one you received first.  Under the proposal, you would have a counter for both, and if the 2nd one gets more mini-confirms, you would switch to it.  This would also include forwarding the actual full block, since the nodes wouldn't have forwarded the full blocks as they didn't extend the main chain.

So, the process where 2 blocks are found together would be something like

50%: mining on top of block E*
50%: mining on top of block E'

A miner building on E* finds a mini confirm and broadcasts it.  It gets to 70% of the miners before an E' mini-confirm (since the E' "hit" happens slightly later).

All miners who received the E* mini-confirm first now consider that the longest chain.

Miners would move from E' to E* as quickly as block E* can be spread over the network (a smaller number will move in the other direction).  

If an actual "fight" happened, where it was moving back and forward between the 2, then eventually most miners would have both blocks and so can switch to the one with the most mini-confirms instantly.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
TierNolan (OP)
Legendary
*
Offline Offline

Activity: 1232
Merit: 1083


View Profile
June 28, 2013, 09:10:14 AM
 #8

Why 16 instead of 64?

There is a tradeoff.

If it was set to 128, then there is no real point in participating in the system.  If E* was getting most of the mining then it would have around 64 micro-confirms when the next block is found.  However, a miner who didn't bother to listen could publish F' (built on E') and that would be the longest chain, even though E* was the accepted block, since it gets 128 points of credit.

This removes the incentive to participate.

Now that I think about it, the main disadvantage of having a very low value (say 1) doesn't apply to this system.

With the other system it was actually a chain.  This meant that a miner could hold back their mini-confirms until they hit a block and then publish them as a unit.  A miner who doesn't have a "lead-in" set of mini-confirms would lose the tie-break even if he published his block first.  This gives larger miners an advantage.

That doesn't apply here though, since the mini-confirms don't actually form a chain, they just confirm the previous block.

However, a low value means that full blocks are easier to reverse which I think would reduce stability.  16 seems a reasonable trade-off, it creates an incentive to participate without causing to many issues if some mini-confirms are lost.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1025



View Profile
June 28, 2013, 10:41:39 AM
 #9

Basically, this is just a mechanism that miners can use to publish proof that they are working on one branch or the other.  Other miners can then take it as an advisory and decide voluntarily to switch (or not).

I like it a lot more than the usual idea that pops up once a month.  But I don't see it as being very useful, at least not for miners.  There is no penalty for working on the unpopular side of a fork, and there may even be a reward.

But for users, it may be useful if a transaction they care about is only in one fork or the other because they would be able to see what fraction of the network (by hashing power) is building on top of that fork.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
TierNolan (OP)
Legendary
*
Offline Offline

Activity: 1232
Merit: 1083


View Profile
June 28, 2013, 11:11:39 AM
 #10

Basically, this is just a mechanism that miners can use to publish proof that they are working on one branch or the other.  

Right

Quote
I like it a lot more than the usual idea that pops up once a month.  But I don't see it as being very useful, at least not for miners.  There is no penalty for working on the unpopular side of a fork, and there may even be a reward.

That is why a full block has a weight of 16 and not 64.

If E* has 43 mini-confirms and E' has 20 and a miner finds F', then it still doesn't move to the front of the chain, since 20 mini-confirms + 16 for F' is still less than the 43 mini-confirms E* has.

Miners need to make sure they are mining on a block that is within 16 of the highest number of mini-confirms.

Quote
But for users, it may be useful if a transaction they care about is only in one fork or the other because they would be able to see what fraction of the network (by hashing power) is building on top of that fork.

That is another benefit, it would give finer resolution on hashing power if there is a network fork, like what happened with the upgrade to 8.x.

However, in that case, just looking at full blocks would have shown there was an alt chain with more than 10% of the hashing power and could have triggered automatic warnings in the client.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!