こんにちは。2020年の技術職就業型コースのインターンシップに参加した高橋です。
普段は京都大学でアルゴリズムやデータ構造の研究をしています。
インターンでは LINE Blockchain Lab に所属し、各種ブロックチェーン技術の調査や、それに基づく機能改善の提案などを行いました。
この記事では、調査中に自分が面白いと思った技術、またインターンを通した感想についてお伝えできればと思います。
調査内容
ブロックチェーンについて
ブロックチェーンについて、聞いたことがある人も多いのではないかと思います。
ビットコインをはじめとした暗号通貨の基盤となる技術であり、最近では、DApp と呼ばれる分散型アプリケーションのプラットフォームとしても注目されています。一方で、技術の詳細については、まだまだ知っている人は少ないかもしれません。
ブロックチェーンが実現するのは、「非中央集権的に意思決定を行う分散システム」です。順を追って説明します。
まず分散システムとは、独立した複数のコンピュータが通信によって協調しながら特定のタスクを遂行するシステムのことです。たとえばインターネットは、情報交換を目的とした典型的な（そして最大の）分散システムです。
このような分散システム上で意思決定、たとえば多数決を行うことを考えます。
システム上のコンピュータがすべて正常で信頼できる場合、話は簡単です。これはその分散システムが、特定企業の社内システムとして運用されている場合などに相当します。このときは単に、コンピュータ同士でお互いの意見を教え合い、それを基に多数決を行えばよいです。
しかし、非中央集権的な P2P の分散システムなどには、システムを攻撃する意図を持った悪意のあるコンピュータが紛れ込んでいることがあります。
悪意を持ったコンピュータは無尽蔵に水増しされている可能性もあり、単純にシステム全体の多数決を行おうとすると正しい判断ができないおそれがあります。
そのようなコンピュータからの攻撃に耐えて、正常なコンピュータ間の多数決を行うことは、分散システムにおける主要な問題です（ビザンチン将軍問題として知られています）。
ブロックチェーンはそのような、P2P ネットワークにおける合意の形成を実現するためのシステムの一種です。たとえば最初のブロックチェーンであるビットコインは、暗号通貨の決済という意味での合意を行うためのシステムとして、Satoshi Nakamoto により開発されました。ビットコインでは、決済の処理に多くの計算資源 (work) を要求することで、不正な決済を回避するようにしています（このような方法を proof-of-work (PoW) と呼びます）。
一方で proof-of-stake (PoS) と呼ばれる形式を採用しているブロックチェーンもあります。PoS 型のブロックチェーンでは、合意形成プロセス（コンセンサス）の参加者は、ネットワークのトークン（通貨のようなものです）をどれだけ賭けるかによって重みづけされます。賭けたトークンは、コンセンサスでよい主張をすれば増え、悪い主張をすれば没収されます。そして合意に影響力を持つために多くの掛けトークン (stake) を要請することで、不正に対応します。
PoW では計算資源という、ブロックチェーン外部の価値に安全性が担保されているのに対して、PoS ではトークンという、ブロックチェーン内部の価値に安全性が担保されていると対比することができます。
コンセンサス参加者の選出
自分が今回のインターンで主に調査した Polkadot と呼ばれるブロックチェーンは、PoS 型のコンセンサスを採用しています。
より正確には、Polkadot のコンセンサスは Nominated PoS 型と呼ばれていて、参加者間の投票によって選ばれた一部の参加者がコンセンサスの過程に加わります (コンセンサスに加わる参加者のことを、Polkadot では validators と呼びます)。
このように、コンセンサスの参加者を限定する理由としては、以下のような理由があります。
- コンセンサスにかかる遅延を減らす
PoS 型のコンセンサスで用いられるコンセンサスアルゴリズムは、一般に、コンセンサスの参加者が増えるほど実行に多くの時間がかかります。
特に全参加者をコンセンサスプロセスに加えてしまうと、一回のコンセンサスに莫大な時間を費やしてしまうことも考えられます。
そのような事態を避けるためには、参加者の代表だけをコンセンサスに参加させることが必要になってきます。 - コンセンサスの参加者は高い可用性を求められる
ブロックチェーンにおけるコンセンサスは、昼夜問わず絶えず行われ続けます。
そのため、コンセンサスの参加者は常にネットワークに接続し、また広い帯域を確保している必要があります。
そのような要請は全ての参加者が達成できるものではないため、参加者を限定する必要があります。
ところで、投票による validators の選出は、具体的にどのように行えばよいでしょうか？
というのも、ただ投票数が多い順に選出してしまうと、投票者の意見を適切に validators へと反映できない場合がありうるからです。投票者が持つ主義主張の構造を保って圧縮したような validators を得られるのが理想になります。
BalPhragmms
そのような要求を持った選出に使うことできるアルゴリズムとして、BalPhragmms と呼ばれるものが Polkadot の運営元である Web 3.0 Technologies Foundation より提案されています (https://arxiv.org/abs/2004.12990)。
このアルゴリズムはかなり込み入っており、完璧に説明するのは難しいですが、概要について述べたいと思います。
BalPhragmms では、参加者間の投票の様子を以下のような二部グラフの構造で捉えます。
このグラフを用いて、投票者の投票によって候補者の中から validators を選出する方法について考えます。
グラフの左側の頂点は投票を行う参加者 (nominator と呼ばれる) を表していて、右側の頂点は投票の対象となる validators の候補者を表しています。投票者と候補者を結ぶ辺は、その投票者がその候補者に投票したことを意味しています。nominator に複数の辺が接続しうる、つまりある投票者が複数の候補者に投票することができる点が、一般的な投票のイメージとは少し違うかもしれません。また上の図には載っていませんが、各 nominator は投票に際して DOT と呼ばれる Polkadot のトークンをネットワークに対して賭け（ステークし）ます。そして、より多くのステークを行っている nominator の投票ほど、重視して扱うことにします (PoS の原則)。
このような投票状況が与えられたとき、候補者から選出した validators の「よさ」を、どのように測ればよいでしょうか？
BalPhragmms では、validators のよさを測るために、一風変わった指標を用いています。それは、「nominator のステークを、その nominator が投票した validator に対して分配すると仮定したとき、validator 全体でどれだけ均等になるように配れるか？」というものです。この指標は論文中で、under representation（一定以上支持されている意見が採用されないこと）および over-representation（一定未満しか支持されていない意見を採用してしまうこと）を防ぐために使えることが証明されています。
たとえば以下の図のように、各 nominator がステーク（図ではコインで表される）を行っていたとして、これをグラフの辺に沿って、選ばれた validators に対して分配することを考えます。
仮に validators として、上から 1, 2 番目の候補者を選ぶことにすると、以下のように、2 人の validator が受け取るステークの量が均等になるように分配を行うことができます。
一方で、上から 2, 3 番目の候補者を選ぶことにすると、以下のように少し偏りのある分配しかできません。
この場合 BalPhragmms では、前者の validators のほうを、よりよいものとして評価します。
ここではインフォーマルに説明しましたが、「均等な割り当て」や「validators のよさ」などの概念は厳密に数式を用いて定義することができます（詳しくは原著論文の方を参照してください）。そして BalPhragmms は、そのような定義のもとで、できるだけよい validators を見つけることができるアルゴリズムになっています (最もよい validators を求める問題は NP-hard であることが示せるので解くのを諦めざるをえませんが、BalPhragmms は出力のよさが理論的に保証できる近似アルゴリズムです)。
成果
インターン期間中は、上記の BalPhragmms を始めとしたブロックチェーンで用いられているアルゴリズムについて、いくつか調査を行い、最終的に調べた内容をインターンの最終週にチーム内のミーティングで発表しました。発表に際してチームの方々から多くの助言をいただくことができ、アルゴリズムのような複雑なことがらを説明することについて、とても有益な経験をできたと思っています。
インターンを通した感想
LINE のインターンでは、実際のアクティブなチームに配属されて仕事を行います。そのため、会議やミーティングへの参加、勤怠の管理なども実際の社員の人と同様に行います。なので、より実際に近い仕事を体験できる環境だと感じました。今年のインターンは基本的にリモートで進めていく形になりましたが、一度だけ新宿にあるミライナオフィスに行く機会をいただくことができました。
ミライナオフィスはとてもきれいな広々としたオフィスで、快適に仕事をするためのいろいろな工夫が散りばめられていると感じました。
受付近くのショップスペースでは、お弁当やコーヒーなどを購入できるほか、LINE の各種グッズが飾られていました。
LINE のインターンは、他にはない経験ができる貴重なインターンだと思います。気になった方は是非、来年のインターンに応募してみてください。