Return-Path:
Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136])
by lists.linuxfoundation.org (Postfix) with ESMTP id 0A730C0051
for ;
Thu, 24 Sep 2020 19:41:22 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by silver.osuosl.org (Postfix) with ESMTP id D2C3D203AE
for ;
Thu, 24 Sep 2020 19:41:21 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from silver.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id 83sAgmrsouc8
for ;
Thu, 24 Sep 2020 19:41:18 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mail-il1-f193.google.com (mail-il1-f193.google.com
[209.85.166.193])
by silver.osuosl.org (Postfix) with ESMTPS id 2EB9220399
for ;
Thu, 24 Sep 2020 19:41:18 +0000 (UTC)
Received: by mail-il1-f193.google.com with SMTP id q5so69188ilj.1
for ;
Thu, 24 Sep 2020 12:41:18 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=in-st-capital.20150623.gappssmtp.com; s=20150623;
h=mime-version:from:date:message-id:subject:to;
bh=zRBF3XS5EWJyJAnhBNuUh9+ojDrvCVs8Ab4iHwGpDIY=;
b=WR/LSSTq9RFBIWUnI8YRMsj81TctrMmK6tY/IVRAeGzlBjtCcLJjjVPB5RasYmT1YH
ca/ayQZIuX1o9XYxdAWc5dW1CqLj9eypm9pd2fcIcEUE/5+KhXLSs3BiRFRqgfosHN+j
oFA3EeejdFz8tC5xSXnecnXFlx+K8BgSqyp1eaVocoeZXBi2eK+LlnMe+puYYvTLd5Pp
/HXdOdvuZOrLXdhrkd7Fq4BtbVj2gYxByJkRZDvnJ6+6MK4G/kCVdHhpx4z817uLzs8O
j+P1wfOmL5Z6Kjm4IuW5Jgbus3a/jYDB+FTBir85ZPXsxrB2K74tdsSLh97Jvp7ioku4
U7+w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=zRBF3XS5EWJyJAnhBNuUh9+ojDrvCVs8Ab4iHwGpDIY=;
b=MadnXxMdcZaLeGmwEvPAzVXoMK9SbMrN48Py9L3vVqZWz57xsLZrWIdGlKpNhnMmSp
NQSc0tO8vTJG5Lj1SNWy1IzL7F9ownrKvrFNDg4rvTRo4lHtdvNE/bIKaf+fnYzgNppw
ksrqlxQ3vLnN28Q1ai8M44ZM0nGdai8MNKKXoqcN5pNNxDaEfLXxL73wTPiDXggZEXS3
voQ2gpi+tsUajR+RJm4GaU7wufbOViwlClXOuBmn9JttjWNRHFRnYU51r1imDSPCC3y3
Tco62BEHq2FjWGHWuwUNWj/jITFd8TsszxSORXmt/cGf0mf0iuQhHlDl+7AY5wpGLSh8
a/CQ==
X-Gm-Message-State: AOAM531u/kANaxRdxdmLc2dqst/iRyRVzVMbBPyhDtUOH7ZnZSsY2aQc
KejJPTzVQhdCLJPoP9VuO6rPkW8bgj3UjjnD3YdUZMN3HJroYeLNdu8=
X-Google-Smtp-Source: ABdhPJzji9f5UmThApP8dhbmW2kBv/YbKuJUjMO1PJ8K9ewvfLLr0u2KM2kqnl/vdlf48oyHDnUge939lUuetJAmbQw=
X-Received: by 2002:a05:6e02:f48:: with SMTP id
y8mr245152ilj.103.1600976476298;
Thu, 24 Sep 2020 12:41:16 -0700 (PDT)
MIME-Version: 1.0
From: Mike Brooks
Date: Thu, 24 Sep 2020 12:40:46 -0700
Message-ID:
To: bitcoin-dev
Content-Type: multipart/alternative; boundary="00000000000029f84305b01462e8"
X-Mailman-Approved-At: Fri, 25 Sep 2020 12:08:53 +0000
Subject: [bitcoin-dev] Floating-Point Nakamoto Consensus
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Thu, 24 Sep 2020 19:41:22 -0000
--00000000000029f84305b01462e8
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
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/Floa=
ting-Point%20Nakamoto%20Consensus.pdf
Pull Request:
https://github.com/bitcoin/bitcoin/pull/19665/files
---
Floating-Point Nakamoto Consensus
Abstract =E2=80=94 It has been shown that Nakamoto Consensus is very useful=
in the
formation of long-term global agreement =E2=80=94 and has issues with short=
-term
disagreement which can lead to re-organization (=E2=80=9Cor-org=E2=80=9D) o=
f 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 =E2=80=9Ceclipsing=E2=80=9D atta=
ck. When two
segments of the network disagree it creates a moment of weakness in which
less than 51% of the network=E2=80=99s 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 =E2=80=9Cdisho=
nest
nodes.=E2=80=9D Without a central authority or central view - all peers dep=
end 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 (=E2=80=9C0-day=E2=80=9D) which will strictl=
y prevent honest
nodes from communicating to new members of the network - a so-called =E2=80=
=9Ctotal
eclipse.=E2=80=9D The kind of DoS vulnerability needed to conduct an eclip=
se 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=E2=80=
=99t
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 =E2=80=98k=E2=80=99, is the sum of all available worker threads fo=
r all nodes in
the network, establishing =E2=80=98k+1=E2=80=99 connections by the pidgin-h=
ole 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=E2=80=99s assume a dishonest node is modified in two ways - it incr=
eases
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 =C2=BD as possible. If the netwo=
rk
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=E2=80=
=99s
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=E2=80=99s perspective, Bitcoi=
n 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=E2=80=99t ne=
ed 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=E2=80=99s process is determi=
nistic.
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 =E2=80=9Cblack thursday=E2=80=9D resulted in secured loans acci=
dentally 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=E2=80=99s
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=E2=80=99s original paper it was stated that the elector=
ate
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=E2=80=99s 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=E2=80=99t need to validate any lower-valued solution. In fact this=
fitness
value has a high degree of confidence that it won=E2=80=99t be unseated by =
a larger
value - being able to produce a proof-of-work with 19 0=E2=80=99s and a dec=
imal
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=E2=80=99s 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 =3D 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=E2=80=99s 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 =3D 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 =E2=80=9CSo=
ft Fork=E2=80=9D
otherwise known as a compatible software update. By contrast a =E2=80=9CHa=
rd-Fork=E2=80=9D
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
--00000000000029f84305b01462e8
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
=C2=A0 Hey Everyone,
=C2=A0A lot of wor=
k has gone into this paper, and the current revision has been well received=
and there is a lot of excitement on this side to=C2=A0be sharing it with y=
ou 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.=
=C2=A0 It is wildly underrated that future proofing was never really a cons=
ideration=C2=A0in the initial=C2=A0design - but here we are a decade later =
with amazing solutions like SegWit which=C2=A0gives us a real future-proofi=
ng framework.=C2=A0 The fact that future-proofing was added to Bitcoin with=
a softfork gives me goosebumps.=C2=A0I'd just like to take the time to=
thank the people who worked on SegWit and it is an appreciation=C2=A0that =
comes up in conversation of how difficult and necessary that process was,=
=C2=A0and this appreciation may not be vocalized to the great people who wo=
rked 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 p=
roject.
This current proposal really has nothing t=
o do with=C2=A0SegWit - but it is an update that will make the network a li=
ttle better for the future, and we hope you enjoy the paper.=C2=A0
=C2=
=A0
---
<=
div>
Floating-Point Nakamoto Consensus
=
Abstract =E2=80=94 It has been shown that Nakamoto Consensus is very useful in the format=
ion of long-term global agreement =E2=80=94 and has issues with short-term =
disagreement which can lead to re-organization (=E2=80=9Cor-org=E2=80=9D) o=
f the blockchain.=C2=A0 A malicious miner with knowledge of a specific kind=
of denial-of-service (DoS) vulnerability can gain an unfair advantage in t=
he current Bitcoin network, and can be used to undermine the security guara=
ntees that developers rely upon.=C2=A0 Floating-Point Nakamoto consensu mak=
es it more expensive to replace an already mined block vs. creation of a ne=
w block, and by resolving ambiguity of competition solutions it helps achie=
ve global consumers more quickly.=C2=A0 A floating-point fitness test stron=
gly incentivises the correct network behavior, and prevents disagreement fr=
om ever forming in the first place.
Introduction
The Bitcoin protocol was created=
to provide a decentralized consensus on a fully distributed p2p network.=
=C2=A0 A problem arises when more than one proof-of-work is presented as th=
e next solution block in the blockchain.=C2=A0 Two solutions of the same he=
ight are seen as authoritative equals which is the basis of a growing disag=
reement. A node will adopt the first solution seen, as both solutions propa=
gate across the network a race condition of disagreement is formed. This ra=
ce condition can be controlled by byzentiene fault injection commonly refer=
red to as an =E2=80=9Ceclipsing=E2=80=9D attack.=C2=A0 When two segments of=
the network disagree it creates a moment of weakness in which less than 51=
% of the network=E2=80=99s computational resources are required to keep the=
network balanced against itself.=C2=A0
Nakamoto Consensus=
h4>
Nakamoto Consensus is t=
he process of proving computational resources in order to determine eligibi=
lity to participate in the decision making process.=C2=A0 If the outcome of=
an election were based on one node (or one-IP-address-one-vote), then repr=
esentation could be subverted by anyone able to allocate many IPs. A consen=
sus is only formed when the prevailing decision has the greatest proof-of-w=
ork effort invested in it. In order for a Nakamoto Consensus to operate, th=
e network must ensure that incentives are aligned such that the resources n=
eeded to subvert a proof-of-work based consensus outweigh the resources gai=
ned through its exploitation. In this consensus model, the proof-of-work re=
quirements for the creation of the next valid solution has the exact same c=
ost 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 t=
he 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 require=
d to support Nakamoto Conesus, and for our purposes this is entirely decent=
ralized. 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.=C2=A0 This design makes no =
guarantees that the peers connected do not misrepresent the network or so c=
alled =E2=80=9Cdishonest nodes.=E2=80=9D Without a central authority or cen=
tral view - all peers depend on the data provided by neighboring peers - th=
erefore a dishonest node can continue until a peer is able to make contact =
an honest node.
Security=C2=A0
In this threat model let us assume a malicious mine=
r possesses knowledge of an unpatched DoS vulnerability (=E2=80=9C0-day=E2=
=80=9D) which will strictly prevent honest nodes from communicating to new =
members of the network - a so-called =E2=80=9Ctotal eclipse.=E2=80=9D=C2=A0=
The kind of DoS vulnerability needed to conduct an eclipse does not need t=
o consume all CPU or computaitly ability of target nodes - but rather preve=
nt target nodes from forming new connections that would undermine the eclip=
sing effect. These kinds of DoS vulnerabilities are somewhat less substiona=
l than actually knocking a powerful-mining node offline.=C2=A0 This class o=
f 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 connect=
ion to a segment of the network that isn=E2=80=99t entirely suppressed. Let=
us assume a defense-in-depth strategy and plan on this kind of failure.
Let us now con=
sider that the C++ Bitcoind has a finite number of worker threads and a fin=
ite number of connections that can be serviced by these workers.=C2=A0 When=
a rude client occupies all connections - then a pidgin-hole principle come=
s into play. If a network's maximum capacity for connection handlers =
=E2=80=98k=E2=80=99, is the sum of all available worker threads for all nod=
es in the network, establishing =E2=80=98k+1=E2=80=99 connections by the pi=
dgin-hole principle will prevent any new connections from being formed by h=
onest nodes - thereby creating a perfect eclipse for any new miners joining=
the network would only be able to form connections with dishonest nodes.=
span>
Now let=E2=80=
=99s assume a dishonest node is modified in two ways - it increases the max=
imum connection handles to hundreds of thousands instead of the current val=
ue which is about 10. Then this node is modified to ignore any solution blo=
cks 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 si=
des that disagree about which tip of the chain to use.=C2=A0 Any new soluti=
on propagates through nodes one hop at a time. This propagation can be pred=
icted 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 o=
ne solution, while slowing another. If ever a competing proof-of-work is br=
oadcasted to the network, the adversary will use their network influence to=
split knowledge of the proof-of-work as close to =C2=BD as possible. If th=
e 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 s=
ystem is in balance. =C2=A0 As long as two sides of the network are perfect=
ly in disagreement and generating new blocks - the attacker has intentional=
ly created a hard-fork against the will of the network architects and opera=
tors. The disagreement needs to be kept open until the adversary=E2=80=99s =
transactions have been validated on the honest chain - at which point the a=
ttacker will add more nodes to the dishonest chain to make sure it is the u=
ltimate winner - thus replacing out the honest chain with the one generated=
by dishonest miners.
This attack is convenient from the adversary=E2=80=99s perspectiv=
e,=C2=A0 Bitcoin being a broadcast network advertises the IP addresses of a=
ll active nodes - and Shodan and the internet scanning project can find all=
passive nodes responding on TCP 8333.=C2=A0 This should illuminate all hon=
est nodes on the network, and even honest nodes that are trying to obscure =
themselves by not announcing their presence.=C2=A0 This means that the atta=
cker doesn=E2=80=99t 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.<=
/p>
During a split in t=
he blockchain, each side of the network will honor a separate merkel-tree f=
ormation and therefore a separate ledger of transactions. An adversary will=
then broadcast currency deposits to public exchanges, but only on the weak=
er 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 do=
uble-spend. With this currency deposited on a chain that will become epheme=
ral, the attacker can wire out the account balance on a different blockchai=
n - such as Tether which is an erc20 token on the Ethereum network which wo=
uld be unaffected by this attack.=C2=A0 When the weaker chain collapses, th=
e 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=E2=
=80=99s process is deterministic.=C2=A0 In the short term, we can observe t=
hat the Nakamoto Consensus is empirically non-deterministic which is eviden=
t by re-organizations (re-org) as a method of resolving disagreements withi=
n the network. =C2=A0 During a reorganization a blockchain network is at it=
s 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 o=
n the network which creates disagreement between miners.=C2=A0
DeFi (Decentralized Fina=
nce) and smart-contract obligations depend on network stability and determi=
nism.=C2=A0 Failure to pay contracts, such as what happened on =E2=80=9Cbla=
ck thursday=E2=80=9D resulted in secured loans accidentally falling into re=
demption.=C2=A0 The transactions used by a smart contract are intended to b=
e completed quickly and the outcome is irreversible.=C2=A0 However, if the =
blockchain network has split then a contract may fire and have it=E2=80=99s=
side-effects execute only to have the transaction on the ledger to be repl=
aced.=C2=A0 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 colla=
teral backed loans have a redemption clause which would force the borrower =
on the loan to lose their deposit entirely.=C2=A0
With two sides of the network balance=
d against each other - an attacker has split the blockchain and this hard-f=
ork 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 side=
s of the network.=C2=A0 The amount of resources needed to balance the netwo=
rk against itself is far less than a 51% attack - thereby undermining the s=
ecurity guarantees needed for a decentralized untrusted payment network to =
function.=C2=A0 An adversary with a sufficiently large network of dishonest=
bots could use this to take a tally of which miners are participating in w=
hich side of the network split. This will create an attacker-controlled har=
d 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 co=
llapse is up to the individual with the most IP address, not the most compu=
tation.
In S=
atoshi Nakamoto=E2=80=99s original paper it was stated that the electorate =
should be represented by computational effort in the form of a proof-of-wor=
k, and only these nodes can participate in the consues process.=C2=A0 Howev=
er, the electorate can be misled by non-voting nodes which can reshape the =
network to benefit an individual adversary.
Chain Fitness
Any solution to byzantin=
e fault-injection or the intentional formation of disagreements must be ful=
ly decentralized. A blockchain is allowed to split because there is ambigui=
ty 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 s=
olution block is the same value, and a more-fit solution is always chosen o=
ver a weaker solution. Any adversary attempting to have a weaker chain to w=
in out would have to overcome a kind of relay-race, whereby the winning tea=
m=E2=80=99s strength is carried forward and the loser will have to work har=
der and harder to maintain the disagreement.=C2=A0 In most cases Floating-P=
oint Nakamoto Consensus will prevent a re-org blockchain from ever going pa=
st a single block thereby expediting the formation of a global consensus.=
=C2=A0 Floating-Point Nakamoto Consensus cements the lead of the winner and=
to greatly incentivize the network to adopt the dominant chain no matter h=
ow many valid solutions are advertised, or what order they arrive.=
p>
The first step in Fl=
oating-Point Nakamoto Consensus is that all nodes in the network should con=
tinue to conduct traditional Nakamoto Consensus and the formation of new bl=
ocks is dictated by the same zero-prefix proof-of-work requirements.=C2=A0 =
If at any point there are two solution blocks advertised for the same heigh=
t - 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 nei=
ghbors. Any time two solutions are advertised then a re-org is inevitable a=
nd it is in the best interest of all miners to adopt the most-fit block, fa=
iling to do so risks wasting resources on a mining of a block that would be=
discarded.=C2=A0 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 i=
s also more fit that the current solution - which is much more computationa=
lly 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 sol=
utions, each replacement can only be done if it is more fit, thereby provin=
g that it has an increased expense.=C2=A0 If at any point two solutions of =
the same height are found it means that eventually some node will have to r=
eplace 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-w=
ork so that it is universally and identically verifiable by all nodes on th=
e network.=C2=A0 Additionally, this fitness-test evaluation needs to ensure=
that no two competing solutions can be numerically equivalent.
<=
br>Let us suppose that two=
or more valid solutions will be proposed for the same block.=C2=A0 To weig=
h the value of a given solution, let's consider a solution for block 63=
9254, in which the following hash was proposed:
=C2=A0=C2=A0=C2=A0=C2=A00000000000000000000=
8e33faa94d30cc73aa4fd819e58ce55970e7db82e10f8
There are 19 zeros, and the remaining has=
h in base 16 starts with 9e3 and ends with f8.=C2=A0 This can value can be =
represented in floating point as:
=C2=A0=C2=A0=C2=A0=C2=A019.847052573336114130069196154809=
453027792121882588614904
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.=C2=A0<=
/span>
=C2=A0=C2=A0=C2=
=A01.847
Now=
let us suppose that a few minutes later another solution is advertised to =
the network shown in base16 below:
=C2=A0=C2=A0=C2=A0=C2=A0000000000000000000028285ed9bd2c7=
74136af8e8b90ca1bbb0caa36544fbc2
The solution above also has 19 prefixed zeros, and is =
being broadcast for the same blockheight value of 639254 - and a fitness sc=
ore of 1.282.=C2=A0 With Nakamoto Consensus both of these solutions would b=
e equivalent and a given node would adopt the one that it received first.=
=C2=A0 In Floating-Post Nakamoto Consensus, we compare the fitness scores a=
nd keep the highest.=C2=A0 In this case no matter what happens - some nodes=
will have to change their tip and a fitness test makes sure this happens i=
mmediately.=C2=A0
With both solutions circulating in the network - any node who has rec=
eived both proof-of-works should know 1.847 is the current highest value, a=
nd shouldn=E2=80=99t need to validate any lower-valued solution.=C2=A0 In f=
act this fitness value has a high degree of confidence that it won=E2=80=99=
t be unseated by a larger value - being able to produce a proof-of-work wit=
h 19 0=E2=80=99s and a decimal component greater than 0.847 is non-trivial.=
=C2=A0 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.8=
47 version of the blockchain.=C2=A0
All nodes are incentivized to support the solution with=
the highest fitness value - irregardless of which order these proof-of-wor=
k were validated. Miners are incentivized to support the dominant chain whi=
ch helps preserve the global consensus.
Let us assume that the underlying cryptographi=
c 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 the=
ir proof-of-work.=C2=A0 Additionally if we assume an ideal cipher then the =
fitness of all possible solutions is gaussian-random. With these assumption=
s then on average a new solution would split the keyspace of remaining solu=
tions in half.=C2=A0 Given that the work needed to form a=C2=A0 new block r=
emains 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 ad=
opted by all nodes if it is the first solution.=C2=A0 To leverage a chain r=
eplacement on nodes conducting Floating-Point Nakamoto Consensus a maliciou=
s 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 neede=
d to overcome the 19 zero prefix, but also the non-zero fitness test. =C2=
=A0 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 chanc=
e to move on with the next solution.=C2=A0 With inductive reasoning, we can=
see that a demissiniong keyspace increases the amount of work needed to fi=
nd a solution that also meets this new criteria.
Now let us assume a heavily-fragmente=
d network where some nodes have gotten one or both of the solutions.=C2=A0 =
In the case of nodes that received the proof-of-work solution with a fitnes=
s 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.=C2=A0 However, we must=
assume some parts of the network never got the message about 1.847 proof o=
f work, and instead continued to mine using a value of 1.240 as the previou=
s block. =C2=A0 Now, let=E2=80=99s say this group of isolated miners manage=
s to present a new conflicting proof-of-work solution for 639255:
=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0000000000000000000058d8ebeb076584bb5853c80111bc06b5ada35463091a6=
span>
The above bas=
e16 block has a fitness score of 1.532=C2=A0 The fitness value for the prev=
ious block 639254 is added together:
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A02.772 =3D 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.=C2=A0 If the weaker branch is suf=
ficiently lucky, and finds a solution before the dominant branch then this =
solution will have a higher overall fitness score, and this solution will p=
ropagate as it has the higher value.=C2=A0 This is also important for trans=
actions 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.=C2=A0 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 u=
s assume that both the weaker group and the dominant group have produced co=
mpeting proof-of-work solutions for blocks 639254 and 639255 respectively.=
=C2=A0 Let=E2=80=99s assume that the dominant group that went with the 1.84=
7 fitness score - also produces a solution with a similar fitness value and=
advertises the following solution to the network:
0000000000000000000=
455207e375bf1dac0d483a7442239f1ef2c70d050c113
19.4149736494645748775491982=
90879237036867705594421756179
or
3.262 =3D 1.847 + 1.415
A total of 3.262 is still do=
minant 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.=C2=A0 I=
n this scenario, in order for the weaker chain to supplant the dominant cha=
in it must overcome a -0.49 point deficit. In traditional Nakamoto Consensu=
s the nodes would see both forks as authoritative equals which creates a di=
vide in mining capacity while two groups of miners search for the next bloc=
k.=C2=A0 In Floating-Point Nakamoto Consensus any nodes receiving both fork=
s, would prefer to mine on the chain with an overall fitness score of +3.26=
2 - making it even harder for the weaker chain to find miners to compete in=
any future disagreement, thereby eroding support for the weaker chain. Thi=
s kind of comparison requires an empirical method for determining fitness b=
y miners following the same same system of rules will insure a self-fulfill=
ed outcome.=C2=A0 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 n=
etwork has a mechanism to resolve ambiguity and de-incentivise dissent.
Soft Fork
=
Blockchain networks that would like to improve the consensus generation met=
hod by adding a fitness test should be able to do so using a =E2=80=9CSoft =
Fork=E2=80=9D otherwise known as a compatible software update.=C2=A0 By con=
trast a =E2=80=9CHard-Fork=E2=80=9D is a separate incompatible network that=
does not form the same consensus.=C2=A0 Floating-Point Nakamoto Consensus =
can be implemented as a soft-fork because both patched, and non-patched nod=
es can co-exist and non-patched nodes will benefit from a kind of herd immu=
nity in overall network stability.=C2=A0 This is because once a small numbe=
r of nodes start following the same rules then they will become the decidin=
g factor in which chain is chosen.=C2=A0 Clients that are using only tradit=
ional Nakamoto Consensus will still agree with new clients over the total c=
hain length. Miners that adopt the new strategy early, will be less likely =
to lose out on mining invalid solutions.
Conclusion
Floating-Point Nakamoto consen=
sus allows the network to form a consensus more quickly by avoiding ambigui=
ty allowing for determinism to take hold. Bitcoin has become an essential u=
tility, and attacks against our networks must be avoided and adapting, patc=
hing and protecting the network is a constant effort. An organized attack a=
gainst a cryptocurrency network will undermine the guarantees that blockcha=
in 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 Nakam=
oto Consensus.=C2=A0 An example implementation has been written and submitt=
ed as a PR to the bitcoin core which is free to be adapted by other network=
s.
A complete implementation of Floating-Point Nakamot=
o 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
--00000000000029f84305b01462e8--