Status | IN PROGRESS |
---|---|
Stakeholders | |
Outcome | |
Due date | |
Owner |
Background
Shorthand
Discussion Participants: Makoto Takemiya , Salakhiev Kamil
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.
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.
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
7 Comments
Nikita Puzankov
Makoto Takemiya , Salakhiev Kamil , Egor Ivkov - please comment.
Nikita Puzankov
From Egor Ivkov:
Nikita Puzankov
Question Makoto Takemiya:
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
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?
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.
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.
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
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