Base58check in rust

Source Code - https://github.com/448-OG/Btrust-Deliverables/blob/master/base58check/src/main.rs

Base58Check is a binary-to-text encoding algorithm that allows us to convert byte arrays into human-readable strings that are resistant to errors. These byte arrays can be public keys, digests of hash functions and even private keys.

The algorithm used to convert bytes to Base58Check is the Base58 algorithm. We will first look at the Base58 algorithm and later combine it to create the Base58Check algorithm.

Base58Check is primarily used for encoding Bitcoin addresses, but it can be more broadly applied to any data that needs to be represented in a compact, user-friendly format that excludes characters like 0, O, I, and l that can look similar in certain fonts. This prevents confusion and ensures readability.

As illustrated above, the Base58 avoids characters that can create confusion reducing the alphabet of allowed characters to 58 which are 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

To convert a decimal value to Base58 we use the modulus function until no remainders are left. Using modulus function makes sure we circle around when we reach the maximum number of characters which is 58. Each remainder corresponds to the character at the index in the Base58 alphabet, for example remainder 10 equals to the character A

Example the decimal number 1024

base10 = 1024

1025 % 58 = 38 <- Ignoring the fractional part
17 % 58 = 17

The numbers are 17 and 38 respectively
So we look for the characters at index 17 and 38 in the Base58 alphabet

123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz
                 |                    |
             index 17 is `J`      index 38 is `f`

Therefore:
Base58 = `Jf`

To convert back to decimal from Base58 string you take each character and lookup it’s index in the Bas58 alphabet and multiply it by how many 58s that position represents and then you add all the values together.

Base58 = `Jf`

J = index 17 in the Base58 alphabet
f = index 38 in the Base58 alphabet

To get the index at character we start with the last one as index 0 moving backwards
J = index 1 in the Base58 string
f = index 0 in the Base58 string

f = 38 * 58^0 = 38
J = 17 * 58^1 = 986
Decimal = 38 + 989 = 1024

In our code, we will use bytes instead of decimals in order to allow conversions from any value that can be converted to and from bytes like public and private keys.

Let’s create a new cargo project.

$ cargo new base58

Switch to the project directory.

cd base58

We need to add some dependencies in the Cargo.toml file

[dependencies]
sha = "0.10.8"
rand_chacha = "0.3.1"
rand_core = { version = "0.6.4", features = ["getrandom"]}
bitcoin =  { version = "0.31.1", features = ["std", "rand-std"] }

Let’s import the data types into our main.rs file

use bitcoin::base58;
use rand_chacha::ChaCha20Rng;
use rand_core::{RngCore, SeedableRng};
use sha2::{Digest, Sha256};
use std::collections::VecDeque;

fn main() {}

We import the base58 type from the bitcoin crate to compare the output of our custom base58 to the output of the mostly use Rust bitcoin crate. This is done to check for correctness in converting to base58 from bytes and vice versa.

rand_chacha and rand_core crates are used to generate random bytes while sha2 will be used to create our checksum for Base58Check algorithm.

Next we create our code for random byte generation. We use a const generic N so that we can pass the number of bytes we want to generate.

/// Our random byte generator
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Entropy<const N: usize>([u8; N]);

impl<const N: usize> Entropy<N> {
    /// Generate our random bytes
    pub fn generate() -> Self {
        // Create a chacha based 
        // cryptographically secure psuedo-random
        // number generator.
        let mut rng = ChaCha20Rng::from_entropy();
        // Initialize an empty byte array of `N`
        // number of bytes
        let mut buffer = [0u8; N];
        // Fill our buffer with randomly generated bytes
        rng.fill_bytes(&mut buffer);

        Self(buffer)
    }
}

Next we write code to parse bytes to Base58 encoding.

/// Add our base58 alphabet
const ALPHABET: &str = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

/// Converts our bytes to base58. 
/// It takes a byte slice
fn to_base58(base58_bytes: &[u8]) -> String {
    // We use a `VecDeque` so that we don't have to
    // call `.reverse()` function on our `Vec`
    // since this can be an expensive operation.
    let mut base58_char = VecDeque::<char>::new();

    // We create a new String to hold our final base58 string
    let mut outcome = String::new();

    // We iterate checking for `0` bytes that appear at the
    // beginning of our array since they are supposed
    // to be prefixed by `1`. We then push a `1` for 
    // every 0 byte we find.
    for _ in base58_bytes.iter().take_while(|&&x| x == 0) {
        outcome.push('1');
    }

    // This will be the result of every modulo operation
    // holding the quotient of our division
    let mut decimal = 0usize;

    // We multiply by 256 since bytes are in
    // base 2 and our division to base58 is in
    // base 10. This is done by using left shift
    // to multiply since 2^8 is equal to 256.
    // we then assign the result to `decimal` variable
    for value in base58_bytes {
        decimal = (decimal << 8) | *value as usize;
    }

    // We know split the alphabet and collect the individual
    // characters so that we can get the index
    let index_alphabet = ALPHABET.chars().collect::<Vec<char>>();

    // We iterate over decimal variable
    // dividing by `58` and getting the remainder.
    // We then lookup the character at the index
    // of that remainder and then we push that character
    // to our vecdeque pushing it to the front.
    // We halt the loop when `decimal` variable equals 0
    while decimal != 0 {
        // This is equivalent to diving and getting the
        // remainder while allowing compilers to
        // optimize for speed.
        let (quotient, remainder) = (decimal / 58, decimal % 58);

        base58_char.push_front(index_alphabet[remainder as usize]);
        decimal = quotient;
    }

    // We know iterate over our characters and add them
    // to the `outcome` variable which might
    // contain leading zeros represented by `1`s
    outcome += base58_char.iter().collect::<String>().as_str();

    outcome
}

Next we create our base58 decoder.

/// This decodes a base58 string into bytes
fn from_base58(base58_str: &str) -> Vec<u8> {
    // Initialize a variable to hold the decimal equivalent of the base58 string
    let mut decimal = 0usize;

    // Create a vector of characters from the base58 alphabet
    let index_alphabet: Vec<_> = ALPHABET.chars().collect();

    // Initialize a variable to count the number of leading zeros in the base58 string
    let mut leading_zeros_total = 0usize;

    // Initialize a vector to hold the outcome of the decoding
    let mut outcome = Vec::<u8>::new();

    // Convert the base58 string into a vector of characters
    let mut split_chars = base58_str.chars().collect::<Vec<char>>();

    // Count the number of leading zeros in the base58 string and add a corresponding number of zeros to the outcome
    for _ in split_chars.iter().take_while(|&x| x == &'1') {
        leading_zeros_total += 1;
        outcome.push(0);
    }

    // Remove the leading zeros from the base58 string
    split_chars.drain(0..leading_zeros_total);

    // Convert each character in the base58 string to its decimal equivalent and add it to the decimal variable
    for current_char in split_chars {
        let value = index_alphabet
            .iter()
            .position(|&in_alphabet| in_alphabet == current_char)
            .unwrap();
        decimal = (decimal * 58) + value;
    }

    // Initialize a vector to hold the bytes of the decimal
    let mut bytes = Vec::<u8>::new();

    // This loop continues as long as the decimal value is greater than 0
    while decimal > 0 {
        // The division operation (decimal / 256) gives the quotient
        // The modulus operation (decimal % 256) gives the remainder
        // These two values are stored in the variables 'quotient' and 'remainder' respectively
        let (quotient, remainder) = (decimal / 256, decimal % 256);

        // The remainder (which is the result of the modulus operation) is converted to an 8-bit unsigned integer (u8)
        // and then pushed onto the 'bytes' vector. This is because each byte represents a value between 0 and 255 (inclusive),
        // which is the range of possible remainders from the modulus operation.
        bytes.push(remainder as u8);

        // The 'decimal' variable is updated to the 'quotient' from the division operation.
        // This effectively reduces the 'decimal' value by a factor of 256 in each iteration of the loop,
        // preparing it for the next iteration where the process repeats.
        decimal = quotient;
    }

    // Reverse the bytes to get them in the correct order
    bytes.reverse();

    // Add the bytes to the outcome
    outcome.extend_from_slice(&bytes);

    // Return the outcome
    outcome
}

Bitcoin uses Base58Check which is an enhanced version of Base58 algorithm. Base58Check has some advantages like a version number and error detection due to the addition of four bytes checksum from the double hashing of a prefix byte and the payload using the SHA256 hash function.

Let add code to create our Base58Check algorithm.

#[derive(Debug, Default)]
pub struct Base58Check {
    // Will hold our prefix
    prefix: Vec<u8>,
    // Our bytes
    payload: Vec<u8>,
    // 4 byte result of double hashing
    checksum: Vec<u8>,
}

Next we implement our initialization function.

impl Base58Check {
  // Initialize Self with defaults since we derive default on our struct
   fn new() -> Self {
      Self::default()
  }
}

We need a way to add our prefix and payload

impl Base58Check {
    /// We call this method to add our prefix
    /// taking a byte slice as argument to allow any prefix
    fn add_prefix(mut self, prefix: &[u8]) -> Self {
        self.prefix.extend_from_slice(prefix);

        self
    }

    /// Method to add byte payload Self
    fn add_payload(mut self, payload: &[u8]) -> Self {
        self.payload.extend_from_slice(payload);

        self
    }
}

To generate our checksum, we first pass our prefix and payload to a SHA256 hashing function and then using our SHA256 hashing function we hash the result of the digest of the hash function (double hashing).

impl Base58Check {
  // This takes a mutable self and assigns the result
  // of the payload to `checksum` field in `Self`
  fn calc_checksum(mut self) -> Self {
        // Initialize our sha256 hashing function
        let mut hasher = Sha256::new();
        // Hash the prefix
        hasher.update(&self.prefix);
        // Hash our payload
        hasher.update(&self.payload);

        // Get the result of the digest
        let first_hash = hasher.finalize();

        let mut hasher = Sha256::new();
        // Hash the hash
        hasher.update(first_hash.as_slice());
        let double_hash = hasher.finalize();

        // Take the first four bytes and add them as the checksum
        self.checksum.extend_from_slice(&double_hash[0..4]);

        self
    }
}

Our last method for our struct with generate a vector of bytes that we can pass to our base58 encoder.

impl Base58Check {
  // This method just combines all fields of `Self`
  // into one vector by draining the other vectors
  fn build(mut self) -> Vec<u8> {
        let mut outcome = Vec::<u8>::new();
        outcome.extend(self.prefix.drain(..));
        outcome.extend(self.payload.drain(..));
        outcome.extend(self.checksum.drain(..));

        outcome
    }
}

Now let’s test our code in the main function.

fn main() {
    // Generate some random bytes
    let private_key = Entropy::<4>::generate().0;
    // Intialize our Base58Check struct
    let mut bytes = Base58Check::new()
        // Add our prefix
        .add_prefix(&[0u8, 0, 0, 0])
        // Add the payload
        .add_payload(&private_key)
        // Calculate the checksum
        .calc_checksum()
        // Combine all our bytes (prefix + payload + checksum)
        .build();
    let custom_conversion = to_base58(&mut bytes);

    // Assert that the base58 string generated
    // equals to the the base58 string 
    // generated by the bitcoin crate
    assert_eq!(base58::encode(&bytes).to_string(), custom_conversion);

    let to_custom_vec = from_base58(&custom_conversion);
    assert_eq!(
        to_custom_vec,
        base58::decode(&base58::encode(&bytes)).unwrap()
    );
}

That’s it! We have implemented a Base58Check encoder and decoder

References

https://learnmeabitcoin.com/technical/base58

Implementing a Base58Check Encoder in Rust

References

Subscribe to my newsletter

448-OG

448-OG