Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Snarl: Entangled Merkle Trees for Improved File Availability and Storage Utilization
 
conference paper

Snarl: Entangled Merkle Trees for Improved File Availability and Storage Utilization

Nygaard, Racin
•
Estrada-Galiñanes, Vero  
•
Meling, Hein
December 2, 2021
Middleware '21: Proceedings of the 22nd International Middleware Conference
22nd International Middleware Conference (Middleware '21)

In cryptographic decentralized storage systems, files are split into chunks and distributed across a network of peers. These storage systems encode files using Merkle trees, a hierarchical data structure that provides integrity verification and lookup services. A Merkle tree maps the chunks of a file to a single root whose hash value is the file's content-address.A major concern is that even minor network churn can result in chunks becoming irretrievable due to the hierarchical dependencies in the Merkle tree. For example, chunks may be available but can not be found if all peers storing the root fail. Thus, to reduce the impact of churn, a decentralized replication process typically stores each chunk at multiple peers. However, we observe that this process reduces the network's storage utilization and is vulnerable to cascading failures as some chunks are replicated 10X less than others.We propose Snarl, a novel storage component that uses a variation of alpha entanglement codes to add user-controlled redundancy to address these problems. Our contributions are summarized as follows: 1) the design of an entangled Merkle tree, a resilient data structure that reduces the impact of hierarchical dependencies, and 2) the Snarl prototype to improve file availability and storage utilization in a real-world storage network. We evaluate Snarl using various failure scenarios on a large cluster running the Ethereum Swarm network. Our evaluation shows that Snarl increases storage utilization by 5X in Swarm with improved file availability. File recovery is bandwidth-efficient and uses less than 2X chunks on average in scenarios with up to 50% of total chunk loss.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/3464298.3493397
Author(s)
Nygaard, Racin
Estrada-Galiñanes, Vero  
Meling, Hein
Date Issued

2021-12-02

Publisher

Association for Computing Machinery

Publisher place

New York, NY, USA

Published in
Middleware '21: Proceedings of the 22nd International Middleware Conference
ISBN of the book

978-1-450385-34-3

Total of pages

12

Start page

236

End page

247

Subjects

storage utilization

•

file availability

•

entanglement codes

•

erasure codes

•

cryptographic decentralized storage system

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DEDIS  
Event nameEvent placeEvent date
22nd International Middleware Conference (Middleware '21)

Quebec, Canada

Decembre 6-10, 2021

Available on Infoscience
August 12, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/189944
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés