In
another thread, I suggested that the upcoming hard fork for block size is a opportunity to submit other hard-fork changes.
[edit]I created a draft
BIP[/edit]
If they are "no-brainers", then they have a reasonable chance of being accepted if there is merge-ready code available and there is consensus that it is useful and low-risk. Controversial changes are much more likely to be passed over.
Sum based Merkle trees allow compact proofs that miners are trying to inflate the currency by paying themselves higher fees than the rules allow.
This makes it possible for auditing the block chain and if any fraud is found, sending a short proof that a particular block is invalid. Clients could then blacklist the block.
The fraud proof is not a hard-fork, but changing the way the Merkle tree is calculated is.
Merkle Sum TreeEach leaf of the tree is a transaction. The current serialization of the transaction doesn't allow the fee to be calculated by just looking at the transaction.
I suggest that the transaction serialization is changed so that input values are included in the transaction.
Each input contains
hash( 32 ): Hash of the previous output tx
int( 4 ): index
var_int(1+): script_length
char[script_length]: sigScript
This could be changed to include the input value
hash( 32 ): Hash of the previous output tx
long( 8 ): value
int( 4 ): index
var_int(1+): script_length
char[script_length]: sigScript
This allows processing of the transaction to compute the fee paid by this transaction. Coinbase transactions would have an input value of 0.
At 250 bytes per transaction and 2 inputs, this would increase the tx size by 6.4%. Transaction which are dominated by the size of the inputs would increase by 10% (assuming a sigScript length of 50).
A transaction would be invalid if the input value is different from the matching output value and it would have to be within the valid money range.
The fee for a transaction would be equal to the sum of the output values minus the sum of the input values.
A 36 byte digest must be produced for each transaction as input into the Merkle sum hash algorithm.
The digest of a transaction is {little_endian(fee), DoubleSHA256(transaction)}
The parent digest for two child digests is {little_endian(left_fee + right_fee), DoubleSHA256(left_digest | right_digest)}
The root of the tree is a 36 byte array. The final Merkle root is then DoubleSHA256(sum tree root).
This gives the benefits of a sum-tree without changing the size of the merkle root.
The costs for this proposal are
6.4% increase in block size
Input value must be read when checking transactions (but that should happen anyway)
Optional ExtraProving that an input is invalid requires providing the entire transaction. For very large transactions, this makes the fraud proof large.
The sum tree could be propagated down to the inputs and outputs of the transaction.
The sigScripts and the sigPubKeys can be long arrays. They can be replaced by hashes to keep the size of the fraud proof limited.
A input is of the form:
output_hash( 32 ): Hash of the previous output tx
long( 8 ): value
int( 4 ): index
var_int(1+): script_length
char[script_length]: sigScript
The 36 byte digest would be {little_endian(value), DoubleSHA256(Prev_tx | little_endian(value) | little_endian(index) | DoubleSHA256(sigScript))}
The fraud proof would only include DoubleSHA256(sigScript). The length of the script is irrelevant.
Outputs are of the form:
long( 8 ): value
var_int(1+): script_length
char[script_length]: scriptPubKey
The 36 byte digest would be {little_endian(value) | DoubleSHA256(value | DoubleSHA256(scriptPubKey))}
The Merkle sum root for the outputs and the inputs could be computed. The digest for the transaction would be
{little_endian(mint_fee(*) + input_value - output_value), DoubleSHA256(little_endian(tx_version) | input_digest | output_digest | little_endian(lock_time)}
(*) Coinbase only
The entire transaction is still hashed one way or another. The lengths for the scripts would have to be encoded minimally or the encoding of the length also needs to be added into the doubleSHA256.
