Share
Explore

Add Transaction Root to Block Header

Author:
@Daniel Cogan
Problem
Currently Compact blocks (Block Header + Transaction Hashes) are not verifiable without obtaining the full transactions and building the new merkle tree from those transactions. This is because the only connection transactions have with the block header is through the merkle root of the spend and nullifier trees. Many other coins such as , and have a merkle root of block transactions in the block header. This is used to make compact blocks non-malleable as well as allow for merkle proofs of transactions in a block for light clients.
Makes Gossiping Blocks by Hash and Compact Block Inefficient
A node can’t verify that transaction hashes sent with compact blocks belong with the block header without having the full transactions and rebuilding the note and nullifier merkle tree. This is because an adversary could send compact blocks with incorrect transaction hashes and there is no direct connection from the transaction hashes to the block hash. Nodes must assume that the transaction hashes in a compact block are malleable.
This is not much of a problem when receiving blocks that append to the main chain. The node requests the full block, adds it to the chain, adds the note to the note merkle tree and verifies new merkle note root hash against the block header. Inefficiencies arise outside of this happy path.
Consider the scenario where the node receives a block on a fork. It is expensive to recalculate the note merkle root for that block since it would involve removing notes from the note merkle tree then re-adding them up to that block. An adversary could spam blocks that have incorrect transaction and the only way for a node to tell the transactions are incorrect is to recalculate the note merkle tree. If the transaction are in fact correct, it would be nice to be able to no longer validate blocks with that hash. However, because another block with the same hash and different (possibly valid) transactions could exist, the node would have to download the full block and recompute the note merkle tree for every block it sees. This opens the node up to either
doing an expensive computation on every block hash it sees allowing for this DDoS attack
not computing every block and potentially missing valid blocks
If the block header contained a root hash of a new merkle tree of transaction hashes then the expensive computation would be replaced by a cheap one: checking that the transaction hashes form the merkle root in the block header. This also means that if any of the transactions in that block are invalid, or the notes in the block don’t match the note merkle tree hash, that block hash can permanently be marked as invalid and never be processed by the node again. This is even more helpful given the fact that the majority NewBlock messages received from peers are simply the block hash.

Makes it More Difficult to Implement Light Clients
In the current implementation a node cannot succinctly prove that a transaction is included in a specific block. The node would have to calculate the note merkle tree from the genesis block to the current block to verify inclusion. With a transaction merkle tree root the node could easily verify inclusion of a transaction in a block. The note merkle tree still needs to be computed to validate the block itself but that is somewhat of a separate problem.
Light clients for privacy chains need to operate a little differently. Requesting specific transactions by hash as a light client could de-anonymize the light client to other peers. For this reason the best way to maintain full anonymity it to request every transaction. The sapling implementation also makes it difficult to spend a note without creating a whole merkle tree of all notes in the chain. This is another reason for a node/light client to process every transaction. This makes filtering by transaction ID less appealing for our light clients. Here are some ZCash Light Client Proposals that it would be good to study more in-depth: , ,
How Do Other Coins Do It?
ZCash: Merkle Roots
Described more in , ZCash actually has two merkle roots on the block header relating to transactions: hashMerkleRoot and hashAuthDataRoot . The former is a merkle tree hash where the leaf nodes are all the Transaction ID of transactions in that block NOT including the witness data. The later is an almost identical tree but instead of Transaction IDs as leaves it contains the Transaction Auth (signature) data.
Transactions are separated from their auth data in ZCash because of the same issues solved by Bitcoin’s upgrade. Transaction signature data can be which would in turn modify the transaction ID. If other systems rely on that transaction ID, they may miss a transaction that they’re expecting because it was confirmed under a different ID. For this reason systems should rely on a transaction hash generated without the signature. Having two merkle trees gives the option to prove a certain transaction (regardless of which witness data it was confirmed with) is contained in a block.

Bitcoin: Merkle Roots
Bitcoin’s implementation is very similar to ZCash most likely because ZCash took much of its implementation from the Bitcoin code. Bitcoin has a Merkle root hash of transactions without the witness data. This is as merkle_root . Bitcoin also has signature data in a separate merkle tree aggregated into the witness_merkle_root. This is not stored on the block header but rather in the coinbase transaction of the block. Bitcoin core developer Pieter Wuille (a ) gives a good explanation as to . Essentially it would have been stored in the block header if not for the complications arising from adding a new field to the block header. The coinbase transaction was a much easier place to put it.

Ethereum: Merkle Roots
Ethereum as multiple per block Merkle trees as well. Instead of simple trees they are encoded as tries. Their transaction merkle root is encoded as a trie as well. Encoding transaction hashes as a trie seems like it would just make longer merkle proofs for our use case. Cannot see much benefit for this specific merkle tree.
Potential Solutions
Transaction Merkle Roots
The simplest solution is to include a new field in the block header (transaction_merkle_root) that represent the combined hash of all the transactions in that block. This is what Bitcoin, ZCash and Ethereuem do for their blocks. There are a few nuances to this approach:
Do we include witness/signature data in the transaction merkle tree? Separating transaction and witness data does not seem as relevant for our chain because all transactions are private. This means when nodes are listening for transaction confirmations they need to download and attempt to decrypt every transaction with their view key. If a node just requests specific transaction IDs then it would somewhat de-anonymize their transactions from other peers. Non-shielded ZCH transactions and BTC don’t have this limitation so their light clients can depend more on transaction ID. However, there could be implementations of privacy light clients that this is useful for.
How to build the merkle tree securely such that the root can only represent one set of transactions. Here are some potential attack vectors we want to defend against.
. This is an instance of a second pre-image attack and here’s .
ZCash until the tree is a power of 2 size.

Alternative Commitment Schemes
A Merkle Tree is not the only way of committing to a set of values. Some popular alternatives are Vector Commitments (, ) and Verkle Trees ().
Vector Commitments are a way to provide a proof of inclusion in constant time rather than the Merkle Tree log(n) time. However they do this at the cost of O(n^2) time to generate. This could be a potentially better than a Merkle Tree for us but given the number of transactions in a block will most likely not exceed 1000, it seems like overkill for our solution. Given that they are relatively new compared to Merkle Trees it doesn’t seem beneficial to experiment for such a small performance gain.
Verkle Trees are a combination of Merkle Trees and Vector Commitments. It is a Merkle Tree of n-arity where each node contains a vector commitment to the n elements underneath. Similarly this could be a good solution but comes at the cost of experimentation.
Proposed Solution
The origin of this change is attempting to solve the problem of not being able to mark gossiped blocks as invalid which can cause performance problems. The biggest open question seems to be whether we should separate out transaction data and witness data into separate merkle roots. Other coins do this so it warranted investigation. The alternative is to have both witness and transaction data under the same tree. After investigation I feel confident that other coins do not do this for security reasons but instead because of a combination of historical reasons and for light clients of non-shielded transactions. Light clients are not a pressing issue for us at the moment and are sufficiently complicated for private chains that it’s not clear whether or not separating these two trees out will help. Given this I propose we create a single merkle tree with leaves being the serialized transaction with witness data.
This comes with a few practical and short term advantages:
Getting the hash of the serialized transaction is much more performant in our current code. The unsignedHash which is still takes noticeably longer
The hash of serialized transaction is already what we use on gossiped compact blocks. If we use this to construct the merkle tree we will not have to modify the compact block to be able to reconstruct the merkle root from a compact block

Merkle Root Proposed Code
function transactionMerkleRoot(hashes: Buffer[]): Buffer {
if (hashes.length === 0) {
return blake3(TRANSACTION_ROOT_PERSONALIZATION)
}
// Get the number of nodes needed for a perfectly balanced tree
const perfectSize = hashes.length === 1 ? 2 : 2 ** Math.ceil(Math.log2(hashes.length))

Assert.isTrue(perfectSize >= hashes.length)
Assert.isGreaterThan(perfectSize, 1)
Assert.isEqual(perfectSize & (perfectSize - 1), 0)
let currentLevelHashes = hashes
while (currentLevelHashes.length < perfectSize) {
currentLevelHashes.push(NULL_NODE)
}

Assert.isEqual(perfectSize, currentLevelHashes.length)
let currentLevel = 0
while (currentLevelHashes.length > 1) {
const nextLevelHashes = []
for (let i = 0; i < currentLevelHashes.length; i += 2) {
// Add personalization so these hashes cannot be replayed to/from different contexts
// Also add in the level of the currentLevel to be resilient to second pre-image attacks
const combination = blake3(
Buffer.concat([
TRANSACTION_ROOT_PERSONALIZATION,
Buffer.from([currentLevel]),
currentLevelHashes[i],
currentLevelHashes[i + 1],
]),
)
nextLevelHashes.push(combination)
}

currentLevelHashes = nextLevelHashes
currentLevel++
}

return currentLevelHashes[0]
}
Open Questions
There seem to be a couple good reason to have a separation between transaction merkle tree and witness merkle tree. Mainly for light clients to look for transaction regardless of their witness data (maybe the witness data is malleable or it is a 1 of n signature scheme with multiple valid signatures). But not sure if this really applies to us if all transactions are shielded because light clients would be anonymized if they filtered for specific transactions
If we wanted to have a flexible commitment similar to
would it make sense to have this as a list of hashes as ZCash does or even move to merkle tree of hashes which seems more flexible
Look into Light Client proposals to see if any of them require some other block commitments. This should be a separate project
How long would creating this merkle tree take for ~1500 transactions. This is going to add to our processing blocks time
Doing some profiling for the above function with blake3 hash it looks like creating merkle tree from 1500 transaction hashes takes about 2.5ms on M1 MacBook. We would also need to hash the transactions themselves which seems like it would take about the same amount of time so a total of 5ms
Does ZCash store shielded transactions in either of their two trees
It does look like shielded spends are stored on the which is what is stored on the When the auth data merkle tree is created it seems like all of the transactions . Additionally the AuthDataCommitment is said to contain the which is the combination of zkproofs for sapling spends along with a binding signature.
Computing the merkle root for transaction hashes also seems like it is using the . They use the WTIX

Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.