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

[yanmaani--- via bitcoin-dev]

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  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  on
behalf of Mike Brooks via bitcoin-dev

Sent: Friday, 25 September 2020 5:40 AM
To: bitcoin-dev 
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 vocaliz

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

[Mike Brooks via bitcoin-dev]

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

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

[Mike Brooks via bitcoin-dev]

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 

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

[Bob McElrath via bitcoin-dev]

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 

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Mike Brooks via bitcoin-dev]

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

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

[Mike Brooks via bitcoin-dev]

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

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

[Larry Ruane via bitcoin-dev]

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

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

[Mike Brooks via bitcoin-dev]

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.

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

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

[ZmnSCPxj via bitcoin-dev]

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  wrote:
>
> > Good morning Mike,
> >
> > > You are incorrect. 
> >
> > You make no argument to back this 

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

[ZmnSCPxj via bitcoin-dev]

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

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[ZmnSCPxj via bitcoin-dev]

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

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

[Mike Brooks via bitcoin-dev]

ZmnSCPxj,

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

-Mike Brooks

On Tue, Sep 29, 2020, 11:31 PM ZmnSCPxj  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
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[ZmnSCPxj via bitcoin-dev]

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

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

[Mike Brooks via bitcoin-dev]

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

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

[LORD HIS EXCELLENCY JAMES HRMH via bitcoin-dev]

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  on behalf of 
Mike Brooks via bitcoin-dev 
Sent: Friday, 25 September 2020 5:40 AM
To: bitcoin-dev 
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 solut

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

[Franck Royer via bitcoin-dev]

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

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

[Mike Brooks via bitcoin-dev]

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

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

[David A. Harding via bitcoin-dev]

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


signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Mike Brooks via bitcoin-dev]

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

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

[Mike Brooks via bitcoin-dev]

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 

Re: [bitcoin-dev] Floating-Point Nakamoto Consensus (bitcoin ml)

[John Tromp via bitcoin-dev]

Re: Floating-Point Nakamoto Consensus (bitcoin ml)
>

> This is a pretty big departure from cumulative POW.

It's still cumulative. But instead of cumulating network difficulty,
they cumulate log_2(solution difficulty).

So if two solutions are found simultaneously, and one has a hash
that's only half of the other, then that will have twice the solution
difficulty and thus contribute 1 more the cumulate log_2(solution
difficulty).

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

Nothing happens in these cases, as the new blocks are still far behind
the tip in cumulative score (they just have higher score at their
height).

regards,
-John
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

[Jeremy via bitcoin-dev]

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

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

[bitcoin ml via bitcoin-dev]

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