Contract

Meeda's verification contract is mainly implemented by FileProof. Next, the design details of FileProof will be explained in detail for developers to discuss.

Background

Layer2 nodes upload transaction data through DABackend node, and the data availability layer of Meeda ensures the availability of files. Layer2 nodes need to pay DABakcend to maintain data availability services.

FileProof serves as Meeda's data availability layer, which is the smart contract part of Meeda, and acts as a decentralized regulator. The DABackend node needs to regularly submit data availability certificates to the chain. If the certificate is passed, it can be considered that the availability of the Layer2 node data is guaranteed, and the DABackend node can obtain the corresponding service fee. If it proves that the DABackend node cannot obtain the corresponding service fee, the fee will be issued to the foundation for the development and maintenance of a more stable and reliable service platform.

In order to reduce the cost of data availability proof and improve the efficiency of data availability proof, FileProof gets inspiration from Optimistic Rollup in Layer 2 and implements optimistic verification and multi-round interactive fraud proof schemes suitable for file availability proof. And the use of KZG polynomial commitment technology makes the verification method efficient and low-cost. This provides a simple, efficient, low-cost, scalable, and decentralized DA solution.

Technical Background

Apply BLS12-381 curve and KZG polynomial commitment techniques.

Generate a private parameter s through multi-party calculation, publicize ψ=s*g_2, that is the verification public key vk; and publicize s_i = s^i*g_1. Among them, g_2 is the G2 generator of the bls12_381 curve, and g_1 is the G1 generator of the bls12_381 curve.

For the data to be proved, it can be regarded as a vector P: {p0, p1, ... , p_{n-1} }, where pi ∈ Fr, the size does not exceed 32 bytes, and the data can be splitted into 32-byte atoms, and then convert each atom into an Fr element.

Then the vector P is constructed into a polynomial P(x) = \sum_{i=0}^{n-1}p_ix^i, and then the commitment C of the file is obtained, C = P(s)g_1 = \ sum_{i=0}^{n-1}p_i s_i , C is a G1 point.

prove:

The prover needs to provide proof of possession of data P.

The verifier is given a random number z (bytes32), the data owner, that is the prover, can calculate: y = P(z), and take the polynomial Q(x) = \frac{P(x)-y} {x-z}, where Q(x) = \frac{P(x)-y}{x-z} = \sum_{i=0}^{n-2}q_ix^i, and where q_{ n-2} = p_{n-1}, q_i = p_{i+1} + q_{i+1} * y.

Then calculate: π = Q(s)g_1 = \sum_{i=0}^{n-2}q_is_i

The proof is (y, π).

verify:

When the verifier does not know the data, that is, when he does not know the vector P, he verifies that the prover does know the data based on the public parameters ψ, z, y, π, C. The verifier can verify e(π, ψ-z*g_2) = e(C - y*g_1, g_2) based on the linear pairing property of bls12_381. If the verification passes, it can be determined that the prover knows the data P, otherwise the prover does not know the data P.

batch proof:

In the case of the same random number z, the prover provides batch proof. Batch generate commitment C_j and proof (y_j, π_j) for each file. Assume ϕ = y*g_1, then the aggregate commitment Cn and aggregate proof (ϕ, π) are in order:

C = \sum_{j=0}^{m-1}C_j

ϕ = \sum_{j=0}^{m-1}ϕ_j

π=\sum_{i=0}^{m-1}π_j

The verifier still verifies: e(π, ψ-z*g_2) = e(C - ϕ, g_2).

Process

1. Upload Data

1.1 Off-Chain

The Layer2 node uploads the file, and the DABackend node returns to the Layer2 node a certificate credential that the file has been uploaded and a file unique identifier commitment (that is, the polynomial commitment generated by the file).

Among them, commitment is a G1 element with a length of 96 bytes, an x coordinate of 48 bytes, and a y coordinate of 48 bytes. In the contract, the bytes32[4] format is used to represent the Affine coordinate format of a G1 element. The first two bytes32 represent the x coordinate, and the last two bytes32 represent the y coordinate. Both x and y are in big-endian encoding format, and bytes32[2] The first 16 bytes are all filled with 0.

The credential for the uploaded file can be a signature of the DABackend node. The signature content should include the contract address of FileProof (to prevent the risk of the signature being reused due to future contract changes), the Layer2 node address (the person who uploaded the file, that is, the file owner ), file commitment, file size (unit Byte), file storage start time start (expressed by timestamp), file storage end time end, the DABackend node does not need to provide this after the file expires. Proof of availability of documents. After obtaining the signature content, the DABackend node signs with the private key to ensure that the file has been successfully uploaded to the storage node. Otherwise, the Layer 2 node may submit an unuploaded file commitment to the contract, and the DABackend node will not be able to provide the availability proof of the file subsequently, and thus received undue punishment.

Hash calculation method of signature content:

bytes32 hash = keccak256(abi.encodePacked(fileProofAddr, caller, commitment, sizeByte, start, end));

1.2 On-Chain

The Layer2 node calls the addFile method in the contract to save the file commitment to the chain, which will be used by subsequent DABackend nodes to provide proof of file availability.

The contract verifies the credential. If the verification is successful, the file commitment can be saved in the contract (the DABackend node will regularly submit the availability certificate of some files to the contract), and the Layer 2 node needs to pay for the file availability service. The fees are uniformly kept in the contract account. The service unit price is price (unit is attomemo/byte/second, service fee value = size * price * (end - start)), which will be recorded in the contract, and can be modified by foundation members according to the actual situation by generating the multi-signature. Modifying price will not affect the uploaded files.

The reason why it is stipulated here that only the availability proof of some files should be submitted instead of all files is because if the availability proof of all files is submitted each time, then the DABackend node does not need to save the file data itself, but only the polynomials of all files. The sum of the parameters is enough to handle periodic proof submissions. It is stipulated that each time some files are randomly checked, the DABackend node must save the file data, so that the availability proof of the randomly checked part of the files can be generated based on the file and the random number, and then submitted through periodic verification.

The Layer2 node cannot upload an existing file commitment again.

Each time you upload a commitment, you need to maintain the final validity period finalExpire, which indicates the time when all files expire. After finalExpire, the DABackend node no longer needs to submit an availability certificate, and the DABackend node will no longer receive benefits.

2. Submit Proof

All uploaded files, their commitment and validity period end are saved on the chain. For unexpired files, DABackend nodes need to regularly submit availability proofs to the chain to obtain corresponding service fees. If the proof is passed, it can be considered that the availability of Layer 2 node data is guaranteed to a certain extent (sampling testing cannot guarantee 100%).

2.1 Generate random numbers

According to the kzg polynomial commitment scheme and decentralization characteristics, a pseudo-random number rnd will be generated regularly by the contract. The contract will determine the files to be randomly checked during this period based on rnd. After that, the DABackend node will generate an availability proof based on rnd for the randomly checked files, and the contract also verifies the proof based on rnd.

It is necessary to ensure that the pseudo-random number cannot be predicted. If the random number can be predicted, then the DABackend node can perform malicious behavior to know the file to be verified in advance, and then prepare the availability proof in advance without the need to completely save the Layer2 node data. In this case, the availability of Layer 2 node data cannot be reliably guaranteed. Therefore, the random numbers for each period need to be generated within a specific short period of time when submission of availability proofs can begin.

Therefore, in addition to determining the interval for submitting the availability proof, it is also necessary to determine a validity period for submitting the proof. Every once in a while interval, the DABackend node needs to submit a proof within the valid period. If the DABackend node does not submit a proof within the validity period, it can be regarded as the DABackend node has not fulfilled the agreement to ensure the availability of Layer 2 node data during the interval, and the DABackend node will not be able to obtain the service revenue during this period.

The random number rnd used by the DABackend node to submit an availability proof each time can only be generated after the interval and within the validity period. Once generated, it cannot be changed within the period. After the validity period, the random number rnd will become invalid.

The interval for the DABackend node to submit the proof and the validity period for the submission of the proof are discussed and decided by the foundation members and specified when deploying the contract, and can be changed later according to the actual situation.

2.2 Select documents to be verified

Within the valid period of the submitted proof, the contract will generate this valid random number rnd and determine which files to select for verification based on the random number rnd. The DABackend node needs to generate and aggregate the availability proof of these files, and then submit the aggregated proof to the contract for verification (verification will be carried out in an optimistic and multi-round interactive manner, which will be explained in detail later).

The DABackend node needs to ensure that it uses the same algorithm as the contract to obtain the file to be verified, or directly queries from the interface provided by the contract, otherwise the verification will always fail. The total number of files selected each time is specified by chalSum, which is calculated with a certain probability based on the total number of files in the system. The number of expired files in the system is not considered here for the time being. Meeda will take this situation into consideration later to make the solution more concise and efficient.

The function of querying which files were selected during this period is implemented by the interface selectFiles(uint i) in the contract.

From rnd, the total number of files length and the index of the file to be selected i[0, chalSum), the commitment value of the file to be selected is obtained (if the selected file has expired, the commitment value is 0), According to the kzg polynomial commitment, the corresponding availability proof is generated for the selected file, all the availability proofs are aggregated to obtain Pn, and the commitments of the selected file are aggregated to obtain Cn.

The last proof submission time is recorded as last, then the deadline for submitting the proof this time is last+interval+period. When selecting files during each verification period, files whose storage end time end does not exceed last will be considered expired files.

2.3 Generate proof and submit

The DABackend node obtains the data holding proofs of the selected files to be verified off-chain, aggregates these proofs, and submits the aggregated proof Pn and the aggregated commitment Cn to the chain. The DABackend node needs to ensure that the random numbers used are valid, that is, consistent with the valid random numbers generated in the contract.

Optimistic verification assumes that the Cn (aggregation commitment of the selected file) submitted by the DABackend node is correct, and only needs to verify the correctness of Pn to Cn. Within the specified validity period, if no node (any node) questions Cn, then the availability proof will be deemed successful. If a node raises a question, the node will initiate a challenge on the chain (the node is called a challenger). Subsequently, multiple rounds of interactive verification will be triggered to verify the correctness of Cn. If the verification is passed, the availability proof will be considered successful. This logic will be explained in detail in the fraud proof.

If the proof Pn submitted by the DABackend node passes the verification, then the service revenue that should be obtained during this verification period (that is, <last_pre, last_now>) thisProfit = balance * (last_now - last_pre) / (finalExpire - last_pre) , where balance represents the effective balance of the contract account (the service fee is handed over to the contract account for safekeeping when the Layer2 node uploads files, and is linearly released to the DABackend node each time the availability proof is submitted). In order to support the cost-effective multi-round interactive verification method and encourage DABackend nodes to provide better service, service revenue is deferred in the form of release. In other words, the benefits that should be obtained from submitting the availability proof this time will be released when the next proof is submitted. Regardless of whether the verification of this availability proof is passed or not, the contract account will release the income earned when the last availability proof was submitted to the DABackend node.

3. Fraud Proof

After the DABackend node submits the availability proof regularly, in order to reduce the cost of verification, an optimistic verification method is adopted. That is, only the aggregated commitment Pn is verified. If it fails, it directly indicates that the verification failed; if it succeeds, any node can choose to further question Cn. Because the first stage only assumes that there is no fraud on the DABackend node, that is, it is assumed that Cn is correct. If any node finds that Cn is wrong during the off-chain calculation process, it can raise questions about Cn on the chain and initiate a challenge. If the challenge is successful, the challenger will receive an economic reward; if the challenge fails (that is, Cn is indeed correct), the challenger will lose the funds pledged during the challenge. The process in which a node raises a question and initiates a challenge and finally obtains the challenge result is called fraud proof.

The first stage is to prove the correctness of Pn to Cn, and the second stage of fraud proof is to prove the correctness of Cn. In order to reduce the amount of calculation on the chain and improve the coverage of sample inspection of files, an Arbitrum-style multi-round interactive verification mode is adopted.

3.1 Raise doubt

After the DABackend node submits the proof, the first phase of proof verification will be carried out. According to the verification public key vk, verify whether there is a valid pairing relationship between the aggregate commitment Cn, the aggregate proof Pn and the valid random number rnd.

Regardless of whether this round of verification passes, the proceeds from the last submitted proof will be released to the DABackend node (in order to ensure the security of funds, the DABackend node can set up a cold account address receiver dedicated to receiving funds).

If the verification fails, the income from this submission will be directly 0. If the verification is successful, the income will be recorded first and then released when the next proof is submitted. If a node raises a question, the second phase is started. The node initiates a challenge and triggers a fraud proof. The purpose is to prove that there is fraud in the DABackend node. If the fraud does exist, then the income this time will also be deducted (part of the reward will be given to Challengers, part of the reward will be given to the foundation).

3.2 Multiple rounds of interaction

Nodes can choose whether to initiate a challenge. If the challenge fails (there is no fraud on the DABackend node), then the challenger will waste his transaction fees and pledge fees (a pledge fee is required when initiating a challenge); if the challenge succeeds (there is indeed fraud on the DABackend node), then the challenger will be rewarded. This mechanism effectively reduces the cost of proving document availability and effectively curbs fraud.

When the challenge is initiated, the DABackend node needs to respond within the validity period respondTime. If it does not respond within the validity period, it will be deemed that the DABackend node has failed, indicating that the DABackend node has committed fraud. If the DABackend node wants to respond normally, it needs to divide the selected files to be verified into ten equal parts in order, aggregate the commitment values of each file, and obtain 10 aggregated commitment values _cns, and call the responseChal method to submit _cns to the on-chain contract, and aggregation verification is performed in the contract. The contract aggregates _cns again to verify whether it is consistent with the cn submitted in the first phase. If they are consistent, it means that no fraud on the DABackend node in this round of interaction; if they are inconsistent, it can directly prove that there is fraud on the DABackend node.

If no fraud on the DABackend node in the first round of interaction, the challenger can choose to initiate the second round of interaction within respondTime, specifically: the challenger calls the continueChal method, and selects a problematic aggregate commitment value _cn in the previous round of _cns , that is, compress the problematic file range 10 times (use chalIndex to indicate the number of decimal files), and continue to challenge the DABackend node for this part of the file. After the DABackend node receives the signal of continueChal, it still needs to respond within respondTime and continue to divide the file represented by chalIndex into ten equal parts in order. The subsequent logic is the same as above.

Once a challenge is initiated, either the DABackend node or the challenger will be deemed a loser if they do not respond within the validity period respondTime.

3.3 One step proof

Until the last round of interaction, the range of challenged files is compressed to only a few. At this time, there is no need to aggregate files, and only a single commitment value of these files needs to be submitted. This process is called a one-step proof. The DABackend node only needs to call the oneStepProve method to submit the commitment value of a single file to the contract. The contract first verifies whether the aggregated commitment value of these files is consistent with the previous round's commitment value, and then adds the commitment values of these files one by one. Compare it with the commitment value of the file recorded on the chain. If the comparison is successful, it can be finally shown that the DABackend node does not commit fraud, and the challenger will pay the price for his malicious challenge; if the comparison is unsuccessful, it means that the DABackend node does commit fraud, and the challengers will be rewarded.