Discussion:
Forcenet: an experimental network with a new header format
(too old to reply)
Johnson Lau via bitcoin-dev
2016-12-04 19:34:00 UTC
Permalink
Raw Message
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
adiabat via bitcoin-dev
2016-12-04 20:00:00 UTC
Permalink
Raw Message
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
Post by Johnson Lau via bitcoin-dev
some amendments as I implemented it. The format is (size in parentheses;
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
Hampus Sjöberg via bitcoin-dev
2016-12-04 20:37:39 UTC
Permalink
Raw Message
Post by adiabat via bitcoin-dev
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 <
Post by adiabat via bitcoin-dev
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
Post by Johnson Lau via bitcoin-dev
some amendments as I implemented it. The format is (size in parentheses;
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Tom Zander via bitcoin-dev
2016-12-05 11:58:54 UTC
Permalink
Raw Message
On Sunday, 4 December 2016 21:37:39 CET Hampus Sjöberg via bitcoin-dev
Post by Hampus Sjöberg via bitcoin-dev
Post by adiabat via bitcoin-dev
Also how about making timestamp 8 bytes? 2106 is coming up soon
https://github.com/jl2012/bitcoin/commit/
fa80b48bb4237b110ceffe11edc14c813
Post by Hampus Sjöberg via bitcoin-dev
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
Johnson Lau via bitcoin-dev
2016-12-14 11:01:58 UTC
Permalink
Raw Message
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.
Post by Tom Zander via bitcoin-dev
On Sunday, 4 December 2016 21:37:39 CET Hampus Sjöberg via bitcoin-dev
Post by Hampus Sjöberg via bitcoin-dev
Post by adiabat via bitcoin-dev
Also how about making timestamp 8 bytes? 2106 is coming up soon
https://github.com/jl2012/bitcoin/commit/
fa80b48bb4237b110ceffe11edc14c813
Post by Hampus Sjöberg via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Luke Dashjr via bitcoin-dev
2016-12-14 11:07:14 UTC
Permalink
Raw Message
Post by Johnson Lau via bitcoin-dev
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
Johnson Lau via bitcoin-dev
2016-12-14 11:12:45 UTC
Permalink
Raw Message
Post by Luke Dashjr via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
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
Johnson Lau via bitcoin-dev
2016-12-14 11:11:29 UTC
Permalink
Raw Message
Post by adiabat via bitcoin-dev
Interesting stuff! I have some comments, mostly about the header.
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.
Post by adiabat via bitcoin-dev
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
Post by adiabat via bitcoin-dev
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>
Post by adiabat via bitcoin-dev
Also how about making timestamp 8 bytes? 2106 is coming up soon :)
No need. See my other reply
Post by adiabat via bitcoin-dev
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
Tier Nolan via bitcoin-dev
2016-12-10 21:29:09 UTC
Permalink
Raw Message
On Sun, Dec 4, 2016 at 7:34 PM, Johnson Lau via bitcoin-dev <
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
5. Many other interesting hardfork ideas, and softfork ideas that works
better with a header redesign
That is very true.
Luke Dashjr via bitcoin-dev
2016-12-10 21:41:57 UTC
Permalink
Raw Message
Post by Tier Nolan via bitcoin-dev
On Sun, Dec 4, 2016 at 7:34 PM, Johnson Lau via bitcoin-dev <
Post by Johnson Lau via bitcoin-dev
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.
Post by Tier Nolan via bitcoin-dev
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.
Post by Tier Nolan via bitcoin-dev
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.
Post by Tier Nolan via bitcoin-dev
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
Tier Nolan via bitcoin-dev
2016-12-11 16:40:30 UTC
Permalink
Raw Message
Post by Luke Dashjr via bitcoin-dev
Post by Tier Nolan via bitcoin-dev
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.
Johnson Lau via bitcoin-dev
2016-12-14 10:55:39 UTC
Permalink
Raw Message
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.
Post by Luke Dashjr via bitcoin-dev
Post by Tier Nolan via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Tier Nolan via bitcoin-dev
2016-12-14 12:52:14 UTC
Permalink
Raw Message
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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?
Post by Johnson Lau via bitcoin-dev
Post by Tier Nolan via bitcoin-dev
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.
Johnson Lau via bitcoin-dev
2016-12-14 15:45:37 UTC
Permalink
Raw Message
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
Post by Johnson Lau via bitcoin-dev
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?
Post by Luke Dashjr via bitcoin-dev
Post by Tier Nolan via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
Tier Nolan via bitcoin-dev
2016-12-14 16:26:58 UTC
Permalink
Raw Message
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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).
Post by Johnson Lau via bitcoin-dev
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
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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 <
Post by Johnson Lau via bitcoin-dev
Post by Tier Nolan via bitcoin-dev
Any new merkle algorithm should use a sum tree for partial validation
and
Post by Tier Nolan via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Johnson Lau via bitcoin-dev
2017-01-14 21:14:55 UTC
Permalink
Raw Message
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
Matt Corallo via bitcoin-dev
2017-01-28 02:32:26 UTC
Permalink
Raw Message
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
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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
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)?
Post by Johnson Lau via bitcoin-dev
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?
Post by Johnson Lau via bitcoin-dev
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?
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Matt Corallo via bitcoin-dev
2017-01-28 03:02:21 UTC
Permalink
Raw Message
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
Post by Matt Corallo via bitcoin-dev
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
Post by Johnson Lau via bitcoin-dev
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)
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.
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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
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)?
Post by Johnson Lau via bitcoin-dev
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?
Post by Johnson Lau via bitcoin-dev
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?
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Johnson Lau via bitcoin-dev
2017-01-28 07:28:14 UTC
Permalink
Raw Message
Post by Matt Corallo via bitcoin-dev
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
Post by Matt Corallo via bitcoin-dev
Matt
Post by Johnson Lau via bitcoin-dev
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)
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
Post by Matt Corallo via bitcoin-dev
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.
Post by Matt Corallo via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
4. A totally new way to define tx weight. Tx weight is the maximum of
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>
Post by Matt Corallo via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
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.
Post by Matt Corallo via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
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)
Post by Matt Corallo via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.
Matt Corallo via bitcoin-dev
2017-01-28 17:14:02 UTC
Permalink
Raw Message
Replies inline.
Post by Johnson Lau via bitcoin-dev
Post by Matt Corallo via bitcoin-dev
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.
1. A secondary header
2. Anti-replay
3. SigHash limit for old scripts
4. New tx weight accounting
Agreed.
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
Post by Matt Corallo via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
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)
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?
Post by Johnson Lau via bitcoin-dev
Post by Matt Corallo via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
Post by Matt Corallo via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
4. A totally new way to define tx weight. Tx weight is the maximum of
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.
Post by Johnson Lau via bitcoin-dev
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)?
Post by Johnson Lau via bitcoin-dev
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).
Post by Johnson Lau via bitcoin-dev
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?).
Post by Johnson Lau via bitcoin-dev
More discussion
at: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/013504.html
Post by Matt Corallo via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
Post by Matt Corallo via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
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-
Post by Johnson Lau via bitcoin-dev
Post by Matt Corallo via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.

Loading...