Format of public key, signature and key_hash literals

Question

According to grammar present in Michelson specification, there are string constants for types signature, key, key_hash. What is the precise format of these strings? Specifically:

1. Suppose I have a key edpktieBMrR9Df3dqzZAJpDZBXb1h188fyrQyRJcm5RH2WpbvMVR8b. It's a ed25519 public key which is 32 bytes. How do I convert this string to bytes?
2. Same question about signature and key_hash.
3. Which hash algorithm is used to compute key_hash? Which data is hashed? 32 bytes of the public key?

Answer 1

There are some Python code to do that in this blog and a comment posted by Alain:

http://www.ocamlpro.com/2018/11/21/an-introduction-to-tezos-rpcs-signing-operations/

Answer 2

1) About the ed25519 public key, and how it is in bytes:

From [1]:

Ed25519 keys start life as a 32-byte (256-bit) uniformly random binary seed (e.g. the output of SHA256 on some random input). The seed is then hashed using SHA512, which gets you 64 bytes (512 bits), which is then split into a “left half” (the first 32 bytes) and a “right half”. The left half is massaged into a curve25519 private scalar “a” by setting and clearing a few high/low-order bits. The pubkey is generated by multiplying this secret scalar by “B” (the generator), which yields a 32-byte/256-bit group element “A”.

To convert it to this String format you need to split it to 6 bit chars as per the Base64 format transformation.

Based on this Q/A (see: [2]), the public 32 bytes / 256 bit key should be 51 bytes or in Base64 format 68 characters.

Your key example seems to have 54 chars, which seems weird, because it is none of the above.

(I modified it to slots of 5 x 10 + 1 x 4)

edpktieBMr R9Df3dqzZA JpDZBXb1h1 88fyrQyRJc m5RH2WpbvM VR8b

That reveals Tezos have different encoding: Base58. That was mentioned in your original link:

contracts, addresses, keys and signatures are written as strings, in their usual Base58 encoded versions (readable), or as their raw bytes (optimized).

To decode, there was a python call base58check.b58decode in the FLF OCP's answer link content.

2) signature and key_hash

signatures are also base58. (see 1)

I found about key_hash that it is its own datatype in Tezos (one of the few ones) and it is used like this:

We can combine those atomic types to build more complex types using constructors. For instance pair int string represents a pair of two value, an integer, and a string, or signature string represents a value that is either a signature or a string, list timestamp a list of time-stamps, and map key_hash nat is the type of an associative map between the hash of a public key and a positive integer.

Other types:

timestamp: Dates in the real world.

mutez: A specific type for manipulating tokens.

contract 'param: A contract, with the type of its code.

address: An untyped contract address.

operation: An internal operation emitted by a contract.

key: A public cryptography key.

key_hash: The hash of a public cryptography key.

signature: A cryptographic signature.

3) About key hash formation:

I did not found more than the usage of it and the fact it is a native type in Tezos.

My Sources:

[1] https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/

[2] https://crypto.stackexchange.com/questions/44584/ed25519-ssh-public-key-is-always-80-characters-long

[3] https://hackernoon.com/hash-consing-in-tezos-e4a59eeea5cd

Answer 3

In Michelson, those types accept two different formats of data (as you mention) - optimized and readable. The readable versions are the base58-check encoded strings (edpk*, tz1*, edsig*, KT1* etc).

The optimized versions are hex bytes that conform to a specific format based on the type of data, for example public keys are either 33 or 34 bytes - a 1 byte tag followed by the public key bytes (32 for ed25519 keys, 33 for secp256k1 and p-256 curves). You can decode a edpk using the following javascript:

eztz.utility.buf2hex(eztz.utility.b58cdecode("edpktieBMrR9Df3dqzZAJpDZBXb1h188fyrQyRJcm5RH2WpbvMVR8b", eztz.prefix.edpk));

Since this is an ed25519 key, you prepend a 0 byte tag, giving you the following in optimized form:

000a0813d070315836bab6e6f57244a291ba61832280fc3db7ad6d6f75920581b4

You can view more about the prefixes here and different formats for optimized forms here

Regarding the hashing function, we generate a 20 byte hash of the 32/33 byte public key. You can see how this is done with eztz here