Flat instructions encoding

[s1na]

Currently instructions are RLP-encoded like other data structures. That's not strictly necessary as after reading each opcode (1 byte) we'd know how many bytes of data to read for that opcode. So it could be a simple flat encoding of the opcodes and their operands without any metadata. This would eliminate the need for decoding them first on the verifier's side. This is also what @cdetrio is doing in turbo-mpas.

I could start working on a PR if you think this makes sense.

[s1na]

Something that could complicate this flat encoding is the EXTENSION opcode. Its operand doesn't have a pre-determined length and might need an additional byte for the length of the extension key.

[s1na]

Implemented this in the Typescript version: ethereumjs/merkle-patricia-tree@cb63d56

Each opcode takes one byte, values for Add and Branch each take one byte. For Extension we first encode the length of the nibbles (one byte is sufficient), and then each nibble as one byte. As an example, the instructions below are encoded to 0204050304030303030006:

const instructions = [                                                                                                                                                                             
  { kind: Opcode.Leaf },                                                                                                                                                                           
  { kind: Opcode.Add, value: 5 },                                                                                                                                                                  
  { kind: Opcode.Extension, value: [3, 3, 3, 3] },                                                                                                                                                 
  { kind: Opcode.Branch, value: 6 }                                                            
]