Topic: Merkle Sum Tree Proposal (Read 2291 times)

That isn't the only benefit.

Fraud proofs are also very important for auditing by SPV clients.  With sum-trees, it is possible to show that the fee maths has been violated with a short proof.  If you find 1 step in the calculation that is wrong, and can create a proof based on just that one step.  A block is invalid even if a single calculation is incorrect.

With the current system, you need to scan the entire block to see if miners are inflating the currency.  In addition to that, when checking a transaction, you need to include the input transaction for every input into the transaction.  That could be 2-3X more data required.

If blocks are 20MB, then fraud proofs could be 60MB or more.

I really hope that this proposal gets adopted as it will allow for "100% air-gapped" offline tx signing to be done without needing any blockchain information (just the tx itself) in order to show the person signing the inputs, outputs, the change *and the fee* (the last not being possible currently).

Personally I have always felt that this was an oversight by Satoshi.

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 Tree

Each 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 Extra

Proving 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.