I am starting to learn and write about cryptography use cases in blockchain technology. I will skip the basic stuff like digital signature, public-key cryptography in general, and look into some specific technologies that are used in some specific cryptocurrencies projects.

I will start with zk-SNARKs in this one. zk-SNARKs stands for zero knowledge Succinct Non-interactive Argument of Knowledge. Zero-knowledge here is exactly the popular protocol in cryptography where a prover can verify that the prover knows certain knowledge to a verifier without revealing it. In cryptocurrencies, zk-SNARKs is a variant of zero knowledge proof that is able to verify a transaction to the nodes without revealing the information about this transaction. This is giving a nice privacy feature to the blockchain world where every transaction is normally publically available. Zcash is an example crypto project that uses zk-SNARKs.

Before going into the technical details, it is worth noticing that zero-knowledge is actually the focus of this protocol in terms of its construction, instead, most efforts of this protocol are on efficiency. Unlike traditional zero knowledge proof that requires frequent communication between the prover and the verifier, zk-SNARKs requires very little communication between the two parties since it is costly in the blockchain world.

So what do zk-SNARKs do exactly? Say Alice creates a transaction and wants to transfer 10 bitcoin to Bob. Alice would need to tell the whole world all about this transaction because the nodes need the information to check whether the transaction is valid. With zk-SNARKs, Alice can prove the transaction is valid without revealing the details of the transaction.

Let’s focus on hiding the amount of the transaction. How can a transaction be verified if the amount is not revealed? zk-SNARKs do so by providing proofs of:

1) the number of coins Alice has equals the number of coins she sends to Bob plus the number of the change (Bitcoin’s UXTO protocol requires all money to be spent in a transaction and the remaining part is the change).
2) the number of coins Alice going to spend is not negative.
3) Alice does have that amount of coins as input.

The first point can be achieved by homomorphic encryption without revealing the number. That is, E(a+b) = E(a) + E(b), where a and b are the money spent and the change. By applying an encryption function that is addition homomorphic, doing addition before encryption and doing encryption before addition outputs the same result, which means a and b do not need to be sent in plain text.

With the first point satisfied, an evil thing Alice can do is to send a negative number to Bob, which will also pass the test of addition. So Alice also needs to prove the number is not negative, in other words, the number is in a certain range. At a rather high level, the range proof needs to be expressed as some polynomials. This was a bit hard to understand for me and it totally worth another article to explain. In short, computable problems can be expressed in polynomials. The verifier can then check whether certain x values in the polynomials correspond to the correct y values. The reason for using polynomials is that, even one simple change in a factor in polynomial results in different y values in almost every corresponding x value, which means a single random check on a certain x value already gives a great guarantee of the correctness of the knowledge.

The last point is to prove that Alice does own that much money. The first method is to use the output from the previous transactions that Alice received as the input of this transaction. As we can imagine, we then have a problem of proving the very first transaction is valid without revealing the number, otherwise all efforts of handling later transactions would be in vain. This is again out of the range of this article unfortunately 🙂 The second method is to keep the so-called world state in the blockchain and the balance of Alice can be checked in the world state. Of course, the balances are hashed in the world state, it’s in the form of Merkle trees actually.

This article will stop here, leaving so many problems unexplained. How to transform the problem into polynomials? How is this protocol non-interactive? Hopefully I will write about them soon 🙂

网站: http://thediscriminationfreemodel.uk

我的毕业设计是一个防止算法歧视的工作流. Demo和实验放在了网站上.

防止人工智能算法歧视的工作很多, 但很多研究提出的方法并不考虑用户隐私, 是基于有对训练集有控制权的假定提出的.

因此我设计了一个工作流, 通过可信第三方的介入, 只应用不需要访问训练集的方法, 帮助在公司用算法分类用户的过程中减少歧视.

其中还应用了差分隐私减少这个工作流对企业的影响. 本来为了防止歧视, 工作流的设计限制了企业对用户隐私数据的访问. 但是鉴于这些数据可以有其他商业用途, 应该给企业一定的访问权限. 差分隐私正好可以让企业在统计级别访问这些隐私数据, 而又不揭露个人隐私.