merkle-patricia-tree

  • Version 4.2.2
  • Published
  • 349 kB
  • 7 dependencies
  • MPL-2.0 license

Install

npm i merkle-patricia-tree
yarn add merkle-patricia-tree
pnpm add merkle-patricia-tree

Overview

This is an implementation of the modified merkle patricia tree as specified in Ethereum's yellow paper.

Index

Classes

class BaseTrie

class Trie {}
  • The basic trie interface, use with import { BaseTrie as Trie } from 'merkle-patricia-tree'. In Ethereum applications stick with the SecureTrie overlay. The API for the base and the secure interface are about the same.

constructor

constructor(db?: any, root?: any, deleteFromDB?: boolean);
  • test

    Parameter db

    A [levelup](https://github.com/Level/levelup) instance. By default (if the db is null or left undefined) creates an in-memory [memdown](https://github.com/Level/memdown) instance.

    Parameter root

    A Buffer for the root of a previously stored trie

    Parameter deleteFromDB

    Delete nodes from DB on delete operations (disallows switching to an older state root) (default: false)

property db

db: DB;
  • The backend DB

property EMPTY_TRIE_ROOT

EMPTY_TRIE_ROOT: any;
  • The root for an empty trie

property isCheckpoint

readonly isCheckpoint: boolean;
  • BaseTrie has no checkpointing so return false

property lock

protected lock: any;

    property root

    root: any;
    • Gets the current root of the trie

    method batch

    batch: (ops: BatchDBOp[]) => Promise<void>;
    • The given hash of operations (key additions or deletions) are executed on the trie (delete operations are only executed on DB with deleteFromDB set to true)

      Parameter ops

      Example 1

      const ops = [ { type: 'del', key: Buffer.from('father') } , { type: 'put', key: Buffer.from('name'), value: Buffer.from('Yuri Irsenovich Kim') } , { type: 'put', key: Buffer.from('dob'), value: Buffer.from('16 February 1941') } , { type: 'put', key: Buffer.from('spouse'), value: Buffer.from('Kim Young-sook') } , { type: 'put', key: Buffer.from('occupation'), value: Buffer.from('Clown') } ] await trie.batch(ops)

    method checkRoot

    checkRoot: (root: any) => Promise<boolean>;
    • Checks if a given root exists.

    method copy

    copy: () => Trie;
    • Creates a new trie backed by the same db.

    method createProof

    static createProof: (trie: Trie, key: any) => Promise<Proof>;
    • Creates a proof from a trie and key that can be verified using Trie.verifyProof.

      Parameter trie

      Parameter key

    method createReadStream

    createReadStream: () => ReadStream;
    • The data event is given an Object that has two properties; the key and the value. Both should be Buffers. Returns a [stream](https://nodejs.org/dist/latest-v12.x/docs/api/stream.html#stream_class_stream_readable) of the contents of the trie

    method del

    del: (key: any) => Promise<void>;
    • Deletes a value given a key from the trie (delete operations are only executed on DB with deleteFromDB set to true)

      Parameter key

      Returns

      A Promise that resolves once value is deleted.

    method findPath

    findPath: (key: any, throwIfMissing?: boolean) => Promise<Path>;
    • Tries to find a path to the node for the given key. It returns a stack of nodes to the closest node.

      Parameter key

      the search key

      Parameter throwIfMissing

      if true, throws if any nodes are missing. Used for verifying proofs. (default: false)

    method fromProof

    static fromProof: (proof: Proof, trie?: Trie) => Promise<Trie>;
    • Saves the nodes from a proof into the trie. If no trie is provided a new one wil be instantiated.

      Parameter proof

      Parameter trie

    method get

    get: (key: any, throwIfMissing?: boolean) => Promise<Buffer | null>;
    • Gets a value given a key

      Parameter key

      the key to search for

      Parameter throwIfMissing

      if true, throws if any nodes are missing. Used for verifying proofs. (default: false)

      Returns

      A Promise that resolves to Buffer if a value was found or null if no value was found.

    method lookupNode

    lookupNode: (node: Buffer | Buffer[]) => Promise<TrieNode | null>;
    • Retrieves a node from db by hash.

    method prove

    static prove: (trie: Trie, key: any) => Promise<Proof>;
    • prove has been renamed to Trie.createProof.

      Parameter trie

      Parameter key

      Deprecated

    method put

    put: (key: any, value: any) => Promise<void>;
    • Stores a given value at the given key or do a delete if value is empty (delete operations are only executed on DB with deleteFromDB set to true)

      Parameter key

      Parameter value

      Returns

      A Promise that resolves once value is stored.

    method setRoot

    setRoot: (value?: any) => void;
    • This method is deprecated. Please use Trie.root instead.

      Parameter value

      Deprecated

    method verifyProof

    static verifyProof: (
    rootHash: any,
    key: any,
    proof: Proof
    ) => Promise<Buffer | null>;
    • Verifies a proof.

      Parameter rootHash

      Parameter key

      Parameter proof

      Returns

      The value from the key, or null if valid proof of non-existence.

      Throws

      If proof is found to be invalid.

    method walkTrie

    walkTrie: (root: any, onFound: FoundNodeFunction) => Promise<void>;
    • Walks a trie until finished.

      Parameter root

      Parameter onFound

      callback to call when a node is found. This schedules new tasks. If no tasks are available, the Promise resolves.

      Returns

      Resolves when finished walking trie.

    class CheckpointTrie

    class CheckpointTrie extends BaseTrie {}

    constructor

    constructor(...args: any);

      property db

      db: CheckpointDB;

        property isCheckpoint

        readonly isCheckpoint: boolean;
        • Is the trie during a checkpoint phase?

        method checkpoint

        checkpoint: () => void;
        • Creates a checkpoint that can later be reverted to or committed. After this is called, all changes can be reverted until commit is called.

        method commit

        commit: () => Promise<void>;
        • Commits a checkpoint to disk, if current checkpoint is not nested. If nested, only sets the parent checkpoint as current checkpoint.

          Throws

          If not during a checkpoint phase

        method copy

        copy: (includeCheckpoints?: boolean) => CheckpointTrie;
        • Returns a copy of the underlying trie with the interface of CheckpointTrie.

          Parameter includeCheckpoints

          If true and during a checkpoint, the copy will contain the checkpointing metadata and will use the same scratch as underlying db.

        method revert

        revert: () => Promise<void>;
        • Reverts the trie to the state it was at when checkpoint was first called. If during a nested checkpoint, sets root to most recent checkpoint, and sets parent checkpoint as current.

        class SecureTrie

        class SecureTrie extends CheckpointTrie {}
        • You can create a secure Trie where the keys are automatically hashed using **keccak256** by using import { SecureTrie as Trie } from 'merkle-patricia-tree'. It has the same methods and constructor as Trie. SecureTrie Trie

          Modifiers

          • @public

        constructor

        constructor(...args: any);

          method copy

          copy: (includeCheckpoints?: boolean) => SecureTrie;
          • Returns a copy of the underlying trie with the interface of SecureTrie.

            Parameter includeCheckpoints

            If true and during a checkpoint, the copy will contain the checkpointing metadata and will use the same scratch as underlying db.

          method createProof

          static createProof: (trie: SecureTrie, key: any) => Promise<Proof>;

          method del

          del: (key: any) => Promise<void>;
          • Deletes a value given a key.

            Parameter key

          method get

          get: (key: any) => Promise<Buffer | null>;
          • Gets a value given a key

            Parameter key

            the key to search for

            Returns

            A Promise that resolves to Buffer if a value was found or null if no value was found.

          method prove

          static prove: (trie: SecureTrie, key: any) => Promise<Proof>;

          method put

          put: (key: any, val: any) => Promise<void>;
          • Stores a given value at the given key. For a falsey value, use the original key to avoid double hashing the key.

            Parameter key

            Parameter value

          method verifyProof

          static verifyProof: (
          rootHash: any,
          key: any,
          proof: Proof
          ) => Promise<Buffer | null>;
          • Verifies a proof.

            Parameter rootHash

            Parameter key

            Parameter proof

            Returns

            The value from the key.

            Throws

            If proof is found to be invalid.

          class WalkController

          class WalkController {}
          • WalkController is an interface to control how the trie is being traversed.

          property onNode

          readonly onNode: FoundNodeFunction;

            property taskExecutor

            readonly taskExecutor: PrioritizedTaskExecutor;

              property trie

              readonly trie: BaseTrie;

                method allChildren

                allChildren: (node: TrieNode, key?: Nibbles) => void;
                • Run all children of a node. Priority of these nodes are the key length of the children.

                  Parameter node

                  Node to get all children of and call onNode on.

                  Parameter key

                  The current key which would yield the node when trying to get this node with a get operation.

                method newWalk

                static newWalk: (
                onNode: FoundNodeFunction,
                trie: BaseTrie,
                root: any,
                poolSize?: number
                ) => Promise<void>;
                • Async function to create and start a new walk over a trie.

                  Parameter onNode

                  The `FoundNodeFunction to call if a node is found.

                  Parameter trie

                  The trie to walk on.

                  Parameter root

                  The root key to walk on.

                  Parameter poolSize

                  Task execution pool size to prevent OOM errors. Defaults to 500.

                method onlyBranchIndex

                onlyBranchIndex: (
                node: BranchNode,
                key: Nibbles | undefined,
                childIndex: number,
                priority?: number
                ) => void;
                • Push a branch of a certain BranchNode to the event queue.

                  Parameter node

                  The node to select a branch on. Should be a BranchNode.

                  Parameter key

                  The current key which leads to the corresponding node.

                  Parameter childIndex

                  The child index to add to the event queue.

                  Parameter priority

                  Optional priority of the event, defaults to the total key length.

                method pushNodeToQueue

                pushNodeToQueue: (nodeRef: any, key?: Nibbles, priority?: number) => void;
                • Push a node to the queue. If the queue has places left for tasks, the node is executed immediately, otherwise it is queued.

                  Parameter nodeRef

                  Push a node reference to the event queue. This reference is a 32-byte keccak hash of the value corresponding to the key.

                  Parameter key

                  The current key.

                  Parameter priority

                  Optional priority, defaults to key length

                Package Files (5)

                Dependencies (7)

                Dev Dependencies (17)

                Peer Dependencies (0)

                No peer dependencies.

                Badge

                To add a badge like this onejsDocs.io badgeto your package's README, use the codes available below.

                You may also use Shields.io to create a custom badge linking to https://www.jsdocs.io/package/merkle-patricia-tree.

                • Markdown
                  [![jsDocs.io](https://img.shields.io/badge/jsDocs.io-reference-blue)](https://www.jsdocs.io/package/merkle-patricia-tree)
                • HTML
                  <a href="https://www.jsdocs.io/package/merkle-patricia-tree"><img src="https://img.shields.io/badge/jsDocs.io-reference-blue" alt="jsDocs.io"></a>