Status
IN PROGRESS
Stakeholders

Salakhiev Kamil Makoto Takemiya Egor Ivkov

Outcome
Due date
Owner

Salakhiev Kamil

Background

Shorthand

Discussion Participants: Makoto Takemiya , Salakhiev Kamil

Makoto Takemiya :

What I was thinking is that the leftmost leaf is a block (except for genesis) and every other leaf is a transaction. However, it is just transactions in the same block.

Do you still think this is too big?

Each block should have its own tree. Not all intermediary parts need to be stored probably.


Salakhiev Kamil:

Yes. We can keep only transactions and keep parent hash for every block. That way we can also prove that transaction belongs to the blockchain.

@mtakemiya btw, if in future we want to have light clients to Iroha (might be useful for wallets and bridges) then we should move transactions outside BlockPayload (or we can call it BlockHeader instead).
Then instead of transactions themselves we should store merkle hash of the tree composed of transactions from the block. This would allow us to keep block headers as light as possible.

Makoto Takemiya :

We should be storing the merkle root in the block header now in iroha 2, I mean, that is how the design is. For the block hash, the txs shouldn't be hashed, but only the merkle root.

Problem

To make fast validations of Blockchain state we should use some secure solution like Merkle Tree.

Solution

Block's Merkle Tree should have parents Block's hash as a leftmost leaf, and transactions hashes for other leafs. Blocks headers will store only hashes of Merkle Tree (Merkle root). 

Block

Decisions

Alternatives

Concerns

Assumptions

Risks

Additional Information

  • No labels

7 Comments

  1. Nikita Puzankov

    Makoto Takemiya , Salakhiev Kamil , Egor Ivkov  - please comment.

  2. Nikita Puzankov

    From Egor Ivkov:

    Parent's block hash is already in the header of the block, I am not sure if we should also add it to the Merkle Tree.

  3. Nikita Puzankov

    Question Makoto Takemiya:

    • Check status of clients in terms of Merkle proofs validation and how they can use it?

  4. Salakhiev Kamil

    > Block's Merkle Tree should have parents Block's hash as a leftmost leaf, and transactions hashes for other leafs. Blocks headers will store only hashes of Merkle Tree (Merkle root). 

    Our discussion about that long time ago:

    Me:

    @mtakemiya with such design of Merkle tree merkle proof messages can be too large.I think the goal for us of having tree is to be able to prove that certain transaction actually belongs to the blockchain. To do so we need to return merkle path containing all siblings of that transaction’s node up to the merkle root.  However, whenever we insert a new block, transaction Tx A from Block #N appears deeeper in tree by one level. Therefore, when we apply M blocks after Block #N, the length of merkle path for Tx A would become M, instead of log2(M) if we had more balanced binary Merkle Tree.

    or leaves in the tree are not transactions? if so, what are the leaves then?

    Makoto:

    What I was thinking is that the leftmost leaf is a block (except for genesis) and every other leaf is a tx. However, it is just txs in the same block. Do you still think this is too big?Each block should have its own tree imho. Not all intermediary parts need to be stored probably

    Me:

    Yes. We can keep only transactions and keep parent hash for every block. That way we can also prove that tx belongs to the blockchain.

    Makoto:

    That seems good to me

  5. Salakhiev Kamil

    > Problem

    > To make fast validations of Blockchain state we should use some secure solution like Merkle Tree.

    Makoto Takemiya What kind of validations you think we need from Merkle tree?

    1. Validate for transactions inclusion?
      If so, then it is enough to store only Merkle Root of block's transactions in block's header (as it is implemented now in Iroha2 and in Bitcoin).
      So if this is what we want, then we don't have to change anything.
    2. Validate state? (like in Ethereum) State validation is when we for example trying to quickly verify the such things:
      1. Is Alice's balance 1000 XOR?
      2. Does Alice account exist?
      3. Does Alice has permission to create new accounts?
        If this is what we want we need to redesign WSV to look like a single KeyValue store. But I thought we already had discussion that we won't do that.
    3. Other kind of validations? Please provide in comment

    1. Salakhiev Kamil

      Just to clarify, we don't need to choose one of the option. It is okay to support several kind of merkle trees (for example for both transactions inclusion validation and state validation)

      Also long time ago when we designed storage for Iroha2 I proposed to use Merkle tree for state validation. For details you can check this document: https://hackmd.io/@jVkDzwsSRbCqx36bM2T_dA/S18hry6EU

    2. Salakhiev Kamil

      Comment from community:

      ```And also how can I get the balance of the account  in a specific point of time? Is it posible?  For example Can a user know what was the balance of their account a month ago ?```


      With Merkle tree on top of State (WSV) such kind of queries will be possible