To get an idea of what is going on in there, are you listing the Merkle leaf hashes from top to bottom and left to right, or are you putting them in another order?
For the merkle proof in the example, the json-ified inputs are:
{
"root": "227c4fdcd6c57bf13f6af315dfeebfab6976e46276f11cc6160bbd0fb5ee22ec",
"siblings": [
"8bf7fe31f973206a1084adc625aceba47a07a406bb7af0a4856be80369879f3f",
"d05ae323ade50eb5b3e2ecfa09a9529bf693fb1a955b1a157f7b71c2cf8d629b",
"08632de6f4ccaccfb2a3ffbf0e2c00ab21e9c09a5864dc052a5578db200edac5",
"e3fe0f607bf194529d798a3c7409a6d0cb5efc19dce375b3c90611bc79f3247d",
"215228fd2afa2869f579093df1525b0e440f43f7145aa988d03438a78e9b72bf",
"f81ce02ef679e2e29d542d3cdee78fd4d556b78ae03421909651bb6be77e7da9",
"a1a08c07ccce1c6a26bc6f3338543e15c8803c5c9f909c459f3127b7b72da0bf",
"dfe8433c4dc9407812272638647640d138b1cc036d38cdb6adc8a1e5efc03f0d",
"17b14e63a9b0eeb7f40552b99ab3ec349dbfe80ed1497c47c1da17c2fc529054",
"ab8c794ff3f0e8c2477f7be9e9660e61218d5ba7be8d6ac8e4ce0568e64b28d8",
"e480b84964547ef3e9342a9f915ec7144d6bec674030b521d20049066474089b",
"a2944984637a8639a2805bd5efb7f0151895f5be68e6f733cf102b332c1aebe6",
"345b091a43a4e56c86ff2034f80279c45e6c3417741c446103b4c29b8cd489e6",
"d59e50b06c21c7a201a1c469e76a21e7cdc0def5be06d49d0ee43ec964176938",
"b58d900f5e182e3c50ef74969ea16c7726c549757cc23523c369587da7293784",
"d49a7502ffcfb0340b1d7885688500ca308161a7f96b62df9d083b71fcc8f2bb",
"8fe6b1689256c0d385f42f5bbe2027a22c1996e110ba97c171d3e5948de92beb",
"8d0d63c39ebade8509e0ae3c9c3876fb5fa112be18f905ecacfecb92057603ab",
"95eec8b2e541cad4e91de38385f2e046619f54496c2382cb6cacd5b98c26f5a4",
"f893e908917775b62bff23294dbbe3a1cd8e6cc1c35b4801887b646a6f81f17f",
"cddba7b592e3133393c16194fac7431abf2f5485ed711db282183c819e08ebaa",
"8a8d7fe3af8caa085a7639a832001457dfb9128a8061142ad0335629ff23ff9c",
"feb3c337d7a51a6fbf00b9e34c52e1c9195c969bd4e7a0bfd51d5c5bed9c1167",
"e71f0aa83cc32edfbefa9f4d3e0174ca85182eec9f3a09f6a6c0df6377a510d7",
"31206fa80a50bb6abe29085058f16212212a60eec8f049fecb92d8c8e0a84bc0",
"21352bfecbeddde993839f614c3dac0a3ee37543f9b412b16199dc158e23b544",
"619e312724bb6d7c3153ed9de791d764a366b389af13c58bf8a8d90481a46765",
"7cdd2986268250628d0c10e385c58c6191e6fbe05191bcc04f133f2cea72c1c4",
"848930bd7ba8cac54661072113fb278869e07bb8587f91392933374d017bcbe1",
"8869ff2c22b28cc10510d9853292803328be4fb0e80495e8bb8d271f5b889636"
],
"index": 999,
"value": "1337133713371337133713371337133713371337133713371337133713371337"
}
You can see that there are 30 siblings in the merkle proof, so the merkle tree has a height of 30 (i.e the tree has a total of 2^30=1073741824 leaves).
Since the tree is of height 30, we first need to decompose the index into its 30 bits:
//tb is a trace builder that emits the code we need
const numBits = 30;
for(let i=numBits-1;i>=1;i--){
tb.OP_DUP();
tb.constant(1< tb.OP_LESSTHAN(); // range check the index to sniff the highest bit
tb.OP_IF();
tb.OP_0();// if the index is less than 2^i, then the i-th bit is 0
tb.OP_TOALTSTACK(); // push the i-th bit of the index to the alt stack
tb.OP_ELSE();
tb.constant(1< tb.OP_SUB(); // subtract 2^i from the index
tb.OP_1(); // if the index is greater or equal to 2^i, then the i-th bit is 1
tb.OP_TOALTSTACK(); // push the i-th bit of the index to the alt stack
tb.OP_ENDIF();
}
tb.OP_TOALTSTACK(); // after the loop, the index is only 1 bit long, so we push it to the alt stack (least significant bit)
Now that we have the bits in the alt stack ordered in increasing significance (i.e, least significant bit is at the top of the alt stack), we can begin to check the merkle proof.
Currently, our primary stack looks like the following:
<0x227c4fdcd6c57bf13f6af315dfeebfab6976e46276f11cc6160bbd0fb5ee22ec> #root,
<0x8869ff2c22b28cc10510d9853292803328be4fb0e80495e8bb8d271f5b889636> #sibling_1,
<0x848930bd7ba8cac54661072113fb278869e07bb8587f91392933374d017bcbe1> #sibling_2,
<0x7cdd2986268250628d0c10e385c58c6191e6fbe05191bcc04f133f2cea72c1c4> #sibling_3,
<0x619e312724bb6d7c3153ed9de791d764a366b389af13c58bf8a8d90481a46765> #sibling_4,
<0x21352bfecbeddde993839f614c3dac0a3ee37543f9b412b16199dc158e23b544> #sibling_5,
<0x31206fa80a50bb6abe29085058f16212212a60eec8f049fecb92d8c8e0a84bc0> #sibling_6,
<0xe71f0aa83cc32edfbefa9f4d3e0174ca85182eec9f3a09f6a6c0df6377a510d7> #sibling_7,
<0xfeb3c337d7a51a6fbf00b9e34c52e1c9195c969bd4e7a0bfd51d5c5bed9c1167> #sibling_8,
<0x8a8d7fe3af8caa085a7639a832001457dfb9128a8061142ad0335629ff23ff9c> #sibling_9,
<0xcddba7b592e3133393c16194fac7431abf2f5485ed711db282183c819e08ebaa> #sibling_10,
<0xf893e908917775b62bff23294dbbe3a1cd8e6cc1c35b4801887b646a6f81f17f> #sibling_11,
<0x95eec8b2e541cad4e91de38385f2e046619f54496c2382cb6cacd5b98c26f5a4> #sibling_12,
<0x8d0d63c39ebade8509e0ae3c9c3876fb5fa112be18f905ecacfecb92057603ab> #sibling_13,
<0x8fe6b1689256c0d385f42f5bbe2027a22c1996e110ba97c171d3e5948de92beb> #sibling_14,
<0xd49a7502ffcfb0340b1d7885688500ca308161a7f96b62df9d083b71fcc8f2bb> #sibling_15,
<0xb58d900f5e182e3c50ef74969ea16c7726c549757cc23523c369587da7293784> #sibling_16,
<0xd59e50b06c21c7a201a1c469e76a21e7cdc0def5be06d49d0ee43ec964176938> #sibling_17,
<0x345b091a43a4e56c86ff2034f80279c45e6c3417741c446103b4c29b8cd489e6> #sibling_18,
<0xa2944984637a8639a2805bd5efb7f0151895f5be68e6f733cf102b332c1aebe6> #sibling_19,
<0xe480b84964547ef3e9342a9f915ec7144d6bec674030b521d20049066474089b> #sibling_20,
<0xab8c794ff3f0e8c2477f7be9e9660e61218d5ba7be8d6ac8e4ce0568e64b28d8> #sibling_21,
<0x17b14e63a9b0eeb7f40552b99ab3ec349dbfe80ed1497c47c1da17c2fc529054> #sibling_22,
<0xdfe8433c4dc9407812272638647640d138b1cc036d38cdb6adc8a1e5efc03f0d> #sibling_23,
<0xa1a08c07ccce1c6a26bc6f3338543e15c8803c5c9f909c459f3127b7b72da0bf> #sibling_24,
<0xf81ce02ef679e2e29d542d3cdee78fd4d556b78ae03421909651bb6be77e7da9> #sibling_25,
<0x215228fd2afa2869f579093df1525b0e440f43f7145aa988d03438a78e9b72bf> #sibling_26,
<0xe3fe0f607bf194529d798a3c7409a6d0cb5efc19dce375b3c90611bc79f3247d> #sibling_27,
<0x08632de6f4ccaccfb2a3ffbf0e2c00ab21e9c09a5864dc052a5578db200edac5> #sibling_28,
<0xd05ae323ade50eb5b3e2ecfa09a9529bf693fb1a955b1a157f7b71c2cf8d629b> #sibling_29,
<0x8bf7fe31f973206a1084adc625aceba47a07a406bb7af0a4856be80369879f3f> #sibling_30,
<0x1337133713371337133713371337133713371337133713371337133713371337> #value
When we verify a merkle proof, we start from the bottom of the tree where our value is, and hash up the tree to the root, and finish by comparing our computed root with the attested root at the bottom of the stack.
for(let i=0;i<30;i++){
tb.OP_FROMALTSTACK(); // pop the i-th least significant bit from the alt stack
tb.OP_NOT(); // invert the bit since our current merkle path is at the top of the stack.
// if the i-th least significant bit of the index is 1, then the merkle path at the i-th level is a right child, so running OP_CAT would push cat(,) to the stack
tb.OP_IF();
tb.OP_SWAP(); // if the i-th least significant bit of the index is a zero, then we need the current merkle path hash on the left, so our OP_CAT'd payload is cat(, )
tb.OP_ENDIF();
tb.OP_CAT(); // cat(,)
tb.OP_SHA256(); // sha256(cat(,))
}
tb.OP_EQUALVERIFY(); // check to make sure the computed root equals the attested root at the bottom of the stack, in this case 227c4fdcd6c57bf13f6af315dfeebfab6976e46276f11cc6160bbd0fb5ee22ec
Hope that helps!
