Re: [bitcoin-dev] Floating-Point Nakamoto Consensus

From: Mike Brooks <m@ib•tc>
To: bitcoin ml <bitcoin.ml@thomaskerin•io>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Floating-Point Nakamoto Consensus
Date: Fri, 25 Sep 2020 09:04:11 -0700	[thread overview]
Message-ID: <CALFqKjQoe6HGpLe3TSt+XvaiUKS6M3MyAYg=SWUu1Kd9+Mcr4g@mail.gmail.com> (raw)
In-Reply-To: <dbb83152-bca4-9ac6-a7cc-9f39ece7a2e4@thomaskerin.io>

[-- Attachment #1: Type: text/plain, Size: 27800 bytes --]

Hey Thomas,

A fitness value is only additive for the length of the disagreement, and
only used to solve disagreements of the same height.  This isn't as large
of a departure as you are expecting.  For 50,000 blocks of agreement, then
no floating point value is calculated.

All the best,
Mike

On Fri, Sep 25, 2020 at 8:57 AM bitcoin ml via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:

> Hi,
>
> This is a pretty big departure from cumulative POW.
>
> Could you explain to me what you see happening if a node with this patch
> and no history starts to sync, and some random node gives it a block with a
> better fitness test for say height 250,000? No other solution will have a
> better fitness test at that height, so from my understanding its going to
> stop syncing. How about even later - say this proposal is activated at
> block 750,000. At 850,000, someone decides it'd be fun to publish a new
> block 800,000 with a better fitness test. What happens the 50,000 blocks?
>
> I can imagine the miners not being particularly happy about it - their
> previously 50:50 chance (well, sort of, it's based on resources-
> connectivity, validation overheads, etc) their tied block would succeed, vs
> the situation with this change - blocks that are inherently more or less
> valid than others.
>
> I think these days people are more focused on improving defences at the
> networking layer than in the consensus layer - especially when it affects
> mining incentives. I don't see how people will take this seriously -
> especially when you regard how often consensus changes are made to _fix_
> something as opposed to add something new.
>
> Best regards,
>
> Thomas
> On 9/24/20 8:40 PM, Mike Brooks via bitcoin-dev wrote:
>
>   Hey Everyone,
>
>  A lot of work has gone into this paper, and the current revision has been
> well received and there is a lot of excitement on this side to be sharing
> it with you today. There are so few people that truly understand this
> topic, but we are all pulling in the same direction to make Bitcoin better
> and it shows.  It is wildly underrated that future proofing was never
> really a consideration in the initial design - but here we are a decade
> later with amazing solutions like SegWit which gives us a real
> future-proofing framework.  The fact that future-proofing was added to
> Bitcoin with a softfork gives me goosebumps. I'd just like to take the time
> to thank the people who worked on SegWit and it is an appreciation that
> comes up in conversation of how difficult and necessary that process
> was, and this appreciation may not be vocalized to the great people who
> worked on it. The fact that Bitcoin keeps improving and is able to respond
> to new threats is nothing short of amazing - thank you everyone for a great
> project.
>
> This current proposal really has nothing to do with SegWit - but it is an
> update that will make the network a little better for the future, and we
> hope you enjoy the paper.
>
> PDF:
>
> https://github.com/in-st/Floating-Point-Nakamoto-Consensus/blob/master/Floating-Point%20Nakamoto%20Consensus.pdf
>
> Pull Request:
> https://github.com/bitcoin/bitcoin/pull/19665/files
>
> ---
>
>
> Floating-Point Nakamoto Consensus
>
> Abstract — It has been shown that Nakamoto Consensus is very useful in
> the formation of long-term global agreement — and has issues with
> short-term disagreement which can lead to re-organization (“or-org”) of the
> blockchain.  A malicious miner with knowledge of a specific kind of
> denial-of-service (DoS) vulnerability can gain an unfair advantage in the
> current Bitcoin network, and can be used to undermine the security
> guarantees that developers rely upon.  Floating-Point Nakamoto consensu
> makes it more expensive to replace an already mined block vs. creation of a
> new block, and by resolving ambiguity of competition solutions it helps
> achieve global consumers more quickly.  A floating-point fitness test
> strongly incentivises the correct network behavior, and prevents
> disagreement from ever forming in the first place.
> Introduction
>
> The Bitcoin protocol was created to provide a decentralized consensus on a
> fully distributed p2p network.  A problem arises when more than one
> proof-of-work is presented as the next solution block in the blockchain.
> Two solutions of the same height are seen as authoritative equals which is
> the basis of a growing disagreement. A node will adopt the first solution
> seen, as both solutions propagate across the network a race condition of
> disagreement is formed. This race condition can be controlled by byzentiene
> fault injection commonly referred to as an “eclipsing” attack.  When two
> segments of the network disagree it creates a moment of weakness in which
> less than 51% of the network’s computational resources are required to keep
> the network balanced against itself.
> Nakamoto Consensus
>
> Nakamoto Consensus is the process of proving computational resources in
> order to determine eligibility to participate in the decision making
> process.  If the outcome of an election were based on one node (or
> one-IP-address-one-vote), then representation could be subverted by anyone
> able to allocate many IPs. A consensus is only formed when the prevailing
> decision has the greatest proof-of-work effort invested in it. In order for
> a Nakamoto Consensus to operate, the network must ensure that incentives
> are aligned such that the resources needed to subvert a proof-of-work based
> consensus outweigh the resources gained through its exploitation. In this
> consensus model, the proof-of-work requirements for the creation of the
> next valid solution has the exact same cost as replacing the current
> solution. There is no penalty for dishonesty, and this has worked well in
> practice because the majority of the nodes on the network are honest and
> transparent, which is a substantial barrier for a single dishonest node to
> overcome.
>
> A minimal network peer-to-peer structure is required to support Nakamoto
> Conesus, and for our purposes this is entirely decentralized. Messages are
> broadcast on a best-effort basis, and nodes can leave and rejoin the
> network at will, accepting the longest proof-of-work chain as proof of what
> happened while they were gone.  This design makes no guarantees that the
> peers connected do not misrepresent the network or so called “dishonest
> nodes.” Without a central authority or central view - all peers depend on
> the data provided by neighboring peers - therefore a dishonest node can
> continue until a peer is able to make contact an honest node.
> Security
>
> In this threat model let us assume a malicious miner possesses knowledge
> of an unpatched DoS vulnerability (“0-day”) which will strictly prevent
> honest nodes from communicating to new members of the network - a so-called
> “total eclipse.”  The kind of DoS vulnerability needed to conduct an
> eclipse does not need to consume all CPU or computaitly ability of target
> nodes - but rather prevent target nodes from forming new connections that
> would undermine the eclipsing effect. These kinds of DoS vulnerabilities
> are somewhat less substional than actually knocking a powerful-mining node
> offline.  This class of attacks are valuable to an adversary because in
> order for an honest node to prove that a dishonest node is lying - they
> would need to form a connection to a segment of the network that isn’t
> entirely suppressed. Let us assume a defense-in-depth strategy and plan on
> this kind of failure.
>
> Let us now consider that the C++ Bitcoind has a finite number of worker
> threads and a finite number of connections that can be serviced by these
> workers.  When a rude client occupies all connections - then a pidgin-hole
> principle comes into play. If a network's maximum capacity for connection
> handlers ‘k’, is the sum of all available worker threads for all nodes in
> the network, establishing ‘k+1’ connections by the pidgin-hole principle
> will prevent any new connections from being formed by honest nodes -
> thereby creating a perfect eclipse for any new miners joining the network
> would only be able to form connections with dishonest nodes.
>
> Now let’s assume a dishonest node is modified in two ways - it increases
> the maximum connection handles to hundreds of thousands instead of the
> current value which is about 10. Then this node is modified to ignore any
> solution blocks found by honest nodes - thus forcing the dishonest side of
> the network to keep searching for a competitive-solution to split the
> network in two sides that disagree about which tip of the chain to use.
> Any new solution propagates through nodes one hop at a time. This
> propagation can be predicted and shaped by dishonest non-voting nodes that
> are being used to pass messages for honest nodes.
>
> At this point an attacker can expedite the transmission of one solution,
> while slowing another. If ever a competing proof-of-work is broadcasted to
> the network, the adversary will use their network influence to split
> knowledge of the proof-of-work as close to ½ as possible. If the network
> eclipse is perfect then an adversary can leverage an eigen-vector of
> computational effort to keep the disagreement in balance for as long as it
> is needed. No mechanism is stopping the attacker from adding additional
> computation resources or adjusting the eclipsing effect to make sure the
> system is in balance.   As long as two sides of the network are perfectly
> in disagreement and generating new blocks - the attacker has intentionally
> created a hard-fork against the will of the network architects and
> operators. The disagreement needs to be kept open until the adversary’s
> transactions have been validated on the honest chain - at which point the
> attacker will add more nodes to the dishonest chain to make sure it is the
> ultimate winner - thus replacing out the honest chain with the one
> generated by dishonest miners.
>
> This attack is convenient from the adversary’s perspective,  Bitcoin being
> a broadcast network advertises the IP addresses of all active nodes - and
> Shodan and the internet scanning project can find all passive nodes
> responding on TCP 8333.  This should illuminate all honest nodes on the
> network, and even honest nodes that are trying to obscure themselves by not
> announcing their presence.  This means that the attacker doesn’t need to
> know exactly which node is used by a targeted exchange - if the attacker
> has subdued all nodes then the targeted exchange must be operating a node
> within this set of targeted honest nodes.
>
> During a split in the blockchain, each side of the network will honor a
> separate merkel-tree formation and therefore a separate ledger of
> transactions. An adversary will then broadcast currency deposits to public
> exchanges, but only on the weaker side, leaving the stronger side with no
> transaction from the adversary. Any exchange that confirms one of these
> deposits is relying upon nodes that have been entirely eclipsed so that
> they cannot see the competing chain - at this point anyone looking to
> confirm a transaction is vulnerable to a double-spend. With this currency
> deposited on a chain that will become ephemeral, the attacker can wire out
> the account balance on a different blockchain - such as Tether which is an
> erc20 token on the Ethereum network which would be unaffected by this
> attack.  When the weaker chain collapses, the transaction that the exchange
> acted upon is no longer codified in Bitcoin blockchain's global ledger, and
> will be replaced with a version of the that did not contain these deposits.
>
> Nakamoto Consensus holds no guarantees that it’s process is
> deterministic.  In the short term, we can observe that the Nakamoto
> Consensus is empirically non-deterministic which is evident by
> re-organizations (re-org) as a method of resolving disagreements within the
> network.   During a reorganization a blockchain network is at its weakest
> point, and a 51% attack to take the network becomes unnecessary. An
> adversary who can eclipse honest hosts on the network can use this as a
> means of byzantine fault-injection to disrupt the normal flow of messages
> on the network which creates disagreement between miners.
>
> DeFi (Decentralized Finance) and smart-contract obligations depend on
> network stability and determinism.  Failure to pay contracts, such as what
> happened on “black thursday” resulted in secured loans accidentally falling
> into redemption.  The transactions used by a smart contract are intended to
> be completed quickly and the outcome is irreversible.  However, if the
> blockchain network has split then a contract may fire and have it’s
> side-effects execute only to have the transaction on the ledger to be
> replaced.  Another example is that a hard-fork might cause the payer of a
> smart contract to default - as the transaction that they broadcasted ended
> up being on the weaker chain that lost. Some smart contracts, such as
> collateral backed loans have a redemption clause which would force the
> borrower on the loan to lose their deposit entirely.
>
> With two sides of the network balanced against each other - an attacker
> has split the blockchain and this hard-fork can last for as long as the
> attacker is able to exert the computational power to ensure that
> proof-of-work blocks are regularly found on both sides of the network.  The
> amount of resources needed to balance the network against itself is far
> less than a 51% attack - thereby undermining the security guarantees needed
> for a decentralized untrusted payment network to function.  An adversary
> with a sufficiently large network of dishonest bots could use this to take
> a tally of which miners are participating in which side of the network
> split. This will create an attacker-controlled hard fork of the network
> with two mutually exclusive merkle trees. Whereby the duration of this
> split is arbitrary, and the decision in which chain to collapse is up to
> the individual with the most IP address, not the most computation.
>
> In Satoshi Nakamoto’s original paper it was stated that the electorate
> should be represented by computational effort in the form of a
> proof-of-work, and only these nodes can participate in the consues
> process.  However, the electorate can be misled by non-voting nodes which
> can reshape the network to benefit an individual adversary.
> Chain Fitness
>
> Any solution to byzantine fault-injection or the intentional formation of
> disagreements must be fully decentralized. A blockchain is allowed to split
> because there is ambiguity in the Nakamoto proof-of-work, which creates the
> environment for a race-condition to form. To resolve this, Floating-Point
> Nakamoto Consensus makes it increasingly more expensive to replace the
> current winning block. This added cost comes from a method of disagreement
> resolution where not every solution block is the same value, and a more-fit
> solution is always chosen over a weaker solution. Any adversary attempting
> to have a weaker chain to win out would have to overcome a kind of
> relay-race, whereby the winning team’s strength is carried forward and the
> loser will have to work harder and harder to maintain the disagreement.  In
> most cases Floating-Point Nakamoto Consensus will prevent a re-org
> blockchain from ever going past a single block thereby expediting the
> formation of a global consensus.  Floating-Point Nakamoto Consensus cements
> 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 Floating-Point Nakamoto Consensus is that all nodes in
> the network should continue to conduct traditional Nakamoto Consensus and
> the formation of new blocks is dictated by the same zero-prefix
> proof-of-work requirements.  If at any point there are two solution blocks
> advertised for the same height - then a floating-point fitness value is
> calculated and the solution with the higher fitness value is the winner
> which is then propagated to all neighbors. Any time two solutions are
> advertised then a re-org is inevitable and 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 of a block that would be discarded.  To make sure
> that incentives are aligned, any zero-prefix proof of work could be the
> next solution, but now in order to replace the current winning solution an
> adversary would need a zero-prefix block that is also more fit that the
> current solution - which is much more computationally expensive to produce.
>
> Any changes to the current tip of the blockchain must be avoided as much
> as possible. To avoid thrashing between two or more competitive solutions,
> each replacement can only be done if it is more fit, thereby proving that
> it has an increased expense.  If at any point two solutions of the same
> height are found it means that eventually some node will have to replace
> their tip - and it is better to have it done as quickly as possible so that
> consensus is maintained.
>
> In order to have a purely decentralized solution, this kind of agreement
> must be empirically derived from the existing proof-of-work so that it is
> universally and identically verifiable by all nodes on the network.
> Additionally, this fitness-test evaluation needs to ensure that no two
> competing solutions can be numerically equivalent.
>
> Let us suppose that two or more valid solutions will be proposed for the
> same block.  To weigh the value of a given solution, let's consider a
> solution for block 639254, in which the following hash was proposed:
>
>     00000000000000000008e33faa94d30cc73aa4fd819e58ce55970e7db82e10f8
>
> There are 19 zeros, and the remaining hash in base 16 starts with 9e3 and
> ends with f8.  This can value can be represented in floating point as:
>
>     19.847052573336114130069196154809453027792121882588614904
>
> To simplify further lets give this block a single whole number to
> represent one complete solution, and use a rounded floating-point value to
> represent some fraction of additional work exerted by the miner.
>
>    1.847
>
> Now let us suppose that a few minutes later another solution is advertised
> to the network shown in base16 below:
>
>     000000000000000000028285ed9bd2c774136af8e8b90ca1bbb0caa36544fbc2
>
> The solution above also has 19 prefixed zeros, and is being broadcast for
> the same blockheight value of 639254 - and a fitness score of 1.282.  With
> Nakamoto Consensus both of these solutions would be equivalent and a given
> node would adopt the one that it received first.  In Floating-Post Nakamoto
> Consensus, we compare the fitness scores and keep the highest.  In this
> case no matter what happens - some nodes will have to change their tip and
> a fitness test makes sure this happens immediately.
>
> With both solutions circulating in the network - any node who has received
> both proof-of-works should know 1.847 is the current highest value, and
> shouldn’t need to validate any lower-valued solution.  In fact this fitness
> value has a high degree of confidence that it won’t be unseated by a larger
> value - being able to produce a proof-of-work with 19 0’s and a decimal
> component greater than 0.847 is non-trivial.  As time passes any nodes that
> received a proof-of-work with a value 1.204 - their view of the network
> should erode as these nodes adopt the 1.847 version of the blockchain.
>
> All nodes are incentivized to support the solution with the highest
> fitness value - irregardless of which order these proof-of-work were
> validated. Miners are incentivized to support the dominant chain which
> helps preserve the global consensus.
>
> Let us assume that the underlying cryptographic hash-function used to
> generate a proof-of-work is an ideal primitive, and therefore a node cannot
> force the outcome of the non-zero component of their proof-of-work.
> Additionally if we assume an ideal cipher then the fitness of all possible
> solutions is gaussian-random. With these assumptions then on average a new
> solution would split the keyspace of remaining solutions in half.  Given
> that the work needed to form a  new block remains a constant at 19 blocks
> for this period - it is cheaper to produce a N+1 block that has any
> floating point value as this is guaranteed to be adopted by all nodes if it
> is the first solution.  To leverage a chain replacement on nodes conducting
> Floating-Point Nakamoto Consensus a malicious miner would have to expend
> significantly more resources.
>
> Each successive n+1 solution variant of the same block-height must
> therefore on average consume half of the remaining finite keyspace.
> Resulting in a the n+1 value not only needed to overcome the 19 zero
> prefix, but also the non-zero fitness test.   It is possible for an
> adversary to waste their time making a 19 where n+1 was not greater, at
> which point the entire network will have had a chance to move on with the
> next solution.  With inductive reasoning, we can see that a demissiniong
> keyspace increases the amount of work needed to find a solution that also
> meets this new criteria.
>
> Now let us assume a heavily-fragmented network where some nodes have
> gotten one or both of the solutions.  In the case of nodes that received
> the proof-of-work solution with a fitness of 1.847, they will be happily
> mining on this version of the blockchain. The nodes that have gotten both
> 1.847 and .240 will still be mining for the 1.847 domainite version,
> ensuring a dominant chain.  However, we must assume some parts of the
> network never got the message about 1.847 proof of work, and instead
> continued to mine using a value of 1.240 as the previous block.   Now,
> let’s say this group of isolated miners manages to present a new
> conflicting proof-of-work solution for 639255:
>
>      000000000000000000058d8ebeb076584bb5853c80111bc06b5ada35463091a6
>
> The above base16 block has a fitness score of 1.532  The fitness value for
> the previous block 639254 is added together:
>
>      2.772 = 1.240 + 1.532
>
> In this specific case, no other solution has been broadcast for block
> height 639255 - putting the weaker branch in the lead.  If the weaker
> branch is sufficiently lucky, and finds a solution before the dominant
> branch then this solution will have a higher overall fitness score, and
> this solution will propagate as it has the higher value.  This is also
> important for transactions on the network as they benefit from using the
> most recently formed block - which will have the highest local fitness
> score at the time of its discovery.  At this junction, the weaker branch
> has an opportunity to prevail enterally thus ending the split.
>
> Now let us return to the DoS threat model and explore the worst-case
> scenario created by byzantine fault injection. Let us assume that both the
> weaker group and the dominant group have produced competing proof-of-work
> solutions for blocks 639254 and 639255 respectively.  Let’s assume that the
> dominant group that went with the 1.847 fitness score - also produces a
> solution with a similar fitness value and advertises the following solution
> to the network:
>
> 0000000000000000000455207e375bf1dac0d483a7442239f1ef2c70d050c113
>
> 19.414973649464574877549198290879237036867705594421756179
>
> or
>
> 3.262 = 1.847 + 1.415
>
> A total of 3.262 is still dominant over the lesser 2.772 - in order to
> overcome this - the 2nd winning block needs to make up for all of the
> losses in the previous block.  In this scenario, in order for the weaker
> chain to supplant the dominant chain it must overcome a -0.49 point
> deficit. In traditional Nakamoto Consensus the nodes would see both forks
> as authoritative equals which creates a divide in mining capacity while two
> groups of miners search for the next block.  In Floating-Point Nakamoto
> Consensus any nodes receiving both forks, would prefer to mine on the chain
> with an overall fitness score of +3.262 - making it even harder for the
> weaker chain to find miners to compete in any future disagreement, thereby
> eroding support for the weaker chain. This kind of comparison requires an
> empirical method for determining fitness by miners following the same same
> system of rules will insure a self-fulfilled outcome.  After all nodes
> adopt the dominant chain normal Nakamoto Consuess can resume without having
> to take into consideration block fitness. This example shows how
> disagreement can be resolved more quickly if the network has a mechanism to
> resolve ambiguity and de-incentivise dissent.
> Soft Fork
>
> Blockchain networks that would like to improve the consensus generation
> method by adding a fitness test should be able to do so using a “Soft Fork”
> otherwise known as a compatible software update.  By contrast a “Hard-Fork”
> is a separate incompatible network that does not form the same consensus.
> Floating-Point Nakamoto Consensus can be implemented as a soft-fork because
> both patched, and non-patched nodes can co-exist and non-patched nodes will
> benefit from a kind of herd immunity in overall network stability.  This is
> because once a small number of nodes start following the same rules then
> they will become the deciding factor in which chain is chosen.  Clients
> that are using only traditional Nakamoto Consensus will still agree with
> new clients over the total chain length. Miners that adopt the new strategy
> early, will be less likely to lose out on mining invalid solutions.
> Conclusion
>
> Floating-Point Nakamoto consensus allows the network to form a consensus
> more quickly by avoiding ambiguity allowing for determinism to take hold.
> Bitcoin has become an essential utility, and attacks against our networks
> must be avoided and adapting, patching and protecting the network is a
> constant effort. An organized attack against a cryptocurrency network will
> undermine the guarantees that blockchain developers are depending on.
>
> Any blockchain using Nakamoto Consensus can be modified to use a fitness
> constraint such as the one used by a Floating-Point Nakamoto Consensus.  An
> example implementation has been written and submitted as a PR to the
> bitcoin core which is free to be adapted by other networks.
>
>
>
>
>
> A complete implementation of Floating-Point Nakamoto consensus is in the
> following pull request:
>
> https://github.com/bitcoin/bitcoin/pull/19665/files
>
> Paper:
>
> https://github.com/in-st/Floating-Point-Nakamoto-Consensus
>
> https://in.st.capital
>
>
> _______________________________________________
> bitcoin-dev mailing listbitcoin-dev@lists•linuxfoundation.orghttps://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 47320 bytes --]