-
Notifications
You must be signed in to change notification settings - Fork 592
/
criteria.ts
114 lines (90 loc) · 2.64 KB
/
criteria.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import { ethers } from "ethers";
const { keccak256 } = ethers.utils;
type BufferElementPositionIndex = { [key: string]: number };
export const merkleTree = (tokenIds: ethers.BigNumber[]) => {
const elements = tokenIds
.map((tokenId) =>
Buffer.from(tokenId.toHexString().slice(2).padStart(64, "0"), "hex")
)
.sort(Buffer.compare)
.filter((el, idx, arr) => {
return idx === 0 || !arr[idx - 1].equals(el);
});
const bufferElementPositionIndex = elements.reduce(
(memo: BufferElementPositionIndex, el, index) => {
memo["0x" + el.toString("hex")] = index;
return memo;
},
{}
);
// Create layers
const layers = getLayers(elements);
const root = "0x" + layers[layers.length - 1][0].toString("hex");
const proofs = Object.fromEntries(
elements.map((el) => [
ethers.BigNumber.from(el).toString(),
getHexProof(el, bufferElementPositionIndex, layers),
])
);
const maxProofLength = Math.max(
...Object.values(proofs).map((i) => i.length)
);
return {
root,
proofs,
maxProofLength,
};
};
const getLayers = (elements: Buffer[]) => {
if (elements.length === 0) {
throw new Error("empty tree");
}
const layers = [];
layers.push(elements.map((el) => Buffer.from(keccak256(el).slice(2), "hex")));
// Get next layer until we reach the root
while (layers[layers.length - 1].length > 1) {
layers.push(getNextLayer(layers[layers.length - 1]));
}
return layers;
};
const getNextLayer = (elements: Buffer[]) => {
return elements.reduce((layer: Buffer[], el, idx, arr) => {
if (idx % 2 === 0) {
// Hash the current element with its pair element
layer.push(combinedHash(el, arr[idx + 1]));
}
return layer;
}, []);
};
const combinedHash = (first: Buffer, second: Buffer) => {
if (!first) {
return second;
}
if (!second) {
return first;
}
return Buffer.from(
keccak256(Buffer.concat([first, second].sort(Buffer.compare))).slice(2),
"hex"
);
};
const getHexProof = (
el: Buffer,
bufferElementPositionIndex: BufferElementPositionIndex,
layers: Buffer[][]
) => {
let idx = bufferElementPositionIndex["0x" + el.toString("hex")];
if (typeof idx !== "number") {
throw new Error("Element does not exist in Merkle tree");
}
const proofBuffer = layers.reduce((proof: Buffer[], layer) => {
const pairIdx = idx % 2 === 0 ? idx + 1 : idx - 1;
const pairElement = pairIdx < layer.length ? layer[pairIdx] : null;
if (pairElement) {
proof.push(pairElement);
}
idx = Math.floor(idx / 2);
return proof;
}, []);
return proofBuffer.map((el) => "0x" + el.toString("hex"));
};