bug: TrieImpl.insert() is not idempotent for duplicate key-value pairs

[vividctrlalt]

Summary

TrieImpl.insert() violates the Merkle Trie invariant: the same dataset should always produce the same root hash, regardless of insertion order. When a duplicate key-value pair is inserted (same key, same value), the node is unconditionally marked as dirty, which invalidates the internal hash cache and causes the final root hash to become insertion-order-dependent.

Root Cause

In TrieImpl.java, the kvNodeSetValueOrNode() method (L873-878) unconditionally sets dirty = true without checking whether the new value equals the existing value:

public Node kvNodeSetValueOrNode(Object valueOrNode) {
    parse();
    assert getType() != NodeType.BranchNode;
    children[1] = valueOrNode;    // overwrites even if same value
    dirty = true;                  // always marks dirty
    return this;
}

This is triggered from insert() (L188-189) when commonPrefix.equals(k):

} else if (commonPrefix.equals(k)) {
    return n.kvNodeSetValueOrNode(nodeOrValue);  // no same-value check
}

Reproduction

The existing TrieTest.testOrder() (currently @Ignore) demonstrates the issue:

1. Insert keys 1-99, then re-insert key 10 with the same value
2. Shuffle the insertion order and rebuild
3. Root hashes differ ~3% of the time depending on shuffle order

Impact

Current: None. The allowAccountStateRoot chain parameter (proposal 25) has not been enabled on mainnet. AccountStateCallBack checks allowAccountStateRoot() before using TrieImpl, so this code path is never executed.

Future: Consensus-level risk. If proposal 25 is approved, AccountStateCallBack will use TrieImpl to compute per-block account state root hashes stored in block headers. Different nodes could compute different root hashes for the same block if duplicate trie.put(address, state) calls occur, leading to BadBlockException and potential chain forks.

Suggested Fix

Add a same-value check in kvNodeSetValueOrNode() to short-circuit when the value hasn't changed:

public Node kvNodeSetValueOrNode(Object valueOrNode) {
    parse();
    assert getType() != NodeType.BranchNode;
    if (valueOrNode instanceof byte[] && children[1] instanceof byte[]
        && Arrays.equals((byte[]) valueOrNode, (byte[]) children[1])) {
        return this;  // no change, skip dirty marking
    }
    children[1] = valueOrNode;
    dirty = true;
    return this;
}

Then remove the @Ignore on TrieTest.testOrder() to verify the fix.

Related

• PR test(framework): add dual DB engine coverage with flaky test fixes #6586 — @Ignore annotation and root cause analysis in TrieTest.java
• AccountStateCallBack.java — production consumer of TrieImpl

[halibobo1205]

+1, great improvement.

• Fixes flaky tests at the root instead of relying on retries
• Helps avoid potential production issues going forward

[lxcmyf]

Right now the fix only skips marking dirty when both sides are byte[] and their contents are equal, which matches the case in this issue. But does this path always deal with plain byte[], or are there cases where the same trie content could show up in another form? If so, it might be good to define the rule a bit more broadly: if a write does not actually change trie content, it probably should not mark the node dirty.

[lvs0075]

From the leaf node to the root node, all nodes along the path (up to 64) are unconditionally marked as ‘dirty’. This is a confirmed bug (which only affects performance); however, the root hash value should be independent of the insertion order.
The calculation logic of encode():

private byte[] encode(final int depth, boolean forceHash) {
      if (!dirty) {
          return hash != null ? Hash.encodeElement(hash) : rlp;  // Use the cache
      } else {
          // Recompute ret from children[]
          byte[] value = kvNodeGetValue();
          ret = encodeList(
              Hash.encodeElement(kvNodeGetKey().toPacked()),
              Hash.encodeElement(value == null ? EMPTY_BYTE_ARRAY : value)  // ← Compute from content
          );
          // ...
          hash = Hash.sha3(ret);   // ← SHA3 is deterministic: if the content remains unchanged, the hash remains unchanged
          addHash(hash, ret);
          return Hash.encodeElement(hash);
      }
  }

Insert the same value repeatedly and then encode:

• The content of children[1] remains unchanged (still the same byte array content)
• The result of ret is exactly the same as before
• Hash.sha3(ret) produces exactly the same hash

SHA3 is content-addressable and is independent of how many times this node has been marked as dirty.

testOrder() instability issue

Root cause: the sub-case 2a bug is always triggered in trie1, but only ~93% of the time in trie2.

trie1 always triggers the bug

Keys 0–99 are inserted in order, then key 10 is inserted a 101st time. By the time of the second insert, the full MPT is already built — key 10's leaf has been split down to a remaining key of [] (empty). Re-inserting key 10 then hits the bug:

• getCommonPrefix([], []) = empty → commonPrefix.isEmpty() = true → sub-case 2a fires
• BranchNode{terminal: value} replaces KVNode([], value) → different RLP encoding → rootHash1 is corrupted

trie2 avoids the bug ~6.7% of the time

The 101-element list (containing 10 twice) is shuffled randomly before building trie2. If the second occurrence of 10 in the shuffled order appears before any other key that shares a path prefix with key 10, then at the moment of the second insert:

• The trie has not yet split key 10's leaf to an empty remaining key
• Key 10's node still has a non-empty remaining key → commonPrefix is non-empty → sub-case 2b fires correctly → bug not triggered
• rootHash2 = the true, correct hash

At this point: rootHash1 (corrupted) ≠ rootHash2 (correct) → assertArrayEquals fails

The probability of trie2 avoiding the bug is approximately 1/15 ≈ 6.7% per run, making the test non-deterministically flaky.

Fix

Swap the branch-check order in insert() — check commonPrefix.equals(k) (sub-case 2b) before commonPrefix.isEmpty() (sub-case 2a):

// Buggy (current):
if (commonPrefix.isEmpty()) {         // incorrectly intercepts the k=[] case
    // sub-case 2a: create BranchNode
} else if (commonPrefix.equals(k)) {
    // sub-case 2b: update value in place
}

// Fixed:
if (commonPrefix.equals(k)) {         // full match handled first, including k=[]
    // sub-case 2b: update value in place
} else if (commonPrefix.isEmpty()) {
    // sub-case 2a: create BranchNode
}