# self-cleaning trusted third party

## 概要
trusted third partyを用いると、hash powerやcryptoなどお金で大量に買えるものではなく、人間や物理的デバイスなど容易に増やすことのできないもので、oracleの投票などにおいてvote powerを重み付けすることができる。しかし、従来のtrusted third partyはそのvote powerを容易に偽ることができ(ex:存在しない人間を登録する)、簡単に51%攻撃を仕掛けることが可能だ。そこで、**trusted third partyの構成員の任命・罷免をそれ自身が授けたvote powerによる投票で決定し、不正をしたtrusted third partyの構成員は罷免されるような自浄作用を導入する。**

## 定義
- TTP: vote powerを与えるtrusted third party。
- honest voter: 想定される通りに投票する善良な投票者。
- malicious voter: 想定された通りに投票せず悪意のある投票者。
- N: 初期状態でのvote powerの総和。
- p: 初期状態でのhonest voterの持つvote powerの割合。
- q: 初期状態でのmalicious voterの持つvote powerの割合。
- r: Nに対する、TTPが1日あたりに新しく追加できるvote powerの割合。
- S(n): n日目にmalicious voterの持つvote power。(1日目は$qN$)
- P(n): n日目での全体に対するmalicious voterの持つvote powerの割合。

## 前提
- ここで扱う投票テーマは、「チェーンに書き込まれたhashが指定されたデータのものか」など明らかな正解が存在するものである。
- TTPがvote powerを削減することは考えない。(=TTPの攻撃はmalicious voterのvote powerの増加のみ)
- $0<p<1,0<q<1,0<r<1$, $p+q=1$
- n=1(1日目)は初期状態。

## 仮定
- pはqよりも十分に大きい。
- rは一定で、TTPは毎日$rN$のvote powerをmalicious voterに与える。
- (malicious TTPを罷免する) $\Rightarrow P(n)>\frac{1}{2}$　逆は成り立たないので、$P(n)>\frac{1}{2}$のうちにTTPがmaliciousであると検知できなければならない。

## 考察
$$S(n)=qN+rN(n-1)=(q+rn-r)N$$
よって、
$$P(n)=\frac{S(n)}{pN+S(n)}=\frac{q+rn-r}{p+q+rn-r}$$
これが50%を超える時、
$$P(n)>\frac{1}{2}$$
$$\Leftrightarrow \frac{q+rn-r}{p+q+rn-r}>\frac{1}{2}$$
$$\Leftrightarrow 2(q+rn-r)>p+q+rn-r$$
$$\Leftrightarrow rn > p-q+r$$
$$\Leftrightarrow n>\frac{p-q}{r}+1$$
よって、$p<q$のとき$\frac{p-q}{r}<0$なので、honest voterがmalicious TTPを罷免することは不可能。
逆に、$p \ge q$の場合、honest voterがmalicious TTPを罷免することのできる猶予が少なくとも1日以上ある。このn日目までの期間に十分な確率でhonest voterがmalicious TTPを罷免できるならば、malicious TTP・malicious voterは51%攻撃できないといえる。**このような、honest voterのvote powerがmalicious voterのvote powerより大きいかつ、その状態が維持される期間中にTTPを罷免できる時、そのvote powerを限定的に追加する権限を持つTTPがmaliciousであっても51%攻撃を仕掛けられない性質を、逆転攻撃耐性(reversal attack tolerance)と呼ぶ。**

## 計算例
以下のグラフは、qを横軸、$n=\frac{p-q}{r}+1$を縦軸にしたものである。(ただし、nの単位は「日」。)

逆にq=0.33の時、rとnの関係は以下のようになる。

maliciousなTTPを検知・罷免するのに十分なほどnを大きくしようとすると、rは0.01 ~ 0.03(1% ~ 3%)当たりにするのが妥当だと考えられる。