Circuits

We use zkemail for email verification and from address reveal from the header of the email.

Proving contiguous elements in merkle tree

This was an interesting problem that I solved. The logic in js for contruction given the siblings.

A note about siblings that siblings at a level are only two for leftmost and rightmost element in the array.

javascript
  static async generateRoot(continousSegment: number[], auditPath: bigint[][], height: number, firstIndex: number, lastIndex: number): Promise<bigint> {
        const mimc = await buildMimc7();
        let aboveLayer: bigint[] = [];
        let currentLayer = continousSegment.map((value) => BigInt(value));
        firstIndex = generalisedIndex(firstIndex, height);
        lastIndex = generalisedIndex(lastIndex, height);
        for (let y = height; y > 0; y--) {
            if (firstIndex % 2 !== 0) {
                currentLayer.unshift(auditPath[y][0]!);
                firstIndex -= 1;
            }
            if (lastIndex % 2 !== 1) {
                currentLayer.push(auditPath[y][1]!);
                lastIndex += 1;
            }
            for (let x = 0; x < currentLayer.length - 1; x += 2) {
                const left = currentLayer[x];
                const right = currentLayer[x + 1];
                const hash = this.hash(left, right, mimc);
                aboveLayer.push(hash);
            }
            currentLayer = aboveLayer;
            aboveLayer = [];
            // a generalised index is 2**height + index-> in the array
            firstIndex = getParentGeneralisedIndex(firstIndex);
            lastIndex = getParentGeneralisedIndex(lastIndex);
        }
        return currentLayer[0];
    }

The circuit is available here

Here is a high level diagram of the circuit’s working

javascript
                 ┌──────────────────────────────────────────────┐
                 │        GenerateRoot Circuit (Top Layer)      │
                 │      Reconstructs Merkle Root from segment   │
                 └──────────────────────────────────────────────┘
                                ▲
                                │
              Reconstructs ↑ layer-by-layer (bottom-up)
                                │
               ┌────────────────────────────────────┐
               │   MerkleLayer (one level up)       │
               │ ────────────────────────────────── │
               │ 1. AddSiblings if needed           │
               │ 2. Hash pairs of nodes             │
               │ 3. Calculate new indices           │
               └────────────────────────────────────┘
                                ▲
                                │
               ┌────────────────────────────────────┐
               │         AddSiblings                │
               │ ────────────────────────────────── │
               │ Uses IsOdd / IsEven to decide      │
               │ if we prepend/append siblings      │
               └────────────────────────────────────┘
                                ▲
                                │
        ┌──────────────┬────────────────────────┬──────────────┐
        │              │                        │              │
┌──────────────┐ ┌──────────────┐        ┌──────────────┐ ┌──────────────┐
│ IsOdd(first) │ │ IsEven(last)│        │  Siblings[0] │ │  Siblings[1] │
└──────────────┘ └──────────────┘        └──────────────┘ └──────────────┘
        │              │                        │              │
        └──────┬───────┴──────┬──────────────────┴──────┬──────┘
               │              │                         │
         ┌─────────────────────────────────────────────────────┐
         │                 Hashing of Pairs                    │
         │ ─────────────────────────────────────────────────── │
         │  loop i = 0 to N:                                   │
         │    if i+1 < size:                                   │
         │      hash = MiMC(left = arr[i], right = arr[i+1])   │
         └─────────────────────────────────────────────────────┘
                                │
                                ▼
              ┌────────────────────────────────────┐
              │   GetParentGeneralisedIndex        │
              │ ────────────────────────────────── │
              │  idx >> 1 (i.e., idx / 2)          │
              └────────────────────────────────────┘

Repeat above `MerkleLayer` for all layers (height times)
until root is computed