# HG changeset patch # User ichikitakahiro # Date 1557242994 -32400 # Node ID d356c4c52bcae67efad9de4c1b80d62a62f894e7 # Parent 9d14310d63645544af1ded83a757084812a559f2 write ~3.1 diff -r 9d14310d6364 -r d356c4c52bca paper/sigos.pdf Binary file paper/sigos.pdf has changed diff -r 9d14310d6364 -r d356c4c52bca paper/sigos.tex --- a/paper/sigos.tex Tue May 07 22:15:13 2019 +0900 +++ b/paper/sigos.tex Wed May 08 00:29:54 2019 +0900 @@ -114,7 +114,7 @@ \begin{figure}[h] \begin{center} \includegraphics[width=240pt]{./images/chain.pdf} -\caption{トランジスタにて作成したANDゲート} +\caption{hash chain} \end{center} \end{figure} @@ -127,248 +127,78 @@ %\|http://www.ipsj.or.jp/journal/submit/style.html| %\end{quote} -\begin{Enumerate} -\item \|ipsj.cls |: 原稿用スタイルファイル -\item \|ipsjpref.sty |: 序文用スタイル -\item \|jsample.tex |: 本稿のソースファイル -\item \|esample.tex |: 英文サンプルのソースファイル -\item \|ipsjsort.bst |: jBibTEX スタイル（著者名順） -\item \|ipsjunsrt.bst |: jBibTEX スタイル（出現順） -\item \|bibsample.bib |: 文献リストのサンプル -\item \|ebibsample.bib|: 英文文献リストのサンプル -\item \makebox[9.47zw][l]{{\tt ipsjtech.sty}}: 研究報告用スタイル -\item \| tech-jsample.tex|: 研究報告（和文）のサンプル -\item \| tech-esample.tex|: 研究報告（英文）のサンプル -\end{Enumerate}% -実行環境としては\LaTeXe を前提としているので，準備されたい． - - -Microsoft Wordに関しては，投稿されたフォーマットを基に， -業者が \LaTeX に変換して組版を行うので， -あくまでも参考としてしか使わないことを承知して頂きたい． - - - -%2.2 -\subsection{最終原稿の作成と投稿} - -本稿に従って用意した原稿の \LaTeX ソースからpdfファイルを作成し， -Adobeのpdf readerで読めることを確認した後， -\begin{quote} -\small -\|https://mc.manuscriptcentral.com/ipsj| -\end{quote} -上記のURLから投稿する． -投稿の流れについては， -\begin{quote} -\small -\|http://www.ipsj.or.jp/journal/submit/manual/|\\ -\|j_manual.html| -\end{quote} -を参照されたい． - - - -なお，情報処理学会論文誌ジャーナルでは， -論文の著者が査読者の名前を知ることがないシングルブラインドの査読を取り入れている． - - - - -%2.3 -\subsection{最終原稿の作成とファイルの送付} - -投稿した論文の採録が決定したら， -査読者からのコメントなどにしたがって原稿を修正し， -図表などのレイアウトも最終的なものとする． -なお後の校正の手間を最小にするために， -この段階で記述の誤りなどを完全に除去するように綿密にチェックして頂きたい． - - - -学会へは{\bf \LaTeX ファイル（をまとめたもの）}を送信する． -送信するファイル群の標準的な構成は \|.tex| と \|.bbl| であり， -この他にPostScriptファイルや特別なスタイルファイルがあれば付加する． -なお \|.tex| は印刷業者が修正することがあるので， -{必ず一つのファイルにする}． -また必要なファイルが全てそろっていること， -特に特別なスタイルファイルに洩れがないことを，注意深く確認して頂きたい． - - -ファイルの送信方法などについては， -採録通知とともに学会事務局から送られる指示に従う． - - - - -%2.4 -\subsection{著者校正・組版・出版} - - -学会では用語や用字を一定の基準（常用漢字および -「現代仮名遣い」等）に従って修正することがある． -また \LaTeX の実行環境の差異などによって著者が作成した最終PDFと -実際の組版結果が微妙に異なることがある． -これらの修正や差異が問題ないかを最終的に確認するために， -著者にPDFファイルが送られるので， -もし問題があれば朱書によって指摘して送信する． -なお{\bf この段階での記述誤りの修正は原則として認められない}ので， -原稿送信時に細心の注意を払っていただきたい． - +\subsection{トランザクションとその構造} +トランザクションとはデータのやり取りを行った記録の最小単位である. トランザクションの構造は次のとおりである. +\begin{description} +\item[TransactionHash] トランザクションをハッシュ化したもの. +\item[data] データ. +\item[sendAddress] 送り元のアカウントのアドレス. +\item[recieveAddress] 送り先のアカウントのアドレス. +\item[signature] トランザクションの一部と秘密鍵をSHA256でハッシュ化したもの. ECDSAで署名している. +\end{description} -その後，著者の校正に基づき最終的な組版を行ない， -オンライン出版する． - - - - -%3 -\section{論文フォーマットの指針} -\label{sec:format} +トランザクションはノード間で伝搬され,ノードごとに検証される.そして検証を終え,不正なトランザクションであればそのトランザクションを破棄し,検証に通った場合はTransaction Poolに取り組まれ,また検証したノードからトランザクションがブロードキャストされる. -以下， -情報処理学会論文誌ジャーナル用スタイルファイルを用いた論文フォーマットの -指針について述べるので， -これに従って原稿を用意頂きたい．\LaTeX を用いた -一般的な文章作成技術については，\cite{okumura, companion} 等を参考にされたい． - - - -%4 -\section{論文の構成} -\label{config} - -ファイルは次のようになる． -下線部は投稿時に省略可能なもの． -また論文誌トランザクション特有コマンドについては \ref{sig}~節を参照されたい． +\subsection{fork} +ブロックの生成をした後にブロードキャストをすると,ブロック高の同じ,もしくは相手のブロック高の高いブロックチェーンにたどり着く場合がある.当然,相手のブロックチェーンはこれを破棄する.しかしこの場合,異なるブロックを持った2つのブロックチェーンをこの状態をforkと呼ぶ.fork状態になると,2つの異なるブロックチェーンができることになるため,一つにまとめなければならない.１つにまとめるためにコンセンサスアルゴリズムを用いるが,コンセンサスアルゴリズムについては次章で説明する. -\noindent -\|\documentclass[submit]{ipsj}|\\ -\quad 必要ならばオプションのスタイルを追加\\ -\Underline{\|\setcounter{|{\bf 巻数}\|}{<巻数>}|}\\ -\Underline{\|\setcounter{|{\bf 号数}\|}{<号数>}|}\\ -\Underline{\|\setcounter{|{\bf page}\|}{<先頭ページ>}|}\\ -\Underline{\|\|{\bf 受付}\|{<年>}{<月>}{<日>}|}\\ -\Underline{\|\|{\bf 採録}\|{<年>}{<月>}{<日>}|}\\ -\quad 必要ならばユーザのマクロをここに記述\\ -\|\begin{document}|\\ -\|\title{表題(和文)}|\\ -\|\etitle{表題(英文)}|\\ -\Underline{\|\affiliate{所属ラベル}{<和文所属>\\<英文所属>}|}\\ -\quad 必要ならば \|\paffiliate| により現在の所属を宣言する\\ -\Underline{\|\paffiliate{現所属ラベル}{<和現所属>\\<英現所属>}|}\\\\ -\Underline{\|\author{情報 太郎}{Taro Joho}|}\\ -\Underline{\| {<所属ラベル>}[E-mail]|}\\ -\Underline{\|\author{処理 花子}{Hanako Shori}|}\\ -\Underline{\| {<所属ラベル2,現所属ラベル3>}|}\\\\ -\|\begin{abstract}|\\ -\|<概要（和文）>|\\ -\|\end{abstract}|\\ -\|\begin{jkeyword}|\\ -\|<キーワード>|\\ -\|\end{jkeyword}|\\ -\|\begin{eabstract}|\\ -\|<概要（英文）>|\\ -\|\end{eabstract}| -\|\begin{ekeyword}|\\ -\||\\ -\|\end{ekeyword}|\\ -\|\maketitle|\\ -\|\section{|第1節の表題\|}|\\ -\dots\dots\dots\dots\dots\\ -\quad \|<本文>|\\ -\dots\dots\dots\dots\dots\\ -謝辞がある場合は\\ -\|\begin{acknowledgment}|\\ -\|\end{acknowledgment}|\\\\ -\|\begin{thebibliography}{99}%9 or 99|\\ -\|\bibitem{1}|\\ -\|\bibitem{2}|\\ -\|\end{thebibliography}|\\\\ -付録がある場合は\\ -\|\appendix|\\ -\|\section{|付録1節の表題\|}|\\\\ -\Underline{\|\begin{biography}|}\\ -\Underline{\|\profile{}{<苗字 名前>}{<プロフィール文章>}|}\\ -\Underline{\|\end{biography}|}\\ -\|\end{document}| +\section{コンセンサスアルゴリズムについて} +\subsection{Proof of Workを用いたコンセンサス} +ブロックチェーンでは,パブリックブロックチェーンの場合とコンソーシアムブロックチェーンによってコンセンサスアルゴリズムが変わる.この章ではパブリックブロックチェーンのBitcoin,Ethereumに使われているProof of Workとコンソーシアムブロックチェーンに使えるPaxosを説明する。 - - -%4.1 -\subsection{オプション・スタイル} -\label{option} -\|\documentclass{ipsj}|のオプション\footnote{論文誌トランザクション用オプションは \ref{sig}~節で説明する．}として， -以下のものを用意してある． -{\bf 何も定義しなければ和文論文用の標準スタイル}となるが， -今回，組版の際に和文論文のタイトル， -和文論文種別に「{\bf 太ミン}」「{\bf 太ゴ}」のフォントを使用しているため， -\TeX 標準フォントに置き換える \|submit| というオプションを用意した． +\subsection{Proof of Workを用いたコンセンサス} +パブリックブロックチェーンとは,不特定多数のノードが参加するブロックチェーンシステムのことをさす。よって,不特定多数のノード間,全体のノードの参加数が変わる状況でコンセンサスが取れるアルゴリズムを使用しなければならない.Proof of Workは不特定多数のノードを対象としてコンセンサスが取れる.ノードの計算量によってコンセンサスを取るからである.次のような問題が生じてもProof of Workはコンセンサスを取ることができる. \begin{enumerate} -\item\|submit | フォント置換用 -\item\|invited | 招待論文 -\item\|sigrecommended | 推薦論文 -\item\|technote | テクニカルノート用 -\item\|preface | 序文用 -\item\|JIP | 英文用 +\item プロセス毎に処理の速度が違う. つまり, メッセージの返信が遅い可能性がある +\item 通信にどれだけの時間がかかるかわからず, その途中でメッセージが失われる可能性がある, +\item プロセスは停止する可能性がある. また, 復旧する可能性もある. +\item 悪意ある情報を他のノードが送信する可能性がある.\\ \end{enumerate} -これらのオプションは任意の組合せで使用が可能である． - - +Proof of Workに必要なパラメータは次のとおりである. -なお，\|\usepackage| で補助的なスタイルファイルを指定した場合には， -最終原稿用のファイル群に必ずスタイルファイルを含める． -ただし，\LaTeXe の標準配布に含まれているもの -（たとえば \|graphicx|）については同封の必要はない． - -スタイルファイルによっては論文誌スタイルと矛盾するようなものもあるので， -注意して使用して頂きたい． - - +\begin{itemize} +\item nonce +\item difficulty +\end{itemize} +nonceはブロックのパラメータに含まれる.difficultyはProof of Workの難しさ,正確にいえば１つのブロックを生成する時間を調整している.Proof of Workはこれらのパラメータを使って次のようにブロックを作る. \\ -%4.1.1 -\subsubsection{研究報告専用オプション・スタイル} -\label{4-1-1} - -上記オプションとは別に，研究報告専用のオプションを用意した． \begin{enumerate} -\item\|techrep | 研究報告（必須） -\item\|noauthor | 英文著者表記無しの指定（和文；任意） +\item ブロックとnonceを加えたものをハッシュ化する. この際, nonceによって, ブロックのハッシュは全く違うものになる. +\item ハッシュ化したブロックの先頭から数えた0ビットの数がdifficultyより多ければ, そのブロックにnonceを埋め込み, ブロックを作る. +\item 2の条件に当てはまらなかった場合はnonceに1を足して, 1からやり直す. \end{enumerate} +difficulty = 2でProof of Workの手順を図にしたものを図３.1に示す. -和文の研究報告では， -和文キーワード， -英文著者名， -英文タイトル， -英文アブスト， -英文キーワードが任意入力となるため， -\|techrep|オプションを使用していれば， -任意項目が無くとも -コンパイルが止まることはない（\|tech-jsample.tex|参照）． - -\|\documentclass[submit,techrep]{ipsj}|\\ -とすれば，研究報告のスタイルとなり， +\begin{figure}[h] +\begin{center} +\includegraphics[width=240pt]{./images/proof-of-work.pdf} +\caption{proof-of-workの例} +\end{center} +\end{figure} -\|\documentclass[submit,techrep,noauthor]{ipsj}|\\ -とすれば， -英文著者名等が入らない研究報告のスタイルとなる． - - +2の条件については,単純に(桁数 - difficulty + 1) * 10 $>$ hash とも置き換えることができる.\\nonceを変えていくことで,hashはほぼ乱数のような状態になる.つまり,difficultyを増やすほど,条件に当てはまるhashが少なくなっていくことがわかり,そのhashを探すための計算量も増えることがわかる.\\これがProof of Workでブロックを生成する手順となる.これを用いることによって,ブロックが長くなるほど,すでに作られたブロックを変更することは計算量が膨大になるため,不可能になっていく.Proof of Workでノード間のコンセンサスを取る方法は単純で,ブロックの長さの差が一定以上になった,場合,長かったブロックを正しいものとする.これを図で示すと3.2のようになる.\\ +\begin{figure}[h] +\begin{center} +\includegraphics[width=240pt]{./images/proof-of-work-fork.pdf} +\caption{Proof of Workのコンセンサス} +\end{center} +\end{figure} +計算量の差が51\%以上になると,forkしたブロック同士で差が生まれる.それによって,IPアドレスでのコンセンサではなく,CPUの性能によるコンセンサスを取ることができる.\\コンセンサスでは,ブロックとの差が大きければ大きいほど,コンセンサスが正確に取れる.しかし,正しいチェーンが決まるのに時間がかかる.そのため,コンセンサスに必要なブロックの差はコンセンサスの正確性と時間のトレードオフになっている.\\ -英文の研究報告では， -キーワードのみが任意入力となるため， -\|noauthor|は使用できないので注意する -（\|tech-esample.tex|参照）． - +この方法でコンセンサスを取る場合の欠点を挙げる. +\begin{itemize} +\item CPUのリソースを使用する. +\item Transactionが確定するのに時間がかかる. +\end{itemize} -%4.2 -\subsection{表題・著者名等} - -表題，著者名とその所属， -および概要を前述のコマンドや環境により{\bf 和文と英文の双方について}定義した後， -\|\maketitle| によって出力する． - +\subsection{Paxos} +コンソーシアムブロックチェーンは許可したのノードのみが参加できるブロックチェーンである.そのため,ノードの数も把握できるため,Paxosを使うことができる.Paxosはノードの多数決によってコンセンサスを取るアルゴリズムである.ただし,Paxosは次のような問題があっても値を一意に決めることができる. +\begin{enumerate} +\item プロセス毎に処理の速度が違う. つまり, メッセージの返信が遅い可能性がある +\item 通信にどれだけの時間がかかるかわからず, その途中でメッセージが失われる可能性がある, +\item プロセスは停止する可能性がある. また, 復旧する可能性もある. +\end{enumerate} %4.2.1