2026-10-28
merkle_proof.c
#include <stdio.h>
static unsigned combine(unsigned left, unsigned right) {
return left * 3 + right;
}
static int verify(unsigned leaf, int index, const unsigned proof[], int depth, unsigned root) {
unsigned hash = leaf;
for (int level = 0; level < depth; level++) {
hash = combine(hash, proof[level]);
index /= 2;
}
return hash == root;
}
int main(void) {
const unsigned proof[] = {3, 5};
printf("%d\n", verify(4, 3, proof, 2, 28));
}
葉の値を左から 1、2、3、4 と並べ、隣り合う2つを combine(左, 右) でまとめて親を作る木があります。根の値は28です。verify は、左から index 番目(0始まり)の葉の値 leaf から根まで上がりながら、各段で隣にある節の値 proof[level] と組み合わせ、最後に根の値と一致するかを確かめるつもりの関数です。main は4番目の葉(index は3)を、隣の葉の値3と、1段上で隣にある節の値5で確かめます。本来は 1 と出力されるはずが、いまは 0 と出力されます。最初の葉を verify(1, 0, (const unsigned[]){2, 13}, 2, 28) で確かめると、いまでも1が返ります。
Answer
Wrong
for (int level = 0; level < depth; level++) {
hash = combine(hash, proof[level]);
index /= 2;
}
combine は left * 3 + right なので、左右を入れ替えると値が変わります。ところがこのループは、いま上がってきた値 hash をいつも左に置いています。4番目の葉は右の子なので、本当の親は combine(3, 4) の13ですが、ループは combine(4, 3) で15を作ります。次の段でも、添字が1の節は右の子なのに combine(15, 5) で50を作り、根の28と一致しないので0が返ります。
最初の葉は、どの段でも左の子です。hash を左に置く計算がたまたま正しいので、こちらは1が返ります。
Right
for (int level = 0; level < depth; level++) {
if (index % 2 == 0) {
hash = combine(hash, proof[level]);
} else {
hash = combine(proof[level], hash);
}
index /= 2;
}
その段で hash が左右どちらの子かは、index の偶奇で決まります。偶数なら左の子なので隣の値を右に、奇数なら右の子なので隣の値を左に置きます。index /= 2 で親の段の位置に移るので、次の段でも同じ判定が使えます。4番目の葉では、combine(3, 4) の13、combine(5, 13) の28と進み、根と一致します1。
- 葉の値と、各段で隣にある節の値の列を使って、その葉が根の値に含まれていることを確かめる手順を Merkle証明(Merkle proof)と呼びます。証明に添える値の数は木の段数だけで済みます。左右の情報を隣の値と一緒に送る実装もあり、その場合は
indexの偶奇ではなく、その印で並べる順を決めます。