MarcoPolo Protocol Sub-protocol: Ultra Light Verification Protocol(ULVP)

Introduction

MarcoPolo Protocol(MAP) is an open and completely decentralized chain-to-chain interoperation protocol that enables the interoperability of multiple independently verifiable consensus blockchains without a relay chain. It has two core components: the Ultra Light Verification Protocol and the Smart Script with Combinable Trigger Conditions. If you treat blockchain as a shared database, then the standard read operation is Ultra Light Verification Protocol and Smart Script with Combinable Trigger Conditions is write operation. Today I will give some details of the Ultra Light Verification Protocol.

For a larger group of users, the need of reading partial data from the blockchain is required. However, the simplified payment verification(SPV) technology requires users to download the block header chain and save it locally. The idea of straightly using SPV proofs is unrealistic in many critical use-cases such as mobile phones or IoTs because the header chain grows linearly as the blockchain grows. For example, the headers of Ethereum is growing at a pace of around 1 GB per year.

The effort about finding a sub-linear verification method began with Kiayias et al’s research on NIPOPOW. Their work can be applied to the POW type of public chain in the invariable difficulty setting. Most POW-based blockchain can not use this technology because they are under a variable difficulty setting. Is there a sub-linear verification method to work in a more general environment? The answer is Yes. Bunz et al proposed Flyclient to extend NIPOPOW to any Proof-of-X public chain (POW, POS, POET, etc.). MAP uses Flyclient technology to construct Ultra Light Verification Protocol.

Ultra-Light Verification Protocol(ULVP)

If a node wants to query a predicate relate to one blockchain using SPV, he needs to download a header chain. Then, he can request some randomly selected full node to relay the corresponding Merkle branch proof. After that, he can verify the Merkle branch proof based on his local stored header chain.

For ULVP, the first step is to validate one target block that exists in the blockchain using MMR and random sampling. Once this step is done, the remaining part is to get the Merkle branch proof corresponding one predicate to relate to the target block and verify this proof. The second step is the same as SPV, I will elaborate on the first step and show why this is called Ultra Light Verification Protocol.

Firstly, I want to introduce a new data structure named Merkle Mountain Range(MMR). This is a variation of the Merkle tree. The leaf nodes of MMR are block headers. Figure 1 shows the MMR construct by 12 block headers(from B0 to B11). The root of this MMR would be store in B12. Then, it is easy to provide Merkle branch proof corresponding any block from B0 to B11 if B12 was given. For example, if one verifier node needs to verify B5(blue marked) which was contained in the blockchain whose tail block is B12, then the prover can generate the Merkle branch proof(green marked) and relay it to the verifier. The verifier node can recover the root based on the Merkle branch proof and compare the recovering root to the root stored in B12. If the two roots are the same, then it means B5 is indeed in this blockchain, otherwise means B5 is not.

Figure 1: Merkle mountain range construct by block headers

The first step of ULVP is to validate one target block that exists in the blockchain. Thanks to MMR introduced above, this problem is equivalent to prove one given tail block of a blockchain is indeed the tail block of the main network. For POW-based blockchain, it means to prove the tail block is indeed in the longest blockchain in the whole network. From the security assumption of the Backbone Protocol, we know that the adversary cannot control more than 50% hash power of the whole network. Let us denote the advantage of the honest node is α. This means that the adversary can generate α blocks when an honest party generates one block. In ULVP, the prover doesn’t provide the whole header chain. How can a verifier tell which tail block to choose if two provers provide two different tail blocks? Let us see Figure 2

Figure 2: Adversary fill some invalid blocks to exceed the honest party

we set α =0.4, then, when an honest party generates 5 blocks, the adversary can mine 2 blocks(yellow blocks). If he wants to cheat the verifier, he will need to fill 4 malicious blocks(blue blocks) to exceed the honest chain. If the algorithm can sample enough so that the verifier can detect these malicious blocks, then this algorithm can be used to prove the tail block one prover claim is indeed filled by all valid-mined blocks. Thus, the verifier can compare the length of all the valid candidate tail blocks and simply select the longest one. This would guarantee that the verifier picks the exact same tail block as the honest majority picks.

Now the problem becomes how to design a sampling algorithm to make sure the verifier detects malicious blocks with overwhelming probability. It can prove that for any sampling distribution over the blocks defined by a non-increasing PDF f, there exists another distribution with an equal or higher probability of catching the adversary. Thus, the optimal distribution over the blocks must be defined by an increasing PDF. Furthermore, Bunz et al prove that the optimal distribution defined by the PDF

maximizes the probability of catching any adversary that optimizes the placement of invalid blocks. And if we use this optimal distribution, we can sample

blocks to bound the failure probability of catching the malicious blocks below 2^{-λ}, where n is the length of the blockchain.

One way we use this sampling algorithm is to let the verifier sample some blocks with certain height and request prover prove the corresponding MMR branch proof. However, we can transform the interactive protocol into a non-interactive protocol using the Fiat-Shamir heuristic. This means that the randomness used to determine which blocks are sampled is derived using a secure hash function (say, SHA-3) applied to the tail block of the chain. The verifier not only checks the queries itself but also that the randomness was properly derived. Now the new procedure is prover first use the hash of the head of the chain as the random seed to sample enough blocks and generate the MMR branch proof corresponding these sampled blocks. Then, the prover sends this proof to the verifier. The verifier first verifies that the randomness comes from the hash of the tail block is correct, and then verify that the MMR branch proof is all valid. If both checks pass, the proof is valid and the tail block represents a blockchain with all valid blocks.

Now we conclude our algorithm of finding the tail block which honest majority agree as follows:

1. The verifier connects some randomly select provers(at least one of these must be honest) and request them to send their tail block and corresponding proof.
2. The verifier verifies the proof with the longest tail block.
3. If it is a valid proof, the verifier would select this tail block as his choice and he can use this tail block for further process. If the proof is invalid, he would drop this prover and verifier the second-longest tail block. The verifier continues this process until he finds the tail block with valid proof. Based on our assumption, he connects at least one honest prover. Thus this algorithm would eventually find the honest tail block.

Conclusion

The Ultra Light Verification Protocol(ULVP) has the following three characteristics:

Security: ULVP can ensure that the result of the predicate query is consistent with the honest majority’s choice. An adversary can cheat the verifier with a negligible probability(less than 2^{-λ}. It should be noted here that the security we are talking about is the security of the verification protocol itself, not the security of the consensus of the blockchain.

Succinctness: ULVP can ensure that the network resources and local storage resources the verifier node need when acquiring the result of a predicate are sub-linear growth, that is, they do not increase significantly with the height of the chain. For example, the length of Ethereum blockchain is approximate n=2^{22}, and suppose one attacker can hold around one third hash power of the total network, the proof size is below 400 KB with a failure probability of 2^{-50}, which is significant small compare to 5GB which SPV requires.

Non-interactive: ULVP can ensure that the verification process is non-interactive, that is, the final result would not be obtained through multiple rounds of question and answer communication.

· MarcoPolo Protocol Twitter and Telegram Channel (For the latest news)

· MarcoPolo Protocol Telegram Community: English, Россия, Türkiye, Việt Nam, Brazil, and Indonesia; Korean Kakao Community: 코리아

· MarcoPolo Protocol Medium (For the latest articles)

· MarcoPolo Protocol WhitePaper, and Roadmap

· MarcoPolo Protocol GitHub (For the complete codes)

For more information, visit marcopolo.link

Conclusion