[bitcoin-dev] Floating-Point Nakamoto Consensus

[bitcoin-dev] Floating-Point Nakamoto Consensus

[Mike Brooks]

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

  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

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

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

[bitcoin ml]

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

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 <https://in.st.capital/>
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

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

[Mike Brooks]

[-- 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 --]

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

[Jeremy]

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

If I understand correctly, this is purely a policy level decision to accept
first-seen or a secondary deterministic test, but the most-work chain is
still always better than a "more fit" but less work chain.

In any case, I'm skeptical of the properties of this change. First-seen has
a nice property that once you receive a block, you have a substantially
reduced incentive to try to orphan it because the rest of the network is
going to work on building on that block. With fitness, I have a 50% shot if
I mine a block of mine being accepted, so floating point would have the
effect of destabilizing consensus convergence at the tip.

I could see using a fitness rule like this be useful if you see both blocks
within some very small window, e.g., 10 seconds, as it could decrease
partition risk if it's likely the orphan was mined within close range of
the other.

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

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

[Mike Brooks]

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

Hey Jeremy,

Thanks for your response, but I think you misunderstood a crucial feature
-  with a fitness test you have a 100% chance of a new block from being
accepted, and only a 50% or less chance for replacing a block which has
already been mined.   This is all about keeping incentives moving forward.

"First seen" was easy to implement, but has a few undesirable attributes.
 One of the big problems is that I don't think it is fair to allow for a
miner to ignore a solution block and still have an unpenalized opportunity
to replace it - this is very much possible with the first scene and an
eclipse of the network to dictate which solution will be seen first by
affected nodes.   Making it more expensive to replace hard work instead of
contributing to new work is a useful feature for stability.  Eclipsing
allows the attacker to make sure that one solution will be seen before
another - but this race condition is resolved uniformly if we have a
fitness test.

But let's dig into this topic more.  What would actually lead to
"thrashing" or unnecessary replacement of the tip?  A malicious miner who
has observed the creation of a new block and intends to replace it - would
have to exceed the work needed to generate a new block - and crucially will
have less time to perform this task than the entire network as whole.
Fitness introduces a neat boundary, whereby it is always cheaper to make a
new block than replace the existing block - which means it would take at
least a 51% attack to overcome this attribute.   That being said, without
this feature - less than 51% is needed when you have miners that will work
for you for free.

-Mike



On Fri, Sep 25, 2020 at 9:33 AM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> If I understand correctly, this is purely a policy level decision to
> accept first-seen or a secondary deterministic test, but the most-work
> chain is still always better than a "more fit" but less work chain.
>
> In any case, I'm skeptical of the properties of this change. First-seen
> has a nice property that once you receive a block, you have a substantially
> reduced incentive to try to orphan it because the rest of the network is
> going to work on building on that block. With fitness, I have a 50% shot if
> I mine a block of mine being accepted, so floating point would have the
> effect of destabilizing consensus convergence at the tip.
>
> I could see using a fitness rule like this be useful if you see both
> blocks within some very small window, e.g., 10 seconds, as it could
> decrease partition risk if it's likely the orphan was mined within close
> range of the other.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

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

[David A. Harding]

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

On Fri, Sep 25, 2020 at 10:35:36AM -0700, Mike Brooks via bitcoin-dev wrote:
> -  with a fitness test you have a 100% chance of a new block from being
> accepted, and only a 50% or less chance for replacing a block which has
> already been mined.   This is all about keeping incentives moving forward.

FYI, I think this topic has been discussed on the list before (in
response to the selfish mining paper).  See this proposal:

  https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-November/003583.html

Of its responses, I thought these two stood out in particular:

  https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-November/003584.html
  https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-November/003588.html

I think there may be some related contemporary discussion from
BitcoinTalk as well; here's a post that's not directly related to the
idea of using hash values but which does describe some of the challenges
in replacing first seen as the tip disambiguation method.  There may be
other useful posts in that thread---I didn't take the time to skim all
11 pages.

  https://bitcointalk.org/index.php?topic=324413.msg3476697#msg3476697

-Dave

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

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

[Mike Brooks]

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

Very interesting find - there are similarities here, but this is hardly
identical.

>
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-November/003584.html

I am largely in agreement with Quinn (from 2013) - simply using the lowest
block value was a bad idea because the value cannot be carried forward to
resolve disagreements greater than N+1. Simply picking a lower value in big
edian is a nieve approach to disagreement resolution that would result in
trashing. I thought of this before writing the paper, and then thought
better of it.

The zero-prefix component can be thought of driving a lower numeric value
in big-edian which is the verifiable proof-of-work we know to expect.  The
remaining value could be minimized or maximized in any edeness - so long as
it is consistent - but more importantly the winner needs to be ahead of the
race for the next block, and we need to add a mechanism by which to make it
more expencive to replace an existing block than producing a new block -
all three components solve the issue at hand, cutting one of these out
isn't a complete answer.

As to Quinn's point - I don't think it should be random.  The miner's
choice of picking the most fit soluton means the any future children of the
winning solution will also be further ahead.  "Survival of the fittest"
block -  The winners have the home field advantage of being in the lead for
the next round - and any miners that disagree are fools to start from a
starting line that is further behind.

The difference between the 2013 post and FPNC is the alignment of
incentives.

-Mike


On Sat, Sep 26, 2020, 3:12 AM David A. Harding <dave@dtrt.org> wrote:

> On Fri, Sep 25, 2020 at 10:35:36AM -0700, Mike Brooks via bitcoin-dev
> wrote:
> > -  with a fitness test you have a 100% chance of a new block from being
> > accepted, and only a 50% or less chance for replacing a block which has
> > already been mined.   This is all about keeping incentives moving
> forward.
>
> FYI, I think this topic has been discussed on the list before (in
> response to the selfish mining paper).  See this proposal:
>
>
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-November/003583.html
>
> Of its responses, I thought these two stood out in particular:
>
>
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-November/003584.html
>
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-November/003588.html
>
> I think there may be some related contemporary discussion from
> BitcoinTalk as well; here's a post that's not directly related to the
> idea of using hash values but which does describe some of the challenges
> in replacing first seen as the tip disambiguation method.  There may be
> other useful posts in that thread---I didn't take the time to skim all
> 11 pages.
>
>   https://bitcointalk.org/index.php?topic=324413.msg3476697#msg3476697
>
> -Dave
>

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

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

[Franck Royer]

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

On Fri, 25 Sep 2020 at 22:09, Mike Brooks via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
[snip]

> 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.
>

Hi Mike,

Any reason why you decided to consider the higher value the "fittest" one
instead of keeping in line with the difficulty algorithm where smallest
values, prefixed with more zeroes, are considered more valuable/difficult?

Also, can you elaborate if anything special would happen if the competitive
chains were created around a difficulty adjustment?

Cheers, Franck

[snip]

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

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

[Mike Brooks]

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

Hey Frank,

Firstly, I must commend you on two very good questions.

The reason why I chose to maximize the value is because I approached this
as an optimization problem to be solved with a genetic algorithm, and it
fit with my internal model of a kind of relay race that moves forward
faster. When confronted with the paradox of one side of the solution being
minimized and the other being maximized I thought to myself that a paradox
leading to determinism was beautiful... But it doesn't have to be this way.

Part 2 of your question - what about the inevitable march of difficulty?
And here is where how we quantify fitness starts to matter.  Your right to
point this out condition, maximizing the non-zero value means that re-org
during an epoch won't optimize for having a trailing zero, which is a
conflict that I see now must be avoided.

The solution is to always choose the smallest, and the summation of all
contestant chains must also be minimized. This approach would then be
compatible with an Epoch - so much so that it would not impeed the use of a
continuous difficulty function that pegs a solution at a range of non-zero
values which would avoid a discrete cliff by requiring a whole extra zero.
We need not be a victim of an early implementation - a continuous
difficulty function would add stability to the network and this is worth
unlocking.

With added determinism and a continuous epoch, the network will be a lot
more stable.  At this point very little is stopping us from speeding up
block creation times. PoS networks are proving that conformations can be a
minute or less - why not allow for a block formation time that is 6 or 12
times faster than the current target and have 1/6th (or 1/12th) of the
subsidy to keep an identical inflation target.

… The really interesting part is the doors that this patch opens. Bitcoin
is the best network, we have the most miners and we as developers have the
opportunity to build an even better system - all with incremental
soft-forks - which is so exciting.

What I am proposing is a patch that is ~100 lines of code and is fully
compatible with the current Bitcoin network - because I am running a node
with my changes on the network, and the more miners who adopt my patch the
more lucky we will become.

Thank you everyone,

Mike


On Mon, Sep 28, 2020, 7:18 PM Franck Royer via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> On Fri, 25 Sep 2020 at 22:09, Mike Brooks via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> [snip]
>
>> 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.
>>
>
> Hi Mike,
>
> Any reason why you decided to consider the higher value the "fittest" one
> instead of keeping in line with the difficulty algorithm where smallest
> values, prefixed with more zeroes, are considered more valuable/difficult?
>
> Also, can you elaborate if anything special would happen if the
> competitive chains were created around a difficulty adjustment?
>
> Cheers, Franck
>
> [snip]
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

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

[ZmnSCPxj]

>  At this point very little is stopping us from speeding up block creation times. PoS networks are proving that conformations can be a minute or less - why not allow for a block formation time that is 6 or 12 times faster than the current target and have 1/6th (or 1/12th) of the subsidy to keep an identical inflation target.

What?

That is surprising information to me.

My understanding is that speeding up block creation times is highly risky due to increasing the tendency to "race" in mining.

The average time to propagate to all miners should be negligible to the average inter-block time.
Efforts like compact blocks and FIBRE already work at the very edges of our capability to keep the propagation time negligible.

Indeed, looking forward, part of my plans for Earth-based civilization involves sending out hapless humans into space and forcing them to survive there, thus the inter-block time may need to be *increased* in consideration of interplanetary communications times, otherwise Bitcoin would dangerously centralize around Earth, potentially leading to the Universal Century and awesome giant robot battles.

(Hmmm, on the one hand, centralizing around Earth is dangerous, on the other hand, giant robots, hmmm)

"PoS" networks mean nothing, as most of them are not global in the scale that Bitcoin is, and all of them have a very different block discovery model from proof-of-work.
In particular, I believe there is no "racing" involved in most PoS schemes in practice.

>
> … The really interesting part is the doors that this patch opens. Bitcoin is the best network, we have the most miners and we as developers have the opportunity to build an even better system - all with incremental soft-forks - which is so exciting.

Changing inter-block times is not possible as a softfork, unless you are planning to (ab)use the timewarp bug, which I believe was proposed by maaku7 before.
My understanding is that the preferred approach would be to close the timewarp bug, in which case increasing the block rate would not be doable as a softfork anymore.

Regards,
ZmnSCPxj

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

[Mike Brooks]

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

ZmnSCPxj,

No, it would be better to use parachains for Mars.

-Mike Brooks

On Tue, Sep 29, 2020, 11:31 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

>
> >  At this point very little is stopping us from speeding up block
> creation times. PoS networks are proving that conformations can be a minute
> or less - why not allow for a block formation time that is 6 or 12 times
> faster than the current target and have 1/6th (or 1/12th) of the subsidy to
> keep an identical inflation target.
>
> What?
>
> That is surprising information to me.
>
> My understanding is that speeding up block creation times is highly risky
> due to increasing the tendency to "race" in mining.
>
> The average time to propagate to all miners should be negligible to the
> average inter-block time.
> Efforts like compact blocks and FIBRE already work at the very edges of
> our capability to keep the propagation time negligible.
>
> Indeed, looking forward, part of my plans for Earth-based civilization
> involves sending out hapless humans into space and forcing them to survive
> there, thus the inter-block time may need to be *increased* in
> consideration of interplanetary communications times, otherwise Bitcoin
> would dangerously centralize around Earth, potentially leading to the
> Universal Century and awesome giant robot battles.
>
> (Hmmm, on the one hand, centralizing around Earth is dangerous, on the
> other hand, giant robots, hmmm)
>
> "PoS" networks mean nothing, as most of them are not global in the scale
> that Bitcoin is, and all of them have a very different block discovery
> model from proof-of-work.
> In particular, I believe there is no "racing" involved in most PoS schemes
> in practice.
>
> >
> > … The really interesting part is the doors that this patch opens.
> Bitcoin is the best network, we have the most miners and we as developers
> have the opportunity to build an even better system - all with incremental
> soft-forks - which is so exciting.
>
> Changing inter-block times is not possible as a softfork, unless you are
> planning to (ab)use the timewarp bug, which I believe was proposed by
> maaku7 before.
> My understanding is that the preferred approach would be to close the
> timewarp bug, in which case increasing the block rate would not be doable
> as a softfork anymore.
>
> Regards,
> ZmnSCPxj
>

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

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

[ZmnSCPxj]

Good morning Mike,

An observation to be made is that the current "first seen" is more incentive-compatible than floating-point Nakamoto consensus.

If a miner A mines a block at height N, then obviously the first block it has seen is that block.

If due to propagation delays on the network, another miner B mines an alternative block (let us say with more fitness score, regardless of the details of the fitness metric you use) at height N, miner A has no incentive to reject its own version of that block and mine on top of the miner B alternative version, even if floating-point Nakamoto consensus is deployed by most nodes.

Even if the rest of the mining network is now mining on top of the miner B version, if miner A chances on another new block at N+1 built on top of its own version of block N, then it would still win both blocks and earn the block subsidy and fees of two blocks.
And since block height, as I understand it, trumps over floating-point Nakamoto consensus, the B version will be reorganized out anyway in that case.
If miner A had switched to mining on top of the miner B block, then if it won another block at height N+1, it would have lost the block subsidy+fees of the lower-scoring miner A block at height N.


Thus, floating-point Nakamoto consensus is not incentive-compatible, so I doubt it would have any kind of adoption.


The problems with stability you mention can be fixed, fairly trivially, by simply waiting for 3 confirmations rather than just 1 confirmation.


In a relativistic universe, information cannot propagate faster than light-speed, and thus there will always be a communications network delay in propagating data.
As I see it, floating-point Nakamoto consensus cannot fix this issue, as it cannot change underlying laws of the universe.

If your goal is "stability" of some kind, then there is still always a possibility that two miners on opposite sides of the Earth will create blocks at the same height outside of the light cones of each other.
In a relativistic universe, this cannot be eliminated unless all miners occupy the same physical location, i.e. have centralized in the same mining hardware.

One of those two blocks created will, with high probability, have a lower score, and thus any nodes in the light cone of the miner of the lower-scored block will still experience a reorg, as they will first see one block, then switch to the higher-scored block when it arrives to them.

Thus, floating-point Nakamoto consensus cannot provide complete stability of the network, still, as the universe we operate in does not have instantaneous information transfer.

A wise designer of automated systems will ***still*** wait for 3 confirmations before doing anything, and by then, the effects of floating-point Nakamoto consensus will be literally a thing of the past.


Regards,
ZmnSCPxj

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

[Mike Brooks]

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

ZmnSCPxj,

The growing tare in growing disagreement continues to divide mining
capacity while the network waits for formation of future blocks - you'll
never get to complete consensus unless three is a way to avoid ambiguity
in disagreement, which you have not addressed.  The topic of my discussion
is an exploitable condition, your three block plan does not add up.

I wrote the exploit before I wrote the paper. It is telling that still no
one here has refenced the threat model, which is the largest section of the
entire 8 page paper.  The security came before the introduction of FPNC
because security fundamentals is what drives the necessity for the solution.

The text you are reading right now was delivered using the mailing list
manager Majordomo2, which I shelled in 2011
<http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2011-0049> and got a
severity metric and an alert in the DHS newsletter. Correct me if I am
wrong, but I bet that just of my exploits has probably popped more shells
<https://www.theregister.com/2010/05/11/phpnuke_infection_purged/> than
everyone on this thread combined.   Cryptography?  Sure, I'll brag about
the time I hacked Square Inc. This is actually my current favorite crypto
exploit — it was the time I used DKIM signature-malleability to conduct a
replay-attack that allowed an adversary to replay another user's
transactions an unlimited number of times. After receiving a normal payment
from another Square user you could empty their account.  This was reported
ethically and it was a mutual joy to work with such a great team.  Now it
is not just impact, but I am also getting the feeling that I have collected
more CVEs, all this is to say that I'm not new to difficult vendors.

To be blunt; some of you on this thread are behaving like a virgin reading
a trashy love novel and failing to see the point — Just because you aren't
excited, doesn't mean that it isn't hot.

The exploit described in this paper was delivered to the Bitcoin-core
security team on August 4 at 9:36 PM PST.  The industry standard of 90 days
gives you until November 2nd. Now clearly, we need more time. However, if
the consensus is a rejection, then there shouldn't be any concerns with a
sensible 90-day disclosure policy.

Regards,
Mike Brooks

On Wed, Sep 30, 2020, 4:45 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Mike,
>
> An observation to be made is that the current "first seen" is more
> incentive-compatible than floating-point Nakamoto consensus.
>
> If a miner A mines a block at height N, then obviously the first block it
> has seen is that block.
>
> If due to propagation delays on the network, another miner B mines an
> alternative block (let us say with more fitness score, regardless of the
> details of the fitness metric you use) at height N, miner A has no
> incentive to reject its own version of that block and mine on top of the
> miner B alternative version, even if floating-point Nakamoto consensus is
> deployed by most nodes.
>
> Even if the rest of the mining network is now mining on top of the miner B
> version, if miner A chances on another new block at N+1 built on top of its
> own version of block N, then it would still win both blocks and earn the
> block subsidy and fees of two blocks.
> And since block height, as I understand it, trumps over floating-point
> Nakamoto consensus, the B version will be reorganized out anyway in that
> case.
> If miner A had switched to mining on top of the miner B block, then if it
> won another block at height N+1, it would have lost the block subsidy+fees
> of the lower-scoring miner A block at height N.
>
>
> Thus, floating-point Nakamoto consensus is not incentive-compatible, so I
> doubt it would have any kind of adoption.
>
>
> The problems with stability you mention can be fixed, fairly trivially, by
> simply waiting for 3 confirmations rather than just 1 confirmation.
>
>
> In a relativistic universe, information cannot propagate faster than
> light-speed, and thus there will always be a communications network delay
> in propagating data.
> As I see it, floating-point Nakamoto consensus cannot fix this issue, as
> it cannot change underlying laws of the universe.
>
> If your goal is "stability" of some kind, then there is still always a
> possibility that two miners on opposite sides of the Earth will create
> blocks at the same height outside of the light cones of each other.
> In a relativistic universe, this cannot be eliminated unless all miners
> occupy the same physical location, i.e. have centralized in the same mining
> hardware.
>
> One of those two blocks created will, with high probability, have a lower
> score, and thus any nodes in the light cone of the miner of the
> lower-scored block will still experience a reorg, as they will first see
> one block, then switch to the higher-scored block when it arrives to them.
>
> Thus, floating-point Nakamoto consensus cannot provide complete stability
> of the network, still, as the universe we operate in does not have
> instantaneous information transfer.
>
> A wise designer of automated systems will ***still*** wait for 3
> confirmations before doing anything, and by then, the effects of
> floating-point Nakamoto consensus will be literally a thing of the past.
>
>
> Regards,
> ZmnSCPxj
>

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

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

[ZmnSCPxj]

Good morning Mike,

> ZmnSCPxj,
>
> The growing tare in growing disagreement continues to divide mining capacity while the network waits for formation of future blocks - you'll never get to complete consensus unless three is a way to avoid ambiguity in disagreement, which you have not addressed.  The topic of my discussion is an exploitable condition, your three block plan does not add up.
>
> I wrote the exploit before I wrote the paper. It is telling that still no one here has refenced the threat model, which is the largest section of the entire 8 page paper.  The security came before the introduction of FPNC because security fundamentals is what drives the necessity for the solution.
>
> The text you are reading right now was delivered using the mailing list manager Majordomo2, which I shelled in 2011 and got a severity metric and an alert in the DHS newsletter. Correct me if I am wrong, but I bet that just of my exploits has probably popped more shells than everyone on this thread combined.   Cryptography?  Sure, I'll brag about the time I hacked Square Inc. This is actually my current favorite crypto exploit — it was the time I used DKIM signature-malleability to conduct a replay-attack that allowed an adversary to replay another user's transactions an unlimited number of times. After receiving a normal payment from another Square user you could empty their account.  This was reported ethically and it was a mutual joy to work with such a great team.  Now it is not just impact, but I am also getting the feeling that I have collected more CVEs, all this is to say that I'm not new to difficult vendors.

Argument screens off authority, thus, even if I have no CVEs under this pseudonym, argument must still be weighted more highly than any authority you may claim.

> To be blunt; some of you on this thread are behaving like a virgin reading a trashy love novel and failing to see the point — Just because you aren't excited, doesn't mean that it isn't hot.
>
> The exploit described in this paper was delivered to the Bitcoin-core security team on August 4 at 9:36 PM PST.  The industry standard of 90 days gives you until November 2nd. Now clearly, we need more time. However, if the consensus is a rejection, then there shouldn't be any concerns with a sensible 90-day disclosure policy. 

I am not a member of this security team, and they may have better information and arguments than I do, in which case, I would defer to them if they are willing to openly discuss it and I find their arguments compelling.

The attack you describe is:

* Not fixable by floating-point Nakamoto consensus, as such a powerful adversary can just as easily prevent propagation of a higher-score block.
* Broken by even a single, manually-created connection between both sides of the chain-split.

Regards,
ZmnSCPxj

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

[ZmnSCPxj]

Good morning Mike,

That is better than implied name-calling and refusing to lay out your argument in detail.
It is still sub-optimal since you are still being insulting by labeling me as "reactionary", when you could have just laid out the exact same argument ***in the first place*** without being unnecessarily inflammatory, but this is significantly better than your previous behavior.

I also strongly prefer to discuss this openly on the mailing list.

> Consider for one moment when the words I have said are correct. Take this moment to see the world from someone else's eyes, and do not be reactionary - just be.
>
> Good.
>
> Consider a threat model, where nodes are unable to form new connections, unless the attacker allows it to happen. The point of threat modeling is not to question if it is possible, but rather to plan on failure because we live in a world where failure happens. Now if you are in a world of limited visibility, and a presented solution has no intrinsic value other than it's length - then you create a node that is gullible. An adversary that controls connections can lie that a new solution was ever even found or selectivally slow the formation of this side of the disagreement, and probably other bad things too.   That sucks, and no one is saying that there is a complete solution to this problem and we are all here to help.
>
> You are absolutely correct - the eclipse effect is never going to be perfect. Which is your point, and it's accurate. Imperfections in the node's visibility allow for a more-fit solution to leak out, and ultimately an identical consensus to form - so long as there is some measure to judge the fitness of two disagreements of identical length.

This is the point at which I think your argument fails.

You are expecting:

* That the attacker is powerful enough to split the network.
* That the attacker is adept enough that it can split the network such that mining hashpower is *exactly* split in half.
* That the universe is in an eldritch state such that at the exact time one side of the chain split finds a block, the other side of the chain split *also* finds a block.

This leads to a metastable state, where both chain splits have diverged and yet are at the exact same block height, and it is true that this state can be maintained indefinitely, with no 100% assurance it will disappear.

Yet this is a [***metastable***](https://en.wikipedia.org/wiki/Metastability) state, as I have mentioned.
Since block discovery is random, inevitably, even if the chain splits are exactly equal in mining hashpower, by random one or the other will win the next block earlier than the other, precisely due to the random nature of mining, and if even a single direct connection were manually made between the chain splits, this would collapse the losing chain split and it will be reorganized out without requiring floating-point Nakamoto.

This is different if the coin had non-random block production, but fortunately in Bitcoin we use proof-of-work.

The confluence of too many things (powerful attacker, exact hashpower split, perfect metastability) is necessary for this state --- and your solution to this state --- to actually ***matter*** in practice.
I estimate that it is far more likely my meat avatar will be destroyed in a hit-and-run accident tomorrow than such a state actually occurring, and I do not bother worrying about my meat avatar being destroyed by a hit-and-run accident tomorrow.

And in Bitcoin, leaving things alone is generally more important, because change is always a risk, as it may introduce *other*, more dangerous attacks that we have not thought of.
I would suggest deferring to those in the security team, as they may have more information than is available to you or me.

>  This minor change of adding a fitness test to solve disagreements is intended to diminish the influence of delayed message passing, and yes there are multiple solutions to this problem, absolutely, but bringing this fact up just derails the important parts of the conversation. 
>
> By the client having limited visibility, then non-voting nodes who simply pass messages *are* given a say in the election process, and that is a problem.   Any attacker can more easily control when a message arrives than a good fitness value.   The old 2013 solution was about naming one side a looser, but that doesn't really help.  It isn't just about calling one solution a winner and a loser. We need to make sure that all descendants of weak solutions are also going to be weak - and that my friend is the basis for a genetic algorithm.
>
> -Michael Brooks 
> (my real name)

Do you think emphasizing that this is your real name ***matters*** compared to actual technical arguments?

>
> On Wed, Sep 30, 2020 at 6:45 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> > Good morning Mike,
> >
> > > You are incorrect. 
> >
> > You make no argument to back this claim, so I will now refuse to engage with you.
> >
> > Regards,
> > ZmnSCPxj
> >
> > >
> > > On Wed, Sep 30, 2020, 6:36 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
> > >
> > > > Good morning Mike,
> > > >
> > > > > ZmnSCPxj,
> > > > >
> > > > > The growing tare in growing disagreement continues to divide mining capacity while the network waits for formation of future blocks - you'll never get to complete consensus unless three is a way to avoid ambiguity in disagreement, which you have not addressed.  The topic of my discussion is an exploitable condition, your three block plan does not add up.
> > > > >
> > > > > I wrote the exploit before I wrote the paper. It is telling that still no one here has refenced the threat model, which is the largest section of the entire 8 page paper.  The security came before the introduction of FPNC because security fundamentals is what drives the necessity for the solution.
> > > > >
> > > > > The text you are reading right now was delivered using the mailing list manager Majordomo2, which I shelled in 2011 and got a severity metric and an alert in the DHS newsletter. Correct me if I am wrong, but I bet that just of my exploits has probably popped more shells than everyone on this thread combined.   Cryptography?  Sure, I'll brag about the time I hacked Square Inc. This is actually my current favorite crypto exploit — it was the time I used DKIM signature-malleability to conduct a replay-attack that allowed an adversary to replay another user's transactions an unlimited number of times. After receiving a normal payment from another Square user you could empty their account.  This was reported ethically and it was a mutual joy to work with such a great team.  Now it is not just impact, but I am also getting the feeling that I have collected more CVEs, all this is to say that I'm not new to difficult vendors.
> > > >
> > > > Argument screens off authority, thus, even if I have no CVEs under this pseudonym, argument must still be weighted more highly than any authority you may claim.
> > > >
> > > > > To be blunt; some of you on this thread are behaving like a virgin reading a trashy love novel and failing to see the point — Just because you aren't excited, doesn't mean that it isn't hot.
> > > > >
> > > > > The exploit described in this paper was delivered to the Bitcoin-core security team on August 4 at 9:36 PM PST.  The industry standard of 90 days gives you until November 2nd. Now clearly, we need more time. However, if the consensus is a rejection, then there shouldn't be any concerns with a sensible 90-day disclosure policy. 
> > > >
> > > > I am not a member of this security team, and they may have better information and arguments than I do, in which case, I would defer to them if they are willing to openly discuss it and I find their arguments compelling.
> > > >
> > > > The attack you describe is:
> > > >
> > > > * Not fixable by floating-point Nakamoto consensus, as such a powerful adversary can just as easily prevent propagation of a higher-score block.
> > > > * Broken by even a single, manually-created connection between both sides of the chain-split.
> > > >
> > > > Regards,
> > > > ZmnSCPxj


Regards,
ZmnSCPxj

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

[Mike Brooks]

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

Good Morning ZmnSCPxj ,

It is cheaper and easier to delay messages, or preempt the spreading of
messages, than it is to produce a better fitness score. Whether it be
through pre-emption or an eclipse - an adversary can influence the size of
both sides of the disagreement, which is a strange feature for any network
to have.  "First seen" is a factor of time, time is an attacker-controlled
element, and this dependence on time creates a race-condition.

My original statement is that it is cheaper to introduce a large number of
non-voting nodes, than it is compeate on mining power -  holds true.  It
doesn't have to be perfect to be a shortcut, an adversary can perform the
same kind of impact as 51% attack - so long as they have a sufficient
number of non-voting nodes.   My language here is referring to the original
paper which makes reference to non-voting nodes and that the electorate
must only be made by computational effort. However, a sufficient number of
non-voting nodes who diligently pass messages, hold the keys to the kingdom.


> This is the point at which I think your argument fails.
>
> You are expecting:
>
> * That the attacker is powerful enough to split the network.
> * That the attacker is adept enough that it can split the network such
> that mining hashpower is *exactly* split in half.
> * That the universe is in an eldritch state such that at the exact time
> one side of the chain split finds a block, the other side of the chain
> split *also* finds a block.
>

* Power is relative, my only comment is that message passing is cheaper
than mining - and that this proposed attack is somewhat better than 51%
mining attack.
* Assuming all adversaries are crippled will not produce a very good threat
model.
* Both sides need to be more or less equal - in practice I don't think this
needs to be exact, and only needs to be held open long enough to trick
validators.  It can and will be unstable, but still exploitable.

This leads to a metastable state, where both chain splits have diverged and
> yet are at the exact same block height, and it is true that this state can
> be maintained indefinitely, with no 100% assurance it will disappear.
>
> Yet this is a [***metastable***](
> https://en.wikipedia.org/wiki/Metastability) state, as I have mentioned.
> Since block discovery is random, inevitably, even if the chain splits are
> exactly equal in mining hashpower, by random one or the other will win the
> next block earlier than the other, precisely due to the random nature of
> mining, and if even a single direct connection were manually made between
> the chain splits, this would collapse the losing chain split and it will be
> reorganized out without requiring floating-point Nakamoto.
>

Mr Nakamoto is assuming normal network conditions - if a majority of
messages are passed by malicious nodes, then this conjecture no longer
holds.  If the majority are dishonest, and non-voting, then the rules
change.


> And in Bitcoin, leaving things alone is generally more important, because
> change is always a risk, as it may introduce *other*, more dangerous
> attacks that we have not thought of.
> I would suggest deferring to those in the security team, as they may have
> more information than is available to you or me.


Offline, we had discussed that there is currently an active
malicious-mining campaign being conducted against the Bitcoin network.
Large mining pools will delay the broadcast of a block that they have
formed in order to have a slight advantage on the formation of the next
block.   Currently, there is an economic incentive for the formation of
disagreement and it is being actively exploited.   FPNC means that blocks
below the 1/2 cut-off are greatly incentivised to be broadcast as quickly
as possible, and blocks above the cutt-off could be held onto a little
longer.  This withholding attack is already taking place because there is
an economic incentive.  Although no proposed solution can prevent it
completely,  seeing that this bad thing would happen 1/2 as often - I see
this as an absolute win.

-Michael

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

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

[Larry Ruane]

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

Hello Mike and others,

I just want to plug the open-source POW network mining simulator I recently
wrote: https://github.com/LarryRuane/minesim

It simulates Bitcoin's existing POW (of course), but probably would be easy
to modify to correspond to variations such as the one being proposed here.
Sometimes simulating an algorithm can lead to insights beyond what's
possible using only abstract reasoning.

Larry Ruane

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

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

[Mike Brooks]

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

Hey Larry,

Great project, and great youtube video.   Expect a PR from me.

... If you actively ping nodes that are running a weaker block, you could
inform them of the new block, there could be a mechanism to
eradicate dissent.

-Mike


On Thu, Oct 1, 2020 at 9:43 AM Larry Ruane <larryruane@gmail.com> wrote:

> Hello Mike and others,
>
> I just want to plug the open-source POW network mining simulator I
> recently wrote: https://github.com/LarryRuane/minesim
>
> It simulates Bitcoin's existing POW (of course), but probably would be
> easy to modify to correspond to variations such as the one being proposed
> here. Sometimes simulating an algorithm can lead to insights beyond what's
> possible using only abstract reasoning.
>
> Larry Ruane
>

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

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

[LORD HIS EXCELLENCY JAMES HRMH]

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

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@lists.linuxfoundation.org> on behalf of Mike Brooks via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Sent: Friday, 25 September 2020 5:40 AM
To: bitcoin-dev <bitcoin-dev@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<https://in.st.capital/>


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

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

[Mike Brooks]

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

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@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@lists.linuxfoundation.org> on
> behalf of Mike Brooks via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org>
> *Sent:* Friday, 25 September 2020 5:40 AM
> *To:* bitcoin-dev <bitcoin-dev@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@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

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

[yanmaani]

What if a miner mines a block that has a very high block reward (i.e. 
confirmed a juicy transaction), while at the same time having a floating 
point fitness very close to the minimum?

For the sake of argument, let's say the block reward is 6.50 (4% more 
than average), the fitness is 1.001, and the orphan rate is 0.3%.

With Nakamoto consensus, the miners would (allegedly) find it in their 
best interest to work on that block, since it was first. It's a problem 
when they don't, but the system basically works right now.

With FPNC, the miners have two equally valid options:
1) Attempt to create a block building on top of that block (reward: 
6.25)
2) Attempt to replace (reward: 6.50)

If they do (1), their probability of success given a matching hash is 
(100 - orphan rate)%, which is very close to 100%.
If they do the second, their probability of success given a hit is (100 
- percentile(1.001)), which also is very close to 100%.

Option 1 has EV of .997 * 1 * 6.25 = 6.25.
Option 2 has EV of (1 - quantile(1.001)) * 1.04 * 6.25, which is surely 
above 6.25. I don't know how to calculate the quantile, but it's 
obvious.

With the block subsidy getting lower and lower as time goes on, the 
probability of this happening goes up.

Don't we want miners to always keep the chain going forward? Your 
proposal incentivizes reorgs.

On 2020-10-10 01:26, Mike Brooks via bitcoin-dev wrote:
> 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@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 [1]
>> www.go-overt.com [2]
>> and other projects
>> 
>> earn.com/willtech [3]
>> linkedin.com/in/damianwilliamson [4]
>> 
>> m. 0487135719
>> f. 61261470192
>> 
>> ----
>> 
>> -------------------------
>> 
>> From: bitcoin-dev <bitcoin-dev-bounces@lists.linuxfoundation.org> on
>> behalf of Mike Brooks via bitcoin-dev
>> <bitcoin-dev@lists.linuxfoundation.org>
>> Sent: Friday, 25 September 2020 5:40 AM
>> To: bitcoin-dev <bitcoin-dev@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:...
>> 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 [5]
>> Paper:
>> 
>> https://github.com/in-st/Floating-Point-Nakamoto-Consensus [6]
>> 
>> https://in.st.capital [7]
>> 
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 
> Links:
> ------
> [1] http://www.willtech.com.au
> [2] http://www.go-overt.com
> [3] http://earn.com/willtech
> [4] http://linkedin.com/in/damianwilliamson
> [5] https://github.com/bitcoin/bitcoin/pull/19665/files
> [6] https://github.com/in-st/Floating-Point-Nakamoto-Consensus
> [7] https://in.st.capital/
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Bob McElrath]

A diversion on statistics:

There are two quantities available for consensus:
    t   target difficulty
    h   block hash where h < t
From these we can form two quantities that might be used in consensus:
    w   work    = log(sum(1/t_i))
    f   fitness = log(sum(1/h_i))   (term used by authors)

(The original authors do not specify mathematically how they obtain their
numbers -- but it doesn't really matter, fundamentally, they want to use the
block hash h instead of t) Bitcoin introduces some constants in the above sums
which I omit for clarity.

The main point here is that the work w is an unbiased statistical estimator for
the number of sha256d computations performed by the network. It is truly a
measurement of "work". The fitness f is a *biased* estimator for exactly the
same thing, and other than introducing statistical bias, provides no additional
information of any value.

The fundamental question of FPNC as I understand it is: should we introduce the
historic block hash h as a consensus-critical parameter?

The answer is a strict no: This quantity f (fitness) is purely random, and does
not in any way favor the "honest" chain, nor can it identify it. Between two
competing chains, the amount of bias on one chain vs. the other is purely random
and does *not* reflect more work done by one side or the other. Nor can it have
any knowledge of things like network splits.

At constant difficulty assuming two competing chains with exactly the same
number of blocks and amount of hashpower, this bias will oscillate, sometimes
favoring one side, sometimes favoring the other. Unlike work, this bias is not
cumulative. Each side will over time converge to having the same amount of bias
from any biased estimator such as f constructed from the hashes h. Just because
one side had an abnormally small hash doesn't mean the other side won't have a
similar abnormally low hash. The expectation value for the amount of bias is
equal on both sides.

Therefore, hard NACK on using h in this way and FPNP. At best it introduces
unecessary randomness into the chain selection process, at worst it proves a new
game to be played by miners. As a consensus critical change, it's also
incredibly risky to push through without some very serious advantage, which this
does not have.

--
Cheers, Bob McElrath

"For every complex problem, there is a solution that is simple, neat, and wrong."
    -- H. L. Mencken 

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

[Mike Brooks]

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

Hey Bob McElarth,

I appreciate this discussion.  The issues with chain thrashing was
explicitly addressed with heredity, I saw this problem, and there is an
elegant solution here.

Sorry that summation process wasn't made clear in the paper, I'll be sure
to go back and improve this.   Here is a full implementation which should
resolve the confusion around the summation of fitness scores:
   https://github.com/bitcoin/bitcoin/pull/19665/files

There is however a minor mistake in the code and in the paper.  We have
changed our position a bit after Franck Royer's post on this thread.   I
think generally optimizing for lower value is a better approach as this
resolves the procession of difficulty when producing blocks across an epoch
divide.  Optimizing for a higher non-zero value would place a non-zero at
the most significant octet, which is avoided by optimizing for a lower
overall numeric value of the solution.  Or, put another way; the lowest
base10 numeric summation of both chains starting at the point of their
disagreement.

The main point here is that the work w is an unbiased statistical estimator
> for
> the number of sha256d computations performed by the network. It is truly a
> measurement of "work". The fitness f is a *biased* estimator for exactly
> the
> same thing, and other than introducing statistical bias, provides no
> additional
> information of any value.
>

FPNC is an extension of the same measure of work, any criticism of
zero-prefix in base16 should also be a criticism of zero-prefix in base2 or
any other base.  A change in base should not affect the bias, and
optimizing for a lower value in big-endian has a continuous difficulty
curve. So long as sha2564 remains ideal no bias will be introduced.

The fundamental question of FPNC as I understand it is: should we introduce
> the
> historic block hash h as a consensus-critical parameter?
>
> The answer is a strict no: This quantity f (fitness) is purely random, and
> does
> not in any way favor the "honest" chain, nor can it identify it. Between
> two
> competing chains, the amount of bias on one chain vs. the other is purely
> random
> and does *not* reflect more work done by one side or the other. Nor can it
> have
> any knowledge of things like network splits.
>

A zero-prefix has the direct effort of lowering the big-endian base16 value
of the hash, and with each epoch the numeric value of the solution is
further decreased. A floating-point evaluation introduces the concept that
no two blocks can ever be of equal value unless they are in fact the same
hash value.  We are in full agreement with the statement you made above,
there is nothing intrinsic about the honest chain vs any other chain —
nodes are acting on an empirical evaluation.  It should only take 10-20
seconds of propagation for every node on the global network to see every
solution block, if we remove ambiguity and make sure that no two blocks are
the same value, since all nodes see all solutions they should all choose
the same highest-value solution.


> At constant difficulty assuming two competing chains with exactly the same
> number of blocks and amount of hashpower, this bias will oscillate,
> sometimes
> favoring one side, sometimes favoring the other. Unlike work, this bias is
> not
> cumulative. Each side will over time converge to having the same amount of
> bias
> from any biased estimator such as f constructed from the hashes h. Just
> because
> one side had an abnormally small hash doesn't mean the other side won't
> have a
> similar abnormally low hash. The expectation value for the amount of bias
> is
> equal on both sides.


Ah!  Yes!  Thank you so much for bringing this up.  This is the single most
important part of the entire soltuion, and I am so happy to have this
discussion.   If this solution was simply labeling one side a winner and
another side a loser, then there is no incentive for mining efforts to
migrate, and with the incentives of sunken cost into mining would be enough
to keep nodes from switching.  So If the solution was simply a label then
your statement above would be correct...  However, this exact situation was
taken into consideration.

In the current protocol clients always choose the chain of greatest value,
because trying mine a full block behind would require more than 50% of the
network power to "catch up."  No miner in their right mind would choose to
be behind the network.   If this evaluation is made on the floating-point
scale, as in not whole numbers and not whole blocks — then the exact same
properties of behind still come into play.  No miner chooses to mine from
N-1 blocks, because they would be behind, just as no miner would choose to
mine from a N-0.5 block.   The threat of generating a loser block from a
loser parent outweighs any other incentive.  The heredity of block fitness
creates convergence on the most valuable chain.  When looking at the
electorate over time, more miners will choose to mine with the higher-value
coinbase - thus eroding support for the computational effort needed to
sustain the disagreement.  No thrashing will happen, because no miner has
incentives for this to happen.

Nodes on the network cannot know the history of a block or why it was
produced,  but through an empirical measure of value we can have a protocol
that avoids ambiguity in the block selection process and prevents
disagreement from forming.   Ambiguity in block selection is also
exploitable, through pre-emption one solution can dominate a "first seen"
system, and any dissent can be silenced with DoS.  But using
resource-consumption attacks and the exploitation of a race-condition to
gain an edge isn't helpful if there isn't a disagreement to shape. The
disagreement here is powerful miners trying to prove each other wrong, but
if they had a more accurate measure of value — there would be no reason to
ever disagree.

All the best,
Michael

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