HollowDB Authentication

Answering "who dis?" with Zero-Knowledge.

HollowDB is a key-value database, and we want users to have control over their data, i.e. only they should be able to change the value at their respective key. This is achieved by the following:

• User knows some secret $s$.

• They hash this secret to obtain a key $k$ as in $k := H(s)$.

The user will PUT to this key, and only they will be able to UPDATE or REMOVE this key! This is done by requiring a ZKP that whoever wants to update some key knows the preimage $s$ of that key. Let’s rewrite the diagram above to show what is happening here:

merm2-l.png

Preimage knowledge proof generation & verification

Let’s examine this diagram:

• The client wants to update some key that they know the preimage of, with some new value.

• Client generates a zero-knowledge proof to prove that they indeed know the preimage. They send the proof, along with the key and the value to the smart contract, which is HollowDB.

• Within the smart contract, the proof is verified and if it is valid, the key is updated. If proof is invalid, transaction is reverted.

The important point here is that Smart Contract does not see preimage at all!

Security Issues

If you think about this method in practice, it has two security issues:

• Replay Attack: If an adversary gets hold of your proof, they can use that proof to claim that they know the preimage to your key even though if they don’t! This is like someone stealing your credit card, and then doing contactless payments that do not ask for password on low amounts. We would like to prevent this.

• Middle-man Attack: Another issue is that the proof contains nothing related to the value to be written. If an adversary steals your proof before it gets to the smart contract (perhaps a middle-man between you and the smart contract) then they can change the value to be written by simply using your proof.

The solution to these problems are simple: we need to put some constraints within our proof related to the current value and the new value to be written.

• if the proof is only valid for some current value at that key, it will be invalid when that value changes, thus preventing the replay attack.

• if the proof is only valid for the new value that I am going to write to that key, it will be invalid for any other value, thus preventing the middle-man attack.

However, we have said that arithmetic circuits operate on integers, but our values can be anything; so how do we represent our values as integers? The answer is: hashing! The client will hash both the current value and the new value separately, obtaining two hashes. So now let’s see the final diagram that shows how how both attacks are mitigated:

merm3.png

HollowDB Authentication proof generation & verification

A technical note must be taken here: you must ensure that the resulting hash is within the limit of the finite-field used in the circuit. For example, Circom supports the Baby JubJub elliptic curve for its arithmetic circuits to be used in Ethereum, and the order of the finite field is:

21888242871839275222246405745257275088548364400416034343698204186575808495617

This means that any value in your circuit must be less than this number. If you have a larger number, they will wrap back around as in modular arithmetic. You can use different curves and thus different orders, but this is important to keep in mind.

The number above is around 254 bits, and if we were to input a 256-bit number, things may work without the way we intend them to. This is especially important if we are trying to use a hash as an input. One could use hash functions with smaller output size, such as ripemd160, which has a 160-bit output and is definitely within the limits of our arithmetic circuit which is much larger. There are other methods to "fit" a hash within a field element too.