2026-10-28
merkle_update.c
#include <stdio.h>
static unsigned combine(unsigned left, unsigned right) {
return left * 3 + right;
}
int main(void) {
unsigned tree[8] = {0, 0, 0, 0, 1, 2, 3, 4};
for (int i = 3; i >= 1; i--) {
tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
}
tree[6] = 5;
for (int i = 6 / 2; i >= 1; i /= 2) {
tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
printf("%d:%u\n", i, tree[i]);
}
}
これは何を出力するでしょうか?
Answer
3:19 と 1:34 の2行です。
配列 tree は、添字1を根とし、添字 i の節の子を 2 * i と 2 * i + 1 に置いた木です。葉は添字4〜7にあり、親の値は2つの子の値を combine でまとめて作ります。子の値を組み合わせて親の値を作るこの形の木を Merkle木と呼びます1。最初のループは親を3、2、1の順に計算するので、tree[3] は 3 * 3 + 4 で13、tree[2] は 1 * 3 + 2 で5、根の tree[1] は 5 * 3 + 13 で28になります。
葉の tree[6] を5に変えたあと、2つ目のループは i を 6 / 2、つまり3から始め、i /= 2 で親へ上がります。整数どうしの除算は小数部を切り捨てるので、3の次は1、1の次は0で、ループはそこで終わります。通るのは書き換えた葉から根までの道にある節3と節1だけです。tree[3] は 5 * 3 + 4 で19になり、tree[1] は変わっていない tree[2] の5を使って 5 * 3 + 19 で34になります。
i /= 2 を1ずつ減らす操作と読むと節2も表示されると答えてしまい、3を2で割った1.5を四捨五入すると節2から計算し直すと読み違えます。節2の下の葉は変わっていないので、計算し直さなくても値は5のままです。
- Merkle木(マークル木、Merkle tree)は Ralph Merkle の名から取った呼び名で、ハッシュ木とも呼びます。実際の Merkle木では
combineの代わりに暗号学的ハッシュ関数を使い、根の値を比べるだけで大きなデータ全体が一致するかを確かめます。