Merkle tree | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

In cryptography and computer science, a hash tree or Merkle tree is a tree in which every "leaf" (node) is labelled with the cryptographic hash of a data block, and every node that is not a leaf (called a branch, inner node, or inode) is labelled with the cryptographic hash of the labels of its child nodes. A hash tree allows efficient and secure verification of the contents of a large data structure. A hash tree is a generalization of a hash list and a hash chain. Demonstrating that a leaf node is a part of a given binary hash tree requires computing a number of hashes proportional to the logarithm of the number of leaf nodes in the tree. Conversely, in a hash list, the number is proportional to the number of leaf nodes itself. A Merkle tree is therefore an efficient example of a cryptographic commitment scheme, in which the root of the tree is seen as a commitment and leaf nodes may be revealed and proven to be part of the original commitment. The concept of a hash tree is named after Ralph Merkle, who patented it in 1979. Hash trees can be used to verify any kind of data stored, handled and transferred in and between computers. They can help ensure that data blocks received from other peers in a peer-to-peer network are received undamaged and unaltered, and even to check that the other peers do not lie and send fake blocks. Hash trees are used in hash-based cryptography. Hash trees are also used in the (IPFS), Btrfs and ZFS file systems (to counter data degradation); Dat protocol; Apache Wave protocol; Git and Mercurial distributed revision control systems; the Tahoe-LAFS backup system; Zeronet; the Bitcoin and Ethereum peer-to-peer networks; the Certificate Transparency framework; the Nix package manager and descendants like GNU Guix; and a number of NoSQL systems such as Apache Cassandra, Riak, and Dynamo. Suggestions have been made to use hash trees in trusted computing systems. The initial Bitcoin implementation of Merkle trees by Satoshi Nakamoto applies the compression step of the hash function to an excessive degree, which is mitigated by using Fast Merkle Trees.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (1)

Related concepts (15)

Related courses (3)

Related lectures (25)

Blockchain

A blockchain is a distributed ledger with growing lists of records (blocks) that are securely linked together via cryptographic hashes. Each block contains a cryptographic hash of the previous block, a timestamp, and transaction data (generally represented as a Merkle tree, where data nodes are represented by leaves). Since each block contains information about the previous block, they effectively form a chain (compare linked list data structure), with each additional block linking to the ones before it.

Merkle tree

Bitcoin

Bitcoin (abbreviation: BTC or XBT; sign: ₿) is a decentralized digital currency. Bitcoin transactions are verified by network nodes through cryptography and recorded in a public distributed ledger called a blockchain. The cryptocurrency was invented in 2008 by an unknown person or group of people using the name Satoshi Nakamoto. The currency began use in 2009, when its implementation was released as open-source software. The word "bitcoin" was defined in a white paper published on October 31, 2008.

Improving Stateless Hash-Based Signatures

Jean-Philippe Aumasson

present several optimizations to SPHINCS, a stateless hash-based signature scheme proposed by Bernstein et al. in (2015): PORS, a more secure variant of the HORS few-time signature scheme used in SPHINCS; secret key caching, to speed-up signing and reduce signature size; batch signing, to amortize signature time and reduce signature size when signing multiple messages at once; mask-less constructions to reduce the key size and simplify the scheme; and Octopus, a technique to eliminate redundancies from authentication paths in Merkle trees. Based on a refined analysis of the subset resilience problem, we show that SPHINCS' parameters can be modified to reduce the signature size while retaining a similar security level and computation time. We then propose Gravity-SPHINCS, our variant of SPHINCS embodying the aforementioned tricks. Gravity-SPHINCS has shorter keys (32 and 64 bytes instead of approximate to 1 KB), shorter signatures (approximate to 30 KB instead of 41KB), and faster signing and verification for the same security level as SPHINCS.

SPRINGER INTERNATIONAL PUBLISHING AG2018

A decentralized system is one that works when no single party is in charge or fully trusted. This course teaches decentralized systems principles while guiding students through the engineering of thei

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how

This course provides an introduction to Distributed Ledger Technology (DLT), blockchains and cryptocurrencies, and their applications in finance and banking and draws the analogies between Traditional

Blockchain Basics: Financial Applications FIN-413: Financial applications of blockchains and distributed ledgers

Delves into blockchain basics and financial applications, covering hash puzzles, Merkle trees, proof of stake, and smart contracts.

Decentralized Systems: Distributed Storage and Eclipse Attacks CS-234: Technologies for democratic society

Explores decentralized systems, distributed storage, and Eclipse attacks in peer-to-peer networks, emphasizing security and consistency.

Decentralized Storage & Distribution: BitTorrent & IPFS

Explores decentralized storage & distribution using BitTorrent & IPFS, covering goals, challenges, building specifications, integrity, bootstrapping, performance, incentives, versioning, naming, and CRDTs.