search

gballet / multiproof-rs

A rust implementation of Alexey Akhunov's multiproof algorithm
Apache License 2.0
32 stars 8 forks source link

Flat instructions encoding #18

Open s1na opened 4 years ago

s1na commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

Implemented this in the Typescript version: https://github.com/ethereumjs/merkle-patricia-tree/pull/101/commits/cb63d5643f3f17ae475ad1b7afc04064490ad183

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 }                                                            
]