ビットコイントランザクション生成コードを最適化する

最近、非常に大きなブロックを持つビットコイン ネットワークをシミュレートするために、複数のマシンから多数のトランザクションを生成する必要がありました。 bitcoind の「sendtoaddress」API を使用する簡単なスクリプトをいくつか作成したので、これらのスクリプトを無限ループで実行して何が起こるかを確認しました。

結果は満足できるものではありません。なぜこのようなことが起こるのかを理解するには、「未確認入力」の問題を理解する必要があります。基本的に、前払い金の一部を使用すると、2 つの新しい出力が生成されます。1 つは目的地への出力、もう 1 つは自分自身への出力 (お釣り) です。これらの出力は、新しいブロックが見つかるまでは「未確認」とみなされ、その後、これらの未確認出力を再度使用できるようになります。ただし、Bitcoin クライアントでは、ユーザーが比較的短い未確認出力のチェーンを構築することしかできず、その後は「未確認出力が多すぎます」というエラーが返されます。 （翻訳者注：ただし、Bitcoin クライアントでは、「未確認の出力が多すぎます」というエラーが返される前に、比較的浅い未確認の出力のチェーンしか構築できません。）

ブロックごとに 1 つのウォレットから 50,000 件を超えるトランザクションを生成することになるため、多くの支払いを確実に生成するには、確認済み出力に似た方法が必要であることにすぐに気付きました。

CPU が 100% 使用され、トランザクションの生成が 10 秒ごとに 1 トランザクション程度に低下しました。これは問題です。これは私が人為的に作り上げたものですが、大企業にとってこれは本当にあり得ない金額なのでしょうか？年間何百万もの支払いを処理する大企業にとって、アドレスの再利用は解決策ではないと思います。問題はアドレスの数ではなく、ウォレット内のトランザクション出力の数です。

そこで、トランザクションコードの最適化を考えました。最終的には、トランザクション生成の効率を約 1,000 倍に高めることができ、UXTO の成長を抑えることができました。詳細は下記をご覧ください！

増分最適化

最初に気づいたのは、ロックに多くの時間が費やされているということでした。具体的にはHaveKey（）とGetTimeOffset（）です。この動作は通常、ループの最初と最後にロックが 1 回ずつ取得されるときではなく、「内部」ループ内でロックが取得および解放されるときに発生します。案の定、 CWallet:: AvailableCoins（...）にタイトなループが見つかりました。そこで、IsMine のロックフリー バージョンを追加し、 LOCK（cs_KeyStore）ループの外側に移動したところ、約 5 ～ 10% の改善が得られました。

前にも述べたように、GetTimeOffset() が CPU を大量に消費していることにも気付きました... そうです... 再びロックがかかります。今回の目的は、64 ビット変数のアトミック読み取りを保証することです。すべての CPU アーキテクチャでこれを実現するには、よりよい方法があるため、サポートされているコンパイラでロックをアトミック 64 ビット操作に置き換えます。

 int64_tGetTimeOffset()
{
t1 は 0 です。
#ifdef __GNUC__ // BU 最適化 - ロックではなくバリアを実行する
t1 = __sync_fetch_and_add(&nTimeOffset,0);
＃それ以外
LOCK(cs_nTimeOffset);
t1 = nタイムオフセット;
#終了
t1 を返します。
}

この問題は、ループ内にGetTimeOffset（）呼び出しを組み込むことでも解決できますが、コードの構造上これは不適切であったため、さらに 5 ～ 10% の改善を実現するためにこのアプローチを選択しました。

これらのパッチはサブシステムへの良い入門書ではありますが、私が望むところに到達できるわけではありません。これを本当に解決するには、大きな実装上の決定を見直す必要があります。

実装を最適化する

最初に目立つ問題は、支払いが行われるたびにウォレット全体がベクターに取得されることです (SelectCoins() CWallet ::AvailableCoins（）を呼び出すのを参照してください)。そして、このベクトルはここで値によって複数回渡されます（つまり、コピーされます）。このビットコインは通常、このウォレットから支払いを行う唯一のエンティティであり、私たち側で最終的なトランザクションの有効性チェックを行うため、「利用可能な」TXO データ構造を保持し、それを支払いとして使用した TXO 関数を削除するだけで安全です。通常、コード サイズが定数より小さい場合、コードはこの構造を再生成します。これは、新しい TXO を追加したり、ブロックの再編成を修正したりして、構造が常にウォレットとまったく同じであることを保証しようとするよりもはるかに簡単で、データ構造をすばやく再生成できるため、小さなウォレットに大きな影響を与えません。

2 番目の効率ボトルネックとなるのは、トランザクションの構築とは別に、ウォレットに支払い要件を満たすのに十分な資金が含まれているかどうかを確認するコードです。問題は、これを行うには、コードがウォレット内のすべての出力をカウントする必要があることです。つまり、ウォレットの TXO セット全体を再度反復処理する必要があります。一般的に、例外的な条件のテストがコストがかかり、遅かれ早かれ発見される場合は、パフォーマンスのボトルネックとなるコードの後半でテストを実行する方が適切です。もう 1 つのアプローチは、ウォレットの現在の残高をキャッシュし、再計算するのではなく、入出金に基づいて更新することです。しかし、このアプローチでは、一貫性を確保するために多くの脆弱なコードが必要になります。

最後に、 CWallet:: CreateTransactionのコードには重大な非効率性があります。まず、取引手数料がないと仮定すると、常にコイン選択が実行されます。これは、Bitcoin Core に最近追加されたブロック サイズの制限やその他の手数料コードを考慮すると、まったくばかげています (これについては後で詳しく説明します)。 2 番目に、コードが取引手数料を誤って推測した場合、選択された入力に実際の取引手数料を支払うのに十分な金額があったとしても、コードはより多くの手数料で通貨選択を再実行します。 (こちらとこちらを参照)

アルゴリズムの最適化

最適化ツールボックスの最後のパフォーマンス オプションは、「このアルゴリズムは実際に目標を達成しているか?」と尋ねることです。考えれば考えるほど、目標が達成されていないことに気づきました。実装されたアルゴリズムは「ナップサック問題」を解決しようとします。主な問題は、特定の重量を超えない「物」の最大値を選択することです。ビットコイン ウォレットの場合、問題は似ていますが異なります。トランザクション値よりも大きい入力セットを選択し、入力と出力の値を可能な限り一致させるようにすることです。ナップサック問題は非常に難しく、NP困難であることが証明されています。しかし、私はビットコインには価値を失わせる別の問題があることに気づきました。それは、「ナップサック問題」の大きさ（取引価値）が取引手数料に基づいており、その手数料は取引全体がシリアル化されるまで不明だったのです。

最終結果として、オプティマイザが出力値に近い入力セットを見つけることで「良い仕事」をした場合、取引手数料を含めることはできず、取引は拒否されます。この場合、コードは計算された手数料を取引金額に追加して再試行します。しかし、これは意味がありません。前のソリューションのサイズと次のソリューションのサイズの間には実際の関係はありません。代わりに、トランザクションの一般的な類似性により、それは単なる操作です。トランザクションの入力と出力がわかれば、そのサイズを大まかに見積もることができます。

実際、私のテストでは、バックパック オプティマイザーはほぼ毎回複数回の支払いを求められました。

この「ナップサック問題」を最適化する目的は何でしょうか? .1 または .0001 の変更が受け入れられるかどうかを誰が気にするでしょうか?正確な解を見つけられなかった場合のペナルティは追加の出力変更であり、どのアルゴリズムを省略しても障害はまったく同じです。はい、保存された出力と完全に一致することは可能ですが、6〜10桁の数字（1ビットコインは100,000,000サトシ、コード内のカウントはサトシ）を考えると、その可能性は低くなります。特に、取引手数料によって各支払いに小さな非端数が追加されるため、末尾に多数のゼロが付いた 3 桁の数字ではなく、実際には 6 桁から 10 桁の数字を扱うことになります。このアルゴリズムには柔軟性があまりなく、大量の入力を使用するのに実際に障壁があります。最後に、ユーザーにとって、ニアエラーは実際には重大なエラーではなく軽微なエラーです。ニアエラーの場合、コードは出力を生成する代わりに、この「ダスト」をトランザクション手数料に変換するためです。しかし、もっと大きな間違いは、残りの金額を変更先の住所に支払うことです...

したがって、明らかに通貨の選択は間違った最適化になっています。

では、通貨の選択では実際に何を最適化すべきでしょうか?今日のビットコインの文脈では、この質問に対する答えは明らかになります。通貨の選択により、取引手数料に大きな影響を与えることなく、UTXO セットを最小限に抑えることができます。言い換えれば、出力を生成するよりも多くの TXO 入力を消費するようにし、トランザクションを妨げない大きな入力を持つことで、ウォレットのニアダスト出力をトランザクションで使用するのが理想的です。 [プライバシー擁護派は驚くかもしれないが、ウォレットはブロックチェーン分析を混乱させるためにデジタルコインを分離しようとすべきではないのか？]この質問に対する私の答えは、トランザクションを作成するにはこれらの出力を組み合わせる必要があるため、アルゴリズムに依存するのは非常に危険であるということです。多くのウォレットは、ウォレットを「アカウント」または混ざらないサブセクションに分割できるようにするという、より良いアプローチを採用しています。

新しいアルゴリズム

新しいアルゴリズムは非常にシンプルです。目標は NP 困難な問題を解決することではなく、UTXO セットを最小化し、効率を最大化することだからです。

すべてのウォレット出力を出力値別に分類されたコンテナに保存することにより、「オフライン」で開始します。このコンテナは、支払いリクエストを受信するたびにウォレットから再ロードされるわけではありません。代わりに、数百未満の TXO が含まれている場合にのみリロードされます。

支払いリクエストを受信すると、まずトランザクション手数料を見積もり、妥当な数の入力と出力を考慮してリクエストの値に追加します。これを「目標値」と呼びましょう。次に、最大のターゲット値を持つ最小の TXO を選択し、それをソリューションとして保存します (ソリューションがない場合は、ソリューションが見つかるまで、または他に何も不可能になるまで、それを最大の TXO と組み合わせます)。次に、後方に反復して、このターゲット値よりも小さい TXO を選択します。これらの TXO ごとに、新しいターゲット値 (ターゲット値 - TXO 値) を作成し、構成可能な TXO の数よりも大きいソリューション セットを再帰的に構築します。同時に、ランダムな TXO を選択し、同じアルゴリズムを試します。これにより、特に後方反復子が小さな値の変更のセットに対して動作する場合に、アルゴリズムが TXO のさまざまな値を考慮できるようになります。

多数の反復処理の後、またはアルゴリズムが目標値に「近づいた」場合 (必要な反復処理の数が多いほど、「近い」の意味についての考え方が緩和されます)、最適なソリューションが返されます。

アルゴリズム全体は約 200 行のコードで実装されています。

その他のアイデア

ユーザーが不満を言っていることの一つは、取引手数料が高いことです。これは明白です。誰も 5 ～ 20% を支払いたくありません。クレジットカードを使うのもいいでしょう。では、コードにいくつかのチェックを含めてみてはいかがでしょうか?それは複雑でなければなりませんよね？間違っている。

結果

このアルゴリズムは、「標準」の 2GHZ ラップトップ ハードウェアおよび VM 内で 1 秒あたり 20 件の支払いをサポートし、CPU をわずか数パーセントしか使用しません (大規模なトラフィックをブロックしている原因が判明したらこのファイルを更新しますが、おそらくウォレットの変更をディスクに書き込むことになります)。したがって、トラフィックはテストに使用されたウォレット サイズの元のアルゴリズムの約 200 倍になり、最も重要なのは、トラフィックが指数関数的に増加するのではなく、ウォレット サイズの対数で増加することです。元のアルゴリズムは CPU を 100% 使用しますが、このアルゴリズムは最大 10% しか使用しません。つまり、元のアルゴリズムよりも約 1000 倍効率的です。

ウォレットに 1 mBTC から 10 BTC の範囲の 10000 以上のランダム TXO があると仮定すると、ほとんどの場合、2 ～ 4 つの入力が選択され、2 つの出力 (出力 + 変更) が使用されます。したがって、UTXO サイズは同じままか、減少します。

当然のことながら、TXO 選択結果を元のアルゴリズムと比較するなど、さらに分析を行う必要があります。しかし、このコードは非常に大きなブロックをテストするという私の目的を簡単に達成したので、この投稿を書く時が来たと思いました。

ユーザー エクスペリエンスを向上させ、完全に検証された、企業に適した Bitcoin ウォレットを作成するには、トランザクションの作成に関してまだ多くの作業が必要であることは明らかです。私が考え、示したように、これらの変更により、他のソリューションよりも簡単な方法で、ウォレットの動作の改善（UTXO の膨張制御など）を奨励することもできます。また、UTXO の膨張を最小限に抑えようとしているアルゴリズムは、UTXO を削減するトランザクションを優先するマイナー アルゴリズムにも対処する可能性があります。

時間とエネルギーがあれば、この変化は起こり得ます。十分な変更（ユーザー エクスペリエンスに重点を置いた変更と、Bitcoin クライアントを企業が使用できるようにする変更）が行われれば、実際にノード数が増加する可能性があります。