Optimized-Merkle-Proof

This contract is not finished yet. I am still adding further optimizations and comments. Below is a current snapshot of gas savings using Openzeppelin's MerkleProof Implementation as a baseline.

╭──────────────────────┬─────────────────┬──────┬────────┬──────┬─────────╮
│ MerkleProof contract ┆                 ┆      ┆        ┆      ┆         │
╞══════════════════════╪═════════════════╪══════╪════════╪══════╪═════════╡
│ Deployment Cost      ┆ Deployment Size ┆      ┆        ┆      ┆         │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ 105953               ┆ 561             ┆      ┆        ┆      ┆         │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ Function Name        ┆ min             ┆ avg  ┆ median ┆ max  ┆ # calls │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ verify               ┆ 1437            ┆ 1437 ┆ 1437   ┆ 1437 ┆ 1       │
╰──────────────────────┴─────────────────┴──────┴────────┴──────┴─────────╯
╭───────────────────────────────┬─────────────────┬─────┬────────┬─────┬─────────╮
│ OptimizedMerkleProof contract ┆                 ┆     ┆        ┆     ┆         │
╞═══════════════════════════════╪═════════════════╪═════╪════════╪═════╪═════════╡
│ Deployment Cost               ┆ Deployment Size ┆     ┆        ┆     ┆         │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ 66517                         ┆ 364             ┆     ┆        ┆     ┆         │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ Function Name                 ┆ min             ┆ avg ┆ median ┆ max ┆ # calls │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ verifyProof                   ┆ 893             ┆ 893 ┆ 893    ┆ 893 ┆ 1       │
╰───────────────────────────────┴─────────────────┴─────┴────────┴─────┴─────────╯