The v12 stratum server uses pre-generated Merkle branches to efficiently generate work for each miner regardless of block size by copying and modifying the coinbase transaction only. The placement of the witness commitment in the block-final transaction and the inclusion of both the coinbase and block-final transaction in the witness Merkle tree makes supporting stratum with segwit-aware miners a bit trickier. So as to not delay the release of v13, it was decided to merge a preliminary version which didn't attempt this optimization but instead copies the entire block each time work is generated or received. For current low transaction rates this isn't an issue, but the performance issue does need to be addressed as soon as possible.
In v12 the stratum server needed only retain the path from the coinbase to the Merkle root of the block. With v13, it needs to retain the path from the coinbase to the root of the witness Merkle tree, which is used to regenerate the witness commitment. It then needs to use the path to both the coinbase and block-final transaction (both sides of the block Merkle tree) to generate the Merkle root. A trick helps us do this last part efficiently: drop the last hash in the proof for both the coinbase and block-final transactions, as in both cases that hash is represented by the other proof. Once the block-final transaction is known, calculate the root of the truncated proof, which is the hash of the right-hand side of the tree, which is the last hash for the coinbase proof. Then use the updated coinbase hash to calculate the updated block Merkle root.
Unfortunately the existing code for manipulating proofs of Satoshi-design Merkle trees is not up to task for this. When we generate a branch proof for the block-final transaction, that proof sometimes includes the hash of the block final transaction itself, unless the number of transactions is precisely a power of 2. This is because the hash gets duplicated, and the duplicate becomes part of the proof.
New Merkle proof code needs to be written which does not include duplicated hashes, but instead uses knowledge of the total number of objects and the position to do the duplication at verification time. This new Merkle tree code can then be used to implement efficient work generation and verification for segwit-aware stratum mining services.
maaku
commented
4 years ago
The v12 stratum server uses pre-generated Merkle branches to efficiently generate work for each miner regardless of block size by copying and modifying the coinbase transaction only. The placement of the witness commitment in the block-final transaction and the inclusion of both the coinbase and block-final transaction in the witness Merkle tree makes supporting stratum with segwit-aware miners a bit trickier. So as to not delay the release of v13, it was decided to merge a preliminary version which didn't attempt this optimization but instead copies the entire block each time work is generated or received. For current low transaction rates this isn't an issue, but the performance issue does need to be addressed as soon as possible.
In v12 the stratum server needed only retain the path from the coinbase to the Merkle root of the block. With v13, it needs to retain the path from the coinbase to the root of the witness Merkle tree, which is used to regenerate the witness commitment. It then needs to use the path to both the coinbase and block-final transaction (both sides of the block Merkle tree) to generate the Merkle root. A trick helps us do this last part efficiently: drop the last hash in the proof for both the coinbase and block-final transactions, as in both cases that hash is represented by the other proof. Once the block-final transaction is known, calculate the root of the truncated proof, which is the hash of the right-hand side of the tree, which is the last hash for the coinbase proof. Then use the updated coinbase hash to calculate the updated block Merkle root.
Unfortunately the existing code for manipulating proofs of Satoshi-design Merkle trees is not up to task for this. When we generate a branch proof for the block-final transaction, that proof sometimes includes the hash of the block final transaction itself, unless the number of transactions is precisely a power of 2. This is because the hash gets duplicated, and the duplicate becomes part of the proof.
New Merkle proof code needs to be written which does not include duplicated hashes, but instead uses knowledge of the total number of objects and the position to do the duplication at verification time. This new Merkle tree code can then be used to implement efficient work generation and verification for segwit-aware stratum mining services.