Hashed Trie - Revision history

Fireduck at 17:40, 4 September 2019

2019-09-04T17:40:12Z

Fireduck at 04:21, 3 September 2019

2019-09-03T04:21:18Z

Fireduck at 04:12, 3 September 2019

2019-09-03T04:12:12Z

Fireduck at 04:09, 3 September 2019

2019-09-03T04:09:54Z

Fireduck at 04:07, 3 September 2019

2019-09-03T04:07:43Z

Fireduck: Created page with "==Hashed Trie== ===Definition=== ===Advantages=== ===Disadvantages=== ===Why it is awesome for blockchains==="

2019-09-03T03:53:28Z

Created page with "==Hashed Trie== ===Definition=== ===Advantages=== ===Disadvantages=== ===Why it is awesome for blockchains==="

New page

==Hashed Trie==

===Definition===

===Advantages===

===Disadvantages===

===Why it is awesome for blockchains===

@@ Line 37: / Line 37: @@
 * The root hash can be shared in consensus to insure that nodes have the same data in the tree.  For example, in Snowblossom the UXTO root hash is from the UTXO hashed trie.
 ** Then the shared root hash and the intermediate nodes can be used to prove the existence and completeness of any data in the tree to light clients or header only nodes.
 * If there is a reorg, or potential reorg the new root hashes can be updated based on the root hashes of the previous blocks.  No need to back out changes or pick a chain, just apply all reasonable blocks to the hashed trie.  Use whatever ends up winning.  For example, lets say the trie is storing the transactions that have been confirmed as of the most recent block.  Lets say we are on block 10000.  Suppose there is a reorg so a new block 9997 comes in.  We build the transaction trie for that simply taking the root hash from block 9996 and mutating from there.  Then the new chain fork can be imported independently of the existing fork.
 * If we save the root hash for previous blocks, we can query the tree for the state of things at any previous block we want.  This way, a client that is doing a long read of a bunch of stuff can pick and block and query everything relative to that even as new blocks are coming in.
 * Since for a blockchain ledger, we generally don't want to throw data away, the fact that nothing is ever pruned is fine.

@@ Line 13: / Line 13: @@
 ==Definition==
-A Hashed Trie is a structure that is a [https://en.wikipedia.org/wiki/Trie Trie] where each node has a hash value based on its contents.  The tree state is saved as a hash, which simply points to the root node for that state.  The children of each node are referenced by their hash.  No node is every overwritten, if it is change the hash changes and it is saved under the new hash.  This makes it a space efficient Copy-on-Write (CoW) structure.
+A Hashed Trie is a structure that is a [https://en.wikipedia.org/wiki/Trie Trie] where each node has a hash value based on its contents.  In my implementation there is an underlying map of hashs to nodes: Map<Hash,Node>.  The tree state is saved as a hash, which simply points to the root node for that state.  The children of each node are referenced by their hash.  No node is every overwritten (except as possibly rewritten as the exact same data), if it is changed the hash changes and it is saved under the new hash.  This makes it a space efficient Copy-on-Write (CoW) structure.
 Each operation is given the root hash as a parameter.  Any modify operation returns a new root hash for the new tree.
@@ Line 30: / Line 30: @@
 * Any write will involve rewriting all the nodes from the root on down to the leaf node in question log(n) operations.  Can be helped by batching updates.
 * Reads involve reading all the nodes along the path, log(n) operations (likely helped greatly with cache).
 ==Why it is awesome for blockchains==
@@ Line 35: / Line 37: @@
 * The root hash can be shared in consensus to insure that nodes have the same data in the tree.  For example, in Snowblossom the UXTO root hash is from the UTXO hashed trie.
 ** Then the shared root hash and the intermediate nodes can be used to prove the existence and completeness of any data in the tree to light clients or header only nodes.
-* If there is a reorg, or potential reorg the new root hashes can be updated based on the root hashes of the previous blocks.  No need to back out changes or pick a chain, just apply all reasonable blocks to the hashed trie.  Use whatever ends up winning.
+* If there is a reorg, or potential reorg the new root hashes can be updated based on the root hashes of the previous blocks.  No need to back out changes or pick a chain, just apply all reasonable blocks to the hashed trie.  Use whatever ends up winning.  For example, lets say the trie is storing the transactions that have been confirmed as of the most recent block.  Lets say we are on block 10000.  Suppose there is a reorg so a new block 9997 comes in.  We build the transaction trie for that simply taking the root hash from block 9996 and mutating from there.  Then the new chain fork can be imported independently of the existing fork.

← Older revision		Revision as of 04:12, 3 September 2019
Line 2:		Line 2:

	I think this is novel, but if I am wrong, please let me know.		I think this is novel, but if I am wrong, please let me know.
		+
		+	==Implementation==
		+
		+	* Source [https://github.com/snowblossomcoin/snowblossom/tree/master/lib/src/trie Snowblossom Trie]
		+	* Tests [https://github.com/snowblossomcoin/snowblossom/tree/master/lib/test/trie Snowblossom Trie Tests]
		+
		+
		+

	==Definition==		==Definition==

← Older revision		Revision as of 04:09, 3 September 2019
Line 27:		Line 27:
	* The root hash can be shared in consensus to insure that nodes have the same data in the tree. For example, in Snowblossom the UXTO root hash is from the UTXO hashed trie.		* The root hash can be shared in consensus to insure that nodes have the same data in the tree. For example, in Snowblossom the UXTO root hash is from the UTXO hashed trie.
	** Then the shared root hash and the intermediate nodes can be used to prove the existence and completeness of any data in the tree to light clients or header only nodes.		** Then the shared root hash and the intermediate nodes can be used to prove the existence and completeness of any data in the tree to light clients or header only nodes.
		+	* If there is a reorg, or potential reorg the new root hashes can be updated based on the root hashes of the previous blocks. No need to back out changes or pick a chain, just apply all reasonable blocks to the hashed trie. Use whatever ends up winning.

@@ Line 1: / Line 1: @@
-==Hashed Trie==
+=Hashed Trie=
-===Definition===
+I think this is novel, but if I am wrong, please let me know.
-===Advantages===
+==Definition==
-===Disadvantages===
+A Hashed Trie is a structure that is a [https://en.wikipedia.org/wiki/Trie Trie] where each node has a hash value based on its contents.  The tree state is saved as a hash, which simply points to the root node for that state.  The children of each node are referenced by their hash.  No node is every overwritten, if it is change the hash changes and it is saved under the new hash.  This makes it a space efficient Copy-on-Write (CoW) structure.
-===Why it is awesome for blockchains===
+Each operation is given the root hash as a parameter.  Any modify operation returns a new root hash for the new tree.