Curve Trees

An implementation of the ideas behind Curve Trees, albeit not the exact protocol.

This library is premised on BP+, not BP, which offers a proof for an identical arithmetic circuit relationship as BPs. Despite this, Curve Trees actually expects a distinct relationship supporting vector commitments. The authors notes can be found here.

The BP+ library utilized implements its own vector commitment scheme pending formalization of the author's work.

This work uses the BP+ library's provided ECC gadgets, which include a DLog PoK which is roughly 33% more efficient than the incomplete addition series described in the Curve Trees paper.

Status

• An in-memory tree is implemented. A production usage would require:

  1. Moving the paths to the DB.
  2. A more-efficient in-memory algorithm. The current one grows by power of two, and doesn't archive no longer needed left hand nodes.
  3. A pop algorithm, so reorgs can be successfully handled.

• This library uses asserts instead of Result. It also has extraneous asserts which should be moved to debug.

• Wallets likely want to be able to prune irrelevant sub-trees/pathing data.