[bitcoin] siphashとは?

多くのプログラミング言語ではDJBX33AやDJBX33Xが使われていたが、多くの言語の連想配列で利用されているハッシュ関数がSipHash
Python, Perl, Redis, Rubyなどで実装されている

### HashDos耐性のある高速ハッシュアルゴリズム
– 128bitから初期状態を作れる
– ブロックは64bit単位
– ルックアップテーブルを使わない

bitcoinではnetaddress.hで使用されている

#ifndef BITCOIN_NETADDRESS_H
#define BITCOIN_NETADDRESS_H

#if defined(HAVE_CONFIG_H)
#include <config/bitcoin-config.h>
#endif

#include <compat/compat.h>
#include <crypto/siphash.h>

siphash.h

#ifndef BITCOIN_DRYPTO_SIPHASH_H
#define BITCOIN_DRYPTO_SIPHASH_H

#include <stdint.h>

#include <span.h>
#include <uint256.h>

class CSiphasher
{
private:
    uint64_t v[4];
    uint64_t tmp;
    uint8_t count;

public:
    CSipHasher(uint64_t k0, uint64_t k1);

    CSipHasher& Write(uint64_t data);
    CSipHasher& Write(Span<const unsigned char> data);

    uint64_t Finalize() const;
}

uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val);
uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra);

siphash.cpp

#include <crypto/siphash.h>

#include <bit>

#define SIPROUND do {
    v0 += v1; v1 = std::rotl(v1, 13); v1 ^= v0;
    v0 = std::rotl(v0, 32);
    v2 += v3; v3 = std::rotl(v3, 16); v3 ^= v2;
    v0 += v3; v3 = std::rotl(v3, 21); v3 ^= v0;
    v2 += v1; v1 = std::rotl(v1, 17); v1 ^= v2;
    v2 = std::rotl(v2, 32);
} while(0)

CSipHasher::CSipHasher(uint64_t k0, uint64_t k1)
{
    v[0] = 0x736f6d6570736575ULL ^ k0;
    v[1] = 0x646f72616e646f6dULL ^ k1;
    v[2] = 0x6c7967656e657261ULL ^ k0;
    v[3] = 0x7465646279746573ULL ^ k1;
    count = 0;
    tmp = 0;
}

CSipHasher& CSiphHasher::Write(uint64_t data){
    uint64_t v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3];

    assert(coiunt % 8 == 0);

    v3 ^= data;
    SIPROUND;
    SIPROUND;
    v0 ^= data;

    v[0] = v0;
    v[1] = v1;
    v[2] = v2;
    v[3] = v3;

    count += 8;
    return *this;
}

CSipHasher& CSipHasher::Write(Span<const usigned char> data){
    uint64_t v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3];
    uint64_t t = tmp;
    uint8_t c = count;

    while (data.size() > 0){
        t == uint64_t{data.fron()} << (8 * (c % 8));
        c++;
        if((c & 7) == 0){
            v3 ^= t;
            SIPROUND;
            SIPROUND;
            v0 ^= t;
            t = 0;
        }
        data = data.subspan(1);
    }

    v[0] = v0;
    v[1] = v1;
    v[2] = v2;
    v[3] = v3;
    count = c;
    tmp = t;

    return *this;
}

uint64_t CSipHasher::Finalize() const
{
    uint64_t v0 = v[0], v1 = v[1], v2= v[2], v3 = v[3];
    uint64_t t = tmp | (((uint64_t)count) << 56);

    v3 ^= t;
    SIPROUND;
    SIPROUND;
    v0 ^= t;
    v2 ^= 0xFF;
    SIPROUND;
    SIPROUND;
    SIPROUND;
    SIPROUND;
    return v0 ^ v1 ^ v2 ^ v3;
}

uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val){
    uint64_t d = val.GetUint64(0);

    uint64_t v0 = 0x736f6d6570736575ULL ^ k0;
    uint64_t v1 = 0x646f72616e646f6dULL ^ k1;
    uint64_t v2 = 0x6c7967656e657261ULL ^ k0;
    uint64_t v3 = 0x7465646279746573ULL ^ k0 ^ d;

    SIPROUND;
    SIPROUND;
    v0 ^= d;
    d = val.GetUint64(1);
    v3 ^= d;
    SIPROUND;
    SIPROUND;
    v0 ^= d;
    d = val.GetUint64(2);
    v3 ^= d;
    SIPROUND;
    SIPROUND;
    v0 ^= d;
    v3 ^= (uint64_t{4}) << 59;
    SIPROUND;
    SIPROUND;
    v0 ^= (uint64_t{4}) << 59;
    v2 ^= 0xFF;
    SIPROUND;
    SIPROUND;
    SIPROUND;
    SIPROUND;
    return v0 ^ v1 ^ v2 ^v3;
}

uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra){

    uint64_t d == val.GetUint64(0);
    uint64_t v0 = 0x736f6d6570736575ULL ^ k0;
    uint64_t v1 = 0x646f72616e646f6dULL ^ k1;
    uint64_t v2 = 0x6c7967656e657261ULL ^ k0;
    uint64_t v3 = 0x7465646279746573ULL ^ k1 ^ d;

    SIPROUND;
    SIPROUND;
    v0 ^= d;
    d = val.GetUint64(1);
    v3 ^= d;
    SIPROUND;
    SIPROUND;
    v0 ^= d;
    d = val.GetUint64(2);
    v3 ^= d;
    SIPROUND;
    SIPROUND;
    v0 ^= d;
    d = val.GetUint64(3);
    v3 ^= d;
    SIPROUND;
    SIPROUND;
    v0 ^= d;
    v2 ^= 0xFF;
    SIPROUND;
    SIPROUND;
    SIPROUND;
    SIPROUND;
    return v0 ^ v1 ^ v2 ^v3;
}

[bitcoin]Signetとは?

Signetは、Bitcoinのテストネットとは異なり、特定のプロジェクトや開発者が制御できる独自のテストネットワーク
cmd, faucet, addr, passwordなどのオプションがある

getcoins.py

import argparse
import io
import requests
import subprocess
import sys
import xml.etree.ElementTree

DEFAULT_GLOBAL_FAUCET = 'https://signetfaucet.com/claim'
DEFAULT_GLOBAL_CAPTCHA = 'https://signetfaucet.com/captcha'
GLOBAL_FIRST_BLOCK_HASH = '00000086d6b2636cb2a392d45edc4ec544a10024d30141c9adf4bfd9de533b53'

# braille unicode block
BASE = 0x2800
BIT_PER_PIXEL = [
    [0x01, 0x08],
    [0x02, 0x10],
    [0x04, 0x20],
    [0x40, 0x80],
]
BW = 2
BH = 4

# imagemagick or compatible fork (used for converting SVG)
CONVERT = 'convert'

class PPMImage:
    '''
    Load a PPM image (Pillow-ish API).
    '''
    def __init__(self, f):
        if f.readline() != b'P6\n':
            raise ValueError('Invalid ppm format: header')
        line = f.readline()
        (width, height) = (int(x) for x in line.rstrip().split(b' '))
        if f.readline() != b'255\n':
            raise ValueError('Invalid ppm format: color depth')
        data = f.read(width * height * 3)
        stride = width * 3
        self.size = (width, height)
        self._grid = [[tuple(data[stride * y + 3 * x:stride * y + 3 * (x + 1)]) for x in range(width)] for y in range(height)]

    def getpixel(self, pos):
        return self._grid[pos[1]][pos[0]]

def print_image(img, threshold=128):
    '''Print black-and-white image to terminal in braille unicode characters.'''
    x_blocks = (img.size[0] + BW - 1) // BW
    y_blocks = (img.size[1] + BH - 1) // BH

    for yb in range(y_blocks):
        line = []
        for xb in range(x_blocks):
            ch = BASE
            for y in range(BH):
                for x in range(BW):
                    try:
                        val = img.getpixel((xb * BW + x, yb * BH + y))
                    except IndexError:
                        pass
                    else:
                        if val[0] < threshold:
                            ch |= BIT_PER_PIXEL[y][x]
            line.append(chr(ch))
        print(''.join(line))

parser = argparse.ArgumentParser(description='Script to get coins from a faucet.', epilog='You may need to start with double-dash (--) when providing bitcoin-cli arguments.')
parser.add_argument('-c', '--cmd', dest='cmd', default='bitcoin-cli', help='bitcoin-cli command to use')
parser.add_argument('-f', '--faucet', dest='faucet', default=DEFAULT_GLOBAL_FAUCET, help='URL of the faucet')
parser.add_argument('-g', '--captcha', dest='captcha', default=DEFAULT_GLOBAL_CAPTCHA, help='URL of the faucet captcha, or empty if no captcha is needed')
parser.add_argument('-a', '--addr', dest='addr', default='', help='Bitcoin address to which the faucet should send')
parser.add_argument('-p', '--password', dest='password', default='', help='Faucet password, if any')
parser.add_argument('-n', '--amount', dest='amount', default='0.001', help='Amount to request (0.001-0.1, default is 0.001)')
parser.add_argument('-i', '--imagemagick', dest='imagemagick', default=CONVERT, help='Path to imagemagick convert utility')
parser.add_argument('bitcoin_cli_args', nargs='*', help='Arguments to pass on to bitcoin-cli (default: -signet)')

args = parser.parse_args()

if args.bitcoin_cli_args == []:
    args.bitcoin_cli_args = ['-signet']


def bitcoin_cli(rpc_command_and_params):
    argv = [args.cmd] + args.bitcoin_cli_args + rpc_command_and_params
    try:
        return subprocess.check_output(argv).strip().decode()
    except FileNotFoundError:
        raise SystemExit(f"The binary {args.cmd} could not be found")
    except subprocess.CalledProcessError:
        cmdline = ' '.join(argv)
        raise SystemExit(f"-----\nError while calling {cmdline} (see output above).")


if args.faucet.lower() == DEFAULT_GLOBAL_FAUCET:
    # Get the hash of the block at height 1 of the currently active signet chain
    curr_signet_hash = bitcoin_cli(['getblockhash', '1'])
    if curr_signet_hash != GLOBAL_FIRST_BLOCK_HASH:
        raise SystemExit('The global faucet cannot be used with a custom Signet network. Please use the global signet or setup your custom faucet to use this functionality.\n')
else:
    # For custom faucets, don't request captcha by default.
    if args.captcha == DEFAULT_GLOBAL_CAPTCHA:
        args.captcha = ''

if args.addr == '':
    # get address for receiving coins
    args.addr = bitcoin_cli(['getnewaddress', 'faucet', 'bech32'])

data = {'address': args.addr, 'password': args.password, 'amount': args.amount}

# Store cookies
# for debugging: print(session.cookies.get_dict())
session = requests.Session()

if args.captcha != '': # Retrieve a captcha
    try:
        res = session.get(args.captcha)
        res.raise_for_status()
    except requests.exceptions.RequestException as e:
        raise SystemExit(f"Unexpected error when contacting faucet: {e}")

    # Size limitation
    svg = xml.etree.ElementTree.fromstring(res.content)
    if svg.attrib.get('width') != '150' or svg.attrib.get('height') != '50':
        raise SystemExit("Captcha size doesn't match expected dimensions 150x50")

    # Convert SVG image to PPM, and load it
    try:
        rv = subprocess.run([args.imagemagick, 'svg:-', '-depth', '8', 'ppm:-'], input=res.content, check=True, capture_output=True)
    except FileNotFoundError:
        raise SystemExit(f"The binary {args.imagemagick} could not be found. Please make sure ImageMagick (or a compatible fork) is installed and that the correct path is specified.")

    img = PPMImage(io.BytesIO(rv.stdout))

    # Terminal interaction
    print_image(img)
    print(f"Captcha from URL {args.captcha}")
    data['captcha'] = input('Enter captcha: ')

try:
    res = session.post(args.faucet, data=data)
except Exception:
    raise SystemExit(f"Unexpected error when contacting faucet: {sys.exc_info()[0]}")

# Display the output as per the returned status code
if res:
    # When the return code is in between 200 and 400 i.e. successful
    print(res.text)
elif res.status_code == 404:
    print('The specified faucet URL does not exist. Please check for any server issues/typo.')
elif res.status_code == 429:
    print('The script does not allow for repeated transactions as the global faucet is rate-limitied to 1 request/IP/day. You can access the faucet website to get more coins manually')
else:
    print(f'Returned Error Code {res.status_code}\n{res.text}\n')
    print('Please check the provided arguments for their validity and/or any possible typo.')

[bitcoin] headerssync-paramsって何?

Readmeを読むと以下のように書いている
A script to generate optimal parameters for the headerssync module (src/headerssync.cpp). It takes no command-line
options, as all its configuration is set at the top of the file. It runs many times faster inside PyPy. Invocation:
つまり、node間でのヘッダー情報のやり取りのことだ。c++ファイルのヘッダではない。stateで、 PRESYNC、REDOWNLOAD、FINALとある。

src/headerssync.h, src/headerssync.cpp を見てみる。
### headerssync.h
A compressed CBlockHeader, which leaves out the prevhash
HeadersSyncState
We wish to download a peer’s headers chain in a DoS-resistant way.
* – In the first download phase, called pre-synchronization, we can calculate
* the work on the chain as we go (just by checking the nBits value on each
* header, and validating the proof-of-work).
In phase 1 (presync)
In phase 2 (redownload)

#### headerssync.cpp
// The two constants below are computed using the simulation script in
// contrib/devtools/headerssync-params.py.
m_max_commitments = 6*(Ticks(NodeClock::now() – NodeSeconds{std::chrono::seconds{chain_start->GetMedianTimePast()}}) + MAX_FUTURE_BLOCK_TIME) / HEADER_COMMITMENT_PERIOD;

downloadはこれでやってる?

    if (m_current_chain_work >= m_minimum_required_work) {
        m_redownloaded_headers.clear();
        m_redownload_buffer_last_height = m_chain_start->nHeight;
        m_redownload_buffer_first_prev_hash = m_chain_start->GetBlockHash();
        m_redownload_buffer_last_hash = m_chain_start->GetBlockHash();
        m_redownload_chain_work = m_chain_start->nChainWork;
        m_download_state = State::REDOWNLOAD;
        LogPrint(BCLog::NET, "Initial headers sync transition with peer=%d: reached sufficient work at height=%i, redownloading from height=%i\n", m_id, m_current_height, m_redownload_buffer_last_height);
    }

downloadのstatusに応じて処理しているのはわかるが、getHashの処理とかはheaderssync.cppの中には書いてないように見えるがどこでやってるんだろうか?

あと、基本的に、HeadersSyncState::${処理}と書かれていますね。
なんか凄いな…

bitcoin.confの構成

mainnet=1               # mainnetを利用する
txindex=1               # indexを作成して全てのトランザクションIDを参照可能にする
server=1                # JSON RPCサーバとしてコマンドを受け付ける
rest=1                  # REST インターフェースを有効にする
rpcuser= "Username"     # JSON RPCのためのユーザ名
rpcpassword= "Password" # JSON RPCのためのパスワード
rpcport=8332            # JSON RPC用ポート番号

gen-bitcoin-conf.sh

export LC_ALL=C
TOPDIR=${TOPDIR:-$(git rev-parse --show-toplevel)}
BUILDDIR=${BUILDDIR:-$TOPDIR}
BINDIR=${BINDIR:-$BUILDDIR/src}
BITCOIND=${BITCOIND:-$BINDIR/bitcoind}
SHARE_EXAMPLES_DIR=${SHARE_EXAMPLES_DIR:-$TOPDIR/share/examples}
EXAMPLE_CONF_FILE=${EXAMPLE_CONF_FILE:-$SHARE_EXAMPLES_DIR/bitcoin.conf}

[ ! -x "$BITCOIND" ] && echo "$BITCOIND not found or not executable." && exit 1

DIRTY=""
VERSION_OUTPUT=$($BITCOIND --version)
if [[ $VERSION_OUTPUT == *"dirty"* ]]; then
  DIRTY="${DIRTY}${BITCOIND}\n"
fi

if [ -n "$DIRTY" ]
then
  echo -e "WARNING: $BITCOIND was built from a dirty tree.\n"
  echo -e "To safely generate a bitcoin.conf file, please commit your changes to $BITCOIND, rebuild, then run this script again.\n"
fi

echo 'Generating example bitcoin.conf file in share/examples/'

# create the directory, if it doesn't exist
mkdir -p "${SHARE_EXAMPLES_DIR}"

# create the header text
cat > "${EXAMPLE_CONF_FILE}" << 'EOF'
##
## bitcoin.conf configuration file.
## Generated by contrib/devtools/gen-bitcoin-conf.sh.
##
## Lines beginning with # are comments.
## All possible configuration options are provided. To use, copy this file
## to your data directory (default or specified by -datadir), uncomment
## options you would like to change, and save the file.
##


### Options
EOF

# parse the output from bitcoind --help
# adding newlines is a bit funky to ensure portability for BSD
# see here for more details: https://stackoverflow.com/a/24575385
${BITCOIND} --help \
    | sed '1,/Print this help message and exit/d' \
    | sed -E 's/^[[:space:]]{2}\-/#/' \
    | sed -E 's/^[[:space:]]{7}/# /' \
    | sed -E '/[=[:space:]]/!s/#.*$/&=1/' \
    | awk '/^#[a-z]/{x=$0;next}{if (NF==0) print x"\n",x="";else print}' \
    | sed 's,\(^[[:upper:]].*\)\:$,\
### \1,' \
    | sed 's/[[:space:]]*$//' >> "${EXAMPLE_CONF_FILE}"

# create the footer text
cat >> "${EXAMPLE_CONF_FILE}" << 'EOF'

# [Sections]
# Most options will apply to all networks. To confine an option to a specific
# network, add it under the relevant section below.
#
# Note: If not specified under a network section, the options addnode, connect,
# port, bind, rpcport, rpcbind, and wallet will only apply to mainnet.

# Options for mainnet
[main]

# Options for testnet
[test]

# Options for signet
[signet]

# Options for regtest
[regtest]
EOF

sedの使い方

1.rakus rakus
2.rakus

$ sed -e ‘s/rakus/RAKUS/g’ sample.tx
1.RAKUS RAKUS
2.RAKUS

-Eのところは複数指定にしている?

${BITCOIND} --help \
    | sed '1,/Print this help message and exit/d' \
    | sed -E 's/^[[:space:]]{2}\-/#/' \
    | sed -E 's/^[[:space:]]{7}/# /' \
    | sed -E '/[=[:space:]]/!s/#.*$/&=1/' \
    | awk '/^#[a-z]/{x=$0;next}{if (NF==0) print x"\n",x="";else print}' \
    | sed 's,\(^[[:upper:]].*\)\:$,\
### \1,' \
    | sed 's/[[:space:]]*$//' >> "${EXAMPLE_CONF_FILE}"

circular-dependencies : 循環参照

あるファイルを require したときにその結果が空のオブジェクトとして返される問題
module.exports first, lazy require, dependency injectionなどの解決方法がある

import sys
import re

MAPPING = {
    'core_read.cpp': 'core_io.cpp',
    'core_write.cpp': 'core_io.cpp',
}

# Directories with header-based modules, where the assumption that .cpp files
# define functions and variables declared in corresponding .h files is
# incorrect.
HEADER_MODULE_PATHS = [
    'interfaces/'
]

def module_name(path):
    if path in MAPPING:
        path = MAPPING[path]
    if any(path.startswith(dirpath) for dirpath in HEADER_MODULE_PATHS):
        return path
    if path.endswith(".h"):
        return path[:-2]
    if path.endswith(".c"):
        return path[:-2]
    if path.endswith(".cpp"):
        return path[:-4]
    return None

files = dict()
deps: dict[str, set[str]] = dict()

RE = re.compile("^#include <(.*)>")

# Iterate over files, and create list of modules
for arg in sys.argv[1:]:
    module = module_name(arg)
    if module is None:
        print("Ignoring file %s (does not constitute module)\n" % arg)
    else:
        files[arg] = module
        deps[module] = set()

# Iterate again, and build list of direct dependencies for each module
# TODO: implement support for multiple include directories
for arg in sorted(files.keys()):
    module = files[arg]
    with open(arg, 'r', encoding="utf8") as f:
        for line in f:
            match = RE.match(line)
            if match:
                include = match.group(1)
                included_module = module_name(include)
                if included_module is not None and included_module in deps and included_module != module:
                    deps[module].add(included_module)

# Loop to find the shortest (remaining) circular dependency
have_cycle: bool = False
while True:
    shortest_cycle = None
    for module in sorted(deps.keys()):
        # Build the transitive closure of dependencies of module
        closure: dict[str, list[str]] = dict()
        for dep in deps[module]:
            closure[dep] = []
        while True:
            old_size = len(closure)
            old_closure_keys = sorted(closure.keys())
            for src in old_closure_keys:
                for dep in deps[src]:
                    if dep not in closure:
                        closure[dep] = closure[src] + [src]
            if len(closure) == old_size:
                break
        # If module is in its own transitive closure, it's a circular dependency; check if it is the shortest
        if module in closure and (shortest_cycle is None or len(closure[module]) + 1 < len(shortest_cycle)):
            shortest_cycle = [module] + closure[module]
    if shortest_cycle is None:
        break
    # We have the shortest circular dependency; report it
    module = shortest_cycle[0]
    print("Circular dependency: %s" % (" -> ".join(shortest_cycle + [module])))
    # And then break the dependency to avoid repeating in other cycles
    deps[shortest_cycle[-1]] = deps[shortest_cycle[-1]] - set([module])
    have_cycle = True

sys.exit(1 if have_cycle else 0)

[bitcoin] bitcoincoreのファイル構造 [その1]

まずGithubから bitcoincore のソースコードを clone してきます。
github上で見てもいいんですが、なんとなくローカルに落としたいですよね。。

$ git clone https://github.com/bitcoin/bitcoin.git
$ $ tree -L 3 -d
.
└── bitcoin
├── build-aux
│ └── m4
├── build_msvc
│ ├── bench_bitcoin
│ ├── bitcoin-cli
│ ├── bitcoind
│ ├── bitcoin-qt
│ ├── bitcoin-tx
│ ├── bitcoin-util
│ ├── bitcoin-wallet
│ ├── libbitcoin_cli
│ ├── libbitcoin_common
│ ├── libbitcoin_consensus
│ ├── libbitcoin_crypto
│ ├── libbitcoin_node
│ ├── libbitcoin_qt
│ ├── libbitcoin_util
│ ├── libbitcoin_wallet
│ ├── libbitcoin_wallet_tool
│ ├── libbitcoin_zmq
│ ├── libleveldb
│ ├── libminisketch
│ ├── libsecp256k1
│ ├── libtest_util
│ ├── libunivalue
│ ├── msbuild
│ ├── test_bitcoin
│ └── test_bitcoin-qt
├── ci
│ ├── lint
│ ├── retry
│ └── test
├── contrib
│ ├── completions
│ ├── debian
│ ├── devtools
│ ├── guix
│ ├── init
│ ├── linearize
│ ├── macdeploy
│ ├── message-capture
│ ├── qos
│ ├── seeds
│ ├── shell
│ ├── signet
│ ├── testgen
│ ├── tracing
│ ├── verify-binaries
│ ├── verify-commits
│ ├── windeploy
│ └── zmq
├── depends
│ ├── builders
│ ├── hosts
│ ├── packages
│ └── patches
├── doc
│ ├── design
│ ├── man
│ ├── policy
│ └── release-notes
├── share
│ ├── examples
│ ├── pixmaps
│ ├── qt
│ └── rpcauth
├── src
│ ├── bench
│ ├── common
│ ├── compat
│ ├── config
│ ├── consensus
│ ├── crc32c
│ ├── crypto
│ ├── index
│ ├── init
│ ├── interfaces
│ ├── ipc
│ ├── kernel
│ ├── leveldb
│ ├── logging
│ ├── minisketch
│ ├── node
│ ├── policy
│ ├── primitives
│ ├── qt
│ ├── rpc
│ ├── script
│ ├── secp256k1
│ ├── support
│ ├── test
│ ├── univalue
│ ├── util
│ ├── wallet
│ └── zmq
└── test
├── functional
├── fuzz
├── lint
├── sanitizer_suppressions
└── util

各ディレクトリ、各機能ごとの役割を細く見て行くことが必要ですね。

[bitcoin] ASICとは?

ASICとは
L 半導体集積回路の一つで、ある特定の機器や用途のために、必要な機能を組み合わせて設計、製造されるもの。
L フルカスタムICとセミカスタムICがある

[LightningNetwork] pathfinding

支払い人から受取人へのパスを見つけることをpathfindingと呼ぶ
PathfindingはBOLTでは定義されておらず、さまざまなアルゴリズムを選択できる
平均チャネル数は8.8で上位のノードは2000のチャネル数もある
pathfindingはグラフトラバーサルに分類される
MCFPと呼ばれるコストを最小にしながら特定のフローを実現

パス候補のリストを作成し、何らかの関数でフィルタリングしてソートする。続いて、送信できるパスが見つかるまで、パスのプロービングを行う
チャネルグラフの構築で、node_announcementでIP情報が含まれているため、地図を作成できる
マルチパートペイメントでpathを柔軟化できる

[LightningNetwork] オニオンルーティング

オニオンルーティングはTorで使われている暗号化通信の手法
メッセージの送信者が入れ子になった暗号化の層を作成
origin nodeとfinal nodeがある

共通シークレット、セッションの秘密鍵、公開鍵からECDHアルゴリズムにより、rho, mu, um, padの鍵を生成する
オニオンをラッピングする

### ゴシッププロトコル(共有)
LNのイニシャルピアディスカバリはDNSに基づく
チャネルを、チェーン内の位置に基づいて参照する

[LightningNetwork] ルーティング

パス上の中間ノードをルーティングノードという
ライトニングネットワークはHash Time-Locked Contractを採用している
経路探索はチャネルグラフを調べる
ルーティングは経路探索によって事前に選択されたパスを使って、AからBにペイメントを転送しようとするネットワーク経由の一連のやり取り

エスクロー契約にして、ペイメントハッシュでやり取りを行う
契約には期限を設定する
ノードが預託を行うに十分な資金を持っている必要がある
PTLC(Point Time-Locked Contract)はSchnorr signature
インボイスをAliceからDinaにリクエストし、発行する

### HTLC(Hash Time-Lock Contract)
インボイスに暗号学的ハッシュ関数が入っている
H = Sha256(R)
OP_HASH160 OP_EQUALVERIFY
ペイメントプリイメージとの比較
受取人とマッチする公開鍵とその署名をスクリプトに入れる
OP_SHA256 OP_EQUALVERIFY OP_ChECKSIG