• Login
Crypto Newsmart
No Result
View All Result
  • HOME
  • BITCOIN
  • CRYPTO UPDATES
    • ALTCOIN
    • ETEREUM
    • NFT’s
    • CRYPTO PRICE ANALYSIS
  • LEARN CRYPTO
  • CRYPTO EXCHANGES
  • BLOCKCHAIN
  • MINING
  • SCAM ALERT
  • PRESS RELEASE
  • HOME
  • BITCOIN
  • CRYPTO UPDATES
    • ALTCOIN
    • ETEREUM
    • NFT’s
    • CRYPTO PRICE ANALYSIS
  • LEARN CRYPTO
  • CRYPTO EXCHANGES
  • BLOCKCHAIN
  • MINING
  • SCAM ALERT
  • PRESS RELEASE
No Result
View All Result
Crypto Newsmart
No Result
View All Result

Verkle tree structure | Ethereum Foundation Blog

in Ethereum
Reading Time: 5 mins read
Verkle tree structure | Ethereum Foundation Blog
146
VIEWS
Share on Facebook

 

A Verkle tree is a commitment scheme that works similar to a Merkle tree, but has much smaller witnesses. It works by replacing the hashes in a Merkle tree with a vector commitment, which makes wider branching factors more efficient.

Thanks to Kevaundray Wedderburn for feedback on the post.

Contents

  • 1 Overview
  • 2 Layout of the verkle tree
    • 2.1 Commitment to the values leaf nodes
    • 2.2 Commitment of extension nodes
    • 2.3 Commitment of Internal nodes
  • 3 Insertion into the tree
  • 4 Shallower trees, smaller proofs

Overview

For details on how verkle trees work, see:

The aim of this post is to explain the concrete layout of the draft verkle tree EIP. It is aimed at client developers who want to implement verkle trees and are looking for an introduction before delving deeper into the EIP.

Verkle trees introduce a number of changes to the tree structure. The most significant changes are:

  • a switch from 20 byte keys to 32 byte keys (not to be confused with 32 byte addresses, which is a separate change);
  • the merge of the account and storage tries; and finally
  • The introduction of the verkle trie itself, which uses vector commitments instead of hashes.

As the vector commitment scheme for the verkle tree, we use Pedersen commitments. Pedersen commitments are based on elliptic curves. For an introduction to Pedersen commitments and how to use them as polynomial or vector commitments using Inner Product Argumentss, see here.

The curve we are using is Bandersnatch. This curve was chosen because it is performant, and also because it will allow efficient SNARKs in BLS12_381 to reason about the verkle tree in the future. This can be useful for rollups as well as allowing an upgrade where all witnesses can be compressed into one SNARK once that becomes practical, without needing a further commitment update.

The curve order/scalar field size of bandersnatch is p = 13108968793781547619861935127046491459309155893440570251786403306729687672801, which is a 253 bit prime. As a result of this, we can only safely commit to bit strings of at most 252 bits, otherwise the field overflows. We chose a branching factor (width) of 256 for the verkle tree, which means each commitment can commit to up to 256 values of 252 bits each (or to be precise, integers up to p – 1). We write this as Commit(v₀, v₁, …, v₂₅₅) to commit to the list v of length 256.

Layout of the verkle tree

One of the design goals with the verkle tree EIP is to make accesses to neighbouring positions (e.g. storage with almost the same address or neighbouring code chunks) cheap to access. In order to do this, a key consists of a stem of 31 bytes and a suffix of one byte for a total of 32 bytes. The key scheme is designed so that “close” storage locations are mapped to the same stem and a different suffix. For details please look at the EIP draft.

The verkle tree itself is then composed of two types of nodes:

  • Extension nodes, that represent 256 values with the same stem but different suffixes
  • Inner nodes, that have up to 256 children, which can be either other inner nodes or extension nodes.

The commitment to an extension node is a commitment to a 4 element vector; the remaining positions will be 0. It is:

C₁ and C₂ are two further commitments that commit to all the values with stem equal to stem. The reason we need to commitments is that values have 32 bytes, but we can only store 252 bits per field element. A single commitment would thus not be enough to store 256 values. So instead C₁ stores the values for suffix 0 to 127, and C₂ stores 128 to 255, where the values are split in two in order to fit into the field size (we’ll come to that later.)

The extension together with the commitments C₁ and C₂ are referred to as “extension-and-suffix tree” (EaS for short).

upload 11c3da539634c3490428842b8e330fee
Figure 1 Representation of a walk through a verkle tree for the key 0xfe0002abcd..ff04: the path goes through 3 internal nodes with 256 children each (254, 0, 2), one extension node representing abcd..ff and the two suffix tree commitments, including the value for 04, v₄. Note that stem is actually the first 31 bytes of the key, including the path through the internal nodes.

Commitment to the values leaf nodes

Each extension and suffix tree node contain 256 values. Because a value is 256 bits wide, and we can only store 252 bits safely in one field element, four bits would be lost if we simply tried so store one value in one field element.

To circumvent this problem, we chose to partition the group of 256 values into two groups of 128 values each. Each 32-byte value in a group is split into two 16-byte values. So a value vᵢ∈ 𝔹₃₂ is turned into v⁽ˡᵒʷᵉʳ⁾ᵢ ∈ 𝔹₁₆ and v⁽ᵘᵖᵖᵉʳ⁾ᵢ∈ 𝔹₁₆ such that v⁽ˡᵒʷᵉʳ⁾ᵢ ++ v⁽ᵘᵖᵖᵉʳ⁾ᵢ= vᵢ.

A “leaf marker” is added to the v⁽ˡᵒʷᵉʳ⁾ᵢ, to differentiate between a leaf that has never been accessed and a leaf that has been overwritten with 0s. No value ever gets deleted from a verkle tree. This is needed for upcoming state expiry schemes. That marker is set at the 129th bit, i.e. v⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ = v⁽ˡᵒʷᵉʳ⁾ᵢ + 2¹²⁸ if vᵢ has been accessed before, and v⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ = 0 if vᵢ has never been accessed.

The two commitments C₁ and C₂ are then defined as

c1 c2

Commitment of extension nodes

The commitment to an extension node is composed of an “extension marker”, which is just the number 1, the two subtree commitments C₁ and C₂, and the stem of the key leading to this extension node.

commitment

Unlike extension nodes in the Merkle-Patricia tree, which only contain the section of the key that bridges the parent internal node to the child internal node, the stem covers the whole key up to that point. This is because verkle trees are designed with stateless proofs in mind: if a new key is inserted that “splits” the extension in two, the older sibling need not be updated, which allows for a smaller proof.

Commitment of Internal nodes

Internal nodes have the simpler calculation method for their commitments: the node is seen as a vector of 256 values, that are the (field representation of the) root commitment of each of their 256 subtrees. The commitment for an empty subtree is 0. If the subtree is not empty, then the commitment for the internal node is

internal

where the Cᵢ are the children of the internal node, and 0 if a child is empty.

Insertion into the tree

Figure 2 is an illustration of the process of inserting a new value into the tree, which gets interesting when the stems collide on several initial bytes.

upload 5196292ae56f82a63cf260429315b736

Figure 2 Value v₁₉₂ is inserted at location 0000010000...0000 in a verkle tree containing only value v₁₂₇ at location 0000000000...0000. Because the stems differ at the third byte, two internal nodes are added until the differing byte. Then another “extension-and-suffix” tree is inserted, with a full 31-byte stem. The initial node is untouched, and C²₀ has the same value as C⁰₀ before the insertion.

Shallower trees, smaller proofs

The verkle tree structure makes for shallower trees, which reduces the amount of stored data. Its real power, however, comes from the ability to produce smaller proofs, i.e. witnesses. This will be explained in the next article.

 

Next Article: What Cryptocurrency to mine right now
Next Article: what is ethereum in depth
Next Article: What is a protocol?
Next Article:  Ethereum price
Next Article: Top 5 Crypto games play&Earn
Next Article: How today cryptocurrency & environment are interconnected?

Source link


  • Trending
  • Comments
  • Latest
Expert Bitcoin Price Predictions: From K to K in 2023, and Beyond

Expert Bitcoin Price Predictions: From $20K to $38K in 2023

1 February 2023
How Investigators Trace Crypto Criminals?

How Investigators Trace Crypto Criminals?

30 January 2023
How to trade cryptocurrency on Coinbase

How to trade cryptocurrency on Coinbase

31 January 2023
MoneyGram Partners With Circle To Enable USDC Cross-Border Stablecoin Transactions on Stellar (XLM) Blockchain

MoneyGram Partners With Circle To Enable USDC Cross-Border Stablecoin Transactions on Stellar (XLM) Blockchain

2 February 2023
How to trade cryptocurrency on Binance

How to trade cryptocurrency on Binance

27 January 2023
Sberbank Cover 1024x538 1

Russia’s Largest Bank to Launch Ethereum-Compatible DeFi Platform

5 February 2023
upload 7d22bc5d7be9c0d5d8f50161734559ae

KZG Ceremony Grant Round | Ethereum Foundation Blog

5 February 2023
Article Post Images 23

Bitcoin (BTC) Price to Surge 8x If This Scenario Plays Out – Here’s How and When

5 February 2023
crypto hacking

Hackers Stole $3.8 Billion From Crypto Firms in 2022, Says Chainalysis – Featured Bitcoin News

4 February 2023
ripple sec lawsuit

Ripple Vs SEC Update: Latest Hearing Offers Hope, XRP Gains Upper Hand

3 February 2023

  • Home
  • Disclaimer
  • Privacy Policy
  • Digital Millennium Copyright Act Policy (DMCA)
  • Cookie Privacy Policy
  • Terms and Conditions
  • Contact us
CRYPTO NEWSMART

Copyright © 2021 Crypto Newsmart.

No Result
View All Result
  • HOME
  • BITCOIN
  • CRYPTO UPDATES
    • ALTCOIN
    • ETEREUM
    • NFT’s
    • CRYPTO PRICE ANALYSIS
  • LEARN CRYPTO
  • CRYPTO EXCHANGES
  • BLOCKCHAIN
  • MINING
  • SCAM ALERT
  • PRESS RELEASE

Copyright © 2021 Crypto Newsmart.

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
  • bitcoinBitcoin(BTC)€21,152.17-2.34%
    BITCOIN
    24H : -2.34%
    Volume : €25,415,399,985.28
    Marketcap : €407,506,639,786.24
  • ethereumEthereum(ETH)€1,503.85-2.57%
    ETHEREUM
    24H : -2.57%
    Volume : €7,513,657,747.76
    Marketcap : €181,136,092,305.44
  • usdex-stablecoinUSDEX(USDEX)€0.995-0.96%
    USDEX
    24H : -0.96%
    Volume : €118,440.27
    Marketcap : €102,881,883,688.82
  • tetherTether(USDT)€0.9320.420%
    TETHER
    24H : 0.420%
    Volume : €34,494,852,884.69
    Marketcap : €63,127,939,919.15
  • binancecoinBNB(BNB)€300.26-2.33%
    BNB
    24H : -2.33%
    Volume : €937,863,814.50
    Marketcap : €40,491,244,847.95
  • usd-coinUSD Coin(USDC)€0.9300.280%
    USD COIN
    24H : 0.280%
    Volume : €2,491,708,601.34
    Marketcap : €38,933,277,035.98
  • rippleXRP(XRP)€0.369-3.07%
    XRP
    24H : -3.07%
    Volume : €897,646,353.69
    Marketcap : €18,732,078,914.79
  • binance-usdBinance USD(BUSD)€0.9320.500%
    BINANCE USD
    24H : 0.500%
    Volume : €8,546,203,443.97
    Marketcap : €15,115,063,408.58
  • cardanoCardano(ADA)€0.362-2.15%
    CARDANO
    24H : -2.15%
    Volume : €342,232,221.70
    Marketcap : €12,683,980,395.78
  • dogecoinDogecoin(DOGE)€0.085-4.09%
    DOGECOIN
    24H : -4.09%
    Volume : €859,317,511.76
    Marketcap : €11,693,200,912.06
  • okbOKB(OKB)€41.160.290%
    OKB
    24H : 0.290%
    Volume : €26,014,287.66
    Marketcap : €10,105,156,383.41
  • matic-networkPolygon(MATIC)€1.10-4.82%
    POLYGON
    24H : -4.82%
    Volume : €567,428,877.71
    Marketcap : €9,939,832,686.16
  • solanaSolana(SOL)€21.44-5.04%
    SOLANA
    24H : -5.04%
    Volume : €622,197,700.49
    Marketcap : €7,995,316,474.90
  • shiba-inuShiba Inu(SHIB)€0.000013-4.80%
    SHIBA INU
    24H : -4.80%
    Volume : €949,851,919.05
    Marketcap : €7,793,403,412.94
  • staked-etherLido Staked Ether(STETH)€1,503.51-2.36%
    LIDO STAKED ETHER
    24H : -2.36%
    Volume : €15,437,611.19
    Marketcap : €7,583,844,185.78
  • polkadotPolkadot(DOT)€6.15-3.40%
    POLKADOT
    24H : -3.40%
    Volume : €247,427,232.21
    Marketcap : €7,364,957,254.95
  • litecoinLitecoin(LTC)€88.66-2.79%
    LITECOIN
    24H : -2.79%
    Volume : €480,192,578.61
    Marketcap : €6,397,580,130.06
  • avalanche-2Avalanche(AVAX)€18.39-5.77%
    AVALANCHE
    24H : -5.77%
    Volume : €342,870,680.98
    Marketcap : €5,791,493,506.40
  • tronTRON(TRX)€0.059-1.98%
    TRON
    24H : -1.98%
    Volume : €468,404,899.03
    Marketcap : €5,366,684,892.66
  • uniswapUniswap(UNI)€6.29-6.58%
    UNISWAP
    24H : -6.58%
    Volume : €140,990,182.21
    Marketcap : €4,735,533,303.21
Manage Cookie Consent

We use cookies to optimise our website and our service.

Functional Always active
The technical storage or access is strictly necessary for the legitimate purpose of enabling the use of a specific service explicitly requested by the subscriber or user, or for the sole purpose of carrying out the transmission of a communication over an electronic communications network.
Preferences
The technical storage or access is necessary for the legitimate purpose of storing preferences that are not requested by the subscriber or user.
Statistics
The technical storage or access that is used exclusively for statistical purposes. The technical storage or access that is used exclusively for anonymous statistical purposes. Without a subpoena, voluntary compliance on the part of your Internet Service Provider, or additional records from a third party, information stored or retrieved for this purpose alone cannot usually be used to identify you.
Marketing
The technical storage or access is required to create user profiles to send advertising, or to track the user on a website or across several websites for similar marketing purposes.
Manage options Manage services Manage vendors Read more about these purposes
Preferences
{title} {title} {title}