Going Through the Weeds with Cryptos

By popular demand from the Twitterverse, we are currently creating a detailed documentation on the mechanics behind cryptographic math and decentralized technology which are the foundations for cryptocurrencies. This series will be EXTREMELY technically driven. For a laymen version please remain patient. I plan on ending this series with a summary that highlights the most important parts to understand.

The best analogy I heard from a client was the comparison to a camera r even a credit card. We (as a society) don’t necessarily understand the full mechanics behind the function, yet we use them on a daily basis. Same concept here. you do not need to fully understand the functionality and the details to know that it works. So, don’t get caught up in the details.

I’m going to start this series by breaking down the fundamentals of cryptographic math, the core infrastructure behind cryptocurrencies.

1.1 Cryptographic Hash Functions

There are 3 integral components in the hash functions that continue to keep cryptography a viable solution for security. The security properties lay the groundwork for protection against Bad Actors, Fraud, and Theft.

I) Hash Property: Collision-Free

It is impossible to find x and y such that
x! = y and H(x)=H(y)

Collisions DO exist, BUT can anyone find them?

With a large input possibility there is a high probability collision could occur without proper randomization.

How to find a collision:

Try 2¹³⁰ randomly chosen inputs and you’ll get a 99.8% probability that they’ll collide. This process is guaranteed to work no matter what the Hash function is, but it takes A LOT of computing power and even more time.

Let me contextualize on why it doesn’t matter. If every computer ever created was computing since the beginning of the entire universe up to now the odds that they would have found a collision would be infinitesimally small. So small that the odds of the human race being exterminated by Daleks in the next 2 seconds are drastically greater (waits two seconds — nothing happened).

DISCLAIMER: We (proverbial we) have not found a truly ‘collision-free’ hash function. We have tested many functions and have failed to find the collision. So, we CHOOSE to believe that these are viable solutions. Once again, collision is negligible regardless.

Application: Hash Message Digest

If we know that H(x) = H(y) then its safe to assume that x = y.

Example:
If we wanted to recognize a massive file we’ve seen before we can remember the contents of the file and/or compare it; OR we can simply remember the hash (256 bit — much smaller)

II) Hash Property: Hiding

We want something like this:
Given H(x) [output], it is impossible to find x [input].

PROBLEM:

For this to work there needs to be no value of ‘x’ which is particularly likely. ‘x’ has to be chosen from some set that is very randomized or spread out so that an adversary cannot chug&plug values to find x efficiently.

SOLUTION:
To solve this problem we are given ‘r’ which is chosen from a probability distribution that has high min-entropy, then given H(r | x), it is infeasible to find x. H(r | x) is just a hash function of r concatenated with x. Basically, take all the bits of ‘r’ and put after it all the bits of ‘x’.

high min-entropy means that the distribution is extremely “spread out” so that no particular value is chosen with more than negligible probability.

APPLICATION: Commitment
We want to “Seal a value in an envelope” leave it on a table for everyone to see and “open the envelope” later. Once we do this we commit to a value in the envelope but its seals. We can reveal it later. Let’s do this in a digital sense.

WARNING: This part gets daunting. Just follow the variables and it will make sense. Once again, DO NOT GET DISCOURAGED ABOUT THE DETAILS.

Commitment API:

1. (com, key) := commit (msg)
   Think of the commitment as the envelope you will place on
   the table and the key as a secret key to unlocking the
   envelope.
2. match:= verify(com, key, msg)
   Later, you allow someone else to verify that the msg (value)
   belong with the key and commitment. This will return a true
   or false.

To “seal” the message(value) in the envelope:
(com, key) := commit(msg) — then publish com
To “open” the envelope to “read” the message (value):
publish key, msg anyone can use [verify()] to check
— This effectively works like sealing an envelope.

Security Properties:

1. Hidden: Given com, it is infeasible to find msg.
   — Given the envelope, on the table, no one can figure out the contents.
2. Binding: Infeasible to find msg != msg’ such that
   verify(commitment(msg), msg’) == true
   — Once you commit to the contents of the envelope you CANNOT change . — whats inside it.

How this actually works:

Commit(msg):=(H(key | msg), H(key)), where key is a random 256-bit value
Verify(com, key, msg):= (H(key | msg) == com)

Security Properties:

Just plug in the definitions into the previous properties above and you get:

1. Hidding: Given H(key | msg), it is infeasible to find msg.
2. Binding: Infeasible to find msg != msg’ such that
   H(key | msg) ==H(key | msg’)

III) Hash Property: Puzzle Friendly

For every possible output value ‘y’, if ‘k’ is chosen from a distribution with high min-entropy, then it is infeasible to find ‘x’ such that H(k | x) = y

Application: Search Puzzle
Create a mathematical problem that searches in quite a large space for a solution. With no shortcuts or resolutions other than searching in that space.

Given a “puzzle ID” id (from H.M.E.), and a target set Y:
Try to find a “solution” ‘x’ such that H(id | x) {element-of symbol} Y.

The idea is that ‘Y’ is a set or target range of hash results that we want, ‘id’ specifies a particular puzzle and ‘x’ is the solution.

Puzzle-friendly property implies that no solving strategy is much better than randomly trying x-values. So long we can generate id’s in a .suitably random way (USE CASE — MINING BTC).

IV) Hash Functions: SHA-256 (BTC)

These are a popular hash function. There are many other functions out there this is just the easiest to understand and the function used by Bitcoin.

1.2) Hash Pointers & Data Structures

They tell us where something is and what it’s value is by verifying the contents have not been changed.

This structure is a log of data that can detect tampered log in the past, or prevent fraudulent logs.

So as you can see a simple linked chain data structure (blockchain) using hash pointers instead of the data we can create a more efficient and secure data storage. Another useful structure is a binary tree.

This hash pointer data structure is slightly more efficient than a linked chain data structure. Hash pointers work for all data structures that are non-cyclical.

1.3 Digital Signatures

— Only You can sign but anyone can verify

— Signature is tied to a particular document i.e. cannot be Copy & Pasted onto a new document.

ONCE AGAIN JUST FOLLOW ALONG, DO NOT BE INTIMIDATED.

I) API for Digital Signatures

1. (sk, pk):= generateKeys(keysize)

— sk = secret key

— pk = public verification key

2. sig:= sign(sk, message)

3. isValid:= verify(pk, message, sig)

The first are randomized algorithms and number 3 is structured.

II) Requirements for Signatures.

“valid signatures verify”

— verify(pk, msg, sign(sk,msg)) == true

“Impossible to Forge”

— An adversary who knows the (pk + msg) cannot produce a verifiable signature on another msg.

EXAMPLE:

III) Bitcoin ECDSA

Elliptic Curve Digital Signature Algorithms — Great randomness is essential. A U.S. Government standard.

I’m going to leave this section as follows the math associated with ECDSA gets really hairy. If you don’t believe me just look it up HERE

1.4 Public Key as Identities

Useful Trick: pk == an identity

If you see a sig such that verify(pk, msg, sig) ==true, think of it as pk says “[msg]”.

To “speak for” ‘pk’ you must know the secret key ‘sk’. Pks are considered a person, an actor, an organization etc, but is associated with an identity that cannot be used outside of the ‘sk’ holders permission (use case: double voting, fraud in money, etc).

I) How to Make a New Identity

create a new, random key-pair (sk, pk).

1. Pk is the public “name” you can use. [It would be better to use H(pk) as pk’s are long.]
2. Sk let you “speak for” the identity.
3. If you generate a pk that looks random than now one needs to know who you are.

II)Decentralized ID Management

This leads us to decentralized ID’s and ledgers (i.e. cryptocurrencies).

1. You can create as many new IDs as you want.
2. There is no central point of coordination
3. These are called “addresses” for Bitcoin. When you hear addresses in cryptocurrencies they are actually referencing a ‘pk’ or a H(pk).

III) Privacy

Addresses are NOT connected to real-world identity initially. HOWEVER, an observer over time can begin linking activity and start making inferences. Privacy with Bitcoin is complicated. I will go into greater detail on another blog later. All you need to know is that PK’s are similar to identities that only the person with the sk can use. Similarly, PK’s are public so it allows for both verification and possible convergence of ID reveal.

1.5 Cryptocurrency

Understanding the hash pointers and data structures lay the foundation for understanding the mechanics behind cryptocurrencies. The main challenge in creating a digital currency is to prevent Double-Spending Attacks.

Anyone can verify that I signed the chain because you can go back to see all transaction history as endorsed by me. For this example, we place 1 transaction per block but in practice, we are using optimization and placing multiple transactions per block.

I) Immutable Coins

You CANNOT transfer, subdivide, or combine. HOWEVER, you can create the same effect by using transactions to subdivide:

1. Create new transaction
2. Consume your coin
3. Payout two new coins to yourself (of = value split into new coins).
4. Repeat for combining or transferring.

II) Decentralized

We created an immutable coin and prevented double-spend attacks by using hash pointers to validate a transaction, so let’s start spending the money, right?

The problem now is me. This whole process can work perfectly, contingent upon my willingness to participate. I can claim to be trustworthy but in reality may be a bad-actor. A scenario that is even more devastating would be to stop participating altogether. Everything would freeze and the whole operation would cease to exist. This is the problem we face in legacy-banking institutions. We are forced to place our trust (and money) in a centralized institution that is notorious for being a bad-actor. So how can we accomplish decentralization that’s secure and valid?

We need to learn how to provide the same services that AngelCoin [Fiat-Legacy Banks] provide while creating an environment that is: decentralized, trust-less (the majority of participating party unanimously agrees while validating transactions as true or false), how to assign ID’s in a decentralized way, etc. In the next blog, I’ll go over Decentralization from a Top-Down approach. My goal is to dive deep into the mechanics behind effective decentralization and we will later talk about more efficient models compared to Bitcoin and/or Ethereum.

Please Say Hello On: Instagram | Twitter |

What’s New

Our Execs Newest Positions

Our executives Angel Mondragon (CEO) and Patrick Benske (CMO) were recently announced as Senior Advisors for a Public Company for Crypto Currency. Read Here

Whitepaper | Community

We are releasing a teaser for our whitepaper in addition to our first months results for our fund. We are releasing it on our telegram. Find the channel HERE.

Writer: Angel Mondragon. Edited: Patrick Benske.