github.com/cbergoon/merkletree

Proof generation and verification, mainly.

Locating content was a linear scan, making a single proof O(n) and a full set
O(n squared). WithLeafIndex, GetMerklePathByIndex and the AppendMerklePath forms
take that to a map probe, a direct index, and zero allocations respectively.

VerifyProof checks a proof against a root without the tree, which is what a light
client actually needs and what the package could not previously do.

WithParallelism spreads content hashing across goroutines, off by default because
it calls Content.CalculateHash concurrently.

VerifyTree and the binary decoder allocate substantially less.

The RFC 6962 construction is now checked against the Certificate Transparency
reference vectors, and the default construction against other implementations of
the same folklore. Both live in nested modules, so merkletree still has no
dependencies.

All additive; no existing API changed.

Adds serialization and an opt-in RFC 6962 construction, and fixes four
correctness bugs. The default construction is unchanged: roots, proofs and
indexes are byte for byte identical to v0.3.0.

New:

• Marshal/Unmarshal for binary, JSON and gob, closing #13. A tree is encoded
  as the seed it rebuilds from, and the recorded root makes decoding
  self-checking
• NewTreeWithOptions, with WithHasher, WithSortedSiblings and WithRFC6962
• WithRFC6962 prefixes leaf and interior hashes and splits odd node counts
  rather than duplicating them, closing the second preimage weakness and
  CVE-2012-2459 for trees that opt in
• Sorted() and RFC6962() accessors
• ErrNoContent, ErrNilContent and ErrContentNotFound sentinels

Fixed:

• VerifyTree recomputed from content but never checked the hashes recorded on
  the nodes, so an edited interior hash went unnoticed
• a nil entry in the content slice panicked instead of returning an error
• Node.sort was dead

Behaviour changes, same signatures:

• GetMerklePath returns ErrContentNotFound for content that is not in the
  tree, where it previously returned nil, nil, nil
• VerifyTree is stricter, and now rejects a tree whose stored node hashes have
  been edited

Modernized tooling and fixed four bugs. No API changes, and roots, proofs
and indexes are byte-identical to v0.2.0.

• go 1.21 is now the minimum (was 1.12)
• GitHub Actions replaces Travis
• VerifyContent now compares against the tree's merkle root
• sortAppend no longer writes into its callers' spare capacity
• RebuildTree no longer promotes the odd-count padding leaf to real content
• GetMerklePath tells left from right by node identity, not by hash

adds functionality to specify hash method used to calculate tree. tes…