Namaran

Code daily. Without assist.

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。

  1. 葉の値と、各段で隣にある節の値の列を使って、その葉が根の値に含まれていることを確かめる手順を Merkle証明(Merkle proof)と呼びます。証明に添える値の数は木の段数だけで済みます。左右の情報を隣の値と一緒に送る実装もあり、その場合は index の偶奇ではなく、その印で並べる順を決めます。