By Islam BarakaThree committed groups contain four journals. You want to prove that the correction group belongs to a retained batch without sending the verifier the other two groups.
You can do it with one sibling hash. The first group in that same tree needs two siblings.
That difference is a consequence of the tree shape. Padding the third leaf with a duplicate would produce a different root and a different algorithm. We will implement one explicit construction, verify exact proof boundaries, and keep the assurance claim narrow: these bytes are included under this trusted root.
All Cedar data is synthetic. The worked batch comes from ledger CB-GENERAL, entity CB-A. The source adapter validates complete accepted journals and creates canonical whole-group bytes. The Merkle core accepts those bytes as opaque input; it does not repeat their accounting validation.
Define exactly what the leaf contains
The shared sequence has a funding group, a wrong-transfer group, and one correction group containing the inverse plus replacement. That correction is one leaf, preserving its atomic committed boundary.
The authored G framing commits the stream and scope, complete ordered commands and legs, journal sequences, recording clocks, retained adjustment evidence, correction links and group observer receipt. It uses explicit byte lengths and UTF-8 scalar strings. It is described in the source contract; it is not ordinary pretty-printed JSON.
The Merkle function does not parse G. Its strict interface checks lowercase even-length hex and resource limits, then hashes the resulting bytes. It can calculate valid mathematical inclusion for a byte string that is not a financial journal at all.
That is useful separation, provided the caller keeps it visible. The upstream Hash adapter must establish that each opaque value is the correct canonical G and that its scope and source coverage are genuine.
Use a tree rule that handles every size
We choose the construction in RFC 9162 section 2.1, with SHA-256 as the digest:
Empty tree: SHA256(empty bytes)
Single entry x: SHA256(00 || x)
Branch L, R: SHA256(01 || L || R)
Here 00 and 01 are single octets, and L and R are raw 32-byte digests, not their 64-character hex text. The different leaf and internal prefixes separate the two node roles.
For more than one entry, split at the largest power of two strictly less than the number of entries. Three splits into two plus one; five splits into four plus one; seven splits into four plus three. Recurse with the same rule inside each subtree.
The result is well defined without requiring a power-of-two batch size. We never duplicate the last leaf.
An empty tree has a root but no inclusion proof. A one-leaf tree has an empty sibling path. A single empty byte entry is another case: its hash is SHA256(00), which differs from the empty-tree root. Empty bytes are allowed by this mathematical interface for testing, but they are not a valid D30 G frame.
Calculate the shared three-group root
The independent framing dataset contains three byte strings of 408, 424 and 829 bytes. The last contains both correction journals.
Let A, B and C be their leaf hashes. Short labels below are display aids; the full exact values remain in the datasets and lab.
| Node | Exact rule | Digest prefix |
|---|---|---|
| A · funding | SHA256(00 | |
| B · wrong transfer | SHA256(00 | |
| C · correction group | SHA256(00 | |
| AB | SHA256(01 | |
| Root | SHA256(01 |
The exact root is:
34ad17bffd657e7227adb7083eb1be5d0a7f9bcd5ba6b404313dce2242393192
These values were authored independently before the production tree implementation. The calculation note records the separate iterative stack method and the shared literal vectors.
Open the full-size three-group tree.
Generate the shortest ordered path
An inclusion path contains the sibling digests needed to move from one leaf to the root, ordered from the leaf upward.
For zero-based leaf index 2, the correction leaf C is already the root's right child. The only sibling is AB:
path[0] = f7166ff638fdfea0e5b73405e6f4bf58b7d76a0c7199aa84a453d18eeb7d3cd6
root = SHA256(01 || path[0] || C)
For leaf index 0, first combine A with sibling B on the right. Then combine AB with sibling C on the right. For index 1, combine sibling A on the left of B, then C on the right.
The path does not carry trusted direction flags. The verifier derives each sibling's side from the exact leaf index and tree size. A malicious left/right flag therefore has no place in this wire format.
Open the full-size path comparison.
Bind the proof to an independent commitment
The build function returns a locally calculated root object and an optional proof:
built = build_merkle_commitment(request)
outcome = verify_merkle_inclusion(built["proof"], trusted_commitment)
const built = await buildMerkleCommitment(request);
const outcome = await verifyMerkleInclusion(built.proof, trustedCommitment);
The trusted commitment is a separate argument obtained from an independently retained authorized source. Passing the root you just calculated can test self-consistency, but it does not establish independent trust.
Verification binds the batch identifier, stream, ledger, entity, starting group index, exact tree size and root. A proof from a different declared interval or scope fails that metadata policy even if its hash arithmetic is otherwise valid.
Those labels beside opaque bytes are not themselves cryptographically mixed into the tree by this mathematical layer. Their semantic relationship to the G bytes must be checked by the source adapter. Within the canonical G frame, scope strings are committed as bytes.
The starting group index also does not invent a journal sequence. Group 3 can contain two journals. A final checkpoint over the full ledger prefix requires start index 1 and actual complete source coverage, not merely the word “prefix” in a caller label.
Validate before claiming inclusion
The verifier first validates exact object fields, scope identifiers, bounded canonical counter strings, entry hex, digest path values and expected path length. Unknown fields reject. Short or surplus paths reject; a proof cannot quietly ignore an extra sibling.
Then hash the selected entry with leaf prefix 00. Apply every sibling in its derived order using branch prefix 01, retaining the exact input and output hash for each step.
The outcome remains explicit:
| Outcome | What it establishes |
|---|---|
| MERKLE_INCLUSION_VERIFIED | Computed root and all declared metadata match the supplied trusted commitment |
| MERKLE_ROOT_MISMATCH | Well-formed inclusion arithmetic disagrees with the expected root |
| TRUSTED_COMMITMENT_MISMATCH | Declared batch/scope/start/size disagrees with verification policy |
| MISSING_TRUSTED_COMMITMENT | A local root can be calculated, but no independent expected root was supplied |
| INVALID_PROOF_LENGTH | The supplied path is too short or too long for this index and size |
| CRYPTO_UNAVAILABLE | Native SHA-256 could not execute; no positive result is fabricated |
A validly shaped changed sibling fails the root comparison. A changed leaf or wrong in-range index can do the same. Changing the tree size can alter both shape and metadata, so it is part of the proof's meaning.
The TypeScript implementation uses the native asynchronous digest documented by Node.js v22.22.0. Python uses hashlib SHA-256. The package supplies tree logic rather than a handwritten cryptographic primitive.
Replay the proof rather than watching a pass badge
Open the guided Merkle proof lab. It starts with the correction group's completed proof. Begin replay to inspect the exact bytes, leaf hash, sibling step, expected-root comparison and final assurance boundary.
Try the first group to see a two-sibling path, then a five- or seven-entry byte example. Switch to a modified sibling, changed leaf, wrong index, wrong tree size, scope mismatch, short path or missing trusted root.
The lab runs the actual compiled TypeScript core with native browser SHA-256. It shows exact digest strings and uses shortened labels only in its navigation graphic. Empty-tree and repeated-byte scenarios make the mathematical boundaries visible.
Keep the assurance layers separate
A valid inclusion proof says one byte string occupies a particular position under a particular retained root. It does not prove that all real-world transactions were recorded, that the ledger is current, that the bytes encode a valid journal, that a signer is authorized, or that no competing root exists.
Financial validation, complete source coverage, canonical encoding, independent root retention, signer policy and external anchor evidence each need their own checks. A known bad inclusion result stays a failure even if some separate assurance layer is unavailable.
Open the full-size assurance boundary.
The package's 143 complete expected cases and validation receipt, wire contract, claim ledger, usage and references make the result reproducible.
Continue with hash-chained journals, signed ledger checkpoints and end-to-end ledger integrity verification while keeping those different claims visible.
ReferencesPrimary sources and evidence notesExpand the source trail, evidence role, and limitations behind the engineering choices.
Expand the source trail, evidence role, and limitations behind the engineering choices.
- RFC 9162 — Certificate Transparency Version 2.0, December 2021, Experimental, sections 2.1.1 and 2.1.3, https://www.rfc-editor.org/rfc/rfc9162.html#section-2.1
- Accessed: 2026-10-25.
- Supports: selected empty/leaf/internal Merkle construction, largest-power-of-two split, shortest inclusion path, zero-based index/tree-size verification and distinct consistency-proof purpose.
- Limitations: certificate-transparency protocol context, not banking regulation or financial correctness; this authored G framing is not its CT wire format. No CT protocol conformance or consistency proof is claimed.
- Python 3.11 hashlib documentation, https://docs.python.org/3.11/library/hashlib.html
- Accessed: 2026-10-25; local Python 3.11.3 runtime.
- Supports: native SHA-256 byte input and lowercase hex digest interface.
- Limitations: hashing is not canonicalization, source authentication, signature verification or a proof of financial completeness.
- Node.js v22.22.0 Web Crypto API, https://nodejs.org/download/release/v22.22.0/docs/api/webcrypto.html
- Accessed: 2026-10-25; local Node v22.22.0.
- Supports: globalThis.crypto.subtle native asynchronous SHA-256 digest, used in the same TS core in Node and browser.
- Limitations: availability depends on runtime/secure context; the core reports indeterminate rather than substituting a custom hash when native crypto is unavailable.
Shared authored evidence: datasets/shared-integrity-vectors.json contains literal whole-group framing and roots produced independently before Stage6 core. datasets/merkle-cases.json contains 143 full independent expected outputs. These are synthetic authored calculations, not third-party observed financial records.
Full dependency-light reference implementations in both supported languages.
/** Native SHA-256 tree over opaque bytes. No framing or financial validation. */
type Obj=Record<string,any>;
const META=['batch_id','stream_id','ledger_id','entity_id','start_group_index']as const;
const BUILD=['schema_version',...META,'entries_hex','proof_leaf_index'];
const ROOT=['schema_version',...META,'tree_size','root_hex'];
const PROOF=['schema_version',...META,'tree_size','leaf_index','entry_hex','path'];
class MerkleError extends Error{}class CryptoUnavailable extends Error{}
function need(ok:unknown,code:string):asserts ok{if(!ok)throw new MerkleError(code)}
function exact(v:any,fields:readonly string[]):boolean{return v!==null&&typeof v==='object'&&!Array.isArray(v)&&Object.getPrototypeOf(v)===Object.prototype&&Object.keys(v).length===fields.length&&fields.every(k=>Object.hasOwn(v,k))}
function full(pattern:RegExp,v:any):boolean{return typeof v==='string'&&pattern.exec(v)?.[0]===v}
function count(v:any,low=0,high=4096):boolean{return full(/^(0|[1-9][0-9]{0,3})$/,v)&&Number(v)>=low&&Number(v)<=high}
function scope(v:Obj):boolean{return META.slice(0,-1).every(k=>full(/^[A-Za-z0-9][A-Za-z0-9._:-]{0,63}$/,v[k]))}
function entry(v:any):boolean{return typeof v==='string'&&v.length<=32768&&v.length%2===0&&full(/^[0-9a-f]*$/,v)}
function digest(v:any):boolean{return full(/^[0-9a-f]{64}$/,v)}
function bytes(hex:string):Uint8Array{const out=new Uint8Array(hex.length/2);for(let i=0;i<out.length;i++)out[i]=parseInt(hex.slice(i*2,i*2+2),16);return out}
function cat(prefix:number,...parts:Uint8Array[]):Uint8Array{const out=new Uint8Array(1+parts.reduce((n,p)=>n+p.length,0));out[0]=prefix;let offset=1;for(const p of parts){out.set(p,offset);offset+=p.length}return out}
async function sha(data:Uint8Array):Promise<string>{try{if(!globalThis.crypto?.subtle)throw Error('Native digest unavailable');const value=await globalThis.crypto.subtle.digest('SHA-256',new Uint8Array(data));return Array.from(new Uint8Array(value),b=>b.toString(16).padStart(2,'0')).join('')}catch{throw new CryptoUnavailable()}}
function split(n:number):number{let k=1;while(k*2<n)k*=2;return k}
function sides(n:number,index:number):string[]{if(n===1)return[];const k=split(n);return index<k?[...sides(k,index),'right']:[...sides(n-k,index-k),'left']}
function emptyBuild(status:string,code:string):Obj{return{status,code,commitment:null,proof:null,trace:[]}}
function emptyVerify(status:string,code:string):Obj{return{status,code,scope:null,proof:null,verification:null,trace:[]}}
function metadata(v:Obj):Obj{return Object.fromEntries(META.map(k=>[k,v[k]]))}
export async function buildMerkleCommitment(request:any):Promise<Obj>{
try{
need(exact(request,BUILD)&&request.schema_version==='d30-merkle-build-v1','INVALID_BUILD_SCHEMA');need(scope(request),'INVALID_SCOPE');need(count(request.start_group_index,1),'INVALID_GROUP_RANGE');
const entries=request.entries_hex;need(Array.isArray(entries)&&entries.length<=4096,'INVALID_ENTRIES');const n=entries.length;
need(n===0||Number(request.start_group_index)+n-1<=4096,'INVALID_GROUP_RANGE');need(entries.every(entry),'INVALID_ENTRY_HEX');
const index=request.proof_leaf_index;need(index===null||(count(index,0,4095)&&Number(index)<n),'INVALID_PROOF_INDEX');
const trace:Obj[]=[],cache=new Map<string,string>();
async function tree(start:number,size:number):Promise<string>{
let value:string,kind:string,left:string|null=null,right:string|null=null;
if(size===0){value=await sha(new Uint8Array());kind='empty'}
else if(size===1){value=await sha(cat(0,bytes(entries[start])));kind='leaf'}
else{const k=split(size),a=await tree(start,k),b=await tree(start+k,size-k);value=await sha(cat(1,bytes(a),bytes(b)));kind='branch';left=String(k);right=String(size-k)}
cache.set(start+':'+size,value);trace.push({start_leaf_index:String(start),leaf_count:String(size),kind,hash_hex:value,left_count:left,right_count:right});return value;
}
const root=await tree(0,n),commitment={schema_version:'d30-merkle-root-v1',...metadata(request),tree_size:String(n),root_hex:root};let proof:Obj|null=null;
if(index!==null){let start=0,size=n,i=Number(index);const path:string[]=[];while(size>1){const k=split(size);if(i<k){path.push(cache.get((start+k)+':'+(size-k))!);size=k}else{path.push(cache.get(start+':'+k)!);start+=k;size-=k;i-=k}}
proof={schema_version:'d30-merkle-inclusion-v1',...metadata(request),tree_size:String(n),leaf_index:index,entry_hex:entries[Number(index)],path:path.reverse()}}
return{status:'ok',code:'MERKLE_COMMITMENT_BUILT',commitment,proof,trace};
}catch(e){if(e instanceof MerkleError)return emptyBuild('rejected',e.message);if(e instanceof CryptoUnavailable)return emptyBuild('indeterminate','CRYPTO_UNAVAILABLE');throw e}
}
function validRoot(v:any):boolean{return exact(v,ROOT)&&v.schema_version==='d30-merkle-root-v1'&&scope(v)&&count(v.start_group_index,1)&&count(v.tree_size)&&(Number(v.tree_size)===0||Number(v.start_group_index)+Number(v.tree_size)-1<=4096)&&digest(v.root_hex)}
export async function verifyMerkleInclusion(proof:any,trustedCommitment:any):Promise<Obj>{
try{
need(exact(proof,PROOF)&&proof.schema_version==='d30-merkle-inclusion-v1','INVALID_PROOF_SCHEMA');need(scope(proof),'INVALID_SCOPE');
need(count(proof.start_group_index,1)&&count(proof.tree_size,1)&&Number(proof.start_group_index)+Number(proof.tree_size)-1<=4096,'INVALID_GROUP_RANGE');
need(count(proof.leaf_index,0,4095)&&Number(proof.leaf_index)<Number(proof.tree_size),'INVALID_PROOF_INDEX');need(entry(proof.entry_hex),'INVALID_ENTRY_HEX');
const path=proof.path;need(Array.isArray(path)&&path.length<=12&&path.every(digest),'INVALID_PROOF_PATH');const orientations=sides(Number(proof.tree_size),Number(proof.leaf_index));need(path.length===orientations.length,'INVALID_PROOF_LENGTH');
need(trustedCommitment===null||validRoot(trustedCommitment),'INVALID_TRUSTED_COMMITMENT');
let current=await sha(cat(0,bytes(proof.entry_hex)));const leaf=current,trace:Obj[]=[];
for(let i=0;i<path.length;i++){const sibling=path[i],side=orientations[i],before=current,a=side==='left'?sibling:current,b=side==='left'?current:sibling;current=await sha(cat(1,bytes(a),bytes(b)));trace.push({step:String(i+1),sibling_side:side,sibling_hash_hex:sibling,input_hash_hex:before,output_hash_hex:current})}
const mismatched=trustedCommitment===null?[]:[...META,'tree_size'].filter(k=>proof[k]!==trustedCommitment[k]).sort();let status:string,code:string;
if(trustedCommitment===null){status='indeterminate';code='MISSING_TRUSTED_COMMITMENT'}else if(mismatched.length){status='fail';code='TRUSTED_COMMITMENT_MISMATCH'}else if(current!==trustedCommitment.root_hex){status='fail';code='MERKLE_ROOT_MISMATCH'}else{status='pass';code='MERKLE_INCLUSION_VERIFIED'}
return{status,code,scope:metadata(proof),proof:{...proof,path:[...path]},verification:{computed_root_hex:current,expected_root_hex:trustedCommitment===null?null:trustedCommitment.root_hex,leaf_hash_hex:leaf,tree_size:proof.tree_size,leaf_index:proof.leaf_index,group_index:String(Number(proof.start_group_index)+Number(proof.leaf_index)),path_length:String(path.length),byte_scope_only:true,mismatched_fields:mismatched},trace};
}catch(e){if(e instanceof MerkleError)return emptyVerify('rejected',e.message);if(e instanceof CryptoUnavailable)return emptyVerify('indeterminate','CRYPTO_UNAVAILABLE');throw e}
}
The embedded lab now expands to its full document height, keeping the article as the only scroll surface.