Date: Thu, 28 Jan 2016 13:51:24 -0500
From: Peter Todd <pete@petertodd.org>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <20160128185124.GA5140@savin.petertodd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="opJtzjQTFsWo+cga"
Content-Disposition: inline
Subject: [bitcoin-dev] Segwit Upgrade Procedures & Block Extension Data
Precedence: list


--opJtzjQTFsWo+cga
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

A few notes on upgrade procedures associated with segregated witnesses:


Initial Deployment
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

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
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

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
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

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
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

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/012=
103.html

5) https://github.com/bitcoin/bips/blob/6a315c023f13d83c58aab98cf8668d74cf7=
566c7/bip-0141.mediawiki#Extensible_commitment_structure

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

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

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

--opJtzjQTFsWo+cga
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----

iQGrBAEBCACVBQJWqmMmXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw
MDAwMDAwMDAwMDAwMDAwMWFkOGU2MzQzNDI4ZThmNzRkODViNGVkNTFlODE2NGU0
NWY3Yjk1NGZlODk5NTgvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0
ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfur9QgAnXXAlMolC1+1wuV1IuXaSQar
J0+sLKQMRFkQNnUSmOgtn09nCxCO+mcaPMHQbtfm9v7DX/0sVeFlO+z3zHcR4I2l
6Cxx+ZgJqNDoDEBqd2nQELC7aCh257X5UbakLY559MksGe2brnZSzVaOMiXZwkfV
kSOYaMECZi6vqLXIL3WEpLlcm3tmVmRONElCUVYYihA1x7zbR72a4uWujDIFU/c2
UetEgG7XTvSqxqvpd2Cc3U3SQ2u1mbw1PS3lqigHNAxm0eUPznyG5Sn/6l24RfFv
k6omk94/yjwPXo+SFCqdrvfG/ns6cmLlxxu9Yf5RzKjUDZTkDmmNhzCnqzMoxA==
=AT/O
-----END PGP SIGNATURE-----

--opJtzjQTFsWo+cga--