We demonstrate a zero-knowledge proof of age protocol that could be easily implemented on a proof of process network
In a recent post, we outlined a technique of proving that a hidden value was greater than a given threshold without revealing it: “proof of balance”. Our method used an implementation of a general zero-knowledge framework, called a zkSNARK (courtesy of the pepper project). While immensely powerful, those of you who have played with zkSNARKs are likely quite familiar with its drawbacks in terms of efficiency and ease. Here we present a much simpler protocol to prove in zero-knowledge that an integer (such as age or balance) is greater than a known threshold.
The larger insight for the zero-knowledge aficionado is this:
There are lots of efficient, specialized protocols for proving something in zero knowledge. If you can’t find (or develop) one for your specific need, zkSNARKs can come to the rescue. However, most of the time, it’s worth looking for that specialized solution. At least twice.
Proof of Age Using Hash Chains
Let’s say Milena (who listens to 80s music and is clearly in her 30s) has been riding around town on her brand new yellow spotted tandem bicycle. Paula is dying to cruise around town on Milena’s bicycle and asks Milena out on a date. Milena is interested, but unsure of the legality of their potential adventure. If Milena and Paula have access to a trusted source of digital identification documents (their local government, for example), we would like them to have an easy “challenge and response” protocol, like the following:
Milena sends Paula a challenge: “Prove you are at least 18”
Paula sends Milena the response:
Milena verifies the response is correct: “Ok, I am convinced”
We could implement such a system with the following protocol, from a paper by Sebastian Angel and Michael Walfish. An overview of the protocols follows, but if you don’t care about the details, just skip to the end for the demo.
In the jurisdiction where Paula and Milena live, assume there is a trusted central document authority that provides proof services. Paula has requested a secret S from this authority, for use in proving her age. While the format of S is publicly known, each individual’s S should be kept secret. For this example, S is 256-bit string: 128 zero bits followed by 128 randomly generated bits. Let’s say Paula’s (S) is:
The Authority then calculates a hash-chain one link greater than Paula’s age:
If Paula is 19, the Authority would compute 20 iterative hashes to go from S to EncryptedAge. As good cryptographic hash functions are not easily inverted, it would be difficult for anyone to deduce S or the ActualAge from the EncryptedAge. This means we can distribute the EncryptedAge as needed, without fear that our ActualAge will be discovered. If we choose SHA-256 as our hash function, the intermediate links in the hash chain would be:
and the final link in the chain, the EncryptedAge, would be:
- Finally, the Authority sends Paula a Proving Kit, consisting of the following fields:
– Paula’s name in plaintext
– A timestamp
– Paula’s EncryptedAge
Paula, who is 19, receives Milena’s request to prove she is at least 18 years of age (The AgeToProve)
1) As Paula is eager to go for a ride on Milena’s tandem bicycle, she immediately calculates: Proof=HASH1+ActualAge−AgeToProve(S)=HASH2(S)
In this case, Paula only calculates 2 links in the hash chain to get Proof:
2) Paula then sends Milena the following response:
– The Authority’s signed Proving Kit (which contains her EncryptedAge)
– The Proof she calculated
- Milena first verifies the Authority’s signature on the Proving Kit, and then opens it. She then verifies that the name is correct (Paula) and that the timestamp is valid (perhaps more important when seeking to verify an upper bound on someone’s age).
- Milena extracts Paula’s EncryptedAge from the Authority’s message.
- Milena then calculates:
That is, she finishes the hash chain that Paula started.
- Milena checks if VerifiedAge=EncryptedAge. If so, she is satisfied.
Milena, of course, could just as easily use this protocol to evaluate the sufficiency of Paula’s monthly salary or the size of Paula’s vinyl record collection, if they could agree on a trusted certification authority. Either way, the protocol should guarantee its users completeness, soundness, and zero-knowledge, all of which we will see in the next section.
Some Desirable Properties
This protocol is only useful if it
- Always convinces Milena when Paula is old enough (completeness)
- Never convinces Milena if Paula is not old enough (soundness)
- Leaks no information about Paula’s actual age to Milena (zero-knowledge)
For any age AgeToProve≤ActualAge:
For any age AgeToProve>ActualAge, Paula would have to invert HASH(S) to send a convincing Proof. The exception to this is for AgeToProve=ActualAge+1, in which case Paula could just send S. However, as the format of S is publicly known, a watchful verifier would detect the fraud (and, in addition, be able to answer future challenges on Paula’s behalf)
For Milena to learn S, she would have to know ActualAge and be able to reverse HASH.
For Milena to learn ActualAge she would have to reverse HASH or know S and generate its hash chain until she found Proof.
Note that even if ActualAge=AgeToProve, Milena would learn nothing, as the Proof=HASH(S)
And now, for the Live Demo!
S : 00000000000000000000000000000000ydHtdcfEmPif8L1DB9QtXnvHEXhBacA2
Trusted Authority Generates _EncryptedAge_ ActualAge: 38
Challenge and Construction
Paula Answers Milena's Challenge AgeToProve: 19
Milena Verifies Paula's Response Against _EncryptedAge_
If you don’t trust the “verification” step above, you can complete the hash chain yourself by (repeatedly) using either of the following tools with the hexadecimal proof value from the demo:
Trust in human society is a complex issue and even a good cryptographic hash function won’t solve the entirety of the problem. However, in the context of signed messages from trusted sources, Angel and Walfish’s approach can help share only the desired property about our hidden data (in this case, whether the age is above a threshold) without revealing the data itself.
For other numbers (like a bank balance), significantly more computation may be involved, as the hash chains could have millions of links (or more). While specialized hardware for hashing does exist, the relevant Authority could also encode metadata in its signed message (the units of the encrypted value for instance) that optimize for the desired use-case.
At Stratumn, we are excited to be developing real-world applications to help individuals and organizations share their data intelligently, relevantly, and securely. This demo is another link in the chain that we are building to connect these extraordinary cryptographic tools to real-world applications.
Ankur Shah Delight is a crypto engineer and software architect.