對於包含“x”個未驗證交易的塊，執行多少 SHA256d 雜湊以獲得 hashmerkleroot？

這幾天我一直在努力理解這一點。

我知道 hashmerkleroot 是完全完美二叉樹的根節點。我也知道 sha256d 散列將是樹的非葉/父節點，事務的 sha256d 散列將是葉節點。

我也知道具有“x”葉的完全完美的二叉樹有 2x-1 個節點。

我要回答的問題是，如果要散列的事務數為“x”，則獲取 hashmerkleroot 所需的 SHA256d 散列數的公式是什麼？我上面的任何理解都不正確嗎？

如果葉子的數量正好是 2 的冪（即n = 2 k），那麼執行的雜湊數正好是n-1。這很容易看出：每個雜湊運算都需要兩個輸入，然後將它們簡化為一個。在n-1 次操作之後，這意味著n 個節點減少到1 個，並且那個節點是 Merkle 根。

當葉子的數量不是 2 的冪時，它有點複雜。每當 Merkle 樹的“層”有奇數個葉子時，仍然對最後一個執行散列操作，但它只需要一個輸入。因此，每次發生這種情況時，都意味著在n-1之上進行加法散列操作，否則是預期的。

這種情況多久發生一次？讓我們看看n=9..16葉子的級別大小：

• 9 → 5 → 3 → 2 → 1：11個雜湊（n - 1 + 3 個奇數級別）
• 10 → 5 → 3 → 2 → 1：11個雜湊（n - 1 + 2 個奇數級別）
• 11 → 6 → 3 → 2 → 1：12個散列（n - 1 + 2 個奇數級）
• 12 → 6 → 3 → 2 → 1：12個雜湊（n - 1 + 1 個奇數級別）
• 13 → 7 → 4 → 2 → 1 : 14 個雜湊（n - 1 + 2 個奇數級別）
• 14 → 7 → 4 → 2 → 1：14個雜湊（n - 1 + 1 個奇數級別）
• 15 → 8 → 4 → 2 → 1：15個雜湊（n - 1 + 1 個奇數級別）
• 16 → 8 → 4 → 2 → 1 : 15雜湊（n - 1 + 0奇數級）

奇數級的數量正好等於葉數與二的下一個冪之差的二進製表示中設置的1位的數量。例如，對於n=11葉子，2 的下一個冪是16，它們之間的差是5，用二進制寫為101 2，它有兩個1。因此，散列操作的數量是11-1 + 2 = 12 個散列。

在不知道葉子數量的結構的情況下，散列操作數的下限是n-1，上限是n-1+log 2 (n-1)。

引用自：https://bitcoin.stackexchange.com/questions/108454