dwyl/base58

How to encode a string to base58?

SimonLab opened this issue · 9 comments

SimonLab commented

Given a string what are the steps to get the base58 encoded value?

  1. Convert the string to hexadecimal with Base.encode16
Base.encode16("foo")
666F6F

"foo" in utf8 is represented with the codepoint <<102, 111, 111>>. You can see this representation with "foo" <> <<0>>` which concatane <<0>> to the string. Then 102 in hex is 66 and 6F is 111

  1. Calculate the integer for 66 6F 6F
    6 * 16^5 + 6 * 16^4 + 6 * 16^3 + 15 * 16^2 + 6 * 16^1 + 15 * 16^0 = 6713199
    (where the hexadecimal F is 15 in decimal)

  2. Encode the decimal value to base58 codepoint
    take the rest of the division by 58 and repeat on the rest of the division until we can't divide by 58
    6713199 % 58 = 47 and rest 115744 (% here is the modulo operator)
    115744 % 58 = 34
    1995 % 58 = 23
    34 % 58 = 34

We have the list 34 23 34 47

  1. Find the matching letter from the Base58 alphabet matching the numbers
    34 is b
    23 is Q
    47 is p

For that you just need to find the letter at the indice
123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz
012345... ...57

So "foo" in base58 is "bQbp"

  • I haven't find a function to convert directly a string (binary) to the integer represetation ie "foo" to 6713199. So the first steps is to create this function.

  • Then we can create the function which calculate the modulo of these number with 58 and find the characters at the indices calculated

SimonLab commented

We can use the following Integer.parse function to get the integer represetation of an hex:

iex> Integer.parse(Base.encode16("foo"), 16)
{6713199, ""}
SimonLab commented

Creating the recursive function to convert an integer to a list of base58 point was at the end simple enough (we might found a better way to do this later on see #2)

 defp get_codes(int, codes) do
   rest = div(int, 58)
   code = rem(int, 58)
   if  rest == 0 do
     [code | codes]
   else
     get_codes(rest, [code | codes])
  end
 end

Adding now a Readme and some tests

SimonLab commented

I'm going to update the Readme to

  • Add explanation on what are bases and how to calculate the representation of an integer from base 10 to any other base see
  • Add section "use cases" for this package. Why and where base58 is used?
  • Add Travis and coverage badges

On the code:

  • 👍1
nelsonic commented

@SimonLab this list of additions to the README.md looks good.
The more detail we have the more beginner-friendly it will be to new users.
(not that I'm expecting a deluge of beginners to be reading and independently using the Base58Encode module separately from our CID implementation ... but it's conceivable that someone doing work for a "blockchain" will search for an Elixir B58 implementation and we would like them to use ours ... so that they help us improve it!)

Please liaise with @Danwhy on property-based-testing if you need.
Typespecs are good but they can also be "confusing" to beginners ... if we aren't using them e.g: to provide auto-completion and hints in an IDE then we may not need them.

  • 👍1
SimonLab commented

To be able to use property-based-testing we need to find another library which can produce a base58 string. Once we have something to compare to we should be able to run as much test as we want.
The important step is to make sure that the other library produce a correct base58.

We could maybe use a node package, or the other elixir package? Or a bash command line tool?
I think I would try to use the other elixir package https://hex.pm/packages/basefiftyeight as it is easy to integrate with our current Elixir tests however @Danwhy let me know if you have any other thougth on this.

nelsonic commented

@SimonLab if you need a "reference" library for Base58 see: https://github.com/bitcoin/bitcoin/blob/master/src/base58.h
Just compile that and use it on Travis-CI 😉

That way we can claim to have 100% Compatibility with the Bitcoin Base58.
(which isn't immediately important to us, but might be relevant to other people using our package...)

Edit: I know this is a C module.
Invoking a C executable from Elixir is reasonably straightforward but is an "advanced" topic.
If you feel that it will be more time-effective to reference another JS/Go/Elixir implementation of B58, .then do it and create a "task" in the backlog of this project to migrate to using the C version later.

  • 👍1
SimonLab commented

I've added a property test using basefiftyeight library to compare our result.
See #4 for the next step on how to compile and run a C program with Elixir

  • 👍1
nelsonic commented

@SimonLab this is a good short-term solution. thanks for opening the C issue. 👍

SimonLab commented

initial version merged, #3 and the documentation has been updated
I'll create another issue if we want to add Typespec

  • 👍1