[bitcoin-dev] Segwit Upgrade Procedures & Block Extension Data

[bitcoin-dev] Segwit Upgrade Procedures & Block Extension Data

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 5956 bytes --]

A few notes on upgrade procedures associated with segregated witnesses:


Initial Deployment
==================

While segregated witnesses is a soft-fork, because it adds new data
blocks that old nodes don't relay segwit nodes can't sync from
non-segwit nodes and still be fully validating; once the segwit softfork
has activated full nodes need witness data to function. This poses a
major problem during deployment: if full node adoption lags miner
adoption, the segwit-supporting P2P network can partition and lose
consensus.

While Pieter Wuille's segwit branch(1) doesn't yet implement a fix for
the above problem, the obvious thing to do is to add a new service bit
such as NODE_SEGWIT, and/or bump the protocol version, and for outgoing
peers only connect to peers with segwit support. Interestingly, a
closely related problem already exists in Bitcoin Core: neither addrman
nor the outgoing connection thread takes what service bits a peer
advertises into account. So if a large number of non-block-relaying
nodes joined the network and advertised their addresses the network
could, in theory, partition even without an explicit attack. (My own
full-RBF fork of Bitcoin Core does fix(2) this issue, though by
accident!)

Note how because of this the segwit soft-fork has properties not unlike
hard-forks in terms of the need for nodes to upgrade with regard to the
P2P layer. Even with the above fix, the worst case would be for segwit
to not be adopted widely by full node operators, resulting in a network
much more vulnerable to attacks such as DoSing nodes. This is one of the
(many) reasons why hard-forks are generally significantly more dangerous
than soft-forks.


Future Upgrades
===============

Segwit isn't going to be the last thing that adds new block data. For
example, my own prev-block-proof proposal(3) requires that blocks commit
to another tree, which itself is calculated using a nonce that must be
passed along with the block data. (U)TXO commitments are another
possible future example.

BIP141 (currently) suggests an Extensible Commitment Structure(4)
consisting of a hashed linked list of consensus-critical commitments,
with a redefinable nonce at the end of the list for future soft-forks.
Currently this nonce is put into the otherwise useless, and non-hashed,
witness for the coinbase transaction(6) and a block is invalid if its
witness contains more than that single nonce.(7)

Unfortunately, this means that the next soft-fork upgrade to add
additional data will have the above relaying problem all over again!
Even a minimal upgrade adding a new commitment - like my
prev-block-proof proposal - needs to at least add another nonce for
future upgrades. In addition to having to upgrade full nodes, this also
requires systems like the relay network to upgrade, even though they may
not themselves otherwise need to care about the contents of blocks.

A more subtle implication of this problem is how do you handle parallel
upgrades, as proposed by BIP9? Splitting the P2P network into
non-upgraded nodes, and a much smaller group of upgraded nodes, is bad
enough when done every once in a awhile. How does this look with more
frequent upgrades, not necessarily done by teams that are working
closely with each other?


Proposal: Unvalidated Block Extension Data
==========================================

1) Remove the restriction that the coinbase witness contain exactly one
   32byte value.

2) Hash the contents of the coinbase witness (e.g. as a merkle tree) and
   commit them in place of the current nonce commitment.

3) Include that data in the blocksize limit (to prevent abuse).

Now future soft-forks can simply add additional data, which non-upgraded
nodes simply see as extension data that they don't know how to fully
validate. All nodes can however validate that data came from the miner,
and thus they can freely propagate that data without risk of attack
(Bitcoin Core used to allow additional data to be included with
transactions, which was used in a DoS attack (CVE-2013-4627)).

This is more efficient than it may appear at first glace. As most future
upgrades are expected to be additional commitments where full nodes can
deterministically recalculate the commitment, the additional data for
each new commitment is just 32 bytes.

A significant design consideration is that if arbitrary data can be
added, it is very likely that miners will make use of that ability for
non-Bitcoin purposes; we've already run into problems deploying segwit
itself because of pools using the coinbase space for advertising and
merge-mining. Avoiding this problem is easiest with a merkelized
key:value mapping, with the ability to use collision-resistant ID's as
keys (e.g. UUID).

Secondly, does using the coinbase witness for this really make sense?
Logically it'd make more sense to change the way blocks are serialized,
much the same way transaction serialization was changed to accomodate
segwit; stuffing this in the coinbase witness smells like a hack. (along
those lines, note how witnesses themselves could have been implemented
this way - probably too late to change now)


References
==========

1) https://github.com/sipa/bitcoin/tree/segwit

2) https://github.com/petertodd/bitcoin/blob/replace-by-fee-v0.12.0rc2/src/net.cpp#L1616

3) http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-December/012103.html

5) https://github.com/bitcoin/bips/blob/6a315c023f13d83c58aab98cf8668d74cf7566c7/bip-0141.mediawiki#Extensible_commitment_structure

6) https://github.com/sipa/bitcoin/blob/37973bf2efd7a558c86bf35455a1355e5b0d5d64/src/main.cpp#L3212

7) https://github.com/sipa/bitcoin/blob/37973bf2efd7a558c86bf35455a1355e5b0d5d64/src/main.cpp#L3209

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

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [bitcoin-dev] Segwit Upgrade Procedures & Block Extension Data

[Anthony Towns]

[-- Attachment #1: Type: text/plain, Size: 5808 bytes --]

On Thu, Jan 28, 2016 at 01:51:24PM -0500, Peter Todd via bitcoin-dev wrote:
> While Pieter Wuille's segwit branch(1) doesn't yet implement a fix for
> the above problem, the obvious thing to do is to add a new service bit
> such as NODE_SEGWIT, and/or bump the protocol version, and for outgoing
> peers only connect to peers with segwit support.

If I'm following the code right, the segwit branch has a fHaveWitness
flag for each connection, which is set when a HAVEWITNESS message comes
from the peer, and HAVEWITNESS is sent as part of handshaking. BIP144
suggests maybe this should be changed to a service bit though:

https://github.com/bitcoin/bips/blob/master/bip-0144.mediawiki

If you've got a limit of 8 outgoing connections and >4 of them don't
support witnesses, would it be enough to just drop a non-witness
connection and try a new one? Or is anything less than 8 of 8 outgoing
witness supporting connections likely to be bad for the network?

> Future Upgrades
> ===============
> Segwit isn't going to be the last thing that adds new block data. For
> example, my own prev-block-proof proposal(3) requires that blocks commit
> to another tree, which itself is calculated using a nonce that must be
> passed along with the block data. (U)TXO commitments are another
> possible future example.

Commitments to a merkle sum tree of transaction bytes, sigops, sighash
bytes, fees, priority, etc for small fraud proofs also fit here,
don't they?

> Unfortunately, this means that the next soft-fork upgrade to add
> additional data will have the above relaying problem all over again!

This isn't necessarily true -- you could just make the coinbase witness
nonce become HASH(newinformation | newnonce), and put newnonce back into
the coinbase as an additional OP_RETURN, so that it can be verified.

If you want to have layered soft-forks adding new commitments, I think
you have to keep adding 32 byte hashed nonces; dropping them would be
a hard fork as far as I can see. So if there might eventually be three
or four of them, putting them in the witness block rather than the base
block seems sensible to me.

> Proposal: Unvalidated Block Extension Data
> ==========================================
> 1) Remove the restriction that the coinbase witness contain exactly one
>    32byte value.

+1.

If the linked list approach in BIP141 is used, then I think the logic
could be something like this:

 * suppose there have been a few soft-forks and the coinbase witness
   now handles three commitments: segwit, prevblockproof, fraudproofs

 * then the coinbase witness stack should have at least 3 32-byte
   values pushed on it, which should evaluate to:

     s[1] = HASH( fraudproof-info ; s[2] )
     s[0] = HASH( prevblockproof-info ; s[1] )

   and the coinbase should include

     OP_RETURN SHA256d( segwit-info ; s[0] )

 * old segwit code works fine (assuming the stack.size() != 1 check is
   changed to == 0), just treating s[0] as a meaningless nonce

 * old prevblockproof supporting nodes check s[0], treating s[1] as a
   meaningless nonce, but still validating the prevblock proofs

 * nodes running the latest code validate all three checks, and will
   continue to work if new checks are soft-forked in later

> 2) Hash the contents of the coinbase witness (e.g. as a merkle tree) and
>    commit them in place of the current nonce commitment.

But I think this seems just as good, and a fair bit simpler. ie with the
same three commitments, the coinbase witness contains:

     s[2] = nonce
     s[1] = fraudproof-info-hash
     s[0] = prevblockproof-info-hash

and coinbase includes:

     OP_RETURN SHA256d( HASH(segwit-info) ; s[0] ; s[1] ; s[2] ; ... )

I'm not sure if the use of a nonce has any value if done this way.

With this apporach, the commitments could be ordered arbitrarily --
you only have to check that "fraudproof-info-hash" is somewhere on the
stack of the coinbase witness, not that it's s[1] in particular.

I think it makes sense to plan on cleaning these up with infrequent
hard forks, eg one that combines the transactions hashMerkleRoot
and the witnessMerkleRoot and the fraudProofMerkleSumRoot and the
prevBLockProofHash into a single entry in the block header, but being
able to add features with soft-forks in the meantime seems like a win.

> 3) Include that data in the blocksize limit (to prevent abuse).

Including it in the coinbase witness already includes it in the blocksize
limit, albeit discounted, no? If someone wants to propose a soft-fork
adding 500kB of extra consensus-critical data to each block for some
reason, sticking it in the coinbase witness seems about the least
offensive way to do it?

> Secondly, does using the coinbase witness for this really make sense?

If you look at the witness as a proof of "this is why it's okay to
accept this transaction" in general, and the coinbase witness is "this
is why it's okay to accept this block", then including prevblock proofs
and fraud proof info in the coinbase witness seems pretty logical... Or
at least, it does to me.

This topic seems to be being discussed in a PR on the segwit branch:

  https://github.com/sipa/bitcoin/pull/48

where there's a proposal to have the coinbase witness include the merkle
path to the segwit data, so, if I understand it right, the coinbase
commitment might be:

  OP_RETURN Hash( s[0] || Hash( Hash( s[2] || segwit-data ) || s[1] ) )

if the path to the segwit data happened to be right-left-right. That
would still make it hard to work out the path to some proof that happened
to be in position right-right-left, though, so it seems inferior to the
approaches described above to me...

Cheers,
aj


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [bitcoin-dev] Segwit Upgrade Procedures & Block Extension Data

[Anthony Towns]

[-- Attachment #1: Type: text/plain, Size: 837 bytes --]

On Sun, Jan 31, 2016 at 01:32:26AM +1000, Anthony Towns via bitcoin-dev wrote:
> On Thu, Jan 28, 2016 at 01:51:24PM -0500, Peter Todd via bitcoin-dev wrote:
> > While Pieter Wuille's segwit branch(1) doesn't yet implement a fix for
> > the above problem, the obvious thing to do is to add a new service bit
> > such as NODE_SEGWIT, and/or bump the protocol version, and for outgoing
> > peers only connect to peers with segwit support.
> If I'm following the code right, the segwit branch has a fHaveWitness
> flag for each connection, which is set when a HAVEWITNESS message comes
> from the peer, and HAVEWITNESS is sent as part of handshaking. BIP144
> suggests maybe this should be changed to a service bit though:

Oh, there's a PR to change this to a NODE_WITNESS service bit:

https://github.com/sipa/bitcoin/pull/55

Cheers,
aj


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [bitcoin-dev] Segwit Upgrade Procedures & Block Extension Data

[Pieter Wuille]

On Thu, Jan 28, 2016 at 7:51 PM, Peter Todd via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> A few notes on upgrade procedures associated with segregated witnesses:

> While Pieter Wuille's segwit branch(1) doesn't yet implement a fix for
> the above problem, the obvious thing to do is to add a new service bit
> such as NODE_SEGWIT, and/or bump the protocol version, and for outgoing
> peers only connect to peers with segwit support.

Agree, I've merged the changes to switch to a service bit instead.
We'll need further changes to prefer connecting to segwit nodes.

> Segwit isn't going to be the last thing that adds new block data. For
> example, my own prev-block-proof proposal(3) requires that blocks commit
> to another tree, which itself is calculated using a nonce that must be
> passed along with the block data. (U)TXO commitments are another
> possible future example.

> Unfortunately, this means that the next soft-fork upgrade to add
> additional data will have the above relaying problem all over again!
> Even a minimal upgrade adding a new commitment - like my
> prev-block-proof proposal - needs to at least add another nonce for
> future upgrades. In addition to having to upgrade full nodes, this also
> requires systems like the relay network to upgrade, even though they may
> not themselves otherwise need to care about the contents of blocks.

Those are good arguments for making the witness data more extensible.
>
> A more subtle implication of this problem is how do you handle parallel
> upgrades, as proposed by BIP9? Splitting the P2P network into
> non-upgraded nodes, and a much smaller group of upgraded nodes, is bad
> enough when done every once in a awhile. How does this look with more
> frequent upgrades, not necessarily done by teams that are working
> closely with each other?

I don't expect that changes that add more data to be relayed with
blocks will be frequent, though I certainly agree there may be some.

> Proposal: Unvalidated Block Extension Data
> ==========================================

(snip)

This will need a backward-incompatible change to the current segwit
change anyway, so at the risk of more bikeshedding, let me propose
going a bit further:

* The coinbase scriptSig gets a second number push (similar to the
current BIP34 height push), which pushes a number O. O is a byte
offset inside the coinbase transaction (excluding its witness data)
that points to a 32-byte hash H. This is more flexible and more
compact than what we have now (a suggestion by jl2012).
* H is the root of a Merkle tree, whose leaves are the hashes of the
coinbase witness's stack items.
* Item 0 of the coinbase witness stack must be 32 bytes, and must be
equal to the witness tree root.
* No further restrictions on the rest of the stack items; these can be
used for future commitments.

> A significant design consideration is that if arbitrary data can be
> added, it is very likely that miners will make use of that ability for
> non-Bitcoin purposes; we've already run into problems deploying segwit
> itself because of pools using the coinbase space for advertising and
> merge-mining. Avoiding this problem is easiest with a merkelized
> key:value mapping, with the ability to use collision-resistant ID's as
> keys (e.g. UUID).

I agree with the concern, but I don't really understand how this idea solves it.

-- 
Pieter

Re: [bitcoin-dev] Segwit Upgrade Procedures & Block Extension Data

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 1415 bytes --]

On Mon, Feb 1, 2016 at 4:55 PM, Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> * The coinbase scriptSig gets a second number push (similar to the
> current BIP34 height push), which pushes a number O. O is a byte
> offset inside the coinbase transaction (excluding its witness data)
> that points to a 32-byte hash H. This is more flexible and more
> compact than what we have now (a suggestion by jl2012).
>

So, the script sig is  "<height> <offset> ..... <H>"?

Why is this just not the offset in the extra nonce?

> A significant design consideration is that if arbitrary data can be
> > added, it is very likely that miners will make use of that ability for
> > non-Bitcoin purposes;
> I agree with the concern, but I don't really understand how this idea
> solves it.
>
>
It could be enforced that the data in the coinbase witness stack has a
fixed number of entries, which depends on the block version number.
Version 5 blocks would only have 1 entry.

This would mean a soft-fork could be used to add new entries in the stack.
<https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail>
This
email has been sent from a virus-free computer protected by Avast.
www.avast.com
<https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=webmail>
<#DDB4FAA8-2DD7-40BB-A1B8-4E2AA1F9FDF2>

[-- Attachment #2: Type: text/html, Size: 2713 bytes --]