Full deletion from trie

[VladChernenko]

Hi folk 👋

DISCLAIMER: Before opening issue - already google it and asked GPT, but no answer was founded, so decided to ask devs directly

Have a question regarding the trie data structure: What is the procedure of full deletion the old states ?

1. For example, imagine the code:

import { Trie } from "@ethereumjs/trie";
import { bufferToHex, toBuffer } from "@ethereumjs/util";
import { LevelDB } from "./LevelDB.js";
import { Level } from "level";


class PatriciaTreeWithPersistence {
  constructor(dbPath) {

    this.db = new LevelDB(new Level("STORAGE"));

    this.trie = new Trie({db: this.db});

}

  async insert(key, value) {

    const keyBuffer = toBuffer(key);
    const valueBuffer = toBuffer(value);

    await this.trie.put(keyBuffer, valueBuffer);

  }

    async get(key) {
        
        const keyBuffer = toBuffer(key);
        
        const valueBuffer = await this.trie.get(keyBuffer);

        if (!valueBuffer) {
            return null;
        }

        return valueBuffer.toString("hex");
    }

    async getStateRootHash() {
        const root = await this.trie.root();
        return bufferToHex(root);
    }

    async rollbackToState(stateRoot) {

        const rootBuffer = toBuffer(stateRoot);
        await this.trie.root(rootBuffer);
  
    }

}

const patriciaTree = new PatriciaTreeWithPersistence();


console.log("State root hash before inserting keys => ", await patriciaTree.getStateRootHash());

await patriciaTree.insert(
  "0xaaaaaa",
  "0xbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
);

console.log("State root hash after inserting 0xaaaaaa => ", await patriciaTree.getStateRootHash());

await patriciaTree.insert(
  "0xcccccc",
  "0xabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
);

console.log("State root hash after inserting 0xcccccc => ", await patriciaTree.getStateRootHash());

await patriciaTree.insert(
  "0xcccccd",
  "0xaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
);

console.log("State root hash after insert 0xcccccd => ", await patriciaTree.getStateRootHash());

await patriciaTree.insert(
    "0xcccccd",
    "0xccbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
);

console.log("State root hash after update 0xcccccd => ", await patriciaTree.getStateRootHash());

console.log('Value => ',await patriciaTree.get("0xaaaaaa"))
console.log('Value => ',await patriciaTree.get("0xcccccc"))
console.log('Value => ',await patriciaTree.get("0xcccccd"))

2. The output will be

State root hash before inserting keys =>  0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421
State root hash after inserting 0xaaaaaa =>  0x1b57f1205d93a8569badc609eb5f591e8f916c642431795869cae39ed8abaac8
State root hash after inserting 0xcccccc =>  0x2ea8c6d75a907d9739c7b4d60c49648850cf8ff54bb8517eda3cf6549674a110
State root hash after insert 0xcccccd =>  0x35c1813fe71a6d4d8d37ebeed4d1b5ba8b158d026e6f2e4304cc41aa82a598bf
State root hash after update 0xcccccd =>  0x6e6ff559b204e45a3d15538ddb5b5345091632b74a36d6c3206e69659b619003
Value =>  bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
Value =>  abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
Value =>  0ccbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb

3. Now imagine I want to clean old, non-used storage (for example, to get rid of old state of 0xcccccd account). How to do it ?

1. I don't use useNodePruning as pre-set value because I need rollback functionality, at least for the last N states
2. I assume it's possible to make pruning later, once I'll need it
3. I want to delete let's say super-old states to cleanup the disk
4. From proposed example above, I don't need the state with root 0x35c1813f, I need only the last one with root 0x6e6ff559

How to do it ? Any suggestions? Thank you in advance, hope we'll resolve it!

P.S: Code snippets would be even better from you to help. Thanks 🤝

P.P.S: I also asked because:

1. Via del() method the trie just move to the new root with lack of access to deleted key
2. But it's still in db and consumes disk space
3. I know that some ETH clients (geth for example) runs prunning in offline mode (source), so seems no useNodePrunning was pre-set in Geth clients, so I hope the same functionality should be available here, for JS implementation to clean up old state post-factum

[VladChernenko]

Decided to add clarification (image), maybe will be helpful:

1. On this image, I want to get rid of old values of NodeC, NodeD, NodeE
2. But do it later, not immediately. So, I supposed for this useNodePruning must be still false

[VladChernenko]

Decided to add 2nd clarification (xD)

After a while, noticed this issue(rather comment) by @jochem-brouwer here

This is also from trie test dir. So if we have:

const { Trie, LevelDB } = require('@ethereumjs/trie')
const { Level } = require('level')

const trie = new Trie({ db: new LevelDB(new Level('MY_TRIE_DB_LOCATION')) })

async function test() {
  await trie.put(Buffer.from('test'), Buffer.from('1'))
  await trie.put(Buffer.from('test'), Buffer.from('2'))
  await trie.put(Buffer.from('test'), Buffer.from('3'))
  await trie.put(Buffer.from('test'), Buffer.from('4'))
  await trie.put(Buffer.from('test'), Buffer.from('5'))
  await trie.put(Buffer.from('test'), Buffer.from('6'))

  // this logs 7 keys but I only want 1 key to be stored with the value 6
  console.log(await trie.db._leveldb.keys().all())
}

test()

How to delete states connected with 1,2,3 but have access to the current state(6) and some previous ones(for example, to have ability to rollback to state 5 and 4)?

[jochem-brouwer]

Hi Vlad, interesting issue! I would also advise to also join our discord if you have not yet: https://discord.gg/TNwARpR

Are you also using checkpoints (commit(), revert(), checkpoint())? Or going to use those?

[VladChernenko]

Hi Vlad, interesting issue! I would also advise to also join our discord if you have not yet: https://discord.gg/TNwARpR

Are you also using checkpoints (commit(), revert(), checkpoint())? Or going to use those?

Hello!

No, I don't use this functionality, although I was interested in it during source code research and debugging. I noticed that if I perform put() operations between checkpoint() and commit(), nothing will appear on the disk until commit() is called

However, I still don't understand how this can be used to solve my problem. Do you have a solution?