In A Privacy-aware World, Merlin Is Cool

In A Privacy-aware World, Merlin Is Cool

Our digital world gives away too many of our secrets, and really, it doesn’t have to. Every time we prove our password, we have to pass it to a service, and which then validates it. Why does the system have to store our secrets? Why can’t we have a little puzzle to solve, and which can only be solved if we know our secret? And so, with zero-knowledge proofs (ZKPs) we can.

With ZKPs, Bob initially registers a blinded value of his secret. No one will be able to know his secret from the blinded value. When Bob tries to prove that he knows his password, Alice sends a challenge to him, and then he computes an answer which proves he knows his secret. This is known as an interactive ZKP, and requires some form of handshaking of data between Bob and Alice. A basic interactive version using elliptic curve cryptography is [here]:

In this case, Bob has a secret (x) and creates two elliptic curve points (xG and xH), and sends these to Alice. Alice then sends Bob a scalar value (c), and he then selects a random scalar (v). Next, he computes r, and sends r, vG and vH to Alice. She then does a quick check with the values she has and the values that Bob has sent and can prove that Bob knows x.

But, Bob could also generate his own challenge and answer and gives it to Alice. Alice then checks that the challenge Bob has created is a fair one — and that Eve could not have faked — and that the answer is correct. This is a non-interactive ZKP (NI-ZKP) and cuts down on the overhead of the interaction between Bob and the service. In this version, Bob still generates a random value (v), but now generates his own challenge (c) and which Alice can also compute. This challenge is still much the same as the previous version but is a hash of all the values that he previously sent:

The challenge is then the hash of xG, xH, vG and vH. As Alice knows all these values, she checks the proof is correct (with r, vG and vH, along with Bob’s registered commitments of xG and xH). If the proof checks out, she will know that Bob still knows his password, and will then allow him to log in. In this case, Alice has not been prompted for anything, but Bob has given her the proof she needs.

Meet Merlin

The actual interaction details between Bob and Alice can be a little vague, so Henry de Valence created the Merlin protocol. This protocol aims to automate the Fiat-Shamir method by creating a non-interactive proof through interactive methods. With this, we then create two domains — for Bob and Alice — and create all the required challenges and requests. Thus, for the first time, we now have a library that can robustly generate challenges and responses for both Bob and Alice.

One of the first implementations of Merlin is within Bulletproofs, and where a Bulletproof allows us to create a proof that an integer value (x) is between 0 and 2^n. We can use this method within privacy-preserving cryptocurrency, and where we can prove that Bob has enough UXTOs (unspent transaction outputs) to pay for something without revealing any of his transactions.

In the following, we create a Merlin transcript with a new session label (“test”), and then feed it into a Bulletproof proof that a value (v) is in the range of 0 to 2^n [here]:

Finally, Merlin uses the STROBE framework, and which is a lightweight cryptographic infrastructure for efficient operations.

Conclusions

The whole area of NI-ZKP has struggled through a lack of standardization in the labels and the basic exchange protocol. Merlin now provides a new foundation for building a privacy-aware digital work, and Bulletproofs is one of its first application areas.

You can read more about Merlin here:

If you want to learn more about the Coinbase Kryptology library:

https://asecuritysite.com/kryptology