Truthcoin/Hivemind学習帳¶

by 宮本丈 ¶

Hivemindの勉強にあたってのメモです。

ほぼホワイトペーパーの抜粋です。

間違いがあったらごめんなさい。ご指摘大歓迎です。

このような引用文は宮本による注釈、メモを明示する際に記す。

Overview¶

Truthcoin（現在の名称はHivemind）はビットコインのサイドチェーン上に予測市場を作るプロジェクトである。

パブリックブロックチェーン上に予測市場を作るプロジェクトには他にGNOSISとAugurがあり、これらはいずれもBitcoinではなくEthereumのブロックチェーンを使用している。

分散予測市場においては「誰が答えの正しさを保証するのか」という点が問題だが、上の2つは（少なくともその一部を）ブロックチェーン外部のオラクルに頼る方針であるのに対し、Truthcoinでは全てブロックチェーン内で完結させる点に違いがある。

これは「外部オラクルはIncentive Compatibleではない」という作者の主張に基づいている。

どこまで現実的な主張であるかはまだ確信が持てない

そのため、TruthcoinではCashcoin(CSH)とVoteCoin(VTC)という2つのコインを使用する。

1. CSH¶

CSHはBitcoinと1:1で交換可能な通貨で、所持することによりTruthcoin特有の機能、例えばPredictoin Market(PM)の作成、PMのシェアの売買などを行えるようになる。

2. VTC¶

VTCは「評判」を表すもので、Truthcoin特有の発明である。評判を交換可能なものとすることで様々なメリットがある。

Sybil-attackに対する攻撃
所有権とコントロールのアラインメント ... 価値の追加、破棄はそのまま報酬とペナルティになる。(?)
活発に活動していないエージェントに対して罰則を与えることができる。
インセンティブの計算から、「時間」という次元を取り除く。したがって「全評判を犠牲にしてCSHを手に入れる」という破滅的現象(exit scam, GOX)を防止することができる。

Truthcoinはある種の「オラクルコーポレーション」であるサブセクションにわけられ、これを「ブランチ」と呼ぶ。それぞれのブランチは固有のVotecoinの集合を持ち、ブランチ内での保有VTCはブランチの収益の分配に使用される。

価値の保存という機能においては、VTCはBTC・CSHには劣る。というのも常に投票に参加し続けていないと原価していくためである。イメージとしては従業員IDに近い。

「投票トランザクション」と「移譲(送金)トランザクション」を分ける。投票と送金を同時に行うことができない（送金を行えるのは投票と投票の間のフェーズに限る）ことで、間違った投票をしつつ（VTCの価格が下がる前に）売り抜ける、ということができないようになっている。 SVDに対するスパムを防ぐため、全部で10000アドレスに限定

VTCの所有権は投票活動に応じて移行する¶

保有者が、投票をしなかったり多数派と同じ結果に一致しない投票をした場合、VTCは流出する。
投票者が少ない命題や、票が割れるようなDecisionに投票した場合、VTCを手に入れる。

マーケットの自動調整¶

流通速度を加味して物価を調整するという方法を用いる、具体的には添付のExcel fileを参照。

また、プロトコルは以下の役割を持つ。

LMSR Technologyを用いて、一定の流動性が担保されていることを保証する。
ブロックチェーンのプロパティを持ち、Cencership resistanceを担保する。
資本の流通や、マーケットの開示から閉鎖までをマネージする。

インセンティブ設計の基本方針¶

予測市場はDecision(投票対象)の提起とそれに付随するマーケットの設定により行われ、これを行うものをその市場のAuthorと呼ぶすべての予測市場は単一のブランチに属す。

1. Author¶

a. だれでも自由にあらゆるマーケットを作り、そのAuthorになることができる。 b. Authorは、アウトカムが特定の日付までに誰の目にも明らかな形で開示されるようなマーケットだけを作成するようなインセンティブを持つ。 c. Authorは、十分な流通量が見込める(異なる見解が社会に存在し、したがってPMを作るメリットが見込める)マーケットのみを作成するインセンティブがある。 d. マーケットの開示当初から高い流動性を持つことが見込めるものを作製するインセンティブがある。 e. トレーダーに自身が信用に値することを証明する必要がない(自動で証明される。 )。

2. VoteCoin保持者(「投票者」)¶

a. 投票者は、自身の所属するブランチ(サブマーケットのこと。例えば「スポーツ」「サイエンス」「政治」など)における、ネットワークの長期的信頼を保つインセンティブがある。 b. 投票者はすべての意思決定に投票するインセンティブがある。 c. 投票者は他の投票者が投票すると思われる内容に自分も投票するインセンティブがある。

3. トレーダー¶

通常の予測市場においてベッティングする人と全く同様。異なる点は

a. カウンターパーティリスク(胴元の不正、オッズ比の操作、マーケットの内容の検閲、など)がない b. 代わりにブロックチェーンとその運用プロトコルを信用しなくてはならない。

4. マイナー¶

a. ビットコインのサイドチェーンとして、merged miningを行うため、マイニングの限界費用はゼロである。したがってマイナーは常にブロックをマイニングする動機を持つ。ビットコインが消えた場合も、そのままTruthcoinのマイナーになれるため、マイニングをやめる動機にはならない。

Voteをする際のトランザクションはBallotと呼ばれる。

マーケットの流れ¶

投票対象となる命題をDecisionと呼び、以下の2種類がある。

バイナリ ... 例: 「2016年の大統領選挙はヒラリー・クリントンが勝利する」など。値は0, 0.5, 1。0.5はDecisionが曖昧である。観測不可能である。という場合に投票する。
スカラー ... 例: 「2018年終了時点でのニューヨーク証券取引所のダウ平均株価の値は？」。あらかじめ最小値と最大値を指定しておく。
カテゴリカル(因子型) ... 例: 「時刻Xにおける場所Yの天気は{晴れ、曇、雨、雪}である。」計算上はバイナリとして扱う。

また、マーケットは2次元以上のDecisionを持つことができる。例えば

投票対象	2016年のアメリカ大統領選挙は選挙はヒラリー・クリントンが勝利する	しない
2020年末のアメリカのGDPは2016年末よりも上
下

これにより、参加者の多様な信念を吸収することができる。これを多次元予測市場(Multidemensional Prediction Market)と呼び、Truthcoin独自の機能である。また、次元を「チェイン」させることで、任意のパラメトリックな確率分布を表現できるため、たとえばハザードモデルなどを使用した生存時間予測なども可能

こちらの補講に詳しい。

これらの機能を用いて複雑なマーケットを作成したとしても、投票時には独立に投票を受けるため(多分)、後述のSVDには影響しない

Decisionは大雑把に以下の流れをたどる

作成 -> トレード -> Ballotのハッシュを提出 -> 投票結果の開示 -> SVDとRBCR(以下参照) -> 再分配

いったんBallotのハッシュを提出させることで、おたがいの投票内容を独立させる(投票者が他人の投票内容を参考にするということがないことを保証する)ことができる。

以下はコードを用いた説明¶

import numpy as np
import scipy as sp
import pandas as pd

SVDとRBCR¶

SVD ... 投票行列から「各投票者の誠実さ」を抽出する。
RBCR ... 誠実さに基づいてコインを再分配する。

ここで投票者の誠実な振る舞いがIncentive Compatibleであるように保証している点が、Truthcoinの心臓部であると言える。かなりアクロバティックなことをしている。

ダミーデータの作成¶

# 初期値
# n*m vote matrix, 
N = 5 # number of voters
M = 6 # number of decisions
RV = np.linspace(0,1,num=N).reshape(N,1) # initial Reputation Vector for each Voter
print(RV)

[[ 0.  ]
 [ 0.25]
 [ 0.5 ]
 [ 0.75]
 [ 1.  ]]

d1 = np.random.binomial(1, 0.9, N) # Non-Contraversial Binary Decision
d2 = np.random.binomial(1, 0.55, N) # Contraversial Binary Decision 
# c3 = np.ndarray([np.NaN for i in c1 if np.random.random() < 0.1]) 
d3 = np.random.normal(200, 50, N) # Scalar Decision

# Contraversial Scalar Decision
d4_1 = np.random.normal(100, 20, N - 2)
d4_2 = np.random.normal(260, 40, 2)
d4 = np.append(d4_1, d4_2)

d5 = np.random.binomial(1, 0.9, N)
d6 = np.random.binomial(1, 0.55, N)


# Current Balance ... 現時点でのVTCの保有量、投票の「量」はこれに比例する。
CB = np.random.exponential(scale=1.0, size=N)

(5, 6)
[ 1.  1.  1.  1.  1.  1.]

VM = np.c_[d1, d2, d3, d4, d5, d6]

print(VM, "\n") # 正規化前
VM = (VM / np.max(VM.T, axis=1).T) # Scalar値でも、投票範囲が[0,1]になるよう正規化
print(VM)

[[   1.            0.          171.10985915   93.53984537    1.            1.        ]
 [   1.            1.          255.76681197   91.65815194    1.            0.        ]
 [   1.            0.          249.59841603  120.27508682    1.            1.        ]
 [   1.            0.          196.85612618  216.19506194    0.            0.        ]
 [   1.            1.          201.27566605  291.14515277    0.            0.        ]] 

[[ 1.          0.          0.66900728  0.32128251  1.          1.        ]
 [ 1.          1.          1.          0.31481943  1.          0.        ]
 [ 1.          0.          0.97588274  0.41311039  1.          1.        ]
 [ 1.          0.          0.76967033  0.74256796  0.          0.        ]
 [ 1.          1.          0.7869499   1.          0.          0.        ]]

Consensus Puzzle Piece 1: 特異値分解¶

$n*m$ の投票行列に対してSVDを行う。

行 ...それぞれの投票者
列 ... Decisions

これにより、投票者に協調させるようなインセンティブを与える仕組みをOperationalized Coordination by Singular Value Decomposition(特異値分解による操作的協調)と呼び、Truthcoinに特有の仕組みである。具体的には以下の手順で行う。

1. 欠損値の計算¶

特異値分解は欠損値を扱えないので、以下の手順で埋める。(Appendix 1を参照)

2.¶

協調を測るために、重み付きPCAの第一主成分(重みはその人の持つVTCの総量=Reputation Vector)を見る。この列はある投票者が架空の「代表的投票者」からどれだけ離れているかの指標になる。

VM_weighted = VM * CB[:, np.newaxis]

# since the demension of return value for `cov` function is adjusted to row.
if M > N:
    Gamma = np.cov(VM_weighted.T)
else:
    Gamma = np.cov(VM_weighted)

U, Sigma, V = np.linalg.svd(Gamma)

3. ノーマライズしたVote Matrixの取得¶

すべてのDecisionに関して平均が0になるようにする。

mu = np.ones([N, M]).dot(np.diag(VM.mean(axis=0)))

VM_normed = VM - mu

c = VM_normed.dot(U[:,0:1]) 

c

array([[ 0.43329078],
       [-0.25278416],
       [ 0.26171171],
       [ 0.12081105],
       [-0.56302938]])

その後、$c$にscalarを足し、最も外れた値がゼロになるようにする。これにより、最も他と異なる値を報告した投票者が強い罰則を受けるように保証する。最小の値を足す場合、最大の値を引く場合の二通りがある。(特異値分解に2通りの解があることに起因する)片方は「正解」ベクトルで、もう片方は「正解の反対」ベクトルである。まずは2通りで計算を行い、その後に選ぶ

# honesty vector
c_adj1 = abs(c - (np.ones([N, 1]) * ( min(c)) ) )
c_adj2 = abs(c - (np.ones([N, 1]) * ( max(c)) ) )

print(c_adj1, "\n",(c_adj1.T * CB).T)

[[ 0.99632016]
 [ 0.31024522]
 [ 0.82474109]
 [ 0.68384044]
 [ 0.        ]] 
 [[ 0.12118012]
 [ 0.15308603]
 [ 0.40190971]
 [ 0.18814661]
 [ 0.        ]]

このベクトルは、「最も逸脱した投票者からの距離」を表しているため、システムを攻撃したい主体は自身を二人の投票者に分けることで、最大の値を取得することができる。これは

集計結果を大きく変えるものではない
主体の持つ評判を下げる

ため、大きな問題となるものではないが、以下のような操作を行うことで、簡単に回避することができる。

def adjust(c):
    m = np.median((c.T * CB).T) # 重み付きmedian
    res = np.where(c <= m, c, c - (0.5 * m)) 
    return res
    
    
c_adj1_2 = adjust(c_adj1)
c_adj2_2 = adjust(c_adj2)

0.5倍しているのはより「逸脱していない側」に入るインセンティブを維持させるため。

「正解」のベクトルを選ぶ¶

先ほど後回しにした、「2つのベクトルの内どちらが正解のものか選ぶ」作業を行う。「絶対に正解とわかる」投票が複数あれば問題は解決するので、大きな問題ではない。(人が目で見ればすぐわかる)例えば以下の解決策が考えられる。

前回のReputationを用いて重みをつける。
PCAの因子得点(PCA-score)で重みをつける。

ここでは仮にc_adj1_2が選ばれたものとする。

選ばれたベクトルに重みをつける¶

$r_t$を前回のReputationベクトルとし、ここから新しいReputationベクトルを計算
重みをつけた後に合計が1になるようにする。

def stochastic_vectorize(x, axis=None):
    return np.abs(x) / np.abs(x).sum(axis=axis)

# update Reputation Vector
RV = stochastic_vectorize(c_adj1_2 * RV / RV.mean())

# 投票の判定
Outcome = stochastic_vectorize(RV.T.dot(VM))
print(Outcome)

[[ 0.28762655  0.00688805  0.25208128  0.16411658  0.14808779  0.14119974]]

Reputation Based Coin Redistribution(RBCR)¶

投票の結果に応じて、Branch内のVoteCoinを再分配する。

Ballotには公開鍵が含まれているので、再分配ごとに新しいアドレスを指定できる。

各アカウントについて、前回のReputationベクトルと新しいReputationベクトルの値でスムージングする。スムージングパラメータ$\alpha$を与える。例えば$\alpha = 0.20$の場合、前回までの評判の寄与率を0.8にする。これにより、継続して誠実な投票を行うインセンティブが生まれる。

RBCRを行うことで、投票者はCSH(つまりBTC)の形で収益を得られる。元となるのは

Authorがマーケット作成時に支払った手数料
トレーダーが支払ったトレーディング手数料

(手数料の詳細設定は後述)

悪意を持つ投票戦略の検討¶

連立耐戦略性¶

投票者が結託して誤った結果に投票すること(double-agent incentive)を防ぐため、Truthcoinでは投票者同士が互いに嘘をつくようなインセンティブを与える。(したがって投票者は「どこに投票しようとしているか」という情報の漏洩を防ごうとする) これをactive-coordinationと呼ぶ。

SVDでは、他と協調していない投票者をダイレクトに罰している。Decisionの結果を確認するための探索コストは十分低いので(おそらく投票者間で情報を公開するインセンティブが働くため)、また、曖昧すぎるDecisionには0.5を投票することができるので、SVDは常に「意図的な非協調性投票」だけを検知することができる

個人的に要検証

一度協調ゲームが成立してしまうと、常に正解票だけを投じ続けるのが投票者にとって最善の選択肢となる。
VoteCoin自体も自由市場で売買されるため、プロジェクトに参加する主体が意欲を失うことはない。
ビットコインに対する51%攻撃と同様、一人の投票者が多量のVTC(具体的には($1-\phi = $)35%になるように設定する。Appendix 3を参照)を取得することで結果を操作することは理論上可能ではある。しかし、ここでのミソは「一人」で持たなくてはならない、という点にある。なぜかというと誰がどれだけVTCを持っているのかわからない(義匿名性)」が成立しているため、複数の主体が協力しようとしても裏切るインセンティブが働くからである。また、一人で行った場合、そのブランチの「信用」すなわちマーケットキャピタルが大きく下がるため、成功しても得るものは少ない

Optional: 65%以下の一致しか見られなかった場合、「監査(Audit)」を起こすことができる。

公開監査の手順¶

a. まず、Ballotから代表的なものが5つ選ばれ、VTCではなくCSHによる投票が行われる。詳細は省くが、つまりこれはHivemindの全参加者による投票という意味なので、「Hivemind自体を潰したい」という動機を持つサードパーティ出ない限り、ここから利益を得ることはできない(上訴の仕組みに似ている)

集団的投票攻撃の非現実性ここでは65%のVTCを持つグループは投票の結果を自由に操作することができるが、実際には3つの理由からそのような不正は行われないことが確信できる。
1. Stake ... そのブランチのVTC/USDは一気に下がる。
2. Trust ... グループで攻撃を仕掛けようとすると、グループ内における囚人のジレンマが避けられない。
3. Coordination ... グループ内のメンバーは、「どのDecisionを攻撃すべきか」という点において異なる選好をもつため、協調することができない。

つまり攻撃者のグループは1. どのマーケットを攻撃するか 2. アウトカムはどのようにすべきかを予め決めなくてはならないが、これは攻撃者の一部が、そのDecisionにCSHを大量に賭けるインセンティブを与える。すると今度は他の攻撃者が「攻撃しない」インセンティブを獲得することになる。

8. 単独犯による集団投票攻撃(耐戦略性)¶

VTCの価格の低下というデメリットがあるとはいえ、原理上一度に大量の収益を得てドロンする(exit scam)ことができなくはない。そのような場合、最終的な決断はマイナーに委ねられ、攻撃を防ぐか、攻撃自体をなかったことにできる。(Appendices 3, 7,8参照)。したがって攻撃に成功しても利益はマイナスとなる。このようなマイナーによる罰則が抑止力として働くため、実際に不正を行うものはいないことが予想できる。また、マイナーが自体の不正は

BTCの価格自体が下落する
最後の権利としてのハードフォークは常に可能である。ということから、考えにくい(Bitcoinが安全な理由と同様)

この図がわかりやすい。攻撃者が利益を得るのは右上だけだが、マイナーによって封じられる。

Minerの活動¶

Drivechainの説明を見たほうがわかりやすい。

マイナーに「同じ機能をもつサイドチェーンを自由に作らせない」ようにサイドチェーンのプロトコルを作る。という点がミソ。

Authorの活動¶

マーケットの作成は2段階で行われる。これらは別々のAuthorによって行われてもよく、その場合それぞれDecision Author(DA), Market Author(MA)と呼ばれる。

1. Decisionの作成¶

Feeは定額とする。Feeの決め方はAppendix 4を参照

2. マーケットの追加¶

Nをマーケットが持つパラメータ(次元)の数とする大量のマーケット作成によるスパム防止のため、以下の2種類のFeeを設定する。

1. $b * log(N)$¶

bはAuthorが設定するマーケットの「流動性」パラメータで、Beta Amplificationと呼ばれる。別のNoteに詳しく書いた

これにはマーケット開始時の流動性の担保の役割がある。(「誰も最初に賭ける人物になりたがらない」という問題を防ぐ)

大勢のトレーダーが参加すると期待される場合には低いbを、少ないと期待される場合は大きいbを設定する。

2. $Fee_s * N^2$¶

これはパラメータが多すぎるマーケットに対する罰則のために存在する。著者いわく必須ではない。単に$N>256$をbanするだけでも十分機能する。

Decisionにスカラー値がある場合、投票結果が境界部分(最大、最小)出ない部分のみrefundすることで、適切な境界条件を設定するインセンティブがあるらしいが、この点はよくわからない。

Authorの収益¶

上記に加えてAuthorはトレーディング手数料(例えば0.1%)を設定できる。高すぎると(別の誰かMarketを作りなおすことで)作成時に投資したBondを失う可能性があるが、低すぎると収益が得られない。

全手数料の内50%は投票者の、25%はDAとMAの収益となる。

したがってAuthorは起業家のような性質を持つと言える。

トレーダーの活動¶

ビットコインと予測市場の大まかな仕組みを知っていれば奇妙なところはないので省略。

先述のコスト関数(LMSR)の計算などはAutomated Market Makerが行う。これはフルノードを保持したサービスで、EthereumにおいてEVMが走るノードと似たようなものだと思えば良い。計算はブロックチェーンの内容から決定論的に導出できるので、ユーザーがこのサービスを信用できない場合は自分でノードを持つことができる。したがってマーケットの状態について嘘をつくことができない。

「ブランチ」のライフサイクル¶

Truthcoin内におけるブランチは投票者の分割のために働く。例えば、ある投票者は政治的なことに興味が有り、その事実判定は喜んで行うかもしれないが、スポーツの結果については興味がないということがあり得るかもしれない。

そこで、ビットコインにおけるフォークのように、ブランチをフォークさせることができる。パブリックブロックチェーン上でのフォークの場合、いずれが正当なチェーンであるかの合意が取れないといった問題やダブルスペンドなどの望ましくない性質があるが、VTCの場合、収入は長期的なものでトレーダーの流通量に依存するので大きな問題はない。

したがって(ブロックチェーンそのもののフォークとは別に)ブランチをフォークさせてVTCの量を倍にすることができる仕組みをとる。

とはいえブランチ作成の限界費用が0というのはスパミングなどの観点から望ましくないので、ブランチの作成権は、フォーク元のVTCの所有者に委ねられる。

ブランチの死¶

3回の投票期間にわたってAuthorが現れなかった場合、ブランチは自動消滅する。

課題¶

Confirmation Timeの短縮¶

ビットコインの10分に一ブロックというのでも十分動作はするが、トレーダー間の競争を健全なものにするには出来る限りブロックインターバルを小さくしたほうが良い。GHOSTなどの実装が待たれる。

また、予測市場における売買はその順番によって利益が変わるため、一般に売買の履歴が一意に定まることを前提としている。

したがって

ブロックサイズを十分小さくして同じMarketに対する売買が一ブロックにつき1トランザクションしかないことを保証する。
大きなブロック内で売買の順序が一意に保証される機構を導入する。

のいずれかを用いる方法がある。しかしこれは他人のトランザクションを見てから、同じ内容を先にブロックチェーンに含ませることで利益を得る（Front-Running）問題を引き起こす。これは考慮すべき変数が多すぎてどれだけ実際に問題になるかはわからないが、他人のトランザクションが「良い」取引であるかどうかを確認するのが難しいので、大きな問題にならない可能性もある。

Beta Amplification¶

AugurのようにLS-LMSRのような仕組みを使うかの検討

マーケット開始時に$b_1$から$b_2$へ流動性パラメータを変更する場合、追加コストは$(b_2 - b_1) * log(N)$となる、過去のテストから、これはトレーディング開始後に行ってもトレーダーへの不利益はないことが判明している。 したがって、「取引はしたくないが真実を知りたい」という人がマーケットに寄付を行うことで流動性を高めることは十分に可能である。

LS-LMSRの問題点¶

すべてのトレーダーに少しずつ課金して流動性を確保するため、はじめに参画したトレーダーよりも後に参加したトレーダーを有利にする点にある。基本的に、早く市場に参入することにはメリットがなくてはならない。なぜかというと、その後市場が大きくなりバズれば、情報を手に入れるコストは下がり、正しい内容に賭けるのが楽になるため、リスクが少ないからである。

メリット¶

トレーダーが課金の対象となることは見た目ほど悪いことではない。なぜかというと、トレーダーは売ることも可能で、その際にovercompensatedになるためだ。課金額は中心(2証券市場の場合、各50%の状態)に最大となり、端で0に近づく
早く参加したトレーダーが低い流動性に苦しむことになる問題を解消できる。
特に興味深いメリットは、マーケットAuthorに、すでに存在するマーケットのコピーをしないインセンティブを与える点にある。
したがって、マーケット作成者の起業家精神を刺激する。

と、メリットのほうが多いので、後々は多分LS-LMSRになる。

連続値（スカラー）のDecisionを認めることに伴う問題¶

まず、マーケット作成時には絶対に上限と下限を設定する必要がある。なぜかというとそうしなければトレードもSVDも不可能であるため。

下限を非負にすると、望ましくないレバレッジをもたらす¶

よくわからんが、そうらしい。

さらに、Decisionの幅を変更するとさらに面倒になる。仮にTechnical Minimumを0に設定すると、使用されない流動性を置くことになり、LMSRまたはLS-LMSRの利点を損なうことになる。