Forget the Hype and See the Sheer Beauty of Blockchain: Merkle Trees, Schnorr Signatures, Fiat…
Forget the Hype and See the Sheer Beauty of Blockchain: Merkle Trees, Schnorr Signatures, Fiat Shamir and Pedersen Commitments
I strongly believe that if we started the internet again, we would select all the best elements of blockchain methods, and we would get rid of our 1980s viewpoint of our digital world. Servers, ports, operating systems rights, SQL databases, and so on, have all been built on flawed models of trust, and which do not mirror the world we actually live in.
I kinda worry, too, that the world does not see the true beauty of blockchain.
And so I will outline three things that I see as sheer beauty, and outline how they will change our world: Merkle Trees, Schnorr Signatures and Pedersen Commitments.
Forget the hype, there’s maths down there
In the world of physics, we see the beauty of Maxwell’s equations and of gravity, but for some reason, many fail to get beyond the ‘hype’ of blockchain and Bitcoin. Blockchain has become a word … a hype term … add it to anything you want, and it perks it up. And so, some people now use DLT, but it still — to me — sounds hollow. It is almost as if it has lost its meaning.
And why, when you see presentations on blockchain these days do so few people delve below the surface and see the beauty underneath? For many, it just seems like magic that solves all our problems, without actually explaining what the problem is, and why it solves it. Imagine if someone came up with a water powered car, and told us that it would run forever on one litre of water. We would want to probe inside and find out how it worked. That is the way our world has evolved. We probe and discover, but for some reasons— in blockchain — that whole probing and discovery process for those outside a selected community has evaporated, and all we are left with is the hype of the terms.
Underneath we find mathematical certainty within a digital world which is largely untrusted. It is a world where we can define with almost certainty that something has happen, by someone or something, and at a certain time. It is a world where identity and digital signing actually means something, and where we are not just login IDs that are owned by someone, but where we exist as unique entities within a global world. It is a world where we have ownership of things and it is not the Google and Facebook world of owning your identity, and of all of your online activity.
Like it or not, your data is you!
Not building on sand
We would not build our skyscrapers on sand, so why do we do the same thing with our information systems. The only way to break out of centralised viewpoint of the world is to build digital systems which scale, and integrate citizen rights and governance. For just now, if you appear in the log for a system, there is no real way of know if that is you or not, and no real way for it to be proved. For too long, large organisations have “owned” the Internet, and where very little can be trusted in our digital world. Our future must focus on building on a solid foundation of cryptography and software engineering, and build new digital worlds which scale. In finance, Ian Grigg proposed a seven-layer model [here]:
The most amazing digital tree
For me, the Merkle Tree is one of the most perfectly formed entities in computer science and an almost perfect representation of trust. For this, I start with a genesis block, and then every single transaction that ever occurred is now trustworthy, and I can check on every transaction in an instance, at any point in time. If you were to create a perfect bank, it would be based on the Merkle Tree. In almost an instance I can check the presence of a transaction.
But, the thing I find most beautiful is sheer beauty of the signing process … is the signing process. In cybersecurity we have grown up with the horrible PKI infrastructure, and where my public key is validated by a certificate authority. In this way, you need to develop a circle of trust and install the public keys of the certificate authorities on my computer. We have ended up with a jumbled mess of trust, that few people understand fully.
The most trusted of all signatures
With blockchain, and with ECDSA and Schnorr signatures, I create my own key pair, and then can instantly sign for transactions, and you can match my ID to my public key. This is a truly distributed world and does not centralise trust. I can now create my own ID, and sign things for my code updates, my emails, and everything else. Only I have the private key which defines my identity.
With the Schnorr signature, we create a signature (R,s) for a hash of the message (MM). We first generate a private key (x) and then derive the public key from a point on the elliptic curve (G) to get:
P=x⋅G
Next we select a random value (k) to get a signature value of R:
R=k⋅G
The value of s is then:
s=k−Hash(M,R)⋅x
Our signature of M is (s,R) and the public key is P.
To check the signature we calculate
P⋅Hash(M,R)+s⋅G
This becomes x⋅G⋅Hash(M,R)+(k−Hash(M,R)⋅x)⋅G
which is:
x⋅G⋅Hash(M,R)+k⋅G−Hash(M,R)⋅x⋅G=k⋅G
The value of k⋅G is equal to R, and so if the result is the same as R, the signature checks out.
A sample run with the message of “Hello” is (and where “BN” is “Big Number”) [here]:
Message:Hello
Private Key: dce71358bf6d57dffaf8ac422ea972dca65badd2ce21b585803ea3075b7de388
Public key: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27
Signature [s]: BN: 18573f5212373b51022b00cbe12276b8099a351526b3384ccd1f02ad71761ff1
Signature [r]: BN: 3d96504afbe3beec97a753c38d614ec5fa68cf8219df36d7cce891319058d5db
Public key recover: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27
Signature verified: true
In this case we have 256-bit private key (dce7 … 388), and produce a 512-bit public key (03 96e … 827) — the “03” part identifies that we are using a Bitcoin public key. Thus, if we know the message — and which will be stored on the blockchain in the case of Bitcoin — and the key, we can see that we can recover the public key from the signature.
One of the great advantages of the Schnorr signature is that we can sign more than one message, so that multiple parties can be part of signing for a transaction, and the system can instantly check that all of the signers have signed it.
Towards a world where ownership means something
Blockchain is squarely on the side of the citizen, and now we see ways that citizens can protect their own data, without relying on large companies to protect it for them. With Pedersen Commitments, we now see ways of those who own data having a way to hide it from others, and reveal when require.
So could we create a world which blinded Google, governments, and others, and where no-one could see our purchases, or, in fact, anything about our lives? It would be a world where we can reveal things only to those that we trust. In this world, companies, governments, and others would have to ask us for permission to see our data, and not just push one-sided T&Cs to us. Then, if we had audit/compliance regimes, we could create blinding factors so that only they could see the required information.
So how do we create a world where we can store our secrets in a trusted and then reveal them when required? Let’s say I predict the outcome of an election, but I don’t want to reveal my prediction until after the election. Well, I could store a commitment to my prediction, and then at some time in the future I could reveal it to you, and you can check against the commitment I have made. Anyone who views my commitment should not be able to see what my prediction is.
This is known as Pedersen Commitment, and where we produce our commitment and then show the message that matches the commitment. In its core form, we can implement a Pedersen Commitment in discrete logs [here]. But blockchain, IoT, Tor, and many other application areas, now use elliptic curve methods, so let’s see if we can make a commitment with them.
For this, we can obscure the values in a transaction by adding a blinding value. Let’s say that we have a transaction value of v, we can now define this as a point on the elliptic curve (H) as:
v×H
If we have three transactions (v1, v2 and v3), we can create a sum total of:
Total=v1×H+v2×H+v3×H=(v1+v2+v3)×H
We can thus determine the sum of the transactions. But we could eventually find-out the values of v1, v2 and v3, as they would always appear as the same value when multiplied by H. We can now add a blinding factor by adding a second point on another elliptic curve (G) and a private key (r). A transaction value is then (as defined as a Pedersen Commitment):
C = v×H+r×G
Let’s say that Bob has two input values (v1 and v2) and one output value (v3), and where v3= v1+v2. We can then create a blinding factor for each transaction:
C = (ri1×G+vi1×H)+(ri2×G+vi2×H)=(ro3×G+vo3×H)
Then:
ri1+ri2=ro3
In this case if we can prove this, we have proven that the inputs are equal to the outputs. A sample run is [here]:
Alice's secret key: 110672200165973757670706606013807185435784586203078289927107093258368544244209
Alice's public key: (97877912897005737218928527353789673381377340700475699151216756276689766435015L, 87838438629927847912046825769741818157159420065666269753906778707978168856075L)
==========================
Transaction (r1*G + v1*G) + (r2*G +v2*G): (75012975245730542912551430086949413769034689023115807054516566426350436876319L, 42840948626806857828893112378852997190784128370121817339191672098791182051629L)
Transaction (r3*G + v3*G): (75012975245730542912551430086949413769034689023115807054516566426350436876319L, 42840948626806857828893112378852997190784128370121817339191672098791182051629L)
Now let's compare...
Success!
A world where I can prove things, without giving things away
We are still in a 1980s view of our digital world, and where we actively give away our passwords, our date of birth, our home address, and so many things, and where we should just be proving things. Why does Facebook store a hashed version of my password? Don’t they know that in the Cloud, a cracker can be trying Terahashes per second? And that as humans we tend to put the upper case letter at the start and the numeric value at the end. The concept of storing passwords needs to end sometime soon.
One of the most widely used methods is the “non-interactive random oracle access” for zero-knowledge proofs. It is defined as the Fiat-Shamir heuristic [1].
In the case we will look at the use of a hash value for the non-interactive random oracle part. Normally Alice would pass a random value to whoever it is that wants to prove her identity, but in this case she will use the hash value to randomise the puzzle and answer.
The stages are:
1. First everyone agrees on a puzzle and has a secret (x). The puzzle is:
y=gˣ
where we agree on g and x is the secret that Alice proves that she knows. Let’s say that g is 13, and x is 11, so gˣ is:
1792160394037
2. Next Alice generates a random number (v) and calculates t, which is:
t=gᵛ
Let’s say that the value of v is 8. This gives t of:
815730721
3. She now computes a hash value (c) created from g, y and t:
c=MD5(g+y+t)
Let’s say this gives us 12 (we would normally limit the range of the value produced).
4. Now she computes r of r=v−c×t to get:
-124
5. Now she sends out t and r to prove her identity:
[815730721, -124]
6. Everyone who knows who wants to prove her ID will then compute (where c can be calculated as a hash of g, y and t):
t=gʳ×y-c
In this case the calculation gives 815,730,720, which is the same as the value of t that Alice sent, so they have proven her ID [here].
Every time Alice generates a new random number and proves that she knows the value of t each time.
Conclusions
We live in an almost completed untrusted digital world, and we are not trying to map our human world of trust onto it, and it just doesn’t work. This leaves our world open to abuse and cybercrime.
So, I don’t know if you see the beauty in what I have outlined, so I will repeat …
- I create transactions that go onto the Merkle Tree, and instantly we can all verify them, and know the state of our infrastructure at any time in the past. We can check everything and make sure that there are no transactions which are incorrect, as our system is balanced, and check at almost every instance in time.
- I create a unique ID for myself. It is a private key and a public key. I then do something and make a signature with an r and an s value, and instantly everyone knows that it was me who create this. With the Schnorr signature, I don’t have to rely on Microsoft Active Directory to prove my digital ID. I don’t have to contact Verisign and send them a scan of my passport and a utility bill. If that is not beauty is maths, I don’t know what is.
- I can blind my own data to whoever I want, but still prove things. We have created a world where our large cloud provides define their viewpoint of the world, and where we have very little control of it. With the Pederson Commitment, we can take ownership and properly define that we did things at certain times, without actually revealing it to anyone.
- I can prove that I still know my password, without actually revealing it. with the Fiat-Shamir method we can register a random value, and where you can’t tell the password which was used to generate it.
Forget the hype, and see the beauty!