Vitalik: What is the rationale for trusted initialization?

Editor’s Note:

Data availability sampling is a key part of Dankshading. To implement this cryptographic protocol, the parameters required by the data availability proof scheme need to be initialized using the KZG ceremony.

Therefore, KZG trusted initialization is an important prerequisite for implementing EIP-4844 (proto-danksharding) and the full version of Danksharding.

In addition to this, other cryptographic protocols such as the field of ZK-SNARKs also require a trusted initialization phase.

This article describes how trusted initialization works and how it is verified.

“Sharding + Data Availability Sampling” http://www.ethereum.cn/sharding-proposal

Necessary background knowledge : elliptic curves and elliptic curve pairings.

See also: Dankrad Feist’s article on KZG polynomial commitments. (Chinese version: KZG Polynomial Commitment)

Special thanks to Justin Drake, Dankrad Feist and Chih Cheng Liang for their feedback and review.

Many cryptographic protocols, especially in the areas of data availability sampling and ZK-SNARKs, rely on trusted initialization. A trusted initialization ceremony is a one-time process for generating a batch of data.

Subsequently, this data must be used every time certain cryptographic protocols are run. Generating these data requires some secret information; ” trust ” comes from the fact that someone or a group of people must generate these secrets, use the secrets to generate the data, then publish the data and destroy the secrets.

However, once the data has been generated and the secret destroyed, the ritual creator requires no further involvement.

Vitalik: What is the rationale for trusted initialization?

There are many types of trusted initialization. The earliest instance of trusted initialization used in mainstream protocols was the Zcash launch ceremony in 2016. The ceremony is complex and requires multiple rounds of communication interactions, so there can only be six participants.

At that moment, everyone using Zcash had to trust that at least one of the six participants was honest. Modern protocols generally use a powers-of-tau initialization technique, which follows a 1-of-N trust model, where the value of N is usually in the hundreds.

That is, hundreds of people are involved in generating data, and only one of them needs to be honest and not disclose the secret to guarantee the security of the final output. In practice, a well-executed trusted initialization like this is often considered “close enough to trustless”.

This article will describe how KZG initialization works and how it works, as well as the future of the trusted initialization protocol. Anyone savvy with code is free to browse the code implementation at: https://github.com/ethereum/research/blob/master/trusted_setup/trusted_setup.py.

What does Powers-of-tau initialization look like?

The powers-of-tao initialization consists of two series of elliptic curve points as follows:

Vitalik: What is the rationale for trusted initialization?

Vitalik: What is the rationale for trusted initialization?

and 

Vitalik: What is the rationale for trusted initialization?

are standard generators for two elliptic curve groups; in BLS12-381,

Vitalik: What is the rationale for trusted initialization?

occupies 48 bytes (compressed form),

Vitalik: What is the rationale for trusted initialization?

Occupies 96 bytes.

Vitalik: What is the rationale for trusted initialization?

,

Vitalik: What is the rationale for trusted initialization?

are initialized output

Vitalik: What is the rationale for trusted initialization?

 ,

Vitalik: What is the rationale for trusted initialization?

The length of the generated point column. some protocol requirements

Vitalik: What is the rationale for trusted initialization?

=2 , other protocols require

Vitalik: What is the rationale for trusted initialization?

and

Vitalik: What is the rationale for trusted initialization?

are large, some protocols fall into the middle case (e.g. the current Ethereum data availability sampling scheme requires

Vitalik: What is the rationale for trusted initialization?

=4096 and

Vitalik: What is the rationale for trusted initialization?

=16 ).

Vitalik: What is the rationale for trusted initialization?

Is the secret value used to generate the point column and needs to be destroyed after use.

for the polynomial

Vitalik: What is the rationale for trusted initialization?

To generate KZG commitments, we simply choose a linear combination

Vitalik: What is the rationale for trusted initialization?

,in

Vitalik: What is the rationale for trusted initialization?

(Column of Elliptic Curve Points in Trusted Initialization).

initializing

Vitalik: What is the rationale for trusted initialization?

Used to verify the value of our promised polynomial; I won’t discuss the details of the verification process here, see Dankrad’s article for more details (https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial -commitments.html).

Intuitively, what value does trusted initialization provide?

A deeper understanding of what’s going on here and why trusted initialization can provide these values.

The polynomial promise uses a size of

Vitalik: What is the rationale for trusted initialization?

An object (a single elliptic curve point) for a segment of size

Vitalik: What is the rationale for trusted initialization?

data to commit. We can do this with a simple Pedersen promise:

just put

Vitalik: What is the rationale for trusted initialization?

The value of is set to

Vitalik: What is the rationale for trusted initialization?

uncorrelated random elliptic curve points, then pair the

Vitalik: What is the rationale for trusted initialization?

Polynomials make commitments. In fact, that’s exactly what IPA proofs do. (https://vitalik.ca/general/2021/11/05/halo.html)

However, any IPA-based attestation requires

Vitalik: What is the rationale for trusted initialization?

Time to verify, there is an unavoidable reason: use basis points

Vitalik: What is the rationale for trusted initialization?

to polynomial

Vitalik: What is the rationale for trusted initialization?

The generated promise will correspond to the usage base point

Vitalik: What is the rationale for trusted initialization?

another polynomial of .

Vitalik: What is the rationale for trusted initialization?

Polynomials under a set of basis points

Vitalik: What is the rationale for trusted initialization?

An effective commitment of is equivalent to a polynomial under another set of basis points

Vitalik: What is the rationale for trusted initialization?

a valid commitment.

If we want to generate IPA-based proofs for some propositions (for example, the polynomial in

Vitalik: What is the rationale for trusted initialization?

is equal to 3826 ), the proof should pass when based on the first set of basis points and fail when based on the second set of basis points.

So, regardless of the validation process, it is impossible to avoid thinking about each one in some way

Vitalik: What is the rationale for trusted initialization?

value, and therefore inevitably requires

Vitalik: What is the rationale for trusted initialization?

time.

However, if there is a trusted initialization, there is a hidden mathematical relationship between the points. It is guaranteed that any two adjacent points have the same factor

Vitalik: What is the rationale for trusted initialization?

make

Vitalik: What is the rationale for trusted initialization?

. if

Vitalik: What is the rationale for trusted initialization?

is a valid initialization output, ” the tampered output ” 

Vitalik: What is the rationale for trusted initialization?

it is invalid.

Therefore, we do not need

Vitalik: What is the rationale for trusted initialization?

The amount of computation; on the contrary, we can use this mathematical relationship to

Vitalik: What is the rationale for trusted initialization?

Time to verify anything we need to verify.

However, the mathematical relationship must be kept secret: if

Vitalik: What is the rationale for trusted initialization?

is known, then anyone can come up with a promise that represents many different polynomials: if

Vitalik: What is the rationale for trusted initialization?

Yes

Vitalik: What is the rationale for trusted initialization?

promise, then it is also

Vitalik: What is the rationale for trusted initialization?

or

Vitalik: What is the rationale for trusted initialization?

or many other polynomial commitments. This would completely break the very foundation of all applications of polynomial commitments.

So while there must be some secret value at some point in time

Vitalik: What is the rationale for trusted initialization?

,Let

Vitalik: What is the rationale for trusted initialization?

Mathematical connections between values ​​are possible, enabling efficient verification, but

Vitalik: What is the rationale for trusted initialization?

must also be destroyed.

How does multi-party trusted initialization work?

Initializing a single participant is simple: just choose a random value

Vitalik: What is the rationale for trusted initialization?

, and use

Vitalik: What is the rationale for trusted initialization?

value generates a series of elliptic curve points. But trusted initialization of a single participant is insecure: you have to trust a specific person!

The solution is multi-party trusted initialization, where ” many ” refers to many participants: more than 100 is normal, and may exceed 1000 for a less computationally intensive initialization scheme. Here’s how multi-party powers-of-tau initialization works.

Vitalik: What is the rationale for trusted initialization?

Take an existing initialization output as a pointcut (note that you don’t know

Vitalik: What is the rationale for trusted initialization?

value, you only know a series of elliptic curve points):

Vitalik: What is the rationale for trusted initialization?

Now, choose your own random secret value 

Vitalik: What is the rationale for trusted initialization?

. calculate:

Vitalik: What is the rationale for trusted initialization?

Note that this is equivalent to:

Vitalik: What is the rationale for trusted initialization?

That is, you have created a secret value

Vitalik: What is the rationale for trusted initialization?

The corresponding valid initialization output! you never put your secret value 

Vitalik: What is the rationale for trusted initialization?

to the previous participant, and the previous participant will not give their secret value

Vitalik: What is the rationale for trusted initialization?

to you.

As long as either participant is honest and does not reveal his part of the secret value, the combined secret value will not be revealed.

In particular, finite fields have the property that if you know

Vitalik: What is the rationale for trusted initialization?

but don’t know

Vitalik: What is the rationale for trusted initialization?

,and

Vitalik: What is the rationale for trusted initialization?

is generated safely and randomly, then you are right

Vitalik: What is the rationale for trusted initialization?

The value of nothing is known!

Verify trusted initialization

To verify that each participant is indeed participating in trusted initialization, each participant can provide such a proof, including (i) the points they received

Vitalik: What is the rationale for trusted initialization?

and (ii)

Vitalik: What is the rationale for trusted initialization?

, where tt is the secret value they introduce.

This series of proofs can be used to verify that the final initialization output combines all secret values ​​(in contrast, the last participant simply discards the previous values ​​and outputs an initialization result generated only from his own secret values , he can keep this secret value for himself, thus cheating in any protocol that uses this initialization output).

Vitalik: What is the rationale for trusted initialization?

Vitalik: What is the rationale for trusted initialization?

is the secret value of the first participant,

Vitalik: What is the rationale for trusted initialization?

is the secret value of the second participant, and so on. A pairing check at each step verifies that the initialization output of each step indeed originates from a combination of the initialization output of the previous step and the new secret value known to the participants at the current step.

Translator ‘s Note: Paired characteristics

Vitalik: What is the rationale for trusted initialization?

)

Every participant should disclose their evidence on some publicly verifiable medium (e.g. personal website, transactions from their eth address, twitter).

Note that this mechanism doesn’t prevent someone from claiming to be involved in a stage when in fact someone else (assuming someone else has revealed their evidence), but it’s usually not considered a problem: participate if someone wants to lie about the situation, they will also be willing to lie about the covert takedown. Initialization is safe as long as at least one of the people who publicly claim to be participating is honest.

In addition to the above checks, we also want to verify that the powers of all elliptic curve points in the initialization are correct (i.e. they are powers of the same secret value). ( Translator’s Note, that an elliptic curve can be represented as a sequence

Vitalik: What is the rationale for trusted initialization?

)

To this end, we can perform a series of paired checks, verifying

Vitalik: What is the rationale for trusted initialization?

(in

Vitalik: What is the rationale for trusted initialization?

is initializing

Vitalik: What is the rationale for trusted initialization?

value).

This verifies that each

Vitalik: What is the rationale for trusted initialization?

and

Vitalik: What is the rationale for trusted initialization?

factor between and

Vitalik: What is the rationale for trusted initialization?

and

Vitalik: What is the rationale for trusted initialization?

The factors are the same. Then, we can do the same on the G_{2}G2 side. (Translator’s note, that is, verification

Vitalik: What is the rationale for trusted initialization?

(in

Vitalik: What is the rationale for trusted initialization?

is initializing

Vitalik: What is the rationale for trusted initialization?

value)

However, this requires many pairings and is expensive. Instead, we take random linear combinations

Vitalik: What is the rationale for trusted initialization?

, and the same linear combination shifted by one bit:

Vitalik: What is the rationale for trusted initialization?

. We use a single pair check to verify that they match:

Vitalik: What is the rationale for trusted initialization?

.

We can even put

Vitalik: What is the rationale for trusted initialization?

side and

Vitalik: What is the rationale for trusted initialization?

The verification process on the side is combined: in addition to the calculation as described above

Vitalik: What is the rationale for trusted initialization?

and

Vitalik: What is the rationale for trusted initialization?

, we also calculate

Vitalik: What is the rationale for trusted initialization?

(

Vitalik: What is the rationale for trusted initialization?

is another set of random coefficients) and

Vitalik: What is the rationale for trusted initialization?

, then verify

Vitalik: What is the rationale for trusted initialization?

.

Trusted initialization in Lagrangian form

In many use cases, you are less inclined to use polynomials in the form of coefficients (e.g.

Vitalik: What is the rationale for trusted initialization?

, you would prefer to use a point-valued polynomial (e.g.

Vitalik: What is the rationale for trusted initialization?

is in the domain

Vitalik: What is the rationale for trusted initialization?

The value modulo 337 is

Vitalik: What is the rationale for trusted initialization?

polynomial). ( Translator ‘s Note: The logic here is that a polynomial of degree n requires n+1 points to determine, and the point-valued form actually refers to

Vitalik: What is the rationale for trusted initialization?

,

Vitalik: What is the rationale for trusted initialization?

,And so on)

The point value form has many advantages (for example, you can

Vitalik: What is the rationale for trusted initialization?

multiplication of polynomials in time, and division in some cases), you can even use it in

Vitalik: What is the rationale for trusted initialization?

Evaluate in time. In particular, data availability sampling requires blobs to be represented in point-valued form.

To handle these cases, it is often convenient to convert trusted initialization to point-valued form. This allows you to get the point value (in the above example,

Vitalik: What is the rationale for trusted initialization?

, and use them directly to compute commitment values.

Using the Fast Fourier Transform (FFT) is the most convenient method, but passes curve points as input instead of numerical values. I’ll avoid repeating the detailed explanation of FFTs here, but here’s an implementation; FFTs aren’t actually that hard.

The future of trusted initialization

Powers-of-tau is not the only trusted initialization scheme. Some other (actually or potentially) notable trusted initialization scenarios include:

  • The more complex initialization schemes used in older versions of the ZK-SNARK protocol (see here for example) are still sometimes used (in particular, Groth16) because it will be less expensive to verify than PLONK.
  • Some cryptographic protocols (e.g., DARK) rely on groups of hidden order, where the elements of the group do not know how many multiplications are performed to get to the zero element. There are currently completely trustless versions (see: class groups), but by far the most efficient version uses RSA groups (mod of powers, where, unknown). Trusted initialization schemes that follow the 1-of-n trust assumption are possible, but very complex to implement.

    Vitalik: What is the rationale for trusted initialization?

    Vitalik: What is the rationale for trusted initialization?

    Vitalik: What is the rationale for trusted initialization?

    Vitalik: What is the rationale for trusted initialization?

  • If/when indistinguishable obfuscation becomes feasible, many protocols that rely on it will involve: someone creating and publishing an obfuscation program that uses a hidden secret inside to do something. This is the trusted initialization process: the creator needs to hold the secret value to create the program, and then the secret value needs to be deleted.

Cryptography is still a rapidly evolving field, and the importance of trusted initialization could easily change.

Technological solutions using IPA and Halo-like thinking may be improved to the point where KZG becomes obsolete and unnecessary, or quantum computers make all elliptic curve-based solutions infeasible in a decade, at which point we will have to Use a hash-based protocol that does not require a trustless initialization.

It is possible that the KZG improves faster, or a whole new field of cryptography that relies on another trusted initialization emerges.

Trusted initialization is necessary to some extent, and it is important to remember that not all trusted initializations are equal. 176 participants is better than 6, 2000 is better.

A trusted initialization ceremony that is cheap enough to run on a browser or mobile app (eg, ZKopru initialization is a web-based application) can attract far more participants than requiring a complex software package to run.

Ideally, each ceremony should have participants running multiple independently built software implementations, running on different operating systems and environments, to reduce the risk of common-mode failures.

Rituals with only one round of interaction between participants (such as powers-of-tau) are far superior to rituals with multiple rounds of interaction, both because more participants can be supported and because it is simpler to write multiple implementations.

Ideally, rituals should be generic (the output of a ritual can support a large number of protocols). These are things we can and should continue to dig into to keep trusted initialization as safe and secure as possible.

Special thanks to ECN community translation volunteer @doublespending for contributing to the translation of this article.

Posted by:CoinYuppie,Reprinted with attribution to:https://coinyuppie.com/vitalik-what-is-the-rationale-for-trusted-initialization/
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.

Like (0)
Donate Buy me a coffee Buy me a coffee
Previous 2022-07-29 10:15
Next 2022-07-29 10:17

Related articles