import type { EpochNumber } from '@aztec/foundation/branded-types';
import { Fr } from '@aztec/foundation/curves/bn254';
import { SiblingPath } from '@aztec/foundation/trees';
import type { AztecNode } from '../interfaces/aztec-node.js';
import { TxHash } from '../tx/tx_hash.js';
/**
 * # L2-to-L1 Message Tree Structure and Leaf IDs
 *
 * ## Overview
 * L2-to-L1 messages are organized in a hierarchical 4-level tree structure within each epoch:
 *   Epoch → Checkpoints → Blocks → Transactions → Messages
 *
 * Each level uses an unbalanced Merkle tree, and some levels use compression (skipping zero hashes).
 *
 * ## Tree Levels
 *
 * 1. **Message Tree (TX Out Hash)**
 *    - Leaves: Individual L2-to-L1 messages within a transaction
 *    - Root: TX out hash
 *    - Type: Unbalanced, non-compressed (the circuits ensure that all messages are not empty.)
 *
 * 2. **Block Tree**
 *    - Leaves: TX out hashes from all transactions in a block
 *    - Root: Block out hash
 *    - Type: Unbalanced, compressed (zero hashes are skipped)
 *    - Compression: If a tx has no messages (out hash = 0), that branch is ignored
 *
 * 3. **Checkpoint Tree**
 *    - Leaves: Block out hashes from all blocks in a checkpoint
 *    - Root: Checkpoint out hash
 *    - Type: Unbalanced, compressed (zero hashes are skipped)
 *    - Compression: If a block has no messages (out hash = 0), that branch is ignored
 *
 * 4. **Epoch Tree**
 *    - Leaves: Checkpoint out hashes from all checkpoints in an epoch (padded to OUT_HASH_TREE_LEAF_COUNT)
 *    - Root: Epoch out hash (set in the root rollup's public inputs and inserted into the Outbox on L1 when the epoch is proven)
 *    - Type: Unbalanced, non-compressed
 *    - **Important**: Padded with zeros up to OUT_HASH_TREE_LEAF_COUNT to allow for proofs of partial epochs
 *
 * ## Combined Membership Proof
 * To prove a message exists in an epoch, we combine the sibling paths from all 4 trees:
 *   [message siblings] + [tx siblings] + [block siblings] + [checkpoint siblings]
 *
 * ## Leaf ID: Stable Message Identification
 *
 * Each message gets a unique, stable **leaf ID** that identifies its position in the combined tree.
 * The leaf ID is computed as:
 *   leafId = 2^pathSize + leafIndex
 *
 * Where:
 * - `pathSize`: Total length of the combined sibling path (from all 4 tree levels)
 * - `leafIndex`: The message's index in a balanced tree representation at that height
 *
 * ### Why Leaf IDs Are Stable
 *
 * The leaf ID is based on the message's position in the tree structure, which is determined by:
 * - The checkpoint index within the epoch
 * - The block index within the checkpoint
 * - The transaction index within the block
 * - The message index within the transaction
 *
 * These indices are structural and do NOT depend on the total number of blocks/checkpoints in the epoch.
 *
 * ### Critical Property: Preserving Consumed Status
 *
 * **Problem**: On L1, epoch proofs can be submitted incrementally. For example:
 * - First, a proof for checkpoints 1-10 of epoch 0 is submitted (proves the first 10 checkpoints)
 * - Later, a proof for checkpoints 1-20 of epoch 0 is submitted (proves all 20 checkpoints)
 *
 * When the longer proof is submitted, it updates the epoch's out hash root on L1 to reflect the complete epoch (all 20
 * checkpoints). However, some messages from checkpoints 1-10 may have already been consumed.
 *
 * **Solution**: The Outbox on L1 tracks consumed messages using a bitmap indexed by leaf ID.
 * Because leaf IDs are stable (they don't change when more checkpoints are added to the epoch), messages that were consumed
 * under the shorter proof remain marked as consumed under the longer proof.
 *
 * This prevents double-spending of L2-to-L1 messages when longer epoch proofs are submitted.
 */
/**
 * Computes the unique leaf ID for an L2-to-L1 message.
 *
 * The leaf ID is stable across different epoch proof lengths and is used by the Outbox
 * on L1 to track which messages have been consumed.
 *
 * @param membershipWitness - Contains the leafIndex and siblingPath for the message
 * @returns The unique leaf ID used for tracking message consumption on L1
 */
export declare function getL2ToL1MessageLeafId(membershipWitness: Pick<L2ToL1MembershipWitness, 'leafIndex' | 'siblingPath'>): bigint;
export type L2ToL1MembershipWitness = {
    root: Fr;
    leafIndex: bigint;
    siblingPath: SiblingPath<number>;
    epochNumber: EpochNumber;
};
/**
 * Computes the L2 to L1 membership witness for a given message in a transaction.
 *
 * @param node - The Aztec node to query for block/tx/epoch data.
 * @param message - The L2 to L1 message hash to prove membership of.
 * @param txHash - The hash of the transaction that emitted the message.
 * @param messageIndexInTx - Optional index of the message within the transaction's L2-to-L1 messages.
 *   If not provided, the message is found by scanning the tx's messages (throws if duplicates exist).
 * @returns The membership witness and epoch number, or undefined if the tx is not yet in a block/epoch.
 */
export declare function computeL2ToL1MembershipWitness(node: Pick<AztecNode, 'getL2ToL1Messages' | 'getTxReceipt' | 'getTxEffect' | 'getBlock' | 'getCheckpointsDataForEpoch'>, message: Fr, txHash: TxHash, messageIndexInTx?: number): Promise<L2ToL1MembershipWitness | undefined>;
/**
 * Computes a membership witness for a message in the epoch's L2-to-L1 message tree, given explicit position indices.
 *
 * @param messagesInEpoch - All L2-to-L1 messages in the epoch, organized as checkpoints → blocks → txs → messages.
 * @param message - The message hash to prove membership of.
 * @param checkpointIndex - Index of the checkpoint within the epoch's message array.
 * @param blockIndex - Index of the block within the checkpoint.
 * @param txIndex - Index of the transaction within the block.
 * @param messageIndexInTx - Optional index of the message within the transaction's messages.
 *   If not provided, the message is found by scanning (throws if duplicates exist within the tx).
 */
/** @internal Exported for testing only. */
export declare function computeL2ToL1MembershipWitnessFromMessagesInEpoch(messagesInEpoch: Fr[][][][], message: Fr, checkpointIndex: number, blockIndex: number, txIndex: number, messageIndexInTx?: number): {
    root: Fr;
    leafIndex: bigint;
    siblingPath: SiblingPath<number>;
};
//# sourceMappingURL=data:application/json;base64,eyJ2ZXJzaW9uIjozLCJmaWxlIjoibDJfdG9fbDFfbWVtYmVyc2hpcC5kLnRzIiwic291cmNlUm9vdCI6IiIsInNvdXJjZXMiOlsiLi4vLi4vc3JjL21lc3NhZ2luZy9sMl90b19sMV9tZW1iZXJzaGlwLnRzIl0sIm5hbWVzIjpbXSwibWFwcGluZ3MiOiJBQUNBLE9BQU8sS0FBSyxFQUFFLFdBQVcsRUFBRSxNQUFNLGlDQUFpQyxDQUFDO0FBQ25FLE9BQU8sRUFBRSxFQUFFLEVBQUUsTUFBTSxnQ0FBZ0MsQ0FBQztBQUNwRCxPQUFPLEVBQUUsV0FBVyxFQUE0RCxNQUFNLHlCQUF5QixDQUFDO0FBRWhILE9BQU8sS0FBSyxFQUFFLFNBQVMsRUFBRSxNQUFNLDZCQUE2QixDQUFDO0FBQzdELE9BQU8sRUFBRSxNQUFNLEVBQUUsTUFBTSxrQkFBa0IsQ0FBQztBQUUxQzs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7O0dBd0VHO0FBRUg7Ozs7Ozs7O0dBUUc7QUFDSCx3QkFBZ0Isc0JBQXNCLENBQ3BDLGlCQUFpQixFQUFFLElBQUksQ0FBQyx1QkFBdUIsRUFBRSxXQUFXLEdBQUcsYUFBYSxDQUFDLEdBQzVFLE1BQU0sQ0FFUjtBQUVELE1BQU0sTUFBTSx1QkFBdUIsR0FBRztJQUNwQyxJQUFJLEVBQUUsRUFBRSxDQUFDO0lBQ1QsU0FBUyxFQUFFLE1BQU0sQ0FBQztJQUNsQixXQUFXLEVBQUUsV0FBVyxDQUFDLE1BQU0sQ0FBQyxDQUFDO0lBQ2pDLFdBQVcsRUFBRSxXQUFXLENBQUM7Q0FDMUIsQ0FBQztBQUVGOzs7Ozs7Ozs7R0FTRztBQUNILHdCQUFzQiw4QkFBOEIsQ0FDbEQsSUFBSSxFQUFFLElBQUksQ0FDUixTQUFTLEVBQ1QsbUJBQW1CLEdBQUcsY0FBYyxHQUFHLGFBQWEsR0FBRyxVQUFVLEdBQUcsNEJBQTRCLENBQ2pHLEVBQ0QsT0FBTyxFQUFFLEVBQUUsRUFDWCxNQUFNLEVBQUUsTUFBTSxFQUNkLGdCQUFnQixDQUFDLEVBQUUsTUFBTSxHQUN4QixPQUFPLENBQUMsdUJBQXVCLEdBQUcsU0FBUyxDQUFDLENBa0M5QztBQUVEOzs7Ozs7Ozs7O0dBVUc7QUFDSCwyQ0FBMkM7QUFDM0Msd0JBQWdCLGlEQUFpRCxDQUMvRCxlQUFlLEVBQUUsRUFBRSxFQUFFLEVBQUUsRUFBRSxFQUFFLEVBQzNCLE9BQU8sRUFBRSxFQUFFLEVBQ1gsZUFBZSxFQUFFLE1BQU0sRUFDdkIsVUFBVSxFQUFFLE1BQU0sRUFDbEIsT0FBTyxFQUFFLE1BQU0sRUFDZixnQkFBZ0IsQ0FBQyxFQUFFLE1BQU0sR0FDeEI7SUFBRSxJQUFJLEVBQUUsRUFBRSxDQUFDO0lBQUMsU0FBUyxFQUFFLE1BQU0sQ0FBQztJQUFDLFdBQVcsRUFBRSxXQUFXLENBQUMsTUFBTSxDQUFDLENBQUE7Q0FBRSxDQW9FbkUifQ==