3 ms·

Both git repositories and bitcoin are specialized Merkle trees. Merkle trees are incredibly useful and general; they are used in many kinds of verification, esp

Both git repositories and bitcoin are specialized Merkle trees. Merkle trees are incredibly useful and general; they are used in many kinds of verification, especially of large chunks of data. http://en.wikipedia.org/wiki/Merkle_tree http://en.wikipedia.org/wiki/Merkle_tree

ngoldbaum 11y ago
I thought it was a directed acyclic graph. Care to share the distinction?
- cfallin 11y ago
  You can see git's DAG as a dedup'd Merkle tree: in other words, if two child pointers in two places in the tree point to nodes (blobs) with the same hash, make them share a single node instead. This works because the hash "is" the content/entire subtree (modulo hash collisions), so the resulting data structure has the same meaning as before. Content/hash-addressed stores are related to referential transparency and immutability (and deep equality) in languages like Haskell, FWIW. I've always thought it's sort of beautiful how cleanly the ideas come together like that.
- deleted 11y ago
  [deleted]
- petertodd 11y ago
  The terminology used in #bitcoin-wizards is to call it a merkelized dag, or merkle-dag. Similarly, we also refer to "Merkelized Abstract Syntax Trees", a way of hashing code originally proposed by Pieter Wuille and Russel O'connor(1) that will probably be added to Bitcoin's scripting system eventually. Pretty much any data structure can have hash functions added to it to "merkelize" it, producing an authenticated data structure: http://www.cs.umd.edu/~amiller/gpads/ http://www.cs.umd.edu/~amiller/gpads/ 1) https://download.wpsoftware.net/bitcoin/wizards/2014-12-16.html https://download.wpsoftware.net/bitcoin/wizards/2014-12-16.h...
  - nivertech 11y ago
    Bitcoin Script is Forth-like RPN, why does it need AST? Do you mean there are plans to add more languages/DSLs to Bitcoin which with multiple compiler front-ends generating ASTs. which then translated to "machine opcodes"? Something similar to Ethereum? Or maybe it's a solution for transaction scriptSig malleability? [1] [1] https://en.bitcoin.it/wiki/Transaction_Malleability https://en.bitcoin.it/wiki/Transaction_Malleability
ejholmes 11y ago
The power of the Merkle tree is pretty amazing. IPFS is a good example https://www.ipfs.com https://www.ipfs.com.
- nosir33 11y ago
  http://ipfs.io/ http://ipfs.io/

ngoldbaum 11y ago

I thought it was a directed acyclic graph. Care to share the distinction?

cfallin 11y ago
You can see git's DAG as a dedup'd Merkle tree: in other words, if two child pointers in two places in the tree point to nodes (blobs) with the same hash, make them share a single node instead. This works because the hash "is" the content/entire subtree (modulo hash collisions), so the resulting data structure has the same meaning as before. Content/hash-addressed stores are related to referential transparency and immutability (and deep equality) in languages like Haskell, FWIW. I've always thought it's sort of beautiful how cleanly the ideas come together like that.
deleted 11y ago
[deleted]
petertodd 11y ago
The terminology used in #bitcoin-wizards is to call it a merkelized dag, or merkle-dag. Similarly, we also refer to "Merkelized Abstract Syntax Trees", a way of hashing code originally proposed by Pieter Wuille and Russel O'connor(1) that will probably be added to Bitcoin's scripting system eventually. Pretty much any data structure can have hash functions added to it to "merkelize" it, producing an authenticated data structure: http://www.cs.umd.edu/~amiller/gpads/ http://www.cs.umd.edu/~amiller/gpads/ 1) https://download.wpsoftware.net/bitcoin/wizards/2014-12-16.html https://download.wpsoftware.net/bitcoin/wizards/2014-12-16.h...
- nivertech 11y ago
  Bitcoin Script is Forth-like RPN, why does it need AST? Do you mean there are plans to add more languages/DSLs to Bitcoin which with multiple compiler front-ends generating ASTs. which then translated to "machine opcodes"? Something similar to Ethereum? Or maybe it's a solution for transaction scriptSig malleability? [1] [1] https://en.bitcoin.it/wiki/Transaction_Malleability https://en.bitcoin.it/wiki/Transaction_Malleability

ejholmes 11y ago

The power of the Merkle tree is pretty amazing. IPFS is a good example https://www.ipfs.com https://www.ipfs.com.

nosir33 11y ago
http://ipfs.io/ http://ipfs.io/