Block Header Commitments Discussion

davecgh commented 6 years ago

I'd like to open community discussion and request feedback on potential hard-forking changes to the Decred block header. Obviously, a full blown DCP with additional details such as a description of fraud and inclusion proofs, a full specification versus the informal one provided here, discussion of other designs considered, deployment specifics, and test vectors will be required before any type of vote on this could happen. The intention here is to focus solely on the nuts and bolts of the proposed changes as preliminary work toward that end.

Abstract

This proposes modifications to the block header to provide an extensible framework, via future consensus-voted hard forks, for adding consensus-enforced commitments to the header without requiring any changes to its size or mining-related field offsets.

Motivation

Currently, the only fully supported trustless security model in Decred is the full-node model where every node and wallet is required to have access to the entire blockchain to verify every block faithfully follows all of consensus validation rules.

While this model provides the highest security guarantees and is required by the consensus daemon to provide an ordered and timestamped public ledger that protects against double spends and modification of existing transactions, it is highly desirable to support other security models where applications can make varying levels of security tradeoffs according to their domain in exchange for no longer requiring access to whole blocks or the entire blockchain.

Simplified Payment Verification (SPV)

One well-known alternative security model that was discussed in the original Bitcoin whitepaper is SPV. This model supports verifying payments without requiring access to the entire blockchain in exchange for trusting proof-of-work miners to verify the history and a stronger non-partitioning assumption. However, as the whitepaper notes, this means that if an attacker is able to overpower the network, it can trick SPV nodes into believing fabricated transactions are valid for as long as the attacker overpowers the network.

In addition to all potential avenues for fraud typical to pure proof-of-work systems, Decred's hybrid proof-of-work and proof-of-stake model adds additional considerations such as consensus voting results, ticket selection semantics, and block invalidation. Another complication with this model that was not discussed in the paper is that it relies on the ability to identify and retrieve relevant transactions which can be challenging to do without leaking information regarding coin ownership, which is not ideal from a privacy perspective.

Nevertheless, it is possible to bring the SPV security level very close to that of full nodes through a combination of committed fraud proofs, inclusion proofs, and filters so long as there is at least one honest fully-validating node on the network to sound the alarm. This is the case because once it is possible to generate a compact fraud proof which SPV nodes can verify quickly, they can securely reject the associated invalid block(s) accordingly.

Compare this model to the completely trust-based model many lightweight and mobile wallets use today where they communicate with a centralized server controlled by the wallet vendor and simply trust everything the service reports.

Alternative Security Models

There are also a variety of other security models with varying levels of tradeoffs that can be achieved by making commitments which allow compact proofs that can be verified quickly readily available. A couple of examples are history pruning with full validation starting from the first non-pruned block, and selective proofing.

With careful design, applications can make use of relevant committed proofs to offer strong cryptographic guarantees of certain aspects without needing to fully validate the entire chain themselves. Such models are typically highly preferable to the fully trust-based models that most applications use at the current time.

Informal Specification

Repurpose the StakeRoot field to house a commitment root and rename it to CommitmentRoot accordingly
Calculate the new CommitmentRoot field as the root of a Merkle tree whose leaves are the individual hashes for each desired commitment
- In order to avoid complicating this proposal, the field MUST be set to the zero hash (32-bytes of zeros) to indicate no specific commitments to include are defined
Modify the existing MerkleRoot field to include the stake transactions in addition to the regular transactions to ensure the header still commits to them by calculating it as BLAKE256(regular_tx_tree_merkle_root || stake_tx_tree_merkle_root)
- Note that this is simply itself a two-leaf Merkle tree that consists of the two Merkle roots of the respective transaction trees.

Rationale

The most efficient and convenient location to store consensus-enforced commitments which allow compact proofs to be generated is the block header. Additionally, most software which works with the blockchain nearly always already requires access to the block headers in order to follow the chain with the most proof-of-work and prove transactions are included in the associated block by making use of the committed Merkle root. Further, since headers are already an integral part of the system, there is already significant tooling for acquiring and working with them.

The proposed changes are intentionally engineered to avoid changing the overall size of the header and field offsets of all mining-related fields to prevent breaking existing mining hardware and infrastructure that secures the network.

The StakeRoot field was repurposed to house the new commitment scheme since it is already the correct size for a commitment merkle root hash and the stake transaction tree merkle root can be rolled into the existing MerkleRoot field elegantly without requiring significant modifications.

Making use of a Merkle tree for calculating the new CommitmentRoot field allows efficient log-sized inclusion proofs of the commitments to be generated and requested from untrusted sources. Further, each leaf is itself intended to be a commitment to some arbitrary data which will typically be some structure that employs techniques that also allow compact fraud and inclusion proofs to be constructed such as Fenwick trees, Golomb-Rice filters, and additional Merkle trees.

This approach provides an extensible and efficient method of consensus-enforced proof chaining which allows the block header to commit to an arbitrary number of short proofs which thin clients can very quickly verify.

sumiflow commented 6 years ago

I'm surprised this doesn't have more discussion. Secure SPV seems like a huge step forward to me. Maybe not many people understand this? Maybe they do understand but can't think of any downsides?

I would love to hear from anyone who thinks this might be a bad idea or cause problems if they can point out why.

xaur commented 6 years ago

One application of commitments was noted in floating fees discussion:

in order to support lightweight wallets, they too would need the ability to trustlessly obtain the necessary information for the current fee rate, which implies commitments

lealife commented 5 years ago

What would be stored in CommitmentRoot ? can you give more examples? and how will it secure SPV?

I can understand this:

If the CommitmentRoot store the block filter data hash, such as CommitmentRoot=hash(filter data), the spv client (wallet) will easily check the validity of the filters without having to download the block.

But if CommitmentRoot is the Merkle root of many commitments, how spv client validate the filter data? It should have a Partial Merkle branch for validating. So will it add a new msg to get CommitmentRoot Partial Merkle branch?

jrick commented 5 years ago

@lealife any commitment in the merkle tree can be validated, provided all intermediary hashes are also available.

davecgh commented 5 years ago

A formal proposal for this has now been created. All further discussion should take place there.

decred / dcrd