Mina Learning - MerkleTree

longerd
更新于 2024-12-11 15:06
阅读 201

简单介绍 MerkleTree 和 Delta merkle proof.

## Delta merkle proof

**在实际应用中, 除了证明默克尔树中存在某一特定叶子节点外(merkle proof), 我们通常还希望证明将树中的特定叶子节点从一个值修改为另一个值的结果(delta merkle proof).**

Delta merkle proof 可以证明:
* 在具有默克尔根 A 的树中, 索引为 I 的叶子节点存在值为 X. 
* 如果在不修改树中任何其他叶子节点的情况下, 将索引为 I 的叶子节点的值从 X 更改为 Y, 则树的新默克尔根为 B.

> 注意, 在变更前后的证明中, 兄弟节点是相同的! 即 merkle path(witness) 是相同的.

因此, `delta merkle proof` 包括:
* 叶子的索引
* 叶子的兄弟节点
* 叶子的旧值
* 树的旧根
* 叶子的新值
* 树的新根

### demo

```ts
    const map = new MerkleMap();
    const root1 = map.getRoot();
    const witness1 = map.getWitness(Field(1));
    const [calcroot1, key1] = witness1.computeRootAndKey(Field(0));
    Bool.and(calcroot1.equals(root1), key1.equals(Field(1))).assertTrue('Member validation failed');

map.set(Field(1), Field(10086));
    const root2 = map.getRoot();
    const witness2 = map.getWitness(Field(1));
    const [calcroot2, key2] = witness2.computeRootAndKey(Field(10086));
    Bool.and(calcroot2.equals(root2), key2.equals(Field(1))).assertTrue('Member validation failed');

root1.assertNotEquals(root2);
    witness1.assertEquals(witness2);

map.set(Field(1), Field(10010));
    const root3 = map.getRoot();
    const witness3 = map.getWitness(Field(1));
    const [calcroot3, key3] = witness3.computeRootAndKey(Field(10010));
    Bool.and(calcroot3.equals(root3), key3.equals(Field(1))).assertTrue('Member validation failed');

root2.assertNotEquals(root3);
    witness1.assertEquals(witness3);
```

### Ref

* [a hackers guide to layer 2 merkle trees from scratc](https://medium.com/@carterfeldman/a-hackers-guide-to-layer-2-merkle-trees-from-scratch-f682fc31bced)
* [a hackers guide to layer 2 zero merkle trees from scratch](https://medium.com/@carterfeldman/a-hackers-guide-to-layer-2-zero-merkle-trees-from-scratch-d612ea846016)

## [MerkleTree](https://github.com/o1-labs/o1js/blob/996ebb3119ec087a0badc16ea8036766cb68d3fb/src/lib/provable/merkle-tree.ts#L28)
nodes 是每层节点的 map, 一共 height 层. 更新的叶子节点对应的每一层节点会存放到 nodes 中.
zeros 是每层全是 zeros leaves 的 hash 的数组.

```ts
class MerkleTree {
  nodes: Record<number, Record<string, Field>> = {};
  zeroes: Field[];

constructor(public readonly height: number) {
    this.zeroes = new Array(height);
    this.zeroes[0] = Field(0);
    for (let i = 1; i < height; i += 1) {
      this.zeroes[i] = Poseidon.hash([this.zeroes[i - 1], this.zeroes[i - 1]]);
    }
  }
}
```

### [getNode](https://github.com/o1-labs/o1js/blob/996ebb3119ec087a0badc16ea8036766cb68d3fb/src/lib/provable/merkle-tree.ts#L62)
`getNode` 返回某一层, 某个索引的 value, 如果不存在(为未更新的 zero hash), 则从 `zeros[level]` 中查找.
* `?`: 可选链操作符, 允许在访问对象的深层次属性时, 如果中间某个属性为 `null` 或者 `undefined`, 表达式就会短路返回 `undefined`, 而不会抛出错误.
* `??`: 空值合并操作符, 用于在左侧的值为 `null` 或者 `undefined` 时, 返回右侧的值.

```ts
  getNode(level: number, index: bigint): Field {
    return this.nodes[level]?.[index.toString()] ?? this.zeroes[level];
  }
```

### [getRoot](https://github.com/o1-labs/o1js/blob/996ebb3119ec087a0badc16ea8036766cb68d3fb/src/lib/provable/merkle-tree.ts#L79C1-L81C4)
获取 merkletree root.
```ts
  getRoot(): Field {
    return this.getNode(this.height - 1, 0n);
  }
```
### [setNode](https://github.com/o1-labs/o1js/blob/996ebb3119ec087a0badc16ea8036766cb68d3fb/src/lib/provable/merkle-tree.ts#L84)
参考 `getNode`.
```ts
  private setNode(level: number, index: bigint, value: Field) {
    (this.nodes[level] ??= {})[index.toString()] = value;
  }
```

### [setLeaf](https://github.com/o1-labs/o1js/blob/996ebb3119ec087a0badc16ea8036766cb68d3fb/src/lib/provable/merkle-tree.ts#L94)
沿着要更新的 `Leaf` 的路径更新路径上的节点值. 共更新 `height` 个节点. 
```ts
  setLeaf(index: bigint, leaf: Field) {
    if (index >= this.leafCount) {
      throw new Error(
        `index ${index} is out of range for ${this.leafCount} leaves.`
      );
    }
    this.setNode(0, index, leaf);
    let currIndex = index;
    for (let level = 1; level < this.height; level++) {
      currIndex /= 2n;

const left = this.getNode(level - 1, currIndex * 2n);
      const right = this.getNode(level - 1, currIndex * 2n + 1n);

this.setNode(level, currIndex, Poseidon.hash([left, right]));
    }
  }
```

### [getWitness](https://github.com/o1-labs/o1js/blob/996ebb3119ec087a0badc16ea8036766cb68d3fb/src/lib/provable/merkle-tree.ts#L117)
获取 `index` 叶子节点对应的 merkle path.
```ts
  getWitness(index: bigint): Witness {
    if (index >= this.leafCount) {
      throw new Error(
        `index ${index} is out of range for ${this.leafCount} leaves.`
      );
    }
    const witness = [];
    for (let level = 0; level < this.height - 1; level++) {
      const isLeft = index % 2n === 0n;
      const sibling = this.getNode(level, isLeft ? index + 1n : index - 1n);
      witness.push({ isLeft, sibling });
      index /= 2n;
    }
    return witness;
  }
```

## [BaseMerkleWitness](https://github.com/o1-labs/o1js/blob/996ebb3119ec087a0badc16ea8036766cb68d3fb/src/lib/provable/merkle-tree.ts#L174)

```ts
class BaseMerkleWitness extends CircuitValue {
  static height: number;
  path: Field[];
  isLeft: Bool[];
  height(): number {
    return (this.constructor as any).height;
  }

constructor(witness: Witness) {
    super();
    let height = witness.length + 1;
    if (height !== this.height()) {
      throw Error(
        `Length of witness ${height}-1 doesn't match static tree height ${this.height()}.`
      );
    }
    this.path = witness.map((item) => item.sibling);
    this.isLeft = witness.map((item) => Bool(item.isLeft));
  }
}
```

### [calculateRoot](https://github.com/o1-labs/o1js/blob/996ebb3119ec087a0badc16ea8036766cb68d3fb/src/lib/provable/merkle-tree.ts#L204)
根据输入的叶子节点的 value 和 merkle path 计算 merkletree root.
```ts
  calculateRoot(leaf: Field): Field {
    let hash = leaf;
    let n = this.height();

for (let i = 1; i < n; ++i) {
      let isLeft = this.isLeft[i - 1];
      const [left, right] = conditionalSwap(isLeft, hash, this.path[i - 1]);
      hash = Poseidon.hash([left, right]);
    }

return hash;
  }
  ```

## [MerkleMap](https://github.com/o1-labs/o1js/blob/6ebbc23710f6de023fea6d83dc93c5a914c571f2/src/lib/provable/merkle-map.ts#L10)
* **内部维护一个 height 为 256 的 MerkleTree.**
* 确保 key 为 254 位以避免冲突
```ts
class MerkleMap {
  tree: MerkleTree;

constructor() {
    this.tree = new MerkleTree(256);
  }
}
```

### [_keyToIndex](https://github.com/o1-labs/o1js/blob/6ebbc23710f6de023fea6d83dc93c5a914c571f2/src/lib/provable/merkle-map.ts#L25)

> 注意: 确保 key 为 254 位以避免冲突, 因为 Pasta curve 域模数小于 2 的 255 次方. 
> 关于 Pasta 和 Vesta 曲线参考另外一篇文章 https://learnblockchain.cn/article/10083.

### [set](https://github.com/o1-labs/o1js/blob/6ebbc23710f6de023fea6d83dc93c5a914c571f2/src/lib/provable/merkle-map.ts#L55)
同 MerkleTree setLeaf, 只不过要用 `_keyToIndex` 处理 index.

### [getWitness](https://github.com/o1-labs/o1js/blob/6ebbc23710f6de023fea6d83dc93c5a914c571f2/src/lib/provable/merkle-map.ts#L98)
同 MerkleTree getWitness, 只不过要用 `_keyToIndex` 处理 index.

## [MerkleMapWitness](https://github.com/o1-labs/o1js/blob/6ebbc23710f6de023fea6d83dc93c5a914c571f2/src/lib/provable/merkle-map.ts#L106)
同 BaseMerkleWitness. 
```ts
class MerkleMapWitness extends CircuitValue {
  @arrayProp(Bool, 255) isLefts: Bool[];
  @arrayProp(Field, 255) siblings: Field[];

constructor(isLefts: Bool[], siblings: Field[]) {
    super();
    this.isLefts = isLefts;
    this.siblings = siblings;
  }
```
### [computeRootAndKey](https://github.com/o1-labs/o1js/blob/6ebbc23710f6de023fea6d83dc93c5a914c571f2/src/lib/provable/merkle-map.ts#L121)

同 BaseMerkleWitness computeRoot. 由于限制 key 为 254 位, 这里还会返回 key.

```ts
  computeRootAndKey(value: Field) {
    // Check that the computed key is less than 2^254, in order to avoid collisions since the Pasta field modulus is smaller than 2^255
    this.isLefts[0].assertTrue();

let hash = value;

const isLeft = this.isLefts;
    const siblings = this.siblings;

let key = Field(0);

for (let i = 0; i < 255; i++) {
      const left = Provable.if(isLeft[i], hash, siblings[i]);
      const right = Provable.if(isLeft[i], siblings[i], hash);
      hash = Poseidon.hash([left, right]);

const bit = Provable.if(isLeft[i], Field(0), Field(1));

key = key.mul(2).add(bit);
    }

return [hash, key];
  }
}
```

## [MerkleList](https://github.com/o1-labs/o1js/blob/6ebbc23710f6de023fea6d83dc93c5a914c571f2/src/lib/provable/merkle-list.ts#L80)

Dynamic-length list which is represented as a single hash

Supported operations are () and () and some variants thereof.

A Merkle list is generic over its element types, so before using it you must create a subclass for your element type:

```ts
class MyList extends MerkleList.create(MyType) {}

// now use it
let list = MyList.empty();

list.push(new MyType(...));

let element = list.pop();
```

todo

Delta merkle proof

在实际应用中, 除了证明默克尔树中存在某一特定叶子节点外(merkle proof), 我们通常还希望证明将树中的特定叶子节点从一个值修改为另一个值的结果(delta merkle proof).

Delta merkle proof 可以证明:

在具有默克尔根 A 的树中, 索引为 I 的叶子节点存在值为 X.
如果在不修改树中任何其他叶子节点的情况下, 将索引为 I 的叶子节点的值从 X 更改为 Y, 则树的新默克尔根为 B.

注意, 在变更前后的证明中, 兄弟节点是相同的! 即 merkle path(witness) 是相同的.

因此, delta merkle proof 包括:

叶子的索引
叶子的兄弟节点
叶子的旧值
树的旧根
叶子的新值
树的新根

demo

    const map = new MerkleMap();
    const root1 = map.getRoot();
    const witness1 = map.getWitness(Field(1));
    const [calcroot1, key1] = witness1.computeRootAndKey(Field(0));
    Bool.and(calcroot1.equals(root1), key1.equals(Field(1))).assertTrue('Member validation failed');

    map.set(Field(1), Field(10086));
    const root2 = map.getRoot();
    const witness2 = map.getWitness(Field(1));
    const [calcroot2, key2] = witness2.computeRootAndKey(Field(10086));
    Bool.and(calcroot2.equals(root2), key2.equals(Field(1))).assertTrue('Member validation failed');

    root1.assertNotEquals(root2);
    witness1.assertEquals(witness2);

    map.set(Field(1), Field(10010));
    const root3 = map.getRoot();
    const witness3 = map.getWitness(Field(1));
    const [calcroot3, key3] = witness3.computeRootAndKey(Field(10010));
    Bool.and(calcroot3.equals(root3), key3.equals(Field(1))).assertTrue('Member validation failed');

    root2.assertNotEquals(root3);
    witness1.assertEquals(witness3);

Ref

MerkleTree

nodes 是每层节点的 map, 一共 height 层. 更新的叶子节点对应的每一层节点会存放到 nodes 中. zeros 是每层全是 zeros leaves 的 hash 的数组.

class MerkleTree {
  nodes: Record&lt;number, Record&lt;string, Field>> = {};
  zeroes: Field[];

  constructor(public readonly height: number) {
    this.zeroes = new Array(height);
    this.zeroes[0] = Field(0);
    for (let i = 1; i &lt; height; i += 1) {
      this.zeroes[i] = Poseidon.hash([this.zeroes[i - 1], this.zeroes[i - 1]]);
    }
  }
}

getNode

getNode 返回某一层, 某个索引的 value, 如果不存在(为未更新的 zero hash), 则从 zeros[level] 中查找.

?: 可选链操作符, 允许在访问对象的深层次属性时, 如果中间某个属性为 null 或者 undefined, 表达式就会短路返回 undefined, 而不会抛出错误.
??: 空值合并操作符, 用于在左侧的值为 null 或者 undefined 时, 返回右侧的值.

  getNode(level: number, index: bigint): Field {
    return this.nodes[level]?.[index.toString()] ?? this.zeroes[level];
  }

getRoot

获取 merkletree root.

  getRoot(): Field {
    return this.getNode(this.height - 1, 0n);
  }

setNode

参考 getNode.

  private setNode(level: number, index: bigint, value: Field) {
    (this.nodes[level] ??= {})[index.toString()] = value;
  }

setLeaf

沿着要更新的 Leaf 的路径更新路径上的节点值. 共更新 height 个节点.

  setLeaf(index: bigint, leaf: Field) {
    if (index >= this.leafCount) {
      throw new Error(
        `index ${index} is out of range for ${this.leafCount} leaves.`
      );
    }
    this.setNode(0, index, leaf);
    let currIndex = index;
    for (let level = 1; level &lt; this.height; level++) {
      currIndex /= 2n;

      const left = this.getNode(level - 1, currIndex * 2n);
      const right = this.getNode(level - 1, currIndex * 2n + 1n);

      this.setNode(level, currIndex, Poseidon.hash([left, right]));
    }
  }

getWitness

获取 index 叶子节点对应的 merkle path.

  getWitness(index: bigint): Witness {
    if (index >= this.leafCount) {
      throw new Error(
        `index ${index} is out of range for ${this.leafCount} leaves.`
      );
    }
    const witness = [];
    for (let level = 0; level &lt; this.height - 1; level++) {
      const isLeft = index % 2n === 0n;
      const sibling = this.getNode(level, isLeft ? index + 1n : index - 1n);
      witness.push({ isLeft, sibling });
      index /= 2n;
    }
    return witness;
  }

BaseMerkleWitness

class BaseMerkleWitness extends CircuitValue {
  static height: number;
  path: Field[];
  isLeft: Bool[];
  height(): number {
    return (this.constructor as any).height;
  }

  constructor(witness: Witness) {
    super();
    let height = witness.length + 1;
    if (height !== this.height()) {
      throw Error(
        `Length of witness ${height}-1 doesn't match static tree height ${this.height()}.`
      );
    }
    this.path = witness.map((item) => item.sibling);
    this.isLeft = witness.map((item) => Bool(item.isLeft));
  }
}

calculateRoot

根据输入的叶子节点的 value 和 merkle path 计算 merkletree root.

  calculateRoot(leaf: Field): Field {
    let hash = leaf;
    let n = this.height();

    for (let i = 1; i &lt; n; ++i) {
      let isLeft = this.isLeft[i - 1];
      const [left, right] = conditionalSwap(isLeft, hash, this.path[i - 1]);
      hash = Poseidon.hash([left, right]);
    }

    return hash;
  }

MerkleMap

内部维护一个 height 为 256 的 MerkleTree.

确保 key 为 254 位以避免冲突

class MerkleMap {
tree: MerkleTree;

constructor() {
this.tree = new MerkleTree(256);
}
}

_keyToIndex

注意: 确保 key 为 254 位以避免冲突, 因为 Pasta curve 域模数小于 2 的 255 次方. 关于 Pasta 和 Vesta 曲线参考另外一篇文章 https://learnblockchain.cn/article/10083.

class MerkleMapWitness extends CircuitValue {
  @arrayProp(Bool, 255) isLefts: Bool[];
  @arrayProp(Field, 255) siblings: Field[];

  constructor(isLefts: Bool[], siblings: Field[]) {
    super();
    this.isLefts = isLefts;
    this.siblings = siblings;
  }

computeRootAndKey

同 BaseMerkleWitness computeRoot. 由于限制 key 为 254 位, 这里还会返回 key.

  computeRootAndKey(value: Field) {
    // Check that the computed key is less than 2^254, in order to avoid collisions since the Pasta field modulus is smaller than 2^255
    this.isLefts[0].assertTrue();

    let hash = value;

    const isLeft = this.isLefts;
    const siblings = this.siblings;

    let key = Field(0);

    for (let i = 0; i &lt; 255; i++) {
      const left = Provable.if(isLeft[i], hash, siblings[i]);
      const right = Provable.if(isLeft[i], siblings[i], hash);
      hash = Poseidon.hash([left, right]);

      const bit = Provable.if(isLeft[i], Field(0), Field(1));

      key = key.mul(2).add(bit);
    }

    return [hash, key];
  }
}

MerkleList

Dynamic-length list which is represented as a single hash

Supported operations are () and () and some variants thereof.

A Merkle list is generic over its element types, so before using it you must create a subclass for your element type:

class MyList extends MerkleList.create(MyType) {}

// now use it
let list = MyList.empty();

list.push(new MyType(...));

let element = list.pop();

todo

原创
学分: 24
分类: 公链
标签: Mina OpenBuild zk merkle Merkle树

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。

Mina Learning - MerkleTree

Delta merkle proof

demo

Ref

MerkleTree

getNode

getRoot

setNode

setLeaf

getWitness

BaseMerkleWitness

calculateRoot

MerkleMap

_keyToIndex

set

getWitness

MerkleMapWitness

computeRootAndKey

MerkleList

0 条评论

文章目录