Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

@ethereumjs/trie

Package Overview
Dependencies
Maintainers
3
Versions
18
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@ethereumjs/trie - npm Package Compare versions

Comparing version 5.0.0-rc.1 to 5.0.0

5

dist/db/checkpoint.d.ts

@@ -15,2 +15,7 @@ /// <reference types="node" />

/**
* Flush the checkpoints and use the given checkpoints instead.
* @param {Checkpoint[]} checkpoints
*/
setCheckpoints(checkpoints: Checkpoint[]): void;
/**
* Is the DB during a checkpoint phase?

@@ -17,0 +22,0 @@ */

13

dist/db/checkpoint.js

@@ -18,2 +18,15 @@ "use strict";

/**
* Flush the checkpoints and use the given checkpoints instead.
* @param {Checkpoint[]} checkpoints
*/
setCheckpoints(checkpoints) {
this.checkpoints = [];
for (let i = 0; i < checkpoints.length; i++) {
this.checkpoints.push({
root: checkpoints[i].root,
keyValueMap: new Map(checkpoints[i].keyValueMap),
});
}
}
/**
* Is the DB during a checkpoint phase?

@@ -20,0 +33,0 @@ */

6

dist/trie/trie.d.ts

@@ -5,3 +5,3 @@ /// <reference types="node" />

import { TrieReadStream as ReadStream } from '../util/readStream';
import type { BatchDBOp, EmbeddedNode, FoundNodeFunction, Nibbles, Proof, TrieNode, TrieOpts } from '../types';
import type { BatchDBOp, DB, EmbeddedNode, FoundNodeFunction, Nibbles, Proof, TrieNode, TrieOpts } from '../types';
interface Path {

@@ -32,6 +32,7 @@ node: TrieNode | null;

static create(opts?: TrieOpts): Promise<Trie>;
database(db?: DB): CheckpointDB;
/**
* Gets and/or Sets the current root of the `trie`
*/
root(value?: Buffer): Buffer;
root(value?: Buffer | null): Buffer;
/**

@@ -156,2 +157,3 @@ * Checks if a given root exists.

verifyRangeProof(rootHash: Buffer, firstKey: Buffer | null, lastKey: Buffer | null, keys: Buffer[], values: Buffer[], proof: Buffer[] | null): Promise<boolean>;
verifyPrunedIntegrity(): Promise<boolean>;
/**

@@ -158,0 +160,0 @@ * The `data` event is given an `Object` that has two properties; the `key` and the `value`. Both should be Buffers.

140

dist/trie/trie.js

@@ -26,6 +26,6 @@ "use strict";

this._opts = {
deleteFromDB: false,
useKeyHashing: false,
useKeyHashingFunction: keccak_1.keccak256,
useRootPersistence: false,
useNodePruning: false,
};

@@ -36,6 +36,3 @@ this._lock = new lock_1.Lock();

}
if (opts?.db instanceof db_1.CheckpointDB) {
throw new Error('Cannot pass in an instance of CheckpointDB');
}
this._db = new db_1.CheckpointDB(opts?.db ?? new db_1.MapDB());
this.database(opts?.db ?? new db_1.MapDB());
this.EMPTY_TRIE_ROOT = this.hash(util_1.RLP_EMPTY_STRING);

@@ -64,2 +61,11 @@ this._hashLen = this.EMPTY_TRIE_ROOT.length;

}
database(db) {
if (db !== undefined) {
if (db instanceof db_1.CheckpointDB) {
throw new Error('Cannot pass in an instance of CheckpointDB');
}
this._db = new db_1.CheckpointDB(db);
}
return this._db;
}
/**

@@ -70,3 +76,3 @@ * Gets and/or Sets the current root of the `trie`

if (value !== undefined) {
if ((0, util_1.isFalsy)(value)) {
if (value === null) {
value = this.EMPTY_TRIE_ROOT;

@@ -124,3 +130,3 @@ }

// If value is empty, delete
if ((0, util_1.isFalsy)(value) || value.toString() === '') {
if (value === null || value.length === 0) {
return await this.del(key);

@@ -137,4 +143,27 @@ }

const { remaining, stack } = await this.findPath(appliedKey);
let ops = [];
if (this._opts.useNodePruning) {
const val = await this.get(key);
// Only delete keys if it either does not exist, or if it gets updated
// (The update will update the hash of the node, thus we can delete the original leaf node)
if (val === null || !val.equals(value)) {
// All items of the stack are going to change.
// (This is the path from the root node to wherever it needs to insert nodes)
// The items change, because the leaf value is updated, thus all keyhashes in the
// stack should be updated as well, so that it points to the right key/value pairs of the path
const deleteHashes = stack.map((e) => this.hash(e.serialize()));
ops = deleteHashes.map((e) => {
return {
type: 'del',
key: e,
};
});
}
}
// then update
await this._updateNode(appliedKey, value, remaining, stack);
if (this._opts.useNodePruning) {
// Only after updating the node we can delete the keyhashes
await this._db.batch(ops);
}
}

@@ -154,5 +183,22 @@ await this.persistRoot();

const { node, stack } = await this.findPath(appliedKey);
let ops = [];
// Only delete if the `key` currently has any value
if (this._opts.useNodePruning && node !== null) {
const deleteHashes = stack.map((e) => this.hash(e.serialize()));
// Just as with `put`, the stack items all will have their keyhashes updated
// So after deleting the node, one can safely delete these from the DB
ops = deleteHashes.map((e) => {
return {
type: 'del',
key: e,
};
});
}
if (node) {
await this._deleteNode(appliedKey, stack);
}
if (this._opts.useNodePruning) {
// Only after deleting the node it is possible to delete the keyhashes
await this._db.batch(ops);
}
await this.persistRoot();

@@ -376,5 +422,5 @@ this._lock.release();

// branchNode is the node ON the branch node not THE branch node
if ((0, util_1.isFalsy)(parentNode) || parentNode instanceof node_1.BranchNode) {
if (parentNode === null || parentNode === undefined || parentNode instanceof node_1.BranchNode) {
// branch->?
if ((0, util_1.isTruthy)(parentNode)) {
if (parentNode !== null && parentNode !== undefined) {
stack.push(parentNode);

@@ -412,5 +458,5 @@ }

const branchNodeKey = branchNode.key();
// branch node is an leaf or extension and parent node is an exstention
// branch node is an leaf or extension and parent node is an extension
// add two keys together
// dont push the parent node
// don't push the parent node
branchNodeKey.unshift(branchKey);

@@ -426,3 +472,3 @@ key = key.concat(branchNodeKey);

let lastNode = stack.pop();
if ((0, util_1.isFalsy)(lastNode))
if (lastNode === undefined)
throw new Error('missing last node');

@@ -462,2 +508,14 @@ let parentNode = stack.pop();

const branchNodeKey = branchNodes[0][0];
// Special case where one needs to delete an extra node:
// In this case, after updating the branch, the branch node has just one branch left
// However, this violates the trie spec; this should be converted in either an ExtensionNode
// Or a LeafNode
// Since this branch is deleted, one can thus also delete this branch from the DB
// So add this to the `opStack` and mark the keyhash to be deleted
if (this._opts.useNodePruning) {
opStack.push({
type: 'del',
key: branchNode,
});
}
// look up node

@@ -528,3 +586,3 @@ const foundNode = await this.lookupNode(branchNode);

if (remove) {
if (this._opts.deleteFromDB) {
if (this._opts.useNodePruning) {
opStack.push({

@@ -564,3 +622,3 @@ type: 'del',

if (op.type === 'put') {
if ((0, util_1.isFalsy)(op.value)) {
if (op.value === null || op.value === undefined) {
throw new Error('Invalid batch db operation');

@@ -588,3 +646,3 @@ }

});
if (this.root() === this.EMPTY_TRIE_ROOT && (0, util_1.isTruthy)(opStack[0])) {
if (this.root() === this.EMPTY_TRIE_ROOT && opStack[0] !== undefined && opStack[0] !== null) {
this.root(opStack[0].key);

@@ -645,2 +703,52 @@ }

}
// This method verifies if all keys in the trie (except the root) are reachable
// If one of the key is not reachable, then that key could be deleted from the DB
// (i.e. the Trie is not correctly pruned)
// If this method returns `true`, the Trie is correctly pruned and all keys are reachable
async verifyPrunedIntegrity() {
const root = this.root().toString('hex');
for (const dbkey of this._db.db._database.keys()) {
if (dbkey === root) {
// The root key can never be found from the trie, otherwise this would
// convert the tree from a directed acyclic graph to a directed cycling graph
continue;
}
// Track if key is found
let found = false;
try {
await this.walkTrie(this.root(), async function (nodeRef, node, key, controller) {
if (found) {
// Abort all other children checks
return;
}
if (node instanceof node_1.BranchNode) {
for (const item of node._branches) {
// If one of the branches matches the key, then it is found
if (item && item.toString('hex') === dbkey) {
found = true;
return;
}
}
// Check all children of the branch
controller.allChildren(node, key);
}
if (node instanceof node_1.ExtensionNode) {
// If the value of the ExtensionNode points to the dbkey, then it is found
if (node.value().toString('hex') === dbkey) {
found = true;
return;
}
controller.allChildren(node, key);
}
});
}
catch {
return false;
}
if (!found) {
return false;
}
}
return true;
}
/**

@@ -664,3 +772,3 @@ * The `data` event is given an `Object` that has two properties; the `key` and the `value`. Both should be Buffers.

if (includeCheckpoints && this.hasCheckpoints()) {
trie._db.checkpoints = [...this._db.checkpoints];
trie._db.setCheckpoints(this._db.checkpoints);
}

@@ -667,0 +775,0 @@ return trie;

12

dist/types.d.ts

@@ -20,7 +20,2 @@ /// <reference types="node" />

/**
* Delete nodes from DB on delete operations (disallows switching to an older state root)
* Default: `false`
*/
deleteFromDB?: boolean;
/**
* Create as a secure Trie where the keys are automatically hashed using the

@@ -46,8 +41,13 @@ * **keccak256** hash function or alternatively the custom hash function provided.

useRootPersistence?: boolean;
/**
* Flag to prune the trie. When set to `true`, each time a value is overridden,
* unreachable nodes will be pruned (deleted) from the trie
*/
useNodePruning?: boolean;
}
export declare type TrieOptsWithDefaults = TrieOpts & {
deleteFromDB: boolean;
useKeyHashing: boolean;
useKeyHashingFunction: HashKeysFunction;
useRootPersistence: boolean;
useNodePruning: boolean;
};

@@ -54,0 +54,0 @@ export declare type BatchDBOp = PutBatch | DelBatch;

6

package.json
{
"name": "@ethereumjs/trie",
"version": "5.0.0-rc.1",
"version": "5.0.0",
"description": "This is an implementation of the modified merkle patricia tree as specified in Ethereum's yellow paper.",

@@ -48,4 +48,4 @@ "keywords": [

"dependencies": {
"@ethereumjs/rlp": "4.0.0-rc.1",
"@ethereumjs/util": "8.0.0-rc.1",
"@ethereumjs/rlp": "^4.0.0",
"@ethereumjs/util": "^8.0.0",
"ethereum-cryptography": "^1.1.2",

@@ -52,0 +52,0 @@ "readable-stream": "^3.6.0"

15

src/db/checkpoint.ts

@@ -21,2 +21,17 @@ import type { BatchDBOp, Checkpoint, DB } from '../types'

/**
* Flush the checkpoints and use the given checkpoints instead.
* @param {Checkpoint[]} checkpoints
*/
setCheckpoints(checkpoints: Checkpoint[]) {
this.checkpoints = []
for (let i = 0; i < checkpoints.length; i++) {
this.checkpoints.push({
root: checkpoints[i].root,
keyValueMap: new Map(checkpoints[i].keyValueMap),
})
}
}
/**
* Is the DB during a checkpoint phase?

@@ -23,0 +38,0 @@ */

157

src/trie/trie.ts

@@ -1,2 +0,2 @@

import { RLP_EMPTY_STRING, isFalsy, isTruthy } from '@ethereumjs/util'
import { RLP_EMPTY_STRING } from '@ethereumjs/util'
import { keccak256 } from 'ethereum-cryptography/keccak'

@@ -16,2 +16,3 @@

BatchDBOp,
DB,
EmbeddedNode,

@@ -40,6 +41,6 @@ FoundNodeFunction,

private readonly _opts: TrieOptsWithDefaults = {
deleteFromDB: false,
useKeyHashing: false,
useKeyHashingFunction: keccak256,
useRootPersistence: false,
useNodePruning: false,
}

@@ -51,3 +52,3 @@

/** The backend DB */
protected _db: CheckpointDB
protected _db!: CheckpointDB
protected _hashLen: number

@@ -66,7 +67,4 @@ protected _lock = new Lock()

if (opts?.db instanceof CheckpointDB) {
throw new Error('Cannot pass in an instance of CheckpointDB')
}
this.database(opts?.db ?? new MapDB())
this._db = new CheckpointDB(opts?.db ?? new MapDB())
this.EMPTY_TRIE_ROOT = this.hash(RLP_EMPTY_STRING)

@@ -101,8 +99,20 @@ this._hashLen = this.EMPTY_TRIE_ROOT.length

database(db?: DB) {
if (db !== undefined) {
if (db instanceof CheckpointDB) {
throw new Error('Cannot pass in an instance of CheckpointDB')
}
this._db = new CheckpointDB(db)
}
return this._db
}
/**
* Gets and/or Sets the current root of the `trie`
*/
root(value?: Buffer): Buffer {
root(value?: Buffer | null): Buffer {
if (value !== undefined) {
if (isFalsy(value)) {
if (value === null) {
value = this.EMPTY_TRIE_ROOT

@@ -145,3 +155,3 @@ }

const { node, remaining } = await this.findPath(this.appliedKey(key), throwIfMissing)
let value = null
let value: Buffer | null = null
if (node && remaining.length === 0) {

@@ -166,3 +176,3 @@ value = node.value()

// If value is empty, delete
if (isFalsy(value) || value.toString() === '') {
if (value === null || value.length === 0) {
return await this.del(key)

@@ -179,4 +189,27 @@ }

const { remaining, stack } = await this.findPath(appliedKey)
let ops: BatchDBOp[] = []
if (this._opts.useNodePruning) {
const val = await this.get(key)
// Only delete keys if it either does not exist, or if it gets updated
// (The update will update the hash of the node, thus we can delete the original leaf node)
if (val === null || !val.equals(value)) {
// All items of the stack are going to change.
// (This is the path from the root node to wherever it needs to insert nodes)
// The items change, because the leaf value is updated, thus all keyhashes in the
// stack should be updated as well, so that it points to the right key/value pairs of the path
const deleteHashes = stack.map((e) => this.hash(e.serialize()))
ops = deleteHashes.map((e) => {
return {
type: 'del',
key: e,
}
})
}
}
// then update
await this._updateNode(appliedKey, value, remaining, stack)
if (this._opts.useNodePruning) {
// Only after updating the node we can delete the keyhashes
await this._db.batch(ops)
}
}

@@ -197,5 +230,23 @@ await this.persistRoot()

const { node, stack } = await this.findPath(appliedKey)
let ops: BatchDBOp[] = []
// Only delete if the `key` currently has any value
if (this._opts.useNodePruning && node !== null) {
const deleteHashes = stack.map((e) => this.hash(e.serialize()))
// Just as with `put`, the stack items all will have their keyhashes updated
// So after deleting the node, one can safely delete these from the DB
ops = deleteHashes.map((e) => {
return {
type: 'del',
key: e,
}
})
}
if (node) {
await this._deleteNode(appliedKey, stack)
}
if (this._opts.useNodePruning) {
// Only after deleting the node it is possible to delete the keyhashes
await this._db.batch(ops)
}
await this.persistRoot()

@@ -438,5 +489,5 @@ this._lock.release()

// branchNode is the node ON the branch node not THE branch node
if (isFalsy(parentNode) || parentNode instanceof BranchNode) {
if (parentNode === null || parentNode === undefined || parentNode instanceof BranchNode) {
// branch->?
if (isTruthy(parentNode)) {
if (parentNode !== null && parentNode !== undefined) {
stack.push(parentNode)

@@ -473,5 +524,5 @@ }

const branchNodeKey = branchNode.key()
// branch node is an leaf or extension and parent node is an exstention
// branch node is an leaf or extension and parent node is an extension
// add two keys together
// dont push the parent node
// don't push the parent node
branchNodeKey.unshift(branchKey)

@@ -489,4 +540,4 @@ key = key.concat(branchNodeKey)

let lastNode = stack.pop() as TrieNode
if (isFalsy(lastNode)) throw new Error('missing last node')
let lastNode = stack.pop()
if (lastNode === undefined) throw new Error('missing last node')
let parentNode = stack.pop()

@@ -530,2 +581,15 @@ const opStack: BatchDBOp[] = []

// Special case where one needs to delete an extra node:
// In this case, after updating the branch, the branch node has just one branch left
// However, this violates the trie spec; this should be converted in either an ExtensionNode
// Or a LeafNode
// Since this branch is deleted, one can thus also delete this branch from the DB
// So add this to the `opStack` and mark the keyhash to be deleted
if (this._opts.useNodePruning) {
opStack.push({
type: 'del',
key: branchNode as Buffer,
})
}
// look up node

@@ -612,3 +676,3 @@ const foundNode = await this.lookupNode(branchNode)

if (remove) {
if (this._opts.deleteFromDB) {
if (this._opts.useNodePruning) {
opStack.push({

@@ -650,3 +714,3 @@ type: 'del',

if (op.type === 'put') {
if (isFalsy(op.value)) {
if (op.value === null || op.value === undefined) {
throw new Error('Invalid batch db operation')

@@ -675,3 +739,3 @@ }

if (this.root() === this.EMPTY_TRIE_ROOT && isTruthy(opStack[0])) {
if (this.root() === this.EMPTY_TRIE_ROOT && opStack[0] !== undefined && opStack[0] !== null) {
this.root(opStack[0].key)

@@ -749,2 +813,53 @@ }

// This method verifies if all keys in the trie (except the root) are reachable
// If one of the key is not reachable, then that key could be deleted from the DB
// (i.e. the Trie is not correctly pruned)
// If this method returns `true`, the Trie is correctly pruned and all keys are reachable
async verifyPrunedIntegrity(): Promise<boolean> {
const root = this.root().toString('hex')
for (const dbkey of (<any>this)._db.db._database.keys()) {
if (dbkey === root) {
// The root key can never be found from the trie, otherwise this would
// convert the tree from a directed acyclic graph to a directed cycling graph
continue
}
// Track if key is found
let found = false
try {
await this.walkTrie(this.root(), async function (nodeRef, node, key, controller) {
if (found) {
// Abort all other children checks
return
}
if (node instanceof BranchNode) {
for (const item of node._branches) {
// If one of the branches matches the key, then it is found
if (item && item.toString('hex') === dbkey) {
found = true
return
}
}
// Check all children of the branch
controller.allChildren(node, key)
}
if (node instanceof ExtensionNode) {
// If the value of the ExtensionNode points to the dbkey, then it is found
if (node.value().toString('hex') === dbkey) {
found = true
return
}
controller.allChildren(node, key)
}
})
} catch {
return false
}
if (!found) {
return false
}
}
return true
}
/**

@@ -769,3 +884,3 @@ * The `data` event is given an `Object` that has two properties; the `key` and the `value`. Both should be Buffers.

if (includeCheckpoints && this.hasCheckpoints()) {
trie._db.checkpoints = [...this._db.checkpoints]
trie._db.setCheckpoints(this._db.checkpoints)
}

@@ -772,0 +887,0 @@ return trie

14

src/types.ts

@@ -35,8 +35,2 @@ import type { BranchNode, ExtensionNode, LeafNode } from './trie'

/**
* Delete nodes from DB on delete operations (disallows switching to an older state root)
* Default: `false`
*/
deleteFromDB?: boolean
/**
* Create as a secure Trie where the keys are automatically hashed using the

@@ -64,9 +58,15 @@ * **keccak256** hash function or alternatively the custom hash function provided.

useRootPersistence?: boolean
/**
* Flag to prune the trie. When set to `true`, each time a value is overridden,
* unreachable nodes will be pruned (deleted) from the trie
*/
useNodePruning?: boolean
}
export type TrieOptsWithDefaults = TrieOpts & {
deleteFromDB: boolean
useKeyHashing: boolean
useKeyHashingFunction: HashKeysFunction
useRootPersistence: boolean
useNodePruning: boolean
}

@@ -73,0 +73,0 @@ 

dist/db/checkpoint.d.ts.map

Sorry, the diff of this file is not supported yet

dist/db/checkpoint.js.map

Sorry, the diff of this file is not supported yet

dist/trie/trie.d.ts.map

Sorry, the diff of this file is not supported yet

dist/trie/trie.js.map

Sorry, the diff of this file is not supported yet

dist/types.d.ts.map

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc