HN 日本語サマリー

← 一覧へ戻る
プログラミング

破損したビットコインアドレスの復旧 (2024)

Recovering garbled Bitcoin addresses (2024) (purplesyringa.moe)

5 pointsby zX41ZdbW0 コメント

要約

ZeroNetではサイトのアドレスやコンテンツの署名にビットコインアドレスが使用されていましたが、大文字・小文字の区別やタイプミスによりアドレスが破損し、サイトへのアクセスが失われる問題が発生しました。この記事では、ビットコインアドレスの構造とbase58エンコーディング、チェックサムの仕組みを解説し、破損したアドレスから元の有効なアドレスを復旧するためのPythonとRustを用いた試みを紹介しています。最終的には、自動化された高速な復旧アルゴリズムの開発を目指しています。

全文翻訳

破損したビットコインアドレスの復旧

2024年4月23日 Telegram

この記事では多くのコードスニペットを紹介しています。これらはリポジトリからダウンロードできます。完成したプロジェクトはこちらで公開されています。


昔々、ZeroNetという分散型ネットワークがありました。後に出てきたIPFSのようなコンテンツアドレス指定型のストレージネットワークとは異なり、ZeroNetはブログやフォーラムのように、所有者がリアルタイムで更新できる動的なサイトを可能にしていました。その結果、サイトは不変のハッシュでアドレス指定できなくなりました。しかし、リード開発者は新しい暗号技術を導入したくなかったので、おそらく最も賢明な決断を下しました。サイトはビットコインアドレスでアドレス指定され、そのコンテンツと更新は当該アドレスで署名されていました。

ビットコインを使ったことがない方のために、そのアドレスは以下のようになります: 1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71。これに対し、ウェブ上の典型的なドメイン名は purplesyringa.moe のようになります。主な違いは、ビットコインアドレスはケースセンシティブ(大文字・小文字を区別する)であり、人々はアドレスをケースインセンシティブ(大文字・小文字を区別しない)であることに慣れているという点です。これにより、http://1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71.zero の代わりに http://zero/1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71 を使用するようなハックが発生しましたが、それでも間違いは起こり、時には得られる唯一の手がかりが 1lbcfr7sahtd9cgdqo3htmtkv8lk4znx71 のような小文字化されたアドレスだけになることもあります。そして、このようにして貴重な情報が失われるのです。

当時、私はZeroNetのアーカイブ作業をしていたため、人的ミスによる情報損失は、修正する価値のある迷惑な問題でした。小文字化されたアドレスしか知らない場合、本当にそのサイトへのアクセスを失ってしまったのでしょうか? 元のアドレスを何とかして復旧することはできるのでしょうか?

アドレスとは何か?

よくある誤解は、ビットコインアドレスが公開鍵のエンコーディングであるというものです。これは間違いです。実際には、アドレスは公開鍵のハッシュのエンコーディングを含んでいます。これはUX上の決定です。ハッシュは公開鍵よりも短いため使いやすいですが、セキュリティに影響を与えない程度には十分な長さがあります。

サトシは他のUX上の考慮事項も行っていたことが判明しました。ビットコインアドレスは、公開鍵のハッシュだけでなく、チェックサムもエンコードしています。通貨を送金する際にターゲットアドレスをタイプミスした場合、ビットコインクライアントはそれに気づき、トランザクションをキャンセルします。この保護機能はIBANが使用するものよりもはるかに信頼性が高いです。チェックサムは SHA256(SHA256(key_hash)) の最初の4バイトです。

エンコーディングの最後の重要な部分は、お気に入りのbase64ではなくbase58であるということです。base58の違いは、0, O, I, l といった文字は混同しやすいためエンコーディングから除外され、+ と / はURIセーフではなく(潜在的に紛らわしい)、= はパディングが不要なため除外されている点です。

ここに興味深い図解があります:

秘密鍵(ランダムな32バイト)はECDSAマジックを経て公開鍵(33バイト)にマッピングされます。公開鍵は次にSHA-256とRIPEMD-160でハッシュ化され、20バイトの文字列になります。1バイトのアドレスタイプ(0x00)をハッシュの前に付けると、21バイトのペイロードが生成されます。このペイロードはSHA-256で2回ハッシュ化され、最初の4バイトがチェックサムとして使用されます。ペイロードとチェックサムが連結され、25バイトのデコードされたアドレスが生成されます。このアドレスはbase58でエンコードされ、平均約34文字の人間が読める文字列になります。

秘密鍵(ランダムな32バイト)はECDSAマジックを経て公開鍵(33バイト)にマッピングされます。公開鍵は次にSHA-256とRIPEMD-160でハッシュ化され、20バイトの文字列になります。1バイトのアドレスタイプ(0x00)をハッシュの前に付けると、21バイトのペイロードが生成されます。このペイロードはSHA-256で2回ハッシュ化され、最初の4バイトがチェックサムとして使用されます。ペイロードとチェックサムが連結され、25バイトのデコードされたアドレスが生成されます。このアドレスはbase58でエンコードされ、平均約34文字の人間が読める文字列になります。

初めての試み

大文字・小文字のすべての組み合わせを総当たりで試して、有効なものがあるか確認することはできるでしょうか? 実際に試してみましょう。

import base58
import itertools


address_lowercase = "1lbcfr7sahtd9cgdqo3htmtkv8lk4znx71"


def try_both_cases(c):
    yield c
    if c.upper() != c:
        yield c.upper()

for address in itertools.product(*map(try_both_cases, address_lowercase)):
    address = "".join(address)
    try:
        base58.b58decode_check(address)
    except ValueError:
        pass
    else:
        print("Found valid address:", address)
$ time python3 attempt1.py
^CTraceback (most recent call last):
  File "/home/purplesyringa/btccaserestore/attempt1.py", line 16, in <module>
    base58.b58decode_check(address)
  File "/home/purplesyringa/.local/lib/python3.11/site-packages/base58/__init__.py", line 152, in b58decode_check
    result = b58decode(v, alphabet=alphabet, autofix=autofix)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/purplesyringa/.local/lib/python3.11/site-packages/base58/__init__.py", line 128, in b58decode
    acc, mod = divmod(acc, 256)
               ^^^^^^^^^^^^^^^^
KeyboardInterrupt


real    1m47,770s
user    1m47,301s
sys     0m0,027s
2回目の試み

Pythonを使ったのは間違いでした。宇宙の熱的死を迎える前に終了しないでしょう。Rustで書き直しましょう。

use base58::FromBase58;
use itertools::Itertools;
use sha2::{digest::Update, Digest, Sha256};

fn main() {
    let address_lowercase = "1lbcfr7sahtd9cgdqo3htmtkv8lk4znx71";

    let addresses = address_lowercase
        .bytes()
        .map(|byte| {
            if byte.to_ascii_uppercase() != byte {
                vec![byte, byte.to_ascii_uppercase()]
            } else {
                vec![byte]
            }
        })
        .multi_cartesian_product();

    for address in addresses {
        let address = String::from_utf8(address).unwrap();
        let Ok(decoded_address) = address.from_base58() else {
            continue;
        };
        if decoded_address.len() != 25 {
            continue;
        }
        let round1 = Sha256::new().chain(&decoded_address[..21]).finalize();
        let round2 = Sha256::new().chain(round1).finalize();
        if decoded_address[21..] == round2[..4] {
            eprintln!("Found valid address: {address}");
        }
    }
}
$ time cargo run --bin attempt2 --release
    Finished `release` profile [optimized] target(s) in 0.01s
     Running `target/release/attempt2`
Found valid address: 1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71

real    0m34,296s
user    0m34,275s
sys     0m0,013s

やった!まさに開始したアドレスそのものです。

問題解決? まあ、そうですが、私の場合はアドレス復旧は自動化プロセスの一部でした。つまり、入力が完全にゴミであるかどうかすら定かではありません。

1hell0w0rldd9cgdqo3htmtkv8lk4znx71 は有効なビットコインアドレスに復元できるでしょうか? 多分! 実際にそのアドレスを使っている人はいるのでしょうか? 分かりません! 彼らはVanitygenで運が良かったのかもしれません。

1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa を復旧するためにCPU時間を費やすべきでしょうか? 多分そうではありませんが、偽陽性を避けながら自動的にチェックするにはどうすればよいでしょうか?

そして、これが最速の復旧アルゴリズムへの旅の始まりです。

3回目の試み

プロセスの最初のステップはbase58のデコードです。base58エンコーディングが実際に行っていることを調べて、ショートカットできる部分がないか見てみましょう。

  1. 任意のバイト文字列から始めます。例: 00 d6 f6 4e e7 83 6a cf 6e 5a 93 7d 63 54 c3 a5 96 cd 24 2d fc 2f 78 fa 7c(簡潔さのため16進数で表示)。
  2. バイト文字列をビッグエンディアンの長い数値として解釈します: 5270856372487448678887896392566731007782045065082238990972。
  3. 次に、数値を基数58でエンコードします: 19, 34, 35, 38, 49, 6, 50, 9, 16, 26, 12, 8, 11, 39, 36, 23, 46, 2, 16, 26, 20, 26, 43, 28, 7, 19, 18, 3, 32, 45, 30, 6, 0。
  4. この変換プロセスは、先頭のゼロバイトの数を保持しません(例: 00 ff と ff は、4, 23 という1つの基数58シーケンスにマッピングされます)。そのため、バイト文字列から先頭のすべてのゼロを基数58表現に追加します。バイト文字列にはゼロバイトが1つだけあったので、0, 19, 34, 35, 38, 49, 6, 50, 9, 16, 26, 12, 8, 11, 39, 36, 23, 46, 2, 16, 26, 20, 26, 43, 28, 7, 19, 18, 3, 32, 45, 30, 6, 0 と記述します。
  5. 最後に、数値0〜57を 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz のシーケンスの対応する文字に置き換えます。例えば、0は1に、57はzにマッピングされます: 1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71。

逆に、デコードプロセスは以下のようになります:

  1. アルファベット文字を0〜57の数値に置き換えます。
  2. 基数58の長い数値をデコードします(ビッグエンディアン)。
  3. 長い数値を基数256(ビッグエンディアン)にエンコードします。
  4. 基数58表現にあった先頭のゼロバイトの数を、基数256表現に追加します。

では、エンコードされた文字列の1文字を置き換えると、バイト文字列にどのような影響があるのでしょうか? 例えば、例のアドレスで A を a に置き換えてみましょう。最初のステップでは、…, 6, 50, **9**, 16, 26, … が …, 6, 50, **33**, 16, 26, … に変わります。これは、長い数値の桁に33 - 9 = 24 を加えるだけで、ステップ2の長い数値は 24⋅58^25 だけ増加します。基数256では、これは繰り上がりを伴う単なる加算です。ステップ4は少し複雑ですが、ビットコインアドレスはチェックサム付きで常に25バイト長であるという事実を悪用することで、その複雑さを回避できます。

そこで、アドレスを一度だけ解析し、バイト表現に定数(例では 24⋅58^25)を加算または減算することでケースを反転させることをシミュレートするのはどうでしょうか? 実際にやってみましょう。

use itertools::Itertools;
use num_bigint::BigUint;
use num_traits::{One, Zero};
use sha2::{digest::Update, Digest, Sha256};

const BASE58_ALPHABET: &'static [u8] =
    b"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

fn main() {
    let garbled_address = "1lbcfr7sahtd9cgdqo3htmtkv8lk4znx71";

    let mut parsed_number: BigUint = Zero::zero();
    let mut power_58_i: BigUint = One::one();
    let mut possible_differences = Vec::new();
    let mut base_address = vec![0u8; garbled_address.len()];

    for (digit_index, byte) in garbled_address.bytes().enumerate().rev() {
        // Lやoのような一部の文字は、片方のケースでのみ有効なbase58文字です。これは
        // コードを少し複雑にします。
        let digit1 = BASE58_ALPHABET
            .iter()
            .position(|&b| b == byte.to_ascii_uppercase());
        let digit2 = BASE58_ALPHABET
            .iter()
            .position(|&b| b == byte.to_ascii_lowercase());
        match (digit1, digit2) {
            (Some(digit1), Some(digit2)) if digit1 != digit2 => {
                // 2つの異なるバリアントが可能です
                parsed_number += digit1 * &power_58_i;
                base_address[digit_index] = byte.to_ascii_uppercase();
                // digit1は大文字、digit2は小文字。アルファベットでは小文字が大文字の後にあるため、差は正です
                possible_differences.push((digit_index, (digit2 - digit1) * &power_58_i));
            }
            (Some(digit), _) => {
                // 最初のバリアントのみが正しい
                parsed_number += digit * &power_58_i;
                base_address[digit_index] = byte.to_ascii_uppercase();
            }
            (_, Some(digit)) => {
                // 2番目のバリアントのみが正しい
                parsed_number += digit * &power_58_i;
                base_address[digit_index] = byte.to_ascii_lowercase();
            }
            (None, None) => panic!("The address is invalid"),
        }
        power_58_i *= 58u32;
    }

    let subsets_of_possible_differences = possible_differences
        .iter()
        .map(|_| [false, true])
        .multi_cartesian_product();

    for subset in subsets_of_possible_differences {
        // この文字セットがすべて大文字に切り替わった場合の修正を加えた元の数値を計算します
        let mut fixed_number = parsed_number.clone();
        for (&should_take, (_, addend)) in subset.iter().zip(&possible_differences) {
            if should_take {
                fixed_number += addend;
            }
        }

        // 数値をバイト文字列に変換します
        let byte_string = fixed_number.to_bytes_be();

        // 先頭をゼロで埋めて正確に25バイトにします
        if byte_string.len() > 25 {
            // 運が悪かった、これは明らかに有効なビットコインアドレスではありません
            continue;
        }
        let mut byte_string_25 = [0u8; 25];
        byte_string_25[25 - byte_string.len()..].copy_from_slice(&byte_string);

        let round1 = Sha256::new().chain(&byte_string_25[..21]).finalize();
        let round2 = Sha256::new().chain(round1).finalize();
        if byte_string_25[21..] != round2[..4] {
            // チェックサム失敗
            continue;
        }

        // これは有効なアドレスに違いありません。文字列を復元しましょう。
        let mut address = base_address.clone();
        for (&should_take, &(digit_index, _)) in subset.iter().zip(&possible_differences) {
            if should_take {
                // この文字は小文字に変換されました
                address[digit_index] = address[digit_index].to_ascii_lowercase();
            }
        }
        let address = String::from_utf8(address).unwrap();
        eprintln!("Found valid address: {address}");
    }
}

どうでしたか?

$ time cargo run --bin attempt3 --release
    Finished `release` profile [optimized] target(s) in 0.01s
     Running `target/release/attempt3`
Found valid address: 1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71

real    0m6,625s
user    0m6,615s
sys     0m0,009s

やった、ずっと良くなりました!正直なところ、最後の試みで最も遅い部分が解析ではなくハッシュ計算だったというのは、少々恥ずかしいことです。だからプロファイラは非常に重要です!時には、明白に見えてもボトルネックを推測できないことがあります。

4回目の試み

他の部分に巧妙な最適化を適用する前に、バイト文字列生成のパフォーマンスを最大化したかどうかを確認しましょう。

アドレスに文字が3つだけ含まれていると仮定します。possible_differences には3つの修正数 A, B, C が含まれます。次に、{A, B, C} の8つのサブセットを反復処理し、以下の数値を計算します:

  • base
  • base + A
  • base + B
  • base + A + B
  • base + C
  • base + A + C
  • base + B + C
  • base + A + B + C

奇妙なのは、それらをどのように計算するかです。base + A + B + C を計算するために、base から始めて3つの数値を順番に加算しますが、前のステップで base + B + C を計算した値があり、その値を覚えておいて A を加える方が速いでしょう。

では、この計算を最適化することはできるでしょうか? もちろんです!

これまでは、3つの質問を順番に尋ねていました:

  • A を加えますか、それとも加えないか?
  • B を加えますか、それとも加えないか?
  • C を加えますか、それとも加えないか?

そして、すべての組み合わせを反復処理していました。これをフラットなアルゴリズムではなく、再帰的な決定木のウォークとして解釈できます。

決定木。最初のノードは「Aを加えるか?」と表示され、「はい」と「いいえ」のオプションで分岐します。各オプションで、新しいツリーが開始され、ルートノードは両方のツリーで「Bを加えるか?」と表示されます。ツリーは再び分岐し、「Cを加えるか?」を通過して、最終的に出力が得られます。ツリーは3段階の高さで、合計8つの異なる出力が得られます: base+A+B+C, base+A+B, base+A+C, base+A, base+B+C, base+B, base+C, base。

決定木。最初のノードは「Aを加えるか?」と表示され、「はい」と「いいえ」のオプションで分岐します。各オプションで、新しいツリーが開始され、ルートノードは両方のツリーで「Bを加えるか?」と表示されます。ツリーは再び分岐し、「Cを加えるか?」を通過して、最終的に出力が得られます。ツリーは3段階の高さで、合計8つの異なる出力が得られます: base+A+B+C, base+A+B, base+A+C, base+A, base+B+C, base+B, base+C, base。

再帰は次のようになります。

fn iterate_through_possible_differences(
    partly_fixed_number: &BigUint,
    possible_differences_tail: &[(usize, BigUint)],
    subset_bitmask: u64,
    base_address: &Vec<u8>,
    possible_differences: &[(usize, BigUint)],
) {
    if let Some((digit_index, fixup_to_add)) = possible_differences_tail.get(0) {
        // この修正を加えるべきか?

        // はい
        iterate_through_possible_differences(
            &(partly_fixed_number + fixup_to_add),
            &possible_differences_tail[1..],
            subset_bitmask | (1 << digit_index),
            base_address,
            possible_differences,
        );

        // いいえ
        iterate_through_possible_differences(
            partly_fixed_number,
            &possible_differences_tail[1..],
            subset_bitmask,
            base_address,
            possible_differences,
        );

        return;
    }

    // これ以上決定することはありません、やった!

    // 数値をバイト文字列に変換します
    let byte_string = partly_fixed_number.to_bytes_be();

    // 先頭をゼロで埋めて正確に25バイトにします
    if byte_string.len() > 25 {
        // 運が悪かった、これは明らかに有効なビットコインアドレスではありません
        return;
    }
    let mut byte_string_25 = [0u8; 25];
    byte_string_25[25 - byte_string.len()..].copy_from_slice(&byte_string);

    let round1 = Sha256::new().chain(&byte_string_25[..21]).finalize();
    let round2 = Sha256::new().chain(round1).finalize();
    if byte_string_25[21..] != round2[..4] {
        // チェックサム失敗
        return;
    }

    // これは有効なアドレスに違いありません。文字列を復元しましょう。
    let mut address = base_address.clone();
    for &(digit_index, _) in possible_differences {
        if (subset_bitmask >> digit_index) & 1 == 1 {
            // この文字は小文字に変換されました
            address[digit_index] = address[digit_index].to_ascii_lowercase();
        }
    }
    let address = String::from_utf8(address).unwrap();
    eprintln!("Found valid address: {address}");
}

そして、次のように開始されます。

iterate_through_possible_differences(
    &parsed_number,
    &possible_differences,
    0,
    &base_address,
    &possible_differences,
);

これは、引数 base_address と possible_differences を再帰全体に明示的に渡すため、少し冗長です。より良い世界では、これは構造体メソッドになり、引数は暗黙的に渡されるでしょうが、それは今のところプロトタイプコードです。

どうでしたか?

$ time cargo run --bin attempt4 --release
    Finished `release` profile [optimized] target(s) in 0.01s
     Running `target/release/attempt4`
Found valid address: 1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71

real    0m5,744s
user    0m5,729s
sys     0m0,014s

これはわずかな改善ですが、一見したところ手間をかけるほどの価値はないかもしれません。しかし、すぐに他の部分でどのように役立つかが見えてくるでしょう。

5回目の試み

これで解析はほぼ完了したので、ハッシュ計算を最適化できるか見てみましょう。まあ、当たり前ですが、暗号化を壊さずにそれはできません。しかし、ハッシュ計算の回数を減らすことはできるでしょうか?

文字のケースを反転させたときに何が起こるかを詳しく見てみましょう。

大文字の A を持つアドレス 1Lbcfr7sAHT...。アドレスをbase58でデコードすると、文字列 00 d6 f6 4e e7 83 6a ... 2f 78 fa 7c が得られます。

大文字の A を持つアドレス 1Lbcfr7sAHT...。アドレスをbase58でデコードすると、文字列 00 d6 f6 4e e7 83 6a ... 2f 78 fa 7c が得られます。

以前と同じアドレスですが、小文字の a になっています。アドレスをbase58でデコードすると、文字列 00 d6 f6 4e e7 83 ed ... 9f 78 fa 7c が得られます。最初の6バイトと最後の3バイトはそのままですが、間の16バイトはすべて以前と異なります。

以前と同じアドレスですが、小文字の a になっています。アドレスをbase58でデコードすると、文字列 00 d6 f6 4e e7 83 ed ... 9f 78 fa 7c が得られます。最初の6バイトと最後の3バイトはそのままですが、間の16バイトはすべて以前と異なります。

文字のケースを反転させると、基になるバイト文字列の部分区間に影響することが判明しました。実際、長い数値に小さい数値を加えると、下位の桁だけが変更されるのは当然のことです(長い繰り上がりが起こるまれなケースを除いて)。58は偶数なので、例えば x⋅58^25 の下位3バイトは必然的にゼロになります。

これは調査する価値があります。もし文字のケースを反転させることがチェックサムだけに影響する場合、それらの文字のすべての組み合わせを反復処理し、不変の21バイトプレフィックスのハッシュを毎回計算する必要はありません。なぜなら、変更されない21バイトプレフィックスのチェックサムを一度計算し、そこから正しい文字のケースを推測できるからです。残念ながら、一部の文字が最初の21バイトにのみ影響する場合、何も最適化できません。2つの文字列が同じチェックサムを持つことは容易です。

新しいアルゴリズムは次のようになります。ケースのすべての組み合わせを再帰的に反復処理し、左から右へ文字ごとに分岐し、さらにケースの変更が最初の21バイトに影響しないことが判明したら、推測を停止して直接ハッシュを計算します。

// snip

fn iterate_through_possible_differences(
    partly_fixed_number: &BigUint,
    possible_differences_tail: &[(usize, BigUint)],
    suffix_sums_of_possible_differences_tail: &[BigUint],
    mut subset_bitmask: u64,
    base_address: &Vec<u8>,
    possible_differences: &[(usize, BigUint)],
) {
    let interval_length = &suffix_sums_of_possible_differences_tail[0];
    // 私たちのさらなる選択に関わらず、最終的なfixed_numberは範囲
    // [partly_fixed_number, partly_fixed_number + interval_length] になります。この
    // 範囲内のすべての数値は、同一の先頭21バイトを持ちますか?

    if partly_fixed_number >> 32 != (partly_fixed_number + interval_length) >> 32 {
        // いいえ、そうではありません。これは、現在の修正を加えるかどうかを推測する必要があることを意味します。
        let (digit_index, fixup_to_add) = &possible_differences_tail[0];

        // はい
        iterate_through_possible_differences(
            &(partly_fixed_number + fixup_to_add),
            &possible_differences_tail[1..],
            &suffix_sums_of_possible_differences_tail[1..],
            subset_bitmask | (1 << digit_index),
            base_address,
            possible_differences,
        );

        // いいえ
        iterate_through_possible_differences(
            partly_fixed_number,
            &possible_differences_tail[1..],
            &suffix_sums_of_possible_differences_tail[1..],
            subset_bitmask,
            base_address,
            possible_differences,
        );

        return;
    }

    // はい、同じです。期待されるチェックサムを計算しましょう。

    // 数値をバイト文字列に変換します
    let byte_string = partly_fixed_number.to_bytes_be();

    // 先頭をゼロで埋めて正確に25バイトにします
    if byte_string.len() > 25 {
        // 運が悪かった、これは明らかに有効なビットコインアドレスではありません
        return;
    }
    let mut byte_string_25 = [0u8; 25];
    byte_string_25[25 - byte_string.len()..].copy_from_slice(&byte_string);

    let round1 = Sha256::new().chain(&byte_string_25[..21]).finalize();
    let round2 = Sha256::new().chain(round1).finalize();
    let correct_checksum = u32::from_be_bytes(*round2.first_chunk::<4>().unwrap());

    let mut current_checksum =
        u32::from_be_bytes(*byte_string_25[21..].first_chunk::<4>().unwrap());
    if current_checksum >= correct_checksum {
        // 最小可能な値が必要な値よりも大きいです。したがって、解はありません。
        return;
    }

    // current_checksum == correct_checksum を得るために追加する修正を決定します
    for (digit_index, fixup_to_add) in possible_differences_tail {
        // fixup_to_add は必然的に u32 に収まります
        let fixup_to_add = fixup_to_add.iter_u32_digits().next().unwrap();
        if current_checksum + fixup_to_add <= correct_checksum {
            subset_bitmask |= 1 << digit_index;
            current_checksum += fixup_to_add;
        }
    }

    if current_checksum != correct_checksum {
        // 解なし
        return;
    }

    // これは有効なアドレスに違いありません。文字列を復元しましょう。
    let mut address = base_address.clone();
    for &(digit_index, _) in possible_differences {
        if (subset_bitmask >> digit_index) & 1 == 1 {
            // この文字は小文字に変換されました
            address[digit_index] = address[digit_index].to_ascii_lowercase();
        }
    }
    let address = String::from_utf8(address).unwrap();
    eprintln!("Found valid address: {address}");
}

fn main() {
    // snip

    // 左から右へ、つまり最上位から最下位へ再帰します
    possible_differences.reverse();

    // 差 A, B, C に対して、[A + B + C, B + C, C, 0] を計算します。
    let mut suffix_sums_of_possible_differences: Vec<BigUint> = possible_differences
        .iter()
        .rev()
        .scan(<BigUint as Zero>::zero(), |state, (_, fixup)| {
            *state += fixup;
            Some(state.clone())
        })
        .collect();
    suffix_sums_of_possible_differences.reverse();
    suffix_sums_of_possible_differences.push(Zero::zero());

    iterate_through_possible_differences(
        &parsed_number,
        &possible_differences,
        &suffix_sums_of_possible_differences,
        0,
        &base_address,
        &possible_differences,
    );
}

理論的には、これは O(2^n) のパフォーマンスを O(n) に最適化するはずです。それは実践的でしょうか?

$ time cargo run --bin attempt5 --release
    Finished `release` profile [optimized] target(s) in 0.01s
     Running `target/release/attempt5`
Found valid address: 1Lbcfr7sAHTD9CgdQo3HTMTkV8LK4ZnX71

real    0m0,954s
user    0m0,941s
sys     0m0,013s

はい、その通りです!

すでに元のRustバージョンよりも35倍高速になりました。そして、1秒未満で完了する総当たり計算は、神のみぞ知る時間がかかるPythonバージョンと比較すると、さらに速く見えます。稼いだ休息を使えるでしょうか? それをする前に、別のアドレスを復旧してみましょう。

-let garbled_address = "1lbcfr7sahtd9cgdqo3htmtkv8lk4znx71";
+let garbled_address = "18ryviovmwfyzhrzktjkqgycjkujoxh3k6";
$ time cargo run --bin attempt5 --release
    Finished `release` profile [optimized] target(s) in 0.01s
     Running `target/release/attempt5`
Found valid address: 18ryVioVmwFYzhRZKTjKqGYCjkUjoxH3k6

real    0m14,347s
user    0m14,334s
sys     0m0,012s

おや。それは良くないです。その遅さの理由は、ベンチマークに使用したアドレスよりもこのアドレスの方が桁数がはるかに少ないため、振り返ってみると明らかです。そして、これは私が意地悪をしているのではなく、実際にZeroNetで使用していたランダムに生成されたアドレスです。

6回目の試み

おそらく、ドメイン固有の最適化はすべて適用したので、プロファイラを開始して、非漸近的なローエンドの果実がないか確認しましょう!

$ perf record target/release/attempt5
WARNING: perf not found for kernel 6.8.1-060801

  You may need to install the following packages for this specific kernel:
    linux-tools-6.8.1-060801-generic
    linux-cloud-tools-6.8.1-060801-generic

  You may also want to install one of the following packages to keep up to date:
    linux-tools-generic
    linux-cloud-tools-generic

そうです、すみません、Ubuntuでメインラインカーネルを使っています。別のコンピューターからperfとそれにリンクするものを取得します。

$ alias perf="LD_LIBRARY_PATH=. ./perf"

$ perf record target/release/attempt5
Found valid address: 18ryVioVmwFYzhRZKTjKqGYCjkUjoxH3k6
[ perf record: Woken up 9 times to write data ]
[ perf record: Captured and wrote 2,271 MB perf.data (59225 samples) ]

$ perf report
Samples: 59K of event 'cycles:P', Event count (approx.): 58317241835
Overhead  Command   Shared Object      Symbol
  66,33%  attempt5  attempt5           [.] sha2::sha256::soft::compress
   8,23%  attempt5  attempt5           [.] attempt5::iterate_through_possible_differences
   5,63%  attempt5  attempt5           [.] num_bigint::biguint::convert::to_bitwise_digits_le
   5,50%  attempt5  attempt5           [.] num_bigint::biguint::shift::biguint_shr2
   3,80%  attempt5  libc.so.6          [.] _int_free
   2,68%  attempt5  libc.so.6          [.] malloc
   2,17%  attempt5  libc.so.6          [.] cfree@GLIBC_2.2.5
   1,93%  attempt5  attempt5           [.] num_bigint::biguint::addition::<impl core::ops::arith::Add<&num_bigint::biguint::BigUint> for num_bigint::biguint::BigUint>::add
<snip>

これは驚くことではありません。最も遅い部分はハッシュ計算です。sha2 クレートはどのようにハッシュを計算するのでしょうか?

https://docs.rs/sha2 には異なる実装についての言及はありません。GitHubページにもありません。しかし、おお、待ってください、GitHubリポジトリを見ると、そのCargo.tomlには興味深い機能があります!

[features]
default = ["std"]
std = ["digest/std"]
oid = ["digest/oid"] # Enable OID support. WARNING: Bumps MSRV to 1.57
assembly = ["sha2-asm"] # WARNING: this feature SHOULD NOT be enabled by library crates
# Use assembly backend for LoongArch64 targets
# WARNING: Bumps MSRV to 1.72. This feature SHOULD NOT be enabled by library crates
loongarch64_asm = []
compress = [] # Expose compress functions
force-soft = [] # Force software implementation
assembly-aarch64 = ["assembly"] # DEPRECATED: use `assembly` instead

asm 機能を使ってみるべきでしょうか?

$ cargo add sha2 -F asm
    Updating crates.io index
      Adding sha2 v0.10.8 to dependencies
             Features:
             + assembly
             + sha2-asm
             + std
             - assembly-aarch64
             - compress
             - force-soft
             - loongarch64_asm
             - oid
    Updating crates.io index
     Locking 2 packages
      Adding cc v1.0.94
      Adding sha2-asm v0.6.3

$ cargo build --bin attempt5 --release
<snip>

$ time cargo run --bin attempt5 --release
    Finished `release` profile [optimized] target(s) in 0.01s
     Running `target/release/attempt5`
Found valid address: 18ryVioVmwFYzhRZKTjKqGYCjkUjoxH3k6

real    0m13,143s
user    0m13,127s
sys     0m0,015s

実行時間はわずかに減少しましたが、顕著ではありません。sha2 は行き止まりのようです。

SHA-256とはそもそも何でしょうか? SHA-2 のWikipediaページには次のように書かれています。

SHA-256 および SHA-512 は、それぞれ8つの32ビットおよび64ビットワードで計算される新しいハッシュ関数です。

これは、SHA-256ハッシュの計算が32ビット整数の多くの操作から成ることを示唆しています。実際、擬似コードはそのようにしています。SIMDを使えるでしょうか? 多くのx86プロセッサはAVXおよびAVX2拡張をサポートしており、これらは他の機能に加えて、8つの32ビット整数に対する並列計算を可能にします。古いプロセッサやx86以外のプロセッサは通常、128ビットSIMDしかサポートしませんが、それでもパフォーマンスを4倍に向上させるはずです。試す価値はあります!

いくつかのボイラープレートから始めましょう。

// snip

struct ParallelChecksum<'a> {
    todo: PhantomData<&'a ()>,
}

impl<'a> ParallelChecksum<'a> {
    fn new() -> Self {
        Self { todo: PhantomData }
    }

    fn compute_later(&mut self, string: [u8; 21], callback: Box<dyn FnOnce(u32) + 'a>) {
        // TODO: 並列化
        let round1 = Sha256::new().chain(&string).finalize();
        let round2 = Sha256::new().chain(round1).finalize();
        callback(u32::from_be_bytes(*round2.first_chunk::<4>().unwrap()));
    }

    fn finalize(self) {
        // TODO
    }
}

// snip

fn iterate_through_possible_differences<'a>(
    // snip
    parallel_checksum: &mut ParallelChecksum<'a>,
) {
    // snip

    parallel_checksum.compute_later(
        *byte_string_25.first_chunk::<21>().unwrap(),
        Box::new(move |correct_checksum| {
            if current_checksum >= correct_checksum {
                // 最小可能な値が必要な値よりも大きいです。したがって、解はありません。
                return;
            }
            // snip
            eprintln!("Found valid address: {address}");
        }),
    );
}

fn main() {
    // snip

    let mut parallel_checksum = ParallelChecksum::new();

    iterate_through_possible_differences(
        // snip
        &mut parallel_checksum,
    );

    parallel_checksum.finalize();
}

これは機能しますか?

$ time cargo run --bin attempt6 --release
    Finished `release` profile [optimized] target(s) in 0.01s
     Running `target/release/attempt6`
Found valid address: 18ryVioVmwFYzhRZKTjKqGYCjkUjoxH3k6

real    0m13,922s
user    0m13,864s
sys     0m0,023s

ほぼ大丈夫だと思います。しかし、それは2倍の改善ではありません。CPUポートの異なる効率で異なるCPUポートを利用しているため、本当に同じCPU時間の割合を利用していると言えるのでしょうか?

そうは思いません。この、より現実に近い値に対して、技術用語をinventすべきでしょうか? アイデアはありますか?


結果

以下の最適化を適用しました。

  • Rustで書き直す
  • base58解析を単純な算術演算に置き換える 5x
  • 積ループを再帰に置き換える 1.15x
  • 低い再帰レベルで正しいケースを推測なしで計算する 6x
  • SHA-256計算のベクトル化 2.3x
  • 専用の長整数算術実装を使用する 2.5x
  • よりスマートなベクトル化アルゴリズムを使用する 1.05x
  • 利用可能な場合はSHA-NIを使用する 1.8x

これは約300〜400倍の高速化です。これらのうち、最初の4つは理論に基づいた最適化であり、34倍の改善をもたらし、後者の4つはハードウェアをより活用することで、さらに11倍のパフォーマンスを向上させます。


したがって、良いソフトウェアを書くためにコンピュータサイエンスや数学を知る必要はないと思うなら、それは嘘です。

整数の解析は複雑な数学ですか? そうではありません。base58解析をこのように最適化するために、ある程度の数学的背景知識が必要ですか? 多分。

再帰アルゴリズムを書くためにコンピュータサイエンスの知識が必要ですか? いいえ。ループよりも再帰が時々効率的であることに気づくために、コンピュータサイエンスが提供する直感が必要ですか? そう思います。

先頭の21バイトが変わらなくなる時点で、数学の知識が必要ですか? いいえ。その時点で再帰を終了するのではなく、ハッシュをキャッシュして続行するトリックをいくつか知る必要がありますか? そう思います。

ロケット科学ではありませんが、人々は同じ間違いを犯し続けています。RustのasyncはO(1)ではなくO(n)の継続複雑性を持っているため、tokioはさまざまなハックでこの非効率性を回避する必要があります。開発者は、単に慣れているという理由だけで、タスクに不適切な言語(一般的には悪いわけではない)に固執したり、最も非効率的なデータ構造を選択し続けたりします。これらの選択にもう少し注意を払うべきかもしれません。


ここにはもう一つの教訓があります。問題に、あたかもそれが魔法のように非効率性を隠してくれるかのように、より多くの労働力を投入しようとすることがよくあります。しかし、ハードウェアはしばしば強力であり、問題は、それを利用する方法を学んだことがないことです。

ある逸話を聞いたことがありますが、それは私の中に残っています。ある人がfreeコマンドで利用可能なメモリが少ないことに気づき、Linuxがすべてのメモリを占有しているのは愚かで意地悪だと考えました。しかし、Linuxは実際にはすべてのメモリを永続データに使用していたわけではありません。それは大きなディスクキャッシュを保持しており、プログラムが利用可能なメモリよりも多くのメモリを必要とした場合には安全に削除できました。Linuxは「現時点では誰もこのメモリを使用していないので、I/Oパフォーマンスを向上させるためにそれを借りるのはどうだろうか?」と言いました。

これはCPU使用率にも当てはまります。少なくともサーバーでは。サービスが常にCPUリソースの10%未満しか使用していない場合は、より安価なハードウェアに切り替えるか、ソフトウェアを設定してCPUをより積極的に使用することを検討すべきです。

しかし、CPU使用率とは何でしょうか? すべての主流オペレーティングシステムは、CPU使用率を、プロセッサがCPUで命令を実行する時間の割合として解釈しますが、マイクロアーキテクチャの条件は無視します。スカラーコードとベクトル化コードはどちらもCPUを100%使用しますが、異なる効率で異なるCPUポートを利用します。したがって、それらが同じCPU時間の割合を利用していると言えるのでしょうか?

そうは思いません。この、より現実に近い値に対して、技術用語をinventすべきでしょうか? アイデアはありますか?