Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

Crypto Currency(仮想通貨) リスト

仮想通貨

Crypto Currencyの公開されているソースリポジトリと実装言語をまとめてみました。(2017年12月)
ついでに、githubで管理されているものはissueの数を数えて見ました。
ご指摘ありましたら教えていただけると助かります。

Bitcoin(BTC or XBT)

承認時間: 10 分
Language:C++
Digital Signature: secp256k1
Issue count: 3,604
Consensus: Proof of work (sha256)
github.com

Ethereum(ETH)

スマートコントラクト
ゼロ知識証明技術(zk-SNARK)によりトランザクションの情報を隠ぺい可能
Language:Go, C++
Digital Signature: secp256k1
Issue count: 2840
Consensus: Proof of work (将来的にProof of stakeに移行予定)
github.com

Bitcoin Cash(BCH)

Bitcoin Cashは特殊で複数のプロジェクトで独立にノードが実装されています。
ビットコインのハードフォーク(2017年8月)

Language: C++
Digital Signature: secp256k1
Consensus: Proof of work

www.bitcoincash.org

Issue count: 103
github.com

Issue count: 161
github.com

Issue count: 88 https://github.com/bitcoinxt/bitcoinxt

Issue count: 128 github.com

github.com

Monero(XMR)

匿名通貨
Language: C++
Digital Signature: curve25519,ed25519
Issue count: 954
Consensus: Proof of work
github.com

Ripple(XRP)

取引時間 数秒
Language: C++
Digital Signature: Ed25519, secp256k1
Consensus: Proof of consensus
issue count: 314
github.com

Zcash(ZEC)

匿名通貨
ゼロ知識証明技術(zk-SNARK)によりトランザクションの情報を隠ぺい可能
Language: C++
Digital Signature: secp256k1
Issue count: 1983
github.com

Lisk(LISK)

Language: JavaScript Issue count: 743
Consensus: Proof of stake
github.com

Dash(DASH)

ビットコインベース
匿名性
取引時間 4秒
Language: C++
Digital Signature: secp256k1
Issue count: 286
Consensus: Proof of work
github.com

Litecoin(LTC)

承認時間2.5min 2011年10月 BTCのハードフォーク
Language: C++
Digital Signature: secp256k1 (scrypt)
Issue count: 224
github.com litecoin.org

VERGE(XVG)

匿名通貨 Language: C
Digital Signature: curve25519, ed25519 (tor project)
Issue count: 226
Consensus: Proof of work
github.com https://vergecurrency.com/langs/ja/

Augur(REP)

Issue count: 133
github.com

NEM(XEM)

Language: Java
Digital Signature: Ed25519, secp256k1
Issue count: 12
Consensus: Proof of Importance
github.com

Monacoin(MONA)

Language: C++
Digital Signature: secp256k1
Issue count: 17
Consensus: Proof of work
github.com

Factom(FCT)

Language: Go
Issue count: 28 github.com

Ethereum Classic(ETC)

イーサリウムのハードフォーク
github.com

EOS

手数料 無料
スマートコントラクトプロジェクトの資金集めのためのICO
ERC20ベース
仮想通貨ではない
eos.io

GNO

Gnosis
gnosis.pm

ICN

ICONOMI
ICONOMI - Your connection to the distributed economy

MLN

Melonport
melonport.com

REP

Augur
augur.net

USDT

Tether
https://tether.to

XDG

Dogecoin

XLM

stellar
www.stellar.org

TRX

Tron
TRON | Decentralize The Web

BCG

Bitcoin Gold
bitcoingold.org

BCD

Bitcoin Diamond
http://www.btcd.io/#/www.btcd.io

OMG

OmiseGO
Consensus: Proof of stake
omisego.network

ZNY

BitZeny bitzeny.org

secp256k1における体演算の最適化

secp256k1

secp256k1の体演算の最適化手法として、x,yが法素数q未満であることと256bit値の範囲内であることを用いて、
256bitサイズの値を9個の26bit値と1つの22bitの値(9*26+22=256bit)に分割する手法があります。
法素数q=0x FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

q未満の値のマスク値をビット表現すると、上位から
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1110 = 0x FFFFFFFE
1111_1111_1111_1111_1111_1100_0010_1111 = 0x FFFFFC2F
となり下位から26bitずつにわけ10個目を22ビットとします。
11_1111_1111_1111_1111_1111 = 0x 3FFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1011_1111 = 0x 3FFFFBF
11_1111_1111_1111_1100_0010_1111 = 0x 3FFFC2F

26ビットの値は変数としてuint32_tを使い、32ビットの値の範囲内の演算であれば、そのまま計算できます。
元は法素数倍してもmod qの世界では同一値ですから、10個の要素に同時に、これらのマスク値の倍数を加えても、
値としては同じということになります。

なお、32bitの要素を8個使って(32*8=256bit)表現するものも使います。

secp256k1における逆数計算

secp256k1

secp256k1における逆数つまり1/aの計算方法を解説します。
法素数qに対して、 {a}^{q-2}が1/aとなります。
なぜなら {a}^{q-2} {a} = {a}^{q-1} = 1 \mod q
最後の等号は、フェルマーの小定理を使っています。

やることはaをq-2回ベキ乗することです。
pythonでq-2を2進表現してみましょう。

>>> q = 2 ** 256 - 2 ** 32 - 2 ** 9 - 2** 8 - 2 ** 7 - 2 ** 6 - 2 ** 4 -1
115792089237316195423570985008687907853269984665640564039457584007908834671663
>>> print(q-2)
115792089237316195423570985008687907853269984665640564039457584007908834671661
>>> print(format(q-2, 'b'))
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111110000101101

1が223個,1が22個,1が1個,1が2個,最後に1が2個という5つの1の連続領域に分かれています。 あとは、

secp256k1における平方剰余計算 - Pebble Coding

でやったのと同じ手法で、計算すればよいだけです。

平方剰余とは

整数論

平方剰余 http://nakano.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2011/11.pdf

について簡単に説明しておきます。

整数aと整数pを与えた時に
{x}^{2} = a \mod p
の式を満たす解xは存在する場合と、存在しない場合があります。
解が存在する時、a は p を法として平方剰余であるといいます。
解が存在しない時、a は p を法として平方非剰余であるといいます。

例えば、p=5の場合を考えると、
x=1のとき、 {x}^{2} = 1 \mod 5
x=2のとき、 {x}^{2} = 4 \mod 5
x=3のとき、 {x}^{2} = 9 \mod 5 = 4 \mod 5
x=4のとき、 {x}^{2} = 16 \mod 5 = 1 \mod 5
となるので、
a=1,4の時は解が存在し、a=2,3の時は解が存在しません。

楕円曲線暗号において、平方剰余計算が出てくるのはなぜでしょうか？
法素数 q における楕円曲線 {y}^{2} = {x}^{3} + 7 の乗法群で、楕円曲線上の点{x, y}が決まっているとします。
ここでx,yは整数です。
点の２倍算で先にxの値を計算し、楕円曲線の右辺を計算すれば、あとは、
{y}^{2} = a \mod q を満たすyを求めればいいということになります。
２倍算なので、このような解yが存在することは分かっています。
これはまさに平方剰余の解計算です。

はじめての数論 原著第3版 発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

はじめての数論 原著第3版 発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

  • 作者:Joseph H. Silverman
  • 出版社/メーカー: 丸善出版
  • 発売日: 2014/05/13
  • メディア: 単行本（ソフトカバー）

secp256k1における平方剰余計算

secp256k1

secp256k1における平方剰余計算を考えてみます。

secp256k1の法素数
q = {2}^{256} - {2}^{32} - {2}^{9} - {2}^{8} - {2}^{7} - {2}^{6} - {2}^{4} - 1
はこの形をみてわかる通り、 q \mod 4 = 3なので、
この記事mod p での平方剰余を計算する(p mod 4 = 3の場合) - Pebble Coding
で示したように、解は(存在する場合は)
x = {a} ^ { \frac {q+1} {4} }
と書けます。
コンピュータで計算する場合は、次のように計算します。
まず、pythonで値を見てみます。
q+1は4で割り切れるので、python3での整数の割り算には//が使用できます。

>>> q = 2 ** 256 - 2 ** 32 - 2 ** 9 - 2** 8 - 2 ** 7 - 2 ** 6 - 2 ** 4 -1
>>> print(q)
115792089237316195423570985008687907853269984665640564039457584007908834671663
>>> print((q+1)//4)
28948022309329048855892746252171976963317496166410141009864396001977208667916

この値の２進表現(バイナリ表現)を見てみます。

>>> print(format((q+1)//4, 'b'))
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111100001100

とても綺麗な形をしており、1が連続する箇所が3箇所しかありません。
最初の1は223個、次の1は22個、最後の1は2個が連続で続いています。
やることはaをこの値分だけベキ乗することです。
問題を少し単純化してみてみましょう。

この２進数が仮に
10010 だったとしましょう。
計算すべきは {a}^{10010}です。
{a}^{1001}を2乗すると {a}^{10010}になります。
上位へビットシフトしたら2倍になるので、こうなります。
手順は、まず {a}^{1}を計算し、3回ビットシフトつまり{a}^{1}の2乗を3回行い、それにaを掛け、 その値を1回ビットシフト、つまりその値を2乗すると {a}^{10010}が得られます。
この考えを用いて今度は、 {a}^{1が223個並んだもの}を計算したいのですが、効率よく計算するには次のようにします。

表現を簡単にするため、 {a}^{2進表現}のことを以後、x111001...001のように表現します。
まず、x1を2乗するとx10となります、これにaを掛けるとx11となります。
これを2乗しx110となり、それにaを掛け、x111とします。
これの2乗を3回して、x111_000としますが、先ほど計算したx111と掛けx111_111となります。
これの2乗を3回して、x111_111_000となりますが、先ほど計算したx111を掛け、x111_111_111となります。
これの2乗を2回して、x11_111_111_100となりますが、先ほど計算したx11を掛け、x11_111_111_111となります。
これの2乗を11回して,...
これの2乗を22回して,...
これの2乗を44回して,...
これの2乗を88回して,...
...
こんな感じで、1が223個並んだ値が計算でき、このロジックを利用して、最終的に、
{a}^{11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111100001100}を計算します。

コンピュータで解があるかどうかはこうして計算したxを使って x^{2} mod q を計算してaに等しければ解あり、等しくなければ解なしと判断します。

参考:

secp256k1/field_impl.h at master · bitcoin-core/secp256k1 · GitHub