1 | import * as rlp from 'rlp'
|
2 | import { keccak256 } from 'ethereumjs-util'
|
3 | import { bufferToNibbles, nibblesToBuffer } from './util/nibbles'
|
4 | import { isTerminator, addHexPrefix, removeHexPrefix } from './util/hex'
|
5 |
|
6 | export type TrieNode = BranchNode | ExtensionNode | LeafNode
|
7 | export type Nibbles = number[]
|
8 |
|
9 |
|
10 | export type EmbeddedNode = Buffer | Buffer[]
|
11 |
|
12 | export class BranchNode {
|
13 | _branches: (EmbeddedNode | null)[]
|
14 | _value: Buffer | null
|
15 |
|
16 | constructor() {
|
17 | this._branches = new Array(16).fill(null)
|
18 | this._value = null
|
19 | }
|
20 |
|
21 | static fromArray(arr: Buffer[]): BranchNode {
|
22 | const node = new BranchNode()
|
23 | node._branches = arr.slice(0, 16)
|
24 | node._value = arr[16]
|
25 | return node
|
26 | }
|
27 |
|
28 | get value(): Buffer | null {
|
29 | return this._value && this._value.length > 0 ? this._value : null
|
30 | }
|
31 |
|
32 | set value(v: Buffer | null) {
|
33 | this._value = v
|
34 | }
|
35 |
|
36 | setBranch(i: number, v: EmbeddedNode | null) {
|
37 | this._branches[i] = v
|
38 | }
|
39 |
|
40 | raw(): (EmbeddedNode | null)[] {
|
41 | return [...this._branches, this._value]
|
42 | }
|
43 |
|
44 | serialize(): Buffer {
|
45 | return rlp.encode(this.raw())
|
46 | }
|
47 |
|
48 | hash(): Buffer {
|
49 | return keccak256(this.serialize())
|
50 | }
|
51 |
|
52 | getBranch(i: number) {
|
53 | const b = this._branches[i]
|
54 | if (b !== null && b.length > 0) {
|
55 | return b
|
56 | } else {
|
57 | return null
|
58 | }
|
59 | }
|
60 |
|
61 | getChildren(): [number, EmbeddedNode][] {
|
62 | const children: [number, EmbeddedNode][] = []
|
63 | for (let i = 0; i < 16; i++) {
|
64 | const b = this._branches[i]
|
65 | if (b !== null && b.length > 0) {
|
66 | children.push([i, b])
|
67 | }
|
68 | }
|
69 | return children
|
70 | }
|
71 | }
|
72 |
|
73 | export class ExtensionNode {
|
74 | _nibbles: Nibbles
|
75 | _value: Buffer
|
76 |
|
77 | constructor(nibbles: Nibbles, value: Buffer) {
|
78 | this._nibbles = nibbles
|
79 | this._value = value
|
80 | }
|
81 |
|
82 | static encodeKey(key: Nibbles): Nibbles {
|
83 | return addHexPrefix(key, false)
|
84 | }
|
85 |
|
86 | static decodeKey(key: Nibbles): Nibbles {
|
87 | return removeHexPrefix(key)
|
88 | }
|
89 |
|
90 | get key(): Nibbles {
|
91 | return this._nibbles.slice(0)
|
92 | }
|
93 |
|
94 | set key(k: Nibbles) {
|
95 | this._nibbles = k
|
96 | }
|
97 |
|
98 | get value(): Buffer {
|
99 | return this._value
|
100 | }
|
101 |
|
102 | set value(v: Buffer) {
|
103 | this._value = v
|
104 | }
|
105 |
|
106 | encodedKey(): Nibbles {
|
107 | return ExtensionNode.encodeKey(this._nibbles.slice(0))
|
108 | }
|
109 |
|
110 | raw(): [Buffer, Buffer] {
|
111 | return [nibblesToBuffer(this.encodedKey()), this._value]
|
112 | }
|
113 |
|
114 | serialize(): Buffer {
|
115 | return rlp.encode(this.raw())
|
116 | }
|
117 |
|
118 | hash(): Buffer {
|
119 | return keccak256(this.serialize())
|
120 | }
|
121 | }
|
122 |
|
123 | export class LeafNode {
|
124 | _nibbles: Nibbles
|
125 | _value: Buffer
|
126 |
|
127 | constructor(nibbles: Nibbles, value: Buffer) {
|
128 | this._nibbles = nibbles
|
129 | this._value = value
|
130 | }
|
131 |
|
132 | static encodeKey(key: Nibbles): Nibbles {
|
133 | return addHexPrefix(key, true)
|
134 | }
|
135 |
|
136 | static decodeKey(encodedKey: Nibbles): Nibbles {
|
137 | return removeHexPrefix(encodedKey)
|
138 | }
|
139 |
|
140 | get key(): Nibbles {
|
141 | return this._nibbles.slice(0)
|
142 | }
|
143 |
|
144 | set key(k: Nibbles) {
|
145 | this._nibbles = k
|
146 | }
|
147 |
|
148 | get value(): Buffer {
|
149 | return this._value
|
150 | }
|
151 |
|
152 | set value(v: Buffer) {
|
153 | this._value = v
|
154 | }
|
155 |
|
156 | encodedKey(): Nibbles {
|
157 | return LeafNode.encodeKey(this._nibbles.slice(0))
|
158 | }
|
159 |
|
160 | raw(): [Buffer, Buffer] {
|
161 | return [nibblesToBuffer(this.encodedKey()), this._value]
|
162 | }
|
163 |
|
164 | serialize(): Buffer {
|
165 | return rlp.encode(this.raw())
|
166 | }
|
167 |
|
168 | hash(): Buffer {
|
169 | return keccak256(this.serialize())
|
170 | }
|
171 | }
|
172 |
|
173 | export function decodeRawNode(raw: Buffer[]): TrieNode {
|
174 | if (raw.length === 17) {
|
175 | return BranchNode.fromArray(raw)
|
176 | } else if (raw.length === 2) {
|
177 | const nibbles = bufferToNibbles(raw[0])
|
178 | if (isTerminator(nibbles)) {
|
179 | return new LeafNode(LeafNode.decodeKey(nibbles), raw[1])
|
180 | }
|
181 | return new ExtensionNode(ExtensionNode.decodeKey(nibbles), raw[1])
|
182 | } else {
|
183 | throw new Error('Invalid node')
|
184 | }
|
185 | }
|
186 |
|
187 | export function decodeNode(raw: Buffer): TrieNode {
|
188 | const des = rlp.decode(raw)
|
189 | if (!Array.isArray(des)) {
|
190 | throw new Error('Invalid node')
|
191 | }
|
192 | return decodeRawNode(des)
|
193 | }
|
194 |
|
195 | export function isRawNode(n: any): boolean {
|
196 | return Array.isArray(n) && !Buffer.isBuffer(n)
|
197 | }
|