bitcoin/bitcoin — pull request #3977 by maaku (2014-03-28 22:41:33+00:00)
Title: [soft fork] Block v3: miner commitments with compact proofs

There are proposals in the pipeline, and some currently deployed applications which require commitments of special forms of data to the blockchain by miners. For example, merged mining requires each block to have a data commitment at a single deterministically identifiable position. UTXO hash-tree commitments adds the root hash of a Merkle tree of the current validation state at a similarly known or identifiable position such that clients using such an index structure can acquire UTXO proofs with SPV security. Compact SPV proofs require commitments of a Merkle heap or skip list structure of past block headers, for the purpose of constructing traversals through the block headers with logarithmic scaling in space. All of these miner-commitment applications require to varying degrees three essential properties:

1. *A unique or identifiable place within the block where the commitment is to be placed*. For a given commitment type the miner must know where to put the commitment into a block template, someone using it must know where to find it within a block or its Merkle proof (the transaction containing the commitment, the path to the transaction through the Merkle tree of the block, and the block header).

2. *Impossible for a miner to create multiple block commitments of the same type within the context of a single block*. A user given just the transaction containing the commitment, its path through the Merkle tree, and the block header must have confidence that the commitment is of the indicated type, and the only one of that type in the block.

3. *Compact commitment proofs*. The transaction containing the commitment should contain no more information than is necessary to uniquely identify the commitment type and the commitment itself, so as to minimize the size of commitment Merkle proofs. Achieving this property directly benefits protocols built on top of data commitments.

The only extant example of miner commited data in Bitcoin Core is BIP 34, which add the block height to the coinbase string in order to ensure coinbase transaction uniqueness. Higher level protocols such as p2pool and namecoin's merged mining also require commitments via the coinbase transaction. However such schemes fail to meet one or more of the properties above, especially the requirement for compact commitment proofs: coinbase transactions can be unreasonably large due to mining pool payout schedules and the increasing amount of data being stuffed in the coinbase string.

An alternative is to use transactions of a special form, and a separate transaction for each commitment. These commitment transactions have a single input whose scriptSig consists of a single data push, the contents of which is the commitment type:

scriptPubKey: OP_EQUAL
scriptSig:

The outputs of the transaction are available for prune-able OP_RETURN data commitments. In order to meet requirement #1 and #2, a soft-fork validation rule is added such that any block containing two such special-form transactions with the same commitment type is rejected, and the anyone-can-spend outputs of the form ` OP_EQUAL` must be present for each required commitment, in order to provide an output to be spent COINBASE_MATURITY blocks later. It is suggested that one data commitment be set aside for the purpose of document timestamping, merged mining, and other applications which do not need additional validation rules. This patchset sets aside the `OP_0` commitment type for this purpose.