Zendoo Protocol: A Deep Dive

The privacy coin project Horizen team once claimed: "If Satoshi Nakamoto wants to design a sidechain for Bitcoin, then he should design something analogous to Zendoo." Zendoo here is the sidechain protocol designed by the Horizen team. Let's study the Zendoo protocol white paper today.

The Zendoo white paper was jointly written by the Horizen team and the IOHK team. The protocol supports a sidechain of any type, including the sidechain of the UTXO model, the sidechain of smart contracts, and even an ordinary centralized application. It is understandable that the Zendoo protocol only supports cross-chain funds because Horizen is a UTXO-model private currency public chain that does not support smart contracts, hence the cross-chain agreement is only cross-chain funds. Zendoo utilizes zero-knowledge proofs to support a decentralized approach to achieve cross-chain purposes.

The Cross-Chain Mode

There are four cross-chain modes in total:

Let's further study:

1. FT (Forward Transfer)

FT operates on the main blockchain: it transfers the assets on the main blockchain to the sidechains. The protocol is also quite simple: the main blockchain treats FT as a special transaction, destroying coins on the main blockchain and providing metadata concerning the payment on the sidechains. The side chain needs to monitor the main blockchain in real-time. If the latest block of the main chain does not contain FT transactions, the side chain will only use the hash of the block in the main blockchain as a reference and add it to the side chain; if the latest block of the main blockchain contains FT transactions, the entire block header, all FT transactions, and the Merkle path of all FT transactions will be introduced into the side chain as a reference. In this way, anyone on the side chain is able to verify whether the transaction is legal instead of going to the main blockchain for query verification.

1. BT（Backward Transfer）

BT operates on the side chain and transfers the assets on the side chain to the main blockchain. As mentioned before, IOHK is also one of the authors of the Zendoo white paper, so we can see the resemblance of the Ouroboros protocol in the design of BT.

Like the Ouroboros protocol, the protocol design of BT also involves the concepts of epoch and slot, as shown in the figure above. A withdrawal epoch is composed of lens and slots, and the len has different parameters for different side chains. If a withdrawal certificate is not submitted to the main chain within this period of time, the side chain will be considered as ceased (for instance, a withdrawal certificate in epoch i is not submitted to the main blockchain in the first len blocks in epoch i+1), and subsequent withdrawal certificates will not be accepted by the main blockchain, but the funds of the side chain can still be withdrawn. The B in the above figure is a slot. The side chain forger (block producer) will package the slot with BT signature and submit the withdrawal application certificate to the main blockchain within the specified epoch time. Regarding the withdrawal certificate, we will talk about it later.

The main blockchain does not care about the role of submitting the withdrawal certificate, and the way the withdrawal certificate should be packaged is a consideration for the side chain but not for the main blockchain.

BT = (receiverAddr, amount)

Among them：

• receiverAddr-the address of the recipient on the main blockchain

• amount - transfer amount

  
  

A Withdrawal Certificate (WCert, Withdrawal Certificate) is a standardized posting that allows the side chain to communicate with the main blockchain. This requires at least 51% of the block producer signatures to prevent fraud, and then send it to the main blockchain.

The main functions are:

• Send BT to the main blockchain
• As a heartbeat message, the main blockchain can identify the state of the side chain

It is defined as below:

WCert = (ledgerId, epochId, quality, BTList, proofdata, proof)

Among them:

• ledgerId-sidechain id to create WCert
• epochld-the id of a withdrawal epoch, generally increasing in order
• quality-indicates the quality of this withdrawal certificate (actually, it is the block height of the last status update)
• BTList-an array of multiple withdrawal transactions within a withdrawal period
• Proofdata-public input parameters used by SNARK verifiers
• Proof-the proof used by the SNARK verifier

The main blockchain contains vk (written when the sidechain is registered), and the certificate generator of the sidechain (can be anyone) contains pk.

true/false <- verify (vk, public_input, proof) public_input = (wcert_sysdata, MH (proofdata)) wcert_sysdata = (quality, MH(BTList), H(Bi-1), H(Bi)) proofdata = (H(SB_last), H(state_SB_last [MST]), mst_delta)

Among them:

• Bi-1-the last block hash of i-1 withdrawal epoch in the main blockchain
• Bi-the last block hash of i withdrawal epoch in the main blockchain
• H(SB_last)-the last block hash of the i withdrawal epoch sidechain
• H(state_SB_last[MST])-the Merkle hash after updating the state SB_last
• mst_delta - bit vector modified by MST. Since MST is a fixed-size tree, mst_delta is also a fixed-size bit vector, and each bit represents a leaf of the tree. This is applied for data visibility. In the UTXO model, withdrawal data can be restored on the main blockchain without the need for sidechain data.

Bit vector algorithm

As demonstrated in the above figure, an MST is in a depth of 3 leaves and with a node of 2³. The grey leaf node indicates that there is an update, and the white leaf node indicates that there is no update. The bit vector algorithm is used to represent the change of MST, which is:

mst_delta = (10111001)`

The algorithm can effectively save the data on the chain every time in the Data Availability characteristic expansion scheme, that is, only the transmission of the changed delta value, the root hash before the MST change, and the root hash after the MST change can verify the legality of the data. For L1 verifiers, it is not necessary to verify all the data but just the changed state.

Surely, if there are large volumes of data and the MST has a lot of leaves, then the bit vector will also be large and will consume a lot of gas. This is the direction that needs to be optimized in the future.

2. BTR（Backward Transfer Request）

It is possible that users cannot perform BT operations on the sidechain. For example, the RPC address on the sidechain refuses to access. At this time, if one wants to retrieve the funds on the sidechain to the main blockchain, one can only initiate a BTR operation on the main blockchain. BTR will not directly transfer funds on the main chain, but synchronize this BTR to the sidechain, and go through the process analogous to BT (excluding the user's active part) on the sidechain.

BTR = (ledgerId, receiver, amount, nullifier, proofdata, proof)

Among them:

• ledgerId -sidechain id
• receiver -the recipient on the main blockchain
• amount - transfer amount
• nullifier -the unique identifier of this claimed coin (similar to the nonce in Ethereum, anti-double spending)
• proofdata - publicly entered parameters, which will be discussed in detail later
• proof -proof of zero-knowledge proof

The vk and pk in a ZKSnark protocol are public, so anyone can employ vk to verify the correctness of the proof.

true/false <- verify(vk, public_input, proof) public_input = (btr_sysdata, MH(proofdata)) btr_sysdata = (H(Bw), nullifier, receiver, amount)

Among them:

Others are the same as the above-mentioned WCert, H(Bw) is the block hash of the main blockchain when this sidechain submits the last withdrawal certificate.

3. CSW（Cessed Sidechain Withdrawal）

When the sidechain does not respond, for example, the sidechain is attacked or the heartbeat message is not sent to the main blockchain within the specified time. At this time, the funds on the sidechain need to be withdrawn from the main blockchain. It is defined as follows:

CSW = (ledgerId, receiver, amount, nullifier, proofdata, proof)

The meaning of the parameters is the same as that of BTR. Unlike BTR, CSW will not go to the sidechain to follow the BT process (because the sidechain has no response at the time), but directly complete the transfer on the main blockchain.

Detailed Design

Withdrawal Safeguard

Set a global variable on the main blockchain, increase the corresponding transfer amount when performing FT, decrease the corresponding amount when performing BT, and when withdrawing, the amount cannot be greater than this amount. (This function is easier to implement in smart contracts.)

Main Blockchain Refers to Sidechain

In order to synchronize the main blockchain and the sidechain, an extra field is included in the block header of the main blockchain to commit all operations related to the sidechain in the main chain block (except CSW, used when the sidechain is ceased).

Introducing scTxsCommitment (Sidechain Transactions Commitment) is to include the root hash of the Merkle tree that is related to all transactions or output concerning the sidechain.

For example:

type MCBlockHeader { prevBlock: BlockId, height: int, … scTxsCommitment: Hash, }

Sidechain Refers to Main Blockchain

The sidechain (SC) block contains the high reference (or hash) of the main chain (MC), which has two advantages:

• The sidechain can be synchronized quickly
• The main chain is forked, and the sidechain can be referenced as a rollback point based on the final height of the main chain

As can be seen from the above figure, the main chain block may contain sidechain-related transactions, and the transactions will also be included in the sidechain block, which will also reference the main chain block.

Among them, the sidechain contains a reference to the main chain:

type MCBlockRefrence { header: MCBlockHeader, mproof: Option [MerkleProof], proofOfNoData: Option [MerkleProof], forwardTransfers: Option [FTTx], btRequests: Option [BTRTx], wcert: Option [WCert], }

• header- the header that refers to a certain MC block
• mproof-optional, if the MC block contains at least one transaction related to this SC, this field is used for the Merkle root of the SC, otherwise, it is empty.
• proofOFNoData-optional
• forwardTransfers-MC cross-chain to SC
• btRequests -Request to redeem funds from SC to MC
• WCert-withdrawal certificate

Proof Combination

Composing SNARKs recursively can transfer multiple states and finally generate a proof.

The transfer (BT/BTR) form of a single token is fixed, so the basic circuit is universal. For example, ERC20 is implemented in the form of "transfer". Then, base_proof can be aggregated to finally generate a proof. This form of aggregation is actually MMR (Merkle Mountain Range). Then the MMR will be discussed in detail as below.

Merkle Mountain Range (MMR)

For the aggregation proof of the ordinary Merkle Tree structure, if one wants to aggregate the proofs of 10 transactions into one proof, one needs to aggregate the leaf nodes in pairs. If the proofs of some of the leaf nodes are not yet ready (for example, we set that 10 transactions can generate a base_proof in the ZK Rollup. At this time, 8 transactions may be ready, but the remaining two have not yet occurred), the entire prove process will wait until the leaf node's proof is ready, and then make the aggregation in pairs, and finally aggregate sequentially to generate a merge_proof.

MMR has improved the Merkle tree structure. It can first aggregate the generated base_proofs in pairs to generate merge_proof, and then aggregate merge_proofs in pairs to generate merge_proof. As shown in the figure above, when the transactions Tx9 and Tx10 are not yet ready, the base_proofs of the previous 8 transactions can be aggregated to generate the merge_proof (1->8), and after Tx9 and Tx10 are completed, combine this two base_proof to generate a merge_proof (9->10), and then aggregates the proof with the ready merge_proof (1->8) to generate the final merge_proof (1->10).

Compared with the aggregation proof of the Merkle tree, MMR has the following characteristics:

• The efficiency of generating aggregated proofs is high, and the proof time is greatly reduced

• The structure is more flexible, and base_proof and merge_proof can be aggregated

  
  

Certificate Submission

When submitting, only the node maintainer (Forger/Slot leader) is eligible to be rewarded after submission, and within a specific submission period. If the submission fails or is not submitted within the time limit, it will be postponed to the next competitor. (Slot leader election uses the smallest block hash of an epoch on the main chain to generate random numbers.)

In Latus, both the block producer and the prover are rewarded, and the block producer packs, while the prover generates a certificate.

For basic state transitions, prove and verify are:

proof^{Base}{a} = Prove(pk^{Base}{a}, (s_i, s_{i+1}), (tx_a)) true/false = Verify(vk^{Base}{a}, (s_i, s{i+1}), proof^{Base}{a})

Among them:

• a ∈ {pay, FT, BT, BTR}
• s_i，s{i+1} are public inputs, si= Hash(State_i), that is, public input is the hash before and after the state transition, for Latus, it is the merkle tree root hash

For the merged SNARK, prove and verify are:

proof^{Merge} = Prove(pk^{Merge}, (s_i, s_{i+k}), (s_{i+j}, proof^b_1, proof^c_2)) true/false = Verify(vk^{Merge}, (s_i, s_{i+k}), proof^{Merge})

Among them:

• b,c ∈ {Base, Merge}
• proof^b_1 proves that there is such a transaction, tx_1, …, tx_j, enables State_{i+j} = update ([tx_i, …, tx_j], State_i)
• proof^c_2 proves that there is such a transaction, tx_{j+1}, …, tx_k, enables State_{i+k} = update([tx_{j+1}, …, tx_k], State_{i+j})

Summary

Judging from the white paper, Zendoo and ZK Rollup are quite similar. For Data Availability, the former involves the cross-chain generation of proofs, and sidechain transfers cannot generate. The latter will generate proofs for all L2 transactions and submit them to L1 verification. For withdrawal, Zendoo has BT/BTR/CSW, and ZK Rollup has similar operations such as Withdraw/Exit/Force_exit. For MST data maintenance, the existing ZK Rollup implementation basically applies a single node or a centralized node, while the Zendoo node is decentralized storage.

Compared with the current popular Polygon, Zendoo is decentralized in the cross-chain form, and anyone can submit a ZK proof, while Polygon applies authorized multi-signature bridges to control the billing on both sides of the contract to achieve cross-chain. As for the withdrawal time, Zendoo needs to generate a proof and submit it to the chain, the process which is more time-consuming, while Polygon is more centralized and time-controllable. Regarding the difficulty of implementation, Zendoo also needs a prover for generating proof in addition to the node. This requires the realization of a zero-knowledge proof circuit, which is more difficult to develop, while Polygon only needs to implement multi-signature contract control.

Reference

• https://heap.horizen.io/
• https://www.horizen.io/assets/files/Horizen-Sidechain-Zendoo-A_zk-SNARK-Verifiable-Cross-Chain-Transfer-Protocol.pdf
• https://www.horizen.io/assets/files/whitepaper-snarks.pdf
• https://academy.horizen.io/horizen/expert/sidechains/