サイトへ戻る

TumbleBit論文輪読会資料を公開

2017年2月7日にユナイテッド・ビットコイナーズ株式会社のブログに載せたものを移動しました。

今井です。

今回は以下ボストン大学(preprint当時)から2016年に提出された論文TumbleBitを説明します。

puzzle-promiseプロトコルとpuzzle-solverプロトコルの詳細はあとで追加になるかもしれません。

論文情報

  • Title: TumbleBit: An Untrusted Bitcoin-Compatible Anonymous Payment Hub
  • Author: Ethan Heilman, Leen AlShenibr, Foteini Baldimtsi, Alessandra Scafuro and Sharon Goldberg
  • Year: 2016
  • URL: https://eprint.iacr.org/2016/575

Bitcoinの問題点

Bitcoinにおける一つの問題点として、以下が挙げられます。

  • 秒間に処理できるトランザクション数が多くても7つ程度で少ない
  • トランザクションの増加に従ってブロックチェーンが線形で肥大化していってしまう

一つ目は、1ブロックのサイズが1MBまでということが起因しています。

ブロックが承認される平均時間(ブロックタイム)がBitcoinでは10分です。この中にいくつのTX(トランザクション)が入るでしょうか。

broken image

Blockchain.infoを見てみると、最近だとだいたい1800TX/ブロックのようです。なので、現実的には平均して3TX/秒程度です。

また、ブロックチェーンサイズは現在100GBを超えており、どんどん肥大化していっていることがわかります。

broken image

また、もっと長期でブロックチェーンサイズをみると、TX数の増加に従って増えていっていることがわかります。

broken image

上記を解決する方法はいくつか考えられています。

  • Lightning Network
  • TumbleBit
  • Sidechain

また、Bitcoin P2Pネットワークが処理できるTX数をさらに増やすために以下のようなことも考えられています。

  • Segregated Witness(Segwit) TXの構造を整理し、TXの一部をブロックサイズにカウントされない部分に置くことで、1ブロックのサイズを変えずに処理できるTX数を増やす、現在Bitcoinメインネットでのアクティベーション中
  • Block Size Limit 1ブロックのデータサイズを増やすことで、処理できるTX数を増やす

Lightning NetworkとTumbleBitともにオフチェーンを使って行います。「オフチェーン」というのは、ブロックチェーン外でのTXを使うと言う意味です。

通常だと誰かにbitcoinを送るには、TXを作成しそれをBitcoin P2Pネットワークにブロードキャストし、TXを承認してもらうためマイナーにTXをブロックチェーンに取り込んでもらう必要があります。

しかし、TXを1回承認してもらうには平均して10分待たなければいけません。場合によっては、もっと短い時もありますがもっと長い時もあります。これが、秒間TX数が限定される一つの原因なのですが、最初の状態と最後の状態だけをブロックチェーンに取り込んでもらい、途中はブロックチェーンに取り込まれないようにする(オフチェーン)ことで、処理を高速化することができます。

TumbleBitは現在のBitcoinプロトコルを変えることなく問題点を解決できるという点で興味深いものです。

Lightning Networkは現在Bitcoinテストネットでしか稼動できません。Bitcoinメインネットでは上記のSegwitが有効化されていないためです。Segwitは秒間TX処理数の問題解決策ではありますが、それ以外にTX malleability(トランザクション展性)を解決する方法の一つでもあります。

TX malleabilityとは、Bitcoin P2Pネットワークにブロードキャストしてからブロックチェーンに取り込まれるまでの間にTX idを変えることができてしまう性質のことです。idなので変わらないように作っておくはずなのですが、現在は変えることができてしまいます。

Lightning NetworkとTumbleBitは両方ともオフチェーンを使うのですが、Lightning Networkではブロードキャストする前にTXの連鎖を作る必要があり、TX idが途中で変わってしまうとLightning Networkは稼動できません。

TumbleBitの概要

TumbleBitの特徴は、オフチェーンペイメントを使ってブロックチェーンの肥大化を抑え高速な処理を実現しつつ、他の多くの解決策と異なり現在のBitcoin プロトコルに何の変更も加えずに実装できるという点です。 また、Tumbler という中間者の媒介を必要としながらも匿名性があり、またTumblerを信用する必要すらないということも特徴となっています。

broken image

大きく分けて、手順は以下の3つのフェイズに分けられます。

  1. エスクローフェイズ(オンチェーン)
  2. ペイメントフェイズ(オフチェーン)
  3. キャッシュアウトフェイズ(オンチェーン)

エスクローフェイズ(オンチェーン)

  1. AliceとBobの間で、Tumblerを使って支払いをすることに合意する。
  2. BobがTumblerにペイメントチャンネルの開設を依頼する。この後、BobとTumbler間の2-of-2エスクローTX(3BTC)をブロックチェーンにポストする。このTXのアウトプットは時刻tw2以降Tumblerだけでロックを解除できるようになっている。
  3. AliceがTumblerにペイメントチャンネルの開設を依頼する。この後、AliceとTumbler間の2-of-2エスクローTX(3BTC)をブロックチェーンにポストする。このTXのアウトプットは時刻tw1以降Aliceだけでロックを解除できるようになっている。
  4. BobはTumblerからパズルzをもらう。このパズルを解かないと、BobはキャッシュアウトのTXをブロードキャストできない。(puzzle-promiseプロトコルという)

ペイメントフェイズ(オフチェーン)

  1. AliceはBobに準備が整ったことを伝える。
  2. BobはTumblerからもらったパズルzにブラインドファクターをつけて変換(z)し、zではなくzをAliceに送る。
  3. AliceはTumblerにパズルzの答えεを見つけてもらうように依頼する。Tumblerは解き方を知っているため、Aliceにパズルzの答えεを伝える。このとき、Aliceは答えεが正しいことを確認した上で1BTCをTumblerに送る。(puzzle-solverプロトコルという)
  4. AliceはBobにパズルの答えεを伝える。

キャッシュアウトフェイズ(オンチェーン)

  1. BobはAliceからもらったパズルzの答えεから逆変換をしてパズルzの答えεを得る。
  2. Bobは答えεを使って、キャッシュアウトTXをブロードキャストしTumblerからの支払い(1BTC)を得る。

TumbleBit手順でのポイント

  1. TumblerはAliceとBobの仲介をしているが、直接つなぎ合わせているわけではない。
  2. BobがAliceに変換されたパズルzを送るため、TumblerがAliceとBobをつなぎ合わせにくい。
  3. AliceとTumbler間、TumblerとBob間のオフチェーンTXはマイクロペイメントチャンネルを使うため、ここでいくらやりとりしてもTX手数料はかからず、また秒間TX処理数を多くできる。
  4. マイクロペイメントチャンネルで送る金額をどのユーザでも全て同じ(1BTC)にすることで、金額を使ってのAliceとBobの紐付けもできない。

マイクロペイメントチャンネル

ある二者間の一方向支払いに限られるが、オフチェーンを使うことでTX手数料を使うことなく、処理時間を短くしつつ少額支払いをする方法

一度TumbleBitの説明から外れて、AliceとBob間でのマイクロペイメントチャンネルを説明します。

broken image
broken image
broken image
broken image
broken image
broken image
broken image

でも、さきほど説明したTumbleBit手順にはいくつか問題点がある

  1. BobはTumblerからパズルzをもらう。このパズルを解いたら、必ずTumblerはお金を払ってくれるのでしょうか?
  2. TumblerはAliceからお金をもらって、Bobに送らないということはできない?
  3. AliceはTumblerからパズルzの答えεをもらう。この答えがパズルzの答えじゃないのにAliceがお金を払ってしまうことはない?逆に、Tumlerは正しい答えεを教えたのに、Aliceがお金を払わなかったら?

論文にはこれに対する解決策が示されている。

論文で示されている方法を説明する前に、簡単化した例を先に説明します。

こんなことを考えてみます。

Aliceがパズルを解きたがっている。

Bobが答え(数字)がわかったよとAliceに話しかけた。

AliceはBobの答えが本当にパズルを解けるのなら、答えと引き換えにお金を払ってもいいよと答えた。

でも、Bobが答えを話してしまったら、お金をもらう前にAliceに答えが渡ってしまう。

Aliceが答えを得た後に必ずBobにお金を払うという保証はない。

 

Aliceは、どうやったらBobが正しい答えを持っていることをお金の支払い前に確認し、正しい答えを得ると同時にお金を払うことができるだろうか。

図で説明します。

broken image

C付きTXのLocking script(スマートコントラクト)を例えば以下にして、Aliceはブロードキャストします。(これはあくまでも例で実際に使うにはもう少し細工が必要です)

OP_SHA256
<C> OP_EQUAL
OP_IF
<Bob Pubkey>
OP_ELSE
<block_height+100> OP_CHECKLOCKTIMEVERIFY OP_DROP
<Alice Pubkey>
OP_ENDIF
OP_CHECKSIG

C付きTXを使うとき、Unlocking scriptとしてBobは以下を使います。

<Bob Sig>

<K>

Bobは、普通にKをAliceに送ったらいいと考えるかもしれませんが、その場合、Aliceが裏切りBobにお金を送ってくれない可能性があります。

もしBobが間違ったKを使った場合、block_height + 100だけ経ったあとでお金がAliceに戻ってきます。

Aliceが間違ったCを使った場合、BobはまだAliceに渡していないKからそれが間違いであることが事前にわかるので、AliceにTXを再送するように要求できます。

Proofの部分をTumbleBitではどうやっているのか

これは、puzzle-solverプロトコル、puzzle-promiseプロトコルに深く関係するところです。

まずは、puzzle-solverプロトコルです。

broken image

つぎに、puzzle-promiseプロトコルです。

broken image

さきほどのTimbleBit手続きでは書きませんでしたが、Bobがお金を得るために実際に必要なのはσ(キャッシュアウトTXのTumbler側署名)で、パズルzと一緒にTumblerから得たプロミス Cを、答えεを共通鍵として使って復号するとσが手に入ります。

他の問題点は?

  1. あるTumblerを使う人が少ない場合、紐付けができてしまう。
  2. 完全な人の特定はできないが、Tumblerを使っている人のいずれかであるというのはわかる