StateService: broken findstates filtering logic

[AnnaShaleva]

Describe the bug
findstates RPC handler introduced in #638 seems to have a bug in the results filtering logic when the fourth argument (key to start the search from) is specified. The bug happens due to invalid MPTTrie.Find behaviour:

• First of all, we check whether from starts with the specified prefix - that's OK.
• After that, we seek for the node located at the specified prefix to start the traversal process from. The actual path to the start node is returned from Seek method. This path can be the same as the prefix passed to Seek, or it can also be longer than the prefix in case if the last node found by that prefix is an extension. And that's also OK.
• After that, we start the traversal process from this new path with an offset equals to the length of this path. Here's the place where the bug occurs. If the new path is longer than prefix, then we do not perform the comparison of path's extra bytes with from argument like it is done in step 1. We just start searching from the offset.

For example, we want to find all storage items with prefix abc starting from abcdef. Let's suppose that Extension node is located at the path ab and has the Key equal to cc. Then Seek with abc prefix will give us path=abcc and the start node equals the Extension's Next. After that we'll start the traversal process with abcc path, from abcdef and 4 offset. I.e. we'll traverse from the start node with the ef path and will probably find some suitable MPT nodes. That's not correct, because this algorithm doesn't take into account new abcc path which is less than the abcdef at the fourth byte (c < d). So we shouldn't return anything from that query.

To Reproduce
I found the described situation in the current testnet, so to reproduce this bug send findstates RPC call to the v3.0.3 testnet C# node with the following arguments:

• Stateroot of the 5-th block
• Hash of the GasToken contract
• FJI= prefix (1492 in hex)
• Start from the FJK0 (1492b4 in hex)

curl -d '{ "jsonrpc": "2.0", "id": 1, "method": "findstates", "params": ["0x56135b6bace2de89aee44b9e560905ec46e2400951234ec1bc98005efe4ed899", "0xd2a4cff31913016155e38e474a2c06d08be276cf", "FJI=", "FJK0"] }' http://seed1t4.neo.org:20332 | json_pp

The result is:

{
   "id" : 1,
   "result" : {
      "firstProof" : "Gfr///8UkrOcd6pg8ptXwXPO2Rfxf9MhpusIJAEBDwMfaO/ZijWNW8VCFuKvmwSANW/DXdLaUi+E3z7BRFZJuLIABAQEBAQEBAMe+jlFz2/5ZKl+ycxczvmS75mO9ssmFZef+WHov7XIHQQDiT6zHh/siCZ0c2bfBEymPmRNTiXSAKFIammjmnnBnJYDHlEWsB5o45j0CUUUwe7FPMt8AGe9fDi7soQ8AvnPwywDZpf5IXDMrUiHAxeVAUxH2T5GGnFZjnGRCocIuFINlygEBAQDsyA6/WuQyV98xH99kDVz3bhQHmUNBIQqJd0x0R/+TGwEKQEGDw8PDw8PA0QMdyvgzY/nn0gU1YrmMWg6QSjVwN4W+ZX+tnPg6aoxUgADIRuLqG6IDaprzffYO40G2P3mdM9kvOE1h4kpPMRcn3oDQBZhzeWqraNKhSHkyiBN7/f/nkvT2OjFrjdle37kuZAEBAQEBAQEBAQEBAQEBAQkAQEEAygI/cWsZIk1pGkjUi+Wo//b1yaPsr81iF9Yp5vlbVML8gADa6Pvesc8zjndbSiBpw81Qkmh8H5tq/oKEzoM8F/eq2QEBAQDkDItPZued0hTTNWIVf+MEowuUJE15ZfXTZQjHA0ZDXIDrejHIQAHCzuZPkYlWL9fkqvDH8scDNOTCdaQt0SiCY4EBANuF/aVQB5/ZEhDQZ0srrD6awer8u3KfgPt+IJtUPIfXwP9p++Nl9YcNjyIcbb0vVDdZ7ZU4QUpouFUGCYI+WgA5AQDQ+5OR1PWJv0wC3vBLRvlO1Q9Tpbsm0DIuSEviEMlsE8EBAQDUi73Hk+tF18JrEkbEeT3LAOBavJNE5Lu6XmVG04/C2AESgEnAgsDCQwHBwoKBgAPAgkLBQcMAQcDDA4NCQEHDwEHDw0DAgEKBg4LA5L5mtknpOeIfgNH3SgMaFIxE7nw3cN21/wq52nfdqj1DQILQQEhBwAA1VhfeRI=",
      "results" : [
         {
            "value" : "QQEhBwAA1VhfeRI=",
            "key" : "FJKznHeqYPKbV8FzztkX8X/TIabr"
         }
      ],
      "truncated" : false
   },
   "jsonrpc" : "2.0"
}

So you can see that the single storage item with key FJKznHeqYPKbV8FzztkX8X/TIabr (1492b39c77aa60f29b57c173ced917f17fd321a6eb in hex) was found. It has the requested 1492 prefix, but it shouldn't be included in the result, because we ask to start from the 1492b4 path and this item is located at the 1492b3... path.

Expected behavior
We should check the path returned after Seek against from argument.

You can see the way how this case is handled in the Go implementation: https://github.com/nspcc-dev/neo-go/blob/40dfca3edae9d99dd79f7884584a241fe382387c/pkg/core/mpt/trie.go#L549.

Platform:

• StateService, current master (dd81842).