Clarify Distinction Between MerkleTree.insert() and MerkleTree.insertHash() API

[emnul]

Where is the issue?

Issue is located on this page.

Type of issue

• Missing content
• Outdated content
• Inaccurate content

Description of the issue

The insert and insertHash API operate fundamentally differently under the hood and this should be clarified in the documentation. For example, given the following contract

test.compact

import CompactStandardLibrary;

export {
  ZswapCoinPublicKey,
  ContractAddress,
  Either,
  Maybe,
  MerkleTreePath,
};

export ledger merkleTree: MerkleTree<10, Bytes<32>>;

witness wit_getCommitmentPath(commitment: Bytes<32>): MerkleTreePath<10, Bytes<32>>;

export circuit insertIntoMerkleTree(): [] {
  merkleTree.insert(1 as Field as Bytes<32>);
}

export circuit insertHashIntoMerkleTree(): [] {
  merkleTree.insertHash(2 as Field as Bytes<32>);
}

export circuit checkMerkleTreeInsert(): Boolean {
  const authPath = wit_getCommitmentPath(1 as Field as Bytes<32>);
  const isPathInTree = merkleTree
      .checkRoot(merkleTreePathRoot<10, Bytes<32>>(disclose(authPath)));
  return isPathInTree;
}

export circuit checkMerkleTreeInsertHash(): Boolean {
  const authPath = wit_getCommitmentPath(2 as Field as Bytes<32>);
  const isPathInTree = merkleTree
      .checkRoot(merkleTreePathRoot<10, Bytes<32>>(disclose(authPath)));
  return isPathInTree;
}

and the following witness implementation

testWitnesses.ts

import { type WitnessContext } from '@midnight-ntwrk/compact-runtime';
import type { Ledger, MerkleTreePath } from '../../../artifacts/MockTest/contract/index.cjs';

/**
 * @description Interface defining the witness methods for MockTest operations.
 * @template P - The private state type.
 */
export interface IMockTestWitnesses<P> {
  /**
   * Retrieves a MerkleTreePath
   * @param context - The witness context containing the private state.
   * @returns A tuple of the private state and the MerkleTreePath.
   */
  wit_getCommitmentPath(context: WitnessContext<Ledger, P>, commitment: Uint8Array): [P, MerkleTreePath<Uint8Array>];
}

export type MockTestPrivateState = {
};

/**
 * @description Utility object for managing the private state of a contract.
 */
export const MockTestPrivateState = {
  getCommitmentPath: (ledger: Ledger, commitment: Uint8Array): MerkleTreePath<Uint8Array> => {
    const path = ledger.merkleTree.findPathForLeaf(commitment);
    const defaultPath: MerkleTreePath<Uint8Array> = {
      leaf: new Uint8Array(32),
      path: Array.from({ length: 10 }, () => ({
        sibling: { field: 0n },
        goes_left: false,
      }))
    }
    return path ? path : defaultPath;
  },
};

/**
 * @description Factory function creating witness implementations for MockTest operations.
 * @returns An object implementing the Witnesses interface for MockTestPrivateState.
 */
export const MockTestWitnesses =
  (): IMockTestWitnesses<MockTestPrivateState> => ({
    wit_getCommitmentPath(
      context: WitnessContext<Ledger, MockTestPrivateState>,
      commitment: Uint8Array
    ): [MockTestPrivateState, MerkleTreePath<Uint8Array>] {
      return [context.privateState, MockTestPrivateState.getCommitmentPath(context.ledger, commitment)];
    },
  });

Once the insertIntoMerkleTree and insertHashIntoMerkleTree circuits have been called, checkMerkleTreeInsert will always return true, but checkMerkleTreeInsertHash will always return false. The documentation does not state what operations take place on the values passed to insertHash making it impossible to recreate the final value and proving knowledge of it.

Suggested change

The behavior of the insertHash* functions for the MerkleTree LDT should be clarified.

[tkerber]

For context, what's going on here is that merkleTreePathRoot hashed the leaf element contained in the path, which is not correct for paths to a 'raw' hash produced with insertHash. Instead, in this case you should determine the path root with merkleTreePathRootNoLeafHash.

[nebelsprachen]

@tkerber could you provide additional context on this and possibly open a PR to address what needs to be changed?