Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Validate the transaction merkle root and transaction uniqueness #1385

Closed
4 tasks
teor2345 opened this issue Nov 25, 2020 · 1 comment · Fixed by #1386
Closed
4 tasks

Validate the transaction merkle root and transaction uniqueness #1385

teor2345 opened this issue Nov 25, 2020 · 1 comment · Fixed by #1386
Assignees
@hdevalence
Labels
A-rust Area: Updates to Rust code C-bug Category: This is a bug
Milestone
First Alpha Release

Comments

@teor2345
Copy link
Contributor

teor2345 commented Nov 25, 2020 •
edited
Loading

Zebra should validate the transaction merkle root during both checkpoint and block validation.

The chain of block header hashes ensures that the block headers are correct for each checkpointed block.
But we also need need to check the transaction merkle root before adding a block to the queue.

The queue rejects blocks with identical block header hashes, so we need to check for invalid transaction data before queuing the block. Otherwise, we could add an invalid block to the queue, and then reject valid blocks with identical hashes.

Due to a mistake in the bitcoin merkle tree design, it's easy to create identical merkle roots by duplicating trailing transactions.

TODO:

Before adding a block to the checkpoint queue:

  • check the transaction merkle root matches the transactions in the block
  • check that each transaction hash is unique

In the block verifier:

  • check the transaction merkle root matches the transactions in the block
  • check that each transaction hash is unique

Related issues:

Full Disclosure - CVE-2012-2459 - block merkle calculation exploit: https://bitcointalk.org/?topic=102395
@teor2345 teor2345 added C-bug Category: This is a bug A-rust Area: Updates to Rust code S-needs-triage Status: A bug report needs triage labels Nov 25, 2020
@teor2345 teor2345 added this to the First Alpha Release milestone Nov 25, 2020
hdevalence added a commit that referenced this issue Nov 25, 2020
@hdevalence
consensus: check Merkle roots
7f8e87a 
As a side effect of computing Merkle roots, we build a list of
transaction hashes.  Instead of discarding these, add them to
PreparedBlock and FinalizedBlock so that they can be reused rather than
recomputed.

This commit adds Merkle root validation to:

1. the block verifier;
2. the checkpoint verifier.

In the first case, Bitcoin Merkle tree malleability has no effect,
because only a single Merkle tree in each malleablity set is valid (the
others have duplicate transactions).

In the second case, we need to check that the Merkle tree does not contain any
duplicate transactions.

Closes #1385
hdevalence added a commit that referenced this issue Nov 25, 2020
@hdevalence
consensus: check Merkle roots
ec89ae9 
As a side effect of computing Merkle roots, we build a list of
transaction hashes.  Instead of discarding these, add them to
PreparedBlock and FinalizedBlock so that they can be reused rather than
recomputed.

This commit adds Merkle root validation to:

1. the block verifier;
2. the checkpoint verifier.

In the first case, Bitcoin Merkle tree malleability has no effect,
because only a single Merkle tree in each malleablity set is valid (the
others have duplicate transactions).

In the second case, we need to check that the Merkle tree does not contain any
duplicate transactions.

Closes #1385
Closes #906
@hdevalence hdevalence mentioned this issue Nov 25, 2020
Merged
2 tasks
hdevalence added a commit that referenced this issue Nov 25, 2020
@hdevalence
consensus: check Merkle roots
3d5d14e 
As a side effect of computing Merkle roots, we build a list of
transaction hashes.  Instead of discarding these, add them to
PreparedBlock and FinalizedBlock so that they can be reused rather than
recomputed.

This commit adds Merkle root validation to:

1. the block verifier;
2. the checkpoint verifier.

In the first case, Bitcoin Merkle tree malleability has no effect,
because only a single Merkle tree in each malleablity set is valid (the
others have duplicate transactions).

In the second case, we need to check that the Merkle tree does not contain any
duplicate transactions.

Closes #1385
Closes #906
hdevalence added a commit that referenced this issue Nov 25, 2020
@hdevalence
consensus: check Merkle roots
3e5c37e 
As a side effect of computing Merkle roots, we build a list of
transaction hashes.  Instead of discarding these, add them to
PreparedBlock and FinalizedBlock so that they can be reused rather than
recomputed.

This commit adds Merkle root validation to:

1. the block verifier;
2. the checkpoint verifier.

In the first case, Bitcoin Merkle tree malleability has no effect,
because only a single Merkle tree in each malleablity set is valid (the
others have duplicate transactions).

In the second case, we need to check that the Merkle tree does not contain any
duplicate transactions.

Closes #1385
Closes #906
@mpguerra mpguerra removed the S-needs-triage Status: A bug report needs triage label Nov 26, 2020
@mpguerra
Copy link
Contributor

assigning to @hdevalence as he is working on this in #1386 already

hdevalence added a commit that referenced this issue Nov 30, 2020
@hdevalence
consensus: check Merkle roots
ae36058 
As a side effect of computing Merkle roots, we build a list of
transaction hashes.  Instead of discarding these, add them to
PreparedBlock and FinalizedBlock so that they can be reused rather than
recomputed.

This commit adds Merkle root validation to:

1. the block verifier;
2. the checkpoint verifier.

In the first case, Bitcoin Merkle tree malleability has no effect,
because only a single Merkle tree in each malleablity set is valid (the
others have duplicate transactions).

In the second case, we need to check that the Merkle tree does not contain any
duplicate transactions.

Closes #1385
Closes #906
teor2345 pushed a commit that referenced this issue Dec 1, 2020
@hdevalence @teor2345
consensus: check Merkle roots
7c08c0c 
As a side effect of computing Merkle roots, we build a list of
transaction hashes.  Instead of discarding these, add them to
PreparedBlock and FinalizedBlock so that they can be reused rather than
recomputed.

This commit adds Merkle root validation to:

1. the block verifier;
2. the checkpoint verifier.

In the first case, Bitcoin Merkle tree malleability has no effect,
because only a single Merkle tree in each malleablity set is valid (the
others have duplicate transactions).

In the second case, we need to check that the Merkle tree does not contain any
duplicate transactions.

Closes #1385
Closes #906
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@hdevalence hdevalence

Labels
A-rust Area: Updates to Rust code C-bug Category: This is a bug
Projects
None yet
Milestone
First Alpha Release
Development

Successfully merging a pull request may close this issue.

Implement Bitcoin Merkle trees ZcashFoundation/zebra
3 participants
@hdevalence @mpguerra @teor2345