Research Summary: Massive off-chain minting with verifiable on-chain commitments

TLDR

Minting a large number of documents on Blockchain is achievable with the help of off-chain commitment and proof preparations.
The transaction costs of the protocol are low, especially when using L2 Blockchain solutions.

Core Research Question

Can a large volume of documents be minted on-chain in real-time, with the support of off-chain computations?

Citation

Aleksandar Veljković, 3327, Minty - Massive off-chain minting with verifiable on-chain commitments

Background

  • Merkle tree - Data structure where the values of nodes (except leaf nodes) are determined as hashes of the values in their children nodes.
  • Commitment - Value to which all future computations are bound
  • Blockchain transaction - Transaction upon which the sent data is written on the blockchain

Summary

  • Storing large documents on Blockchain is practically impossible.
  • Real-time execution of Blockchain transactions is not guaranteed.
  • Costs of writing only commitments of individual files in individual transactions or batches can skyrocket the costs when dealing with thousands of files.
  • Signing thousands of individual commitments can be inefficient when the documents come frequently and in large volumes.
  • Merkle tree root hash can represent a commitment of multiple files.
  • Proof of knowledge for any leaf of a Merkle tree can be derived from the tree and verified in the smart contract.
  • An exponential time complexity for generating Merkle trees can also be a limiting factor when dealing with tens of thousands of documents.

Method

  • Parallelization of Merkle tree construction can be achieved efficiently on multicore processors.
  • Multiple Merkle trees can be joined into one single tree by generating a “cap” tree where the leaves of the new tree are roots of individual subtrees.
  • Commitments of documents can be generated as a root hash of a document Merkle tree constructed in a parallel manner and submitted on Blockchain in semi-real-time.
  • Documents can represent any digital document or token (NFTs, for example).
  • Document issuers can generate tree leaves as hashes of documents and addresses of the associated owners and construct Merkle tree in parallel.
  • For each document, issuers derive Merkle proofs and send them to the owners off-chain, while the Merkle tree roots are written on-chain as commitments.
  • A document owner can provide data to the smart contract and Merkle proof to mint the document on-chain.

Results

  • The proposed protocol can construct root hash commitments and proofs of more than 1,000,000 individual documents in less than 1 minute on a quad-core CPU.
  • Compared to signing individual documents, parallel Merkle tree generation and proof extraction efficiency achieve better results.

Discussion and Key Takeaways

  • Minting a large number of documents on Blockchain is achievable with the help of off-chain commitment and proof preparations.
  • The transaction costs of the protocol are low, especially when using L2 Blockchain solutions.
  • The protocol is named Minty.

Implications and Follow-ups

  • The proposed tree generation method could be further improved to run parallel tree generation using multiple processors or a cluster of computation servers.
  • Further work will be oriented toward implementing practical solutions that utilize the Minty protocol.

Applicability

  • Minting a large number of documents on- and off-chain represents a primitive that could be applied in many new use cases.
  • The presented protocol can be utilized for creating NFT markets with massive off-chain minting.
  • The protocol can also be applied for minting large volumes of credentials, like ID cards, passports, licenses, etc.
8 Likes

Thank you @Aleksandar_3327, for posting this research paper, it is really nice and simple. I enjoyed reading same. But do you think if there factors to consider before minting?

3 Likes

@Aleksandar_3327 welcome to the community :hugs: and congrats on your summary.

I was introduced to Merkle trees a while ago; I had no idea they could be combined. The combination definitely opens up different opportunities/use cases in this context and more.

It doesn’t help that storing data, especially large forms on the blockchain is deemed impossible due to how expensive it is. This shortcoming defeats the purpose of the blockchain – storing and securing any form of data.

That said, I’m glad to see solutions to the problem, in the form of Minty and I like that the proposed costs are low due to L2 blockchain solutions.

My question is: have there been any IRL/practical applications of the protocol or are the discussions and takeaways only based on the author’s research?

4 Likes

Hi @Lucas, I’m glad you enjoyed it! The two general factors are:

  1. The expected volume of documents - More documents require deeper trees - but as complexity grows exponentially with the depth of the trees, a balance should be established between the depth of the trees, the number of the trees, and the hardware resources of the machine that computes the commitments.

  2. Frequency of the commitments - Less frequent commitments can save a significant amount of money but can also affect the real-time property of the system.

2 Likes

Hi @Harvesto !

Some of the potential applications for Minty are the mass-minting of NFTs, airdrops, issuing cards/items that are frequently generated in online games (treasure box items, looted items, etc.), and similar.

2 Likes