[bitcoin-dev] Forcenet: an experimental network with a new header format

[bitcoin-dev] Forcenet: an experimental network with a new header format

[Johnson Lau]

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

Based on Luke Dashjr’s code and BIP: https://github.com/luke-jr/bips/blob/bip-mmhf/bip-mmhf.mediawiki , I created an experimental network to show how a new header format may be implemented.

Basically, the header hash is calculated in a way that non-upgrading nodes would see it as a block with only the coinbase tx and zero output value. They are effectively broken as they won’t see any transactions confirmed. This allows rewriting most of the rules related to block and transaction validity. Such technique has different names like soft-hardfork, firmfork, evil softfork, and could be itself a controversial topic. However, I’d rather not to focus on its soft-hardfork property, as that would be trivial to turn this into a true hardfork (e.g. setting the sign bit in block nVersion, or setting the most significant bit in the dummy coinbase nLockTime)

Instead of its soft-HF property, I think the more interesting thing is the new header format. The current bitcoin header has only 80 bytes. It provides only 32bits of nonce space and is far not enough for ASICs. It also provides no room for committing to additional data. Therefore, people are forced to put many different data in the coinbase transaction, such as merge-mining commitments, and the segwit commitment. It is not a ideal solution, especially for light wallets.

Following the practice of segwit development of making a experimental network (segnet), I made something similar and call it the Forcenet (as it forces legacy nodes to follow the post-fork chain)

The header of forcenet is mostly described in Luke’s BIP, but I have made some amendments as I implemented it. The format is (size in parentheses; little endian):

Height (4), BIP9 signalling field (4), hardfork signalling field (3), merge-mining hard fork signalling field (1), prev hash (32), timestamp (4), nonce1 (4), nonce2 (4), nonce3 (compactSize + variable), Hash TMR (32), Hash WMR (32), total tx size (8) , total tx weight (8), total sigops (8), number of tx (4), merkle branches leading to header C (compactSize + 32 bit hashes)

In addition to increasing the max block size, I also showed how the calculation and validation of witness commitment may be changed with a new header. For example, since the commitment is no longer in the coinbase tx, we don’t need to use a 0000….0000 hash for the coinbase tx like in BIP141.

Something not yet done:
1. The new merkle root algorithm described in the MMHF BIP
2. The nTxsSigops has no meaning currently
3. Communication with legacy nodes. This version can’t talk to legacy nodes through the P2P network, but theoretically they could be linked up with a bridge node
4. A new block weight definition to provide incentives for slowing down UTXO growth
5. Many other interesting hardfork ideas, and softfork ideas that works better with a header redesign

For easier testing, forcenet has the following parameters:

Hardfork at block 200
Segwit is always activated
1 minutes block with 40000 (prefork) and 80000 (postfork) weight limit
50 blocks coinbase maturity
21000 blocks halving
144 blocks retarget

How to join: codes at https://github.com/jl2012/bitcoin/tree/forcenet1 , start with "bitcoind —forcenet" .
Connection: I’m running a node at 8333.info with default port (38901)
Mining: there is only basic internal mining support. Limited GBT support is theoretically possible but needs more hacking. To use the internal miner, writeup a shell script to repeatedly call “bitcoin-cli —forcenet generate 1”
New RPC commands: getlegacyblock and getlegacyblockheader, which generates blocks and headers that are compatible with legacy nodes.

This is largely work-in-progress so expect a reset every couple weeks

jl2012



[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 671 bytes --]

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[adiabat]

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

Interesting stuff! I have some comments, mostly about the header.

The header of forcenet is mostly described in Luke’s BIP, but I have made
> some amendments as I implemented it. The format is (size in parentheses;
> little endian):
>
> Height (4), BIP9 signalling field (4), hardfork signalling field (3),
> merge-mining hard fork signalling field (1), prev hash (32), timestamp (4),
> nonce1 (4), nonce2 (4), nonce3 (compactSize + variable), Hash TMR (32),
> Hash WMR (32), total tx size (8) , total tx weight (8), total sigops (8),
> number of tx (4), merkle branches leading to header C (compactSize + 32 bit
> hashes)
>

First, I'd really rather not have variable length fields in the header.
It's so much nicer to just have a fixed size.

Is having both TMR and WMR really needed?  As segwit would be required with
this header type, and the WMR covers a superset of the data that the TMR
does, couldn't you get rid of the TMR?  The only disadvantage I can see is
that light clients may want a merkle proof of a transaction without having
to download the witnesses for that transaction.  This seems pretty minor,
especially as once they're convinced of block inclusion they can discard
the witness data, and also the tradeoff is that light clients will have to
download and store and extra 32 bytes per block, likely offsetting any
savings from omitting witness data.

The other question is that there's a bit that's redundant: height is also
committed to in the coinbase tx via bip 34 (speaking of which, if there's a
hard-fork, how about reverting bip 34 and committing to the height with
coinbase tx nlocktime instead?)

Total size / weight / number of txs also feels pretty redundant.  Not a lot
of space but it's hard to come up with a use for them.  Number of tx could
be useful if you want to send all the leaves of a merkle tree, but you
could also do that by committing to the depth of the merkle tree in the
header, which is 1 byte.

Also how about making timestamp 8 bytes?  2106 is coming up soon :)

Maybe this is too nit-picky; maybe it's better to put lots of stuff in for
testing the forcenet and then take out all the stuff that wasn't used or
had issues as it progresses.

Thanks and looking forward to trying out forcenet!

-Tadge

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

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Hampus Sjöberg]

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

> Also how about making timestamp 8 bytes?  2106 is coming up soon :)

AFAICT this was fixed in this commit:
https://github.com/jl2012/bitcoin/commit/fa80b48bb4237b110ceffe11edc14c8130672cd2#diff-499d7ee7998a27095063ed7b4dd7c119R200


2016-12-04 21:00 GMT+01:00 adiabat via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org>:

> Interesting stuff! I have some comments, mostly about the header.
>
> The header of forcenet is mostly described in Luke’s BIP, but I have made
>> some amendments as I implemented it. The format is (size in parentheses;
>> little endian):
>>
>> Height (4), BIP9 signalling field (4), hardfork signalling field (3),
>> merge-mining hard fork signalling field (1), prev hash (32), timestamp (4),
>> nonce1 (4), nonce2 (4), nonce3 (compactSize + variable), Hash TMR (32),
>> Hash WMR (32), total tx size (8) , total tx weight (8), total sigops (8),
>> number of tx (4), merkle branches leading to header C (compactSize + 32 bit
>> hashes)
>>
>
> First, I'd really rather not have variable length fields in the header.
> It's so much nicer to just have a fixed size.
>
> Is having both TMR and WMR really needed?  As segwit would be required
> with this header type, and the WMR covers a superset of the data that the
> TMR does, couldn't you get rid of the TMR?  The only disadvantage I can see
> is that light clients may want a merkle proof of a transaction without
> having to download the witnesses for that transaction.  This seems pretty
> minor, especially as once they're convinced of block inclusion they can
> discard the witness data, and also the tradeoff is that light clients will
> have to download and store and extra 32 bytes per block, likely offsetting
> any savings from omitting witness data.
>
> The other question is that there's a bit that's redundant: height is also
> committed to in the coinbase tx via bip 34 (speaking of which, if there's a
> hard-fork, how about reverting bip 34 and committing to the height with
> coinbase tx nlocktime instead?)
>
> Total size / weight / number of txs also feels pretty redundant.  Not a
> lot of space but it's hard to come up with a use for them.  Number of tx
> could be useful if you want to send all the leaves of a merkle tree, but
> you could also do that by committing to the depth of the merkle tree in the
> header, which is 1 byte.
>
> Also how about making timestamp 8 bytes?  2106 is coming up soon :)
>
> Maybe this is too nit-picky; maybe it's better to put lots of stuff in for
> testing the forcenet and then take out all the stuff that wasn't used or
> had issues as it progresses.
>
> Thanks and looking forward to trying out forcenet!
>
> -Tadge
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

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

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Tom Zander]

On Sunday, 4 December 2016 21:37:39 CET Hampus Sjöberg via bitcoin-dev 
wrote:
> > Also how about making timestamp 8 bytes?  2106 is coming up soon 
> 
> AFAICT this was fixed in this commit:
> https://github.com/jl2012/bitcoin/commit/
fa80b48bb4237b110ceffe11edc14c813
> 0672cd2#diff-499d7ee7998a27095063ed7b4dd7c119R200

That commit hacks around it, a new block header fixes it. Subtle difference.

-- 
Tom Zander
Blog: https://zander.github.io
Vlog: https://vimeo.com/channels/tomscryptochannel

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Tier Nolan]

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

On Sun, Dec 4, 2016 at 7:34 PM, Johnson Lau via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Something not yet done:
> 1. The new merkle root algorithm described in the MMHF BIP
>

Any new merkle algorithm should use a sum tree for partial validation and
fraud proofs.

Is there something special about 216 bits?  I guess at most 448 bits total
means only one round of SHA256.  16 bits for flags would give 216 for each
child.

Even better would be to make the protocol extendable.  Allow blocks to
indicate new trees and legacy nodes would just ignore the extra ones.  If
Bitcoin supported that then the segregated witness tree could have been
added as a easier soft fork.

The sum-tree could be added later as an extra tree.


> 3. Communication with legacy nodes. This version can’t talk to legacy
> nodes through the P2P network, but theoretically they could be linked up
> with a bridge node
>

The bridge would only need to transfer the legacy blocks which are coinbase
only, so very little data.


> 5. Many other interesting hardfork ideas, and softfork ideas that works
> better with a header redesign
>

That is very true.

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

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Luke Dashjr]

On Saturday, December 10, 2016 9:29:09 PM Tier Nolan via bitcoin-dev wrote:
> On Sun, Dec 4, 2016 at 7:34 PM, Johnson Lau via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> > Something not yet done:
> > 1. The new merkle root algorithm described in the MMHF BIP
> 
> Any new merkle algorithm should use a sum tree for partial validation and
> fraud proofs.

PR welcome.

> Is there something special about 216 bits?  I guess at most 448 bits total
> means only one round of SHA256.  16 bits for flags would give 216 for each
> child.

See https://github.com/luke-jr/bips/blob/bip-mmhf/bip-mmhf.mediawiki#Merkle_tree_algorithm

But yes, the 448 bits total target is to optimise the tree-building.

> Even better would be to make the protocol extendable.  Allow blocks to
> indicate new trees and legacy nodes would just ignore the extra ones.  If
> Bitcoin supported that then the segregated witness tree could have been
> added as a easier soft fork.

It already is. This is a primary goal of the new protocol.

> The sum-tree could be added later as an extra tree.

Adding new trees means more hashing to validate blocks, so it'd be better to 
keep it at a minimum.

Luke

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Tier Nolan]

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

On Sat, Dec 10, 2016 at 9:41 PM, Luke Dashjr <luke@dashjr.org> wrote:

> On Saturday, December 10, 2016 9:29:09 PM Tier Nolan via bitcoin-dev wrote:
> > Any new merkle algorithm should use a sum tree for partial validation and
> > fraud proofs.
>
> PR welcome.
>

Fair enough.  It is pretty basic.

https://github.com/luke-jr/bips/pull/2

It sums up sigops, block size, block cost (that is "weight" right?) and
fees.

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

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Johnson Lau]

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

I think the biggest problem of sum tree is the lack of flexibility to redefine the values with softforks. For example, in the future we may want to define a new CHECKSIG with witness script version 1. That would be counted as a SigOp. Without a sum tree design, that’d be easy as we could just define new SigOp through a softfork (e.g. the introduction of P2SH SigOp, and the witness v0 SigOp). In a sum tree, however, since the nSigOp is implied, any redefinition requires either a hardfork or a new sum tree (and the original sum tree becomes a placebo for old nodes. So every softfork of this type creates a new tree)

Similarly, we may have secondary witness in the future, and the tx weight would be redefined with a softfork. We will face the same problem with a sum tree

The only way to fix this is to explicitly commit to the weight and nSigOp, and the committed value must be equal to or larger than the real value. Only in this way we could redefine it with softfork. However, that means each tx will have an overhead of 16 bytes (if two int64 are used)

You could find related discussion here: https://github.com/jl2012/bitcoin/commit/69e613bfb0f777c8dcd2576fe1c2541ee7a17208 <https://github.com/jl2012/bitcoin/commit/69e613bfb0f777c8dcd2576fe1c2541ee7a17208>

Maybe we could make this optional: for nodes running exactly the same rules, they could omit the weight and nSigOp value in transmission. To talk to legacy nodes, they need to transmit the newly defined weight and nSigOp. But this makes script upgrade much complex.


> On 12 Dec 2016, at 00:40, Tier Nolan via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org <mailto:bitcoin-dev@lists.linuxfoundation.org>> wrote:
> 
> On Sat, Dec 10, 2016 at 9:41 PM, Luke Dashjr <luke@dashjr.org <mailto:luke@dashjr.org>> wrote:
> On Saturday, December 10, 2016 9:29:09 PM Tier Nolan via bitcoin-dev wrote:
> > Any new merkle algorithm should use a sum tree for partial validation and
> > fraud proofs.
> 
> PR welcome.
> 
> Fair enough.  It is pretty basic.
> 
> https://github.com/luke-jr/bips/pull/2 <https://github.com/luke-jr/bips/pull/2>
> 
> It sums up sigops, block size, block cost (that is "weight" right?) and fees.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org <mailto:bitcoin-dev@lists.linuxfoundation.org>
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


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

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Johnson Lau]

There is no reason to use a timestamp beyond 4 bytes. Just let it overflow. If a blockchain is stopped for more than 2^31 seconds, it’s just dead.

> On 5 Dec 2016, at 19:58, Tom Zander via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> On Sunday, 4 December 2016 21:37:39 CET Hampus Sjöberg via bitcoin-dev 
> wrote:
>>> Also how about making timestamp 8 bytes?  2106 is coming up soon 
>> 
>> AFAICT this was fixed in this commit:
>> https://github.com/jl2012/bitcoin/commit/
> fa80b48bb4237b110ceffe11edc14c813
>> 0672cd2#diff-499d7ee7998a27095063ed7b4dd7c119R200
> 
> That commit hacks around it, a new block header fixes it. Subtle difference.
> 
> -- 
> Tom Zander
> Blog: https://zander.github.io
> Vlog: https://vimeo.com/channels/tomscryptochannel
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Luke Dashjr]

On Wednesday, December 14, 2016 11:01:58 AM Johnson Lau via bitcoin-dev wrote:
> There is no reason to use a timestamp beyond 4 bytes.

Actually, there is: lock times... my overflow solution doesn't have a solution 
to that. :x

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Johnson Lau]

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


> On 5 Dec 2016, at 04:00, adiabat <rx@awsomnet.org> wrote:
> 
> Interesting stuff! I have some comments, mostly about the header.
> 
> The header of forcenet is mostly described in Luke’s BIP, but I have made some amendments as I implemented it. The format is (size in parentheses; little endian):
> 
> Height (4), BIP9 signalling field (4), hardfork signalling field (3), merge-mining hard fork signalling field (1), prev hash (32), timestamp (4), nonce1 (4), nonce2 (4), nonce3 (compactSize + variable), Hash TMR (32), Hash WMR (32), total tx size (8) , total tx weight (8), total sigops (8), number of tx (4), merkle branches leading to header C (compactSize + 32 bit hashes)
> 
> First, I'd really rather not have variable length fields in the header.  It's so much nicer to just have a fixed size.
> 
> Is having both TMR and WMR really needed?  As segwit would be required with this header type, and the WMR covers a superset of the data that the TMR does, couldn't you get rid of the TMR?  The only disadvantage I can see is that light clients may want a merkle proof of a transaction without having to download the witnesses for that transaction.  This seems pretty minor, especially as once they're convinced of block inclusion they can discard the witness data, and also the tradeoff is that light clients will have to download and store and extra 32 bytes per block, likely offsetting any savings from omitting witness data.
> 

I foresee there will be 2 types of headers under this system: the 80 bytes short header and the variable length full header. Short headers are enough to link everything up. SPV needs the full header only if they are interested in any tx in a block. 

> The other question is that there's a bit that's redundant: height is also committed to in the coinbase tx via bip 34 (speaking of which, if there's a hard-fork, how about reverting bip 34 and committing to the height with coinbase tx nlocktime instead?)

you could omit the transmission of nHeight, as it is implied (saving 4bytes). Storing nHeight of headers is what every full and SPV nodes would do anyway


> 
> Total size / weight / number of txs also feels pretty redundant.  Not a lot of space but it's hard to come up with a use for them.  Number of tx could be useful if you want to send all the leaves of a merkle tree, but you could also do that by committing to the depth of the merkle tree in the header, which is 1 byte.

Yes, I agree with you that these are not particularly useful. Sum tree is more useful but it has other problems (see my other reply)

Related discussion: https://github.com/jl2012/bitcoin/commit/69e613bfb0f777c8dcd2576fe1c2541ee7a17208 <https://github.com/jl2012/bitcoin/commit/69e613bfb0f777c8dcd2576fe1c2541ee7a17208>
> 
> Also how about making timestamp 8 bytes?  2106 is coming up soon :)

No need. See my other reply

> 
> Maybe this is too nit-picky; maybe it's better to put lots of stuff in for testing the forcenet and then take out all the stuff that wasn't used or had issues as it progresses.
> 
> Thanks and looking forward to trying out forcenet!
> 
> -Tadge


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

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Johnson Lau]

> On 14 Dec 2016, at 19:07, Luke Dashjr <luke@dashjr.org> wrote:
> 
> On Wednesday, December 14, 2016 11:01:58 AM Johnson Lau via bitcoin-dev wrote:
>> There is no reason to use a timestamp beyond 4 bytes.
> 
> Actually, there is: lock times... my overflow solution doesn't have a solution 
> to that. :x


You could steal a few bits form tx nVersion through a softfork

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Tier Nolan]

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

On Wed, Dec 14, 2016 at 10:55 AM, Johnson Lau <jl2012@xbt.hk> wrote:

> In a sum tree, however, since the nSigOp is implied, any redefinition
> requires either a hardfork or a new sum tree (and the original sum tree
> becomes a placebo for old nodes. So every softfork of this type creates a
> new tree)
>

That's a good point.


> The only way to fix this is to explicitly commit to the weight and nSigOp,
> and the committed value must be equal to or larger than the real value.
> Only in this way we could redefine it with softfork. However, that means
> each tx will have an overhead of 16 bytes (if two int64 are used)
>

The weight and sigop count could be transmitted as variable length
integers.  That would be around 2 bytes for the sigops and 3 bytes for the
weight, per transaction.

It would mean that the block format would have to include the raw
transaction, "extra"/tree information and witness data for each transaction.

On an unrelated note, the two costs could be combined into a unified cost.
For example, a sigop could have equal cost to 250 bytes.  This would make
it easier for miners to decide what to charge.

On the other hand, CPU cost and storage/network costs are not completely
interchangeable.

Is there anything that would need to be summed fees, raw tx size, weight
and sigops that the greater or equal rule wouldn't cover?

On 12 Dec 2016, at 00:40, Tier Nolan via bitcoin-dev <bitcoin-dev@lists.
linuxfoundation.org> wrote:


On Sat, Dec 10, 2016 at 9:41 PM, Luke Dashjr <luke@dashjr.org> wrote:

> On Saturday, December 10, 2016 9:29:09 PM Tier Nolan via bitcoin-dev wrote:
> > Any new merkle algorithm should use a sum tree for partial validation and
> > fraud proofs.
>
> PR welcome.
>

Fair enough.  It is pretty basic.

https://github.com/luke-jr/bips/pull/2

It sums up sigops, block size, block cost (that is "weight" right?) and
fees.
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

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

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Johnson Lau]

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

I think that’s too much tech debt just for softforkability.

The better way would be making the sum tree as an independent tree with a separate commitment, and define a special type of softfork (e.g. a special BIP9 bit). When the softfork is activated, the legacy full node will stop validating the sum tree. This doesn’t really degrade the security by more than a normal softfork, as the legacy full node would still validate the total weight and nSigOp based on its own rules. The only purpose of the sum tree is to help SPV nodes to validate. This way we could even completely redefine the structure and data committed in the sum tree.

I’d like to combine the size weight and sigOp weight, but not sure if we could. The current size weight limit is 4,000,000 and sigop limit is 80,000. It’s 50:1. If we maintain this ratio, and define
weight = n * (total size +  3 * base size) + sigop , with n = 50
a block may have millions of sigops which is totally unacceptable.

On the other hand, if we make n too low, we may allow either too few sigop, or a too big block size.

Signature aggregation will make this a bigger problem as one signature may spend thousands of sigop



> On 14 Dec 2016, at 20:52, Tier Nolan <tier.nolan@gmail.com> wrote:
> 
> 
> 
> On Wed, Dec 14, 2016 at 10:55 AM, Johnson Lau <jl2012@xbt.hk <mailto:jl2012@xbt.hk>> wrote:
> In a sum tree, however, since the nSigOp is implied, any redefinition requires either a hardfork or a new sum tree (and the original sum tree becomes a placebo for old nodes. So every softfork of this type creates a new tree)
> 
> That's a good point.
>  
> The only way to fix this is to explicitly commit to the weight and nSigOp, and the committed value must be equal to or larger than the real value. Only in this way we could redefine it with softfork. However, that means each tx will have an overhead of 16 bytes (if two int64 are used)
> 
> The weight and sigop count could be transmitted as variable length integers.  That would be around 2 bytes for the sigops and 3 bytes for the weight, per transaction.
> 
> It would mean that the block format would have to include the raw transaction, "extra"/tree information and witness data for each transaction.
> 
> On an unrelated note, the two costs could be combined into a unified cost.  For example, a sigop could have equal cost to 250 bytes.  This would make it easier for miners to decide what to charge.
> 
> On the other hand, CPU cost and storage/network costs are not completely interchangeable.
> 
> Is there anything that would need to be summed fees, raw tx size, weight and sigops that the greater or equal rule wouldn't cover?
> 
> On 12 Dec 2016, at 00:40, Tier Nolan via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org <mailto:bitcoin-dev@lists.linuxfoundation.org>> wrote:
>> 
>> On Sat, Dec 10, 2016 at 9:41 PM, Luke Dashjr <luke@dashjr.org <mailto:luke@dashjr.org>> wrote:
>> On Saturday, December 10, 2016 9:29:09 PM Tier Nolan via bitcoin-dev wrote:
>> > Any new merkle algorithm should use a sum tree for partial validation and
>> > fraud proofs.
>> 
>> PR welcome.
>> 
>> Fair enough.  It is pretty basic.
>> 
>> https://github.com/luke-jr/bips/pull/2 <https://github.com/luke-jr/bips/pull/2>
>> 
>> It sums up sigops, block size, block cost (that is "weight" right?) and fees.
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org <mailto:bitcoin-dev@lists.linuxfoundation.org>
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
> 
> 


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

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Tier Nolan]

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

On Wed, Dec 14, 2016 at 3:45 PM, Johnson Lau <jl2012@xbt.hk> wrote:

> I think that’s too much tech debt just for softforkability.
>
> The better way would be making the sum tree as an independent tree with a
> separate commitment, and define a special type of softfork (e.g. a special
> BIP9 bit).
>

One of the problems with fraud proofs is withholding by miners.  It is
important that proof of publication/archive nodes check that the miners are
actually publishing their blocks.

If you place the data in another tree, then care needs to be taken that the
merkle path information can be obtained for that tree.

If an SPV node asks for a run of transactions from an archive node, then
the archive node can give the merkle branch for all of those transactions.
The archive node inherently has to check that tree.

The question is if there is a way to show that data is not available, but
without opening up the network to DOS.  If enough people run full nodes
then this isn't a problem.

>
> When the softfork is activated, the legacy full node will stop validating
> the sum tree. This doesn’t really degrade the security by more than a
> normal softfork, as the legacy full node would still validate the total
> weight and nSigOp based on its own rules. The only purpose of the sum tree
> is to help SPV nodes to validate. This way we could even completely
> redefine the structure and data committed in the sum tree.
>

Seems reasonable.  I think the soft-fork would have to have a timeout
before actually activating.  That would give SPV clients time to switch
over.

That could happen before the vote though, so it isn't essential.  The SPV
clients would have to support both trees and then switch mode.  Ensuring
that SPV nodes actually bother would be helped by proving that the network
actually intends to soft fork.

The SPV client just has to check that every block has at least one of the
commitments that it accepts so that it can understand fraud proofs.


>
> I’d like to combine the size weight and sigOp weight, but not sure if we
> could. The current size weight limit is 4,000,000 and sigop limit is
> 80,000. It’s 50:1. If we maintain this ratio, and define
> weight = n * (total size +  3 * base size) + sigop , with n = 50
> a block may have millions of sigops which is totally unacceptable.
>

You multiplied by the wrong term.

weight = total size +  3 * base size + n * sigop , with n = 50

weight for max block = 8,000,000

That gives a maximum of 8,000,000 / 50 = 160,000 sigops.

To get that you would need zero transaction length.  You could get close if
you have transactions that just repeat OP_CHECKSIG over and over (or maybe
something with OP_CHECKMULTISIG).


>
> On the other hand, if we make n too low, we may allow either too few
> sigop, or a too big block size.
>
> Signature aggregation will make this a bigger problem as one signature may
> spend thousands of sigop
>
>
>
> On 14 Dec 2016, at 20:52, Tier Nolan <tier.nolan@gmail.com> wrote:
>
>
>
> On Wed, Dec 14, 2016 at 10:55 AM, Johnson Lau <jl2012@xbt.hk> wrote:
>
>> In a sum tree, however, since the nSigOp is implied, any redefinition
>> requires either a hardfork or a new sum tree (and the original sum tree
>> becomes a placebo for old nodes. So every softfork of this type creates a
>> new tree)
>>
>
> That's a good point.
>
>
>> The only way to fix this is to explicitly commit to the weight and
>> nSigOp, and the committed value must be equal to or larger than the real
>> value. Only in this way we could redefine it with softfork. However, that
>> means each tx will have an overhead of 16 bytes (if two int64 are used)
>>
>
> The weight and sigop count could be transmitted as variable length
> integers.  That would be around 2 bytes for the sigops and 3 bytes for the
> weight, per transaction.
>
> It would mean that the block format would have to include the raw
> transaction, "extra"/tree information and witness data for each transaction.
>
> On an unrelated note, the two costs could be combined into a unified
> cost.  For example, a sigop could have equal cost to 250 bytes.  This would
> make it easier for miners to decide what to charge.
>
> On the other hand, CPU cost and storage/network costs are not completely
> interchangeable.
>
> Is there anything that would need to be summed fees, raw tx size, weight
> and sigops that the greater or equal rule wouldn't cover?
>
> On 12 Dec 2016, at 00:40, Tier Nolan via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>
> On Sat, Dec 10, 2016 at 9:41 PM, Luke Dashjr <luke@dashjr.org> wrote:
>
>> On Saturday, December 10, 2016 9:29:09 PM Tier Nolan via bitcoin-dev
>> wrote:
>> > Any new merkle algorithm should use a sum tree for partial validation
>> and
>> > fraud proofs.
>>
>> PR welcome.
>>
>
> Fair enough.  It is pretty basic.
>
> https://github.com/luke-jr/bips/pull/2
>
> It sums up sigops, block size, block cost (that is "weight" right?) and
> fees.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
>
>
>

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

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Johnson Lau]

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

I created a second version of forcenet with more experimental features and stopped my forcenet1 node.

1. It has a new header format: Height (4), BIP9 signalling field (4), hardfork signalling field (2), Hash TMR (32), Hash WMR (32), Merkle sum root (32), number of tx (4), prev hash (32), timestamp (4), nBits (4), nonce1 (4), nonce2 (4), nonce3 (compactSize + variable), merkle branches leading to header C (compactSize + 32 bit hashes)

2. Anti-tx-replay. If, after masking the highest byte, the tx nVersion is >=3, the sighash for both segwit and non-segwit outputs is calculated with BIP143, except 0x2000000 is added to the nHashType. Such signatures are invalid for legacy nodes. But since they are non-std due the nVersion, they won’t be relayed nor validated by legacy nodes. This also removes the O(n^2) sighash problem when spending non-segwit outputs. (anti-replay is a long story and I will discuss in a separate post/BIP)

3. Block sighashlimit (https://github.com/jl2012/bips/blob/sighash/bip-sighash.mediawiki <https://github.com/jl2012/bips/blob/sighash/bip-sighash.mediawiki>). Due to point 2, SigHashSize is counted only for legacy non-segwit inputs (with masked tx nVersion < 3). We have to support legacy signature to make sure time-locked txs made before the hard fork are still valid.

4. A totally new way to define tx weight. Tx weight is the maximum of the following metrics:
a. SigHashSize (see the bip in point 3)
b. Witness serialised size * 2 * 90
c. Adjusted size * 90. Adjusted size = tx weight (BIP141) + (number of non-OP_RETURN outputs - number of inputs) * 41 * 4
d. nSigOps * 50 * 90. All SigOps are equal (no witness scaling). For non-segwit txs, the sigops in output scriptPubKey are not counted, while the sigops in input scriptPubKey are counted.

90 is the scaling factor for SigHashSize, to maintain the 1:90 ratio (see the BIP in point 3)
50 is the scaling factor for nSigOps, maintaining the 1:50 ratio in BIP141

Rationale for adjusted size: 4 is witness scaling factor. 41 is the minimum size for an input (32 hash + 4 index + 4 nSequence + 1 scriptSig). This requires people to pre-pay majority of the fee of spending an UTXO. It makes creation of UTXO more expensive, while spending of UTXO cheaper, creates a strong incentive to limit the growth of UTXO set.

Rationale for taking the maximum of different metrics: this indirectly set an upper block resources for _every_ metrics, while making the tx fee estimation a linear function. Currently, there are 2 block resources limits: block weight and nSigOp cost (BIP141). However, since users do not know what the other txs are included in the next block, it is difficult to determine whether tx weight of nSigOp cost is a more important factor in determining the tx fee. (This is not a real problem now, because weight is more important in most cases). With an unified definition of tx weight, the fee estimation becomes a linear problem.

Translating to new metric, the current BIP141 limit is 360,000,000. This is equivalent to 360MB of sighashing, 2MB of serialised size, 4MB of adjusted size, or 80000 nSigOp.

Any new block-level limit metrics could be added to tx weight using soft forks.

5. Smooth halving: the reward of the last 2016 blocks in a halving cycle will be reduced by 25%, which is contributed to the first 2016 blocks of the new halving cycle. (different parameters for forcenet) This makes a more graceful transition but we will lose some fun around halving.

6. A new coinbase tx format. BIP34 is removed. Coinbase tx may have more than 1 input. The prevout hash of first input must be the hash of previous block, and index must be 0xffffffff. The other inputs (if any) must come from UTXOs with valid signatures. Spending of previous coinbase outputs in a coinbase tx is exempted from the 100 block maturity requirement. Therefore, miners of an earlier block may pay other miners to convince them to confirm their blocks.

7. Merkle sum tree: it allows generating of fraud-proof for fee and weight. A special softfork (bit 15) is defined. When this softfork is activated, the full node will not validate the sum tree. This is needed because when the definition of tx weight is changed through a softfork (e.g. a new script version introducing new sigop), olds nodes won’t know the new rules and will find the sum tree invalid. Disabling the sum tree validation won’t degrade the security of a full node by more than an usual softfork, because the full node would still validate all other known rules.

However, it is still not possible to create fraud proof for spending of non-existing UTXO. This requires commitment of the block height of inputs, and the tx index in the block. I’m not quire sure how this could be implemented because a re-org may change such info (I think validation is easy but mining is more tricky)

How to join: codes at https://github.com/jl2012/bitcoin/tree/forcenet2 <https://github.com/jl2012/bitcoin/tree/forcenet2> , start with "bitcoind —forcenet" .
Connection: I’m running a node at 8333.info <http://8333.info/> with default port (39901)
Mining: there is only basic internal mining support. To use the internal miner, writeup a shell script to repeatedly call “bitcoin-cli —forcenet generate 1”

jl2012

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

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Matt Corallo]

Looks cool, though I have a few comments inline.

One general note - it looks like you're letting complexity run away from
you a bit here. If the motivation for something is only weak, its
probably not worth doing! A hard fork is something that must be
undertaken cautiously because it has so much inherent risk, lets not add
tons to it.

Matt

On 01/14/17 21:14, Johnson Lau via bitcoin-dev wrote:
> I created a second version of forcenet with more experimental features
> and stopped my forcenet1 node.
> 
> 1. It has a new header format: Height (4), BIP9 signalling field (4),
> hardfork signalling field (2), Hash TMR (32), Hash WMR (32), Merkle sum
> root (32), number of tx (4), prev hash (32), timestamp (4), nBits (4),
> nonce1 (4), nonce2 (4), nonce3 (compactSize + variable), merkle branches
> leading to header C (compactSize + 32 bit hashes)

In order of appearance:

First of all lets try to minimize header size. We really dont want any
more space taken up here than we absolutely need to.

I'm super unconvinced that we need more than one merkle tree for
transactions. Lets just have one merkle tree who's leaves are
transactions hashed 2 ways (without witnesses and only witnesses).

Why duplicate the nBits here? shouldn't the PoW proof be the
responsibility of the parent header?

I have to agree with Tadge here, variable-length header fields are evil,
lets avoid them.

Why have merkle branches to yet another header? Lets just leave it as an
opaque commitment header (32).

Finally, lets not jump through hoops here - the transaction merkle root
of the "old-style" (now PoW) header should simply be the hash of the new
header. No coinbase transaction, just the hash of the secondary header.
This saves space without giving up utility - SPV nodes are already not
looking at the coinbase transaction, so no harm in not having one to give.

> 2. Anti-tx-replay. If, after masking the highest byte, the tx nVersion
> is >=3, the sighash for both segwit and non-segwit outputs is calculated
> with BIP143, except 0x2000000 is added to the nHashType. Such signatures
> are invalid for legacy nodes. But since they are non-std due the
> nVersion, they won’t be relayed nor validated by legacy nodes. This also
> removes the O(n^2) sighash problem when spending non-segwit outputs.
> (anti-replay is a long story and I will discuss in a separate post/BIP)

Will comment on the anti-replay post.

> 3. Block sighashlimit
> (https://github.com/jl2012/bips/blob/sighash/bip-sighash.mediawiki). Due
> to point 2, SigHashSize is counted only for legacy non-segwit inputs
> (with masked tx nVersion < 3). We have to support legacy signature to
> make sure time-locked txs made before the hard fork are still valid.
> 
> 4. A totally new way to define tx weight. Tx weight is the maximum of
> the following metrics:
> a. SigHashSize (see the bip in point 3)
> b. Witness serialised size * 2 * 90
> c. Adjusted size * 90. Adjusted size = tx weight (BIP141) + (number of
> non-OP_RETURN outputs - number of inputs) * 41 * 4
> d. nSigOps * 50 * 90. All SigOps are equal (no witness scaling). For
> non-segwit txs, the sigops in output scriptPubKey are not counted, while
> the sigops in input scriptPubKey are counted.

This is definitely too much. On the one hand its certainly nice to be
able to use max() for limits, and nice to add all the reasonable limits
we might want to, but on the other hand this can make things like coin
selection super complicated - how do you take into consideration the 4
different limits? Can we do something much, much simpler like
max(serialized size with some input discount, nSigOps * X) (which is
what we effectively already have in our mining code)?

> 90 is the scaling factor for SigHashSize, to maintain the 1:90 ratio
> (see the BIP in point 3)
> 50 is the scaling factor for nSigOps, maintaining the 1:50 ratio in BIP141
> 
> Rationale for adjusted size: 4 is witness scaling factor. 41 is the
> minimum size for an input (32 hash + 4 index + 4 nSequence + 1
> scriptSig). This requires people to pre-pay majority of the fee of
> spending an UTXO. It makes creation of UTXO more expensive, while
> spending of UTXO cheaper, creates a strong incentive to limit the growth
> of UTXO set.
> 
> Rationale for taking the maximum of different metrics: this indirectly
> set an upper block resources for _every_ metrics, while making the tx
> fee estimation a linear function. Currently, there are 2 block resources
> limits: block weight and nSigOp cost (BIP141). However, since users do
> not know what the other txs are included in the next block, it is
> difficult to determine whether tx weight of nSigOp cost is a more
> important factor in determining the tx fee. (This is not a real problem
> now, because weight is more important in most cases). With an unified
> definition of tx weight, the fee estimation becomes a linear problem.
> 
> Translating to new metric, the current BIP141 limit is 360,000,000. This
> is equivalent to 360MB of sighashing, 2MB of serialised size, 4MB of
> adjusted size, or 80000 nSigOp.
> 
> Any new block-level limit metrics could be added to tx weight using soft
> forks.
> 
> 5. Smooth halving: the reward of the last 2016 blocks in a halving cycle
> will be reduced by 25%, which is contributed to the first 2016 blocks of
> the new halving cycle. (different parameters for forcenet) This makes a
> more graceful transition but we will lose some fun around halving.

Hum, not sure this is sufficient. Its still stair-stepping at big enough
jumps that we could conceivably see super slow block times around
halvings in the distant future. Maybe instead of 100%-75%-75%-50% (I
believe that's what you're proposing here?),
100%-87.5%-75%-75%-62.5%-50% might be smoother?

> 6. A new coinbase tx format. BIP34 is removed. Coinbase tx may have more
> than 1 input. The prevout hash of first input must be the hash of
> previous block, and index must be 0xffffffff.

I'm not necessarily opposed to this, but what is the justification for it?

> The other inputs (if any)
> must come from UTXOs with valid signatures. Spending of previous
> coinbase outputs in a coinbase tx is exempted from the 100 block
> maturity requirement. Therefore, miners of an earlier block may pay
> other miners to convince them to confirm their blocks.

Sounds good.

> 7. Merkle sum tree: it allows generating of fraud-proof for fee and
> weight. A special softfork (bit 15) is defined. When this softfork is
> activated, the full node will not validate the sum tree. This is needed
> because when the definition of tx weight is changed through a softfork
> (e.g. a new script version introducing new sigop), olds nodes won’t know
> the new rules and will find the sum tree invalid. Disabling the sum tree
> validation won’t degrade the security of a full node by more than an
> usual softfork, because the full node would still validate all other
> known rules.
> 
> However, it is still not possible to create fraud proof for spending of
> non-existing UTXO. This requires commitment of the block height of
> inputs, and the tx index in the block. I’m not quire sure how this could
> be implemented because a re-org may change such info (I think validation
> is easy but mining is more tricky)

If we cant build wholesale proofs, then lets not jump through hoops and
add special bits to build partial ones? Its not clear to me that it
would be any reduction in soft-fork-ability later down the road to not
have this - if you're changing the definition of tx weight, you're
likely doing something like segwit where you're adding something else,
not trying to re-adjust weights.

> How to join: codes at https://github.com/jl2012/bitcoin/tree/forcenet2 ,
> start with "bitcoind —forcenet" .
> Connection: I’m running a node at 8333.info <http://8333.info> with
> default port (39901)
> Mining: there is only basic internal mining support. To use the internal
> miner, writeup a shell script to repeatedly call “bitcoin-cli —forcenet
> generate 1”
> 
> jl2012
> 
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Matt Corallo]

Oops, forgot to mention, in the "parent" (ie old) block header, we should:

1) fix the version field so its a static constant
2) swap first 2 bytes of the merkle root with the timestamp's two
high-order bytes (preferably more, I'm not sure how much ASIC hardware
has timestamp-rolling in it anymore, but if there is none left we should
take all 4 bytes from the timestamp field).

Matt

On 01/28/17 02:32, Matt Corallo via bitcoin-dev wrote:
> Looks cool, though I have a few comments inline.
> 
> One general note - it looks like you're letting complexity run away from
> you a bit here. If the motivation for something is only weak, its
> probably not worth doing! A hard fork is something that must be
> undertaken cautiously because it has so much inherent risk, lets not add
> tons to it.
> 
> Matt
> 
> On 01/14/17 21:14, Johnson Lau via bitcoin-dev wrote:
>> I created a second version of forcenet with more experimental features
>> and stopped my forcenet1 node.
>>
>> 1. It has a new header format: Height (4), BIP9 signalling field (4),
>> hardfork signalling field (2), Hash TMR (32), Hash WMR (32), Merkle sum
>> root (32), number of tx (4), prev hash (32), timestamp (4), nBits (4),
>> nonce1 (4), nonce2 (4), nonce3 (compactSize + variable), merkle branches
>> leading to header C (compactSize + 32 bit hashes)
> 
> In order of appearance:
> 
> First of all lets try to minimize header size. We really dont want any
> more space taken up here than we absolutely need to.
> 
> I'm super unconvinced that we need more than one merkle tree for
> transactions. Lets just have one merkle tree who's leaves are
> transactions hashed 2 ways (without witnesses and only witnesses).
> 
> Why duplicate the nBits here? shouldn't the PoW proof be the
> responsibility of the parent header?
> 
> I have to agree with Tadge here, variable-length header fields are evil,
> lets avoid them.
> 
> Why have merkle branches to yet another header? Lets just leave it as an
> opaque commitment header (32).
> 
> Finally, lets not jump through hoops here - the transaction merkle root
> of the "old-style" (now PoW) header should simply be the hash of the new
> header. No coinbase transaction, just the hash of the secondary header.
> This saves space without giving up utility - SPV nodes are already not
> looking at the coinbase transaction, so no harm in not having one to give.
> 
>> 2. Anti-tx-replay. If, after masking the highest byte, the tx nVersion
>> is >=3, the sighash for both segwit and non-segwit outputs is calculated
>> with BIP143, except 0x2000000 is added to the nHashType. Such signatures
>> are invalid for legacy nodes. But since they are non-std due the
>> nVersion, they won’t be relayed nor validated by legacy nodes. This also
>> removes the O(n^2) sighash problem when spending non-segwit outputs.
>> (anti-replay is a long story and I will discuss in a separate post/BIP)
> 
> Will comment on the anti-replay post.
> 
>> 3. Block sighashlimit
>> (https://github.com/jl2012/bips/blob/sighash/bip-sighash.mediawiki). Due
>> to point 2, SigHashSize is counted only for legacy non-segwit inputs
>> (with masked tx nVersion < 3). We have to support legacy signature to
>> make sure time-locked txs made before the hard fork are still valid.
>>
>> 4. A totally new way to define tx weight. Tx weight is the maximum of
>> the following metrics:
>> a. SigHashSize (see the bip in point 3)
>> b. Witness serialised size * 2 * 90
>> c. Adjusted size * 90. Adjusted size = tx weight (BIP141) + (number of
>> non-OP_RETURN outputs - number of inputs) * 41 * 4
>> d. nSigOps * 50 * 90. All SigOps are equal (no witness scaling). For
>> non-segwit txs, the sigops in output scriptPubKey are not counted, while
>> the sigops in input scriptPubKey are counted.
> 
> This is definitely too much. On the one hand its certainly nice to be
> able to use max() for limits, and nice to add all the reasonable limits
> we might want to, but on the other hand this can make things like coin
> selection super complicated - how do you take into consideration the 4
> different limits? Can we do something much, much simpler like
> max(serialized size with some input discount, nSigOps * X) (which is
> what we effectively already have in our mining code)?
> 
>> 90 is the scaling factor for SigHashSize, to maintain the 1:90 ratio
>> (see the BIP in point 3)
>> 50 is the scaling factor for nSigOps, maintaining the 1:50 ratio in BIP141
>>
>> Rationale for adjusted size: 4 is witness scaling factor. 41 is the
>> minimum size for an input (32 hash + 4 index + 4 nSequence + 1
>> scriptSig). This requires people to pre-pay majority of the fee of
>> spending an UTXO. It makes creation of UTXO more expensive, while
>> spending of UTXO cheaper, creates a strong incentive to limit the growth
>> of UTXO set.
>>
>> Rationale for taking the maximum of different metrics: this indirectly
>> set an upper block resources for _every_ metrics, while making the tx
>> fee estimation a linear function. Currently, there are 2 block resources
>> limits: block weight and nSigOp cost (BIP141). However, since users do
>> not know what the other txs are included in the next block, it is
>> difficult to determine whether tx weight of nSigOp cost is a more
>> important factor in determining the tx fee. (This is not a real problem
>> now, because weight is more important in most cases). With an unified
>> definition of tx weight, the fee estimation becomes a linear problem.
>>
>> Translating to new metric, the current BIP141 limit is 360,000,000. This
>> is equivalent to 360MB of sighashing, 2MB of serialised size, 4MB of
>> adjusted size, or 80000 nSigOp.
>>
>> Any new block-level limit metrics could be added to tx weight using soft
>> forks.
>>
>> 5. Smooth halving: the reward of the last 2016 blocks in a halving cycle
>> will be reduced by 25%, which is contributed to the first 2016 blocks of
>> the new halving cycle. (different parameters for forcenet) This makes a
>> more graceful transition but we will lose some fun around halving.
> 
> Hum, not sure this is sufficient. Its still stair-stepping at big enough
> jumps that we could conceivably see super slow block times around
> halvings in the distant future. Maybe instead of 100%-75%-75%-50% (I
> believe that's what you're proposing here?),
> 100%-87.5%-75%-75%-62.5%-50% might be smoother?
> 
>> 6. A new coinbase tx format. BIP34 is removed. Coinbase tx may have more
>> than 1 input. The prevout hash of first input must be the hash of
>> previous block, and index must be 0xffffffff.
> 
> I'm not necessarily opposed to this, but what is the justification for it?
> 
>> The other inputs (if any)
>> must come from UTXOs with valid signatures. Spending of previous
>> coinbase outputs in a coinbase tx is exempted from the 100 block
>> maturity requirement. Therefore, miners of an earlier block may pay
>> other miners to convince them to confirm their blocks.
> 
> Sounds good.
> 
>> 7. Merkle sum tree: it allows generating of fraud-proof for fee and
>> weight. A special softfork (bit 15) is defined. When this softfork is
>> activated, the full node will not validate the sum tree. This is needed
>> because when the definition of tx weight is changed through a softfork
>> (e.g. a new script version introducing new sigop), olds nodes won’t know
>> the new rules and will find the sum tree invalid. Disabling the sum tree
>> validation won’t degrade the security of a full node by more than an
>> usual softfork, because the full node would still validate all other
>> known rules.
>>
>> However, it is still not possible to create fraud proof for spending of
>> non-existing UTXO. This requires commitment of the block height of
>> inputs, and the tx index in the block. I’m not quire sure how this could
>> be implemented because a re-org may change such info (I think validation
>> is easy but mining is more tricky)
> 
> If we cant build wholesale proofs, then lets not jump through hoops and
> add special bits to build partial ones? Its not clear to me that it
> would be any reduction in soft-fork-ability later down the road to not
> have this - if you're changing the definition of tx weight, you're
> likely doing something like segwit where you're adding something else,
> not trying to re-adjust weights.
> 
>> How to join: codes at https://github.com/jl2012/bitcoin/tree/forcenet2 ,
>> start with "bitcoind —forcenet" .
>> Connection: I’m running a node at 8333.info <http://8333.info> with
>> default port (39901)
>> Mining: there is only basic internal mining support. To use the internal
>> miner, writeup a shell script to repeatedly call “bitcoin-cli —forcenet
>> generate 1”
>>
>> jl2012
>>
>>
>> _______________________________________________
>> 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] Forcenet: an experimental network with a new header format

[Johnson Lau]

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


> On 28 Jan 2017, at 10:32, Matt Corallo <lf-lists@mattcorallo.com> wrote:
> 
> Looks cool, though I have a few comments inline.
> 
> One general note - it looks like you're letting complexity run away from
> you a bit here. If the motivation for something is only weak, its
> probably not worth doing! A hard fork is something that must be
> undertaken cautiously because it has so much inherent risk, lets not add
> tons to it.
> 

I think the following features are necessary for a hardfork. The rest are optional:

1. A secondary header
2. Anti-replay
3. SigHash limit for old scripts
4. New tx weight accounting

Optional:
1. New coinbase format is nice but not strictly needed. But this can’t be reintroduced later with softfork due to the 100 block maturity requirement
2. Smooth halving: could be a less elegant softfork
3. Mekle sum tree: definitely could be a softfork

> Matt
> 
> On 01/14/17 21:14, Johnson Lau via bitcoin-dev wrote:
>> I created a second version of forcenet with more experimental features
>> and stopped my forcenet1 node.
>> 
>> 1. It has a new header format: Height (4), BIP9 signalling field (4),
>> hardfork signalling field (2), Hash TMR (32), Hash WMR (32), Merkle sum
>> root (32), number of tx (4), prev hash (32), timestamp (4), nBits (4),
>> nonce1 (4), nonce2 (4), nonce3 (compactSize + variable), merkle branches
>> leading to header C (compactSize + 32 bit hashes)
> 
> In order of appearance:
> 
> First of all lets try to minimize header size. We really dont want any
> more space taken up here than we absolutely need to.
> 
> I'm super unconvinced that we need more than one merkle tree for
> transactions. Lets just have one merkle tree who's leaves are
> transactions hashed 2 ways (without witnesses and only witnesses).
> 
> Why duplicate the nBits here? shouldn't the PoW proof be the
> responsibility of the parent header?
> 

Without nBits in the header, the checking of PoW become contextual and I think that may involve too much change. The saving of these 4 bytes, if it is really desired, might be done on a p2p level 

> I have to agree with Tadge here, variable-length header fields are evil,
> lets avoid them.
> 
> Why have merkle branches to yet another header? Lets just leave it as an
> opaque commitment header (32).
> 
> Finally, lets not jump through hoops here - the transaction merkle root
> of the "old-style" (now PoW) header should simply be the hash of the new
> header. No coinbase transaction, just the hash of the secondary header.
> This saves space without giving up utility - SPV nodes are already not
> looking at the coinbase transaction, so no harm in not having one to give.


Regarding the header format, a big question we never came into consensus is the format of the hardfork. Although I designed forcenet to be a soft-hardfork, I am now more inclined to suggest a simple hardfork, given that the warning system is properly fixed (at the minimum: https://github.com/bitcoin/bitcoin/pull/9443 <https://github.com/bitcoin/bitcoin/pull/9443>)

Assuming a simple hardfork is made, the next question is whether we want to keep existing light wallets functioning without upgrade, cheating them by hiding the hash of the new header somewhere in the transaction merkle tree.

We also need to think about the Stratum protocol. Ideally we should not require firmware upgrade.

For the primary 80 bytes header, I think it will always be a fixed size. But for the secondary header, I’m not quite sure. Actually, one may argue that we already have a secondary header (i.e. coinbase tx), and it is not fixed size.

>> 
>> 4. A totally new way to define tx weight. Tx weight is the maximum of
>> the following metrics:
>> a. SigHashSize (see the bip in point 3)
>> b. Witness serialised size * 2 * 90
>> c. Adjusted size * 90. Adjusted size = tx weight (BIP141) + (number of
>> non-OP_RETURN outputs - number of inputs) * 41 * 4
>> d. nSigOps * 50 * 90. All SigOps are equal (no witness scaling). For
>> non-segwit txs, the sigops in output scriptPubKey are not counted, while
>> the sigops in input scriptPubKey are counted.
> 
> This is definitely too much. On the one hand its certainly nice to be
> able to use max() for limits, and nice to add all the reasonable limits
> we might want to, but on the other hand this can make things like coin
> selection super complicated - how do you take into consideration the 4
> different limits? Can we do something much, much simpler like
> max(serialized size with some input discount, nSigOps * X) (which is
> what we effectively already have in our mining code)?
> 

The max() is at transaction level, not block level. Unless your wallet is full of different types of UTXOs, coin selection would not be more difficult than current.

Among the 4 limits, the SigHash limit is mostly a safety limit that will never be hit by a tx smaller than 100kB. As part of the replay attack fix, a linear SigHash may be optionally used. So wallets may just ignore this limit in coin selection

Similarly, the SigOp limit is also unlikely to be hit, unless you are using a very big multi-sig. Again, this is very uncommon and wallets primarily dealing with signal sig may safely ignore this

Finally, an important principle here is to encourage spending of UTXO, and limiting creation of UTXO. This might be a bit difficult to fully optimise for this, but I think this is necessary evil.

More discussion at: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/013504.html <https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/013504.html>

>> 
>> 
>> 5. Smooth halving: the reward of the last 2016 blocks in a halving cycle
>> will be reduced by 25%, which is contributed to the first 2016 blocks of
>> the new halving cycle. (different parameters for forcenet) This makes a
>> more graceful transition but we will lose some fun around halving.
> 
> Hum, not sure this is sufficient. Its still stair-stepping at big enough
> jumps that we could conceivably see super slow block times around
> halvings in the distant future. Maybe instead of 100%-75%-75%-50% (I
> believe that's what you're proposing here?),
> 100%-87.5%-75%-75%-62.5%-50% might be smoother?
> 

Yes, but maybe we just don’t need this at all. This could also be done with a softfork using OP_CSV, just a bit ugly.

>> 6. A new coinbase tx format. BIP34 is removed. Coinbase tx may have more
>> than 1 input. The prevout hash of first input must be the hash of
>> previous block, and index must be 0xffffffff.
> 
> I'm not necessarily opposed to this, but what is the justification for it?

This allows people to sign an input, to be part of a coinbase tx, but limited to a particular previous block hash. This is currently not possible, but through a later softfork we could introduce a new SigHash function that allows something between SIGHASH_ALL and SIGHASH_ANYONECANPAY, so people may sign its own input and another input, while ignoring the rests of input. (in other words: change the name SIGHASH_ANYONECANPAY to SIGHASH_SINGLE_INPUT, and we introduce SIGHASH_DUAL_INPUT. But we don’t need to do this in this hardfork)


>> The other inputs (if any)
>> must come from UTXOs with valid signatures. Spending of previous
>> coinbase outputs in a coinbase tx is exempted from the 100 block
>> maturity requirement. Therefore, miners of an earlier block may pay
>> other miners to convince them to confirm their blocks.
> 
> Sounds good.
> 
>> 7. Merkle sum tree: it allows generating of fraud-proof for fee and
>> weight. A special softfork (bit 15) is defined. When this softfork is
>> activated, the full node will not validate the sum tree. This is needed
>> because when the definition of tx weight is changed through a softfork
>> (e.g. a new script version introducing new sigop), olds nodes won’t know
>> the new rules and will find the sum tree invalid. Disabling the sum tree
>> validation won’t degrade the security of a full node by more than an
>> usual softfork, because the full node would still validate all other
>> known rules.
>> 
>> However, it is still not possible to create fraud proof for spending of
>> non-existing UTXO. This requires commitment of the block height of
>> inputs, and the tx index in the block. I’m not quire sure how this could
>> be implemented because a re-org may change such info (I think validation
>> is easy but mining is more tricky)
> 
> If we cant build wholesale proofs, then lets not jump through hoops and
> add special bits to build partial ones? Its not clear to me that it
> would be any reduction in soft-fork-ability later down the road to not
> have this - if you're changing the definition of tx weight, you're
> likely doing something like segwit where you're adding something else,
> not trying to re-adjust weights.

This is just a demo, and I agree this could be added through a softfork later. But even if we add this as a softfork, we have to have the ability to disable it through a special softfork. I think I have explained the reason but let me try again.

Here, when I talking about “tx weight”, it’s the “tx weight” defined in point 4, which covers not only size, but also other limits like SigOp. For a fraud proof to be really useful, it has to cover every type of block level limits. One feature of segwit is the script versioning, which allows introduction of new scripts. In the process, we will change the definition of SigOp: previous 0 SigOp scripts now carries some amount of SigOp. This is by itself a softfork (we did this type of softfork twice already: P2SH and segwit). However, if we have a merkle sum root covering the SigOp, old nodes won’t count these new SigOps, and they will fail to validate the sum root.

Without a backdoor to disable the sum tree validation in old nodes, the only way would be keeping the original sum tree untouched, while create another sum tree, every time we have a new script version. This is not acceptable at all.

But even such backdoor would not be harmful to the security of full nodes because they will still fully verify the tx and witness merkle root.

I’d argue that any fraud proof related commitment: sum tree, delayed UTXO commitment etc will require such a backdoor to disable. Maybe we should just remove this from here and make this a new topic. We could even do this as a softfork today.



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

Re: [bitcoin-dev] Forcenet: an experimental network with a new header format

[Matt Corallo]

Replies inline.

On 01/28/17 07:28, Johnson Lau wrote:
> 
>> On 28 Jan 2017, at 10:32, Matt Corallo <lf-lists@mattcorallo.com
>> <mailto:lf-lists@mattcorallo.com>> wrote:
>>
>> Looks cool, though I have a few comments inline.
>>
>> One general note - it looks like you're letting complexity run away from
>> you a bit here. If the motivation for something is only weak, its
>> probably not worth doing! A hard fork is something that must be
>> undertaken cautiously because it has so much inherent risk, lets not add
>> tons to it.
>>
> 
> I think the following features are necessary for a hardfork. The rest
> are optional:
> 
> 1. A secondary header
> 2. Anti-replay
> 3. SigHash limit for old scripts
> 4. New tx weight accounting

Agreed.

> Optional:
> 1. New coinbase format is nice but not strictly needed. But this can’t
> be reintroduced later with softfork due to the 100 block maturity
> requirement
> 2. Smooth halving: could be a less elegant softfork
> 3. Mekle sum tree: definitely could be a softfork

Agreed. Would like 1, dont care about 2, not a fan of 3. 2 could even be
implemented easily as a softfork if we allow the
spend-other-coinbase-outputs from 1.

>>
>> On 01/14/17 21:14, Johnson Lau via bitcoin-dev wrote:
>>> I created a second version of forcenet with more experimental features
>>> and stopped my forcenet1 node.
>>>
>>> 1. It has a new header format: Height (4), BIP9 signalling field (4),
>>> hardfork signalling field (2), Hash TMR (32), Hash WMR (32), Merkle sum
>>> root (32), number of tx (4), prev hash (32), timestamp (4), nBits (4),
>>> nonce1 (4), nonce2 (4), nonce3 (compactSize + variable), merkle branches
>>> leading to header C (compactSize + 32 bit hashes)
>>
>> In order of appearance:
>>
>> First of all lets try to minimize header size. We really dont want any
>> more space taken up here than we absolutely need to.
>>
>> I'm super unconvinced that we need more than one merkle tree for
>> transactions. Lets just have one merkle tree who's leaves are
>> transactions hashed 2 ways (without witnesses and only witnesses).
>>
>> Why duplicate the nBits here? shouldn't the PoW proof be the
>> responsibility of the parent header?
>>
> 
> Without nBits in the header, the checking of PoW become contextual and I
> think that may involve too much change. The saving of these 4 bytes, if
> it is really desired, might be done on a p2p level 

Hmm? I'm saying that "the header" should be viewed as both the
"top-level" PoW-proving header, and the sub-header. There is no need to
have nBits in both?

>> I have to agree with Tadge here, variable-length header fields are evil,
>> lets avoid them.
>>
>> Why have merkle branches to yet another header? Lets just leave it as an
>> opaque commitment header (32).
>>
>> Finally, lets not jump through hoops here - the transaction merkle root
>> of the "old-style" (now PoW) header should simply be the hash of the new
>> header. No coinbase transaction, just the hash of the secondary header.
>> This saves space without giving up utility - SPV nodes are already not
>> looking at the coinbase transaction, so no harm in not having one to give.
> 
> 
> Regarding the header format, a big question we never came into consensus
> is the format of the hardfork. Although I designed forcenet to be a
> soft-hardfork, I am now more inclined to suggest a simple hardfork,
> given that the warning system is properly fixed (at the
> minimum: https://github.com/bitcoin/bitcoin/pull/9443)
> 
> Assuming a simple hardfork is made, the next question is whether we want
> to keep existing light wallets functioning without upgrade, cheating
> them by hiding the hash of the new header somewhere in the transaction
> merkle tree.
> 
> We also need to think about the Stratum protocol. Ideally we should not
> require firmware upgrade.
> 
> For the primary 80 bytes header, I think it will always be a fixed size.
> But for the secondary header, I’m not quite sure. Actually, one may
> argue that we already have a secondary header (i.e. coinbase tx), and it
> is not fixed size.

We can safely disable SPV clients post-fork by just keeping the header
format sufficiently compatible with PR#9443 without caring about the
coinbase transaction, which I think should be the goal.

Regarding firmware upgrade, you make a valid point. I suppose we need
something that looks sufficiently like a coinbase transaction that
miners can do nonce-rolling using existing algorithms. Personally, I'd
kinda prefer something like a two-leaf merkle tree root as the merkle
root in the "primary 80-byte header" (can we agree on terminology for
this before we go any further?) - the left one is a
coinbase-transaction-looking thing, the right one the header of the new
block header.

>>>
>>> 4. A totally new way to define tx weight. Tx weight is the maximum of
>>> the following metrics:
>>> a. SigHashSize (see the bip in point 3)
>>> b. Witness serialised size * 2 * 90
>>> c. Adjusted size * 90. Adjusted size = tx weight (BIP141) + (number of
>>> non-OP_RETURN outputs - number of inputs) * 41 * 4
>>> d. nSigOps * 50 * 90. All SigOps are equal (no witness scaling). For
>>> non-segwit txs, the sigops in output scriptPubKey are not counted, while
>>> the sigops in input scriptPubKey are counted.
>>
>> This is definitely too much. On the one hand its certainly nice to be
>> able to use max() for limits, and nice to add all the reasonable limits
>> we might want to, but on the other hand this can make things like coin
>> selection super complicated - how do you take into consideration the 4
>> different limits? Can we do something much, much simpler like
>> max(serialized size with some input discount, nSigOps * X) (which is
>> what we effectively already have in our mining code)?
>>
> 
> The max() is at transaction level, not block level. Unless your wallet
> is full of different types of UTXOs, coin selection would not be more
> difficult than current.

Yes, I got the max() being at the transaction level (at the block level
would just be stupid) :).

This does not, however, make UTXO selection trivial, indeed, the second
you start having not-completely-homogeneous UTXOs in your wallet you
have to consider "what if the selection of this UTXO would switch my
criteria from one to another", which I believe makes this nonlinear.

> Among the 4 limits, the SigHash limit is mostly a safety limit that will
> never be hit by a tx smaller than 100kB. As part of the replay attack
> fix, a linear SigHash may be optionally used. So wallets may just ignore
> this limit in coin selection

So lets apply this only to non-Segwit-hashed transactions (incl
transactions which opted into the new sighash rules using the
anti-replay stuff)?

> Similarly, the SigOp limit is also unlikely to be hit, unless you are
> using a very big multi-sig. Again, this is very uncommon and wallets
> primarily dealing with signal sig may safely ignore this

Yes, I tend to agree that there isnt much way around a sigops limit (as
we have now).

> Finally, an important principle here is to encourage spending of UTXO,
> and limiting creation of UTXO. This might be a bit difficult to fully
> optimise for this, but I think this is necessary evil.

Totally agree there, but we can easily discount inputs more than outputs
to accomplish this for most potential outputs, I believe.

Did I miss a justification for there being a separate b (witness
serialized size) and c (txweight-with-discounts?).

> More discussion
> at: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/013504.html
> 
>>>
>>>
>>> 5. Smooth halving: the reward of the last 2016 blocks in a halving cycle
>>> will be reduced by 25%, which is contributed to the first 2016 blocks of
>>> the new halving cycle. (different parameters for forcenet) This makes a
>>> more graceful transition but we will lose some fun around halving.
>>
>> Hum, not sure this is sufficient. Its still stair-stepping at big enough
>> jumps that we could conceivably see super slow block times around
>> halvings in the distant future. Maybe instead of 100%-75%-75%-50% (I
>> believe that's what you're proposing here?),
>> 100%-87.5%-75%-75%-62.5%-50% might be smoother?
>>
> 
> Yes, but maybe we just don’t need this at all. This could also be done
> with a softfork using OP_CSV, just a bit ugly.

Or by allowing coinbase txn to spend previous coinbase outputs. This
seems to not be an issue at present, though is something to consider in
future soft forks, so, agreed, lets table this and make sure we're set
up to do it in a soft fork if we need to.

>>> 6. A new coinbase tx format. BIP34 is removed. Coinbase tx may have more
>>> than 1 input. The prevout hash of first input must be the hash of
>>> previous block, and index must be 0xffffffff.
>>
>> I'm not necessarily opposed to this, but what is the justification for it?
> 
> This allows people to sign an input, to be part of a coinbase tx, but
> limited to a particular previous block hash. This is currently not
> possible, but through a later softfork we could introduce a new SigHash
> function that allows something between SIGHASH_ALL and
> SIGHASH_ANYONECANPAY, so people may sign its own input and another
> input, while ignoring the rests of input. (in other words: change the
> name SIGHASH_ANYONECANPAY to SIGHASH_SINGLE_INPUT, and we introduce
> SIGHASH_DUAL_INPUT. But we don’t need to do this in this hardfork)

Hmm, cant we accomplish this with a future sighash mode in which you
simply include the block's hash in the sighash and then spend to an
anyone-can-spend?

-snip-

>>> 7. Merkle sum tree: it allows generating of fraud-proof for fee and
>>> weight. A special softfork (bit 15) is defined. When this softfork is
>>> activated, the full node will not validate the sum tree. This is needed
>>> because when the definition of tx weight is changed through a softfork
>>> (e.g. a new script version introducing new sigop), olds nodes won’t know
>>> the new rules and will find the sum tree invalid. Disabling the sum tree
>>> validation won’t degrade the security of a full node by more than an
>>> usual softfork, because the full node would still validate all other
>>> known rules.
>>>
>>> However, it is still not possible to create fraud proof for spending of
>>> non-existing UTXO. This requires commitment of the block height of
>>> inputs, and the tx index in the block. I’m not quire sure how this could
>>> be implemented because a re-org may change such info (I think validation
>>> is easy but mining is more tricky)
>>
>> If we cant build wholesale proofs, then lets not jump through hoops and
>> add special bits to build partial ones? Its not clear to me that it
>> would be any reduction in soft-fork-ability later down the road to not
>> have this - if you're changing the definition of tx weight, you're
>> likely doing something like segwit where you're adding something else,
>> not trying to re-adjust weights.
> 
> This is just a demo, and I agree this could be added through a softfork
> later. But even if we add this as a softfork, we have to have the
> ability to disable it through a special softfork. I think I have
> explained the reason but let me try again.
> 
> Here, when I talking about “tx weight”, it’s the “tx weight” defined in
> point 4, which covers not only size, but also other limits like SigOp.
> For a fraud proof to be really useful, it has to cover every type of
> block level limits. One feature of segwit is the script versioning,
> which allows introduction of new scripts. In the process, we will change
> the definition of SigOp: previous 0 SigOp scripts now carries some
> amount of SigOp. This is by itself a softfork (we did this type of
> softfork twice already: P2SH and segwit). However, if we have a merkle
> sum root covering the SigOp, old nodes won’t count these new SigOps, and
> they will fail to validate the sum root.
> 
> Without a backdoor to disable the sum tree validation in old nodes, the
> only way would be keeping the original sum tree untouched, while create
> another sum tree, every time we have a new script version. This is not
> acceptable at all.

Hmm, I think you missed my point - if we're soft-forking in a new limit,
we can trivially add a new merkle tree over only that limit, which is
sufficient to make fraud proofs for the new limit.

> But even such backdoor would not be harmful to the security of full
> nodes because they will still fully verify the tx and witness merkle root.

Sure, but now miners can disable fraud proofs using a simple majority,
which really, super sucks.

> I’d argue that any fraud proof related commitment: sum tree, delayed
> UTXO commitment etc will require such a backdoor to disable. Maybe we
> should just remove this from here and make this a new topic. We could
> even do this as a softfork today.

Yes, lets skip it for now, I dont see much value in debating it for a HF
now.