Floating-Point Nakamoto Consensus #19665

TheRook commented at 3:15 AM on August 5, 2020: none

This change is related to a whitepaper I submitted privately to ZmnSCPxj, and this PR is by his request.

Changes in this pr:

Updated the protocol layer to accept a competing chain of the same height so that it's fitness can be tested.
Updated the verification layer to incorporate a block fitness test to resolve disagreements.
Introduced an uint256-bit addition operator to support the block fitness test.

When forming a Nakamoto Consensus, two competing chains of equal length can presented to the network. Nodes within the network see these two chains authoritative equals, and a disagreement forms on which is the authoritative equal. Floating-Point Nakamoto Consensus introduces a method of disagreement resolution by setting up a kind of relay-race - where the winning team’s strength is carried forward. This design is intended to cement the lead of the winner and to greatly incentivize the network to adopt the dominant chain no matter how many valid solutions are advertised, or what order they arrive.

The first step in this new algorithm is that a node in the network should continue to conduct traditional Nakamoto Consensus, but If at any point there are two solution blocks advertised for the same height - then the more-fit block is chosen as the winner which is then propagated to neighbors. It is in the best interest of all miners to adopt the most-fit block, failing to do so risks wasting resources on a mining a block that would be discarded.

In order to have a decentralized solution, this kind of agreement must be empirically derived from the existing proof-of-work so that it is identically verifiable by all nodes on the network. Additionally, this fitness evaluation needs to ensure that no two competing solutions can be numerically equivalent.

Floating-Point Nakamoto Consensus

Implaments a new way to resovle disagreements between the adoption of two chains of the same height.

- net_processing.cppy - the protocol needed to be altered to accept updates from a competiting chain that is of the same height as it may have a higher fitness score.
- uint256.h - wrote an addition routine to allow for the in-place addition of two 256 bit numbers.
- validation.cpp Added the floating-point nakamoto fitness resolution protocol.

56803c27f1

Floating-Point Nakamoto Consensus

Implaments a new way to resovle disagreements between the adoption of two chains of the same height.

- net_processing.cppy - the protocol needed to be altered to accept updates from a competiting chain that is of the same height as it may have a higher fitness score.
- uint256.h - wrote an addition routine to allow for the in-place addition of two 256 bit numbers.
- validation.cpp Added the floating-point nakamoto fitness resolution protocol.

5bf7261c9a

Merge branch 'master' of https://github.com/in-st/bitcoin 05578ac859

tryphe commented at 3:44 AM on August 5, 2020: contributor

It's not clear to me why this is desirable. If two chains of equal work exist (correct me if I'm wrong, but the chance for this happening is pretty much zero), why not just wait until the next block to resolve the conflict? And if there are two chains of equal cumulative work, why choose one?

DrahtBot added the label P2P on Aug 5, 2020

DrahtBot added the label Validation on Aug 5, 2020

TheRook commented at 3:57 AM on August 5, 2020: none

I have a formal paper written up but I don't want to make it public, perhaps contact ZmnSCPxj directly for a copy. In short, this is extremely desirable as it makes it virtually impossible for a competing chain to be longer than a single block. But more importantly, this is a patch for an exploit - which is why the paper is private.

sipa commented at 4:07 AM on August 5, 2020: member

If there is an epxloitable condition that warrants a change like this, please contact security@bitcoincore.org (see https://bitcoincore.org/en/contact/ for PGP keys).

Ignoring that, this sounds like it's effectively a consensus change, which means it needs discussion on the mailinglist, and widespread support first before we can consider merging things here.

fanquake closed this on Aug 5, 2020

luke-jr commented at 6:09 AM on August 5, 2020: member

This change is probably exploitable: if nodes will reorg from one height to another deterministically rather than first-seen, there is less incentive for miners to update to the most recent block, and even perhaps in some cases (such as the most recent block being poorly "fit") try to intentionally replace it.

I'm not sure it can really be considered a consensus change, however... First-seen is non-deterministic and therefore must be outside consensus. Furthermore, preciousblock isn't considered consensus-modifying and does essentially the same thing.

TheRook commented at 7:11 AM on August 5, 2020: none

A fitness-based re-org can only be between two chains of the same length.

Any exploit that requries an adversary to generate a pow that is 2x more difficult than the current tip means that this patch is working exactly as intended.

On Tue, Aug 4, 2020, 11:09 PM Luke Dashjr notifications@github.com wrote:

This change is probably exploitable: if nodes will reorg from one height to another deterministically rather than first-seen, there is less incentive for miners to update to the most recent block, and even perhaps in some cases (such as the most recent block being poorly "fit") try to intentionally replace it.

I'm not sure it can really be considered a consensus change, however... First-seen is non-deterministic and therefore must be outside consensus. Furthermore, preciousblock isn't considered consensus-modifying and does essentially the same thing.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/bitcoin/bitcoin/pull/19665#issuecomment-669000631, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAD7MN2MIFU5GAXY6ISY2XDR7DZTBANCNFSM4PVAZSZA .

MarcoFalke commented at 7:23 AM on August 5, 2020: member

requries an adversary to generate

It doesn't require the adversary to generate such a pow, when it is expected to happen by chance eventually. Selfish mining attacks can be mounted easier with this patch. I think this is also what @luke-jr said above.

In any case, if this is a Bitcoin Core related exploit, it would be best to contact the security email. #19665 (comment)

TheRook commented at 3:23 PM on August 5, 2020: none

MarcoFalke,

The exact scenario you have described was addressed in my paper which was encrypted and emailed to security@ last night - Peter should have a copy.

Requiring the adversary to spend more resources than required to generate a replacement block than create a new block is intended. This does introduce the possibility of intentionally replacing a single block - but in order to do so the adversarial miner must expend more energy than what is required to simply create a new block. The built-in network incentives come into the defender's advantage.

On Wed, Aug 5, 2020 at 12:23 AM MarcoFalke notifications@github.com wrote:

requries an adversary to generate

It doesn't require the adversary to generate such a pow, when it is expected to happen by chance eventually. Selfish mining attacks can be mounted easier with this patch. I think this is also what @luke-jr https://github.com/luke-jr said above.

In any case, if this is a Bitcoin Core related exploit, it would be best to contact the security email. #19665 (comment) https://github.com/bitcoin/bitcoin/pull/19665#issuecomment-668967888

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/bitcoin/bitcoin/pull/19665#issuecomment-669028334, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAD7MN2XSILCIOS77IIPXGTR7ECGJANCNFSM4PVAZSZA .

TheRook commented at 10:41 PM on September 25, 2020: none

Can this PR be re-opened?

https://github.com/in-st/Floating-Point-Nakamoto-Consensus/blob/master/Floating-Point%20Nakamoto%20Consensus.pdf

sipa commented at 10:45 PM on September 25, 2020: member

Only If there is widespread agreement the consensus protocol should be changed.

mcelrath commented at 12:59 AM on October 9, 2020: none

Hard NACK on this and on reopening it. It simply does not do what is described.

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-October/018243.html

TheRook commented at 6:55 PM on October 9, 2020: none

@sipa @mcelrath This idea is still quite raw, and has changed based on feedback. It is worthwhile to add a consensus-resolution protocol that is good for; the network, the coin, miners and the environment — and progress has been made. Having a consensus for how we form a consensus is delightfully meta. I am advocating for re-balancing of the incentives created by "first seen" and this PR is a step in that direction.

DrahtBot locked this on Feb 15, 2022