ビットコインの技術 Base58

2016年04月23日(編集2016年04月23日)
このエントリーをはてなブックマークに追加

この記事は、ビットコインで利用されているバイナリ変換形式のBase58の説明をします。
コードを通して、Base58の仕様と実装方法を理解します。

javaはoracle jdk 1.8.0_77を利用します。

環境

  • Windows8.1
  • oracle jdk version 1.8.0_77
  • Eclipse version Luna Service Release 2 (4.4.2)

Base58利用例

  • Flickrの短縮URL
  • リップル
  • ビットコイン

内容

中級者向け

Base58

Base58は、バイナリデータを58種類の文字で表現するフォーマットです。
Base64との違いは、l(小文字:エル)と1(数字:いち)のような間違えやすい文字を除外していることです。

使用可能な文字は

123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

です。

文字列の並び順

Base58で利用する58種類の文字は、アプリケーションによって並び順を変えて利用されています。
Base58を利用している有名なアプリには、ビットコインの他にフリッカーの短縮URLがあります。

この二つのアプリでは、58種類の文字を以下の並び順で利用しています。

Application Alphabet
短縮URL 123456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ
ビットコイン 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

エンコード実装

ここからは、実際にビットコインで使用しているBase58のエンコードを実装します。
JavaでBase58クラスとencodeメソッドを作成します。

{project_folder}/src/main/java/{package}/Base58.java
public class Base58 {
  
  public static final char[] ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz".toCharArray();
  private static final char ENCODED_ZERO = ALPHABET[0];
  
  public Base58() {
    
  }
  
  /**
   * 文字列をBase58エンコードして返す
   * @param str word(文字列)
   * @return encoded word(エンコードした文字列)
   */
  public String encode(String str) {
    
    // 文字列をバイナリにする
    byte [] b = str.getBytes();
    
    // 文字列を16進数にする
    String s_hex = DatatypeConverter.printHexBinary(b);
    
    // 16進数 → 10進数
    long decimal = Long.valueOf(s_hex, 16);
    
    // 10進数を58種類の文字列にする
    StringBuffer res = new StringBuffer();
    while (decimal > 0) {
      char c = ALPHABET[(int)decimal%58];
      res.append(c);
      decimal = decimal/58;
    }
    
    // 0byteのデータがないことを確認
    byte [] temp_b = str.getBytes();
    for (int i = 0; i < temp_b.length; i++) {
      if (temp_b[i] != 0) {
        break;
      }
      res.append(ENCODED_ZERO);
    }
    
    return res.reverse().toString();
  }

}
        

Base58のエンコード処理手順は以下の通りです。

  • 文字列(バイナリ)を16進数に変換する
  • 16進数を10進数に変換する
  • 10進数を58種類の文字列に変換する
  • 文字列を逆順にする

これだけです。非常にシンプルです。では、上記のコードを使って詳しく説明していきます。

  • 文字列(バイナリ)を16進数に変換する
// 文字列をバイナリにする
byte [] b = str.getBytes();

// 文字列を16進数にする
String s_hex = DatatypeConverter.printHexBinary(b);
        

DatatypeConverterクラスはjava1.6から導入されたライブラリです。
printHexBinaryメソッドはbyte配列を16進数の文字列にして返します。
Hexは英語で16進数のことです。

  • 16進数を10進数に変換する
// 16進数 → 10進数
long decimal = Long.valueOf(s_hex, 16);
        

Integer.valueOf(s_hex, 16)を使っても10進数に変換できます。
Long.MAX_VALUE: 9223372036854775807 -< 約922京(けい)で、Integerより大きなデータが扱えるので、Longを使用しています。

  • 10進数を58種類の文字列に変換する
// 10進数を58種類の文字列にする
StringBuffer res = new StringBuffer();
while (decimal > 0) {
  char c = ALPHABET[(int)decimal%58];
  res.append(c);
  decimal = decimal/58;
}
        

58進数の計算をしています。除算の余りから文字を決定し、新たな文字列を作成しています。
最後に文字列を逆順(リバース)にして、58進数にします。

デコード実装

エンコードしたBase58を元の文字列に戻します。
Base58クラスにdecodeメソッドを作成します。

{project_folder}/src/main/java/{package}/Base58.java
  /**
   * エンコードされた文字列をBase58デコードして返す
   * @param encoded word(エンコードした文字列)
   * @return original word(元の文字列)
   */
  public String decode(String str) {
    
    int decimal = 0;
    
    // 10進数に戻す
    char []chars = str.toCharArray();
    for (int i = 0; i < chars.length; i++) {
      char temp_c = chars[i];
      
      int index_num = 0;
      for (int j = 0; j < ALPHABET.length; j++) {
        if (ALPHABET[j] == temp_c) {
          index_num = j;
        }
      }
      
      decimal = decimal*58;
      decimal = decimal + index_num;
    }
    
    // 10進数 → 16進数
    String s_hex = Integer.toHexString((int)decimal);
    
    // 16進数をバイナリに戻す
    byte[] bytes = DatatypeConverter.parseHexBinary(s_hex);
    return new String(bytes);
  }
        

Base58のデコード処理手順は以下の通りです。

  • エンコード文字列を10進数に戻す
  • 10進数を16進数に変換する
  • 16進数をバイナリ(文字列)に戻す

上記のコードで説明します。

  • エンコード文字列を10進数に戻す
int decimal = 0;

// 10進数に戻す
char []chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
  char temp_c = chars[i];
  
  int index_num = 0;
  for (int j = 0; j < ALPHABET.length; j++) {
    if (ALPHABET[j] == temp_c) {
      index_num = j;
    }
  }
  
  decimal = decimal*58;
  decimal = decimal + index_num;
}
        

エンコードされた58進数を10進数に戻します。
58種類の文字列のインデックス位置を取得して、元の10進数に戻す計算をおこなっています。

  • 16進数をバイナリ(文字列)に戻す
// 16進数をバイナリに戻す
byte[] bytes = DatatypeConverter.parseHexBinary(s_hex);
return new String(bytes);
        

2. DatatypeConverterのparseHexBinaryメソッドで16進数文字列をバイト配列にすることができます。
このメソッドも、java1.6から導入されています。

実行

上記で実装したコードをMainクラスで実装します。

{project_folder}/src/main/java/{package}/App.java
public class App {

  public static void main(String [] args) {
    Base58 base = new Base58();
    System.out.println(base.encode("abc"));
    System.out.println(base.decode("ZiCa"));
  }
}
        

Eclipseで実行します。

terminal
ZiCa
abc
        

abcがZiCaにエンコードされ、ZiCaがabcにデコードされました。

まとめ

Base58は、ビットコインや短縮URLだけでなく、今後も色々なアプリで使用されていくと思います。

セキュリティの点からもBaseXXのアルゴリズムの考え方は重要になってくると思うので、ぜひ原理を理解してください。

ブラックボックス状態の知識は解消しておきましょう。

関連記事

タグ検索で調べてみよう

ビットコイン