Cointime

Download App
iOS & Android

VERKLE TREE → THE ‘VERGE’ PART OF ETHEREUM

Validated Project

The “Verge” stage is one amongst the six potential upgrades in the roadmap proposed by Ethereum co-founder Vitalik Buterin for revamping blockchain technology. It is set to address the scalability trilemma the blockchain platform continues to face. The “Verge” puts forward the idea of “Verkle tree” that is set to replace the erstwhile Merkle proofs/Merkle tree. Before going to the Verkle tree concept it is essential to understand the need for such a mechanism in the blockchain framework. So let us get into the basics of it by looking through the blockchain itself.

In a blockchain, there are numerous blocks lined up indicating the number of transactions verified and validated. This is only set to increase with more participants/nodes joining the blockchain network. So every block contains a set of data including all the details pertaining to the transactions. With the addition of more blocks into the blockchain, there is a proportional increase in the database too!

In order to manage these enormous databases and to keep the blockchain running, the “state” concept comes to the fore. The state includes the block data in a specialized format using the Merkle tree concept by keeping all accounts linked by hashes and finally reducing to a single root hash stored on the blockchain. This root hash or the Merkle proof poses as a stronger digital signature with a simplified verification procedure. The Merkle proofs not only ease the block verification procedure but also helps in reducing the disc space requirements for performing unhindered transactions.

But unknown to many there lies a hidden concern of bulging state size. According to the Ethereum Foundation, the state size and the Merkle Proofs together have exceeded 135+ gigabytes of storage space. In order to overcome this dilemma, the “ Verge” stage of Ethereum upgradation proposes the idea of the Verkle tree. Introduced by John Kuszmaul in 2018, the Verkle tree concept works similarly to the Merkle tree but here the proofs are shorter in size, and the proof calculation time is also considerably reduced.

We will try to understand the overall concept through a simple example.

Generally, the Merkle tree is represented as a binary tree where the branching factor of nodes is 2. In the example discussed here, we will explore a set of 9 transactions belonging to a block added in a blockchain network using a k-ary Merkle tree where k is the branching factor.

Do you know that Ethereum uses a hexary structure in its Merkle Patricia Trie ?

Ethereum uses a variant of the Merkle tree called Merkle Patricia Trie. In this structure, each parent node can have 16 child nodes. The average depth of the tree ranges from 10 to 15 levels and the Merkle proof requires 15 sibling node details at each level.

So here the branching factor selected is 3. The first step here involves hashing each of the transactions using a cryptographic hash function. The next step is grouping the hashed transactions into subsets, further generating a hash from the subsets until the root hash is computed. The root hash or Merkle proof denotes the entire block of transactions. The figure below shows how a Merkle tree is constructed.

Figure 1: A 3-ary Merkle tree with Merkle proof highlighted in yellow

As depicted in the figure, the hashes of sibling nodes of T3 i.e. Hash(T1) and Hash(T2) + concatenated hashes of T4 to T9 can cumulatively help in tracing if T3 belongs to the entire set of transactions. And here the root Hash [ T123456789] is the Merkle proof that serves as the digest (footprint) for the entire set of transactions.

Moving further, it’s time to explore the Verkle tree with a similar setting as above. Unlike the Merkle tree which uses a cryptographic hash function to calculate the proof, the Verkle tree uses the Vector Commitment (VC) method for computing the same. The Vector Commitment is computed using the polynomial functions.

Figure 2 : A 3-ary Verkle tree

Thus for a Verkle Tree with a certain number of transactions, say, T1, T2, T3…..T9, the branching factor of the tree, k (here k = 3) is considered first. The Vector Commitment is then computed over each of these subsets. The membership proofs πi for each transaction Ti in the subset is computed with respect to the Vector Commitment (note that i refers to the index position of the given transactions). Here C1, C2, and C3 are the resulting Vector Commitments. The Vector Commitment C4 is computed over these three commitments along with their membership proofs π10, π11, and π12 respectively. Hence, C4 is the root commitment that forms the digest of the Verkle Tree.

To comprehend in a better way, consider Figure 2, here (T3,π3) in the yellow colour block means that transaction T3 exists in Commitment C1 and π3 is proof of this existence. Similarly (C1,π10) means that the Commitment C1 exists in the root Commitment C4 and π10 is proof of this existence.

Vector commitments are cryptographic techniques which allow committing to an ordered sequence of k values (t1, t2 . . . ,tk ) in such a way that one can later reveal one or many values at a specific position and prove it consistent with the initial commitment (for e.g., prove that ti is the i-th committed value) values. A Merkle tree is also a vector commitment, with the property that opening the i-th value requires a specific number of hashes as proof (Merkle proof).

The Ethereum team plans the use of KZG polynomial commitment using elliptic-curve cryptography scheme to replace the hash functions used in the Merkle tree.

Thus for a tree with billion data storage points, making Merkle proofs cumulatively would require about 1 kilobyte, but in a Verkle tree the proof would be less than 150 bytes. With the addition of nodes, the Merkle proof calculations continue to expand leading to an increase in the depth of the Merkle tree. On the contrary, the proof size in the Verkle tree remains constant and the depth of the tree is considerably reduced.

So while a verifier has to look through multiple hash calculations at each level to reach the Merkle root, the proofs in the Verkle tree simplify the process by requiring to provide only a single proof at each level to reach the root Commitment, thereby proving that a transaction or a piece of data is part of a given set.

To sum up, Verkle tree’s application in blockchain can be summarised below:

  • Overcomes related issues to data storage: Smaller proofs in Verkle trees address the data storage problem. For instance from the above example in the case of Merkle tree the proofs for transaction T3 are [Hash(T1)+Hash (T2)+ Hash (T456) +Hash (T789)] while those for the Verkle tree are [ π3 + (C1, π10) + C4].
  • Verification time is reduced with shorter proofs generated in a shorter duration of time which further enables more participation from network validators.
  • Renders implementation of stateless blockchain networks.
  • Verkle tree’s proof size efficiency in turn helps to reduce the node size, this will further lead to actualizing the stateless client’s concept.
  • The stateless clients help in the validation of execution blocks without entirely possessing the full account state.
  • Network synchronizations will be more simplified.
  • Promotes sustainable storage requirements.
  • Reduced proof sizes help smaller devices to participate as validators.
  • Faster access to information ( With root commitment in hand, blocks contain all the data required to process further).

References:

  1. Kuszmaul, J. (2019). Verkle trees. Verkle Trees, 1.
  2. https://vitalik.ca/general/2021/06/18/verkle.html
  3. https://nethermind.io/verkle-trees/
  4. https://notes.ethereum.org/@vbuterin/verkle_and_state_expiry_proposal
  5. Campanelli, M., Fiore, D., Greco, N., Kolonelos, D., & Nizzardo, L. (2020). Vector Commitment Techniques and Applications to Verifiable Decentralized Storage. IACR Cryptol. ePrint Arch., 2020, 149
  6. https://blog.ethereum.org/2021/12/02/verkle-tree-structure
  7. https://blog.ethereum.org/2015/11/15/merkling-in-ethereum
  8. https://learn.bybit.com/blockchain/what-is-merkle-tree/
  9. https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf
  10. https://cointelegraph.com/explained/merkle-trees-vs-verkle-trees-explained
  11. https://consensys.net/blog/news/the-merge-is-done-whats-next-for-the-ethereum-ecosystem/
  12. Catalano, D., & Fiore, D. (2013). Vector commitments and their applications. In Public-Key Cryptography–PKC 2013: 16th International Conference on Practice and Theory in Public-Key Cryptography, Nara, Japan, February 26–March 1, 2013. Proceedings 16 (pp. 55–72). Springer Berlin Heidelberg.

(By Sivadas Neelima, Intern Kerala Blockchain Academy)

Get the latest news here: Cointime channel — https://t.me/cointime_en

Comments

All Comments

Recommended for you

  • A British court has postponed the final sentencing of Wen Jian, a British-Chinese national involved in the country's largest Bitcoin money laundering case, until May 24.

    On May 11th, it was reported that Jian Wen, a 42-year-old British Chinese citizen, was found guilty of "participating in arranging money laundering" in the UK's largest Bitcoin money laundering case. He could be sentenced to up to 14 years in prison. Jian Wen's defense lawyer, Mark Harries, stated that due to the judge's busy schedule, the UK court has postponed Jian Wen's final sentencing, which was originally scheduled for May 10th, to May 24th.

  • Web3 startup Star Nest completes $6 million in Pre-A round of financing

    Hong Kong Web3 music startup Star Nest announced that it has completed a $6 million Pre-A round of financing, led by Chuangqi International Limited, a wholly-owned subsidiary of Hong Kong Stock Exchange-listed company Guofu Innovation. Star Nest will collaborate with Armonia Meta Chain to develop the Star Nest SpaceStar metaverse game, which includes music, role-playing, and social features.In addition, Star Nest plans to launch its NEST project in the third quarter of 2024. Nest will receive 2.1 billion NEST tokens tailored for the project, and Star Nest will use the NEST token to build a more complete music industry token economic system. The NEST token will be widely used for purchasing performance tickets, chain game cooperation, metaverse consumption, governance voting, and other activities.

  • Over $594 million worth of PYTH is staked

    According to Dune data,  there are currently 1,201,167,362 PYTH tokens in the staked state, with a total staked value exceeding $594 million. The number of PYTH stakers has reached 151,211.

  • US Department of Justice: Tornado Cash indictment has nothing to do with "free speech"

    On May 11th, the US Department of Justice explained why the motion to dismiss the criminal case against Tornado Cash founder Roman Storm was invalid. The Department of Justice reiterated that their indictment was not related to whether the Tornado Cash computer code had freedom of speech or was protected by the First Amendment of the Constitution. The defendant was not charged for publishing computer code, but for using it to facilitate profitable illegal activities.

  • USDC circulation decreased by $100 million in the past week, with a total circulation of $33 billion

    According to official data,as of May 9th, Circle has issued approximately $2 billion USDC and redeemed approximately $2 billion USDC in the past 7 days, with a decrease in circulation of approximately $100 million. The total circulation of USDC is $33 billion, with a reserve of $33.1 billion, including approximately $3.3 billion in cash and Circle Reserve Fund holding approximately $29.8 billion.

  • SEC rejects Coinbase's request for appeals court ruling on cryptocurrency rules

    The US SEC has rejected Coinbase's request to appeal to the court to review whether traditional securities rules are applicable to cryptocurrencies. In its application, Coinbase stated that it hoped the appeals court would consider whether the Howey test, which has long been used for securities evaluation, should be applied to digital assets. However, the SEC pointed out that Coinbase has not successfully demonstrated the need for such an evaluation. The SEC stated that Coinbase is attempting to create a "new legal test," but this attempt was rejected by the court. The court found that Coinbase's arguments lacked consistency and did not successfully demonstrate the existence of decisive issues. Currently, the judge responsible for hearing the SEC's case against Coinbase will make a ruling on Coinbase's intermediate appeal motion.

  • Colombian President Suspected of Accepting $500,000 in Illegal Crypto Donations

    Colombian President Gustavo Petro is suspected of accepting over $500,000 in digital token donations from a fraudulent cryptocurrency project during his 2022 election campaign. A former contractor revealed that the illegal donation occurred during a meeting in February 2022 that discussed the advantages of cryptocurrency and the possibility of working with the government. This allegation is one of the latest charges faced by President Petro during his election campaign, with the Colombian Prosecutor's Office investigating his campaign last year.

  • Fed's Kashkari: The bar for another rate hike is high, but it cannot be ruled out

    The Federal Reserve's Kashkari expressed a cautious attitude towards restrictive monetary policy; he is adopting a wait-and-see attitude towards future monetary policy; he is in a wait-and-see state to see if inflation is stagnating; the threshold for raising interest rates again is high, but this possibility cannot be ruled out; if inflation data supports it, the Fed will maintain interest rates.

  • The address that defrauded 1,155 wBTC has returned more than 96% of the funds to the victims

    Blockchain data shows that the address poisoning attacker lured users to send 1,155 Wrapped Bitcoins (wBTC) (valued at $68 million at the time) to them. The attacker has returned almost all of the stolen funds. These funds were exchanged for Ethereum (ETH) during the attacker's holding period, and the price of ETH has since fallen. However, the attacker returned about 22,960.07 ETH, worth about $65.7 million, which accounts for over 96% of the initial stolen funds in terms of US dollar value.

  • The 133rd Ethereum ACDC meeting: The goal is to complete the devnet within 7-10 days

    The Ethereum developers held their 133rd ACDC conference call. First, they outlined the latest research on Ethereum protocol confirmation rules. Then, they discussed Pectra updates related to EIP-7547 and CFI states, and decided to put them on hold temporarily. They also updated the v1.5.0-alpha.1 specification. Regarding the implementation updates for devnet-0, most teams are making progress, but there are also some unexpected complexities. The goal is to complete devnet within 7-10 days.