trie.put fails with "Error: Stack underflow"

[TimDaub]

Code: https://github.com/attestate/kiwistand/blob/7060bd6573f8b966d40e6af07d18d6ac2cb4a926/src/store.mjs#L282-L319

You can find the message in the logs and the index. I'm using v5.0.4

[1] 2024-09-09T15:47:50.482Z @attestate/kiwistand Attempting to store message with index "66d065b901d62e385338b3bcf4e173f7a3ba9ea34bbd64cd2332bbbd51289c9350300b88" and message: "{"href":"https://longform.asmartbear.com/reputation/","signature":"0xd53711394867b8393a3c6c961ff8da2c4c88db97a047bce8c780f7436352d1e451aaa99c2af046f0f7878995ed04393937c215bac562def00879328bad26e2401c","timestamp":1724933561,"title":"Reputation isn’t as powerful as you imagine","type":"amplify"}"
[1] 2024-09-09T15:47:50.483Z @attestate/kiwistand trie.put failed with "Error: Stack underflow
[1]     at Trie._updateNode (/Users/timdaub/Projects/attestate/kiwistand/node_modules/@ethereumjs/trie/dist/trie/trie.js:325:19)
[1]     at Trie.put (/Users/timdaub/Projects/attestate/kiwistand/node_modules/@ethereumjs/trie/dist/trie/trie.js:158:24)
[1]     at process.processTicksAndRejections (node:internal/process/task_queues:95:5)
[1]     at async atomicPut (file:///Users/timdaub/Projects/attestate/kiwistand/src/store.mjs:283:5)
[1]     at async _add (file:///Users/timdaub/Projects/attestate/kiwistand/src/store.mjs:438:32)". Successfully rolled back constraint
[1] Message: put: Didn't add message to database
[1] Stack Trace: Error: trie.put failed with "Error: Stack underflow
[1]     at Trie._updateNode (/Users/timdaub/Projects/attestate/kiwistand/node_modules/@ethereumjs/trie/dist/trie/trie.js:325:19)
[1]     at Trie.put (/Users/timdaub/Projects/attestate/kiwistand/node_modules/@ethereumjs/trie/dist/trie/trie.js:158:24)
[1]     at process.processTicksAndRejections (node:internal/process/task_queues:95:5)
[1]     at async atomicPut (file:///Users/timdaub/Projects/attestate/kiwistand/src/store.mjs:283:5)
[1]     at async _add (file:///Users/timdaub/Projects/attestate/kiwistand/src/store.mjs:438:32)". Successfully rolled back constraint
[1]     at atomicPut (file:///Users/timdaub/Projects/attestate/kiwistand/src/store.mjs:318:11)
[1]     at process.processTicksAndRejections (node:internal/process/task_queues:95:5)
[1]     at async _add (file:///Users/timdaub/Projects/attestate/kiwistand/src/store.mjs:438:32)

It seems to be this line which is faulty: https://github.com/ethereumjs/ethereumjs-monorepo/blob/295e5a3caa69c226e8f8edfad4ea72a843bc0b4f/packages/trie/src/trie/trie.ts#L377

I went in my ethereumjs/trie/dist/trie/trie.js and added a console log of all the function's inputs

    async _updateNode(k, value, keyRemainder, stack) {
        const toSave = [];
        console.log(k, value, keyRemainder, stack);
        const lastNode = stack.pop();
        if (!lastNode) {
            throw new Error('Stack underflow');
        }

[1] <Buffer 66 d0 65 b9 01 d6 2e 38 53 38 b3 bc f4 e1 73 f7 a3 ba 9e a3 4b bd 64 cd 23 32 bb bd 51 28 9c 93 50 30 0b 88> <Buffer 79 01 29 7b 22 68 72 65 66 22 3a 22 68 74 74 70 73 3a 2f 2f 6c 6f 6e 67 66 6f 72 6d 2e 61 73 6d 61 72 74 62 65 61 72 2e 63 6f 6d 2f 72 65 70 75 74 61 ... 250 more bytes> [] []

this is what I get for the stack overflow throwing message

[gabrocheleau]

Hi Tim! Thanks for submitting the issue. It's going to be hard for us to prioritize troubleshooting an issue from an older release (we've been on v6 for quite some time, and are looking at v7 shortly). Would you be able to upgrade your dependencies to use the latest ethjs versions?

From reading the error messages, the issue seems to come from whatever is passed down to _updateNode. You are passing the key/value fields, but the keyRemained and stack are empty. Stack can't be empty in this context. I would recommend logging the stack upstream and seeing if that gives more clarity into the issue.

[TimDaub]

Pretty sure revert, checkpoint and commit are faulty. I removed the entire logic now from my code base and I haven't run into these issues anymore. I'm pretty sure that if I create a checkpoint and add a ton of data and then my program panics without commit then there are issues with this library

[holgerd77]

Hmm. We might want to add on the suite of test cases, that might be the most realistic way to catch that. 🤔

For trie itself we are not as good tested as for state manager (regarding the checkpointing logic).

[holgerd77]

(can you guys nevertheless move over to v6? Or do you need to keep v5 for now?)

[TimDaub]

We sadly don't have budget to move to v6 as of now. That code is mission critical and very costly to maintain because it is related to our set reconciliation algorithm. Not something I wanna mess with unless absolutely necessary, as it currently works, and since it is hard to get working in the first place. We run Kiwi News through self-funding etc., so we've been focusing as much as we can on making money to pay rent. I'm hopeful that we'll manage to upgrade some time in the future!