ネズミ講 (ピラミッド・スキーム) の数学的考察

Bitcoin が誕生して以来, これまで星の数ほどのデジタルアセットがブロックチェーン上で次々と誕生しています.
このデジタルアセットを用いることで, クロスボーダー送金が以前よりも格段に容易となりました.

便利になる一方で, デジタルアセットにかかるクロスボーダー犯罪 (特に詐欺) が多発しているのが現状です.
例えば, ポンジ・スキーム, HYIP (High Yield Investment Program),
違法性の高いマルチ商法 (ネットワークビジネス, ネットワークマーケティングとも言う)*1, ネズミ講などが挙げられます.
数年前の仮想通貨ブーム時は, ICO 詐欺, マイニング詐欺をよく見かけていました.

*1 マルチ商法自体は違法ではありませんが, 勧誘行為に違法性が見受けられるという意味です.

詐欺の被害にあったとしても, 仮想通貨のアドレス (アカウント) は本人確認が必要な取引所を介さない限り,
犯人の個人情報と紐付かないため, 振り込め詐欺の捜査よりも難航します.
ちなみに, 本人確認が必要な取引所を介したとしても, 途中で匿名通貨に交換していれば*2,
換金される可能性があります.

*2 よく勘違いされている事実ですが, Bitcoin は暗号化がされおらず, 匿名でもありません.
ここで, 匿名とは, Bitcoin の送信者アドレスと受信者アドレスが秘匿されているという意味です.
アドレスが個人情報と直接紐付かないというだけで, あくまでも擬似的な匿名性を有しているだけです.

さて, ここからはタイトルにある通り, 詐欺の1つであるネズミ講 (ピラミッド・スキームとも言う) について,
それが破綻する仕組みを数学的に考察します.

ネズミ講にかかる商法の会員の報酬は, 同じ商法への会員を募ることによって得られます.
会員 (親) はそれぞれ数人の新規会員を勧誘しなければなりません.
新規会員 (子) は入会費等の手数料を支払い, その一部が紹介料として勧誘者 (親) の報酬となります.
さらに, 子の会員が新規会員 (孫) を入会させると, 親と子は紹介料を得ることができます.
このように, 会員が会員を勧誘していくことで会員が増えていくさまを, ネズミの出産に例えてネズミ講と呼ばれています.
数学的に言うと, ネズミ講はある期間にネズミがどれだけ増えるかを求めるネズミ算式で, 等比級数の問題となります.

仮に, それぞれの会員が報酬を受け取るための条件として, 2 人の新規会員の勧誘が必要とします.
このネズミ講の首謀者を第 1 階層とすれば, 第 2 階層は 2 人, 第 3 階層は 4 人, と続いていきます.

このとき, 等比級数で表現すると, 初項が 1 (首謀者), 公比 2 (新規会員) であるから,
第 N 階層までの人数は,
1 × (1 – 2N) / (1 – 2) = 2N – 1
となります.
第 26 階層にもなると, 合計会員数が 6,700 万人となり, 第 27 階層目で日本の人口を超えてしまいます.
このようなことから, 会員が飽和してしまい破綻することになるのです.

視覚的には下図のようにピラミッド型の構造をしていることがピラミッド・スキームと言われる所以です.


図1 ネズミ講の構造はピラミッド型

逆に, 上記と同じ条件で, アメリカの人口 329,065,000 (2019年データ) を超える時点を見てみましょう.
次の式を満たす最小の階層 (自然数) N を求めます:
2N – 1 > 329065000
⇔ 2N > 329065001.

ここで, 両辺に log2 をとれば,
N > log2(329065001)
⇔ N > 28.293797350225926.

よって, 最小の階層 N は 29 となります.

Scam Vectors by Vecteezy

簡単なブロックチェーンの実装

ブロックチェーンベースの分散型合意形成アルゴリズムの一部であるノードを実装してみました.
プログラムは, 入力されるトランザクションとブロックを受信し, 更新されたブロックチェーンを維持するよう実装します.
これは Princeton 大学の講義 “Bitcoin and Cryptocurrency Technologies” のプログラミング課題の1つです.

ブロックチェーンでは, (複数の) フォークが存在する可能性があるため, ブロックはリストではなくツリーを形成します.
また, 新しいブロックが作成される可能性のある全てのブロックに対応する UTXO プールを維持する必要があります.

以下, 実装における前提です:

  • ブロックチェーン全体は巨大なサイズになる可能性があるため, 最新ブロックだけを維持するものとします.
    保存する数は, API の機能を全て実装できていれば, 自由に決められます,
  • 新しい Genesis block は採掘されません. Genesis block を名乗るブロック (親は NULL ハッシュ) を受信した場合,
    BlockChain クラスの addBlock(Block b) メソッドで false を返すことが出来ます,
  • 同じ高さのブロックが複数ある場合は, getMaxHeightBlock() メソッドで最も古いブロックを返します,
  • 簡単のために, あるブロックの coinbase トランザクションは,
    その上に採掘された次のブロックで使うことが出来ると仮定します.
    これは, 実際の Bitcoin プロトコルでは, 使用可能になるまでに 100 回の承認が必要な「満期」期間がある事と異なります,
  • ブロックチェーンのグローバルトランザクションプールを 1 つだけ維持し,
    トランザクションを受信したらそこにトランザクションを追加し,
    新しいブロックを受信または作成したらそこからトランザクションを削除します.
    ブロックチェーンの再編成, つまり分岐チェーンが新たな最長チェーンになったときに,
    一部のトランザクションが削除されても構いません.
    具体的には, 元のメインブランチに存在する (つまりトランザクションプールから削除される) が,
    分岐ブランチには存在しないトランザクションが失われる可能性があります,
  • coinbase の値は 25 コインで一定とします*1, 
  • ノードが新しく受信したブロックの有効性を確認する場合,
    取引が有効な集合を形成しているかどうかを確認するだけで十分です.
    その集合は, 可能な限り最大のトランザクションの集合である必要はありません.
    また, PoW (Proof of Work) のチェックも必要ありません.

*1 coinbase はいわゆる採掘報酬を意味します. Bitcoin では, 25 BTC からスタートし, 約4年ごとに半分になり,
2021年5月現在は 6.25 BTC です.ちなみに最後のブロックの発掘は 2140 年頃です.

下表に, 使用するクラス一覧とその説明を纏めました.

表1 クラスの仕様 (概要)

FileDescription
Block.javaブロックのデータ構造を格納するための Block クラス.
フィールドとして, ブロックのハッシュ値, 直前のブロックのハッシュ値,
トランザクションデータが含まれる.
BlockChain.javaブロックチェーンの管理を行うための BlockChain クラス.
フィールドとして, ブロックチェーン, 最大高さのブロックノード,
トランザクションプールが含まれる.
さらに, 内部クラスに BlockNode がある. そのフィールドとして, ブロック, 親ノード, 子ノード,
ブロックの高さ, ブロックの上に新ブロックを作成するための UTXO プールが含まれる.
BlockHandler.javaBlockChain クラス を使用して, 新しく受信したブロックの処理, 新しいブロックの作成,
または新しく受信したトランザクションの処理を行うための BlockHandler クラス.
ByteArrayWrapper.javaHashMap のキーとして使用できるように, バイト配列のラッパーを作成するための ByteArrayWrapper クラス. TransactionPool クラスを参照.
Crypto.java電子署名の有効性を確認する verifySignature() メソッドを含んだ Crypto クラス.
Transaction.javaScrooge Coin 取引の実装」の Transaction クラスと似ているが,
coinbase トランザクションを作成する機能を追加している.
coinbase トランザクションの作成方法は, Block クラスのコンストラクタで実装する.
TransactionPool.java新しいブロックを作成する際に必要なトランザクションプールを実装するための
TransactionPool クラス.
TxHandler.javaScrooge Coin 取引の実装」の TxHandler クラスに, getUTXOPool() メソッドを追加している.
UTXO.javaScrooge Coin 取引の実装」の UTXO クラスと同じ.
UTXOPool.javaScrooge Coin 取引の実装」の UTXOPool クラスと同じ.

ここでは, 次のように BlockChain クラスを作成します.
ただし, ここでは処理の流れを分かりやすく表現するために擬似コードで書きました.

public class BlockChain {

    private class BlockNode {
        
        Declares fields b, parent, children, height, uPool;
        
        public BlockNode(Block b, BlockNode parent, UTXOPool uPool) {
            Assign b to the b field of own instance;
            Assign parent to the parent field of own instance;
            Create a children instance;
            Assign uPool to the uPool field of own instance;
            
            if (!parent is null) {
                Assign parent.height + 1 to the height;
                Add own instance to the end of parent.children;
            } else {
                Assign 1 to the height;
            }

        }

        public UTXOPool getUTXOPoolCopy() {
            return new instance with the argument value uPool;
        }
    }

    Declares fields blockChain, maxHeightNode, txPool;
    
    Initializes the class constant CUT_OFF_AGE is 10;

    /** create an empty block chain with just a genesis block. Assume {@code genesisBlock} is a valid block */
    public BlockChain(Block genesisBlock) {    
        Create a blockChain instance;
        Create a utxoPool instance;
        Add a coinbase transaction to the UTXO pool;
        Initializes the field genesisNode with the argument values genesisBlock, null utxoPool;
        Store the pair of genesisBlock hash and genesisNode in the blockchain;
        Create a txPool instance;        
        Assign genesisNode to the maxHeightNode;
    }

    /** Get the maximum height block */
    public Block getMaxHeightBlock() {
        return the block of maxHeightNode;
    }

    /** Get the UTXOPool for mining a new block on top of max height block */
    public UTXOPool getMaxHeightUTXOPool() {
        return the UTXO pool of maxHeightNode;
    }

    /** Get the transaction pool to mine a new block */
    public TransactionPool getTransactionPool() {
        return the transaction pool;
    }

    /** Add {@code block} to the block chain if it is valid */
    /** Return true if block is successfully added */
    public boolean addBlock(Block block) {
        Initializes the prevBlockHash is getPrevBlockHash() of block;

        if (prevBlockHash is null)
            return false;

        Initializes the field parentBlockNode is BlockNode corresponding to the prevBlockHash of blockChain;

        if (parentBlockNode is null) {
            return false;
        }

        /** Transaction validity check */
        Initializes the field handler with the argument value UTXO pool of parentBlockNode;
        Initializes the field txs is the transaction of block;
        Initializes the field validTxs is the valid transaction set in txs;

        if (!validTxs.length is txs.length) {
            return false;
        }

        /** Block validity check*/
        Initializes the field proposedHeight is parentBlockNode.height + 1;         

        if (proposedHeight <= maxHeightNode.height - CUT_OFF_AGE) {
            return false;
        }

        Initializes the field utxoPool is the UTXO pool of handler;
        Add a coinbase transaction to the UTXO pool;
        Initializes the field node with the argument values block, parentBlockNode, utxoPool;
        Store the pair of block hash and node in the blockchain;

        if (proposedHeight > maxHeightNode.height) {
            Assign node to the maxHeightNode;
        }

        return true;
    }

    /** Add a transaction to the transaction pool */
    public void addTransaction(Transaction tx) {
        Add a tx to the transaction pool;
    }

}

Web Stock photos by Vecteezy

信頼からの合意形成アルゴリズムの実装

分散ネットワークシステムにおける合意形成の1つを実装してみました.
これは Princeton 大学の講義 “Bitcoin and Cryptocurrency Technologies” のプログラミング課題の1つです.

ノード間の「信頼」関係のグラフが与えられたときの, 分散型合意形成アルゴリズムを実装します.

これは, Sybil 攻撃に対抗し*1, 合意形成を得るための代替手段であり,
PoW のように膨大な電力を「浪費」しないという利点があります.

*1 Sybil (シビル) というのは, 解離性同一性障害を患った女性の名に由来します.
ブロックチェーン業界の用語では, 攻撃者が複数のノードを作ってネットワークを支配しようとする攻撃の事を言います.

まず, ネットワーク内のノードには, Compliant (善良) と Malicious (悪意) の2種類があるとします.
「信頼」とは, ネットワークが有向ランダムグラフで表され, 各エッジがノード間の信頼関係を表しているという意味です.
例えば, A → B のエッジがある場合, ノード B はノード A が伝搬したトランザクションをリッスンしていることを意味し,
B は A のフォロワーであり, A は B のフォロイーであると言います.
もちろん善良ノードと悪意のあるノードには信頼関係が成り立たちません.

図1 善良ノード間の信頼関係

ここで, 悪意のあるノードは, 例えば次のような動作をします:

  • 機能的に死んでいて, トランザクションを伝搬しない,
  • 独自のトランザクションを常に伝搬し, 与えられたトランザクションを決して受け入れない.

次に, 各ノードは, 同じコードを実行している他のノードをピアとするネットワークで合意形成を得ることに
成功しなければなりません.
異なるトランザクションの集合を受け取るノードのネットワークが, 受け入れるべき集合に合意できるように設計します.
また, 一定のシミュレーション回数が設定され, 各回にノードはフォロワーに提案を伝搬し,
全回数の終了時には合意すべき取引について合意に達している必要があります.

各ノードにはフォロイーのリストが与えられ, フォロイーにはフォロワーに伝搬できるトランザクションの
リスト (提案リスト) が与えられます.
ここで, 全てのトランザクションは有効であり, 無効なトランザクションは作成できないものとします.

最後にテストに関してですが, コードを実行しているノードが, 悪意のあるノードに遭遇する可能性があります (最大45%).
ノードは, 可能な限り多くの悪意のあるノードに耐え, かつ合意形成を得ることができなければなりません.

テストは次に基づいて評価されます:

  • どのくらいの規模のノードの集合が合意に達したか.
    全てのノードが同じトランザクションのリストを出力した場合にのみ合意に達したとカウントされる,
  • 合意に達した集合の大きさ (トランザクションの合意に達した集合を可能な限り大きくしたい).

下表に, 使用するクラス一覧とその説明を纏めました.

表1 クラスの仕様 (概要)

FileDescription
Node.javaCompliantNode クラス, MaliciousNode クラスのインターフェース.
フォロイーを設定する setFollowees() メソッド,
トランザクションの提案リストを初期化する setPendingTransaction() メソッド,
自分のフォロワーに送る提案リストを返す (return) sendToFollowers() メソッド,
他のノードからトランザクション候補を受信する receiveFromFllowees() メソッド
が含まれる.
CompliantNode.javaCompliantNode クラス. Node インターフェイスを実装したもの.
MaliciousNode.java悪意のあるノードのクラス. Node インターフェイスを実装したもの.
Candidate.javaノードが受け取るトランザクション候補を記述するためのクラス.
フィールドとして, 提案されているトランザクションの ID,
トランザクションを提案しているノードのインデックスが含まれる.
Simulation.java合意形成のテストをするためのクラス.
グラフを生成し, グラフのパラメータを変更してシミュレーションを行い,
CompliantNode クラスをテストすることが可能.
Transaction.javaトランザクションのクラス. フィールドとして, 一意の ID が含まれる.

Simulation.java の処理の概要を述べておきましょう:

  1. ノードたちを生成する. その中で, どれが悪意のあるノードで, どれが善良ノードかを選択する,
  2. 1 で生成したグラフを, ランダムグラフとして初期化する,
  3. 全てのノードにそれらのフォロー先 (フォロイー) を通知する,
  4. ランダムな ID で有効なトランザクションの集合 (例えば 500個のトランザクションを含む) を初期化する,
  5. 各ノードが聞いたトランザクションの開始状態を初期化するために, ノード全体にトランザクションを分散させる.
    配布はトランザクションとノードのペアごとに, 定めた確率でランダムに行う,
  6. 各ノードがフォロワーへ提案するトランザクションのリストを1つに纏める,
  7. 6 で纏めた提案リストを, 各ノードに配布する (伝搬させる),
  8. 6 と 7 を一定のシミュレーション回数だけ繰り返す.

以上を踏まえ, 実際にテストしてみた結果は次のようになりました:

Tests for this assignment involve your submitted miner competing with a number of different types of malicious miners

Running test with parameters: numNodes = 100, p_graph = 0.1, p_malicious = 0.3, p_txDistribution = 0.01, numRounds = 10
On average 44 out of 72 of nodes reach consensus

Running test with parameters: numNodes = 100, p_graph = 0.1, p_malicious = 0.3, p_txDistribution = 0.05, numRounds = 10
On average 61 out of 72 of nodes reach consensus

Running test with parameters: numNodes = 100, p_graph = 0.1, p_malicious = 0.45, p_txDistribution = 0.01, numRounds = 10
On average 33 out of 58 of nodes reach consensus

Running test with parameters: numNodes = 100, p_graph = 0.1, p_malicious = 0.45, p_txDistribution = 0.05, numRounds = 10
On average 42 out of 58 of nodes reach consensus

Running test with parameters: numNodes = 100, p_graph = 0.2, p_malicious = 0.3, p_txDistribution = 0.01, numRounds = 10
On average 69 out of 76 of nodes reach consensus

Running test with parameters: numNodes = 100, p_graph = 0.2, p_malicious = 0.3, p_txDistribution = 0.05, numRounds = 10
On average 74 out of 76 of nodes reach consensus

Running test with parameters: numNodes = 100, p_graph = 0.2, p_malicious = 0.45, p_txDistribution = 0.01, numRounds = 10
On average 41 out of 54 of nodes reach consensus

Running test with parameters: numNodes = 100, p_graph = 0.2, p_malicious = 0.45, p_txDistribution = 0.05, numRounds = 10
On average 49 out of 54 of nodes reach consensus

ここで, numNodes はノード数, p_graph はランダムグラフのパラメータでエッジが存在する確率, 
p_malicious はあるノードが悪意のあるノードとして設定される確率,
p_txDistribution は各ノードに初期トランザクションを割り当てる確率,
numRounds はノードが実行するシミュレーション回数です. 

Trust Stock photos by Vecteezy

Bitcoin における合意形成アルゴリズム Part 2

Bitcoin における合意形成アルゴリズム Part 1」の続きです.

ここでは, Bitcoin の合意形成アルゴリズムが実用的には上手く機能している理由について,
攻撃者 (悪意のあるノード) を想定しながら述べます.

Bitcoin のブロックチェーンでは, 悪意のあるマイナー含め, 各マイナーが自主的にチェーンを伸ばしていきます.
このとき, 必然的にチェーンの分岐が起こってしまいますが, その中の最長チェーンだけを有効なものとするという
ルールを定めています*1.
これにより, ブロックの有効性について, マイナーの多数決での合意形成が行われたことになります.

*1 もちろん2つの有効なブロックが同時に作成されても, チェーンに組み込まれるのはそれらのうちどちらか一方となります.
最終的にどちらのブロックが組み込まれるかは, 他のマイナーがどちらのブロックを選択するかによって決まります.

図1 Bitcoin ブロックチェーンの分岐と最長チェーン

不正なブロックを作成する攻撃者は, PoW により大量の計算コストをかけることになりますが,
最長チェーンに組み込まれる確率は非常に低く, さらに報酬を得ることもできません.
そのため, わざわざ高いコストを支払ってまで不正なブロックを作成しようとする動機にならず,
全てのノードがルールに従い続けようというインセンティブが働くのです.

攻撃者の負ける確率が非常に高いという数学的根拠は Bitcoin の原論文に記述があります:
Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, bitcoin.org, 2008.

まず P を善良ノードが次のブロックを見つける確率, Q を攻撃者が次のブロックを見つける確率,
Qz を攻撃者が z ブロックの遅れから追いつく確率とします.

ここで, P > Q と仮定すれば、Qz = (Q/P)z が成り立つため,
追いつく必要のあるブロック数の増加に伴い, 攻撃者が追いつく確率は指数関数的に下がっていきます.
一方, P ≦ Q と仮定すれば Qz = 1 が成り立ち, 攻撃者の勝利となります.

ここで, P ≦ Q のとき, つまり Q が 50% 以上というのは、
攻撃者が全体のハッシュレートのうち半分以上の割合を支配しているという意味で*2,
不正な合意形成が行われてしまいます. これは 51% 攻撃などと呼ばれています.
しかし, 現実的には 50% 以上のハッシュレートを確保するのは非常に高コストであるため,
難しいとされています.

*2 ハッシュレートとは, 1秒あたりに何回ハッシュ計算ができるかという単位 [H/s] です.
ハッシュパワーや採掘速度とも言います.

いま見たように, 51% 攻撃が行われなければ Bitcoin ブロックチェーンは安心, と誰もが信じたいところですが,
実はそれが覆される攻撃手法が存在するのです.
これは 利己的マイニング (selfish mining) と呼ばれる攻撃で, 2013年に Eyal と Sirer により提案されました:
Ittay Eyal, Emin Gun Sirer, Majority is not Enough: Bitcoin Mining is Vulnerable, 2013.

具体的には, 攻撃者はマイニングに成功してもそのブロックを公開せず,
数ブロック分を公開しないままマイニングを進め, ある時点でまとめて数ブロック分を公開することで,
最長チェーンを伸ばす競争を利己的に進めることができるというものです.

Q を攻撃者が次のブロックを見つける確率,
2つの公開 (分岐) チェーンがあったとき, Z を善良ノードが攻撃者のチェーン上にブロックを追加する確率とします.
このとき, Z = 1/2 ならば, Q > 1/4 で攻撃者は通常マイニングよりも利己的マイニングの方が儲かります.
さらに, Q > 1/3 ならば, 任意の Z に対して, 攻撃者は利己的マイニングの方が儲かることになります.

よって, ハッシュレートの 50% 以上を支配していないマイナーがいなければ安全と信じ込むのは危険です.

Network Stock photos by Vecteezy

Bitcoin における合意形成アルゴリズム Part 1

分散ネットワークシステムで合意形成 (コンセンサス) を得るためには, Byzantine 将軍問題があり,
全ノードのうち 1/3 以上が悪意のあるノードならば, 合意形成は不可能であることを
分散型合意形成と Byzantine 将軍問題で見ました.

Byzantine 将軍問題が発生しても, ネットワークが正しい値について合意できるという性質を
BFT (Byzantine Fault Tolerance, ビザンチン障害耐性) と言います.

Bitcoin のような分散型電子通貨システムを構築する上で解決すべき重要な技術的課題の1つは,
分散型合意形成を実現することですが, Bitcoin ブロックチェーンには BFT があるでしょうか.

結論から言うと, Bitcoin ブロックチェーンは Byzantine 将軍問題に対して,
理論的な解を与えていないが, 実用的な解を与えています.
これは従前のモデルにない条件があることで, 実用的には上手く機能しています.

その条件は2つあります.
1つ目は, インセンティブという概念です.
不正取引を防ぎブロックチェーンの維持に貢献した報酬として, ブロックを作成 (マイニング) したノード (マイナー) に
Bitcoin (ブロック作成報酬と取引手数料の合計) が与えられます*1.
Bitcoin が通貨であるため, 参加ノードが誠実に行動しようと思うインセンティブが働くのです.

*1 ブロックチェーンの維持に貢献したという意味は, PoW (Proof of Work, 作業をしたことの証明) という
大量の計算コストをかけた (ハッシュ計算をした) ということです.

2つ目は, 確率的な合意形成です. Bitcoin ブロックチェーンでは, 合意形成のための特定の出発点や終点の概念がありません.
その代わりに, 合意形成に長い時間をかけ, 実際の運用では1時間程度の時間をかけています*2.
しかし, それだけの時間をかけた後も, ノードは特定の取引やブロックがブロックチェーンに書き込まれたかどうかを
確実に知ることができません.
ただし, 時間が経つにつれて, 自分から見える形は最終的に合意が得られた形に一致していき,
2つの形が乖離する確率は指数関数的に下がります.

*2 ブロックが作成される間隔が約10分であるため, ブロックがブロックチェーンに組み込まれた後に,
6個のブロックが追加されればそのブロックは有効だろうと確信できるということです.
ここで, 6個という数に理論的な根拠はなく, あくまでも経験的な答えであることに注意しましょう.

Bitcoin ブロックチェーンが従来の分散型合意形成にかかる Byzantine 将軍問題を回避する上でのポイントは,
モデルのこのような違いです.
Byzantine 将軍問題を「解決」でなく「回避」というのは, 冒頭で申し上げた通り理論的には解が与えられていないからです.

実際、理論的に解が与えられたと言うためには, 合意が覆る可能性がゼロでなければなりませんが,
Bitcoin ブロックチェーンでは, PoW による合意はブロックが作成された時点では確定しておらず,
あくまでも時間の経過とともにその時点の合意が覆る確率がゼロへ収束する, 仕組みとなっています.

Bitcoin における合意形成アルゴリズム Part 2」に続きます.

Network Stock photos by Vecteezy