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] Progress on Miner Withholding - FPNC

[Mike Brooks via bitcoin-dev]

Pieter,

You are correct.

And also, I did prove what I set out to prove. The code provided privately
to the security team will in fact consume 99% of the CPU, which means it
does have an effect on the electorate.  It is true the node still
stubbornly passes messages, but I would argue that this is still very much
a problem that would concern operators, and perhaps the threshold for a
patch is much too high.  A layered security system like what is found in
bitcoin necessitates an attack chain.  The `getdata` message is an implicit
information disclosure that allows for the identification of dissenting
nodes.   As ZmnSCPxj pointed out, block mixing will give preemption at most
67% of the network, and the remaining dissenting nodes can be quelled by
maxing out their processing power.  All of this can be used together to
make sure that a withheld block becomes the prevailing solution.

FPNC rebalances incentives to serve the interests of the network, and
fundamentally resolves a class of abuses that reshape the electorate.  FPNC
will produce a more deceliterized and fair network than "first seen."

Cheers,
Mike

On Wed, Oct 7, 2020 at 5:12 PM Pieter Wuille  wrote:

> On Wednesday, October 7, 2020 1:31 PM, Mike Brooks via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> But first of all, I'd like to say that the idea for FPNC came out of a
> conversation with ZmnSCPxj's in regards to re-org stability.  When I had
> proposed blockchain pointers with the PubRef opcode, he took the time to
> explain to me concerns around re-orgs and why it is a bigger problem than I
> initially had thought — and I greatly appreciate this detail.   After
> touching base with ZmnSCPxj and Greg Maxwell there is an overwhelming view
> that the current problems that face the network outweigh any theoretical
> ones.
>
>
> Greg Maxwell isn't on this list, but assuming this is about the conversion
> you've had on Bitcoin Core's security disclosure list, I believe this is a
> misrepresentation. The discussion has been mostly around a DoS attack
> report which turned out to be a mistake.
>
> Cheers,
>
> --
> Pieter
>
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Progress on Miner Withholding - FPNC

[Mike Brooks via bitcoin-dev]

Very interesting,

Block mixing did not resolve the selfish mining that is currently observed
on the network.  This mitigation was only intended to limit the maximum
impact of waiting for a 2nd block to be produced.

Rebalancing the selfish-mining incentives with FPNC and a faster block
creation time is the single best thing we can do to decentralize mining
efforts.  It will also produce a better network.



On Wed, Oct 7, 2020 at 6:40 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning all,
>
> >
> > Below is a novel discussion on block-withholding attacks and FPNC. These
> are two very simple changes being proposed here that will
> dramatically impact the network for the better.
> >
> > But first of all, I'd like to say that the idea for FPNC came out of a
> conversation with ZmnSCPxj's in regards to re-org stability.  When I had
> proposed blockchain pointers with the PubRef opcode, he took the time to
> explain to me concerns around re-orgs and why it is a bigger problem than I
> initially had thought — and I greatly appreciate this detail.   After
> touching base with ZmnSCPxj and Greg Maxwell there is an overwhelming view
> that the current problems that face the network outweigh any theoretical
> ones.
> >
> > Currently the elephant in the room is the miner withholding
> attack. There is an unintended incentive to hold onto blocks because
> keeping knowledge of this coinbase private gives a greedy miner more time
> to calculate the next block.  Major mining pools are actively employing
> this strategy because winning two blocks in a row has a much greater payoff
> than common robbery. This unfair advantage happens each time a new block is
> found, and provides a kind of home-field advantage for large pools, and
> contributes to a more centralized network. This odd feature of the bitcoin
> protocol provides a material incentive to delay transactions and encourages
> the formation of disagreements. In a sense, withholding is a deception of
> the computational power of a miner, and by extension a deception of their
> influence within the electorate.  In effect, other miners are forced to
> work harder, and when they are successful in finding a 2nd solution of the
> same height — no one benefits. Disagreement on the bitcoin network is not
> good for the environment, or for the users, or for honest miners, but is
> ideal for dishonest miners looking for an advantage.
>
> This is my understanding:
>
> The selfish mining attack described above was already presented and known
> about **many years** ago, with the solution presented here:
> https://www.cs.cornell.edu/~ie53/publications/btcProcFC.pdf
>
> The solution was later determined to actually raise the needed threshhold
> to 33%, not 25% in the paper.
>
> That solution is what is used in the network today.
>
> Implementing floating-point Nakamoto Consensus removes the solution
> presented in the paper, and therefore risks reintroducing the selfish
> mining attack.
>
> Therefore, floating-point Nakamoto Consensus is a hard NAK.
>
>
> Regards,
> ZmnSCPxj
>
> ___
> 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

[bitcoin-dev] Progress on Miner Withholding - FPNC

[Mike Brooks via bitcoin-dev]

Hello Everyone,

Below is a novel discussion on block-withholding attacks and FPNC. These
are two very simple changes being proposed here that will
dramatically impact the network for the better.

But first of all, I'd like to say that the idea for FPNC came out of a
conversation with ZmnSCPxj's in regards to re-org stability.  When I had
proposed blockchain pointers with the PubRef opcode, he took the time to
explain to me concerns around re-orgs and why it is a bigger problem than I
initially had thought — and I greatly appreciate this detail.   After
touching base with ZmnSCPxj and Greg Maxwell there is an overwhelming view
that the current problems that face the network outweigh any theoretical
ones.

Currently the elephant in the room is the miner withholding attack. There
is an unintended incentive to hold onto blocks because keeping knowledge of
this coinbase private gives a greedy miner more time to calculate the next
block.  Major mining pools are actively employing this strategy because
winning two blocks in a row has a much greater payoff than common robbery.
This unfair advantage happens each time a new block is found, and provides
a kind of home-field advantage for large pools, and contributes to a more
centralized network. This odd feature of the bitcoin protocol provides a
material incentive to delay transactions and encourages the formation of
disagreements. In a sense, withholding is a deception of the computational
power of a miner, and by extension a deception of their influence within
the electorate.  In effect, other miners are forced to work harder, and
when they are successful in finding a 2nd solution of the same height — no
one benefits. Disagreement on the bitcoin network is not good for the
environment, or for the users, or for honest miners, but is ideal for
dishonest miners looking for an advantage.

Currently, there is no way to resolve disagreements of the same block
height in Bitcoin protocol.  Floating-point Nakamoto Consensus (
https://github.com/in-st/Floating-Point-Nakamoto-Consensus/blob/master/Floating-Point%20Nakamoto%20Consensus.pdf)
address ambiguity in the consensus formation process so that disagreements
can be empirically resolved without wasted effort. With FPNC every block
has a non-zero element which provides the basis for a floating-point
fitness value. Nodes are already incentivised to choose the solution that
represents the most amount of work, FPNC allows for this same calculation
to happen for two solutions of the same height. With FPNC the higher
fitness-value carries forward, and all children of this higher value block
will be stronger from having a higher fitness value, this is to make sure
that  winning blocks stay as the winner.  If a rogue client chooses to mine
a low value disagreement, they will have to make-up the difference in
fitness score with their next solution — This is the genetic
algorithm supported by FPNC which ensures that the child blocks from a
loser will also be losers.

Using FPNC as a method of disagreement resolution enables two features that
provide better incentives over "first seen." For one,  FPNC introduces risk
into holding onto low-value solutions, which de-incentivises 1/2 of all
withholding attacks.  Additionally, FPNC can be used to increase the rate
of block formation which will reduce the amount of time that a miner can
hold onto private blocks.

With FPNC, a node will only accept the highest-value chain.  With the added
threat of another miner finding a higher-FPNC value solution, any
unscrupulous miner who has mined a low-value block (less than 50% value) is
greatly incentives to broadcast out this block before a more valuable
solution is found.  It is important to note that replacing a low-FPNC value
block is more expensive than simply finding a new block, so even if the
lowest value is broadcast it is the winner, until proven otherwise.  These
greedy miners are holding onto 100% of solution blocks - but FPNC creates a
class of block that isn't incentivised on holding. The threat of being
replaced by a fair disagreement-resolution process, keeps all miners honest.

With 1/2 of the blocks being withheld, and 1/2 not being
broadcast immediately, you could eventually identify malicious miners based
on this timing difference. With the current system it isn't as clear, but
with a split incentive you the network can observe unfair treatment of
high-valued blocks.  FPNC makes the silent process of withholding into one
that must show a value-bias, and this unethical behavior can be
observed and acted upon.

The question that is on everyone's mind: Does FPNC create new bad
incentives? No, it only limits the bad incentives that already exist in the
protocol.
->
Any miner holding onto a high FPNC-value block would have a slight
advantage only for the immediate next block.  The hopes of generating
future blocks and armed with a slight advantage, would need at-least 50%
processing power to maintain. At-least 50% is needed 

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

[bitcoin-dev] Preferential Treatment in AttemptToEvictConnection()

[Mike Brooks via bitcoin-dev]

Hey Everyone,

A lot of pressure rides on AttemptToEvictConnection() because it is used to
limit the impact of eclipsing attacks. With continued centralization, fair
connection formation becomes a bigger concern. I am curious how other
members of the community feel about the preferential treatment and odd
comments found in AttemptToEvictConnection().  In short, the concern is
that an adversary which intends on providing the useful service of
data-arbitrage will have preferential treatment in the formation of the
network.

https://github.com/bitcoin/bitcoin/blame/df2129a2349b1877049f250551f49a4592e73765/src/net.cpp#L946-L981

Line 948:
// An attacker cannot predict which netgroups will be protected
->
Perhaps not, but the attacker can have more netgroups than node slots, this
can be optimized for. Simply being in different places does not mean the
nodes are honest or safe. This is probably a good check to have, but it
should not say an "attacker cannot", as this is misleading.

Line 952:
// An attacker cannot manipulate this metric without physically moving
nodes closer to the target.
 ->
Yes, that is exactly what the attacker will do. An attacker can run
tcp-traceroute on the network to find where miners clump up, and run a
malicious message-relay in a nearby datacenter. With a financial motive it
is cheaper to run a low-cost message relay than a mining node.


Line 955:
// Protect 4 nodes that most recently sent us novel transactions accepted
into our mempool. Add recently accepted blocks and txn to
AttemptToEvictConnection.
// An attacker cannot manipulate this metric without performing useful work
.->
If an honest node sees an novel transaction from a new incoming connection,
it will be less likely to remove it. A dishonest centralized-service can
preemptively send novel-transactions as part of the handshake for new
hosts, this will improve the odds of the connection staying open and
cutting contact with an honest node.


line 962:
// Protect 4 nodes that most recently sent us novel blocks.
// An attacker cannot manipulate this metric without performing useful work.
->
This code has the assumption that an adversary will play by the rules. An
attacker will manipluate this metric with the data-arbitrage of novel
blocks. An attacker can move newly created blocks from the source (large
mining pools) to all parts of the network which can be used to garner value
within the connection pool of new hosts.


All of the above checks, except for the one starting on 948 is subject to a
race condition.

All the best,
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

[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

[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

[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

[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

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

[bitcoin-dev] Floating-Point Nakamoto Consensus

[Mike Brooks via bitcoin-dev]

  Hey Everyone,

 A lot of work has gone into this paper, and the current revision has been
well received and there is a lot of excitement on this side to be sharing
it with you today. There are so few people that truly understand this
topic, but we are all pulling in the same direction to make Bitcoin better
and it shows.  It is wildly underrated that future proofing was never
really a consideration in the initial design - but here we are a decade
later with amazing solutions like SegWit which gives us a real
future-proofing framework.  The fact that future-proofing was added to
Bitcoin with a softfork gives me goosebumps. I'd just like to take the time
to thank the people who worked on SegWit and it is an appreciation that
comes up in conversation of how difficult and necessary that process
was, and this appreciation may not be vocalized to the great people who
worked on it. The fact that Bitcoin keeps improving and is able to respond
to new threats is nothing short of amazing - thank you everyone for a great
project.

This current proposal really has nothing to do with SegWit - but it is an
update that will make the network a little better for the future, and we
hope you enjoy the paper.

PDF:
https://github.com/in-st/Floating-Point-Nakamoto-Consensus/blob/master/Floating-Point%20Nakamoto%20Consensus.pdf

Pull Request:
https://github.com/bitcoin/bitcoin/pull/19665/files

---


Floating-Point Nakamoto Consensus

Abstract — It has been shown that Nakamoto Consensus is very useful in the
formation of long-term global agreement — and has issues with short-term
disagreement which can lead to re-organization (“or-org”) of the
blockchain.  A malicious miner with knowledge of a specific kind of
denial-of-service (DoS) vulnerability can gain an unfair advantage in the
current Bitcoin network, and can be used to undermine the security
guarantees that developers rely upon.  Floating-Point Nakamoto consensu
makes it more expensive to replace an already mined block vs. creation of a
new block, and by resolving ambiguity of competition solutions it helps
achieve global consumers more quickly.  A floating-point fitness test
strongly incentivises the correct network behavior, and prevents
disagreement from ever forming in the first place.
Introduction

The Bitcoin protocol was created to provide a decentralized consensus on a
fully distributed p2p network.  A problem arises when more than one
proof-of-work is presented as the next solution block in the blockchain.
Two solutions of the same height are seen as authoritative equals which is
the basis of a growing disagreement. A node will adopt the first solution
seen, as both solutions propagate across the network a race condition of
disagreement is formed. This race condition can be controlled by byzentiene
fault injection commonly referred to as an “eclipsing” attack.  When two
segments of the network disagree it creates a moment of weakness in which
less than 51% of the network’s computational resources are required to keep
the network balanced against itself.
Nakamoto Consensus

Nakamoto Consensus is the process of proving computational resources in
order to determine eligibility to participate in the decision making
process.  If the outcome of an election were based on one node (or
one-IP-address-one-vote), then representation could be subverted by anyone
able to allocate many IPs. A consensus is only formed when the prevailing
decision has the greatest proof-of-work effort invested in it. In order for
a Nakamoto Consensus to operate, the network must ensure that incentives
are aligned such that the resources needed to subvert a proof-of-work based
consensus outweigh the resources gained through its exploitation. In this
consensus model, the proof-of-work requirements for the creation of the
next valid solution has the exact same cost as replacing the current
solution. There is no penalty for dishonesty, and this has worked well in
practice because the majority of the nodes on the network are honest and
transparent, which is a substantial barrier for a single dishonest node to
overcome.

A minimal network peer-to-peer structure is required to support Nakamoto
Conesus, and for our purposes this is entirely decentralized. Messages are
broadcast on a best-effort basis, and nodes can leave and rejoin the
network at will, accepting the longest proof-of-work chain as proof of what
happened while they were gone.  This design makes no guarantees that the
peers connected do not misrepresent the network or so called “dishonest
nodes.” Without a central authority or central view - all peers depend on
the data provided by neighboring peers - therefore a dishonest node can
continue until a peer is able to make contact an honest node.
Security

In this threat model let us assume a malicious miner possesses knowledge of
an unpatched DoS vulnerability (“0-day”) which will strictly prevent honest
nodes from communicating to new members of the network - a so-called “total
eclipse.”  

Re: [bitcoin-dev] Smaller Transactions with PubRef

[Mike Brooks via bitcoin-dev]

Hey  ZmnSCPxj,

Re-orgs should be solved in a different way.

Best Regards,
Micahel

On Sat, Aug 1, 2020 at 5:36 PM ZmnSCPxj  wrote:

> Good morning Mike,
>
> Hard NAK.
>
> The responses to the original posting already pointed out important
> problems with this:
>
> * Encourages address reuse, hurting fungibility and privacy.
> * Prevents pruning, since access to previous blocks must always be
> available in order to validate.
> * Optimized implementation requires creating yet another index to previous
> block data, increasing requirements on fullnodes.
> * Requires SCRIPT to be re-evaluated on transactions arriving in
> newblocks, to protect against reorgs of the chaintip, and in particular
> `OP_PUBREF` references to near the chaintip.
>
> None of these issues have been addressed in your current proposal.
> The proposal looks at clients only, without considering what validators
> have to implement in order to validate new blocks with this opcode.
>
> Regards,
> ZmnSCPxj
>


Floating-Point Nakamoto Consensus.pdf
Description: Adobe PDF document
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] Smaller Transactions with PubRef

[Mike Brooks via bitcoin-dev]

The attached BIP describes a new opcode that unlocks the ability to have
transactions that are about 37% smaller than a traditional single-source
segwit transaction.  (Savings vary based on the number of inputs.)

The pursuit of smaller transactions is vital for Inclusive Accountability
as less data needs to be recorded on chain. Frugality is improved in two
ways; more transactions can be confirmed in a  block, and small value
inputs otherwise inaccessible can now be referenced without losing
unrecoverable value due to transaction overhead.

https://github.com/TheRook/bip-pubref/blob/master/bip-PubRef.mediawiki

The variant of this technology on the ethereum side is Ditto Transactions:
https://ethereum-magicians.org/t/eip-ditto-transactions/4455
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] PubRef - Script OP Code For Public Data References

[Mike Brooks via bitcoin-dev]

ZmnSCPxj,

> Lightning uses a "short channel ID" which is basically an index of block
number + index of transaction + index of output to refer to channels.

Oh wow, this is very similar to the PUBREF proposal. In fact the OP_PUBREF4
operation could be modified to take the tuple: (block number, index of
transaction, index of PUSHDATA) and it would be functionally equivalent.
It looks like the construction of the short channel ID was chosen for the
performance needed to resolve the lookup.

  > The problem with transaction being pruned is that the data in them
might now be used in a *future* `OP_PUBREF`.

I can see how pruning is needed for scalability, and pruning can be made
compatible with a reference to a transaction. If a transaction is pruned,
then the key material used in a prune'ed block's PUSHDATA operations are of
no value.  A user of the network shouldn't need to make this kind of
PUBREF, and if a user did want to bring a wallet back from the dead - then
the utility of PUBREF wouldn't be available to them.

Best Regards,
Mike


On Sun, Jul 28, 2019 at 7:49 PM ZmnSCPxj  wrote:

> Good morning Mike,
>
> >  I think that this implication affects other applications built on the
> blockchain, not just the PubRef proposal:
> >
>
> I believe not?
> Current applications use txids to refer to previous transactions, so even
> a short-ranged history rewrite will mostly not affect them --- they can
> just rebroadcast the transactions they are spending and get those
> reconfirmed again.
> There is admittedly a risk of double-spending, but each individual
> application can just spend deeply-confirmed transactions, and tune what it
> considers "deeply-confirmed" depending on how large the value being spent
> is.
> The point is that history rewrites are costly, but if the value being put
> in a `scriptPubKey` that uses `OP_PUBREF` is large enough, it may justify
> the cost of history rewrites --- but if the value is small, the individual
> application (which refers to transactions by their txid anyway) can
> generally assume miners will not bother to history-rewrite.
>
> Since `OP_PUBREF` would be a consensus rule, we need to select a
> "deeply-confirmed" point that is deep enough for *all* cases, unlike
> applications **on top of the blockchain** which can tune their rule of
> "deeply-confirmed" based on value.
> Thus my suggestion to use 100, which we consider "deep enough" to risk
> allowing miners to sell their coins.
>
> Lightning uses a "short channel ID" which is basically an index of block
> number + index of transaction + index of output to refer to channels.
> This is not a problem, however, even in case of short-ranged history
> rewrites.
> The short channel ID is only used for public routing.
> Between the channel counterparties, no security is based on short channel
> ID being stable; it just loses you potential routing fees from the channel
> (and can be fixed by increasing your "deeply-confirmed" enough level before
> you announce the channel for public routing).
>
> >  > There is a potential for a targeted attack where a large payout going
> to a `scriptPubKey` that uses `OP_PUBREF` on a recently-confirmed
> transaction finds that recently-confirmed transaction is replaced with one
> that pays to a different public key, via a history-rewrite attack.
> >  > Such an attack is doable by miners, and if we consider that we accept
> 100 blocks for miner coinbase maturity as "acceptably low risk" against
> miner shenanigans, then we might consider that 100 blocks might be
> acceptable for this also.
> >  > Whether 100 is too high or not largely depends on your risk appetite.
> >
> > I agree 100% this attack is unexpected and very interesting.
>
> It is precisely because of this possibility that we tend to avoid making
> SCRIPT validity dependent on anything that is not in the transaction.
> We would have to re-evaluate the SCRIPT every time there is a chain tip
> reorganization (increasing validation CPU load), unless we do something
> like "only allow `OP_PUBREF` to data that is more than 100 blocks
> confirmed".
>
> >  However, I find the arbitrary '100' to be unsatisfying - I'll have to
> do some more digging. It would be interesting to trigger this on the
> testnet to see what happens.  Do you know if anyone has pushed these
> limits?  I am so taken by this attack I might attempt it.
> >
> >  > Data derived from > 220Gb of perpetually-growing blockchain is
> hardly, to my mind, "only needs an array".
> >
> > There are other open source projects that have to deal with larger data
> sets and have accounted for the real-world limits on computability. Apache
> HTTPD's Bucket-Brigade comes to mind, which has been well tested and can
> account for limited RAM when accessing linear data structures. For a more
> general purpose utility leveldb (bsd-license) provides random access to
> arbitrary data collections.
>
> Which is the point: we need to use something, the details need to be
> considered during 

Re: [bitcoin-dev] PubRef - Script OP Code For Public Data References

[Mike Brooks via bitcoin-dev]

ZmnSCPxj,

 I think that this implication affects other applications built on the
blockchain, not just the PubRef proposal:

 > There is a potential for a targeted attack where a large payout going to
a `scriptPubKey` that uses `OP_PUBREF` on a recently-confirmed transaction
finds that recently-confirmed transaction is replaced with one that pays to
a different public key, via a history-rewrite attack.
 > Such an attack is doable by miners, and if we consider that we accept
100 blocks for miner coinbase maturity as "acceptably low risk" against
miner shenanigans, then we might consider that 100 blocks might be
acceptable for this also.
 > Whether 100 is too high or not largely depends on your risk appetite.

I agree 100% this attack is unexpected and very interesting.  However, I
find the arbitrary '100' to be unsatisfying - I'll have to do some more
digging. It would be interesting to trigger this on the testnet to see what
happens.  Do you know if anyone has pushed these limits?  I am so taken by
this attack I might attempt it.

 > Data derived from > 220Gb of perpetually-growing blockchain is hardly,
to my mind, "only needs an array".

There are other open source projects that have to deal with larger data
sets and have accounted for the real-world limits on computability. Apache
HTTPD's Bucket-Brigade comes to mind, which has been well tested and can
account for limited RAM when accessing linear data structures. For a more
general purpose utility leveldb (bsd-license) provides random access to
arbitrary data collections.  Pruning can also be a real asset for PubRef.
If all transactions for a wallet have been pruned, then there is no need to
index this PubRef - a validator can safely skip over it.

Best Regards,
Mike

On Sun, Jul 28, 2019 at 6:46 PM ZmnSCPxj  wrote:

> Good morning Mike,
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐ Original Message ‐‐‐
> On Sunday, July 28, 2019 4:03 AM, Mike Brooks  wrote:
>
> > Hey ZmnSCPxj,
> >
> > As to your first point.  I wasn't aware there was so much volatility at
> the tip, also 100 blocks is quite the difference!  I agree no one could
> references a transaction in a newly formed blocks, but I'm curious how this
> number was chosen. Do you have any documentation or code that you can share
> related to how re-orgs are handled? Do we have a kind of 'consensus
> checkpoint' when a re-org is no longer possible? This is a very interesting
> topic.
> >
>
> Miner coinbases need 100 blocks for maturity, which is the basis of my
> suggestion to use 100 blocks.
> It might be too high, but I doubt there will be good reason to be less
> than 100.
>
> There is a potential for a targeted attack where a large payout going to a
> `scriptPubKey` that uses `OP_PUBREF` on a recently-confirmed transaction
> finds that recently-confirmed transaction is replaced with one that pays to
> a different public key, via a history-rewrite attack.
> Such an attack is doable by miners, and if we consider that we accept 100
> blocks for miner coinbase maturity as "acceptably low risk" against miner
> shenanigans, then we might consider that 100 blocks might be acceptable for
> this also.
> Whether 100 is too high or not largely depends on your risk appetite.
>
> >  A validator only needs an array of PUSHDATA elements and can then
> validate any given SCRIPT at O(1).
>
> Data derived from > 220Gb of perpetually-growing blockchain is hardly, to
> my mind, "only needs an array".
> Such an array would not fit in memory for many devices that today are
> practical for running fullnodes.
> It is keeping that array and indexing it which is the problem, i.e. the
> devil in the details.
>
> Reiterating also, current pruned nodes did not retain that data and would
> be forced to re-download the entire blockchain.
> Unless you propose that we can refer only to `OP_PUSHDATA` after
> activation of `OP_PUSHREF`.
>
> Regards,
> ZmnSCPxj
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] PubRef - Script OP Code For Public Data References

[Mike Brooks via bitcoin-dev]

Hey ZmnSCPxj,

As to your first point.  I wasn't aware there was so much volatility at the
tip, also 100 blocks is quite the difference!  I agree no one could
references a transaction in a newly formed blocks, but I'm curious how this
number was chosen. Do you have any documentation or code that you can share
related to how re-orgs are handled? Do we have a kind of 'consensus
checkpoint' when a re-org is no longer possible? This is a very interesting
topic.

 > * It strongly encourages pubkey reuse, reducing privacy.
Privacy-aware users are free to have single-use p2sh transactions, and they
are free to use the same SCRIPT opcodes we have now.  Adding an extra
opcode helps with the utility of SCRIPT by compressing the smallest SegWit
transactions by a further 40% from 233 bytes to 148 bytes.  Cost savings is
a great utility - and it need not undermine anyones privacy. The resulting
p2sh SCRIPT could end up using public key material that could be compressed
with a PubRef - everyone wins.

 > * There is a design-decision wherein a SCRIPT can only access data in
the transaction that triggers its execution.
In order for a compression algorithm like LZ78 to be written in a
stack-based language like SCRIPT, there needs to be pointer arithmetic to
refer back to the dictionary or a larger application state.  If Bitcoin's
entire stack was made available to the SCRIPT language as an application
state, then LZ78-like compression could be accomplished using PubRef. If a
Script can reuse a PUSHDATA, then transactions will be less repetitious...
and this isn't free.  There is a cost in supporting this opcode.

Giving the SCRIPT language access to more data opens the door for
interesting algorithms, not just LZ78.  This is interesting to discuss how
this application state could be brought to the language.  It strikes me
that your concerns(ZmnSCPxj), as well as the topic of pruning brought up by
others (including Pieter Wuille) could be fixed by the creation of a
side-chain of indexes.  A validator would not need a hash table which is
only needed for O(1) PUBREF creation, these nodes need not be burdened with
this added index.  A validator only needs an array of PUSHDATA elements and
can then validate any given SCRIPT at O(1).

Just a thought.

Best Regards,
Mike


On Fri, Jul 19, 2019 at 11:08 AM ZmnSCPxj  wrote:

> Good morning Mike,
>
> > PubRef is not susceptible to malleability attacks because the blockchain
> is immutable.
>
> This is not quite accurate.
> While very old blocks are indeed immutable-in-practice, chain tips are
> not, and are often replaced.
> At least specify that such data can only be referred to if buried under
> 100 blocks.
>
> --
>
> There are a number of other issues:
>
> * It strongly encourages pubkey reuse, reducing privacy.
> * There is a design-decision wherein a SCRIPT can only access data in the
> transaction that triggers its execution.
>   In particular, it cannot access data in the block the transaction is in,
> or in past blocks.
>   For example, `OP_CHECKLOCKTIMEVERIFY` does not check the blockheight of
> the block that the transaction is confirmed in, but instead checks only
> `nLockTime`, a field in the transaction.
>   * This lets us run SCRIPT in isolation on a transaction, exactly one
> time, when the transaction is about to be put into our mempool.
> When a new block arrives, transactions in our mempool that are in the
> block do not need to have their SCRIPTs re-executed or re-validated.
>
> > In order for a client to make use of the PUBREF operations they’ll need
> access to a database that look up public-keys and resolve their PUBREF
> index.  A value can be resolved to an index with a hash-table lookup in
> O(1) constant time. Additionally, all instances of PUSHDATA can be indexed
> as an ordered list, resolution of a PUBREF index to the intended value
> would be an O(1) array lookup.  Although the data needed to build and
> resolve public references is already included with every full node,
> additional computational effort is needed to build and maintain these
> indices - a tradeoff which provides smaller transaction sizes and relieving
> the need to store repetitive data on the blockchain.
>
> This is not only necessary at the creator of the transaction --- it is
> also necessary at every validator.
>
> In particular, consider existing pruning nodes, which cannot refer to
> previous block data.
>
> We would need to have another new database containing every `PUSHDATA` in
> existence.
> And existing pruning nodes would need to restart from genesis, as this
> database would not exist yet.
>
> Regards,
> ZmnSCPxj
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] PubRef - Script OP Code For Public Data References

[Mike Brooks via bitcoin-dev]

Fungibility is a good question for inductive reasoning.  After all, what is
a claim without some rigger?

There exists some set of wallets 'w' which contain a balance of satoshi too
small to recover because it doesn't meet the minimum transaction fee
required to confirm the transaction.  These wallets are un-spendable by
their very nature - and quantifying un-spendable wallets is one way to
measure the fungibility of Bitcoin.  The number of un-spendable wallets can
be quantified as follows:

   Let 'p' equal the current price/per-bit for a transaction
   Let 'n' equal the number of bits in the transaction
   Let '[a]' be the set of all wallets with a balance
   Let '[w]' be the set of un-spendable wallets
   [w0] = [a] > b*n

Now, let's introduce a savings measure 'k' which is a constant flat savings
per transaction.

   [w1] = [a] > b*(n - k0)

As the savings 'k' increase, the set of 'w' also increases in size.
   len([w0]) < len([w1]) ... < len([wk])

In this case 'k0' could be the savings from a P2PKH transaction to a 233
byte SegWit transaction, and 'k1' could be 148 byte SegWit+PubRef
transaction, and the same model can be used for some future transaction
type that is even smaller.   As the savings 'k' approaches infinity the set
of un-spendable wallets approaches zero.

If a user is privacy-aware, and chooses to use single-use p2sh for all
transactions, then these users can still gain from PubRef because
block-weight should be decreased for everyone. There are cases where a user
or merchant might want to reuse their p2sh hash - and PubRef can provide
savings.  Additionally, the resulting p2sh script could be a multi-sig
transaction which could still benefit from PubRef compression.  PubRef
improves fungibility of Bitcoin in two different ways - both reduced cost
of transaction and increasing the max number of transactions that are able
to be confirmed by a block. Which is pretty hot - QED.

On Fri, Jul 19, 2019 at 3:48 PM Yuval Kogman 
wrote:

> Hi,
>
> On Fri, 19 Jul 2019 at 17:49, Mike Brooks  wrote:
>
>> Users will adopt whatever the client accepts - this feature would be
>> transparent.
>>
>
> My skepticism was based in an assumption on my part that most such data is
> produced by actors with a track record of neglecting transaction
> efficiency. I'd be happy to be proven wrong, but considering say usage
> rates of native witness outputs, or the fraction of transactions with more
> than 2 outputs so far I see little evidence in support of widespread
> adoption of cost saving measures. Assuming this is intended as a new script
> version, all fully validating nodes need to commit to keeping all data
> indefinitely before they can enforce the rules that make transactions
> benefiting from this opcode safe to broadcast.
>
> That said, if successful, the main concern is still that of address reuse
> - currently there is no incentive in the protocol to do that, and with
> BIP32 wallets fewer reasons to do it as well, but this proposal introduces
> such an incentive for users which would otherwise generate new addresses
> (disregarding the ones that already reuse addresses anyway), and this is
> problematic for privacy and fungibility.
>
> Since address reuse has privacy concerns, I think it's important to draw a
> distinction between clients accepting and producing such transactions, if
> the latter were done transparently that would be very concerning IMO, and
> even the former would not be transparent for users who run currently
> pruning nodes.
>
> I'm not sure how an O(1) time complexity leads to DoS, that seems like a
>> very creative jump.
>>
>
> For what it's worth, that was in reference to hypothetical deduplication
> only at the p2p layer, similar to compact blocks, but on further reflection
> I'd like to retract that, as since both scenarios which I had in mind seem
> easily mitigated.
>
>   Based on this response, it makes me want to calculate the savings, what
>> if it was a staggering reduction in the tree size?
>>
>
> Assuming past address reuse rates are predictive this only places an upper
> bound on the potential size savings, so personally I would not find that
> very compelling. Even if the realized size savings would be substantial,
> I'm not convinced the benefits outweigh the downsides (increased validation
> costs, monotonically growing unprunable data, and direct incentive for
> address reuse), especially when compared to other methods/proposals that
> can reduce on chain footprint generally improve privacy while reducing
> validation costs for others (e.g. batching, lightning, MAST for
> sufficiently large scripts, Schnorr signatures (musig, adaptor signatures),
> {tap,graft}root, ).
>
> Regards,
> Yuval
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] PubRef - Script OP Code For Public Data References

[Mike Brooks via bitcoin-dev]

I noticed that this Merkle tree we are building is made more expensive by
including repetitive data.  So, this proposal draws inspiration from LZ78,
an algorithm which constructs a dictionary of repetitive strings which are
then referred to by their index. What if the blockchain already built a
dictionary for us, and now we just need to index it?

---

Abstract

This BIP describes how a new OP code can be used to construct smaller, more
compact transactions.  With a public reference (PubRef), a newly created
transaction can reuse elements of a previously confirmed transaction by
representing this information with a smaller numeric offset or “pointer”.

Motivation

Giving scripts the ability to refer to data on the blockchain will reduce
transaction sizes because key material does not have to be repeated in
every Script. Users of the network are rewarded with smaller transaction
sizes, and miners are able to fit more transactions into new blocks.
Pointers are a common feature and it felt like this was missing from
Bitcoin Script.

Specification

This BIP defines a new Script opcode that can be introduced with BIP-0141
(Segregated Witness (Consensus layer)). This new opcode is as follows:

Word

Opcode

Hex

Input

Output

Description

OP_PUBREF4

TBD

TBD

uint4

data

The next four bytes is an integer reference to a previously defined
PUSHDATA

Let there be an ordered list of all invocations of PUSHDATA (OP codes;
0x4c,0x4d,0x4e) across all scripts starting from the genesis block:
[t0,t2,...,tn].   With this list a newly created script can refer to a
specific PUSHDATA that was used in any previously confirmed block. The
values referenced by this list are immutable and uniform to all observers.

Lets assume there is some transaction containing a ScriptSig and
outputScript pair, here is what an input and an output script would look
like:

ScriptSig

PUSHDATA(72)[30450221008f906b9fe728cb17c81deccd6704f664ed1ac920223bb2eca918f066269c703302203b1c496fd4c3fa5071262b98447fbca5e3ed7a52efe3da26aa58f738bd342d3101]
PUSHDATA
(65)[04bca69c59dc7a6d8ef4d3043bdcb626e9e29837b9beb143168938ae8165848bfc788d6ff4cdf1ef843e6a9ccda988b323d12a367dd758261dd27a63f18f56ce77]

outputScript

DUP HASH160 PUSHDATA(20)[dd6cce9f255a8cc17bda8ba0373df8e861cb866e]
EQUALVERIFY CHECKSIG

The ScriptSig of an input typically contains the full public key which is
~65 bytes. Outputs will typically contain a hash of the public key which is
20 bytes.  Using PubRef, the public-key material shown above no longer need
to be repeated, instead the needed values can be resolved from previously
confirmed transaction.   The signature of the input must still be unique,
however, the public key can be replaced with a call to PUBREF, as shown
below:

ScriptSig

PUSHDATA(72)[30450221008f906b9fe728cb17c81deccd6704f664ed1ac920223bb2eca918f066269c703302203b1c496fd4c3fa5071262b98447fbca5e3ed7a52efe3da26aa58f738bd342d3101]
PUBREF[43123]

outputScript

DUP HASH160 PUBREF[12123] EQUALVERIFY CHECKSIG

The above call to PUBREF removed the need to include the full public-key,
or hash of the public key in a given transaction.  This is only possible
because these values where used previously in a confirmed block. If for
example a user was sending Bitcoins to a newly formed address, then no
PUBREF can be created in this case - and a outputScript using PUSHDATA
would need to be used at least once.  If a newly created wallet has never
been used on the Bitcoin network, then the full public-key will need to be
included in the ScriptSig. Once these transactions have been confirmed,
then these values will be indexed and any future script can refer to these
public-key values with a PUBREF operation.

PubRef is not susceptible to malleability attacks because the blockchain is
immutable. The PUSHDATA operation can store at most 520 bytes on the stack,
therefore a single PUBREF operation can never obtain more than 520 bytes.

In order for a client to make use of the PUBREF operations they’ll need
access to a database that look up public-keys and resolve their PUBREF
index.  A value can be resolved to an index with a hash-table lookup in
O(1) constant time. Additionally, all instances of PUSHDATA can be indexed
as an ordered list, resolution of a PUBREF index to the intended value
would be an O(1) array lookup.  Although the data needed to build and
resolve public references is already included with every full node,
additional computational effort is needed to build and maintain these
indices - a tradeoff which provides smaller transaction sizes and relieving
the need to store repetitive data on the blockchain.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev