Rust-Verkle

https://github.com/crate-crypto/rust-verkle

English Version

Verkle tree motivation

Stateless client is a key milestone in the Ethereum roadmap. The state of the existing Ethereum execution layer is stored in the MPT structure. Although MPT can also implement Stateless client, the corresponding Proof size is too large and cannot be used in one area. The block interval is broadcast to all nodes:

Verkle trees solve a key problem standing in the way of Ethereum being stateless-client-friendly: witness sizes. A witness accessing an account in today’s hexary Patricia tree is, in the average case, close to 3 kB, and in the worst case it may be three times larger. Assuming a worst case of 6000 accesses per block (15m gas / 2500 gas per access), this corresponds to a witness size of ~18 MB, which is too large to safely broadcast through a p2p network within a 12-second slot. Verkle trees reduce witness sizes to ~200 bytes per account in the average case, allowing stateless client witnesses to be acceptably small.

from https://eips.ethereum.org/EIPS/eip-6800

And Verkle Tree will greatly reduce the Proof size.

What is Verkle tree

Verkle tree ("Vector commitment" and "Merkle Trees") is a data structure based on Trie. The goal is to store a collection of KVs and provide the function of inserting, modifying and getting KVs efficiently, and can provide proof for any certain set of KVs, which proves the V corresponding to K is indeed this value or does not exist.

Commitment, Proof

Here is a simple science for readers who are not familiar with commitments and proofs.

In one scenario, Alice and Bob play a game:

• Alice: I know a polynomial
  $f(x)=a_0+a_{1}x+\cdots +a_{n-1}{x}^{n-1}$, and I can prove it to you
• Bob: I don’t know anything about
  $f(x)$, how can I verify it?
• Alice: Yes, now
  $f(x)$ is entirely up to me, and I can modify its coefficients at will. Therefore, I need to public a Commitment of
  $f(x)$ first, so that I cannot change
  $f(x)$ randomly.
• Bob: Yes, I first generate a random number
  $r$, but I won’t tell you this
  $r$, then select two points
  $G_1,G_2$ of BLS12-381, and calculate
  $(P_0,P_1,P_2\dots ,P_{n-1})=(G_1,r{G}_1,r^2{G}_1,\dots ,r^{n-1}{G}_1)$, and sends you the
  $n$ points on the elliptic curve. Because according to the elliptic curve discrete logarithm problem, there is no way to get the value of
  $r$ by having
  $rG$.
• Alice: OK, I calculated
  $P=f(r)G_1=a_0{G}_1+(a_1\cdot r)G_1+(a_2\cdot r^2)G_1+\cdots +(a_{n-1}{r}^{n-1})G_1=a_0{P}_0+a_1{P}_1+a_2{P}_2+\cdots +a_{n-1}{P}_{n-1}$, and then send
  $P$ points to you, then
  $P$ points are
  $f(x)$ commitment. As can be seen, although I don't know
  $r$, I can compute the commitment of any polynomial.
• Bob: OK, I will generate another challenge value (random number)
  $s$ and send this
  $s$ to you.
• Alice: I calculate
  $f(s)$, and
  $q(x)=\frac{f(x)-f(s)}{x-s}$, and calculate
  $Q=q(r)G_1$, I Send
  $f(s),Q$ to you. where
  $f(s)$ is the result and
  $Q$ is the proof of
  $f(s)$.
• Bob: I verify whether
  $e(f(r)G_1-f(s)G_1,G_2)=e(q(r)G_1,(r-s)G_2)$ is true. If it is true, it can prove
  $f(r)-f(s)=q(r)(r-s)$, I can most likely believe that you know
  $f(x)$.
  $e(G_1,G_2)$ is pairing, and some elliptic curves have this property, such as BLS12-381.

The above is a simplified description of KZG. For details, please refer to https://hackmd.io/DA-UGXFFRzCCznM1JBuZcA

To sum up, Bob does not know the coefficient

$a_i$ of

$f(x)$ in the end, but he believes that Alice knows

$f(x)$ with a high probability, so which

$f(x)$ does he believe Alice knows? That is, the one corresponding to the commitment

$P$.

Back to Verkle Tree, you don't need to know the state(whole KV pairs), you only need to know the state root in advance, similar to the commitment to all KV, and the relevant KVs' proof, you can verify that the relevant KVs are indeed under the Tree represented by this state root.

Structure of Verkle Tree

figure 1

A typical Verkle tree is shown in the figure above and contains 3 types of nodes. According to the naming in rust-verkle, they are Branch node, Stem node, and Leaf node. Note that although the values in node in the above figure are represented by the same characters, the values in different nodes are not necessarily equal. Among them,

$C$ represents the commitment of Branch node, which is a point on the elliptic curve.

$H_C$ represents the hash value of the Commitment, which is the element in the scalar field

${\mathbb{F}}_r$ on the elliptic curve.

$C_1,C_2,C_s$ respectively represent the Commitment of Stem node.

$K,V$ represent the actual data to be saved.

We can draw conclusions based on the above figure:

• The root node is the Branch node
• The child node of Branch node may be Branch node, which may be Stem node
• The parent node of Stem node has multiple child nodes, because if there is only one child node, it will be optimized into stem
• The child node of Stem node is Leaf node, and the parent node of Leaf node is Stem node
• There are at most 256 child nodes under a certain Branch/Stem node
• Because the key of Leaf node is represented by [u8;32], the deepest of the entire tree is 32

other information:

• The key value of the Stem node is 31 bytes. Its Path in the Tree can only obtain the first part to the entire value of the key (depending on its depth), so additional field storage is required.
• Based on the 31 bytes of Leaf node, plus the index of its position under the Stem node, 32 bytes can be formed, which can be used as the key of Leaf node
• Knowing the key of the Stem node and its depth d, you can get its path: path = key[0..d]

question:

• What is the function of Stem node? This is an optimization for trie. There is also a similar optimization in MPT: when consecutive nodes in the trie have only one child node, they can be compressed into one node to represent them, which can reduce the depth of the tree.
• For example, when using 2-ary to represent 256-ary, the following figure is a simulation of the actual situation, because all keys are obtained through pedersen hash of address and other information, which can be regarded as random number, so leaf nodes are evenly distributed in each branch starting from the root. Assuming that there is no Stem node, and the depth is after 3-4, most nodes will appear as shown in the figure above, that is, they will degenerate into a Linked list.
  Some data show that in actual situations, the average depth of the Verkle tree is 3.8, which is normal,
  ${256}^{3.8}\approx 1.4\text{B}$, and the number of Ethereum addresses is 0.268B, the capacity is sufficient.
• Why does the second-to-last node start to fork again (the so-called suffix trie)?
  Interesting question, I am still discussing it with the ETH R&D team responsible for the verkle tree.

I do have a question about the design of verkle trees, here a binary tree is used to represent a 256-ary tree. My understanding is that since all keys are the results of pedersen_hash and are relatively random, the keys will be evenly distributed in each branch starting from the root. In actual situations, the structure of the tree should be like Figure 1: the first 3-4 layers are almost a balanced tree, and the subsequent nodes will degenerate into linked lists. Then use stem node to represent nodes that degenerate into linked lists for optimization. My question is, 1. Why not put the nonce, balance, and even some storage slots of the same address under the same stem node, because when a transaction occurs, these fields are relatively easy to update at the same time, and this can reduce the number of required to update stem nodes and branch nodes. The actual situation is that they will be randomly distributed in different stem nodes. 2. Since all leaf nodes will be randomly distributed, why is Figure 2 chosen for the final layout, which branches into 256 child nodes after the stem node? I think the actual situation is that under a stem node, in most cases only one child has a value, and the others are Null.

• The disadvantage of the Stem node is that if Leaf nodes 2 and 4, or 3 and 4 appear at the same time, it will not play a role in reducing the depth, and it is a possible DDoS attack surface. And you don’t need to have the private key of the relevant address to attack. For example, if I directly transfer a small amount of ether as a balance to the accounts represented by Leaf nodes 2 and 3, the Verkle Tree can be deepened. The solution is that the key is not generated directly based on the account address, but is hashed and reflected in EIP 6800.
• Why is the Key of Stem node designed to be 31 bytes, and Stem node cannot be root, so at least its first byte can be obtained directly from the Path of Stem without saving it? My understanding is that this is a difference in implementation. This is how it is implemented in memoryDB: [u8;31]
• I saw in some information before that with the Verkle Tree, there is no need to create an additional Storage tree for the contract account under the account. How is this achieved? The potential space of the Verkel tree is very large (
  $2^{256}$), so the storage tree is embedded into the Verkle tree in the following form.

def get_tree_key_for_storage_slot(address: Address32, storage_key: int):
     if storage_key < (CODE_OFFSET - HEADER_STORAGE_OFFSET):
         pos = HEADER_STORAGE_OFFSET + storage_key
     else:
         pos = MAIN_STORAGE_OFFSET + storage_key
     return get_tree_key(
         address,
         pos // VERKLE_NODE_WIDTH,
         pos % VERKLE_NODE_WIDTH
     )

Verkle Tree based on Memory

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/database/memory_db.rs#L6-L11
pub struct MemoryDb {
    pub leaf_table: HashMap<[u8; 32], [u8; 32]>,
    pub stem_table: HashMap<[u8; 31], StemMeta>,
    pub branch_table: HashMap<Vec<u8>, BranchChild>,
}

pub struct StemMeta {
    pub c_1: Element,
    pub hash_c1: Fr,

    pub c_2: Element,
    pub hash_c2: Fr,

    pub stem_commitment: Element,
    pub hash_stem_commitment: Fr,
}

pub enum BranchChild {
    Stem([u8; 31]),
    Branch(BranchMeta),
}

pub struct BranchMeta {
    pub commitment: Element,
    pub hash_commitment: Fr,
}

Three types of nodes correspond to three tables, leaf_table corresponds to the KV pair of 32 bytes, stem_table corresponds to the key of 31 bytes and the value of

$C_1,C_2,C_s,H_{C_1},H_{C_2},H_{C_s}$ . branch_table corresponds to variable-length bytes (Path) as the key. The node under the Path may be Stem or Branch.

The above picture is the result of printing Figure 1. You can see 5 leaf nodes, 31 branch nodes, and 4 stem nodes. Note that branch_table contains 31 branch nodes and 4 stem nodes.

Method of Verkle Tree

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/lib.rs#L17-L50
pub type Key = [u8; 32];
pub type Value = [u8; 32];

pub trait TrieTrait {
    /// Inserts multiple values into the trie
    /// If the number of items is below FLUSH_BATCH, they will be persisted
    /// atomically
    /// This method will implicitly compute the new root
    fn insert(&mut self, kv: impl Iterator<Item = (Key, Value)>);

    /// Inserts a single value
    /// This method will implicitly compute the new root
    fn insert_single(&mut self, key: Key, value: Value) {
        self.insert(vec![(key, value)].into_iter())
    }

    /// Gets the value at the `Key` if it exists
    /// Returns an none if it does not exist
    /// TODO: Find out if this method is ever needed
    fn get(&self, key: Key) -> Option<Value>;

    /// Returns the root of the trie
    fn root_hash(&self) -> Fr;

    /// Returns the root commitment of the trie
    fn root_commitment(&self) -> Element;

    /// Creates a verkle proof over many keys
    fn create_verkle_proof(
        &self,
        key: impl Iterator<Item = Key>,
    ) -> Result<proof::VerkleProof, ProofCreationError>;
}

In fact, Ethereum's State Trie only needs to implement TrieTrait, that is, it only needs to provide the above functions to the outside world to complete the task, regardless of whether the underlying layer uses Verkle Tree or SALT. Here we first analyze how it will be implemented if it is a Verkle Tree.

• insert, given a set of KV pairs, save them. In MemoryDB, insert into leaf_table
• insert_single, call insert directly
• get, given a K, returns V. In MemoryDB, get the KV pair in leaf_table
• root_hash, the hash of root node commitment
• root_commitment, root node commitment
• create_verkle_proof, given a set of K, returns a VerkleProof

In addition to insert_single, let’s take a look at the implementation of the remaining 5 interfaces.

First, let’s take a look at the definition of Trie. Trie has two fields, storage and committer. Their types are both generic. There are no requirements for the Storage type. The PolyCommit type also needs to implement the Committer trait. Let’s focus on storage first.

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/trie.rs#L12-L15
pub struct Trie<Storage, PolyCommit: Committer> {
    pub storage: Storage,
    pub committer: committer,
}

get

For the Storage type that implements the ReadWriteHigherDb trait, because there is a get_leaf interface in the ReadWriteHigherDb trait, self.storage.get_leaf(key) is called directly

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/trie.rs#L26-L28
impl<S: ReadWriteHigherDb, P: Committer> TrieTrait for Trie<S, P> {
    fn get(&self, key: crate::Key) -> Option<crate::Value> {
        self.storage.get_leaf(key)
    }
}

So how does MemoryDb implement get_leaf? You can get it directly from the HashMap get of leaf_table in MemoryDb.

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/database.rs#L8
pub trait ReadWriteHigherDb: ReadOnlyHigherDb + WriteOnlyHigherDb {}

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/database/memory_db.rs#L59-L63
impl ReadOnlyHigherDb for MemoryDb {
    fn get_leaf(&self, key: [u8; 32]) -> Option<[u8; 32]> {
        self.leaf_table
            .get(&key)
            .map(|val| val.to_vec().try_into().unwrap())
    }
}

I think there is no need to convert types. It can be achieved like this:

    fn get_leaf(&self, key: [u8; 32]) -> Option<[u8; 32]> {
        self.leaf_table.get(&key).copied()
    }

the complexity
In the implementation of MemoryDB, on average get is a

$\mathcal{O}(1)$ operation, because the get in HashMap is directly called.

root_hash and root_commitment

Similarly, for the Trie that implements the ReadWriteHigherDb trait for the S type, because there is a get_branch_meta interface in the ReadWriteHigherDb trait, you can directly call self.storage.get_branch_meta and enter the path of the root node: &[] to obtain the meta information of the root node. Including commitment and hash.

impl<S: ReadWriteHigherDb, P: Committer> TrieTrait for Trie<S, P> {
    fn root_hash(&self) -> Fr {
        // This covers the case when the tree is empty
        // If the number of stems is zero, then this branch will return zero
        let root_node = self
            .storage
            .get_branch_meta(&[])
            .expect("this should be infallible as every trie should have a root upon creation");
        root_node.hash_commitment
    }
    
    fn root_commitment(&self) -> Element {
        // TODO: This is needed for proofs, can we remove the root hash as the root?
        let root_node = self.storage.get_branch_meta(&[]).unwrap();
        root_node.commitment
    }
}

impl ReadOnlyHigherDb for MemoryDb {
    fn get_branch_meta(&self, key: &[u8]) -> Option<BranchMeta> {
        let branch_child = match self.branch_table.get(key) {
            Some(b_child) => b_child,
            None => return None,
        };

        match branch_child {
            BranchChild::Stem(stem_id) => panic!(
                "expected branch meta data, however under this path there is a stem: {}",
                hex::encode(stem_id)
            ),
            BranchChild::Branch(b_meta) => Some(*b_meta),
        }
    }
}

And how does MemoryDb implement get_branch_meta? Because the HashMap of branch_table is saved, you can get it directly. However, as described before, there are two types of value, one is Branch and the other is Stem. If it is Stem, panic directly because the parameter you gave is Stem. path, and then you want to get Branch here.

the complexity
In the implementation in MemoryDB, on average root_hash and root_commitment are a

$\mathcal{O}(1)$ operation, because the get in HashMap is directly called

insert

Insert will be more complicated, we will analyze it by combining the schematic diagram and code.

From the implementation below, you can see that the implementation involves two processes. Each KV pair to be inserted is converted into a series of small operations consisting of instructions, and then the instructions are applied to the Tree.

impl<S: ReadWriteHigherDb, P: Committer> TrieTrait for Trie<S, P> {
    fn insert(&mut self, kv: impl Iterator<Item = (crate::Key, crate::Value)>) {
        for (key_bytes, value_bytes) in kv {
            let ins = self.create_insert_instructions(key_bytes, value_bytes);
            self.process_instructions(ins);
        }
    }
}

However, it should be noted that the processing of KV here is serial. Only one KV can be processed after updating one KV. An optimization idea is to preprocess these KVs in advance, and try to allow KVs with a common path to be processed at the same time. Processing, so that the number of updates to stem nodes and branch nodes on the public path can be reduced.

There are three types of instructions, UpdateLeaf, ChainInsert, InternalNodeFallThrough

pub enum Ins {
    UpdateLeaf {
        ...
    },

    ChainInsert {
        ...
    },

    InternalNodeFallThrough {
        ...
    },
}

UpdateLeaf

pub(crate) type BranchId = Vec<u8>;

UpdateLeaf {
    key: [u8; 32],
    new_leaf_value: [u8; 32],
    depth: u8,
    branch_id: BranchId,
    branch_child_index: u8,
},

Updating the leaf node will update all nodes on the path from the root to the leaf node:

1. Update the value of the leaf node
2. Update one of
   $C_1,C_2$ of its corresponding stem node, and the corresponding hash
3. Update
   $C$ and
   $H_C$ of the stem node’s parent nodes (branch node)

Information included:

• key, new_leaf_value, used for the first update
• depth, the depth of the leaf node
• branch_id, the path of the stem node corresponding to the leaf node
• branch_child_index, the position of the leaf node under the stem node.

A scenario of UpdateLeaf is as shown below, assuming that leaf node 6 is added based on the existing tree:

Let’s first look at how the UpdateLeaf instruction is processed in process_instructions:

impl<Storage: ReadWriteHigherDb, PolyCommit: Committer> Trie<Storage, PolyCommit> {
    pub fn process_instructions(&mut self, instructions: Vec<Ins>) {
        for ins in instructions.into_iter().rev() {
            match ins {            
                Ins::UpdateLeaf {
                    key,
                    new_leaf_value,
                    depth,
                    branch_id,
                    branch_child_index,
                } => {
                    let leaf_update = match self.update_leaf_table(key, new_leaf_value, depth) {
                        Some(leaf_update) => leaf_update,
                        None => {
                            // No value was updated, early exit
                            return;
                        }
                    };

                    let stem_update = self.update_stem_table(leaf_update, depth);

                    self.update_branch_table(stem_update, branch_id, branch_child_index, depth);
                }
                ...
            }
        }
    }
    ...
}

As shown in the figure above, if the leaf node has a value before, update_leaf_table, update_stem_table, update_branch_table are called in sequence. If the return is empty, only update_leaf_table is needed, which feels a bit strange.

Look at the implementation of these three updates:

update_leaf_table:

     // Store the leaf, we return data on the old leaf, so that we can do the delta optimization
     //
     // If a leaf was not updated, this function will return None
     // else Some will be returned with the old value
     fn update_leaf_table(
         &mut self,
         key: [u8; 32],
         value: [u8; 32],
         depth: u8,
     ) -> Option<LeafUpdated> {
         let old_val = match self.storage.insert_leaf(key, value, depth) {
             Some(vec) => {
                 // Check if they have just inserted the previous value
                 // if so, we exit early and return None
                 if vec == value {
                     return None;
                 }
                 Some(vec)
             }
             None => None,
         };

         Some(LeafUpdated {
             old_val,
             new_value: value.to_vec(),
             key: key.to_vec(),
         })

         // Storing a leaf means we need to change the stem table too
     }

impl WriteOnlyHigherDb for MemoryDb {
     fn insert_leaf(&mut self, key: [u8; 32], value: [u8; 32], _depth: u8) -> Option<Vec<u8>> {
         self.leaf_table
             .insert(key, value)
             .map(|old_val| old_val.to_vec())
     }
}

The insert_leaf method of storage is called. Then the insert of HashMap is called. If there is a value, return the value; if there is no value, return none.

The summary is update_leaf_table if leaf node

• The new KV is the same as the previous KV
• V did not exist before this K

It returns None, and UpdateLeaf only executes update_leaf_table. Otherwise, return the update result: LeafUpdated, and continue to execute update_stem_table, update_branch_table.

update_stem_table

• Why only one commitment is needed in the branch node, but two commitments are needed in the stem node. Aren't they both committed to 256 child nodes? Because the objects being promised are different. The child node of a branch node is a branch node or a stem node, and the committed object is the hash value of the commitment of the branch node or stem node. The value range is [0, order), and you can commit directly. The child node of the stem node is KV, the committed object is V, the value range is [0,2^256), and the part beyond the order cannot be committed. Therefore two commitments are required. How to divide it? A natural idea is to put the [0,127] bit of the 256 child nodes V in the first
  $C_1$, and the [128,255] bit in
  $C_2$. However, if you do this, as long as a certain value in V is updated, it will This results in the need to update
  $C_1$,
  $C_2$. Therefore, different partitioning methods are used:
  $C_1$ is used for the commitment of V with index 0-127,
  $C_2$ is used for the commitment of V with index 128-255. The specific implementation is:

There are a total of 256 leaf nodes

$V_0$~

$V_{255}$ under a stem node, each

$K_i,V_i$, assuming [u8; 32], then:

• Vi_l = Fr::from_le_bytes_mod_order(V_i[0..=15]) + 2^128
• Vi_h = Fr::from_le_bytes_mod_order(V_i[16..=31])
• stem: [u8;31] = Ki[0..=30]

If the node with index i does not exist, Vi uses 0 instead.

Assume that the Commitment base is

$(G_0,G_1,\dots ,G_{255})$. In fact, all

$C$ of branch nodes and

$C_1$ and

$C_2$ of stem nodes use the same set of Commitment base. Then the calculation formula is:

Assume that the Commitment base is

$(G_0,G_1,\dots ,G_{255})$. In fact, all

$C$ of branch nodes and

$C_1$ and

$C_2$ of stem nodes use the same set of Commitment base .Then the calculation formula is:

$$\begin{array}{rl}{C}_1& =\sum _{i=0}^{127}(V_i\mathrm{\_}l\cdot G_{2i}+V_i\mathrm{\_}h\cdot G_{2i+1})\\ C_2& =\sum _{i=0}^{127}(V_{i+128}\mathrm{\_}l\cdot G_{2i}+V_{i+128}\mathrm{\_}h\cdot G_{2i+1})\\ H_C& =\text{group\_to\_field}(C)\\ C_{stem}& =1\cdot G_0+\text{stem}\cdot G_1+H_{C_1}\cdot G_2+H_{C_2}\cdot G_3\end{array}$$

The calculation method of

$C_{stem}$ is also the source of the green node in the figure below,

The calculation method of

$C_{stem}$ is also the source of the green node in the figure below,

from https://blog.ethereum.org/2021/12/02/verkle-tree-structure

I won’t post all the specific codes, there are quite a few, you can go here to view them yourself:
https://github.com/crate-crypto/rust-verkle/blob/e07b17b0538fcd227c221d2388e5468417116f00/verkle-trie/src/trie.rs#L537-L675

It should be noted that the additive homomorphism of points on the elliptic curve is used for optimization. Assume that

$V_1$ is updated, then:

$C_1^{\prime }=C_1+(V_1\mathrm{\_}{l}^{\prime }-V_1\mathrm{\_}l)\cdot G_2+(V_1\mathrm{\_}{h}^{\prime }-V_1\mathrm{\_}h)\cdot G_3$

$C_2^{\prime }=C_2$

$C_{stem}^{\prime }=C_{stem}+(H_{C_1}^{\prime }-H_{C_1})\ast G_2$

Then the following is my step-by-step calculation of

$C_1,C_2,C_{stem}$ and the equality in the updated trie based on the above formula:
https://github.com/flyq/verkle_tree_example/blob/da877d33309ee036661c4408a519b27357dbd335/src/main.rs#L14-L47

Finally, call insert_stem to insert directly on the stem_table of MemoryDb:

     fn insert_stem(&mut self, key: [u8; 31], meta: StemMeta, _depth: u8) -> Option<StemMeta> {
         self.stem_table.insert(key, meta)
     }

update_branch_table

$$\begin{array}{rl}{C}_{branch}& =\sum _{i=0}^{255}{H}_i\cdot G_i\\ H_i& =\text{group\_to\_field}(C_i)\end{array}$$

Where

$C_i$ represents the commitment of the child node under the branch node, which may be a branch node or a stem node.

    fn update_branch_table(
        &mut self,
        stem_update: StemUpdated,
        branch_id: BranchId,
        branch_index: u8,
        depth: u8,
    ) -> Fr {
        let old_stem_hash = stem_update.old_val.unwrap_or_else(Fr::zero);
        let new_stem_hash = stem_update.new_val;
        let delta = new_stem_hash - old_stem_hash;

        let old_branch_comm = self.storage.get_branch_meta(&branch_id).unwrap().commitment;
        let delta_comm = self.committer.scalar_mul(delta, branch_index as usize);
        let updated_branch_comm = old_branch_comm + delta_comm;
        let hash_updated_branch_comm = group_to_field(&updated_branch_comm);

        // Update the branch metadata

        self.storage.insert_branch(
            branch_id.clone(),
            BranchMeta {
                commitment: updated_branch_comm,
                hash_commitment: hash_updated_branch_comm,
            },
            depth,
        );
        let mut branch_child_id = branch_id;
        branch_child_id.push(branch_index);
        self.storage
            .add_stem_as_branch_child(branch_child_id, stem_update.stem, depth);

        hash_updated_branch_comm
    }

The above code implementation also takes advantage of the additive homomorphism of elliptic curve points:

$C_{branch}^{\prime }=C_{branch}+(H_i^{\prime }-H_i)G_i$

Then the following is my step-by-step calculation of the equality between

$C_{branch}$ and trie based on the original formula:

https://github.com/flyq/verkle_tree_example/blob/d4fdd7f5565db9bcb5aaabe861c549847063598e/src/main.rs#L78-L112

InternalNodeFallThrough

    InternalNodeFallThrough {
        branch_id: BranchId,
        branch_child_index: u8,
        child: BranchId,
        old_child_value: Option<Meta>,
        depth: u8,
    },

               Ins::InternalNodeFallThrough {
                    branch_id,
                    branch_child_index,
                    child,
                    depth,
                    old_child_value,
                } => {
                    let new_branch_meta = self.storage.get_branch_meta(&child).unwrap();
                    let new_hash_comm = new_branch_meta.hash_commitment;

                    let old_hash_comm = match old_child_value {
                        Some(old_branch_meta) => old_branch_meta.into_branch().hash_commitment,
                        None => Fr::zero(),
                    };

                    let delta = new_hash_comm - old_hash_comm;
                    let delta_comm = self
                        .committer
                        .scalar_mul(delta, branch_child_index as usize);

                    let old_parent_branch_metadata =
                        self.storage.get_branch_meta(&branch_id).unwrap();

                    let old_branch_comm = old_parent_branch_metadata.commitment;
                    let updated_comm = old_branch_comm + delta_comm;
                    let hash_updated_comm = group_to_field(&updated_comm);

                    self.storage.insert_branch(
                        branch_id,
                        BranchMeta {
                            commitment: updated_comm,
                            hash_commitment: hash_updated_comm,
                        },
                        depth,
                    );
                }

This is used to update C and Hc of a special type of branch node. The child nodes of this type of branch node are also branch nodes, not stem nodes. And after the trie has updated the child nodes of the branch node, the current branch node is updated.

ChainInsert

    ChainInsert {
        starting_depth: u8,
        chain_insert_path: Vec<u8>,
        parent_branch_node: BranchId,
        child_index: u8,
        old_leaf_index: u8,
        new_leaf_key: [u8; 32],
        new_leaf_value: [u8; 32],
        new_leaf_index: u8,
    },

This instruction is used to update a series of branch nodes under a certain path. I won’t post the source code, which is in: https://github.com/crate-crypto/rust-verkle/blob/e07b17b0538fcd227c221d2388e5468417116f00/verkle-trie/src/trie.rs#L362-L485

create_verkle_proof

    fn create_verkle_proof(
        &self,
        keys: impl Iterator<Item = [u8; 32]>,
    ) -> Result<crate::proof::VerkleProof, crate::errors::ProofCreationError> {
        use crate::proof::prover;
        prover::create_verkle_proof(&self.storage, keys.collect())
    }
    
pub fn create_verkle_proof<Storage: ReadOnlyHigherDb>(
    storage: &Storage,
    keys: Vec<[u8; 32]>,
) -> Result<VerkleProof, ProofCreationError> {
    if keys.is_empty() {
        return Err(ProofCreationError::EmptyKeySet);
    }
    let (queries, verification_hint) = create_prover_queries(storage, keys);

    // Commitments without duplicates and without the root, (implicitly) sorted by path, since the queries were
    // processed by path order
    let root_query = match queries.first() {
        Some(query) => query,
        None => return Err(ProofCreationError::ExpectedOneQueryAgainstRoot),
    };

    let root_comm = root_query.commitment;

    let comms_sorted: Vec<_> = queries
        .iter()
        // Filter out the root commitment
        .filter(|query| query.commitment != root_comm)
        // Pull out the commitments from each query
        .map(|query| query.commitment)
        // Duplicate all commitments
        .dedup()
        .collect();

    let mut transcript = Transcript::new(b"vt");
    let proof = MultiPoint::open(CRS.clone(), &PRECOMPUTED_WEIGHTS, &mut transcript, queries);

    Ok(VerkleProof {
        comms_sorted,
        verification_hint,
        proof,
    })
}    

verkle proof relies on the implementation of IPA

ipa-multipoint

pub struct IPAProof {
     pub(crate) L_vec: Vec<Element>,
     pub(crate) R_vec: Vec<Element>,
     pub(crate) a: Fr,
}

Let’s deduce the create function in ipa-multipoint/src/ipa.rs:

parameter:

• transcript, used for Fiat-Shamir Transform, that is, the interactive part in IPA (generating random challenge values) is replaced by random oracle. The transcript plays the role of random oracle, and the verifier can also obtain the corresponding challenge by following the same steps. value, eliminating the need for transcript transmission
• crs, Common Reference String, used here to save the base corresponding to Pedersen commitments, that is, 256 + 1 linearly independent point Element
• a_vec, vector a
• a_comm, the commitment of vector a, equal to
  $\sum _{i=0}^{n-1}{a}_i{G}_i$
• b_vec, vector b
• input_point, the value of the polynomial argument, only used for transcript

logic:

• $out\mathrm{\_}point=\overrightarrow{a}\cdot \overrightarrow{b}$
• $Q=w\cdot Q$
• $C_{L_i}=a_R\cdot G_L+a_R\cdot b_L\cdot Q$
• $C_{R_i}=a_L\cdot G_R+a_L\cdot b_R\cdot Q$
• $L=(C_{L_0},C_{L_1},\dots ,C_{L_{rounds}})$
• $R=(C_{R_0},C_{R_1},\dots ,C_{R_{rounds}})$
• $a=a_L+x\cdot a_R$
• $b=b_L+x^{-1}{b}_R$
• $G=G_L+x^{-1}{G}_R$

Output:
proof:

$L,R,a[0]$

verify function

parameter:

• transcript, same as create
• crs, same as create
• b, same as b_vec of create
• a_comm, same as create
• input_point, input_point
• output_point, the result, is equal to f(input_point), also equal to
  $\overrightarrow{a}\cdot \overrightarrow{b}$

Compared with create, the parameters include less vector a and more output_point.

logic:

• $a\mathrm{\_}comm=a\mathrm{\_}comm+w\cdot Q\cdot output\mathrm{\_}point$
• $a\mathrm{\_}comm=a\mathrm{\_}comm+C_{L_i}\cdot x_i+C_{R_i}\cdot x^{-1}$
• $G_i=G_{L_{i-1}}+x_i^{-1}{G}_{R_{i-1}}$
• $b_i=b_{L_{i-1}}+x_i^{-1}{b}_{R_{i-1}}$
• $a\mathrm{\_}comm?=G_n[0]\cdot proof.a+proof.a\cdot b_n[0]\cdot w\cdot Q$

The summary of the above is:

• $\mathcal{P}$ knows
  $\overrightarrow{a}$,
  $\overrightarrow{b}$,
• $\mathcal{V}$ knows
  $\overrightarrow{b}$, doesn’t know (don’t want to know)
  $\overrightarrow{a}$
• base is
  $\overrightarrow{G}=(G_0,G_1,\cdots ,G_{n-1})$ and
  $U$

process:

• $C_a=\overrightarrow{a}\cdot \overrightarrow{G}$
• $U=w\cdot U$
• $C_0=C_a+\overrightarrow{a}\cdot \overrightarrow{b}U$
• $C_{L1}={\overrightarrow{a}}_{R0}\cdot {\overrightarrow{G}}_{L0}+{\overrightarrow{a}}_{R0}\cdot {\overrightarrow{b}}_{L0}U$
• $C_{R1}={\overrightarrow{a}}_{L0}\cdot {\overrightarrow{G}}_{R0}+{\overrightarrow{a}}_{L0}\cdot {\overrightarrow{b}}_{R0}U$
• $C_1=C_0+x_1{C}_{L1}+x_1^{-1}{C}_{R1}$

Until

$k=\log n$:

• ${\overrightarrow{a}}_k={\overrightarrow{a}}_{Lk-1}+x_k{\overrightarrow{a}}_{Rk-1}$
• ${\overrightarrow{b}}_k={\overrightarrow{b}}_{Lk-1}+x_k^{-1}{\overrightarrow{b}}_{Rk-1}$
• $C_{Lk}={\overrightarrow{a}}_{Rk-1}\cdot {\overrightarrow{G}}_{Lk-1}+{\overrightarrow{a}}_{Rk-1}\cdot {\overrightarrow{b}}_{Lk-1}U$
• $C_{Rk}={\overrightarrow{a}}_{Lk-1}\cdot {\overrightarrow{G}}_{Rk-1}+{\overrightarrow{a}}_{Lk-1}\cdot {\overrightarrow{b}}_{Rk-1}U$
• $C_k=C_{k-1}+x_k{C}_{Lk}+x_k^{-1}{C}_{Rk}$

also,

• ${\overrightarrow{a}}_k,{\overrightarrow{G}}_k$ are both of length 1

$C_a,{\overrightarrow{a}}_k,\overrightarrow{a}\cdot \overrightarrow{b},{\overrightarrow{C}}_L,{\overrightarrow{C}}_R$ sent to

$\mathcal{V}$

$\mathcal{V}$ Verification:

• $C_k=C_a+\overrightarrow{a}\cdot \overrightarrow{b}U+\sum _{i=1}^k(x_i{C}_{Li}+x_i^{-1}{C}_{Ri})$
• $C_k\stackrel{\text{?}}{=}{\overrightarrow{a}}_k[0]\cdot {\overrightarrow{G}}_k[0]+{\overrightarrow{a}}_k[0]{\overrightarrow{b}}_k[0]U$

verify_multiexp:

• $\sum _{i=1}^k(x_i{C}_{Li}+x_i^{-1}{C}_{Ri})+C_a+(\overrightarrow{a}\cdot \overrightarrow{b}-{\overrightarrow{a}}_k[0]{\overrightarrow{b}}_k[0])\cdot U-{\overrightarrow{a}}_k[0]\cdot {\overrightarrow{G}}_k[0]\stackrel{\text{?}}{=}0$

MultiPointProof

pub struct MultiPointProof {
     open_proof: IPAProof,
     g_x_comm: Element,
}

pub struct PrecomputedWeights {
     // This stores A'(x_i) and 1/A'(x_i)
     barycentric_weights: Vec<Fr>,
     // This stores 1/k for k \in [-255, 255]
     inverted_domain: Vec<Fr>,
}

• PrecomputedWeights.barycentric_weights: In the verkle tree scenario, there are 256+256 values,
  $A^{\prime }(0),A^{\prime }(1),\dots ,A^{\prime }(255),\frac{1}{A^{\prime }(0)},\frac{1}{A^{\prime }(1)},\dots ,\frac{1}{A^{\prime }(255)}$,
• PrecomputedWeights.inverted_domain: In the verkle tree scenario, there are 255+255 values,
  $1,\frac{1}{2},\frac{1}{3},\dots ,\frac{1}{255},-1,-\frac{1}{2},-\frac{1}{3},\dots ,-\frac{1}{255}$

pub struct LagrangeBasis {
     // We assume that the domain starts at zero,
     // so we only need to supply the upperbound
     domain: usize,
     values: Vec<Fr>,
}

For the polynomial

$f(x)$ obtained by Lagrange interpolation by:

$(0,f(0)),(1,f(1)),(2,f(2)),\dots ,(255,f(255))$:

• LagrangeBasis.domain is 256
• LagrangeBasis.values is
  $(f(0),f(1),f(2),\dots ,f(255))$

Methods:

• divide_by_linear_vanishing, computes new polynomial
  $q(x)=\frac{f(x)-f(x_i)}{x-x_i}$
• evaluate_in_domain, when
  $x_i\in \{0,1,\dots ,255\}$, directly take
  $f(x_i)$
• evaluate_lagrange_coefficients, when
  $x_i$ is not in domain, return new LagrangeBasis,
  $f(z)=A(z)\sum _{i=0}^{N-1}\frac{f(i)}{A^{\prime }(x_i)(z-x_i)}$,
  • $A(z)=\prod _{i=0}^{255}(z-i)$
  • a vector, which contains:
    $re{s}_i=\frac{A(z)}{A^{\prime }(i)(z-i)}$

pub struct ProverQuery {
     pub commitment: Element,
     pub poly: LagrangeBasis, // TODO: Make this a reference so that upstream libraries do not need to clone
     // Given a function f, we use z_i to denote the input point and y_i to denote the output, ie f(z_i) = y_i
     pub point: usize,
     pub result: Fr,
}

After reading the previous dependency data structure, let’s see how open is implemented.
open() -> MultiPointProof

enter:

• crs, base of Pedersen promise
• precomp, precompute some
  $A^{\prime },+-\frac{1}{i}$
• transcript, for Fait-Shamir transformation
• queries, an array of length
  $t$, representing
  $t$ polynomials
  $f_i(x)$

logic:

• Get a random r and generate
  $1,r,r^2,r^3,\dots ,r^{t-1}$
• Grouping:
  $(i,vec\{(r^i,f_i(x)),(r^j,f_j(x)),\cdots \})$, where
  $i\in [0..t]$
• aggregated_polynomial has 256 items, assumed to be
  $h_i(x)$
• $h_i(j)=f_i(j)\cdot r^i$
• $h_i(x)=A(x)\cdot r^i\cdot \sum _{j=0}^{255}{f}_i(j)\cdot \frac{1}{A^{\prime }\cdot (x-j)}$

Polynomials opened for the same point:
HashMap<point, Vec<(f_i, r^i)>> performs aggregation:

• $ag\mathrm{\_}poly=\sum _i{r}^i\cdot \overrightarrow{f_i}$

Then we have a Vector consisting of

$(point,ag\mathrm{\_}poly)$

Use

$d_i(x)$ to represent

$ag\mathrm{\_}poly$

$g(x)=\sum _{i=0}^h\frac{d_i(x)-d_i(point)}{x-point}$

h is equal to how many different points there are, and is also the length of the Vector above.

$C_g=\sum _{i=0}^{255}g(i)\cdot G_i$

Reference

• https://blog.ethereum.org/2021/12/02/verkle-tree-structure
• https://vitalik.eth.limo/general/2021/06/18/verkle.html
• https://ihagopian.com/posts/anatomy-of-a-verkle-proof
• https://verkle.dev
• https://verkle.info
• https://eips.ethereum.org/EIPS/eip-6800
• https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html
• https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html

Chinese Version

Verkle tree 的动机

Stateless 客户端是以太坊路线图里面的关键里程碑，现有的以太坊 execution layer 的状态存储在 MPT 结构里面，虽然 MPT 也能实现 Stateless 客户端，但是对应的 Proof size 太大了，无法在一个区块的时间间隔广播到所有节点：

Verkle trees solve a key problem standing in the way of Ethereum being stateless-client-friendly: witness sizes. A witness accessing an account in today’s hexary Patricia tree is, in the average case, close to 3 kB, and in the worst case it may be three times larger. Assuming a worst case of 6000 accesses per block (15m gas / 2500 gas per access), this corresponds to a witness size of ~18 MB, which is too large to safely broadcast through a p2p network within a 12-second slot. Verkle trees reduce witness sizes to ~200 bytes per account in the average case, allowing stateless client witnesses to be acceptably small.

from https://eips.ethereum.org/EIPS/eip-6800

而 Verkle Tree 将大大减少 Proof size。

什么是 Verkle tree

Verkle tree("Vector commitment" 和 "Merkle Trees") 是一种基于 Trie 的数据结构，目标是存储 KVs 的集合，并尽可能效率高的提供对 KVs 的增删改查的功能，而且能够提供某组 K 对应的 V 确实是返回的 V 的正确性证明。

承诺，证明

这里对不熟悉承诺和证明的读者进行一个简单的科普。

一个这样的场景，Alice 和 Bob 玩一个游戏：

• Alice：我知道一个多项式
  $f(x)=a_0+a_{1}x+\cdots +a_{n-1}{x}^{n-1}$，我能够向你证明
• Bob：我对
  $f(x)$ 一无所知，怎么验证呢？
• Alice：是的，现在
  $f(x)$ 完全是我说了算，我可以随意修改它的系数。因此需要我先公开一个
  $f(x)$ 的承诺(Commitment)，这样我就不能乱改
  $f(x)$
• Bob：是的，我先生成一个随机数
  $r$，但是这个
  $r$ 我不会告诉你，然后选取 BLS12-381 的
  $G_1,G_2$ 两点, 并且计算
  $(P_0,P_1,P_2\dots ,P_{n-1})=(G_1,r{G}_1,r^2{G}_1,\dots ,r^{n-1}{G}_1)$，并将这
  $n$ 个椭圆曲线上的点发送给你。因为根据椭圆曲线离散对数难题，拥有
  $rG$ 无法得到
  $r$ 的值。
• Alice：好的，我计算
  $P=f(r)G_1=a_0{G}_1+(a_1\cdot r)G_1+(a_2\cdot r^2)G_1+\cdots +(a_{n-1}{r}^{n-1})G_1=a_0{P}_0+a_1{P}_1+a_2{P}_2+\cdots +a_{n-1}{P}_{n-1}$，然后将
  $P$ 点发送给你，那么
  $P$ 点就是
  $f(x)$ 的承诺。可以看出，虽然我不知道
  $r$，但是我能够计算任意多项式的承诺。
• Bob：好的，我再生成一个挑战值（随机数）
  $s$，并且把这个
  $s$ 发送给你。
• Alice：我计算
  $f(s)$，以及
  $q(x)=\frac{f(x)-f(s)}{x-s}$，并计算
  $Q=q(r)G_1$，我把
  $f(s),Q$ 发送给你。其中
  $f(s)$ 是结果，
  $Q$ 是对
  $f(s)$ 的证明 proof。
• Bob：我验证
  $e(f(r)G_1-f(s)G_1,G_2)=e(q(r)G_1,(r-s)G_2)$ 是否成立，如果成立，就能证明
  $f(r)-f(s)=q(r)(r-s)$, 我就大概率可以相信你知道
  $f(x)$。
  $e(G_1,G_2)$ 是 pairing，部分椭圆曲线拥有该性质，比如 BLS12-381。

以上是对 KZG 的一个简化描述。具体可以参考 https://hackmd.io/DA-UGXFFRzCCznM1JBuZcA

总结一下，Bob 到最后都不知道

$f(x)$ 的系数

$a_i$，但是他大概率相信 Alice 知道

$f(x)$，那么他相信 Alice 知道哪个

$f(x)$？即承诺

$P$ 对应的那个。

回到 Verkle Tree，你不需要知道具体 KV 的值，只需要提前知道 state root，类似对所有的 KV 的承诺，以及相关 KV proof，你就能验证相关 KV 确实在这个 state root 代表的 Tree 的下面。

Verkle Tree 的结构

图 1

一个典型的 Verkle tree 如上图所示，包含 3 类节点，根据 rust-verkle 里面的命名，为 Branch node，Stem node, Leaf node。注意，上图里面 node 的里面值虽然用相同字符表示，但不同 node 中的值并不一定相等。其中

$C$ 表示 Branch node 的 commitment，是一个椭圆曲线上的点，

$H_C$ 表示对该 Commitment 的hash 值，是椭圆曲线上的标量域

${\mathbb{F}}_r$ 里面的元素。

$C_1,C_2,C_s$ 分别表示 Stem node 的 Commitment。

$K,V$ 表示要存的实际数据。

我们可以根据上图得出结论：

• root 节点是 Branch node
• Branch node 的子节点可能是 Branch node，可能是 Stem node
• Stem node 的父节点有多个子节点，因为假设只有一个子节点的话，它会被优化进 stem
• Stem node 的子节点为 Leaf node，Leaf node 的父节点为 Stem node
• 某个 Branch/Stem node 下最多有 256 子节点
• 因为 Leaf node 的 key 使用 [u8;32] 表示，整个 tree 最深为 32

其他信息：

• Stem node 的 key 值为 31 bytes，它在 Tree 里面的 Path 只能获取这个 key 的前面一部分到全部的值（取决于它所处深度），因此需要额外字段存储。
• Leaf node 在这 31 bytes 的基础上，再加上它在 Stem node 下所处位置的 index，就能组成 32 bytes，作为 Leaf node 的 key
• 已知 Stem node 的 key，以及它所处的深度 d，可以得到它的 path：path = key[0..d]

问题：

• Stem node 的作用是什么？这是对 trie 的一种优化，MPT 里面也存在类似的优化：当 Trie 中连续 node 都只有一个子节点时，可以把它们压缩成一个节点来表示，这样可以降低 Tree 的深度。
• 比如使用 2-ary 来代表 256-ary 时，下图是对实际情况的一种模拟，因为所有的 Key 都是通过 address 和其他信息的 pedersen hash 得来，可以看作是随机数，因此 leaf node 从 root 开始就均匀分布在各个分支，假设没有 Stem node，深度在 3-4 之后，大部分 node 将呈现如上图所示的情况，即退化成 Linked list。
  某个资料显示，在实际情况中 Verkle tree 的平均深度为 3.8，这是正常的，
  ${256}^{3.8}\approx 1.4\text{B}$，而以太坊的地址数为 0.268B，容量足够。
• 为什么到倒数第 2 个 node 又开始分叉了(所谓的 suffix trie)？
  有意思的问题，还在和 ETH R&D 负责 verkle tree 团队讨论。

I do have a question about the design of verkle trees, here a binary tree is used to represent a 256-ary tree. My understanding is that since all keys are the results of pedersen_hash and are relatively random, the keys will be evenly distributed in each branch starting from the root. In actual situations, the structure of the tree should be like Figure 1: the first 3-4 layers are almost a balanced tree, and the subsequent nodes will degenerate into linked lists. Then use stem node to represent nodes that degenerate into linked lists for optimization. My question is, 1. Why not put the nonce, balance, and even some storage slots of the same address under the same stem node, because when a transaction occurs, these fields are relatively easy to update at the same time, and this can reduce the number of required to update stem nodes and branch nodes. The actual situation is that they will be randomly distributed in different stem nodes. 2. Since all leaf nodes will be randomly distributed, why is Figure 2 chosen for the final layout, which branches into 256 child nodes after the stem node? I think the actual situation is that under a stem node, in most cases only one child has a value, and the others are Null.

• Stem node 的缺点是如果同时出现 Leaf node 2 和 4，或者 3 和 4 时，它就没起到降低深度的作用了，是一个可能的 DDoS 攻击面。并且你并不需要拥有相关地址的私钥就能攻击，比如我直接给 Leaf node 2 和 3 所代表的账号转入微量的 ether 作为余额，就可以让 Verkle Tree 深度加深。解决方案是 key 不是根据 account address 直接生成，而是经过一次 hash，在 EIP 6800 里面有体现。
• 为什么 Stem node 的 Key 设计为 31 bytes，Stem node 不能做 root，那么至少它的第一个 byte 就可以不存，直接从 Stem 的 Path 获取？我的理解这是实现方式的差异，memoryDB 里面就是这么实现的：[u8;31]
• 之前在某个资料里面看到，有了 Verkle Tree 之后，account 下面不需要给 contract account 额外新建 Storage tree 了，这是怎么实现的？Verkel tree 的潜在空间非常大（
  $2^{256}$），因此按照下面的形式将 storage tree 嵌入到 Verkle tree 里面。

def get_tree_key_for_storage_slot(address: Address32, storage_key: int):
    if storage_key < (CODE_OFFSET - HEADER_STORAGE_OFFSET):
        pos = HEADER_STORAGE_OFFSET + storage_key
    else:
        pos = MAIN_STORAGE_OFFSET + storage_key
    return get_tree_key(
        address,
        pos // VERKLE_NODE_WIDTH,
        pos % VERKLE_NODE_WIDTH
    )

基于 Memory 的 Verkle Tree

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/database/memory_db.rs#L6-L11
pub struct MemoryDb {
    pub leaf_table: HashMap<[u8; 32], [u8; 32]>,
    pub stem_table: HashMap<[u8; 31], StemMeta>,
    pub branch_table: HashMap<Vec<u8>, BranchChild>,
}

pub struct StemMeta {
    pub c_1: Element,
    pub hash_c1: Fr,

    pub c_2: Element,
    pub hash_c2: Fr,

    pub stem_commitment: Element,
    pub hash_stem_commitment: Fr,
}

pub enum BranchChild {
    Stem([u8; 31]),
    Branch(BranchMeta),
}

pub struct BranchMeta {
    pub commitment: Element,
    pub hash_commitment: Fr,
}

三种类型的 node，对应三个 table，leaf_table 对应 32 bytes 的 KV pair，stem_table 对应 31 bytes 的 key 和

$C_1,C_2,C_s,H_{C_1},H_{C_2},H_{C_s}$ 的 value。branch_table 对应可变长度的 bytes（Path）作为 key，该 Path 下的 node 可能是 Stem, 可能是 Branch。

上图为打印图 1 的结果，可以看到 5 个 leaf node，31 个 branch node，4 个 stem node，注意 branch_table 里面包含 31 个branch node 和 4 个 stem node。

Verkle Tree 的 Method

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/lib.rs#L17-L50
pub type Key = [u8; 32];
pub type Value = [u8; 32];

pub trait TrieTrait {
    /// Inserts multiple values into the trie
    /// If the number of items is below FLUSH_BATCH, they will be persisted
    /// atomically
    /// This method will implicitly compute the new root
    fn insert(&mut self, kv: impl Iterator<Item = (Key, Value)>);

    /// Inserts a single value
    /// This method will implicitly compute the new root
    fn insert_single(&mut self, key: Key, value: Value) {
        self.insert(vec![(key, value)].into_iter())
    }

    /// Gets the value at the `Key` if it exists
    /// Returns an none if it does not exist
    /// TODO: Find out if this method is ever needed
    fn get(&self, key: Key) -> Option<Value>;

    /// Returns the root of the trie
    fn root_hash(&self) -> Fr;

    /// Returns the root commitment of the trie
    fn root_commitment(&self) -> Element;

    /// Creates a verkle proof over many keys
    fn create_verkle_proof(
        &self,
        key: impl Iterator<Item = Key>,
    ) -> Result<proof::VerkleProof, ProofCreationError>;
}

实际上，以太坊的 State Trie 只需要实现 TrieTrait，即对外只需要提供以上几条功能就能完成任务，而不管底层使用 Verkle Tree 还是 SALT。这里我们先分析如果是 Verkle Tree 将如何实现。

• insert，给定一组 KV pair，将其保存。在 MemoryDB 中，即 insert 到 leaf_table
• insert_single，直接的调用 insert
• get，给定一个 K，返回 V。在 MemoryDB 中，get leaf_table 里面的 KV pair
• root_hash，root 节点 commitment 的 hash
• root_commitment，root 节点 commitment
• create_verkle_proof，给定一组 K，返回一个 VerkleProof

除了 insert_single，接下来看一下剩下 5 个接口的实现。

首先看一下 Trie 的定义，Trie 有两个字段，storage 和 committer，他们的类型都是泛型，其中 Storage 类型没做要求， PolyCommit 类型还需要实现 Committer 这个 trait，我们先关注 storage。

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/trie.rs#L12-L15
pub struct Trie<Storage, PolyCommit: Committer> {
    pub storage: Storage,
    pub committer: committer,
}

get

对于 Storage 类型实现了 ReadWriteHigherDb trait 的 Trie，因为 ReadWriteHigherDb trait 里面有 get_leaf 接口，因此直接调用 self.storage.get_leaf(key)

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/trie.rs#L26-L28
impl<S: ReadWriteHigherDb, P: Committer> TrieTrait for Trie<S, P> {
    fn get(&self, key: crate::Key) -> Option<crate::Value> {
        self.storage.get_leaf(key)
    }
}

那么 MemoryDb 是怎么实现 get_leaf 的？直接从 MemoryDb 里面的 leaf_table 这个 HashMap get 就能拿到。

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/database.rs#L8
pub trait ReadWriteHigherDb: ReadOnlyHigherDb + WriteOnlyHigherDb {}

// https://github.com/crate-crypto/rust-verkle/blob/7688f0aedfb147d3d391abfe8495e46c46d72ce0/verkle-trie/src/database/memory_db.rs#L59-L63
impl ReadOnlyHigherDb for MemoryDb {
    fn get_leaf(&self, key: [u8; 32]) -> Option<[u8; 32]> {
        self.leaf_table
            .get(&key)
            .map(|val| val.to_vec().try_into().unwrap())
    }
}

实际上我觉得不必把类型转换来转换去，可以这样实现：

In fact, I think there is no need to convert types. It can be achieved like this:

    fn get_leaf(&self, key: [u8; 32]) -> Option<[u8; 32]> {
        self.leaf_table.get(&key).copied()
    }

复杂度
在 MemoryDB 中的实现，平均来说 get 是一个

$\mathcal{O}(1)$ 的操作，因为直接调 HashMap 里面的 get

root_hash 和 root_commitment

同样，对于 S 类型实现了 ReadWriteHigherDb trait 的 Trie，因为 ReadWriteHigherDb trait 里面有 get_branch_meta 接口，因此直接调用 self.storage.get_branch_meta，输入 root node 的 path：&[]，就能获取 root node 的 meta 信息，包括 commitment 和 hash。

impl<S: ReadWriteHigherDb, P: Committer> TrieTrait for Trie<S, P> {
    fn root_hash(&self) -> Fr {
        // This covers the case when the tree is empty
        // If the number of stems is zero, then this branch will return zero
        let root_node = self
            .storage
            .get_branch_meta(&[])
            .expect("this should be infallible as every trie should have a root upon creation");
        root_node.hash_commitment
    }
    
    fn root_commitment(&self) -> Element {
        // TODO: This is needed for proofs, can we remove the root hash as the root?
        let root_node = self.storage.get_branch_meta(&[]).unwrap();
        root_node.commitment
    }
}

impl ReadOnlyHigherDb for MemoryDb {
    fn get_branch_meta(&self, key: &[u8]) -> Option<BranchMeta> {
        let branch_child = match self.branch_table.get(key) {
            Some(b_child) => b_child,
            None => return None,
        };

        match branch_child {
            BranchChild::Stem(stem_id) => panic!(
                "expected branch meta data, however under this path there is a stem: {}",
                hex::encode(stem_id)
            ),
            BranchChild::Branch(b_meta) => Some(*b_meta),
        }
    }
}

而 MemoryDb 是怎么实现 get_branch_meta 的？因为存了 branch_table 这个 HashMap，可以直接拿，但是正如前面描述的， value 有两种类型，一种是 Branch，另一种是 Stem，如果是 Stem 的时候，直接 panic，因为你给的参数是 Stem 的 path，然后你想在这里拿 Branch。

复杂度
在 MemoryDB 中的实现，平均来说 root_hash 和 root_commitment 是一个

$\mathcal{O}(1)$ 的操作，因为直接调 HashMap 里面的 get

insert

insert 会比较复杂，我们结合示意图和代码来分析。

从下面的实现可以看到实现涉及到两个流程，把要 insert 的每个 KV pair 转化成指令组成的一系列小操作 instructions，然后再把 instructions 作用到 Tree 上。

impl<S: ReadWriteHigherDb, P: Committer> TrieTrait for Trie<S, P> {
    fn insert(&mut self, kv: impl Iterator<Item = (crate::Key, crate::Value)>) {
        for (key_bytes, value_bytes) in kv {
            let ins = self.create_insert_instructions(key_bytes, value_bytes);
            self.process_instructions(ins);
        }
    }
}

但是需要注意的是，这里对 KV 的处理是串行，更新完一个 KV 后才能进行才一个 KV，这了有一个优化思路是可以提前对这些 KV 进行预处理，尽量让有公共 path 的 KV 同时处理，这样就可以减少公共 path 上的 stem node 和 branch node 的更新次数。

指令有 3 种，UpdateLeaf，ChainInsert，InternalNodeFallThrough

pub enum Ins {
    UpdateLeaf {
        ...
    },

    ChainInsert {
        ...
    },

    InternalNodeFallThrough {
        ...
    },
}

UpdateLeaf

pub(crate) type BranchId = Vec<u8>;

UpdateLeaf {
    key: [u8; 32],
    new_leaf_value: [u8; 32],
    depth: u8,
    branch_id: BranchId,
    branch_child_index: u8,
},

更新 leaf node，会把从 root 到该 leaf node 的 path 上所有的 node 都更新一遍：

1. 更新该 leaf node 的 value
2. 更新它对应的 stem node 的
   $C_1,C_2$ 中的某一个，以及对应的 hash
3. 更新 stem node 的父节点们（branch node）的
   $C$ 和
   $H_C$

包含的信息：

• key, new_leaf_value，用于第一条更新
• depth，该 leaf node 所处深度
• branch_id，该 leaf node 对应的 stem node 的 path
• branch_child_index，该 leaf node 在 stem node 下的位置。

UpdateLeaf 的一个场景是如下图，假设在已有的 tree 的基础上新增 leaf node 6:

先看 process_instructions 里面是怎么处理 UpdateLeaf 指令的：

impl<Storage: ReadWriteHigherDb, PolyCommit: Committer> Trie<Storage, PolyCommit> {
    pub fn process_instructions(&mut self, instructions: Vec<Ins>) {
        for ins in instructions.into_iter().rev() {
            match ins {            
                Ins::UpdateLeaf {
                    key,
                    new_leaf_value,
                    depth,
                    branch_id,
                    branch_child_index,
                } => {
                    let leaf_update = match self.update_leaf_table(key, new_leaf_value, depth) {
                        Some(leaf_update) => leaf_update,
                        None => {
                            // No value was updated, early exit
                            return;
                        }
                    };

                    let stem_update = self.update_stem_table(leaf_update, depth);

                    self.update_branch_table(stem_update, branch_id, branch_child_index, depth);
                }
                ...
            }
        }
    }
    ...
}

如上图所示， 如果该 leaf node 之前有值，就依次调用了 update_leaf_table，update_stem_table，update_branch_table。如果返回是空，就只需要 update_leaf_table，感觉有点很奇怪。

看这个三个 update 的实现吧：

update_leaf_table：

    // Store the leaf, we return data on the old leaf, so that we can do the delta optimization
    //
    // If a leaf was not updated, this function will return None
    // else Some will be returned with the old value
    fn update_leaf_table(
        &mut self,
        key: [u8; 32],
        value: [u8; 32],
        depth: u8,
    ) -> Option<LeafUpdated> {
        let old_val = match self.storage.insert_leaf(key, value, depth) {
            Some(vec) => {
                // Check if they have just inserted the previous value
                // if so, we early exit and return None
                if vec == value {
                    return None;
                }
                Some(vec)
            }
            None => None,
        };

        Some(LeafUpdated {
            old_val,
            new_value: value.to_vec(),
            key: key.to_vec(),
        })

        // Storing a leaf means we need to change the stem table too
    }

impl WriteOnlyHigherDb for MemoryDb {
    fn insert_leaf(&mut self, key: [u8; 32], value: [u8; 32], _depth: u8) -> Option<Vec<u8>> {
        self.leaf_table
            .insert(key, value)
            .map(|old_val| old_val.to_vec())
    }
}

调用了 storage 的 insert_leaf method。然后调用了 HashMap 的 insert。如果有值就返回值，没值就返回 none。

总结就是 update_leaf_table 如果 leaf node

• 新的 KV 和之前的 KV 相同
• 之前该 K 不存在 V

就返回 None，UpdateLeaf 就只执行 update_leaf_table。否则返回更新结果：LeafUpdated，并继续执行 update_stem_table，update_branch_table。

update_stem_table

• 为什么 branch node 里面只需要一个 commitment 就行，而 stem node 里面需要两个 commitment，他们不都是对 256 个子节点进行承诺吗？因为被承诺的对象不同。branch node 的子节点是 branch node 或者是 stem node，被承诺的对象是 branch node 或者 stem node 的 commitment 的 hash 值，取值范围为 [0, order)，直接承诺就行。而 stem node 的子节点是 KV，被承诺的对象是 V，取值范围 [0,2^256)，超出 order 的那一部分无法被承诺。因此需要两个 commitment。怎样划分呢？一个自然的想法是把子节点 256 个 V 的 [0,127] bit 放在第一个
  $C_1$，[128,255] bit 放在
  $C_2$，但是这样做，只要更新 V 里面的某一个值，就会导致需要更新
  $C_1$,
  $C_2$。因此采用不同的划分办法：
  $C_1$ 用于 index 为 0-127 的 V 的承诺，
  $C_2$ 用于 index 为 128-255 的 V 的承诺。具体实现为：

一个 stem node 下面有

$V_0$~

$V_{255}$ 共 256 个 leaf node，每一个

$K_i,V_i$，假设为 [u8; 32]，则：

• Vi_l = Fr::from_le_bytes_mod_order(V_i[0..=15]) + 2^128
• Vi_h = Fr::from_le_bytes_mod_order(V_i[16..=31])
• stem: [u8;31] = Ki[0..=30]

如果 index 为 i 的 node 不存在，则 Vi 使用 0 代替。

假设 Commitment base 为

$(G_0,G_1,\dots ,G_{255})$，实际上所有的 branch node 的

$C$，stem node 的

$C_1$,

$C_2$ 都是用同一套 Commitment base。那么计算公式为：

Assume that the Commitment base is

$(G_0,G_1,\dots ,G_{255})$. In fact, all

$C$ of branch nodes and

$C_1$ and

$C_2$ of stem nodes use the same set of Commitment base. Then the calculation formula is:

$$\begin{array}{rl}{C}_1& =\sum _{i=0}^{127}(V_i\mathrm{\_}l\cdot G_{2i}+V_i\mathrm{\_}h\cdot G_{2i+1})\\ C_2& =\sum _{i=0}^{127}(V_{i+128}\mathrm{\_}l\cdot G_{2i}+V_{i+128}\mathrm{\_}h\cdot G_{2i+1})\\ H_C& =\text{group\_to\_field}(C)\\ C_{stem}& =1\cdot G_0+\text{stem}\cdot G_1+H_{C_1}\cdot G_2+H_{C_2}\cdot G_3\end{array}$$

其中

$C_{stem}$ 的计算方式也是下图绿色节点的来源，

The calculation method of

$C_{stem}$ is also the source of the green node in the figure below,

from https://blog.ethereum.org/2021/12/02/verkle-tree-structure

具体的代码就不全部贴上来了，还挺多，可以自行去这里查看：
https://github.com/crate-crypto/rust-verkle/blob/e07b17b0538fcd227c221d2388e5468417116f00/verkle-trie/src/trie.rs#L537-L675

需要注意的是，里面利用了椭圆曲线上点的加法同态来优化，假设更新了

$V_1$，那么:

$C_1^{\prime }=C_1+(V_1\mathrm{\_}{l}^{\prime }-V_1\mathrm{\_}l)\cdot G_2+(V_1\mathrm{\_}{h}^{\prime }-V_1\mathrm{\_}h)\cdot G_3$

$C_2^{\prime }=C_2$

$C_{stem}^{\prime }=C_{stem}+(H_{C_1}^{\prime }-H_{C_1})\ast G_2$

然后下面是我根据上面的公式一步步计算

$C_1,C_2,C_{stem}$ 和更新后的 trie 里面的相等：
https://github.com/flyq/verkle_tree_example/blob/da877d33309ee036661c4408a519b27357dbd335/src/main.rs#L14-L47

最后调用 insert_stem 直接在 MemoryDb 的 stem_table 上 insert：

    fn insert_stem(&mut self, key: [u8; 31], meta: StemMeta, _depth: u8) -> Option<StemMeta> {
        self.stem_table.insert(key, meta)
    }

update_branch_table

$$\begin{array}{rl}{C}_{branch}& =\sum _{i=0}^{255}{H}_i\cdot G_i\\ H_i& =\text{group\_to\_field}(C_i)\end{array}$$

其中

$C_i$ 表示该 branch node 下面的子节点的 commitment，可能是 branch 节点，可能是 stem 节点。

    fn update_branch_table(
        &mut self,
        stem_update: StemUpdated,
        branch_id: BranchId,
        branch_index: u8,
        depth: u8,
    ) -> Fr {
        let old_stem_hash = stem_update.old_val.unwrap_or_else(Fr::zero);
        let new_stem_hash = stem_update.new_val;
        let delta = new_stem_hash - old_stem_hash;

        let old_branch_comm = self.storage.get_branch_meta(&branch_id).unwrap().commitment;
        let delta_comm = self.committer.scalar_mul(delta, branch_index as usize);
        let updated_branch_comm = old_branch_comm + delta_comm;
        let hash_updated_branch_comm = group_to_field(&updated_branch_comm);

        // Update the branch metadata

        self.storage.insert_branch(
            branch_id.clone(),
            BranchMeta {
                commitment: updated_branch_comm,
                hash_commitment: hash_updated_branch_comm,
            },
            depth,
        );
        let mut branch_child_id = branch_id;
        branch_child_id.push(branch_index);
        self.storage
            .add_stem_as_branch_child(branch_child_id, stem_update.stem, depth);

        hash_updated_branch_comm
    }

上面的代码实现同样利用了椭圆曲线点的加法同态性：

$C_{branch}^{\prime }=C_{branch}+(H_i^{\prime }-H_i)G_i$

然后下面是我根据原始的公式一步步计算

$C_{branch}$ 和 trie 里面的相等：

https://github.com/flyq/verkle_tree_example/blob/d4fdd7f5565db9bcb5aaabe861c549847063598e/src/main.rs#L78-L112

InternalNodeFallThrough

    InternalNodeFallThrough {
        branch_id: BranchId,
        branch_child_index: u8,
        child: BranchId,
        old_child_value: Option<Meta>,
        depth: u8,
    },

               Ins::InternalNodeFallThrough {
                    branch_id,
                    branch_child_index,
                    child,
                    depth,
                    old_child_value,
                } => {
                    let new_branch_meta = self.storage.get_branch_meta(&child).unwrap();
                    let new_hash_comm = new_branch_meta.hash_commitment;

                    let old_hash_comm = match old_child_value {
                        Some(old_branch_meta) => old_branch_meta.into_branch().hash_commitment,
                        None => Fr::zero(),
                    };

                    let delta = new_hash_comm - old_hash_comm;
                    let delta_comm = self
                        .committer
                        .scalar_mul(delta, branch_child_index as usize);

                    let old_parent_branch_metadata =
                        self.storage.get_branch_meta(&branch_id).unwrap();

                    let old_branch_comm = old_parent_branch_metadata.commitment;
                    let updated_comm = old_branch_comm + delta_comm;
                    let hash_updated_comm = group_to_field(&updated_comm);

                    self.storage.insert_branch(
                        branch_id,
                        BranchMeta {
                            commitment: updated_comm,
                            hash_commitment: hash_updated_comm,
                        },
                        depth,
                    );
                }

这个用于更新一类特殊 branch node 的 C 和 Hc。这类 branch node 的子节点也是 branch node，不是 stem node。并且是在 trie 已经更新好该 branch node 的子节点下，再更新本 branch node。

ChainInsert

    ChainInsert {
        starting_depth: u8,
        chain_insert_path: Vec<u8>,
        parent_branch_node: BranchId,
        child_index: u8,
        old_leaf_index: u8,
        new_leaf_key: [u8; 32],
        new_leaf_value: [u8; 32],
        new_leaf_index: u8,
    },

这个指令用于更新某个路径下一系列的 branch node。源码就不贴了，在 https://github.com/crate-crypto/rust-verkle/blob/e07b17b0538fcd227c221d2388e5468417116f00/verkle-trie/src/trie.rs#L362-L485

create_verkle_proof

    fn create_verkle_proof(
        &self,
        keys: impl Iterator<Item = [u8; 32]>,
    ) -> Result<crate::proof::VerkleProof, crate::errors::ProofCreationError> {
        use crate::proof::prover;
        prover::create_verkle_proof(&self.storage, keys.collect())
    }
    
pub fn create_verkle_proof<Storage: ReadOnlyHigherDb>(
    storage: &Storage,
    keys: Vec<[u8; 32]>,
) -> Result<VerkleProof, ProofCreationError> {
    if keys.is_empty() {
        return Err(ProofCreationError::EmptyKeySet);
    }
    let (queries, verification_hint) = create_prover_queries(storage, keys);

    // Commitments without duplicates and without the root, (implicitly) sorted by path, since the queries were
    // processed by path order
    let root_query = match queries.first() {
        Some(query) => query,
        None => return Err(ProofCreationError::ExpectedOneQueryAgainstRoot),
    };

    let root_comm = root_query.commitment;

    let comms_sorted: Vec<_> = queries
        .iter()
        // Filter out the root commitment
        .filter(|query| query.commitment != root_comm)
        // Pull out the commitments from each query
        .map(|query| query.commitment)
        // Duplicate all commitments
        .dedup()
        .collect();

    let mut transcript = Transcript::new(b"vt");
    let proof = MultiPoint::open(CRS.clone(), &PRECOMPUTED_WEIGHTS, &mut transcript, queries);

    Ok(VerkleProof {
        comms_sorted,
        verification_hint,
        proof,
    })
}    

verkle proof 依赖 IPA 的实现

ipa-multipoint

pub struct IPAProof {
    pub(crate) L_vec: Vec<Element>,
    pub(crate) R_vec: Vec<Element>,
    pub(crate) a: Fr,
}

推导一下 ipa-multipoint/src/ipa.rs 里面的 create function：

参数：

• transcript，用于 Fiat-Shamir Transform，即将 IPA 中的交互式部分（产生随机挑战值），使用 random oracle 代替，transcript 扮演 random oracle，并且，验证者按照相同步骤也能获取到对应的挑战值，省去 transcript 的传输
• crs，Common Reference String, 这里用于保存 Pedersen commitments 对应的 base，即 256 + 1 个线性无关的点 Element
• a_vec，向量 a
• a_comm，向量 a 的承诺，等于
  $\sum _{i=0}^{n-1}{a}_i{G}_i$
• b_vec，向量 b
• input_point，多项式自变量的值，仅仅用于 transcript

逻辑：

• $out\mathrm{\_}point=\overrightarrow{a}\cdot \overrightarrow{b}$
• $Q=w\cdot Q$
• $C_{L_i}=a_R\cdot G_L+a_R\cdot b_L\cdot Q$
• $C_{R_i}=a_L\cdot G_R+a_L\cdot b_R\cdot Q$
• $L=(C_{L_0},C_{L_1},\dots ,C_{L_{rounds}})$
• $R=(C_{R_0},C_{R_1},\dots ,C_{R_{rounds}})$
• $a=a_L+x\cdot a_R$
• $b=b_L+x^{-1}{b}_R$
• $G=G_L+x^{-1}{G}_R$

输出：
proof:

$L,R,a[0]$

verify function

参数：

• transcript，和 create 一样
• crs，和 create 一样
• b，和 create 的 b_vec 一样
• a_comm, 和 create 一样
• input_point, input_point
• output_point，结果，等于f(input_point)，也等于
  $\overrightarrow{a}\cdot \overrightarrow{b}$

参数和 create 相比，少了向量 a，多了 output_point

逻辑：

• $a\mathrm{\_}comm=a\mathrm{\_}comm+w\cdot Q\cdot output\mathrm{\_}point$
• $a\mathrm{\_}comm=a\mathrm{\_}comm+C_{L_i}\cdot x_i+C_{R_i}\cdot x^{-1}$
• $G_i=G_{L_{i-1}}+x_i^{-1}{G}_{R_{i-1}}$
• $b_i=b_{L_{i-1}}+x_i^{-1}{b}_{R_{i-1}}$
• $a\mathrm{\_}comm?=G_n[0]\cdot proof.a+proof.a\cdot b_n[0]\cdot w\cdot Q$

以上总结就是：

• $\mathcal{P}$ 知道
  $\overrightarrow{a}$，
  $\overrightarrow{b}$，
• $\mathcal{V}$ 知道
  $\overrightarrow{b}$，不知道（不想知道）
  $\overrightarrow{a}$
• base 为
  $\overrightarrow{G}=(G_0,G_1,\cdots ,G_{n-1})$ 和
  $U$

过程：

• $C_a=\overrightarrow{a}\cdot \overrightarrow{G}$
• $U=w\cdot U$
• $C_0=C_a+\overrightarrow{a}\cdot \overrightarrow{b}U$
• $C_{L1}={\overrightarrow{a}}_{R0}\cdot {\overrightarrow{G}}_{L0}+{\overrightarrow{a}}_{R0}\cdot {\overrightarrow{b}}_{L0}U$
• $C_{R1}={\overrightarrow{a}}_{L0}\cdot {\overrightarrow{G}}_{R0}+{\overrightarrow{a}}_{L0}\cdot {\overrightarrow{b}}_{R0}U$
• $C_1=C_0+x_1{C}_{L1}+x_1^{-1}{C}_{R1}$

一直到

$k=\log n$:

• ${\overrightarrow{a}}_k={\overrightarrow{a}}_{Lk-1}+x_k{\overrightarrow{a}}_{Rk-1}$
• ${\overrightarrow{b}}_k={\overrightarrow{b}}_{Lk-1}+x_k^{-1}{\overrightarrow{b}}_{Rk-1}$
• $C_{Lk}={\overrightarrow{a}}_{Rk-1}\cdot {\overrightarrow{G}}_{Lk-1}+{\overrightarrow{a}}_{Rk-1}\cdot {\overrightarrow{b}}_{Lk-1}U$
• $C_{Rk}={\overrightarrow{a}}_{Lk-1}\cdot {\overrightarrow{G}}_{Rk-1}+{\overrightarrow{a}}_{Lk-1}\cdot {\overrightarrow{b}}_{Rk-1}U$
• $C_k=C_{k-1}+x_k{C}_{Lk}+x_k^{-1}{C}_{Rk}$

此外，

• ${\overrightarrow{a}}_k,{\overrightarrow{G}}_k$ 长度均为 1

$C_a,{\overrightarrow{a}}_k,\overrightarrow{a}\cdot \overrightarrow{b},{\overrightarrow{C}}_L,{\overrightarrow{C}}_R$ 发送给

$\mathcal{V}$

$\mathcal{V}$ 验证:

• $C_k=C_a+\overrightarrow{a}\cdot \overrightarrow{b}U+\sum _{i=1}^k(x_i{C}_{Li}+x_i^{-1}{C}_{Ri})$
• $C_k\stackrel{\text{?}}{=}{\overrightarrow{a}}_k[0]\cdot {\overrightarrow{G}}_k[0]+{\overrightarrow{a}}_k[0]{\overrightarrow{b}}_k[0]U$

verify_multiexp:

• $\sum _{i=1}^k(x_i{C}_{Li}+x_i^{-1}{C}_{Ri})+C_a+(\overrightarrow{a}\cdot \overrightarrow{b}-{\overrightarrow{a}}_k[0]{\overrightarrow{b}}_k[0])\cdot U-{\overrightarrow{a}}_k[0]\cdot {\overrightarrow{G}}_k[0]\stackrel{\text{?}}{=}0$

MultiPointProof

pub struct MultiPointProof {
    open_proof: IPAProof,
    g_x_comm: Element,
}

pub struct PrecomputedWeights {
    // This stores A'(x_i) and 1/A'(x_i)
    barycentric_weights: Vec<Fr>,
    // This stores 1/k for k \in [-255, 255]
    inverted_domain: Vec<Fr>,
}

• PrecomputedWeights.barycentric_weights: 在 verkle tree 场景下，有 256+256 个值，
  $A^{\prime }(0),A^{\prime }(1),\dots ,A^{\prime }(255),\frac{1}{A^{\prime }(0)},\frac{1}{A^{\prime }(1)},\dots ,\frac{1}{A^{\prime }(255)}$，
• PrecomputedWeights.inverted_domain: 在 verkle tree 的场景下，有 255+255 个值，
  $1,\frac{1}{2},\frac{1}{3},\dots ,\frac{1}{255},-1,-\frac{1}{2},-\frac{1}{3},\dots ,-\frac{1}{255}$

pub struct LagrangeBasis {
    // We assume that the domain starts at zero,
    // so we only need to supply the upperbound
    domain: usize,
    values: Vec<Fr>,
}

对于由：

$(0,f(0)),(1,f(1)),(2,f(2)),\dots ,(255,f(255))$ 进行 Lagrange 插值出来的多项式

$f(x)$:

• LagrangeBasis.domain 为 256
• LagrangeBasis.values 为
  $(f(0),f(1),f(2),\dots ,f(255))$

Methods:

• divide_by_linear_vanishing, 计算新的多项式
  $q(x)=\frac{f(x)-f(x_i)}{x-x_i}$
• evaluate_in_domain，当
  $x_i\in \{0,1,\dots ,255\}$ 时，直接拿
  $f(x_i)$
• evaluate_lagrange_coefficients, 当
  $x_i$ 不在 domain 时，返回新的 LagrangeBasis，
  $f(z)=A(z)\sum _{i=0}^{N-1}\frac{f(i)}{A^{\prime }(x_i)(z-x_i)}$,
  • $A(z)=\prod _{i=0}^{255}z-i$
  • a vector, which contains:
    $re{s}_i=\frac{A(z)}{A^{\prime }(i)(z-i)}$

pub struct ProverQuery {
    pub commitment: Element,
    pub poly: LagrangeBasis, // TODO: Make this a reference so that upstream libraries do not need to clone
    // Given a function f, we use z_i to denote the input point and y_i to denote the output, ie f(z_i) = y_i
    pub point: usize,
    pub result: Fr,
}

前面的依赖数据结构看完了，看看 open 是怎么实现的
open() -> MultiPointProof

输入：

• crs，Pedersen 承诺的 base
• precomp，预计算一些
  $A^{\prime },+-\frac{1}{i}$
• transcript, 用于 Fait-Shamir变换
• queries，数组，长度为
  $t$，代表
  $t$ 个多项式
  $f_i(x)$

逻辑：

• 获取随机 r，生成
  $1,r,r^2,r^3,\dots ,r^{t-1}$
• 分组：
  $(i,(r^i,f_i(x)))$，其中
  $i\in [0..t]$
• aggregated_polynomial 有 256 项，假设为
  $h_i(x)$
• $h_i(j)=f_i(j)\cdot r^i$
• $h_i(x)=A(x)\cdot r^i\cdot \sum _{j=0}^{255}{f}_i(j)\cdot \frac{1}{A^{\prime }\cdot (x-j)}$

对同一点打开的多项式:
HashMap<point, Vec<(f_i, r^i)>>进行聚合：

• $ag\mathrm{\_}poly=\sum _i{r}^i\cdot \overrightarrow{f_i}$

然后我们有由

$(point,ag\mathrm{\_}poly)$ 组成的 Vector

用

$d_i(x)$ 表示

$ag\mathrm{\_}poly$

$g(x)=\sum _{i=0}^h\frac{d_i(x)-d_i(point)}{x-point}$

h 等于有多少个不同的 point，也是上面 Vector 的长度。

$C_g=\sum _{i=0}^{255}g(i)\cdot G_i$

Reference

• https://blog.ethereum.org/2021/12/02/verkle-tree-structure
• https://vitalik.eth.limo/general/2021/06/18/verkle.html
• https://ihagopian.com/posts/anatomy-of-a-verkle-proof
• https://verkle.dev
• https://verkle.info
• https://eips.ethereum.org/EIPS/eip-6800
• https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html
• https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html