#!/bin/sh
# merkle-walk — POSIX RFC 6962 audit-path verifier.
# Usage: merkle-walk merkle.json sth.json
# Exits 0 iff inclusion proof closes to sth.root.
#
# RFC 6962 domain separation:
#   leaf hash:  sha256(0x00 || envelope_canonical_bytes)
#   node hash:  sha256(0x01 || left || right)
#
# verify.sh delegates step 4 to this helper to keep the verifier
# portable. The combinatorial walk mirrors shared-deps' verifyInclusion
# (RFC 6962 §2.1.1).

set -u

[ "$#" -eq 2 ] || { echo "usage: merkle-walk merkle.json sth.json" >&2; exit 2; }
merkle="$1"
sth="$2"

# Platform shim — sha256 hex of stdin → stdout (single line, no path).
if command -v sha256sum >/dev/null 2>&1; then
  sha256_bin() { sha256sum | cut -d' ' -f1; }
elif command -v shasum >/dev/null 2>&1; then
  sha256_bin() { shasum -a 256 | cut -d' ' -f1; }
else
  echo "FAIL: neither sha256sum nor shasum available" >&2
  exit 99
fi

leaf_index=$(jq -r '.leaf_index' "$merkle")
leaf_hash=$(jq -r '.leaf_hash' "$merkle")
expected_root=$(jq -r '.root' "$sth")
tree_size=$(jq -r '.tree_size' "$sth")
path_len=$(jq -r '.audit_path | length' "$merkle")

fn=$leaf_index
sn=$((tree_size - 1))
current_hex=$leaf_hash

# Algorithm mirrors shared-deps verifyInclusion (RFC 6962 §2.1.1).
# For each audit-path element:
#   - if fn is odd OR fn == sn: sibling on left, current = node(sib, cur)
#       AND promote-up: while fn is even AND fn != 0, shift both
#   - else: sibling on right, current = node(cur, sib)
#   - shift fn, sn down one level
# Final inner-loop placement is critical — the promote-up runs ONLY
# after the sibling-on-left case, before the unconditional shift.

i=0
while [ "$i" -lt "$path_len" ]; do
  sibling_hex=$(jq -r ".audit_path[$i]" "$merkle")

  if [ "$((fn % 2))" -eq 1 ] || [ "$fn" -eq "$sn" ]; then
    left_hex=$sibling_hex
    right_hex=$current_hex
    current_hex=$( {
      printf '%b' '\001'
      printf '%s' "$left_hex" | xxd -r -p
      printf '%s' "$right_hex" | xxd -r -p
    } | sha256_bin )
    while [ "$((fn % 2))" -eq 0 ] && [ "$fn" -ne 0 ]; do
      fn=$((fn / 2))
      sn=$((sn / 2))
    done
  else
    left_hex=$current_hex
    right_hex=$sibling_hex
    current_hex=$( {
      printf '%b' '\001'
      printf '%s' "$left_hex" | xxd -r -p
      printf '%s' "$right_hex" | xxd -r -p
    } | sha256_bin )
  fi

  fn=$((fn / 2))
  sn=$((sn / 2))
  i=$((i + 1))
done

# After consuming the audit path, sn must be 0 (we climbed to root)
# AND current_hex must equal expected_root. shared-deps requires both.
if [ "$sn" -eq 0 ] && [ "$current_hex" = "$expected_root" ]; then
  exit 0
else
  exit 1
fi
