sigstore merkle tree inclusion bash

entry.json

{
  "24296fb24b8ad77a4a1a059e1a6c382d91a2d8a8cebb8e68002c926676b676f7250fc37dd32e9fd3": {
    "body": "eyJhcGlWZXJzaW9uIjoiMC4wLjEiLCJraW5kIjoiaGFzaGVkcmVrb3JkIiwic3BlYyI6eyJkYXRhIjp7Imhhc2giOnsiYWxnb3JpdGhtIjoic2hhMjU2IiwidmFsdWUiOiJkOGQzMjEzYzcxOGE0YzBhZWNhMDI1YTNhOWMzZTA3Y2E3NjgwNmRmYmE4N2ZhNTZhMzhhN2U0YTljZjJjYzc3In19LCJzaWduYXR1cmUiOnsiY29udGVudCI6ImQ1RGpBUVBJaUkvdFFsaVE3TmRNb21GSWRFMGhFUmtLWEFhdFlIaVRiLzcrVlA5N1lnbXdncUlFRnI2bFdPTEJzMzZrdmt1NEdHL0hkSlV1em9iNG1ZMDRPenZHVjV3OTlmOVJDQW5vQ0d5aWJNUlk0aDdGQ1VRRXhMMjB4b1duQzhkb0kvNEFGZnlnTnBFbUZEQlpsaCtWYVAzWFFDdkh4WEo2WHZJeVFGVGtNbDFBeSs1TUhQTDVYR2pLblV6a2lmUU5rc0VQZmh5VkpxT092Qm54WHROSHJjcDhQMmFHckR6SnhtN0NZMk9ndzZPZy91M3R0THRLNTN6eDJuSDN5Z2ZTTXFLQVl4djNEMk5NNDRId1FHckVWbHM2UCtuSGk4RjFJODRHWFJjdGd0ZXN3ajU1Z0drRXBPWHZUemgrRmxjaXhYS3d2T3dDamNZNVBIa01IY3RXTEdqZ0h0cURRR3gvU0h0VllqK0RZTUdSMWUzUFFPT2FwMWs5WURyM3podDJUc0ZHYkovQ1hoRGZoR3hUTGZ5U0lwSnNrTGFCOHNXWWpNUUxZRTZtWERTeTBPalYrTndIL29lSTBjeENCL0lhRTF3QUozSE1OSWxGaUpNalZHME93d082NnBUV2E0TTJlRjZVcWdVQ0wvTXV1RmQxNk9IT1BoRk9COXNzTnVHVm1OWE5xQk1nOG5vUjd3ek9TTlFmeXNDaWtSakl1OWY0TW5LcktzNWRyL1pUKzhaaUg0Q1ZrSVdiZHc3N0xnbElPL01VVyt2REtWclBKRCt5VjBPZXVsT0svRUZtdllITEZPS21GaTMvd2FNaWxjVU9LdllqQk5TbFlGeDZleXgxSmp5RlpOOGl0ODhCWTlGcS9idUNoRzhTd3lNVGVnUkFQYWlabkw4PSIsInB1YmxpY0tleSI6eyJjb250ZW50IjoiTFMwdExTMUNSVWRKVGlCUVZVSk1TVU1nUzBWWkxTMHRMUzBLVFVsSlEwbHFRVTVDWjJ0eGFHdHBSemwzTUVKQlVVVkdRVUZQUTBGbk9FRk5TVWxEUTJkTFEwRm5SVUZ1YmpCSmFtWnVSV00xZEZOUlZVbENUVlUxUmdwclRFcE1TRWRvVjBWR01VMDVRbGxrVEVkaFVFNUNZa2hhYlhGRGNEWlhTVlZzYzBKRlIyOUVVemRWU0hkYVVtc3liRzVvVkdSb2RWSnlhMjV4YkhKakNsWkRaRFF6TmtWa1dqZ3ZhRmd4YzBodlJHUjFlREJ2Tm14VVRteElSSE42ZDJaS05tazBRbXh2WkVSbmFERlRMM1pSTldsVVRtOUJUSGxaTWxoSFN6Z0tVQzlTTW01b1ZuZFNOMmR4Tnl0SFJXb3lSMk0wT0doNlpXVkxPRGRFU1V0bE0zRnRPVzlaUzI0MmFXZFlVMWxqUldSRWRqY3JWRFJ3WWl0SWNHMXJlUXBwV205V1NYRldTR3RNZVdWME5sWnNWVzh6VTNNeFJIVXZSWE55VldnMWNEZHNZbk5YUW1WMFEyczBaemhzV0haTVpFRnVlRkJXVTB0dVJ6bHlSa3hIQ201bWVsTk1OM3BUUzBKeWIzVm9RV2h5TXpkb2JtcHFTbXQ2VmpCRFYxcHJSemRuYlROVU5XMXljbXRwTTNrNVducE5Wa1F5VEVGaFUyTlFWbE42T0dZS1VXWTNVSE5QTkVoWmFHbE9kWGxPU2pjd2NHSkRjV0ZNWTBzdllYY3ZRbGh3VUV4Uk5sUXliQzlEVUZaSEwyeEtVVXhQU0ZJNUswNDRjVlpGUWpSUVRncEhialo2Y0d4b2JWaFZhRmd6TmsxM1QyZDVlalJZUlZOR2RYaDFMMGhrUTJSa1RFNXFTbmw0VG10VU9IRTROalJQY25aTGVIWmpMMHBqZVhsYVYwNTJDbmRHVjBGSk1VUlBiVFY1VEhwb2RrcElabWRzVkcxMk1IQTRkbE5IUjJoWWJESXpPVGgwVGpGYVN6aFhhM2xUYlhkaFExUTJVR2hXVUd3eWFsVXdOVmNLVDFkWlREUkNMMEpVVUV0eVMxWm9PR2hzYVhrd09XUTRTMDlSWlhSMk0yMW9NMU54YkZSSmFIVTVSbU55ZGxGMVpWaGlRa0pVVGtwa1NVTXZNV2d6UndwUGJqVnlRbTgyVTNWTmNtNXJjVVJwUTBsYU5XZHBOMnRwV1dkd2NFVm5XV1JzZEc5cE5sbFlUM1JUT0VoVldESnZURFZYUzJnMWVERlVTbTVTVm5RckNtTTNLMlU1TmpoWVMweEpVM3AyYVZkQ2NYaEtiblJyUTBGM1JVRkJVVDA5Q2kwdExTMHRSVTVFSUZCVlFreEpReUJMUlZrdExTMHRMUW89In19fX0=",
    "integratedTime": 1667854219,
    "logID": "c0d23d6ad406973f9559f3ba2d1ca01f84147d8ffc5b8445c224f98b9591801d",
    "logIndex": 6695740,
    "verification": {
      "inclusionProof": {
        "checkpoint": "rekor.sigstore.dev - 2605736670972794746\n2581483\nmG9g7nlpUgM4YDGjM8p9sH8RXACPvonhk+bLZHL0Z7w=\nTimestamp: 1667936729903606871\n\n— rekor.sigstore.dev wNI9ajBFAiB4/GMJ4Jjs61P2OnzDhCt+xoESn2BkeY98mbXiE9BROAIhAM+h7gpaEEQIJSR4WFrZT8PY5h/XO7CVagWyZT6f/GBD\n",
        "hashes": [
          "7cde307b3824eaf1a79bd0b3872832f7f245099f70d1d03f5f4f7f64b28885af",
          "90c4d97e66614fc0c06a1d0980d434a5bedce97db59ef67e9122be063daf7ef8",
          "bdd30d19025562c27c1cbf5dba7b733c695c0bed3966494d355fb66ac6e5c54a",
          "f89314365eafb33b765e8a636a10b8a4733f266d45e8f6216dc9d984c5487fc8",
          "4a93a121703cb5723db1731f6c40f7668c3f8912147a610b478aaa5810e44298",
          "c902701afcdfafa1fb5cf514ffea874ba5803c7b1ba694d762ea01ae570f4406",
          "48afcdbc242d635e3650e5664699fedd8da608976a1208f91b185f22730e9722",
          "e6e7e7de33fd4beb5daadb89949459906fa6dffe6e6f1567242ba95d1bee76ee",
          "cb6e694cfa99218806036c2606c9c367f6028104473b6dde98d20911aa06eaf5",
          "97efd8a96d5af623aa525c87c060d786130b84e1d534c8fe13e374aeb470cd8f",
          "8225affdf7af0f26016a3eabcc53097ec75e9e9550767135c31cc0f54768c439",
          "572effa7879b004c6642891104f1d8ae523d79fab8a58b758046f99cd01991b2",
          "33c8c79ced3a9e1fab953ee67b91a46c7804f52cbf8d633d46d74f0b1199a832",
          "762071437f80306986f3dd7e37006dbbd306a48ebada65ee46e928d86353b985",
          "32f63c29b6bdb9fc6e6dc35386293bbb26558bae764051526dcc67c2f2afc86f",
          "981495a909d4b3524a5672cb5664f50215ff4815eaca0a5b179565766a5c5d6b",
          "e4f4f0e81bf05b7fde9a9358faeaf05716146599ea7e024e276ecf844cf86ef4",
          "1224bc9ed72f1a7075c5c19983d09fddf4e4575c01709355b5258a218559a805",
          "331d4b131eeccec3ddeb608690be8733e35690ecbd630653c2e909115807ec2c",
          "2747468d0ed5e5b1138bba7b7968367a9842437d9004b3166391f115cb867d1e"
        ],
        "logIndex": 2532309,
        "rootHash": "986f60ee79695203386031a333ca7db07f115c008fbe89e193e6cb6472f467bc",
        "treeSize": 2581483
      },
      "signedEntryTimestamp": "MEUCIQDjI1vaBTSQ7J69ynje2MULJdqh5UC5XGbfTtEc2Vra7gIgdiKU8hpBt70bpH/q6zWDbrow7QFtFykQLY6jUmyBzpU="
    }
  }
}

verify.sh

#!/usr/bin/env bash

set -euo pipefail

# https://datatracker.ietf.org/doc/rfc9162/#:~:text=2.1.3.2.%20%20Verifying%20an%20Inclusion%20Proof

entry=$(cat entry.json)
mapfile -t hashes < <(jq -rc '.[].verification.inclusionProof.hashes | .[]' <<< "$entry")
rootHash=$(jq -r '.[].verification.inclusionProof.rootHash' <<< "$entry")
startHash=$(sha256sum <(cat <(printf '\x00') <(jq -r '.[].body' <<< "$entry" | base64 -d)) | cut -d ' ' -f 1)
logIndex=$(jq -r '.[].verification.inclusionProof.logIndex' <<< "$entry")
treeSize=$(jq -r '.[].verification.inclusionProof.treeSize' <<< "$entry")

if [[ $logIndex -ge $treeSize ]]; then
  echo "verification failed! log index larger than tree size"
  exit 1
fi

echo -e "0x00 || leaf\nstart: ${startHash}\n\n"
echo -e "want: ${rootHash}\n\n"

r="${startHash}"
fn="${logIndex}"
sn=$(( treeSize - 1 ))

for i in "${!hashes[@]}"
do
  if [[ $sn -eq 0 ]]; then
    echo "verification failed! tree is incomplete"
    exit 1
  fi

  lsb=$(( fn & 1 ))

  if [[ ($lsb -eq 1) || ($fn -eq $sn) ]]; then
    echo "0x01 || ${hashes[i]} || ${r}"
    r=$(sha256sum <(cat <(printf '\x01') <(xxd -r -p <<< "${hashes[i]}") <(xxd -r -p <<< "${r}")) | cut -d ' ' -f 1)
    while [[ ($lsb -eq 0) || $fn -eq 0 ]]; do
      fn=$(( fn >> 1 ))
      sn=$(( sn >> 1))
      lsb=$(( fn & 1 ))
    done
  else
    echo "0x01 || ${r} || ${hashes[i]}"
    r=$(sha256sum <(cat <(printf '\x01') <(xxd -r -p <<< "${r}") <(xxd -r -p <<< "${hashes[i]}")) | cut -d ' ' -f 1)
  fi
  fn=$(( fn >> 1 ))
  sn=$(( sn >> 1))
  echo -e "${r}\n\n"
done

if [[ "${r}" == "${rootHash}" ]]; then
  echo "verification successful! got: ${r} want: ${rootHash}"
  exit 0
else
  echo "verification failed! got: ${r} want: ${rootHash}"
  exit 1
fi