[EDIT] A more 'difficult' algorithm for POW based on area?

btchris

hero member

Activity: 672

Merit: 504

a.k.a. gurnec on GitHub

Quote from: qdoop on October 23, 2014, 05:28:52 AM

Is there a way to make nodes agree an what is the most appropriate block to mine on top of it?
For example the hash of each block could be used to make all nodes of the network agree and choose either (A) or (B)

Any such scheme would lead to exactly the same attacks mentioned above.

qdoop

member

Activity: 119

Merit: 112

_copy_improve_

Quote from: deepceleron on October 23, 2014, 01:46:49 AM

The hash that comes out of a strong hashing algorithm has a random distribution. Although it is less likely, it doesn't take any more work to find a 000000000000000001.. hash than it does a 0000ffff.. hash, only luck.

The blockchain requires each block to meet the proof of work. To replace ten past blocks, you would have to generate ten blocks of your own. This is a much higher bar than a single lucky hash being able to replace ten blocks.

With a more-difficult-hash chain instantly winning like proposed, it would be an orphan free-for-all, you could get one lucky hash attempting to build on blocks from a week ago and replace tons of transactions. As described, a miner could attack for free by

1. constantly be transferring a large balance between new addresses in every block they mine,
2. find a "lucky" hash much smaller than the average and withhold it, and
3. make all sorts of purchases that will be wiped when they publish the chain-erasing block find that sends the money back to the miner.

OP already annoyed everyone with his great ideas based on a poor understanding of mining here: https://bitcointalksearch.org/topic/m.9204175

I am a honest miner and lets say i mine on level n.
I receive a new valid block (A) at level n+1 so i switch mining on top of this new block.
Due to network delay few seconds later i receive another valid block (B) for lever n+1.
At that particular moment part of the network is mining on top of (A) and the rest on top of (B)

So if our decision (which block to mine on?) is based solely on block's arrival time part of the network would be mining on the 'wrong' block.

Is there a way to make nodes agree an what is the most appropriate block to mine on top of it?
For example the hash of each block could be used to make all nodes of the network agree and choose either (A) or (B)

Do we want a solution in this idiomatic case or we leave it just in luck?

PS. How reference Bitcoin Core client behaves in the above case?

deepceleron

legendary

Activity: 1512

Merit: 1036

The hash that comes out of a strong hashing algorithm has a random distribution. Although it is less likely, it doesn't take any more work to find a 000000000000000001.. hash than it does a 0000ffff.. hash, only luck.

The blockchain requires each block to meet the proof of work. To replace ten past blocks, you would have to generate ten blocks of your own. This is a much higher bar than a single lucky hash being able to replace ten blocks.

With a more-difficult-hash chain instantly winning like proposed, it would be an orphan free-for-all, you could get one lucky hash attempting to build on blocks from a week ago and replace tons of transactions. As described, a miner could attack for free by

1. constantly be transferring a large balance between new addresses in every block they mine,
2. find a "lucky" hash much smaller than the average and withhold it, and
3. make all sorts of purchases that will be wiped when they publish the chain-erasing block find that sends the money back to the miner.

OP already annoyed everyone with his great ideas based on a poor understanding of mining here: https://bitcointalksearch.org/topic/m.9204175

qdoop

member

Activity: 119

Merit: 112

_copy_improve_

Quote from: btchris on October 22, 2014, 02:04:51 PM

Quote from: qdoop on October 22, 2014, 01:50:01 PM

I have edited the OP to take advantage of your feedback on this king of attack
1-6 comfirmation attacks are always possible under normal conditions although you have to be extremely lucky.

What is the issue I try to make more difficult is the possibility of long chains replacing the current

There's nothing magical about the number 6, as I'm sure you're aware. 7-confirmation reorgs or attacks could happen, they're just less likely than 6 (and more likely than 8 ).

I don't think your idea is bad per-se, I just don't think that the advantages it confers outweigh the new vulnerabilities it introduces, but that's just my opinion.

Thanks for your review.

To sum up the case:

Given a block chain(curve) in order for a new block chain to replace it, one currently has to simply stay below the Difficulty bound and make it long enough.

We propose a more strict requirement (to achieve), that the new curve has most of the points below the given bock chain(curve) and be of equal length in order to replace it.

PS.
a)The maths may be much simpler as sum of -1,0,+1 depending on pointwise comparisons.
b)A form of mathematical "measure" of the quality between the current curve and a possible replacement is what we seek

btchris

hero member

Activity: 672

Merit: 504

a.k.a. gurnec on GitHub

Quote from: qdoop on October 22, 2014, 01:50:01 PM

I have edited the OP to take advantage of your feedback on this king of attack
1-6 comfirmation attacks are always possible under normal conditions although you have to be extremely lucky.

What is the issue I try to make more difficult is the possibility of long chains replacing the current

There's nothing magical about the number 6, as I'm sure you're aware. 7-confirmation reorgs or attacks could happen, they're just less likely than 6 (and more likely than 8 ).

I don't think your idea is bad per-se, I just don't think that the advantages it confers outweigh the new vulnerabilities it introduces, but that's just my opinion.

qdoop

member

Activity: 119

Merit: 112

_copy_improve_

Quote from: qdoop on October 22, 2014, 08:32:57 AM

[EDIT]

Quote from: btchris on October 22, 2014, 09:08:16 AM

You're proposing that the total work be based on the value of the individual hashes, instead of the hash targets, is that correct?

This could incentivize a miner who happens to find a hash with an unusually low value to refrain from immediately broadcasting it. See, for example, this attack proposed a few years ago by casascius, which becomes viable with this proposed change.

Thanks to btchris for feedback

As a measure of performance of a curve/blockchain in order to avoid the above attack we could sum the sign changes between two curves +1,0,-1 comparing curve values point wise and assuming max value were a curve lucks a point.

the scores of the curves would then became

(A)-(C)=+1+1-1
(B)-(A)=+1+1-1
(B)-(C)=+1+1-1-1

I have edited the OP to take advantage of your feedback on this kind of attack
1-6 comfirmation attacks are always possible even under normal conditions although you have to be extremely lucky.

What is the issue I try to make more difficult is the possibility of long chains replacing the current

btchris

hero member

Activity: 672

Merit: 504

a.k.a. gurnec on GitHub

Quote from: qdoop on October 22, 2014, 09:39:42 AM

Quote from: btchris on October 22, 2014, 09:08:16 AM

You're proposing that the total work be based on the value of the individual hashes, instead of the hash targets, is that correct?

Yes but with a little twist. To compare two chains the must include blocks up to the same level.

Quote from: btchris on October 22, 2014, 09:08:16 AM

This could incentivize a miner who happens to find a hash with an unusually low value to refrain from immediately broadcasting it. See, for example, this attack proposed a few years ago by casascius, which becomes viable with this proposed change.

Thanks for this particular case.

To compare two chains they must include blocks up to the same level. So although our friend could through such a block the rest miners lets
say if they where 10 blocks ahead would ask him to catch them up by providing the missing 10 blocks each one with hash value equal or smaller of existing ones.

PS. I try to think of what should happen when 2 separated block chains merge again.

I don't think that this completely eliminates casascius's attack.

Evil miner M finds a lucky block, and withholds it. During this period, evil miner M prepares double-spend attacks, and can point his mining power to his new (secret) chain.

Once good miner A publishes her new (but less lucky) block, M can take advantage of his double-spends (which now have only one confirmation), wait some short period of time and then announce his superior block.

M can therefore trick anyone who chooses to accept 1-conf transactions (which admittedly isn't all that smart, nor does M have that long to do so), plus they've also been able to mine on a secret chain while the rest of the network was wasting their time on A's shorter chain.

qdoop

member

Activity: 119

Merit: 112

_copy_improve_

Quote from: btchris on October 22, 2014, 09:08:16 AM

You're proposing that the total work be based on the value of the individual hashes, instead of the hash targets, is that correct?

Yes but with a little twist. To compare two chains the must include blocks up to the same level.

Quote from: btchris on October 22, 2014, 09:08:16 AM

This could incentivize a miner who happens to find a hash with an unusually low value to refrain from immediately broadcasting it. See, for example, this attack proposed a few years ago by casascius, which becomes viable with this proposed change.

Thanks for this particular case.

To compare two chains they must include blocks up to the same level. So although our friend could through such a block the rest miners lets
say if they where 10 blocks ahead would ask him to catch them up by providing the missing 10 blocks each one with hash value equal or smaller of existing ones.

PS. I try to think of what should happen when 2 separated block chains merge again.

btchris

hero member

Activity: 672

Merit: 504

a.k.a. gurnec on GitHub

You're proposing that the total work be based on the value of the individual hashes, instead of the hash targets, is that correct?

This could incentivize a miner who happens to find a hash with an unusually low value to refrain from immediately broadcasting it. See, for example, this attack proposed a few years ago by casascius, which becomes viable with this proposed change.

qdoop

member

Activity: 119

Merit: 112

_copy_improve_

Code:

	Block Hash (as big integer value)
		|(y)
		|
		|   
		|       -------------------------------+
		|       --- *           #---#---# (C)  |
		|            \         /               |
		|             \       /	               +---------------------(Difficulty bound)
		|              \     /    
		|               *---*---*---* (A)
		|                \
		|                 \
		|                  \
		|                   +---+ (B)
		|
		+---+---+---+---+---+---+---+---+---+---+---+---+----+---+-(x)
					   n-1  n  n+1 n+2 n+3
										n - Height

In the above diagram we represent three different block chains as curves where y(Block Hash as integer) and x(block Height n)

Correct me if i am wrong but according to current Bitcoin POW
Block chain (C) wins as the longest with adequate proof of work (sum of nBits)
Chains (A) and (B) although harder to generate don't count, as shorter.

What if we measured the area bellow each curve as Proof of work for a chain*?
Then a really low hash value in a chain would be taken into account making it further difficult to generate better curves given a known one.

*We would then have to minimize the area at given height.

[EDIT]

Quote from: btchris on October 22, 2014, 09:08:16 AM

You're proposing that the total work be based on the value of the individual hashes, instead of the hash targets, is that correct?

This could incentivize a miner who happens to find a hash with an unusually low value to refrain from immediately broadcasting it. See, for example, this attack proposed a few years ago by casascius, which becomes viable with this proposed change.

Thanks to btchris for feedback

As a measure of performance of a curve/blockchain in order to avoid the above attack we could sum the sign changes between two curves +1,0,-1 comparing curve values point wise and assuming max value were a curve lucks a point.

the scores of the curves would then became

(A)-(C)=+1+1-1
(B)-(A)=+1+1-1
(B)-(C)=+1+1-1-1

Topic: [EDIT] A more 'difficult' algorithm for POW based on area? (Read 1288 times)