Re: [bitcoin-dev] A Method for Computing Merkle Roots of Annotated Binary Trees

[Russell O'Connor via bitcoin-dev]

On May 28, 2017 06:09, "Russell O'Connor"  wrote:



On May 28, 2017 03:16, "Peter Todd"  wrote:

On Mon, May 22, 2017 at 06:32:38PM -0400, Russell O'Connor wrote:
> On May 22, 2017 23:05, "Peter Todd"  wrote:
>
> On Mon, May 22, 2017 at 03:05:49AM -0400, Russell O'Connor via bitcoin-dev
> wrote:
> > MerkleRoot := SHA256(SHA256(LeftRoot ⋅ RightRoot))
> > sha256Compress : Word256 × Word512 -> Word256
>
> To be clear, what math operations do you mean by "⋅" and "×"?
>
>
> By "⋅", I usually mean concatenation (though I also use it for function
> composition in one instance).   By "×", I mean the Cartesian product.

Cartesian product can mean a lot of things.

What specifically do you mean by "cartesian product" here?


Oops, I forgot to reply all.  Below is my reply.

Given two types A and B, then A × B is the type of pairs of A and B in the
sense of type theory as used in Standard ML or Haskell or other typed
languages.


To follow up, by "sha256Compress : Word256 × Word512 -> Word256" I mean
that sha256Compress is a function that takes two arguments, the first being
a 256 bit word and the second being a 512 bit word, and returns a 256 bit
word (or equivalently sha256Compress is a function that takes a pair as
input, the first component being a 256 bit word and the second component
being a 512 bit word, and returns a 256 bit word).

sha256Compress is meant to be the compression function defined by the
SHA256 standard, though nothing here depends on anything more that its type
signature.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Emergency Deployment of SegWit as a partial mitigation of CVE-2017-9230

[Eric Voskuil via bitcoin-dev]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA256

Anthony,

For the sake of argument:

(1) What would the situation look like if there was no patent?

(2) Would the same essential formulation exist if there had been a
patent on bitcoin mining ASICs in general?

(3) Would an unforeseen future patented mining optimization exhibit
the same characteristics?

(4) Given that patent is a state grant of monopoly privilege, could a
state licensing regime for miners, applied in the same scope as a
patent, but absent any patent, have the same effect?

e

On 05/26/2017 11:37 PM, Anthony Towns via bitcoin-dev wrote:
> On Fri, May 26, 2017 at 11:02:27AM +0300, Cameron Garnham via
> bitcoin-dev wrote:
>> If one assumes that the 67% of the hash rate that refuse to
>> signal for SegWit are using ASICBOOST. The entire picture of this
>> political stalemate became much more understandable.
> 
> A couple of bits of math that might be of interest:
> 
> * if 67% of the hash rate is running ASICBoost, and ASICBoost gives
> a 20% performance improvement as stated on asicboost.com and in 
> Greg's BIP proposal, then blocking ASICBoost would change the 
> balance of miners from 67%/33% to 62.8%/37.2%; resulting in a 6.3% 
> loss for income for ASICBoost miners (not 20%), and a 12.7% gain
> for non-ASICBoost miners.  In this case, total apparent hashrate
> reduces to 88.8% of what it originally was when ASICBoost is
> blocked (though the actual security either stays the same or
> increases, depending on your attack model) [0]
> 
> * if ASICBoost use is lower than that, say 33% (eg made up of 
> AntPool 18%, BTC.top 10%, ViaBTC 5%), then the shift is from
> 33%/67% to 29.1%/70.9%, and results in a 13% loss for ASICBoost
> miners, versus a 6% gain for non-ASICBoost miners. In these cases,
> a price rise in the region of 7% to 15% due to blocking ASICBoost
> would be enough to make everyone better off [1].
> 
> * AIUI there are three feasible ways of doing ASICBoost: overt via 
> the version field, semi-covert via mining an empty block and
> grinding the coinbase extra nonce, and fully covert by reordering
> the block transaction merkle tree. If the fully covert method is
> made infeasible via a secondary merkle commitment in the coinbase a
> la segwit, and for whatever reason overt ASICBoost isn't used, then
> empty block mining is still plausible, though presumably becomes
> unprofitable when the extra 20% of block subsidy is less than the
> fees for a block.  That's adds up to fees per block totalling
> greater than 2.5BTC, and 2.5BTC/1MB is 250 satoshis per byte, which
> actually seems to be where fees are these days, so unless they're
> getting more than the claimed 20% benefit, people mining empty
> blocks are already losing money compared to just mining normally...
> (Of course, 250 satoshis per byte is already fairly painful, and
> only gets more so as the price rises)
> 
> Personally, I expect any technical attempt to block ASICBoost use
> to fail or result in a chain split -- 67% of miners losing 6% of
> income is on the order of $5M a month at current prices. Having an
> approach that is as simple as possible (ie, independent from
> segwit, carefully targetted, and impossible to oppose for any
> reason other than wanting to use ASICBoost) seems optimal to me,
> both in that it has the highest chance to succeed, and provides the
> most conclusive information if/when it fails.
> 
> Cheers, aj
> 
> [0] Assuming ASICBoost miners have hardware capable of doing A
> hashes with ASICBoost turned off, or A*B (B=1.2) with ASICBoost
> turned on, and the remainder of miners have a total hashrate of R.
> Then overall hashrate is currently H=A*B+R, and ASICBoost hashrate
> is a = A*B/(A*B+R), with a = 67% if the quoted claim is on the
> money. Rearranging:
> 
> a = A*B/(A*B+R) a*(A*B+R) = A*B a*A*B + a*R = A*B a*R = (1-a)*A*B R
> = (1/a-1)*A*B
> 
> So a' = A/(A+R), the ASICBoost miner's hashrate if they're forced
> to turn ASICBoost off, is:
> 
> a' = A/(A+R) a' = A/(A+(1/a-1)*A*B) = 1/(1+(1/a-1)*B)
> 
> But if a=0.67 and B=1.2, then a' = 0.628.
> 
> The ratio of what they are getting to what they would getting is 
> just a/a',
> 
> a/a' = a*(1+(1/a-1)*B) = (a+(1-a)*B)
> 
> and their loss is a/a'-1, which is:
> 
> a/a'-1 = (a+(1-a)*B) - 1 = (a+(1-a)*B) - (a+1-a) = (1-a)*(B-1)
> 
> which is only 20% (B-1) when a is almost zero. When a increases
> (ie, there is a higher percentage of ASICBoost miners, as sure
> seems to be the case) the potential loss from disabling ASICBoost
> dwindles to nothing (because 1-a goes to zero and B-1 is just a
> constant).
> 
> Note that this is the case even with mining centralisation -- if
> you have 99% of the hashrate with ASICBoost, you'll still have
> 98.8% of the hashrate without it, making a 0.2% loss (though of
> course your competitors with 1% hashrate will go to 1.2%, making a
> 20% gain). The reason is you're competing with all the ASICBoost
> miners, *including your own*, for the next block, and 

Re: [bitcoin-dev] A Method for Computing Merkle Roots of Annotated Binary Trees

[Peter Todd via bitcoin-dev]

On Mon, May 22, 2017 at 06:32:38PM -0400, Russell O'Connor wrote:
> On May 22, 2017 23:05, "Peter Todd"  wrote:
> 
> On Mon, May 22, 2017 at 03:05:49AM -0400, Russell O'Connor via bitcoin-dev
> wrote:
> > MerkleRoot := SHA256(SHA256(LeftRoot ⋅ RightRoot))
> > sha256Compress : Word256 × Word512 -> Word256
> 
> To be clear, what math operations do you mean by "⋅" and "×"?
> 
> 
> By "⋅", I usually mean concatenation (though I also use it for function
> composition in one instance).   By "×", I mean the Cartesian product.

Cartesian product can mean a lot of things.

What specifically do you mean by "cartesian product" here?

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org


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

Re: [bitcoin-dev] Emergency Deployment of SegWit as a partial mitigation of CVE-2017-9230

[Anthony Towns via bitcoin-dev]

On Fri, May 26, 2017 at 11:02:27AM +0300, Cameron Garnham via bitcoin-dev wrote:
> If one assumes that the 67% of the hash rate that refuse to signal
> for SegWit are using ASICBOOST. The entire picture of this political
> stalemate became much more understandable.

A couple of bits of math that might be of interest:

 * if 67% of the hash rate is running ASICBoost, and ASICBoost gives a
   20% performance improvement as stated on asicboost.com and in
   Greg's BIP proposal, then blocking ASICBoost would change the
   balance of miners from 67%/33% to 62.8%/37.2%; resulting in a 6.3%
   loss for income for ASICBoost miners (not 20%), and a 12.7% gain for
   non-ASICBoost miners.  In this case, total apparent hashrate reduces
   to 88.8% of what it originally was when ASICBoost is blocked (though
   the actual security either stays the same or increases, depending on
   your attack model) [0]

 * if ASICBoost use is lower than that, say 33% (eg made up of
   AntPool 18%, BTC.top 10%, ViaBTC 5%), then the shift is from 33%/67%
   to 29.1%/70.9%, and results in a 13% loss for ASICBoost miners,
   versus a 6% gain for non-ASICBoost miners. In these cases, a price
   rise in the region of 7% to 15% due to blocking ASICBoost would be
   enough to make everyone better off [1].

 * AIUI there are three feasible ways of doing ASICBoost: overt via
   the version field, semi-covert via mining an empty block and grinding
   the coinbase extra nonce, and fully covert by reordering the block
   transaction merkle tree. If the fully covert method is made infeasible
   via a secondary merkle commitment in the coinbase a la segwit, and for
   whatever reason overt ASICBoost isn't used, then empty block mining is
   still plausible, though presumably becomes unprofitable when the extra
   20% of block subsidy is less than the fees for a block.  That's adds
   up to fees per block totalling greater than 2.5BTC, and 2.5BTC/1MB is
   250 satoshis per byte, which actually seems to be where fees are these
   days, so unless they're getting more than the claimed 20% benefit,
   people mining empty blocks are already losing money compared to just
   mining normally... (Of course, 250 satoshis per byte is already fairly
   painful, and only gets more so as the price rises)

Personally, I expect any technical attempt to block ASICBoost use to fail
or result in a chain split -- 67% of miners losing 6% of income is on
the order of $5M a month at current prices. Having an approach that is as
simple as possible (ie, independent from segwit, carefully targetted, and
impossible to oppose for any reason other than wanting to use ASICBoost)
seems optimal to me, both in that it has the highest chance to succeed,
and provides the most conclusive information if/when it fails.

Cheers,
aj

[0] Assuming ASICBoost miners have hardware capable of doing A hashes with
ASICBoost turned off, or A*B (B=1.2) with ASICBoost turned on, and
the remainder of miners have a total hashrate of R. Then overall
hashrate is currently H=A*B+R, and ASICBoost hashrate is a = A*B/(A*B+R),
with a = 67% if the quoted claim is on the money. Rearranging:

   a = A*B/(A*B+R)
   a*(A*B+R) = A*B
   a*A*B + a*R = A*B
   a*R = (1-a)*A*B
   R = (1/a-1)*A*B

So a' = A/(A+R), the ASICBoost miner's hashrate if they're forced to
turn ASICBoost off, is:

   a' = A/(A+R)
   a' = A/(A+(1/a-1)*A*B)
  = 1/(1+(1/a-1)*B)

But if a=0.67 and B=1.2, then a' = 0.628.

The ratio of what they are getting to what they would getting is
just a/a',

   a/a' = a*(1+(1/a-1)*B)
= (a+(1-a)*B)

and their loss is a/a'-1, which is:

 a/a'-1 = (a+(1-a)*B) - 1
= (a+(1-a)*B) - (a+1-a)
= (1-a)*(B-1)

which is only 20% (B-1) when a is almost zero. When a increases (ie,
there is a higher percentage of ASICBoost miners, as sure seems to
be the case) the potential loss from disabling ASICBoost dwindles
to nothing (because 1-a goes to zero and B-1 is just a constant).

Note that this is the case even with mining centralisation -- if you
have 99% of the hashrate with ASICBoost, you'll still have 98.8% of
the hashrate without it, making a 0.2% loss (though of course your
competitors with 1% hashrate will go to 1.2%, making a 20% gain).
The reason is you're competing with all the ASICBoost miners,
*including your own*, for the next block, and the size of the reward
you'll get for winning doesn't change.

Total apparent hashrate is A+R versus A*B+R, so

(A+R)/(A*B+R) = 1/(A/(A+R)) * (A*B/(A*B+R))/B
  = 1/a' * a/B
  = a/a' / B
  = (a+(1-a)*B) / B
  = a/B + (1-a)

(yeah, so that formula's kind of obvious...)

[1] Except maybe the patent holders (err, applicants). Though per the
recent open letter it doesn't 

Re: [bitcoin-dev] BIP149 timeout-- why so far in the future?

[Rusty Russell via bitcoin-dev]

Matt Corallo  writes:
> A more important consideration than segwit's timeout is when code can be
> released, which will no doubt be several months after SegWit's current
> timeout.

I was assuming it would be included in the next point release.

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