Support for RFC6962 encoding Audit Paths for Binary Merkle Trees

[OR13]

https://datatracker.ietf.org/doc/html/rfc6962

The following information needs to be encoded:

A. hash algorithm ( could reuse existing entries) B. path a set of tuples of the form (direction: bit, hash: bytes), with "left" 0, and "right" 1 and hash.length determined by (A)... potentially storing the direction part first, and then hashes second (directions: bitstring, hashes: bytes)

Then to verify a membership proof:

verify(root: a multihash, member: bytes_to_be_hashed, proof: audit_path_bytes) => boolean

The problem is how to encode the audit path for a binary merkle tree efficiently.

Someone has to have solved this already right?

I am looking for a "standard" binary encoding of a merkle tree audit path.

[OR13]

Here is some naive code which works for proofs of length less than 255.

// proof looks like:
// {
//   left: <Buffer 04 3a...>
// },
// {
//   left: <Buffer 34 2c ...>
// },
// {
//   right: <Buffer b5 e2 ...>
// },
// {
//   right: <Buffer 8c 3e ...>
// },
// {
//   left: <Buffer 2e b4 ...>
// }
// ]
const encodeProof = (proof: any) => {
  // this is probably not correct.
  const proofLengthBytes = varint.encode(proof.length);
  const prefix = Buffer.concat([
    Buffer.from(proofLengthBytes),
    Buffer.from([0x01]), // unsure how to know this value
  ]);
  const bitstring = new Bitstring({ length: proof.length });
  let proofs = Buffer.from('');
  proof.forEach((p: any, i: number) => {
    if (p.left) {
      bitstring.set(i, false);
      proofs = Buffer.concat([proofs, p.left]);
    }
    if (p.right) {
      bitstring.set(i, true);
      proofs = Buffer.concat([proofs, p.right]);
    }
  });
  return Buffer.concat([prefix, bitstring.bits, proofs]);
};

const decodeProof = (encodedProof: Buffer) => {
  const prefix = encodedProof.slice(0, 2); // unsure how to know this end value
  const proofLength = varint.decode(prefix);
  // attempting to read a bitstring of length encoded by a varint.
  const directions = encodedProof.slice(2, 2 + Math.ceil(proofLength / 8));
  // the rest is the proofs, which will be a multiple of the hash length * number of hashes
  const proofs = encodedProof.slice(2 + Math.ceil(proofLength / 8));
  const bitstring = new Bitstring({ length: proofLength });
  bitstring.bits = new Uint8Array(directions);
  const auditPath = [];
  for (let i = 0; i < bitstring.length; i++) {
    const sibling: any = {
      // exploiting known length of merkle root multihashes..
      [bitstring.get(i) ? 'right' : 'left']: proofs.slice(i * 32, i * 32 + 32),
    };
    auditPath.push(sibling);
  }
  return auditPath;
};

[Stebalien]

This should probably be discussed on discuss.ipfs.io, you're not going to get much traction here.