Golden
Merkle tree

Merkle tree

One-directional tree (data structure) in which every non-leaf node is labelled with the hash of the labels (or values in case of leaves) of its child nodes, until a only a single hash remains at the top of the structure, known as the merkle root.

All edits

Edits on 24 Mar 2019
Dawson Sewell"Approved suggestion from source: https://www.wikidata.org/wiki/Q14746"
Dawson Sewell approved a suggestion from Golden's AI on 24 Mar 2019 3:33 pm
Edits made to:
Infobox (+1 properties)

Infobox

Named after
Edits on 15 Jan 2019
Dawson Sewell
Dawson Sewell approved a suggestion from Golden's AI on 15 Jan 2019 2:14 pm
Edits made to:
Article (+16/-16 characters)

Article

In the Bitcoin whitepaper, Satoshi Nakamoto describes how merkle trees are used in Bitcoin in order to compact transaction datatransaction data so that it's more feasible to store the entire Bitcoin transaction history on a relatively small amount of disk space.

Edits on 11 Jan 2019
Dawson Sewell
Dawson Sewell approved a suggestion from Golden's AI on 11 Jan 2019 3:47 pm
Edits made to:
Article (+16/-16 characters)

Article

In the Bitcoin whitepaper, Satoshi NakamotoSatoshi Nakamoto describes how merkle trees are used in Bitcoin in order to compact transaction data so that it's more feasible to store the entire Bitcoin transaction history on a relatively small amount of disk space.

Edits on 9 Jan 2019
Jude Gomila
Jude Gomila approved a suggestion from Golden's AI on 9 Jan 2019 8:49 pm
Edits made to:
Article (+7/-7 characters)

Article

In the BitcoinBitcoin whitepaper, Satoshi Nakamoto describes how merkle trees are used in Bitcoin in order to compact transaction data so that it's more feasible to store the entire Bitcoin transaction history on a relatively small amount of disk space.

Edits on 7 Jan 2019
Daniel Frumkin"Changed description, wrote article, added resources, added related topics."
Daniel Frumkin edited on 7 Jan 2019 5:59 pm
Edits made to:
Description (+130/-5 characters)
Article (+2 images) (+2874 characters)
People (+3 cells) (+45 characters)
Further reading (+12 cells) (+529 characters)
Documentaries, videos and podcasts (+2 cells) (+108 characters)
Categories (+2/-1 topics)
Related Topics (+2 topics)
Topic thumbnail

Merkle tree

TreeOne-directional tree (data structure) in which every non-leaf node is labelled with the hash of the labels (or values (in case of leaves) of its child nodes, until a only a single hash remains at the top of the structure, known as the merkle root.

Article

Merkle trees (also known as hash trees) are a means of efficiently and securely managing / storing large amounts of data. The idea was created and patented by Ralph C. Merkle in 1979, with the patent expiring in 2002.



In a merkle tree, every non-leaf node is labelled with the hash of the labels of its child nodes (or the hash of the value of a leaf at the bottom of the tree), a process which repeats itself moving up the tree until a single hash remains: the merkle root. 

In the figure above, the leaves are the 8 boxes at the bottom which have no children branching out beneath of them. A cryptographic hash function processes each leaf value to produce a hash output. This is then paired with another hash and run through the cryptographic hash function again to produce yet another hash, and so on moving up the tree, until only the merkle root (a[3,0]) remains. If a value of a leaf or non-leaf hash changes, the change impacts the hashes of every parent node in its branch all the way up to the top of tree, making it immediately obvious that the change has occurred simply by looking at the merkle root.

Benefits of Merkle Trees

Merkle trees are useful in cryptography for several reasons, some of which include:

  • Providing a means of data integrity / validity.
  • Condensing large amounts of data so that less memory / disk space is need to store it and it's easier / faster to transmit across a network.
  • Proofs are computationally easy and fast.

Use of Merkle Trees in Blockchains

In the Bitcoin whitepaper, Satoshi Nakamoto describes how merkle trees are used in Bitcoin in order to compact transaction data so that it's more feasible to store the entire Bitcoin transaction history on a relatively small amount of disk space.

Every signed Bitcoin transaction is hashed and has an ouput tied to the transaction identifier (TXID). Outputs are categorized as either Unspent Transaction Outputs (UTXOs) or spent transaction outputs. This makes it possible to quickly and easily validate future transactions, as validators just need to check that only UTXOs are used as inputs, implying that there isn't an attempted double-spend. 

...

All of this transaction information is part of a merkle tree, and the root hash of that merkle tree is contained in the blockchain. Each block references the hash of the previous block, all the way back to the genesis block of the blockchain. If somebody attempts to change something about the data from any single transaction from the past, it will cause the root hash of that block to change, which subsequently changes the hashes of all of the blocks that followed it. This is a way to ensure the integrity of the blockchain's transaction history without needing to store the complete data of every transaction. 

People

Name
Role
Related Golden topics

Ralph C. Merkle

Creator

Further reading

Title
Author
Link
Type

A Certified Digital Signature

Ralph C. Merkle

PDF

Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis

Georg Becker, Seminararbeit Ruhr

PDF

Understanding Merkle Trees - Why use them, who uses them, and how to use them - CodeProject

Marc Clifton

Web

Documentaries, videos and podcasts

Title
Date
Link

Blockchain Basics Explained - Hashes with Mining and Merkle trees



Categories

Related Topics

Edits on 15 Oct 2018
Golden AI"Move some fields to suggestions"
Golden AI edited on 15 Oct 2018 11:12 pm
Edits made to:
Infobox (-1 properties)
Edits on 22 Sep 2018
Golden AI"Import structured data from Wikidata.org: https://www.wikidata.org/wiki/Q14746"
Golden AI edited on 22 Sep 2018 1:56 am
Edits made to:
Infobox (+1 properties)

Infobox

Named after
Edits on 1 Dec 2017
Alex Dean
Alex Dean edited on 1 Dec 2017 12:23 am
Edits made to:
Article
Related Topics (+3 topics)
Edits on 28 Sep 2017
Alex Dean
Alex Dean edited on 28 Sep 2017 11:49 pm
Edits made to:
Categories (+2 topics)
Related Topics (+2 topics)
Topic thumbnail

Merkle tree

One-directional tree (data structure) in which every non-leaf node is labelled with the hash of the labels (or values in case of leaves) of its child nodes, until a only a single hash remains at the top of the structure, known as the merkle root.

Categories

Related Topics

Edits on 1 Jan 2017
Golden AI"Initial topic creation"
Golden AI created this topic on 1 Jan 2017 12:00 am
Edits made to:
Description (+122 characters)
Article
Topic thumbnail

 Merkle tree

Tree in which every non-leaf node is labelled with the hash of the labels or values (in case of leaves) of its child nodes

No more activity to show.