[btc]TXIDとSegwitのTXIDとWTXID

TXID、というものがある。
Transaction IDの略だ。

IDというと、どこかで管理したりしていそうだが、Bitcoinはどこかに依存することがないというか、全体に依存しているというかで、データのためのデータはそんなにないと思う。

ただ、トランザクションを一意に表す数字がないと不便なのも確か。
だから、トランザクション自体のデータからハッシュ計算してIDを求めている。

さて、Segwitが出る以前。
TXIDはシンプルで、トランザクションデータ全体をSHA256し、それをさらにSHA256した値(32byte)だった。

トランザクションの構成は、こうだ。

• version
• txin
• txout
• locktime

bitcoindでトランザクションを作ったことがある人はわかるだろうが、順番としては、

• 署名が空のトランザクションを作る
• 署名する

という手順を踏む。
署名したトランザクションはブロックチェーンに公開することができるので、署名するのは最後なのだ。
だから、TXIDが計算できるのは署名後ということになる。

さて、時代はSegwit。
Segregated Witnessという名前の通り、署名が分離されたトランザクションになる。
トランザクションから分離したということは・・・TXIDからも分離されたのだ（そういう理屈なのかどうかは、知らん）。

しかし、トランザクションデータには署名が入っている。
細かく言えば、txメッセージで送信するトランザクションデータには署名が載っている。
ではSegwitなトランザクションのTXIDはなんなのかというと、計算方法が以前と異なるのである。
計算式はシンプルなTXID時代からするとかなり面倒になったのだが、署名部分は計算から除外するようになった。

だから、非SegwitトランザクションのTXID計算方法と、SegwitトランザクションのTXID計算方法は異なるのだ。

だいたい話は終わりなのだが、余談としてWTXIDのことも書いておこう。

ずばり、WTXIDは、Segwitトランザクションを以前と同じTXID計算方法で求めた値のことだ。
ただ、WTXIDの使いどころが分からないので、計算をしたことがなく、検証まではできていない。
https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki#transaction-id

[c/c++]JSON-RPCでuint64_tに対応するのは難しいか

最近、サーバ型というかdaemon型というか、バックグラウンドで動くアプリを作っている。
それに対して外部から指示を与えたいことがあるのだが、今までLinuxのメッセージキューを使っていた。
それで困っていなかったのだが、他の類似するツールを見るとJSON-RPCでやりとりしていることが分かった。

長いものに・・・巻かれるしかないのか・・・。

同じ形式でAPIを受け付けるように作っておけば、外側の部分は自分で作らずに済むし、そうしておくことによって他の人から使ってもらえる可能性も上がる（たぶん）。

あきらめて、JSON-RPCのパラメータを受け付けるように改造することにした。

---

こういうときは、githubなどからライブラリを探して、それを使うのがよいだろう。
Google検索して見つかった一番上が、こちら。

• hmng/jsonrpc-c: JSON-RPC in C (server only for now)

httpの方が汎用性が高いのかもしれないが、TCPのsocketをつくってwrite/read()すれば動くので、作るのが楽そうだ。

半分ほど実装していて思い出したが、今回はuint64_tを使っているのだった。
しかし、この子はintかdoubleしか持っていない。
doubleでは丸められる可能性があって困るのだ。。

そういえば、と別の場所で使っているjanssonも見直してみたが、long long型の対応になっているのでint64_tはいけるものの、uint64_tは無理だろう。

よく考えれば、Cは標準型でそこまでしか対応していないし、JavaみたいにBigDecimalみたいな標準もないため、そもそも対応すること自体が難しいだろう。
janssonのbignum版を作っている人もあったが、整数型はgmpかopensslを使うことになるようだ。
うーん、それはちょっと今回の方針にあわない。。。

今回はintかuint64_tまでしか使わないので、自分でuint64_t対応を追加すればよいのだろうが、気力が湧かない（それでいいのか）。
ひとまず、逃げの手段として、uint64_tは文字列に変換して、読み出すときはまたuint64_tとして戻すことにした。
array型で、順番がこちらで決められるからできる技だ。
ただ、serverもclientも自前じゃないとダメなんだけどね。。。

gccなら__int128があるようで、それならuint64_tのサイズでも収まるから少し気は楽になるが、うーん、やっぱり、なんかねー。
この辺りは、pythonみたいに自由な幅にできる言語が有利ですな。

[btc]regtestでsegwitするにはブロック数がいる

最近、というわけでもないが、testnetが今ひとつ順調ではないように見える。

数日前は、トランザクションが1つ(というか、coinbaseだけ)のブロックが多く、トランザクションが全然さばけていないようだった。
https://testnet.blockexplorer.com/blocks-date/2017-08-31

今日は普通だと思っていたのだけど、なんかsegwitのトランザクションだけ除外されていないか？
そういう真似ができるのかどうか知らんが、数時間前に発行したsegwitのトランザクションがマイニングされないのに、faucetから送ってもらったトランザクションはすぐにマイニングされていたのだ。

よくわからんが、不安定で作業にならないので、regtestを使うことにした。
初めてのregtestだ。

---

Bitcoinを使ったアプリケーションのテスト環境 - Develop with pleasure!

bitcoin.confを書き換える程度で動かせた。
regtest時のbitcoin-qtは水色だった。

書いてあるように、bitcoin-cliなどでgenerateコマンドを使うと、その数だけブロックを生成してくれる。
これで、マイニングされたことになるので、ビクビクしなくてよいのだ。

しかし・・・segwitのトランザクションを作ろうとaddwitnessaddressしたのだが、segwitは対応していないとか出てくる。。。
regtestなのに！

検索すると、ちゃんと調べてくれた人が見つかった。
How to activate segwit on regtest

あー、101ブロックしか生成していなかったけど、432ブロック以上ないとsegwitがActiveにならないんだ。
しかし、432ブロックというのはなんだろうか？

https://github.com/bitcoin/bitcoin/blob/28f788e47e58f2b462351d6989348a4e1a241b2b/test/functional/bip68-sequence.py#L371
BIP68関連らしい。

https://github.com/bitcoin/bitcoin/blob/28f788e47e58f2b462351d6989348a4e1a241b2b/test/functional/segwit.py#L198
こちらも432だが、144 * 3ということになっている。

144 = 24(時間) * 60(分) / 10(ブロック毎分)

ということかな？
mainnetの時間で3日分というのが432の根拠のようだ。

なんで3日なのかというのは、わからんかったが、まあいいや。

[win][修復]Windows10が立ち上がらなくなったので復旧 - 2

まさかの第2弾。
というよりも、OSが立ち上がらないということはしばしばあると思うので、その記録だ。

hiro99ma blog: [win][修復]Windows10が立ち上がらなくなったので復旧

予備で用意しているPCがあり、そのWindows10が起動しなくなった。
用意しているというか、マザーボードやCPUが古くなったので一式買い替えたのだが、その前に使っていたPCだ。
Windowsも新しいPCに持っていこうと思ったのだが、マザーボードが変わるとインストールできないという話を聞いたので、そちらは別途購入したのだ。

最後にWindows Updateしたのが1年くらい前だったので、たぶんその間は起動していないのだと思う。
無事に起動したので、過去のデータはもう不要だろう、とWindowsのリセットで全データ消去を選択。
自動的に再起動してクリーンアップが進んだのだが、途中かどこかでブルースクリーンが発生し、再起動を繰り返すようになってしまったのだ。

クリーンアップしたらきれいな状態で立ち上がるだろう、と思っていたので、修復ディスクは作っていたものの、復旧ディスクは作っていない。
復旧ディスクって、USBメモリ1本使うので、もったいない、と思ったのが正直なところだ。

ブルースクリーンになるのはログイン画面が出る前なのだが、F4を押して起動させるとあのメニューは出てくる。
そこでまたPCのリセットを行ったが、エラーが起きましたというだけで何もできない。
修復ディスクで起動させても、同じようなものだった。

復旧ディスクであれば何でもよいかと思い、ThinkPadで作っていた復旧ディスクで起動したのだが、起動させている間にネットで検索すると、どうも共有できるものではないらしい。
ThinkPadはWin10 Home、予備PCはWin10 Proだったのだが、予備PCにWin10 Homeとかいうパーティションが作られてしまった。。。
もちろん、復旧もできなかった。

このWin10はWin7からのネットワークアップグレードでできているので、Win7のディスクはあるものの、Win10用は何もないのだ。

もうあきらめるしかないかと思ったのだが、もう1つ手段があった。
新しいPC用に買ったWindows10のインストールディスクだ。
これが、使えた。
ディスクから起動すると復旧させるボタンが出てくるのだが、それは押さずに普通のインストールを進める。
プロダクトIDを入力するところをスキップさせると、起動時にネットワーク認証を行うらしい(画面にそう出ていた)。
そうやって進めると、無事に起動できる状態になった。

よかったよかった。
復旧ディスクを急いで作ったのは、言うまでもない。

復旧ディスクって、もうすぐ2017年秋バージョンのリリースが行われるそうなのだが、新しくなるごとに更新した方がよいのだろうか？
そこら辺がよくわからんね。

[zybo]PetaLinuxでDigilentのチュートリアルが動かん (17)

前回の動かん(16)では、xparameters.hにアドレスの定義が載っていることを確認した。

では、ソースに直接書く方法から、includeして参照する方法に変更しよう。
と書き換えたものの、xparameters.hをincludeしてくれない。。。

xparameters.hは、この2箇所にあるのだが、使うのは前者だ。

components/plnx_workspace/fsbl_bsp/ps7_cortexa9_0/include/xparameters.h
components/plnx_workspace/fsbl_bsp/ps7_cortexa9_0/libsrc/common_v1_00_a/src/xparameters.h

パスを継ぎ足していったのだが、componentsから書いても見つからない。
どこからかの相対パスで指定したいのだが、どこから書いてよいものかもわからん。

あきらめてモジュールのソースファイルと同じ場所にコピーしたのだが、それでもダメだ。
カレントディレクトリすら参照してくれないというのか！

と思ってfindすると、実際にビルドするディレクトリはproject-spec/meta-user/recipes-modules/led8drv/filesではなく、build/tmp/work/plnx_arm-xilinx-linux-gnueabi/led8drv/1.0-r0という場所にファイルをコピーして行っているようだ。
そして、filesにあるファイルをすべてコピーしているわけではなく、xparameters.hなどはコピーされていないため、参照できていない、ということらしい。

じゃあ、何を書き換えたらよいかというと、bbファイルを変更するとコピーしてくれるようだった。

SRC_URI = "file://Makefile \
            file://zybo_gpio.c \
            file://xparameters.h \
            file://xparameters_ps.h \
        file://COPYING \
           "

これで、取りあえずはファイルをコピーしてくれてビルドもできるようにはなった。
だが、ファイルを手動でコピーする手間がかかるし、なにより格好が悪い。

PetaLinux Tools User Guide(UG977 v2014.2)にはpetalinux-configで更新できるようなことが書いてあるのだが、最近ではこのドキュメントは更新していないようだし、やってもダメだった。
きっと、ちゃんとしたやり方があるのだろうとは思うが、わからんのだ。
SDK内であれば何かありそうなのだけど、PetaLinuxのところだけでやりたいのだよなぁ。

[zybo]PetaLinuxでDigilentのチュートリアルが動かん (16)

久しぶりすぎて、内容を覚えていない・・・。

前回は、GPIOのアドレス定義が自動生成されたxparameters.hに載っていることがわかった、というところまでだった。
何をしていたかというと、Linuxのデバイスドライバを作る際、どのアドレスを操作すればよいのかを調べていたのだ。

今見ているのは、これ。
original: http://www.cqpub.co.jp/interface/download/2016/4/IF1604Z.zip

Interface誌のサンプルをちょっと変更した程度のものだ。
GPIOのアドレスは、gpio_table[]を使っている。

動かん(14)のときにどれを使っているのか計算しているが、mknodしたのが24なのでgpio_table[3]ということだ。
そのアドレスは、0x41200000 + 0x10000 + 0x0。

./components/plnx_workspace/fsbl_bsp/ps7_cortexa9_0/include/xparameters.hを見ると、こういう行があった。

/* Canonical definitions for peripheral BTNS_4BITS */
#define XPAR_GPIO_0_BASEADDR 0x41200000
#define XPAR_GPIO_0_HIGHADDR 0x4120FFFF
#define XPAR_GPIO_0_DEVICE_ID XPAR_BTNS_4BITS_DEVICE_ID
#define XPAR_GPIO_0_INTERRUPT_PRESENT 0

まず、MAP_BASE_ADDRの根拠はわかった。
zybo_gpio.cでは固定値なので、このアドレスも求める方法があるのだろうが、まあ、よかろう。

次はオフセットだ。
制御しているのはZYBOのJEコネクタで、0x41210000から1KBをioremap()し、32bitを書込むようにしている。

ああ、こういう定義が近くにあった。

/* Definitions for peripheral LEDS_4BITS */
#define XPAR_LEDS_4BITS_BASEADDR 0x41210000
#define XPAR_LEDS_4BITS_HIGHADDR 0x4121FFFF
#define XPAR_LEDS_4BITS_DEVICE_ID 1
#define XPAR_LEDS_4BITS_INTERRUPT_PRESENT 0
#define XPAR_LEDS_4BITS_IS_DUAL 0

Block Designを見ると、GPIO類はこうなっていた。

この名前が、そのままマクロ定義になるのか。

mknodするminor番号だが、zybo_gpio.cではビットを表していたのか。

0- 7 : ボタン
8-15 : DIPスイッチ
16-23 : 未割り当て
24-31 : LED

だから、16～23だとエラーなのか。
ビットシフトを3つやってるのも、8bit単位で何番目かを割り出すという意味なのだろう。
読み書きの方向についてはminorのb4を使っているが、0～15はINPUTだから使っただけか。
LEDでもスイッチでもいけるように、GPIO_BUFFという構造体を用意して、そこに情報を突っ込み、あとはシステムコールで呼び出されたらそれを使うだけ、ということにしたかったのだろう。

ioremap()は、物理メモリをアクセスする準備みたいなもののようだ。
IoMemoryAccess - Kernel Newbies Japan
MMUもあるし、こういうやり方になるのか。
戻り値をそのまま使ってよいわけではなく、readb/w/l()、writeb/w/l()を介してアクセスするそうだ。
zybo_gpio.cでは iowrite32()を使っているので、ビット幅で指定するタイプもあるのか。

9.4. Using I/O Memory
こちらはオライリーのLinux Deveice Drivers第3版の元ページ？のようだが、readb()などのタイプはolderと書いてある。
まあ、ビット幅の方がわかりやすいわね。

ioremap()だが、終わったらiounmap()しなくてよいのだろうか？
なんとなく、close()時にやった方が良い気がする。

Linuxデバイスドライバのお作法がわかっていないので、基本的なところは抑えた方がよさそうだ。

[c++]Boostのdijkstra_shortest_paths() - end

Boostのグラフで経路を求めたので、最後に、自分であれこれやったソースをGistに置いておこう。

boostのグラフを使って経路探索するサンプル

経路は、boost.jpのグラフにあるものを使った。

$ g++ -o tst dijk_dist.cpp
$ ./tst
distance: 11
START --> Asia --> Beer --> Devel --> Foobar --> GOAL

Boostのサンプルにあった、graphvizで出力するやりかたも真似した。

双方向にしたのでゴチャゴチャしているが、方向によって重みが違う場合にはこうやることになるだろう(今回は同じ重みだが)。

[c++]Boostのdijkstra_shortest_paths() - 4

前回は、dijkstra_shortest_paths()に重みを指定しつつ、経路を得るための引数を指定するところまでだった。
なんであんな中途半端で終わらせたかというと、仕事に行く時間だっただけだ。。。

動作結果は、OKだった。
検証したソースを載せたいところだが、そっちは仕事で書いているコードでやってしまったのだ。すまん。

第3引数には他の種類もある。
こちらでは、visitor()というものを使っている。
Boost.Graphに入門 - Faith and Brave - C++で遊ぼう
やっていることは同じような内容なのだが、最短経路以外にも試されている。

BoostのGraphは自由度が高いので、あれこれできてしまい、検索して見たサイトで全部やり方が違っていて「うーん、難しい・・・」と感じてしまう。

ただ、便利だし、Cから使うときもそこだけライブラリにしておけばうまいことやれるんじゃなかろうかと思う。
Makefileで、CとC++を混在させるやり方がよくわからんのだ。。。
.oを.cやら.cppに見立てる方式ではダメだから、最近はソースファイル名を列挙する方式にしているのだけど、extern "C"だけでうまく回避できるんだっけ？

いかんいかん、話が逸れてしまった。
ともかく、BoostのGraphは、大ざっぱに言えば、

• adjacency_list<>でグラフを構成する型を作る
• そのインスタンスを作って、vertexやedgeを突っ込んでいく
• アルゴリズムを実行
• 結果を得る

という流れのようだ。

そして、vertexやedgeは単純なものであれば元からある型を使えばよいし、プロパティとして複数の情報を持たせたければ構造体などを指定すればよい。
プロパティを自前で用意する場合は、重みをweight_map()で指定する。
距離の結果を得たい場合はdistance_map()を、経路の結果を得たい場合はpredecessor_map()を指定する。

私が使う範囲では、このくらいわかっておけばよさそうだ。

[c++]Boostのdijkstra_shortest_paths() - 3

第3回。前回はこちら。

前回は、グラフの有向や無向の設定だけを見た。
それ以外にグラフの設定で使いそうなのが、プロパティだろう。
経路探索する場合は、vertexとvertexのつながりだけでなく、経路の取捨選択に用いる情報を付加することが多いからだ。
よくあるのは、距離とか、そこを通るのにかかる費用とか。

距離のような単純な情報であればboostが用意していて、edgeのプロパティとして

boost::property<boost::edge_weight_t, int>

などと書いてあげればよい(これはint型の重み)。

ただ、重みの情報は1つだけど、そのルートを通るようになった場合に参照したくなる情報もある。
さっきの例でいえば、重みとしては距離を使うけれども、経路が分かった後には通行料を知りたい、などという場合だ。
そういうときは、自分でプロパティを設定できるようである。

https://boostjp.github.io/tips/graph.html#bundle-property
ここでは、structを作ってプロパティにしている。
何でもいいのかな？
まあ、C++のtemplateはマクロみたいなものだったと思うので、ちょっと種類が異なるグラフ型を作ると、それに関連する関数も新たに作ることになってしまうのだと思うが。

試して分かったが、このプロパティにする型だが、関数内に書いてはダメだった。
グローバルスコープじゃないと展開できないのだろう(私はC++にあまり詳しくないので、推測だ)。

あとは真似をしておけばdijkstraで経路探索したり、距離を表示させたりすることはできた。
しかし、サンプルではせっかくedgeにもプロパティを付けてTokyoやNagoyaを設定しているのに、表示するときには固定文字列を使っている。
かといって、map[v1].nameなどと指定するだけでは芸が無い気もする。

それに、これは2点間だからよいが、複数のvertexがあって経路探索した場合は、どの経路を通ったかをもらって、そこからプロパティを取得していきたいではないか。

https://boostjp.github.io/tips/graph.html#dijkstra-shortest-paths
経路探索して、その経路を出力するサンプルがこちらだ。
プロパティはedgeだけで、int型になっている。
そして経路出力しているところを見ると、parentという変数を使っている。
使われ方は・・・ああ、プロパティサンプルのdistanceと同じ立ち位置なのか。

ただ、プロパティのサンプルではboost::weight_map()を使っているが、ここではboost::predecessor_map()を使っている。
dijkstra_shortest_paths - boostjp
weight_map()はINで、predecessor_map()はOUTだ。
INなのに、なぜ・・・。

あ、dijkstra_shortest_paths()が長いので気がつかなかったが、引数は3つしかないんだ。
そして、第3引数はxxx_map()がドットでつながっている。

---

Boost Graph Library: Dijkstra's Shortest Paths - 1.65.0

引数が3つのタイプは、これだ。

// named parameter version
template <
         typename Graph,
         typename P,
         typename T,
         typename R>
void dijkstra_shortest_paths(
         Graph& g,
         typename graph_traits<Graph>::vertex_descriptor s,
         const bgl_named_params<P, T, R>& params
);

最後のparamsが、xxx_map()が連鎖しているところになる。
引数が多いタイプも合って、そっちはnon-named parameter versionと呼ばれている。
あまり読んでないが、ここに書いてあるxxx_map()をどんどんつないでいって、指定したいものだけ指定すれば応じた結果が得られるということだろう。

プロパティのサンプルは、こう。

weight_map().distance_map()

経路を求めるサンプルは、こう。

predecessor_map().distance_map()

プロパティのサンプルは重みを別のところから取ってくるからweight_map()を使っているのだろうか。
しかし、それならプロパティにHighwayを指定しなくてもなんとかなるんじゃ無かろうか、と思ったが、それはコンパイルエラーになった。
ではweight_map()だけ外したらどうなるかと思ったら、それはdistance_map()がわからんと言われた。
distance_map()は「UTIL/OUT」になっているから、オプション扱いで、何かの後ろに付けるということか。

weightは任意のプロパティから指定したい、経路の情報は欲しい、ということであれば、こんな感じにするとよいのか。

    std::vector

検証は、次回だ。

[c++]Boostのdijkstra_shortest_paths() - 2

意外なことに、2回目です。
前回はこちら。

グラフ - boostjp
このサイトを見て、探索はできるようになったのだが、あまりにも理解できなさすぎて、応用がまったくできない。
理論はもうあきらめるとして(いいのか。。。)、主な使い方くらいは覚えよう。

---

ツリーではなく、グラフだ。
だから、ノードやブランチではなく、vertexやedgeと呼ぶようだ。
まあ、ツリーでもedgeを使ったりするようなので、そこまで依存した言葉遣いではないのだろう。

このグラフ全体をclass adjacency_listが持つようだ。
派生して使うのではなく、templateになっていて、テンプレートパラメータを指定することでグラフ全体の設定になるようだ。

説明はサイトを読んだ方が早いだろう。
主に変更しそうなものは、グラフの有向(一方向、双方向)/無向と、カスタムプロパティかな。
双方向有向が無向と違うのは、重みが方向によって替えられたり、辺によって一方向にすることができる、というところか。
細かいけど、片方向はdirectedS、無向はundirectedSだけど、双方向はbidirectionalSと末尾が違うので注意だ。

---

こんな感じで、じわじわ読み進めていこう。

主な使い方、と最初に書いたものの、それですらいつ終わるかわからんが、やらねば終わらぬのだ。