bitcoin-coreのtestnetのノードを起動

$ bitcoin-core.daemon -testnet -prune=1000

$ df -h
Filesystem Size Used Avail Use% Mounted on
devtmpfs 459M 0 459M 0% /dev
tmpfs 476M 0 476M 0% /dev/shm
tmpfs 476M 49M 427M 11% /run
tmpfs 476M 0 476M 0% /sys/fs/cgroup
/dev/vda2 25G 21G 2.3G 91% /
/dev/loop0 116M 116M 0 100% /var/lib/snapd/snap/bitcoin-core/145
/dev/loop2 56M 56M 0 100% /var/lib/snapd/snap/core18/2790
/dev/loop1 41M 41M 0 100% /var/lib/snapd/snap/snapd/20290
tmpfs 96M 4.0K 96M 1% /run/user/1000

100GBに拡張したはずだけど、vda2は25Gのままだな…
ただ、testnetの場合はかなり早い

$ bitcoin-core.cli -getinfo -testnet
Chain: test
Blocks: 1579532
Headers: 2571357
Verification progress: ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒░░░░░ 77.2822%
Difficulty: 1

Network: in 0, out 10, total 10
Version: 250100
Time offset (s): 0
Proxies: n/a
Min tx relay fee rate (BTC/kvB): 0.00001000

Warnings: (none)

$ pwd
/home/alma/snap/bitcoin-core/common/.bitcoin

$ ls
anchors.dat chainstate mempool.dat testnet3
banlist.json debug.log peers.dat wallets
blocks fee_estimates.dat settings.json

banlist.dat: 禁止ノードのIPアドレス、サブネットのリスト。
bitcoin.conf: Bitcoin Coreの設定ファイル。接続するのがmainnetかtestnetかなどを指定することができる。自動生成されず、自分で作成する必要がある。
bitcoin.pid: bitcoindをデーモンで起動した際のPIDファイル。
blocks/blk000??.dat: ブロックの生データ。ウォレット内の欠落しているトランザクションを再スキャンする際や、同期中の他のノードにブロックデータを提供する際などの利用される。
blocks/rev000??.dat: blocksディレクトリ内に格納されている、undoデータ。
blocks/index/*: 既知のブロックのメタデータやその格納場所の情報が格納されたLevelDBのDB。
chainstate: 現在未使用のトランザクションアウトプット（UTXO)とそのトランザクションのメタデータをコンパクトにしたLebelDBのDB。受信したブロックやトランザクションを検証するために利用される。
database: Berkeley DBのジャーナリングファイルが格納されるディレクトリ。
db.log: ウォレットデータベースのログファイル。
debug.log: Bitcoinの詳細なログ。
fee_estimates.dat: 手数料と優先順位を予測するための統計。プログラムのシャットダウン時に保存され、起動時に読み込まれる。
mempool.dat: メモリプール内のトランザクションのダンプ。
peers.dat: 再接続を容易にするためのピア情報用のストレージ。ビットコイン専用のフォーマットを使用している。
wallet.dat: 鍵やトランザクション、メタデータ、オプション情報が保存されるBerkelay DBのデータベースファイル。
.cookie: セッションRPC認証クッキー。クッキー認証が使用されている時に書き込まれ、シャットダウン時に削除される。
onionprivatekey: キャッシュされたTor匿名通信サービスの秘密鍵。
testnet3: testnetモードでbitcoindを起動した際のデータ。
regtest: regtestモードでbitcoindを起動した際のデータ。regtestディレクトリを削除してBitcoin Coreを再起動すると、新しいregtest環境になる。
.lock: Berkeley DBのロックファイル。

bitcoin.confはここに書くのね。

[LightningNetwork] p2pの暗号化

1. ゴシッププロトコルを使ってトポロジー情報を伝播する広い範囲のp2p
2. チャネルパートナー間のペイメントチャネルのネットワーク
ピア間の通信はLNメッセージが使われる
Noise Protocol Frameworkを使って暗号化される

### ビットコインとの比較
LNでは支払い受取人がインボイスを作成する。インボイスは1
ライトニングペイメントはBTCのトランザクションに相当
UTXOは必要なく、ペイメントによって残高が更新されて再配分　AMPやMPPを使うと複数のライトニングをまとめられる
マイニングはないがルーティング手数料が課される
ライトニングネットワークのリソースはchannel liquidityとchannel connectivity
LNはmillisatoshi

[LightningNetwork] pathfinding

ソースベースのpthfindingは有効なソリューションの一つ
十分な流動性を持つパスが見つかるまで、様々なパスを反復的に試す
チャネルパートナーであれば、経路探索は難しくはない

### オニオンルーティング
オニオンルーティングプロトコルを使用する SPHINX Mix Formatと呼ばれる
そのノードだけが複合できる層を使って暗号化するのを繰り返す
誰が支払いを開始・行うかをノードが知ることができない
オニオンのホップは最大26、HMACで暗号化

### ペイメント転送アルゴリズム
update_add_htlcメッセージを送信する

[LightningNetwork] ペイメントの配送

### p2pゴシッププロトコル
チャネルアナウンスはp2pのgossip protocolによる伝播される
channel_announcementメッセージでピアに公表
node_announcementメッセージで公表する目的で使われる

支払人から受取人までのパスを見つけ出すことをpathfindingと呼び、そのパスを使ってペイメントを転送することをルーティングと呼ぶ

pathfindingはソースベースプロトコル、支払いのルーテインングにオニオンルーティングと呼ぶ

[LightningNetwork] インボイス

インボイスは支払い指示書
ペイメントID(ペイメントハッシュ)、受取人、金額、オプションなどが含まれる
通常インボイスはbech32エンコードかQRコードとしてエンコードされる
インボイスには請求金額と受取人の署名が含まれる。支払い人はこの署名を使って公開鍵(ノードID)を取得する
LNはインボイスに基づきペイメントを送信
有効期限を設定することもできる

### ペイメントハッシュ
ランダムな数字r
H = sha256(r)

[LightningNetwork] ペイメントチャネル

チャネルパートナーとは2つのノード間の金銭関係、2of2マルチシグの暗号プロトコルによって管理(自分と相手)
チャネルの残高がエンコードされ、その残高をどのように分配するかが定義される
トランザクションシーケンスのトランザクションはスプリクト言語を使う
チャネルを開いた時にコミットされるビットコインの量
チャネル経由で同時に送信できる未実行・実行中のルーティングペイメントの数も制限される
ビットコインブロックチェーンに記録されるのは最終残高のみ

### ファンディングトランザクション
1人がマルチシグアドレスにbitcoinを送金することでペイメントチャネルに資金を預ける
これをchannel capacityと呼ぶ

### チャネルの開き方
2つの公開鍵を使って2of2マルチシグアドレスを作成
払い戻しトランザクションはコミットメントトランザクションと呼ばれる

1. open_channelメッセージでBobに通知
2. accept_channelメッセージでAliceに送信
3. pubkey pubkey 2 CHECKMULTISIGでトランザクションを作成
4. funding_createdでBobに送信
5. コミットメントトランザクションを作成
6. Bobが funding_signedメッセージでAliceに返す
7. 署名交換後にAliceがブロードキャスト

### 古い状態を使った不正
古いコミットメントトランザクションが送信された場合は、罰を与えることができるように作られれている
失効のメカニズム:timelock delayとrevocation secretがペイメントにある
新しいコミットメントの際に、古いコミットメントトランザクションを失効させる
※失効シークレットの管理と格納はLNの最も複雑な部分の1つである

### チャネルを公表・クローズ
チャネルを公表するとルーティング手数料を獲得できる
チャネルを閉じるときはトランザクション手数料がかかる
クローズには相互クローズ、強制クローズ、プロトコル違反などある

LightningNetwork 概要

LNを使うには、ニーズに合ったLNウォレットを選ぶ必要がある
L Eclairウォレットを選択する

ライトニングネットワークノードはウォレットである
他のライトニングノードとP2P方式で通信しなければならない
LNはbitcoin nodeにアクセスし資金を保全する必要がある

ライトニングエクスプローラ
https://1ml.com/
その他にもACINQ, Amboss Space, Fiatjaf, hashXPなどLNエクスプローラがある

### ライトニングウォレット
keystore: secret keyを保持
Lightning Network Node
Bitcoin node
database map: ノードとチャネルのマップ
channel manager: LNチャネルを開閉できるコンポーネント
close-up system: チャネルのパスを調べるコンポーネント
※鍵の管理を外部に委託するウォレットをcustodial walletと呼ぶ。鍵をどのように管理するかでウォレットを選択する。またLN Walletが使うのはfull nodeか第三者のnodeかなどを見極める必要がある
Lightweight, Noneなどはcustodial walletになる。自己管理型かどうかを選択する

Neutrino: ビットコインノードを実行しないwallet, neutrinoプロトコルを使ってアクセス
Electrum: ビットコインノードを実行しないwallet

[bitcoin] ライトニングネットワーク概要

ライトニングネットワークはビットコインの支払いをオフチェーンで実行できるようにするP2Pネットワーク
ビットコインのブロックチェーンにコミットされない、オフチェーンペイメントと呼ぶ
ルーティングネットワークで、支払人から受取人までのパスに沿って各ペイメントチャネルをホップしていく。
LNと略される
ビットコインをベースとしたセカンドレイヤーテクノロジ
チャネルを書き換える1種類のトランザクションにスプライシングと呼ばれるものがあり、チャネルにコミットされている資金を追加または削除に使うことができる
LNの2つのノード間の金銭関係をペイメントチャネルと呼ぶ
ペイメントは送信者から受信者までのパスを辿る1つ以上のペイメントチャネル経由でルーティングされる
LNではビットコイントランザクションを使って資金を移動する

### fairness protocol
互いに信頼していない参加者が公正な結果を得られるようにするためにインセンティブ、ディスインセンティブを利用する
e.g. 2人で均等に分けたい場合は、参加者で分割者と選択者の役割に分ける, hash function, digital signature, encryption/decryption

– チャネルに資金を預けるユーザは、ファンディングトランザクションを公開する前に払い戻しトランザクションが署名されていることを確認する
– チャネルが新しい状態に遷移する度に、誰かが古い状態をブロードキャストしようとしたら残高を全て失って罰を受ける
– ペイメントを転送するユーザは、資金の転送をコミットした場合、1つ前のノードから返金または報酬を受け取れる
– ビットコインを利用するのは最初に読み込む時と、決済(settle)時にビットコインをライトニングから取り出す時のみ。トランザクションは公開されないのでプライベートになる
– LMはThe Onion Routerのオニオンルーティングを使う

SRM452 HamiltonPath

There are N cities in a country, numbered 0 to N-1. Each pair of cities is connected by a bidirectional road.

John plans to travel through the country using the following rules:
He must start in one city and end in another city after travelling exactly N-1 roads.
He must visit each city exactly once.
You are given a String[] roads. If the j-th character of the i-th element of roads is ‘Y’, he must travel the road that connects city i and city j.
For example, if there are three cities, and he wants to travel the road between city 0 and city 1, there are 4 possible paths: 0->1->2, 1->0->2, 2->0->1, 2->1->0. Paths 0->2->1 and 1->2->0 are not allowed because they do not allow him to travel the road between city 0 and city 1.

Return the number of paths he can choose, modulo 1,000,000,007.

#include <string>
#include <vector>
using namespace std;

bool visited[50] = {false};

class HamiltonPath {
    public:
        vector <string> roads;

        int countPaths(vector <string> roads){
            int group=0, free=0;
            int connect[50] = {0};

            long long sum = 1;

            this->roads = roads;

            for(int i=0; i<roads.size(); i++){
                int y = 0;
                for(int j=0; j<roads[i].size(); j++){
                    if(roads[i].substr(j, 1) == "Y"){
                        if( 2 < ++y) return 0;
                    }
                }
                connect[i] = y;
            }

            for (int i = 0; i<roads.size(); i++){
                if(connect[i]==0){
                    visited[i] = true;
                    free++;
                } else if(connect[i] == 1 && !visited[i]){
                    group++;
                    dfs(i);
                }
            }
            for (int i=0; i<roads.size(); i++)
                if(!visited[i]) return 0;
            for (int i=0; i<group+free; i++)
                sum = sum * (i+1) % 100000007;
            for (int i=0; i<group; i++)
                sum = sum * 2 % 100000007;
            return (int)sum;
        }

        void dfs(int city){
            visited[city] = true;
            for(int i=0; i < roads[city].size(); i++){
                if(road[city].substr(i, 1) == "Y" && !visited[i]) dfs(i);
            }
        }
};

SRM443 CirclesCountry

Circles Country is a country that contains several circular-shaped districts. Some districts may be situated inside other districts, but their borders do not intersect or touch. Qatam is a resident of Circles Country. When he travels between two locations, he always tries to cross the fewest number of district borders as possible because crossing borders is usually a laborious task.

Imagine Circles Country as an infinite plane. You are given int[]s X, Y and R, where (X[i], Y[i]) are the coordinates of the i-th district’s center and R[i] is its radius. Qatam is currently at point (x1,y1) and he needs to get to point (x2,y2). Neither of these points lies on a district border. Return the minimal number of district borders he must cross to get to his destination.

#include <vector>
using namespace std;

class CirclesCountry {
    public:
        int leastBorders(vector <int> X, vector <int> Y, vector <int>R, int x1, int y1, int x2, int y2){
            int num = 0;

            for (int i = 0; i < X.size(); i++){
                if (inside(X[i], Y[i], x1, y1, R[i]) != (inside(X[i], Y[i], x2, y2, R[i])))
                    num++;
            }

            bool inside(int x1, int y1, int x2, int y2, int r){
                return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r * r;
            }
        }
};

(x1 – x2) * (x1 – x2) + (y1 – y2) * (y1 – y2) <= r * r;が x1y1とx2y2で正しくなければ境界線が1つとなる。すなわち、insideでは片方が円の中にあり、片方が円の外に点があるかどうかを判定している。コーディングというより問題の理解力の方が求められるか...