ブロックチェーンと等比数列型漸化式

こんにちは。 突然に開発者ブログの出番をつきつけられ戸惑いを隠しきれない代表の釣崎です。

今回は、テコテックという会社の社⻑としての考えや倫理・哲学などは一切抜きにして、ソフトハウスの技術ブログとして何か書いてみようと思う。

当社がどういう会社なのかや、私のことなどは、ほかの人たちが書いているので、また見てください。

さて、とはいえ、しばらくコアプログラムに触れていないどころか、インスタンスの起動すらワンタップで済ませてしまうようになって、たまに JS か何かのフックで実行ファイルを 並べたいときに Shell でも走らせるくらいしかなく、最近の最新プログラム事情がわからない。

ということで、3日かけて社内の git をなめ回してみたところ、意外に基礎的なところでまだ書けそうだと思い、今回は漸化式というものをプログラムに落とし込む際に利用することについて書いてみようと思う。


等差数列型漸化式の一般項の解

そもそも数列と漸化式とは何か、ということについては、どこかのサイトで拾ってきてもらえればと思うが、プログラムを書いてる中で最も頻繁に出くわす場面の等差数列の漸化式の一般項の求め方については押さえておきたいと思う。

a_1 = 3,   a_{n+1} = a_n + 4 で定められる数列{( a_n )}の一般項を求める場合には、

※n が仮に 1000 の場合

$a = 3;
for($n = 1; $n <1000; $n ++)
{
  $a = $a +4;
}

このようにプログラマーはレジスタに仕事をさせがちで、実際に当社でも多くの技術者がこのようなループを作っている(一般的にもそうなのではないかと思う)。ところが、漸化式の一般項の抽出が分かっていれば、

a_{n+1}–a_n=4,  a_1=3

隣り合う項の差が 4 (一定)で、初期値が 3 という例の等差数列型漸化式であることに気づき、a_{n+1}–a_n=4より、数列 (a_n)は初項3、公差4の等差数列であることが分かるので、

 a_n = 3 +(n-1)4 = 4n - 1

と一発で実行環境を駆動させることができる。さらに、コンパイラに気を使ってビルドの処理速度をも稼ぐのであれば、以下のように2行書くだけで良い。

$n = 1000;
$a = $n<<21;


この令和という時代でもシフト演算での畳み込みに意味はあるのか

今回のような 2 の累乗のような美しい例はともかくとして、いくつものシフト演算を結合しなければならない場合に、ネストしたパイプラインやマイコンへのコンパイリングが定着した令和ではどうなんだろうか。昔は乗算のどちらか片方のオペランドが定数でさえあればシフト演算に展開したものだ。

今回の事例をもとにして、最も汎用的に利用されていると思われる Amazon EC2 のオンデマンドインスタンス t2.micro で実験してみたところ、0.021 ミリ程度の差はあるようだった。Execution はともかく、アセンブラへのマッピングには差が出るようで、無数に Call する場合はアドレス上のポインタのフラグメントが散らばるためか、コンテナの深いところでメモリコンパクションが働くらしい。

おそらく、Swift や Android でも同じことであろう。
ガベコレが発動してしまう環境下では、割り込みなど OS と呼吸を合わせるのが実質的に不可能であり、できる限りのコンピュータに対する書き手の思いやりが必要なのではなかろうか。


配列を使うなどはさらに無駄

gitbucket を眺めていると、すぐ配列にデータを投入している事例もよく見受けられるが、配列たるものを導入して良いのは、基本的に、文字列・音声・画像(動画)の処理だけだと思っている。自然・物理現象・デザインやデジタルコンテンツの取り扱いなど、特に中央で管理するサーバーの主記憶は有限なので、I/O の力を借りて局所的に処理をするのが良い。


等比数列型漸化式の場合はどうか

話を戻そう。昨今の AI 技術の中核を担う、ニューラルネットワークやディープラーニングでは、無数のパーセプトロンにウェイトとバイアスを何度もかけて畳み込むため、GPU と CPU のバランスをハードウエアのセレクションで取るのではなく、等比数列を計算するなど深いファンクションで調整できるのではないかと思う。


ブロックチェーンと漸化式

Bitcoin Core を形成する PoW の合意形成メカニズムだが、ハッシュを引き当てる確率密度は 2018 年ごろ以降の Bitcoin Cash(BCH) から Difficulty Adjustment Algorithm -II(DAA-II)を使って調整されていて、これは実際に工程を漸化式によって紐解くことができるのでこれは紹介しておきたい。


そもそも BCH 以前の Bitcoin の何が問題であったか

技術的な観点でいうと、ここは様々なブロックチェーンの中でも最も興味深いところであり、いくつかの問題はあるのだが、重要なポイントは、もともとマイナーが解くゲームが、資源を供給した量によって報酬が決定される設計になっていて、都度現れる難易度に応じてハッシュレートの供給を調整するところである。しかしながら、逆にいうと初期のアルゴリズムではハッシュレートに粘性があったとしても、ハッシュレートがそのパズルの難易度に与える影響を考えられていないために、ブロックの生成を安定的に行うことができないことが課題だったと思う。

難易度調整が入る直前の 2016 ブロックにおける、答えを引き当てる期待値は、ブロックの生成にかかる時間に以前の確率を乗じてリニアに伸ばされている。

2016 / (Exp * B_t)

Exp: 以前の解答を引き当てた期待値
B_t: それに必要とした時間

ところが、2018年以降のアルゴリズムでは、ブロックチェーンの制御において、マイナーが機敏に調整するハッシュレートの粘性に応じてブロックの生成を安定化させるために、Satoshi Nakamoto の書いた bitcoin-abc/src/rpc/blockchain.cppp#L59-L72 の中で、この Difficulty の取得を以下のように再定義している。

{
  int nShift = (blockindex->nBits >> 24) & 0xff;
  double dDiff = double(0x0000ffff) / double(blockindex->nBits & 0x00ffffff);
  
  while (nShift < 29) {
    dDiff *= 256.0;
    nShift++;
  }
  while (nShift > 29) {
    dDiff /= 256.0;
    nShift--;
  }
  return dDiff;
}

これは以下の漸化式に従うことによって確率密度の更新過程を決定することができるようにデザインされたと私は考えている。n 番目のブロックの期待値を Exp(n)とすると、直近 144 ブロックの生成に必要とした時間は、以下の漸化式で書けることになる。

Exp(k+1)*\sum_{n=(k+1)-144}^{k} \frac{1}{Exp(n)}

ブロックが連結されるたびに期待値がアップデートされるため、このような階差数列型の等比数列漸化式で表現することになるが、ハッシュパワーの供給量に応じて確率が変動するために、 Exp(k)に近づいていくことが証明できる。この Normal Difficulty Adjustment については、2017 年前後でのアルゴリズム比較をローカルネットを張って実験することは可能なので、これは次回の機会に残しておきたいと思う。


金融の安定化は誰しもが望むことではあるが、それはアセットが紐づく価値交換の裏づけだからであるという一方で、トレーディングなどのある側面だけを切り取ると、不安定だからこそ価値がある世界もあり、ブロックチェーンというファンクションが決済と運用の狭間で揺れ動いている姿が見てとれる。

tecotec.co.jp