Implementation of Merkle Tree

[Daniel-K-Ivanov]

High-level spec link

Example: LimeChain Merkle tree: github & github2

Description:

• Get all validators from the config and sort them based on the address. The goal is to have the same order every time and everywhere when we are building the Merkle tree (the order of the members from the config should not affect the Merkle tree nodes logic). In case a new validator is added we have to get the current data from the DB and rebuild the tree.
• Create Merkle tree per supported native asset and the related network (to avoid collision of asset addresses on different networks) on validator’s start/restart:
  • Get the supported native assets from the config.
  • Compare the native assets from the config with the records in the DB, if a new asset was added after restarting the validator - insert a new DB row.
  • Add each validator’s data as a leaf. To create the nodes - hash() of:
    • Validator’s address.
    • Network ID.
    • Native asset address.
    • Set the Fee to collect: get the current amount from the DB and add the new fee from the burn TX.
• Signatures: Validators should sign the Merkle tree’s root, once it is built.
• Re-build the Merkle tree on every transfer and update with the new fee.

On initialization:

• Fee to collect = 0
• All nodes hashes including the Root hash.

Automation processes for:

• ❓ (optional - can be implemented later) Adding a new validator - will start with the same records as in the initial.
  • all native assets from the config (validator's address, Fee = 0, etc).
  • Get the current progress from the DB and re-build the Merkle tree. We aim to keep the progress and do not break the tree logic.
• Adding a new asset - will trigger a new record in the validator’s DB.
  • Check on after validator’s restart for a new native asset in the config and compare it with the current records in the DB

Subtasks:

• [ ] Algorithm implementation
• [ ] Integration in the current validators logic
• [ ] Use the new DB to store the data
• [ ] Get validators signatures
• [ ] The logic on initialization
• [ ] The logic for a new validator
• [ ] The logic for a new asset
• [ ] unit tests, docks, PR reviews & fixes