(continued from previous) What is a KZG10 promise?

Note 3.6: If the [s],[s^2]…[s^d] computed by the startup setup only computes to the index d, this set of values cannot be used to generate a commitment for any polynomial of order greater than d. The converse is also true.

Since there is no way to multiply two points to arrive at a third point on a safe curve, [s^(d+k)] is an (always!) value that cannot be derived, so it can be said that any commitment c(f) can only represent a polynomial of order less than or equal to d.

Remark 3.7: The evidence for using the KZG10 commitment is essentially proving that the result of f(x) – some remainder can be decomposed in a particular way, but this requires that there be a way to multiply these factors together and compare C(f) = f([s]) with the original commitment.

For this, we need the “pairing equation”, which is a multiplication method that multiplies two points on a curve and compares them to another curve point, because we cannot directly have these two curve points multiplied directly to get the synthetic curve point.

Note 3.8: The above two properties can be further used to prove that the order k of the polynomial f(x) represented by some commitment c(f) is smaller than d.

In summary, the KZG10 commitment can have the following nice properties.

The process of verifying a commitment is to provide (by the block generator) the value y=f(r) of the underlying polynomial at any point r, and the value of the division polynomial q(x)=(f(x)-y)/(x-r) at point [s] (i.e., q([s])), and to compare the previously provided commitment f[s] using the matching equation. This is called opening the commitment at point r, and q([s]) is the proof. It is easy to see that q(s) is p(s)-r divided by s-r, which happens to be what we check with the pairing equation, i.e., check that (f([s])-[y]) * [1]’ = q([s]) * [s-r]’ (translator’s note: f(s)-r is suspected here, but the original is p(s)-r).

In the non-interactive and deterministic version, Fiat Shamir Heuristic provides a way to obtain a relatively random point r: since randomness is only related to the input we try to prove, i.e., as long as the commitment c=f([s]) is already available, r can be obtained by hashing all inputs (r=Hash(C,…)) to be obtained, and the proposer of the commitment is responsible for providing the opening point and the evidence.

Using pre-computed Lagrangian polynomials, both f([s]) and q([s]) can be computed directly under the summation form. To calculate the on value at r, it is necessary to convert f(x) to f(x)=a0+ a1*x^1…. (i.e., extracting the coefficients a0, a1, …). This can be done with the inverse fast Fourier transform with a complexity of O(d log d), but even here there is an alternative algorithm available that does the computation within the complexity of O(d) without using the inverse fast Fourier transform.

You can use a single turn-on point and evidence to prove multiple values of f(x), that is, values corresponding to multiple index values, index1=>value1, index2=>value2 …

The division polynomial q(x) (used to compute the evidence) now becomes f(x) divided by the zero polynomial z(x) = (x-w^index1)*(x-w^index2)… the quotient of (x-w^indexk)

The remainder is r(x) (r(x) is a polynomial of maximal order k interpolated by index1=>value1, index2=>value2 … indexk=valuek)

check ( f([s]) – r([s]) )* [1] ‘ = q([s]) * z([s]’)

In the PoS chain common start setup, the shared data chunks are represented as low-order polynomials (and expanded to twice the size using the same fitted polynomials for the purpose of censoring codes), which KZG promises can be used to check for arbitrary random chunks and verify and ensure data availability without obtaining brother data points. This opens up the possibility of random sampling.

Now, for a state that can contain at most 2^28 account keys, you need polynomials of order at least 2^28 to construct a flat commitment (the total space of account keys will actually be much larger). There are some inconveniences when it comes to updating and inserting. Any change to either account will trigger a recalculation of the commitment (and, more problematically, the witness data/evidence).

Updating KZG10 commitments

Any change to any index value => numeric point, e.g., a change to indexk, requires updating the commitment using the corresponding Lagrangian polynomial. The complexity is about O(1) per update.

However, since f(x) itself also changes, all witnesses q_i([s]), i.e., all witnesses for the i-th key-value pair, need to be updated as well. The total complexity is about O(N)

If we do not maintain the pre-computed q_i([s]) witness, any witness data has to be computed from scratch, which requires O(N)

A construction of updated KZG10 commitment with complexity sqrt(N)

Therefore, in order to achieve the fourth point of the ideal commitment scheme, we need a special construction: the Verkle trie.

Verkle tree

The state of the Ether that needs to be represented has about 2^28 approximately equal to 16^7 approximately equal to 250 million key-value pairs. If we use only flat commitments (then we need an order of at least 2^28). Although our evidence is always 48 bytes of elliptic curve elements, any insertion or update requires O(N) operations to update all the precomputed witness data (i.e., q_i(s) for all points, since f(x) itself has changed); even more, if there is no precomputed witness data, then each witness data will take O(N ) to recompute.

Therefore, we need to replace the flat structure with a structure called Verkle tree, which is a tree structure like Merkle tree.

That is, a commitment tree is constructed like a Merkle tree, so that we can guarantee that the order d is relatively small (but it also needs to be up to about 256 or 1024).

Each parent node encodes a commitment to its child nodes, which are a mapping whose index values are present in its parent node

In fact, the parent’s commitment encodes the hashed child node, since the input to the commitment is a normalized, 32-byte value (see Note 3.0 above).

A leaf node encodes a commitment to a 32-byte hash of the data it stores; or it jumps directly to the data, if its 32-byte data usage is the same as the proposed usage of the state tree mentioned in the next chapter.

To provide evidence for a branch (similar to Merkle branch evidence), a multi-valued proof of the commitment D, E can be generated around generating a relatively random point t using fiat shamir heruristic.

Complexity

Here is an analysis of the Verkle multi-valued proof

Update/Insert Leaf node index=>value needs to be updated log_d(N) commitments ~ log_d(N)

To generate evidence, the provers need to

Compute f_i(X)/(X-z_i) at [s] for generating D. The complexity totals O(d log_d N), but can be adjusted at update/insertion to save precomputation, and the complexity becomes O d log_d(N)

Compute m ~ O( log_d(N) ) f_i(t) to compute h(t) for a total of O (d log_d N)

To compute π, ρ, it is necessary to divide the sum of m~ log_d N exponential polynomials. It takes about O(d log_d N) to obtain the numerator’s summation form to compute the division

The size of the proof (including the branch commitment used to compute E) plus the complexity of verification ~ O( log_d(N) )

Verkle tree construction

Proposed ETH state Verkle tree

Single tree structure with header and code chunks for storage accounts, and storage item chunks with nodes committed to polynomials of order d=256

Combining addresses and headers/storage gaps to derive a 32-byte storageKey, which is essentially a representation of a tuple (address,sub_key,leaf_key)

The first 30 bytes of the derived key are used to construct ordinary verkle tree node pivots

The second 2 bytes are a subtree of tree height 2, representing up to 65536 32-byte chunks

For basic data, this tree-height 2 subtree has up to 4 leaf commitments to cover haeader and code

Since a chunk of 65536*32 bytes is represented as a single word, there may be many subtrees in the main tree to store an account

Gas pricing scheme

Events of access type (address, sub_key, leaf_key)

WITNESS_CHUNK_COST is charged for each specialized access event

Additional WITNESS_BRANCH_COST is charged for each specialized address,sub_key combination

Code Merkleization

The code is automatically part of the verkle tree (as part of a unified state tree)

Both header and code of a block are part of a commitment tree with a tree height of 2

A single block has up to 4 witness data, each charged with WITNESS_CHUNK_COST and one WITNESS_BRANCH_COST for access accounts

Data Sampling and Chunking in PoS Protocol

One of the goals of ETH PoS is to be able to submit about 1.5MB/s of data (think of this throughput as the throughput of state changes, and therefore the throughput of transactions that L2 rollups can utilize, and ultimately the throughput of L1 EVMs). To achieve this, many parallel block proposals have to be able to be issued and validated within a given 12 seconds; that is, there have to exist multiple slots (about 64), each of which has to publish its own data block at each slot. If there are more than 2/3 votes in favor, the beacon chain block will contain the slice data block and the fork selection rules will also determine whether it can become the main chain block based on the data availability of all data blocks and their ancestors within the beacon chain block.

Note 3: A slice is not a chain at this point, and any implied order is subject to interpretation by the L2 protocol.

KZG promises can also be used to construct data validity and availability schemes, where clients can verify the availability of a slice without accessing the full data published by its proponent.

The slice data block (without censoring codes) is 16384 samples (32 bytes each), which is about 512 kb; there are also data headers, which consist mainly of polynomial commitments of up to 16384 orders corresponding to these samples

But the polynomial valued form D has a scale of 2^16384, i.e., 1,w^1,…w^,…w^32767, while W is the unit root of 32768 (not of 16384)

We can fit a polynomial of order up to 16384 to the data (f(w^i)=sample-i for i<16384) and extend it to 32768 as a sample of the correction code, i.e., compute f(w^16384) … f(w^32767)

The proof of the value for each point is also computed simultaneously and released with the sample

Any 16384 of the 32768 samples can be obtained to fully recover f(x) and the original sample, i.e., f(1), f(w^1), f(w^2)… f(w^16383)

The censored 32768 samples are divided into 2048 chunks, each containing 16 samples, i.e. 512 bytes of data; they are distributed horizontally by the shard proponent, i.e. the i-th chunk and the corresponding evidence to the i-th vertical subnetwork, plus a global commitment to disclose the complete data

At the specified (shard, slot), each verifier downloads and examines these chunks in k-20 vertical subnetworks and verifies them using the promises of the corresponding data chunks to establish data availability guarantees

We need to schedule enough verifiers for each (shard, slot) such that the overall general (and even more data) is fetched; in addition, there are some statistical requirements to be satisfied, with about 128 members per (shard, slot), there needs to be at least 70 (i.e., 2/3) members witnessed such that the shard data block to be successfully packaged on the beacon chain.

At least 262144 validators are required (32 slots, multiplied by 64 shards, multiplied by at least 128 members)

Benchmarking

After building a verkle at the scale of a state tree, insertion and update are very fast, as we see in the POC verkle go codebase.

Insertion/Update Benchmarking

Benchmarking for proof generation validation

Posted by:CoinYuppie，Reprinted with attribution to:https://coinyuppie.com/introducing-the-kzg-promise-for-ether-an-engineers-perspective-below/

Coinyuppie is an open information publishing platform, all information provided is not related to the views and positions of coinyuppie, and does not constitute any investment and financial advice. Users are expected to carefully screen and prevent risks.