Write a fuzzer that generates the valid Merkel Patricia Proof

[0xsarvesh]

Write a fuzzer tool which can generate random positive proofs. This tool should accept the depth and sequence of node types.

Specification of valid proof:

1. A valid proof can end with leaf nodes as well as a branch node.
2. A valid proof can start with the branch as well extension node.
3. Maximum depth of a proof can be 64.
4. There can't be two consecutive extension node.

Input can be a string or Array of character like l, b, e where l represents leaf node, b represents branch node and e represents extension node.

The output of the fuzzer tool:

1. proof: string which represents rlp encoded valid Merkel Patricia proof.
2. value: string which represents value stored at the last node(either extension or leaf) in the proof.
3. path: string which represents a valid path from the root to leaf/branch node.
4. root: string which represents the root of the tree.

The detailed specification of Merkel Patricia tree: https://github.com/ethereum/wiki/wiki/Patricia-Tree#modified-merkle-patricia-trie-specification-also-merkle-patricia-tree

[benjaminbollen]

[Has been reflected in the description]

Improve following proposal:

1. first focus on correct proofs to be generated in this ticket.
2. input to the fuzzer should be a string from an alphabet (b, e, l) for branch, extention or leaf node respectively; the length of the extention nodes or leaf nodes can be random for now; similarly the number of garbage-children a branch node has, or its value can also be random

[benjaminbollen]

@pgev please write a summary of the work done as a handover so that tomorrow someone else on the team can continue this ticket.

Then please unassign and move it to top of backlog.

Thanks!

[pgev]

The implementation consists of 4 main components:

• Utils.ts: contains utility functions, like stringToNibbles, nibblesToBuffer, etc.
• Nodes.ts: contains base node class and branch, extension and leaf child-classes.
• FuzzyProofGenerator.ts: contains generate() function that is used to generate proofs.

Eslint (for typescript) with config files has been setup for the project.

Utility (Util.ts) functions are covered by unit tests.

FuzzyProofGenerator pattern validity functionality mostly covered by tests.

Documentation is mostly missing.

Next steps is to check why generated proof is not passing. One could modify merkle_patricia_proof.js and feed MerklePatriciaProof::verify function with generated proof data. Like this one:

contract('MerklePatriciaProof.verify()', () => {
  let merklePatriciaLib;

  describe('Test Cases for Account proof verification', async () => {
    before(async () => {
      merklePatriciaLib = await MerklePatriciaProof.deployed();
    });

    it('Should pass when all the parameters are valid', async () => {
      const proofData = FuzzyProofGenerator.generate('l', 'do', 'verb');

      const proofStatus = await merklePatriciaLib.verifyDebug.call(
        proofData.value,
        `0x${proofData.encodedPath.toString('hex')}`,
        `0x${proofData.rlpParentNodes.toString('hex')}`,
        proofData.root,
      );
      console.log(proofStatus);

      assert.equal(proofStatus.res_, true);
    });
  });
});

[pgev]

Implementation is ready in PR #729.

As currently, MerklePatriciaProof::verify library has a different handling for a value of ending node (branch and leaf), the implementation of the fuzzy proof generator is adjusted accordingly.

MerklePatriciaProof::verify library uses the following code snippet to check a value in a leaf node:

if(keccak256(abi.encodePacked(RLP.toData(currentNodeList[1]))) == value) {
    return true;
} else {
    return false;
}

RLP.toData function decodes a value before comparing with expected value.
However, a branch node uses the following code snippet:

if(keccak256(abi.encodePacked(RLP.toBytes(currentNodeList[16]))) == value) {
    return true;
} else {
    return false;
}

RLP.toBytes() function returns an underlying data without decoding.

Hence, FuzzyProofGenerator::generate() function returns proof, like:

const proofData = {
      value: (endingWithBranchNode ? rlpValuehash : valueHash),
      encodedPath: path,
      rlpParentNodes: rlp.encode(rlpParentNodesArray),
      root: nodes[0].hash(),
};

In case of a branch node, generator returns a rlpValueHash (instead of valueHash), as MerklePatriciaProof::verify() function compares against an expected value without decoding.