# HG changeset patch # User akahori # Date 1542204277 -32400 # Node ID 99d809a93f6cc008e0851a4313ce3aa7877e5260 # Parent d8977c76fff396a17c68c2a390c741a24ddb7bf8 complete midterm diff -r d8977c76fff3 -r 99d809a93f6c midterm/midterm.pdf Binary file midterm/midterm.pdf has changed diff -r d8977c76fff3 -r 99d809a93f6c midterm/midterm.tex --- a/midterm/midterm.tex Tue Nov 13 23:07:24 2018 +0900 +++ b/midterm/midterm.tex Wed Nov 14 23:04:37 2018 +0900 @@ -5,6 +5,7 @@ \usepackage{url} \usepackage{bussproofs} \usepackage{listings,jlisting} +\usepackage{cite} \lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{./images/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿} \rhead{} \cfoot{} @@ -61,9 +62,25 @@ %% 整合性保持のproof of workでは, OSのcpu使用率に応じて, ファイルの同期が早くなるようにする. \section{ブロックチェーン} -ブロックチェーンとは分散型台帳技術とも呼ばれ, 複数のトランザクションをまとめたブロックをつなげたものを, システムに参加しているすべてのノードが参照できる技術である. ブロックチェーンはデータの追跡, 検証が容易であり, 中央管理者が存在しないと言うメリットがある. +ブロックチェーンとは分散型台帳技術とも呼ばれ, 複数のトランザクションをまとめたブロックをつなげたものを, システムに参加しているすべてのノードが参照できる技術である. +ブロックチェーンを実装することは次のようなメリットが有る. + +\begin{itemize} +\item データの追跡, 検証が容易である. +\item 中央管理者が存在しない. 単一障害点がない. +\end{itemize} + +データの追跡, 検証が容易であるのは, ブロックの構造によるものである. ブロックの構造は簡易化すれば次のようなものである. -ブロックの中身は前のブロックの暗号化ハッシュ, タイムスタンプなどのメタデータと, 複数のトランザクションが入っている. ブロックは前のブロックと暗号化ハッシュでつながっており, 現在のブロックのハッシュは前のブロックのハッシュに依存して作られる. そのため, もしブロックを改ざんしたいとしたら, そのブロックにつながるすべてのブロックを改ざんしなければならない. しかし, その仕組みだけならば複数のブロックのハッシュを同時に改ざんすることで, データが改ざんされてしまう可能性がある. そのため, ブロックに付け加える場合にはある作業を行わせ, それによってある条件に収まるHashを作らせる. 例えば, ビットコインだとProof of Workという計算問題を解かせ, Hashを生成する. これは単純にはソースコード\ref{code:proof of work}のような問題を解くのと同義である. +\begin{itemize} +\item 前のブロックの暗号化ハッシュ. +\item タイムスタンプ. +\item nonce +\item トランザクションリスト. +\end{itemize} + +ブロックは前のブロックと暗号化ハッシュでつながっている. ブロックの中のパラメータをつなげてハッシュ化しているため, 現在のブロックのハッシュは前のブロックのハッシュに依存して作られる. そのため, もしブロックを改ざんしたいとしたら, そのブロックにつながるすべてのブロックを改ざんしなければならない. +その仕組みだけならば複数のブロックのハッシュを同時に改ざんすることで, データが改ざんされてしまう可能性がある. しかし, ブロックに付け加える場合にはある作業を行わせ, それによってある条件に収まるHashを作らせることで, この可能性を少なくしている. 例えば, ビットコインだとProof of Workという計算問題を解かせ, Hashを生成する. これは単純にはソースコード\ref{code:proof of work}のような問題を解くのと同義である. \begin{lstlisting}[caption="Proof of Workを単純にしたコード", label={code:proof of work}] while(1){ @@ -78,9 +95,7 @@ \end{lstlisting} -実際には $0 < rand() < 10000$はもっと大きな値であり, またこれは複数ノードでの分散環境下で計算される. もし, 条件に合うブロックのハッシュが生成できたならば, 他のノードによってそのハッシュが実際に生成されるかどうかを調べる. この仕組みにより, 改ざんを起きにくくしている. - -このような, 計算量の多くするコンセンサスアルゴリズムを用いることで, 中央管理者が存在しないにもかかわらずにデータの整合性保持が行われる. +実際には $0 < rand() < 10000$はもっと大きな値であり, またこれは複数ノードでの分散環境下で計算される. もし, 条件に合うブロックのハッシュが生成できたならば, 他のノードによってそのハッシュが実際に生成されるかどうかを調べる. これを検証するのは, ハッシュが条件に収まっているか否かを判定するだけで良いので容易である. しかし, 新しい条件に収まるHashは簡単には求まらない. しかも, 1つを改ざんすればそれに連なるブロックすべてのHashが変わるため, これら全部を書き換える計算量は膨大なものになる. この仕組みにより, 改ざんを起きにくくしている. トランザクションの中身はデータ, 前のトランザクションと後ろのトランザクションのハッシュ, 暗号鍵でのトランザクションの署名となっている. 署名により, 誰のトランザクションかが簡単にわかる. @@ -88,30 +103,39 @@ 通信はp2pで行われ, トランザクションやブロックが来た場合, ノードはそれらが正当なものかをルールに従って検証する. そしてトランザクション, ブロックが承認された場合, 他のノードにそのトランザクション, もしくはブロックを送り, 承認されなかった場合は破棄する. これによって, 承認されたものだけがネットワーク上に伝搬されていく. - + このような複数の仕組みによって, 中央管理者を必要とせずにデータの整合性保持が行われる.. \section{Christie} -Christieは当研究室で開発している分散フレームワークである. ChristieはJavaで書かれているが, 当研究室で開発しているGearsOSに組み込まれる予定がある. そのため, GearsOSを構成する言語Continuation based Cと似たCodeGear(以下CG)とDataGear(以下DG)という概念がある. CGはメソッドであり, DGは変数データに相当する. また, ChristieにはCodeGearManager(以下CGM)とDataGearManager(以下DGM)という概念もある. CGMはノードに当たり, DGM, CG, DGを管理する. DGMはDGを管理するものであり, putという操作により変数データ, つまりDGを格納できる. +Christieは当研究室で開発している分散フレームワークである. ChristieはJavaで書かれているが, 当研究室で開発しているGearsOSに組み込まれる予定がある. そのため, GearsOSを構成する言語Continuation based Cと似た概念がある. Christieに存在する概念として次のようなものがある. -DGMにはLocalとRemoteと2つの種類があり, Localであれば, DGMを管理しているCGMにDGを格納していき, Remoteであれば接続したRemote先のCGMにDGを格納できる. DGを取り出す際にはアノテーションを付けることで, データの取り出し方も指定できる. Take, Peekという操作があり, Takeは読み込んだDGが消えるが, PeekはDGを消さずにそのまま残す. +\begin{itemize} +\item CodeGear(以下CG) +\item DataGear(以下DG) +\item CodeGearManager(以下CGM) +\item DataGearManager(以下DGM) +\end{itemize} -CGはCGMによって実行されるが, 実行するにはDGが全て揃う必要がある. もしDGが全て揃わない場合, CGMはずっとlistenし, データが揃うまで実行を待つ. +CGはクラスに相当し, DGは変数データに相当する. CGMはノードであり, DGM, CG, DGを管理する. DGMはDGを管理するものであり, putという操作により変数データ, つまりDGを格納できる. + +DGMにはLocalとRemoteと2つの種類があり, Localであれば, LocalのCGMが管理しているDGMに対し, DGを格納していく. Remoteであれば接続したRemote先のCGMのDGMにDGを格納できる. DGを取り出す際にはアノテーションを付けることで, データの取り出し方も指定できる. Take, Peekという操作があり, Takeは読み込んだDGが消えるが, PeekはDGを消さずにそのまま残す. また, RemoteTake, RemotePeekというものもあり, リモート先を指定することにより, RemoteDGMからデータを取ることができる. + +CGはCGMによって実行されるが, 実行するにはCGに必要なDGが全て揃う必要がある. もしDGが全て揃わない場合, CGMはずっとlistenし, データが揃うまで実行を待つ. \section{やったこと} 中間予稿までにやったこととして, コンセンサスアルゴリズムPaxosの論文を読み, ChristieにTopologyManagerという機能を実装した. -Paxosを読んだ理由は, コンセンサスアルゴリズムの調査である. 実際, Paxosもビットコインで使用される候補に上がったコンセンサスアルゴリズムである. 分散システムはどのようなコンセンサスアルゴリズムを用いているかで性能が変わる. ビットコインのコンセンサスアルゴリズムProof of Workは, 計算量を多くして改ざんを起こりにくくしているが無駄が多く, 10分以内で解かれないように動的に条件を変更している. これは先ほどの, 同時にブロックを変更するのを防ぐため, つまり信頼性を上げるためであるが, 速度面で大きな課題となる. 分散ファイルシステムを構成するにはスケーラビリティが課題であり, ノードの数が多くなればなるほど通信時間がかかる. そのため, コンセンサスリズムとして有名なPaxosの論文を読んだ. +Paxosを読んだ理由は, コンセンサスアルゴリズムの調査である. 実際, Paxosもビットコインで使用される候補に上がったコンセンサスアルゴリズムである. 分散システムはどのようなコンセンサスアルゴリズムを用いているかで性能が変わる. 例えばビットコインのコンセンサスアルゴリズムProof of Workは, 計算量を多くして改ざんを起こりにくくしているが無駄が多く, 10分以内で解かれないように動的に条件を変更している. これは先ほどの, 同時にブロックを変更するのを防ぐため, つまり信頼性を上げるためであるが, 速度面で大きな課題となる. 分散ファイルシステムを構成するにはスケーラビリティが課題であり, ノードの数が多くなればなるほど通信時間がかかる. そのため, コンセンサスリズムとして有名なPaxosの論文を読んだ. ChristieにTopologyManagerを実装した理由は, Christieのコードに慣れるため, そしてTopologyManager上に分散システムを実装するのが容易になるからである. TopologyManagerとは, ノードにTopologyを構成させ, ノードごとにどこのノードにつながればいいかを指定する機能である. Christieでは静的, 動的なトポロジー管理ができる. 静的ではdotファイルというものにノードごとの関係を記述する. 動的ではノードの木構造を作る. + また, ブロックチェーンについては実際にブロックを実装し, 簡易的ではあるがProof of Workを動かして理解を深めた. 分散環境の実装はこれから行う. \section{これからやること} -ブロックチェーンのトランザクション部分と分散環境を実装していく. コンセンサスアルゴリズムも調査していき, Proof of Work以外のコンセンサスアルゴリズムを探していく. そして, 実際に分散環境下においてブロックチェーンが動くか検証していく. - +ブロックチェーンのトランザクション部分と分散環境を実装する. そして, 実際に分散環境下においてブロックチェーンを動かし, データの整合性保持, 追跡が行えるかを確認していく. コンセンサスアルゴリズムも調査していき, ファイルシステムに組み込めるコンセンサスアルゴリズムを探していきたい. \nocite{*} \bibliographystyle{junsrt} diff -r d8977c76fff3 -r 99d809a93f6c midterm/reference.bib --- a/midterm/reference.bib Tue Nov 13 23:07:24 2018 +0900 +++ b/midterm/reference.bib Wed Nov 14 23:04:37 2018 +0900 @@ -1,33 +1,60 @@ -@Misc{Yasutaka:2016, - author = "{比嘉 健太, 河野 真治}", - title = "{メタ計算を用いた Continuation based C の検証手法}", - journal = "琉球大学工学部情報工学科平成 28 年度学位論文", - year = 2016 -} +%% This BibTeX bibliography file was created using BibDesk. +%% http://bibdesk.sourceforge.net/ -@Misc{Tatsuki:2016, - author = "{伊波 立樹, 東恩納 琢偉, 河野 真治}", - title = "{Code Gear 、Data Gear に基づく OS のプロトタイプ}", - journal = "{情報処理学会システムソフトウェアとオペレーティングシステム研究会}", - year = 2016 -} +%% Created for 赤堀　貴一 at 2018-11-14 23:03:28 +0900 + -@Misc{kaito:2015, - author = "{徳森 海斗, 河野 真治}", - title = "{LLVM Clang 上の Continuation based C コンパイラ の改良}", - journal = "{琉球大学工学部情報工学科平成 27 年度学位論文}", - year = 2015 -} +%% Saved with string encoding Unicode (UTF-8) -@misc{agda, - title = {The Agda wiki}, - howpublished = {\url{http://wiki.portal.chalmers.se/agda/pmwiki.php}}, - note = {Accessed: 2017/10/24(Tue)} -} -@misc{agda-documentation, - title = {Welcome to Agda’s documentation! — Agda 2.6.0 documentation}, - howpublished = {\url{http://agda.readthedocs.io/en/latest/index.html}}, - note = {Accessed: 2017/10/24(Tue)} -} \ No newline at end of file +@misc{dfs, + Author = {河野 真治}, + Date-Added = {2018-11-14 13:43:20 +0000}, + Date-Modified = {2018-11-14 14:03:24 +0000}, + Howpublished = {IPSJ SIG Technical Report}, + Month = {May}, + Title = {分散フレームワークChristieと分散木構造データベースJungle}, + Year = {2018}} + +@article{cbc, + Author = {Kaito TOKKMORI and Shinji KONO}, + Date-Added = {2018-11-14 13:40:03 +0000}, + Date-Modified = {2018-11-14 13:40:03 +0000}, + Journal = {LOLA 2015}, + Month = {July}, + Title = {Implementing Continuation based language in LLVM and Clang}, + Year = 2015} + +@misc{christie, + Author = {照屋 のぞみ}, + Date-Added = {2018-11-14 13:36:55 +0000}, + Date-Modified = {2018-11-14 13:42:27 +0000}, + Month = {March}, + Title = {分散フレームワークChristieの設計}, + Year = {2018}, + Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QNy4uLy4uL1BhcGVycy8yMDE4L25vem9taS1tYXN0ZXIvcGFwZXIvbm96b21pLW1hc3Rlci5wZGbSFwsYGVdOUy5kYXRhTxEBsAAAAAABsAACAAAMTWFjaW50b3NoIEhEAAAAAAAAAAAAAAAAAAAAAAAAAEJEAAH/////EW5vem9taS1tYXN0ZXIucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAP////8AAAAAAAAAAAAAAAAAAgAFAAAKIGN1AAAAAAAAAAAAAAAAAAVwYXBlcgAAAgBaLzpVc2VyczplMTU1NzUzOlNwZWNpYWxpemVkX3N1YmplY3Q6a29ubzpQYXBlcnM6MjAxODpub3pvbWktbWFzdGVyOnBhcGVyOm5vem9taS1tYXN0ZXIucGRmAA4AJAARAG4AbwB6AG8AbQBpAC0AbQBhAHMAdABlAHIALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAFhVc2Vycy9lMTU1NzUzL1NwZWNpYWxpemVkX3N1YmplY3Qva29uby9QYXBlcnMvMjAxOC9ub3pvbWktbWFzdGVyL3BhcGVyL25vem9taS1tYXN0ZXIucGRmABMAAS8AABUAAgAO//8AAIAG0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVQBgAGcAagBsAG4AcQBzAHUAdwCEAI4AyADNANUCiQKLApACmwKkArICtgK9AsYCywLYAtsC7QLwAvUAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAAC9w==}} + +@misc{paxos, + Author = {Leslie Lamport}, + Date-Added = {2018-11-14 13:29:50 +0000}, + Date-Modified = {2018-11-14 13:41:19 +0000}, + Month = {01 Nov}, + Read = {0}, + Title = {Paxos Made Simple}, + Year = {2001}} + +@comment{BibDesk Static Groups{ + + + + + + group name + Group + keys + + + + +}}