Storage Auditing Using Merkle Trees and KZG Commitments

Dr. Chloe I. Avery

Justin Sheek

January 16, 2025

1 Overview/Background 1

1.1 Erasure Coding 2

2 Performing Audits Using Merkle Trees 2

2.1 What is a Merkle Tree? 2

2.2 Interactive Audits 3

2.3 Non-Interactive Audits 4

2.3.1 Fiat-Shamir 4

3 Performing (Non-Interactive) Audits Using KZG Commitments 5

3.1 KZG Background info 5

3.2 Notation 5

3.3 (Trusted) Setup 6

3.4 Data Upload 6

3.5 Self-Auditing/Commitments 6

4 Open Questions and Future Directions 7

5 Acknowledgements 7

1 Overview/Background

This paper presents ideas for how audits of storage Providers could be performed in a decentralized data storage system. We introduce two different possibilities: using Merkle trees and using KZG commitments. KZG commitments are the more efficient way of performing audits of storage providers, and offer many additional benefits. However, Merkle tree audits work much the same way, are easier to understand, and provide a good scaffolding for understanding the KZG case. Therefore, we first discuss Merkle tree audits, and then discuss KZG audits. Although this paper can stand alone, the ideas presented in this paper will be put in proper context if the Orchid Storage lightpaper [1] is read first.

1.1 Erasure Coding

This paper operates under the assumption that upon upload, Clients erasure code their data. Erasure coding is a way to break up data into multiple overlapping pieces, say n pieces, such that for some k (with k ≤ n), any k pieces can be used to reconstruct the data. The following sections don’t strictly rely on the use of erasure coding, but it is discussed. For more information about erasure coding and how Orchid uses it for decentralized data storage, see [1], Orchid’s storage lightpaper.

2 Performing Audits Using Merkle Trees

In this section we describe how to perform Merkle tree audits both interactively (meaning that the Client is online the entire time and able to interact with the storage Provider) and non-interactively (meaning that the Client is offline and storage Providers post proofs that are later checked by other storage Providers).

2.1 What is a Merkle Tree?

The definition of a Merkle tree relies on cryptographic hash functions.

Definition 2.1. A cryptographic hash function is a map from an arbitrary binary string to a binary string of some fixed length such that:

The function is one way. In other words, for any specified output, it is not computationally feasible to find an input that maps to it.
The function is collision-resistant. In other words, it is computationally infeasible to find two distinct inputs that have the same output. The output of a cryptographic hash function is often referred to simply as a “hash”, and the function applied to a specific input is often referred to as the hash of that input. An example of a cryptographic hash function is SHA-256 (SHA stands for “Secure Hash Algorithm”), which outputs a 256 bit hash. To encode data into a Merkle tree, begin by choosing a number n, then break the data into 2n pieces. That is, thinking of the data as a binary string, we split the data into a sequence of 2n binary strings. Using the data and this hash function, we build a tree, starting at the bottom level (the leaves) of our tree, which represent these pieces of data and their hashes. We then pair off the leaves and let the parent of a pair of leaves be the hash of the concatenation of this pair. Next, we do the same thing for the parents, pairing them off, and then letting the parent of a pair be the hash of the concatenation of that pair. We repeat this all the way up until we get a single hash at the top. Since the data was broken into 2n pieces, we are assured that we can pair off pieces and end up with a single hash at the top of our Merkle tree.

Definition 2.2. The root hash of a Merkle tree is the hash at the top of the tree.

2.2 Interactive Audits

Once a Client selects a Provider and transmits their encoded data, the Client dictates to the Provider how to chunk the data, therefore determining the structure of the Merkle tree. The Provider constructs the tree and then transmits the root to the Client. Meanwhile, the Client constructs the same tree. If the root matches, the Client may delete their data as they only need to retain the root for use in the next stage. Thereafter, at any time the Client can choose a (random) leaf of the Merkle-encoded erasure block and request that it be sent, along with the necessary metadata from the Merkle tree to prove that that piece was a part of the erasure block that has a matching root. This is called a Merkle inclusion proof, and is best described using an example.

2.3 Non-Interactive Audits

When the Client is online, they can perform audits of the providers themselves, as described in section 2.2. However, as soon as the Client goes offline, the issue of trust becomes more complicated. Many projects add another actor, often called an Auditor, to perform this task. Adding another party, however, adds a level of complexity to a system with already carefully balanced incentives. Auditors could conspire with storage Providers, conspire with Clients, or simply perform griefing attacks. Since trust remains an issue as the Client does not inherently trust the Auditors, this begs the question: who audits the Auditors? The idea that there is nothing stopping a storage Provider from also being an Auditor got us thinking: what if instead we start with the assumption that storage Providers are also Auditors.

2.3.1 Fiat-Shamir

We utilize the Fiat-Shamir heuristic, originally described in [4], which is a method for turning an interactive protocol into a non-interactive protocol. The audit itself looks very similar to the interactive audit case, with the main difference being that rather than sending data to the Client, the Provider will post the necessary Merkle tree data on chain at certain pre-specified intervals. These Merkle proofs are then checked by the other providers in the same cohort.

3 Performing (Non-Interactive) Audits Using KZG Commitments

While it is theoretically possible for Providers to perform self-audits using Merkle proofs, posting frequent and large proofs to a blockchain can be very costly. Not to mention that when using the ideas discussed in Section 1, since at every step a piece of the data is posted on-chain, eventually all of the data will be posted on-chain (Then why hire providers in the first place? You might as well have posted your data to a blockchain from the beginning.). KZG commitments reduce both the amount that needs to go on-chain and the frequency with which proofs need to be posted.

3.1 KZG Background info

The following sections use KZG commitments, which we do not describe in detail, but rather describe how we use them. However, there are some quite well-written explanations out there.

3.2 Notation

We call our Clients A and B, our Providers α and β. Assume that Client A has one piece of data, dA, and Client B has one piece of data, dB. dA is broken into blocks bA,α and bA,β and dB is broken into blocks bB,α and bB,β. Provider α stores blocks bA,α and bB,α and provider β stores blocks bA,β and bB,β.

3.3 (Trusted) Setup

Creating a KZG commitment typically involves a trusted third party choosing a random group element and computing public parameters. However, by using Trusted Setups, as outlined in [2], we can eliminate the need for a third party.

3.4 Data Upload

When Client A uploads their data, they will send Provider α the block bA,α. Provider α and Client A come to an agreement on how to break this block into sub-blocks.

3.5 Self-Auditing/Commitments

Using Lagrange interpolation, as discussed in section 3.1. Providers post their self-audits at certain intervals. These intervals could, for example, be specified in the Rate Certificate, or could be left up to the Provider to strike a balance between being paid frequently to minimize risk and being paid infrequently to minimize cost.

4 Open Questions and Future Directions

In this paper, we present ideas both for interactive audits and non-interactive audits. While having a system that uses non-interactive audits works in both cases: when the Client is online or away, it may be advantageous or more cost-effective (as interactive audits do not require anything to be posted to a blockchain) to be able to switch between interactive and non-interactive audits. However, building this switch into a protocol can be complicated, therefore, this, as well as further efficiency improvements are directions for further research.

5 Acknowledgements

A huge thank you to Dan Montgomery, Patrick Niemeyer, and Dr. Steven Waterhouse for edits, feedback, insights, and advice. And thank you to Chad Harper for making the diagrams.

References

[1] Chloe Avery and Justin Sheek. Orchid Storage: A New Open Source Initiative For Decentralized, Incentivized Data Storage. https://www.orchid.com/storage-litepaper-latest.pdf.

[2] Vitalik Buterin. How do trusted setups work? https://vitalik.eth.limo/general/2022/03/14/trustedsetup.html.

[3] Dankrad Feist. KZG Polynomial Commitments. https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html.

[4] Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signa- ture problems. In Conference on the theory and application of cryptographic techniques, pages 186–194. Springer, 1986.

[5] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-Size Commitments to Polynomials and Their Applications. https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf.

[6] Luksgrin. A quick insight on Algebra and KZG Commitments. https://github.com/luksgrin/opensense-algebra-and-kzg/blob/main/algebraandkzg.ipynb.