zk-SNARKSs について (自分用メモ)

Zcash - Technology

イーサリアムに導入されたプライバシー保護技術「zk-SNARK」とは

blog.visvirial.com

zk-SNARKの要求
qiita.com

準同型暗号

www.slideshare.net
入力と出力の和が等しいことがコンセンサスに必要


zk-SNARKの実装とフォーク
GitHub - scipr-lab/libsnark: C++ library for zkSNARKs

人間は絶えず精神的な階段を昇り降りしている

降っては、昇り。昇っては、降る。
穴に落ちる場合もあるし、エスカレーターのようなモノを発見し素速く階段を駆け昇ることもあるだろう。
そんなことは重要ではない。
重要なのはその階段が延々と続いていることである。その上層も下層も分からないくらいに。

私たちにできることは、自分がどれだけ昇ったか、そしてどれだけ降ったか、というその事実を把握することだけである。
しかし、私たちはその相対的な感覚をいとも容易く忘れてしまうのではないだろうか。
眠るという行為がそれを誘発するのではないかと私は思う。

人は眠らずにはいられない。
私が一番眠らずに過ごしたのは大学の卒業論文を投稿締切前の3日間だった。
その当時の私の要領は今以上に悪く、卒業論文のテーマと関係しそうなことを、自分の解釈を加えながらひたすら文字に直していただけであり、文章間の繋がりなど全く考えていなかった。
だから、その3日間でその文章の寄せ集めから、その卒業論文が執筆されるべき、ある程度 (学部生レベル) の理由と、そこから順を追って結論まで導く流れを構築する必要があった。

私の頭の中のパーツが私の中では見事なまでに組み合わさり (それはある種の昂揚からくるまやかしかもしれない) 、目の前にある、1 m も距離が離れれば何が書いてあるかも読むこともできない文章群の全てを理解したような気になった。
これは、いい記憶か悪い記憶かは別として強烈に脳裏に焼き付いている。
しかし、睡眠を取るとそのような強烈な体験すらあっという間に色あせてしまった。

ーーーー省略ーーーー

少しでもその昇り降りの記録を残したい。
その気持ちを込めて今もこの文章を書いている。

行列・ベクトルに関する定義、公式と導出 (自分用メモ)

The Matrix Cookbook
https://www.math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf
2.4

・行列の積の転置の行列
 (AB)^T = B^T A^T を示したい。行列 [tex AB] の [tex (ij)] 成分が[tex (ji)] 成分と

\begin{align}
(追記)
\end{align}

・ベクトルによるスカラー微分
\begin{align}
\frac{ \partial f({\bf x}) }{\partial {\bf x}} = [\frac{ \partial f({\bf x}) }{\partial x_1}, \frac{ \partial f({\bf x}) }{\partial x_2}, ..., \frac{ \partial f({\bf x}) }{\partial x_n} ]^T \equiv grad \bigl( f({\bf x}) \bigl)
\end{align}

\begin{align}
\nabla = \biggl( \frac{ \partial }{\partial x_1}, \frac{ \partial }{\partial x_2}, ..., \frac{ \partial }{\partial x_n} \biggl)
\end{align}

 f ({\bf x}) = {\bf x}^T A  {\bf x} の場合の  \partial f({\bf x}) / \partial {\bf x}

\begin{align}
\frac{\partial f({\bf x})}{\partial x_i} &= \frac{\partial \underset{n}{\sum} \underset{m}{\sum} a_{nm} x_n x_m}{ \partial x_i} \\
&= \underset{n}{\sum} \underset{m}{\sum} a_{nm} \frac{ \partial x_n }{ \partial x_i} x_m + \underset{n}{\sum} \underset{m}{\sum} a_{nm} x_n \frac{ \partial x_m }{ \partial x_i} \\
&= \underset{m}{\sum} a_{im} x_m + \underset{n}{\sum} a_{ni} x_n
\end{align}

第一項は、 A {\bf x}  i 番目成分、第二項は、 A^T {\bf x} の i 番目成分。
つまり、 \frac{\partial \bigl( {\bf x}^T A {\bf x}  \bigl)}{\partial {\bf x}} = (A + A^T) {\bf x} となる。

論文に使っている英語について Part.3 (随時更新)

ーーーーーAtomic Cross-Chain Swaps (written by M. Herlihy), ArXiv v.5より引用。-----
・For example, let  H(\cdot) be a cryptographic hash function.
例えば、 H(\cdot)ハッシュ関数とする。

・with hashlock  h and timelock  t
ハッシュロック  h とタイムロック  t を用いて。

・Hashlock  h means that if Bob sends the contract a value  s, called a secret, such that  h = H(s), then the contract irrevocably transafers ownership of those alt-coins from Alice to Bob.
ハッシュロック  h の意味は、もしボブがコントラクトに h = H(s) となるようなシークレット  s を送信したら、コントラクトは取消不能にこれらのあるとコインの所有権はアリスからボブへ転送される。

・Timelock  t means that if Bob fails to produce that secret before time  t elapses, then the escrowed alt-coins are refunded to Alice.
タイムロック  t の意味は、もしボブが時刻  t より前にシークレットの生成をしない場合、エスクローされたアルトコインはアリスに返金される。

ーーーーーメモURL-----
btcnews.jp

Atomic Cross-Chain Swaps written by M. Herlihy について(自分用メモ)

ブラウン大学のM. HerlihyによりArXivに投稿された Atomic Cross-Chain Swaps についてメモしていく。
[1801.09515] Atomic Cross-Chain Swaps

まず以下が上記論文のアブストラクトである。

     「An atomic cross-chain swap is a distributed coordination task where multiple parties exchange assets across multiple blockchains, for example, trading bitcoin for ether.
An atomic swap protocol guarantees (1) if all parties conform to the protocol, then all swaps take place, (2) if some coalition deviates from the protocol, then no conforming party ends up worse off, and (3) no coalition has an incentive to deviate from the protocol.
A cross-chain swap is modeled as a directed graph  D, whose vertexes are parties and whose arcs are proposed asset transfers. For any pair  (D,L), where  D=(V,A) is a strongly-connected directed graph and  L⊂V a feedback vertex set for  D, we give an atomic cross-chain swap protocol for  D, using a form of hashed timelock contracts, where the vertexes in L generate the hashlocked secrets. We show that no such protocol is possible if  D is not strongly connected, or if  D is strongly connected but L is not a feedback vertex set. The protocol has time complexity  O(diam(A)) and space complexity (bits stored on all blockchains)  O(|A|2).」

拙訳: 「アトミックなクロス・チェーン・スワップとは、複数の参加者が複数のブロックチェーンにわたってアセットを交換する、分散協調タスクのことです(例えば、Etehereumを獲得するためにBitcoinを取引に出すなど)。アトミック・スワッププロトコルは、次の3つを実現する。(1)参加者全員がプロトコルに従う場合、全ての定義されるスワップは実行できる。(2)いくつかの参加者がこのプロトコルに従わなくなった場合でも、プロトコルに従う参加者の状況が、アトミックスワップ実行前より悪くなることはない。(3)プロトコルから離れるインセンティブを持つ参加者はいない。
クロスチェーンスワップは有向付グラフとしてモデル化され、そのグラフの頂点は参加者となり、そのグラフの弧 (arc) は提案されたアセットの移転となる。 どんなペアの  (D,L) (ここで、 D=(V,A)は強く接続された有効付きグラフであり、頂点に含まれる L⊂V は、グラフ Dのフィードバック頂点集合である ) において、我々はグラフ  D のためのアトミッククロスチェーン交換プロトコルを提案した。その提案では、ハッシュ化されたタイムロックコントラクトの形式を用いている。そのコントラクトは、 Lに含まれる頂点がハッシュロックされたシークレットを生成する。我々は、 D が強く接続していない、または、 D が強く接続していても Lがフィードバック頂点集合でない場合、そのようなプロトコルが実現不可能であることを示します。そのプロトコルは、 O(daim(D)) の計算量を持ち、空間的な複雑さ(全ブロックチェーンが保存すべきBit)は  O(|A|^2) となる。

diam とはグラフの直径 (diameter) である。グラフ G の最大頂点間距離が直径と定義される。
グラフ理論 - Wikipedia

ーーーーメモーーーー
www.wikicfp.com (学会投稿先探し)