Anatomy of Factom’s Addresses — Factomize

Brief Overview

You need Factoid Addresses and Entry Credit Addresses to do anything in Factom, so I wanted to dive a little deeper. There are three parts that make up an address: the private key, the public key, and the address. The private key is the most important element and can be used to derive the other two components. The public key can be used to verify data signed by the private key as well as derive the address. The address itself is a hash of an RCD mechanism to allow for multiple authentication schemes, and it cannot be used to determine either the private or public keys.

While using Factom, you are typically only presented with two of these three components: the private key and the address, both of which are in a “human readable” form. The public key only makes an appearance when signing a transaction (or arbitrary data), a step that is typically generated by the wallet or APIs in the background.

Base58

Before doing anything else, we need Base58. Base58 is a way of displaying a number as text using the same math as binary or base64, with the difference between base58 and base64 being the lack of confusable letters, namely: 0 (zero), O (capital o), I (capital i), and l (lowercase L), and the base64 characters + and /.

Here’s a chart with the numerical values ( Val) and the corresponding base58 character ( Chr).

Example: abc (base58) = a * 58^2 + b * 58^1 + c * 58^0 = 33 * 3364 + 34 * 58 + 35 = 113019 (decimal)
The other direction is slightly more difficult but it's the same as converting a number to binary, except with a base of 58.
Example for 30867:

Therefore, 30867 (dec) = 9|10|11 = ABC (base58).

Structure

The human readable addresses (FA & EC) and the human readable keys (Fs & Es) are all containers for a 32-byte payload. After converting from Base58 to binary, the first two bytes are the prefix, followed by a 32 byte payload, followed by a 4 byte checksum.

The prefixes are hardcoded:

Note 1: The human readable strings will have the characters 1, 2, and 3 following the FA/Fs/EC/Es characters. This is due to the fact that base64 does not evenly divide into base58, so bits from the prefix will “bleed over”.

Note 2: Keep in mind that the amount of prefix bytes is not fixed and may be more than two in the future.

For private keys, the payload is a random number between 0 and 2^256 - 1. For FCT and EC addresses, it's the hash of the RCD mechanism of the public key corresponding to the private key. (See below)

The checksum is 4 bytes from the checksum of prefix and payload, used for simple verification to check for typos or transmission errors.

RCD Mechanism

The RCD mechanism is a combination of “RCD Type” and “Public key”. The length and content of the public key is determined by the RCD type. At the time of writing, there is only one RCD type: 1, which is Ed25519 with Schnorr signatures. Unless otherwise mentioned, the rest of the blog will be about RCD Type 1.

The formula is RCDType|PublicKey, or in our case 0x1|<ed25519 public key>, coming to 33 bytes.

The hash of the RCD type is done by hashing it twice with Sha256. This will make the length of an address always 32 byte, regardless of which RCD type is used.

Note 1: For RCD types 1–127 it’s just one byte. For RCD types greater than that, you will need to use Factom’s varInt_f.

Transactions

On the front end, transaction are made from addresses you know the private key of to public addresses but as I explained earlier, it’s impossible to get the corresponding public key from the address. That’s why Factom transactions contain a list of public keys. The detailed binary specification of a Transaction can be summarized as:

1. Header Information
2. List of input addresses with the amount of Factoshis to deduct
3. List of output addresses with the amount of Factoshis to add
4. List of entry credit address with the amount of Factoshis to convert
5. List of unhashed RCDs of the addresses in 2. with a cryptographic signature

The transaction id (TXID) is the SHA256 hash of 1–4.

Note: The difference between the sum of factoshis in the inputs and the sum of factoshis in the outputs/ec is called the Fee, which must be paid for every transaction. See below for more.

Note: There is a maximum limit of 10 KiBi per transaction, which covers 1–5

Creating a Transaction

Assuming you have the data for 1–4 already gathered (this can be done using only public information and usually stems from user input), you now have to sign it so that it’s verifiable. For every input address, generate the public key from the private key. Using the private key, cryptographically sign the binary data of steps 1–4 according to the RCD Type. In the same order as the addresses in step 2, list the RCD Type, public key, and the signature.

This is where the different RCD Types come in, as that specifies how long the public key and signatures are. For RCD Type 1 that’s 32 and 64 bytes respectively. This allows forward compatibility for a range of different digital signature schemes.

Verifying a Transaction

For every address in 2. there is a corresponding signature in 5., and you need to verify every signature according to the following:

1. Check the RCD Type to determine the bytes of the public key and the bytes of the signature
2. Convert the public key to an address and verify that it matches the address from the corresponding input
3. Verify that the signature was signed with the given public key and matches the data

Additionally, you have to check that the Fee was high enough.

Fee

The Fee is the difference between the sum of Factoshis in the inputs and the sum of Factoshis in the outputs/ecs. There are three components to the Fee:

1. 10 EC for every output/ec address
2. 1 EC for every signature
3. 1 EC per KiBi of total transaction bytes

1 and 2 are straightforward but 3 has to be calculated before you sign, which is a point where you do not have the complete transaction. You’ll have to pre-determine how many bytes you need for the signature block. It’s also made slightly more complicated due to the Factoshi amounts being encoded with the variable integer type to preserve space.

The formula for 3 is as follows: ROUND_UP( (<byte size of header, inputs, outputs, ecs> + <# of signatures> * 97) / 1024) where 97 is 1 + 32 + 64 for RCD Type 1, public key, and signature.

Signing

It is possible to sign arbitrary data using your private key by following the schema detailed in the transaction above. You will need to transmit the public key along with the signature so that third parties can verify the signature.

There are functions for signing and verifying data available in Factom Inc.’s ed25519 repository (“Sign” and “VerifyCanonical”) as well as inside factomd’s primitives (“Sign” and “VerifySignature”).

Algorithms

Raw Keys

Factom Inc. has a fork of the agl/ed25519 repository to generate keys. Private keys are generated by reading 32 random bytes. Public keys are generated out of those using the ed25519 algorithm, specifically the function GetPublicKey() in the repository above.

Note: The private key keeps being referred to as being 64 bytes but only 32 bytes of those are random. The full private key consists of the private key in the upper 32 bytes of the array and the public key in the lower 32 bytes of the array. You can derive the public key from the private key so you only need to store half the private key. When using the GenerateKey() function, the public key array will be equal to the second half of the private key array.

Checksum

The checksum is calculated over both the prefix and the payload by taking the SHA-256 hash of <prefix bytes>|<payload> twice and taking the first 4 bytes of the resulting hash.

In pseudo-code, this would look like:

func CHECKSUM(data): hash = SHA256(SHA256(data)) // 32 byte hash return FIRST_FOUR_BYTES(hash) // indices 0,1,2,3

RCD Mechanism

In pseudo-code, this would look like:

func RCD(type, pubkey): rcd = CONCAT(type, pubkey) hash = SHA256(SHA256(rcd)) return hash

Human Readable Strings

func HUMANREADABLE(prefix, payload): data = CONCAT(prefix, payload) checksum = CHECKSUM(data) return BASE58(CONCAT(data, checksum))

FCT Address

public, private = GENERATE_ED25519_KEYS() key = HUMANREADABLE(0x6478, private) address = HUMANREADABLE(0x5fb1, RCD(public))

Example

Let’s assume our private key is the number 0xFA (decimal 250). This would get us the following values:

payload 00000000000000000000000000000000000000000000000000000000000000FA (hex) private key 647800000000000000000000000000000000000000000000000000000000000000FA3FA6D616 (hex) private key Fs1KWJrpLdfucvmYwN2nWrwepLn8ercpMbzXshd1g8zyhokVFkjw (base58) public key 466295a7552441af82398493fdbdb99b166b6ed12134e6518db1439d190ed8c8 (hex) fct address FA3FV48hJzrwB1KumaC5fBeEYuVCJCauEgEeaG694Cs1ydhTok3h (base58)

Address Space

Disclaimer: I’m not an expert in cryptography, so this will more of a layperson’s introspective.

With a 32 byte / 256 bit private key, there are a total of 2^256 - 1 or 1.1579209 * 10^77 addresses available. In english, that's over 115,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 (I really wanted to write this out). For reference, the lottery has around 292,000,000 combinations.

At the time of writing, the Bitcoin network’s hash rate is a little under 60 EH/s or 6*10^19 hashes per second. Assuming it only takes one hash to check a private key against a public address, it would take around 1.9 * 10^57 seconds or 6 * 10^49 years to cover all possibilities.

To put it simply: there’s no realistic way to brute force a private key and there no concerns about ever “running out” of addresses.

Vanity Addresses

Originally, my motivation to look into this was to see what it would take to generate vanity addresses. Turns out it’s very easy but time consuming, since “generating” involves mining hundreds of thousands of hashes looking for one you want. I have created an open-source app that does exactly this: The Factom Vanity Address Generator.

I want to specifically draw attention to the file address.go which contains Golang implementations of the pseudo-code from above.

Originally published at https://factomize.com on May 13, 2019.