Mike Brooks [ARCHIVE] / is on Nostr

📅 Original date posted:2020-10-09
📝 Original message:James,
FPNC and NC will always select the highest-work chain, I am suggesting that
by adding more bits of precision we avoid confusion.
Part 2 -> Using a genetic algorithm that passes fitness with heredity to
resolve disagreements has never been introduced to this mailing list. This
hard-nack is null and void.
Best Regards,
Michael
On Tue, Sep 29, 2020 at 12:30 AM LORD HIS EXCELLENCY JAMES HRMH via
bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
> Good Afternoon,
>
> Re: [bitcoin-dev] Floating-Point Nakamoto Consensus
>
> I note that the discussion thread for this proposal has previously
> received HARD_NAK
>
> I note in the whitepaper the following basic introduction of need:
> >As a result anode will simply adopt the first solution seen, creating a
> kind of race condition.
>
> The said race condition, it is not noted, is 'self-resolving' with the
> network adopting the longest chain with the highest proof of work as any
> contentious tip is built on. This is the proper reason for waiting for two
> confirmations for a transaction as a minimum proof of its inclusion in the
> blockchain (without fraud), and for waiting for six confirmations before
> considering that a transaction is 'final'.
>
> I take it that your work is intended to allow the network to decide
> immediately without waiting for a chain to be further extended, in that
> case, the solution should be as noted elsewhere to accept the higher proof
> of work with the greater precision proof. When comparing two competing
> blocks there is an indirect reference to a higher proof of work due to the
> greater precision in the block hash, although the answer could have been
> arrived with fewer attempts. As it is, the total proof of work is not
> directly calculated but is evaluated as the chain with more blocks being
> the chain with more proof-of-work, whereas in the cases two blocks are
> received as alternates extending the same chain tip there is currently no
> method of comparison to determine which of the blocks, and the correct tip
> is not chosen without further proof-of-work to extend a tip. Resolving this
> reduces the network expense of reorganisation in ordinary conditions but in
> the case of a network-split resolves nothing.
>
> KING JAMES HRMH
> Great British Empire
>
> Regards,
> The Australian
> LORD HIS EXCELLENCY JAMES HRMH (& HMRH)
> of Hougun Manor & Glencoe & British Empire
> MR. Damian A. James Williamson
> Wills
>
> et al.
>
>
> Willtech
> www.willtech.com.au
> www.go-overt.com
> and other projects
>
> earn.com/willtech
> linkedin.com/in/damianwilliamson
>
>
> m. 0487135719
> f. 61261470192
>
>
> ----
> ------------------------------
> *From:* bitcoin-dev <bitcoin-dev-bounces at lists.linuxfoundation.org> on
> behalf of Mike Brooks via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org>
> *Sent:* Friday, 25 September 2020 5:40 AM
> *To:* bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org>
> *Subject:* [bitcoin-dev] Floating-Point Nakamoto Consensus
>
> 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 list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20201009/634f09de/attachment-0001.html>

📅 Original date posted:2020-09-25
📝 Original message: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 at 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 at lists.linuxfoundation.orghttps://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200925/cf4f40e6/attachment-0001.html>