A Blockchain the Size of a Few Tweets – Hacker Noon

Cryptographic Hash — a mathematical algorithm that takes an input of any size and outputs a different, (nearly) unique fixed-length string.

So if we want to hash “This is a banana paper” — we send that string of characters through the algorithm and get this output: “DEA3C406BC9982AD485BCDDC4CD1E7B7A6C1CE819786F7520157743CCD93EE5F”

(For a readable, but detailed explanation of how hashing works, check out this page. At a very simplified level, the algorithm converts the text to binary, then takes the binary through a defined series of simple functions, like adding zeros, breaking the number into pieces, adding steps together, and so forth, until there is a fixed-length result that can’t be reversed-engineered.)

The key here is that the same input generates the exact same output (hash value) every time. But, it’s a one-way process — you can’t figure out the input by somehow starting with, and reverse engineering, the output. The only way to figure out the original input is to “brute-force attack,” or do massive amounts of trial and error of input values, until the desired output hash value occurs. Which, in most cases, is nearly impossible.

Although no one can realistically figure out your original value, you can, using the output value, offer proof of knowing the input without having to reveal it. And anyone else who knows (or later knows) the input can verify that you are telling the truth.

Negligible Function — A cryptographic hash where the chances of someone hacking the hashing algorithm through a brute-force attack (as mentioned above) is very, very small. That’s a good thing!

Collision — If there are more possible inputs than outputs in a hashing algorithm, then sometimes different inputs will by definition have the same output value. So — if we hash something using SHA-256 (a popular set of hashing functions that I used in the example above), which uses inputs of any length, but always outputs 256 bits, inevitably (but rarely) there will be the same output for different inputs, or “collisions.”

Collision Resistant Hash Function — a hashing function where the above collisions are rare. That’s a good thing. It’s difficult to create a collision resistant hash function, but the algorithms in modern hash functions do a pretty good job.

zk-SNARK — “Zero Knowledge Succinct Non-Interactive Argument of Knowledge.” zk-SNARKS are a method for someone to prove, very quickly, that they have some piece of information (such as a key) without revealing the actual information, and without having to interact back-and-forth with the person that verifies the information. That’s complicated, and very difficult to explain using an analogy, because this truly is a unique ability that is only possible through cryptography.

But let’s try. Imagine you’re sitting in a wooden desk chair in a small, bare room, lit by florescents, in some downtown police station. Straight out of the movies. And the cops have you connected to this brand-new lie detector that’s right 100% of the time. The detective walks in and says, “We’re on to you. We know you killed Bob. Admit it!”

Now, you didn’t kill Bob. And you can prove it. But the problem is, you don’t want the detective to know how you can prove it, because on the night Bob was killed you were actually at that detective’s house sleeping with his wife!

But calm down, it’s ok. Because this lie detector is special, and it allows you to whisper into a microphone so that only the machine can hear you. So you whisper to the lie detector: “I didn’t kill Bob; and I can prove it because I was at the detective’s house that night.” The lie detector reveals to the detective that you are innocent, but never has to reveal to the detective what you said. You’re safe and on your way home. But be smarter next time and don’t mess around with a cop’s wife.

I’m telling the truth officer. But don’t ask me what I said!

That’s a decent analogy. Not perfect. But the point is: zk-SNARKS are a fast way to prove that what you are saying is true, without having to reveal what you said.

One popular use of zk-SNARKS in the blockchain world is the zCash implementation. In zCash, zk-SNARKS are used to keep transactions private — you can prove that you sent someone else some amount of coins without revealing the details of that transaction.

Exactly how zk-SNARKs work is complicated. You can start here for more details.

Merkle Tree — A tree of hash values (the output from the cryptographic hash described above) in which every node that has no children (a leaf) is the hashed value of an actual piece of data in the system. All the other nodes (that do have children) don’t have the hashed value of data, but instead their value is created by combining, and then hashing, the hashed values of their direct children.

By Azaghal — https://commons.wikimedia.org/w/index.php?curid=18157888

For example, above is an example of a binary hash tree from wikipedia. In this example, hashes 0–0 and 0–1 are the hashed values of the data L1 and L2, respectively, and hash 0 is the hashed value of the combination of hashed values in 0–0 and 0–1.

Merkle Trees are very helpful in that they allow us to verify the entire tree of data, or just a certain branch or leaf of data, with just one hash, and without having to traverse the entire tree. Basically, if you know one node is true, you know all the nodes under it are true. A Merkle Tree says — hey you can trust this guy A, and because you trust this guy A, you can trust all of his children, because he trusts them.

read original article here