Auxiliary Header - abusing "blank" transactions

[TierNolan]

If there are (2^n) + 1 transactions, then the last transaction is hashed with itself over and over at each merkle tree stage.

For example, if there were 5 (4 + 1) transactions, then the tree is calculated as follows.

A, B, C, D, E

The first pass takes 5 hashes and reduces it to 3

X = H(A, B)
Y = H(C, D)
Z = H(E, E)  (E hashed with itself)

X, Y, Z

The next pass takes 3 and reduces it to 2

M = H(X, Y)
N = H(Z, Z) (Z hashed with itself)

These are then combined to give the final root.

H(M, N)

However, Z is H(E, E), so N is purely determined by E.

The deeper the tree, the more hashes need to be performed, but it is still purely decided by E.

This means that to prove that E was in the tree, you just need to provide E (so N can be computed), M and the depth of the tree.  

This is much more compact.

From what I can gather a transaction is valid if it has at least 1 input and 1 output.  However, the value of an output can be zero.

A transaction would be valid if it moved 0BTC from some output to the transaction's output.

If a transaction was created which paid 0BTC to OP_TRUE, then it could be used as the start of a "blank" transaction chain.

The transaction itself could be used as the source for the next transaction, so only 1 is needed.

This would allow padding the transaction list out to a power of 2.  Each transaction would use the previous padding transaction as input.

The final transaction would be transaction E, and would include Hash(auxiliary root) as part of its script.

The header could then be expanded past 80 bytes.

Standard - 80 bytes
int version
Hash previous
Hash merkle
int timestamp
int bits
int nonce

Info - 65 bytes
Hash "M"
Hash previous-transaction used by E
var_int tree_depth
var_int extra_field_length

Extra fields - ??
var_int blockHeight (for example)

The E transaction can be determined by knowing the previous transaction that it spends.  The rest of the transaction is standard and Hash(extra fields) is included in the transaction.  All of this info is included in the expanded header.

This allows the full header + auxiliary header to be verified without needing any other info.

It is backward compatible.

The disadvantage is transaction spam.  However, miners could be encouraged to aim for powers of 2 of transactions.

Also, each transaction is generated deterministically from the previous one, so it isn't really spam, it is just a compression problem.

It also increased the header size from 80 bytes to 145 bytes, but it allows the header to be expanded indefinitely, while still incorporating the new fields into the block chain.

The extra_field_length variable would mean that clients could still verify headers which have newer fields than the client understands.

[1715240546]

1715240546

[1715240546]

1715240546

[1715240546]

1715240546

[1715240546]

1715240546

[1715240546]

1715240546

[jl2012]

So the number of transaction must be a power of 2? This sounds interesting but not very practical. When block space becomes really scarce, the cost would be too much. Old clients won't understand the "compression" you suggested, so eventually you need a hard-fork

[TierNolan]

So the number of transaction must be a power of 2? This sounds interesting but not very practical. When block space becomes really scarce, the cost would be too much. Old clients won't understand the "compression" you suggested, so eventually you need a hard-fork

The point of the padding is to expand it to a power of 2.

Each block can handle 4000 transactions.  You either use padding or not.

[jl2012]

This is a clever hack but the cost to implement is too high.

Could you name some cases which we need extra header fields, and putting the info in coinbase (like block v2)  is not enough? (e.g. Your sub-block proposal)

[TierNolan]

This is a clever hack but the cost to implement is too high.

If miners restricted themselves to powers of 2 transactions, then the cost would be zero (well 1 extra transaction).

In the period where minting fees dominate, it doesn't cause that big a problem.

Miners could just stop when they hit a power of 2, unless they have enough to get to the next power of 2.

Even when tx fees dominate, if it was a network rule, then miners could optimize to try to get the block up to 1MB.

The cost is a tradeoff.  I am thinking of a situation where a node just wants to download and verify the headers.

If the extra field is in the coinbase transaction, they you have to provide the entire merkle path down to the coinbase.

If a block has 65 - 128 transactions, then the tree depth is 7.  The path to the coinbase is 32 * 7 = 224 bytes.

You also need to provide the coinbase.

I guess it isn't that big a cost.  The "extended" header would be 80 + 224 + coinbase_size.

A compromise would be to add an extra transactions to block right after the coin-base.

0: coinbase
1: tx-pad

This would allow the coinbase to be large without it causing the virtual header from being larger.

With 4096 transactions, that is a depth of 12, the the total header size would be

Path: 11 * 32
Input tx: 32
Aux header: 32
Extra length: 1

That gives 417 bytes (plus the extra fields).  The original proposal would give 145 byte headers (plus extra fields).

Could you name some cases which we need extra header fields, and putting the info in coinbase (like block v2)  is not enough? (e.g. Your sub-block proposal)

The sub-block thing doesn't require a header change (the latest proposal definitely).  It just requires distribution of headers for blocks that didn't quite meet POW.

I was thinking in general.

I think it would be a good idea to reserve 32 bytes in the coinbase transaction as the hash of the extra header info.

The "high hash highway" is a pretty good idea but it adds a 2nd link into the block header.

[jl2012]

If the max block size is raised and we can process million of tx in a block, the "powers of 2" requirement becomes exponentially difficult to archive. (In this case we need a hardfork anyway, so we don't really need a hack like this)

To allow future expansion, it may be better to allow a few hundreds bytes of free space in the block header.

[TierNolan]

To allow future expansion, it may be better to allow a few hundreds bytes of free space in the block header.

If there is a hard fork, I agree, it is better to fix it cleanly.

The problem is hard forks happen, and they are minimal changes (for safety reasons).

The 1MB change would be planned in advance though.

ASICs aren't going to be able to handle non-standard headers (maybe).

With a hard fork, the new header could be changed to:

int: version
hash: prev
hash: merkle_root
int: timestamp
int: diff
int: nonce
<extra fields>
<info fields>

When computing the block hash, the merkle root should be replaced.

block_hash = Hash(
version +
prev +
hash(merkle_root + extra_fields) +
timestamp +
diff +
nonce
)

This means that mining hardware doesn't even need to be changed.  The merkle root is just replaced.

Maybe a BIP should be created as a proposal.

- merkle tree changed to fee tree
- auxiliary fields

Another change that would be good would be the one for Armory.  This is where the input value for transactions can be included in the tx hash.