Cryptographic hash functions

Function

A function is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output.

Hash Function

A function that can be used to map data of arbitrary size to data of fixed size.

Cryptographic Hash Function

It is a special class of hash function that is a mathematical algorithm that maps data of arbitrary size to a bit string of a fixed size (a hash) and is designed to be a one-way function, that is, a function which is infeasible to invert. The only way to recreate the input data from an ideal cryptographic hash function's output is to attempt a brute-force search of possible inputs to see if they produce a match, or use a rainbow table of matched hashes.

The input data is often called the message, and the output (the hash value or hash) is often called the message digest or simply the digest.

A cryptographic hash function has several attributes.

• It can take any string as input of any size.
• It produces a fixed-size output, like 256 bits (that's what bitcoin uses).
• It has to be efficiently computable - Given any string of data, you can figure out what the output will be in a reasonable length of time.
• It is deterministic so the same message always results in the same hash
• It is infeasible to generate a message from its hash value except by trying all possible messages
• A small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value
• It is infeasible to find two different messages with the same hash value

Cryptographic Properties of a Hash Function

• Function needs to be collision-free
  • No one should find values x and y, such that x and y are different, and yet the hash of x is equal to the hash of y.
  • Collisions do exist
  • There can't be any collisions that are findable by regular people using regular computers
• Function has a hiding property
  • No one should be able to figure out what the input was based on the hash output.
  • Commit to a value, but reveal it later.
  • Binding
• Function is puzzle-friendly
  • There's no solving strategy for this puzzle, which is much better than just trying random values of x

Bitcoin and the SHA-256 Hash Function

SHA-256 or SHA-256 takes the message that you're hashing, and it breaks it up into blocks that are 512 bits in size. The message isn't going to be exactly a multiple of the block size, so you have to add some padding at the end. The padding is going to consist of a 64 bit length field, which is the length of the message in bits. And then before that, it's going to consist of a one bit followed by some number of zero bits. And you choose the number of zero bits so that it comes out exactly to the end of a block.

So once you've padded the message so that its length is exactly a multiple of the 512 bit block size, you then chop it up into blocks, and you then execute this computation. You start with the 256 bit value called the IV. That's just a number that you look up in a standards document. And then take the IV and the first block of the message. You take those 768 total bits, and you run them through this special function, c, the compression function, and out comes 256 bits. You now take that with the next 512 bits of the message, run it through c again, and you keep going. Each iteration of c crunches in another 512 bit block of the message and mixes it in, sort of logically to the result.

And when you get to the very end, you have consumed all of the blocks of the message plus the padding. The result is the hash, that's a 256 bit value. And it's easy to show that, if this function, c, this compression function is collision free, then this entire hash function will also be collision free.

Hash Pointers

A hash pointer is a pointer indicating where some information is stored. A regular pointer gives you a way to retrieve the information. A hash pointer is going to let you ask to get the information back. It's also going to let us verify that the information hasn't changed. So a hash pointer tells us where something is and what its value was.

A series of blocks with each block having data as well as a hash pointer to the previous block in the list. The hash pointer says where it is and what the value of the entire previous block was. This gives the blockchain a tamper evident log.

A tamper evident log prevents an adversary from changing the contents of a single block because once they do, they have changed the hash of that block which then creates an inconsistency with the hash pointer of the preceding block. So, they would then need to change the hash pointer of the preceding block to match the hash of the blocked they changed. As soon as they do that however, they have created an inconsistency between that hash pointer and the hash of that block. They would need to change the hash of that block as well to match that hash pointer. But again, once they have done that, they have another inconsistency between that Hash and the hash pointer of the preceding block.

So, if the adversary wants to tamper with data anywhere in this entire chain, in order to keep the story consistent they would have to have to tamper with hash pointers all the way back to the beginning. But, ultimately, they would run into a road block because they can't tamper with the head of the list at the very beginning.

And so you can build a block chain like this containing as many blocks as you want going back to some special block at the beginning of the list call the "genesis block". That is a tamper evidence log built out of the block chamber.

Digital Signatures

3 Operations that are Needed

1. Generate keys
   1. generateKeys operation
   2. Keysize - how big in bits the key needs to be
   3. Produce 2 keys
      1. Secret Signing Key (sk) - this is information you keep secret that you use for making your signature.
      2. Public Verification Key (pk). What you give to everybody and that anybody can use to verify your signature when they see it.
2. Sign Operation - This take your secret signing key and you take some message that you want to put your signature on and it returns, sig which is a signature. It's just some string of bits that represent your signature.
3. Verify - Takes something that claims to be a valid signature and verifies that it's correct. This takes the public key of the signer, and the message that the signature is supposedly on and it takes the supposed signature, and returns yes or no, to whether the signature is valid or not.

2 Requirements for a Signature

1. Valid signatures will verify - If a signature is valid, that is, if you sign a message with (sk), using your secret key, and if someone then tries to validate it using your public key with the same message, it validate correctly.
2. Impossible to forge signature - An adversary who knows your public (verification) key and gets to see signature on some other messages, can't forge it on another message.
3. Randomness - It needs a good source of randomness

Bitcoin uses a particular digital signature scheme that's called the Elliptic Curve Digital Signature Algorithm (ECDSA). This is a US government standard which relies on some extremely complex math but not good randomness. Good randomness is especially essential with ECDSA. If you use bad randomness in generating keys or even in signing, you probably leaked your private key. It stands to reason that if you use bad randomness in generating a key that the key you generate is not secure.

Public Keys as Identities

In order for a public key to be an identity, someone should be able to speak for the public key (pk), meaning, that someone can make statements so it appears to be coming from pk. To do this, you have to know the matching secret key (sk). If you know the secret key that corresponds to the public key, then you can sign messages with that secret key. What you're doing essentially is making statements on behalf of that public key. And that means there is an identity in the system which only you can speak for, and that's what you want. You want, something that one person can speak for or on behalf of another and that everybody can see.

If you treat public keys as identities one of the consequences is that you can make a new identity whenever you want. If you want to make a new identity you just create a new random key pair sk and pk by doing the generate keys operation in our digital signature scheme and you get out sk and pk. pk is then the public name that you can use that represents the name of that identity, although in practice you'd probably use the hash of pk because public keys are big. So pk, or the hash of it, is the public name that we use to talk about the identity, and sk is the information that lets you, the person who generated this identity, speak for the identity. You control the identity because only you know the secret key, and if you generated this in such a way that the public key pk, looks random, then nobody needs to know who you are. You can generate a fresh identity that looks random, that looks like a face in the crowd that only you can control.

Decentralized Identity Management

There is no central point of control, so that you don't have to have anyone in charge of it. This is the way Bitcoin does identity. These identities are called addresses and are just public keys or hashes of a public key. It's an identity that someone made up, out of thin air. As part of its decentralized identity management scheme.

**How private is this? **

On the one hand, the addresses that are made up this way are not connected to a real world identity. You can execute a randomized algorithm, that will make some kind of PK that looks kind of random. And nothing exists initially to connect that pk to a real person. On the other hand, if you want to act privately and use that address, you need to be careful because if that identity makes a series of statements over time, people can see that whoever this is has done a certain series of actions and they can start to connect the dots and see this person is acting a lot like a specific person, so maybe it is this person. So, an observer can link together these things over time and make inferences. This is determining patterns of behavior for an address that emerges over time. The question then becomes, what can be inferred and which dots can be connected which is very complicated, and is really the question of privacy for cryptocurrencies like Bitcoin.

Cryptocurrencies

Double spending attack is the main design challenge in the cryptocurrency space. The public decentralized ledge helps deal with the double spending attacks.

Coins are never changed, they're never subdivided, they're never combined. All they are is created once in one transaction, and then later consumed in some other transaction. But you can get the same effect as being able to subdivide or pay on or combine coins by using transactions. For example, if you want to subdivide a coin, you can just create a new transaction that consumes that one coin and then produces two new coins of the same total value. And if you want you can give those two new coins back to yourself. That's a way that you can subdivide a coin that you own. Similarly, you can combine coins or you can pay on a coin, in effect, by just creating a chain of transactions. Each of which pass that value on in the form of a new coin to someone else. So although coins are immutable in this system, it has all of the flexibility of a system that didn't have immutable coins.