Re: [bitcoin-dev] Treating ‘ASICBOOST’ as a Security Vulnerability

[Cameron Garnham via bitcoin-dev]

Hello Bitcoin-Dev,

A quick update that CVE-2017-9230 has been assigned for the security 
vulnerability commonly called ‘ASICBOOST’:

"The Bitcoin Proof-of-Work algorithm does not consider a certain attack 
methodology related to 80-byte block headers with a variety of initial 64-byte 
chunks followed by the same 16-byte chunk, multiple candidate root values 
ending with the same 4 bytes, and calculations involving sqrt numbers. This 
violates the security assumptions of (1) the choice of input, outside of the 
dedicated nonce area, fed into the Proof-of-Work function should not change its 
difficulty to evaluate and (2) every Proof-of-Work function execution should be 
independent.”

I would like to especially thank the CVE team at Mitre for their suggested 
description that was more appropriate than my proposed text.

https://cve.mitre.org/cgi-bin/cvename.cgi?name=+CVE-2017-9230

Cameron.



> Begin forwarded message:
> 
> From: 
> Subject: Re: [scr-x] Bitcoin - All
> Date: 24 May 2017 at 18:52:22 GMT+3
> To: 
> Cc: 
> 
> Signed PGP part
> > [Suggested description]
> > The Bitcoin Proof-of-Work algorithm does not consider a certain attack
> > methodology related to 80-byte block headers with a variety of initial
> > 64-byte chunks followed by the same 16-byte chunk, multiple candidate
> > root values ending with the same 4 bytes, and calculations involving
> > sqrt numbers. This violates the security assumptions of (1) the choice
> > of input, outside of the dedicated nonce area, fed into the
> > Proof-of-Work function should not change its difficulty to evaluate
> > and (2) every Proof-of-Work function execution should be independent.
> >
> > --
> >
> > [Additional Information]
> > ASICBOOST, originality promoted as a patented mining optimisation(1).
> > Has under detailed study (2), become regarded as an actively exploited
> > (3), security vulnerability (4), of Bitcoin.
> >
> > The Bitcoin Proof-of-Work Algorithm is dependent on the following two
> > security assumptions that are both broken by 'ASICBOOST':
> > 1. The choice of input, outside of the dedicated nonce area, fed into
> > the Proof-of-Work function should not change it's difficulty to
> > evaluate.
> > 2.  Every Proof-of-Work function execution should be independent.
> >
> > 'ASICBOOST' creates a layer-violation where the structure of the input
> > outside of the dedicated nonce area will change the performance of the
> > mining calculations (5). 'ASICBOOST' exploits a vulnerability where
> > the Proof-of-Work function execution is not independent (6).
> >
> > References:
> > (1) Original Whitepaper by Dr. Timo Hanke: 
> > https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf
> > (2) Academic Write-up by Jeremy Rubin: 
> > http://www.mit.edu/~jlrubin//public/pdfs/Asicboost.pdf
> > (3) Evidence of Active Exploit by Gregory Maxwell:
> >  
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-April/013996.html
> > (4) Discussion to assign a CVE Number, by Cameron Garnham:
> >   
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014349.html
> > (5) Discussion of the perverse incentives created by 'ASICBOOST' by Ryan 
> > Grant:
> >   
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014352.html
> > (6) Discussion of ASICBOOST's non-independent PoW calculation by Tier Nolan:
> >   
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014351.html
> >
> > The patent holder of this particular security vulnerability has a dedicated 
> > website: https://www.asicboost.com/
> >
> > --
> >
> > [VulnerabilityType Other]
> > Cryptocurrency Mining Algorithm Weakness
> >
> > --
> >
> > [Vendor of Product]
> > Bitcoin
> >
> > --
> >
> > [Affected Product Code Base]
> > Bitcoin - All
> >
> > --
> >
> > [Affected Component]
> > Bitcoin
> >
> > --
> >
> > [Attack Type Other]
> > Cryptocurrency Proof-of-Work Algorithm Weakness
> >
> > --
> >
> > [CVE Impact Other]
> > Creation of Perverse Incentives in a Cryptocurrency
> >
> > --
> >
> > [Attack Vectors]
> > Bitcoin Mining Unfair Advantage
> > Bitcoin Layer-Violations Creating Perverse System Incentives
> >
> > --
> >
> > [Reference]
> > https://arxiv.org/ftp/arxiv/papers/1604/1604.00575.pdf
> > http://www.mit.edu/~jlrubin//public/pdfs/Asicboost.pdf
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-April/013996.html
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014349.html
> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014352.html
> > 

Re: [bitcoin-dev] Drivechain -- Request for Discussion

[CryptAxe via bitcoin-dev]

Your assumptions of the bribe process are indeed correct you seem to
have a pretty good handle on all of that.

Hopefully I can clear up a few things. BMM among other things is still a
work in progress so you'll have to wait a
bit longer before any reorg code is on github. The "ratchet" system on
github right now just has the block hash
part of the critical hash script. The completed version needs to check
the sidechain number (ID) and the sidechain
block number in the script. Also the block number can only change by +1
or -1, so when a new h* is added to the
queue it must be compared to the most recent h* in the queue.
std::abs(queue.back().nHeight - ToAdd.nHeight) must equal 1.

Here's what the script looks like on github:
Note that the h* is just a block hash.

script << OP_RETURN << ToByteVector(h*);

Here's what I'm testing right now as I'm working on BMM:

script << OP_RETURN << CScriptNum::serialize(nSidechain) <<
CScriptNum(nSidechainHeight) << ToByteVector(sidechain blinded block
hash h*)

One other thing I want to make sure is clear enough is that the block
number in the critical hash script is
a sidechain block number, not a mainchain block number. That might mess
up the new format you have
suggested for bribes. And the reason a sidechain miner would want to
refund their bribe is if the h* doesn't
end up in a coinbase after a number of blocks, making their blinded
block on the sidechain invalid as tx's
will be spent in other blocks that do get their h* in a coinbase.

We were thinking about making bribe outputs have a maturity period like
generated coins. You
think that they should be locked for >100 blocks by having OP_BRIBE also
check the lock time?

I like all of your suggestions so far, thank you for taking a look!


On 05/24/2017 03:05 AM, Tier Nolan via bitcoin-dev wrote:
> On Wed, May 24, 2017 at 9:50 AM, Tier Nolan  > wrote:
>
> OP_BRIBE_VERIFY could then operate as follows
>
>OP_BRIBE_VERIFY
>
> This causes the script to fail if
>does not match the block height, or
>is not the hash for the sidechain with
> , or
>   there is no hash for that sidechain in the block's coinbase
>
>
> I was thinking more on the process for these transactions.
>
> I assume that the process is
>
> - sidechain miner broadcasts transaction with OP_BRIBE output
> - this transaction ends up in the memory pool of miners
> - Miners add the transaction to their next block
> - Miners add a transaction which spends the output to one of their own
> addresses
>
> I think you need an additional rule that OP_BRIBE checks fails unless
> the output is locked 100 or more blocks.
>
> The output script would end up something like
>
> IF
>   OP_BRIBE_VERIFY
> ELSE
>OP_CHECKSIG
> ENDIF
>
> This output acts like "anyone can spend" for the one block height. 
> Otherwise, only the sidechain miner can spend the output.
>
> This allows the sidechain miner to reclaim their coins if the
> transaction ends up in a different block.
>
> OP_BRIBE_VERIFY would have an additional rule
>
> The script to fails if
>   one or more of the transaction outputs start with something other
> than the template
>does not match the block height, or
>is not the hash for the sidechain with
> , or
>   there is no hash for that sidechain in the block's coinbase
>
> The template is
>   <100> OP_CHECKSEQUENCE_VERIFY
>
>
> ___
> 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] Reduced signalling threshold activation of existing segwit deployment

[Erik Aronesty via bitcoin-dev]

Yes, 75% seems fine - given that there is a already a wide deployment of
segwit enforcing nodes

This implementation is 100% compatible with a "UASF movement" since, if
triggered, it essentially turns all supporting miners into equivalent
BIP148 enforcers.   This should allay any fears that this would subvert a
UASF.

The proposed "agreement" which was reached without input from the
development community also apparently requires that a hard fork be locked
in on the same bit (bit 4).

Ideally, such a 2MB increase should be scheduled using BIP103-esqe logic:
Gradually increasing from 1MB to 2MB over the course of at least a couple
years, beginning 6 months from lock-in.

This will give developers ample time to evaluate and react to network
impacts.


On Wed, May 24, 2017 at 12:02 PM, Wang Chun via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I think we should go for 75%, same Litecoin. As I have said before, 95%
> threshold is too high even for unconventional soft forks.
>
> > 在 2017年5月24日，04:58，Andrew Chow via bitcoin-dev  linuxfoundation.org> 写道：
> >
> > Ah. I see now. It wasn't very clear to me that that is what will happen.
> >
> > Also, shouldn't the timeout date be set for before the BIP141 timeout?
> > Otherwise this could lock in but not have enough time for Segwit to be
> > locked in.
> >
> >
> >> On 5/23/2017 4:42 PM, James Hilliard wrote:
> >> That is incorrect, it is compatible with the current segwit
> >> implementation because it triggers a mandatory signalling period that
> >> will activate segwit on existing nodes.
> >>
> >> On Tue, May 23, 2017 at 4:39 PM, Andrew Chow via bitcoin-dev
> >>  wrote:
> >>> Hi James,
> >>>
> >>> From what I understand, this proposal is incompatible with the current
> >>> segwit implementation with regards to the NODE_WITNESS service bit. I
> >>> believe it could cause network partitioning if the service bit is not
> >>> changed.
> >>>
> >>> Andrew
> >>>
> >>>
>  On 5/22/2017 6:40 PM, James Hilliard via bitcoin-dev wrote:
>  I would like to propose an implementation that accomplishes the first
>  part of the Barry Silbert proposal independently from the second:
> 
>  "Activate Segregated Witness at an 80% threshold, signaling at bit 4"
>  in a way that
> 
>  The goal here is to minimize chain split risk and network disruption
>  while maximizing backwards compatibility and still providing for rapid
>  activation of segwit at the 80% threshold using bit 4.
> 
>  By activating segwit immediately and separately from any HF we can
>  scale quickly without risking a rushed combined segwit+HF that would
>  almost certainly cause widespread issues.
> 
>  Draft proposal:
>  https://github.com/jameshilliard/bips/blob/bip-
> segsignal/bip-segsignal.mediawiki
> 
>  Proposal text:
>  
>   BIP: segsignal
>   Layer: Consensus (soft fork)
>   Title: Reduced signalling threshold activation of existing segwit
> deployment
>   Author: James Hilliard 
>   Status: Draft
>   Type: Standards Track
>   Created: 2017-05-22
>   License: BSD-3-Clause
>    CC0-1.0
>  
> 
>  ==Abstract==
> 
>  This document specifies a method to activate the existing BIP9 segwit
>  deployment with a majority hashpower less than 95%.
> 
>  ==Definitions==
> 
>  "existing segwit deployment" refer to the BIP9 "segwit" deployment
>  using bit 1, between November 15th 2016 and November 15th 2017 to
>  activate BIP141, BIP143 and BIP147.
> 
>  ==Motivation==
> 
>  Segwit increases the blocksize, fixes transaction malleability, and
>  makes scripting easier to upgrade as well as bringing many other
>  [https://bitcoincore.org/en/2016/01/26/segwit-benefits/ benefits].
> 
>  This BIP provides a way for a simple majority of miners to coordinate
>  activation of the existing segwit deployment with less than 95%
>  hashpower. For a number of reasons a complete redeployment of segwit
>  is difficulty to do until the existing deployment expires. This is due
>  to 0.13.1+ having many segwit related features active already,
>  including all the P2P components, the new network service flag, the
>  witness-tx and block messages, compact blocks v2 and preferential
>  peering. A redeployment of segwit will need to redefine all these
>  things and doing so before expiry would greatly complicate testing.
> 
>  ==Specification==
> 
>  While this BIP is active, all blocks must set the nVersion header top
>  3 bits to 001 together with bit field (1<<1) (according to the
>  existing segwit deployment). Blocks that do not signal as required
>  will be rejected.
> 
>  ==Deployment==
> 
>  This BIP will be deployed by a "version bits" with an 80%(this can be

[bitcoin-dev] Fwd: Re: Drivechain -- Request for Discussion

[Paul Sztorc via bitcoin-dev]

Responses below.


On 5/23/2017 7:26 PM, ZmnSCPxj wrote:
> Good morning,
> 
> 
>>>
>>> How is OP_BRIBE superior to just using a  OP_RETURN script? Cannot
>>> a sidechain scan the block for OP_RETURN attesting that the block hash
>>> is present in the block?
>>
>>The sidechain software can indeed, but the mainchain software cannot
>>(without making validation of both chains part of the mainchain, which
>>defeats the original purpose of sidechains).
>>
>>The purpose of OP_BRIBE is to allow "Sam" (on the sidechain) and "Mary"
>>(a mainchain miner) to work together. Sam would pay X BTC to Mary, if
>>Mary could provide Sam with some guarantee that Sam's sidechain block
>>[defined by h*] would make it into the largest chain.
> 
> Regarding "largest chain", do you mean mainchain or sidechain?

Sidechain. Sam is paying himself the revenues of the sidechain's block.
These are side:btc, that he gets, if this block is part of the largest
chain.
> 
> An OP_RETURN is still some guarantee that it will make it into the
> longest mainchain.  If OP_RETURN tx is in a shorter mainchain but not on
> the longer mainchain, then on the longer mainchain, the utxo's funding
> the OP_RETURN tx is still unspent and the OP_RETURN tx will still be
> mineable by any miner following the longer mainchain.  The X BTC would
> be the OP_RETURN transaction's fee, which Mary would still want to mine
> into the longest mainchain, as it is still money on the table if it is
> not mined on the longest mainchain.

As you say below, it is about the sidechain, not mainchain. (Anything
not in the longest mainchain is just discarded by everyone, as always.)
> 
> Or, does OP_BRIBE somehow assure that Sam's block goes onto the longer
> sidechain?  But then, do not side blocks refer to their previous side
> block to define the sidechain?

Yes, there is a new construction for this, which might be called "SPV
squared". Classical merged mining (ie Namecoin) does not require the
mainchain to do anything, except occasionally keep track of an ordered
list of hash commitments. BMM is different, it does require the
mainchain to keep track of a minimal amount of things. One is the total
number of sidechains, but the second is what you have hit on here.

In addition to a list of commitments (ideally, one commitment per
block), the mainchain also keeps track of the block number ( ..or, as
you'll see, perhaps "block number modulo x".. ) of recent sidechain
blocks (for the last x=65,536 mainchain blocks). It then subsets the
most recent y=4000 of these, and only allows new sidechain blocks to
appear if they have a blocknumber equal to a member of set Y', where Y'
is the set of all sidechain blocknumbers y blocks ago + 1.

Then, the sidechain nodes simply reject the block if the h* commitment
refers to a side:blockheader that has a different block number.

Perhaps these notes..

http://www.truthcoin.info/images/bmm-outline.txt

..would be helpful. Looking back, this is probably the hackiest part of
the entire system, by a wide margin, so it is good that you bring it up.

> 
> 
> Is there some predictable schedule for side->main withdrawals?  If a
> withdrawal is imminent, or if some actor can get "insider information"
> about whether a withdrawal is imminent, cannot some actor induce the
> above, with potentially shorter time to reach step 3?

Yes, these delays are parameters, which are defined per sidechain. So
once the sidechain has been 'added' to bitcoin, the schedule would be
fully predictable.

> 
> From my reading, Blockstream's sidechains proposal supports a reorg
> proof after a side->main withdrawal on the mainchain side, with a reorg
> proof burn window after the main:side->main withdrawal, preventing its
> utxo from being used.  If the reorg proof is published and shows that a
> sidechain reorg invalidates a particular side->main withdrawal, then the
> main:side->main withdrawal's utxo is burned.

In this, there is no reorg proof (the miners would simply prevent the
withdrawal from accumulating enough ACKs). A 51% miner coalition can
always filter any message they like from the blockchain, including the
reorg proofs.

> 
>>For extraordinary DAO-like situations, disinterested mainchain miners
>>merely need a single bit of information (per sidechain), which is
>>"distress=true", and indicates to them to temporarily stop ACKing
>>withdrawals from the sidechain. This alone is enough to give the reorg
>>an unlimited amount of time to work itself out.
> 
> Do you have some document containing these details?  I cannot find this
> in the blog posts I've read so far.

This specific detail is not documented. I feel it is comparable to, for
example, the March 2013 chain fork.

> 
I feel that my proposal is more secure, as it can operate healthily and
>>> quickly while using spv proofs which are much slower and much much
>>> easier to audit.
>>>
>>> I don't quite understand how Drivechain handles sidechain reorgs, while
>>> keeping Bitcoin miners blinded. It 

Re: [bitcoin-dev] Proposal to allow users to configure the maximum block weight based on a support threshold

[Tomas via bitcoin-dev]

On Wed, May 24, 2017, at 04:42, Erik Aronesty wrote:
> Instead of block thresholds, use utxo bits to coordinate size changes
> (larger and smaller should be allowed).> 
> There is no reason for miners to be involved in a decision to change
> this aspects of the protocol.   Plenty of other ways to coordinate.
Miners cannot change the block size or any other rule without support of
the users, because their blocks and coins would be rejected. This
mechanism that Bitcoin brought us, has been working fine and I see no
reason to change it with utxo bits.
I *only* propose an optional way  to synchronize changes without the
need of off chain agreements, which seems like a simple improvement over
the current situation.

> 
> Otherwise someone can make it seem to a miner like 99pct of nodes are
> ready for a larger weight even though that's false.
I agree that the user agent signalling isn't very important, and I think
that most of us aware that you cannot rely on counting them.
> 
> On May 23, 2017 8:03 AM, "Tomas via bitcoin-dev"  d...@lists.linuxfoundation.org> wrote:>> I have a proposal that would allow 
> each user to optionally
>> configure the>>  maximum block weight at a support threshold.
>> 
>>  It recognizes that there is no need for off chain bickering, by
>>  providing a mechanism that lets each users freely choose their own
>>  parameters while still maintaining full coordination of any changes.>> 
>>  The BIP can be found here:
>> 
>> https://github.com/tomasvdw/bips/blob/master/bip-changing-the-maximum-block%20weight-based-on-a-support-threshold.mediawiki>>
>>  
>>  It is worth noting that this proposal does neither gives more
>>  power to>>  miners nor reduces decentralization. Miners still rely on their
>>  blocks>>  being accepted by economic nodes to sell their minted coins. This
>>  proposal doesn't change that.
>> 
>>  Regards,
>>  Tomas van der Wansem
>>  bitcrust
>>  ___
>>  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] Drivechain -- Request for Discussion

[Tier Nolan via bitcoin-dev]

On Tue, May 23, 2017 at 3:22 PM, Paul Sztorc  wrote:

>
> If you haven't seen http://www.truthcoin.info/blog/drivechain/ , that is
> probably the most human-readable description.
>

I guess I was looking for the detail you get in the code, but without
having to read the code.

My quick reading gives that the sidechain codes (critical hashes) are added
when a coinbase is processed.

Any coinbase output that has the form "OP_RETURN <32 byte push>" counts as
a potential critical hash.

When the block is processed, the key value pair (hash, block_height) is
added to a hash map.

The OP_BRIBE opcode checks that the given hash is in the hash map and
replaces the top element on the stack with the pass/fail result.

It doesn't even check that the height matches the current block, though
there is a comment that that is a TODO.

I agree with ZmnSCPxj, when updating a nop, you can't change the stack.  It
has to fail the script or do nothing.

OP_BRIBE_VERIFY would cause the script to fail if the hash wasn't in the
coinbase, or cause a script failure otherwise.

Another concern is that you could have multiple bribes for the same chain
in a single coinbase.  That isn't fair and arguably what the sidechain
miner is paying for is to get his hash exclusively into the block.

I would suggest that the output is

OP_RETURN  

Then add the rule that only the first hash with a particular sidechain id
actually counts.

This forces the miner to only accept the bribe from 1 miner for each
sidechain for each block.  If he tries to accept 2, then only the first one
counts.

OP_BRIBE_VERIFY could then operate as follows

   OP_BRIBE_VERIFY

This causes the script to fail if
   does not match the block height, or
   is not the hash for the sidechain with , or
  there is no hash for that sidechain in the block's coinbase

If you want reduce the number of drops, you could serialize the info into a
single push.

This has the advantage that a sidechain miner only has to pay if his block
is accepted in the next bitcoin block.  Since he is the only miner for that
sidechain that gets into the main bitcoin block, he is pretty much
guaranteed to form the longest chain.

Without that rule, sidechain miners could end up having to pay even though
it doesn't make their chain the longest.

How are these transactions propagated over the network?  For relaying, you
could have the rule that the opcode passes as long as  is
near the current block height.  Maybe require that they are in the future.
They should be removed from the memory pool once the block height has
arrived, so losing miners can re-spend those outputs.

This opcode can be validated without needing to look at other blocks, which
is good for validating historical blocks.

I am still looking at the deposit/withdrawal code.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev