[bitcoin] Berkeley DB

Bitcoincoreで使用されているBerkeley DBについて

– Cで記述されたソフトウェアライブラリ
– Key/value API
– SQL APIとしてSQLiteが組み込まれている
– Bツリー、ハッシュ、キュー、RECNOストレージ
– C++, Java/JNI, C#, Python, Perlなど
– Java Direct Persistence Layer
– JavaコレクションAPI
– レプリケーション
– Berkeley DB is not a relational database, although it has database features including database transactions, multiversion concurrency control and write-ahead logging. BDB runs on a wide variety of operating systems including most Unix-like and Windows systems, and real-time operating systems.
– SQLのようなデータ操作言語を持たず、データベースへのアクセスは全てサブルーチン呼び出しによって行う。しかしdbmとは異なり、データ操作機能にトランザクションやレプリケーションに対応するインタフェースが備わっている
– Berkeley DB本体が対応するプログラミング言語はCおよびC++だけだが、Perl、Python、Tcl他多くの言語にバインディングが用意されており、それらから容易に利用することができる。

概要はわかったので、使い方ですな。

Scrypt proof of workのScriptとは？

https://cryptobook.nakov.com/mac-and-key-derivation/scrypt

Scrypt (RFC 7914) is a strong cryptographic key-derivation function (KDF). It is memory-intensive, designed to prevent GPU, ASIC and FPGA attacks (highly efficient password cracking hardware).

key = Scrypt(password, salt, N, r, p, derived-key-len)

### Script Parameters
N – iterations count (affects memory and CPU usage), e.g. 16384 or 2048
r – block size (affects memory and CPU usage), e.g. 8
p – parallelism factor (threads to run in parallel – affects the memory, CPU usage), usually 1
password– the input password (8-10 chars minimal length is recommended)
salt – securely-generated random bytes (64 bits minimum, 128 bits recommended)
derived-key-length – how many bytes to generate as output, e.g. 32 bytes (256 bits)

The memory in Scrypt is accessed in strongly dependent order at each step, so the memory access speed is the algorithm’s bottleneck. The memory required to compute Scrypt key derivation is calculated as follows:

Memory required = 128 * N * r * p bytes

Choosing parameters depends on how much you want to wait and what level of security (password cracking resistance) do you want to achieve:

Script hash generator
https://8gwifi.org/scrypt.jsp

$ sudo apt-get install python-dev-is-python3
$ pip3 install scrypt

import pyscript

salt = b'aa1f2d3f4d23ac44e9c5a6c3d8f9ee8c'
passwd = b'p@$Sw0rD~7'
key = pyscript.hash(passwd, salt, 2048, 8, 1, 32)
print("Derived key:", key.hex())

Litecoin, Dogecoinとは

### Litecoin
2011年にリリースされた通貨
scryptをproof of workのアルゴリズムとして使用している

– ブロック生成時間 2.5分
– 通貨総発行量: 2140年までに8400万litecoin
– コンセンサスアルゴリズム: Scrypt proof of work
– 開発者はチャーリーリー
https://github.com/litecoin-project/litecoin

Scrypt proof of workは基本的なハッシュ関数としてscryptを使用しているHashcash証明の証明

### Dogecoin
2013年12月にリリースされたもので、Litecoinのフォークに基づくもの。
支払いやチップの利用を促すもので、通貨発行のスピードを速くしている
– ブロック生成時間 60分
– 通貨総発行量: 2015年までに1000億doge
– コンセンサスアルゴリズム: Scrypt proof of work
– Billy MarkusとJackson Palmerが開発者
https://github.com/dogecoin/dogecoin

[C++] for文のautoの書き方

std::vector<int> v;

for(std::vector<int>::const_iterator it = v.begin(), e=v.end(); it != e; ++it){
    std::cout << *it << std::endl;
}

c++11の範囲for文を使うと以下のように書ける

std::vector<int> v;

for(const auto& e: v){
    std::cout << e << std::endl;
}

### 範囲for文(range-based for statement)
配列やコンテナなど複数の要素を持つものから、全ての要素に含まれる値を取り出して処理する

#include <iostream>
using namespace std;

int main() {
    int a[] = {1, 2, 3, 4, 5};
    int sum = 0;
    for(int x : a){
        sum += x;
    }
    cout << "sum = " << sum << end;
    return 0;
}

vector要素の出力

    vector<string> v(5);
    for (int i = 0; i < v.size(); i++){
        string& x = v[i];
        cin >> x;
    }

autoは型推論を行うキーワード

    vector<string> v(5);
    for (auto& x : v){
        cin >> x;
    }

[C++] ヘッダとソースでファイルを分ける

C++ではクラスの定義とそのメンバ関数の定義をヘッダファイルとソースファイルで分割するのが一般的である

### ファイルを分割していない例
c.hpp

#ifndef C_HPP
#define C_HPP

class c {
    private:
    int m_value;

    public:
    int get() {
        return m_value;
    }

    void set(int const value){
        m_value = value;
    }
};

#endif

### ファイルを分割した例
c.hpp

#ifndef C_HPP
#define C_HPP

class c {
    private:
    int m_value;

    public:
    int get();

    void set(int const value);
};

#endif

c.cpp

#include "c.hpp"

int c::get(){
    return m_value;
}

void c::set(int const value){
    m_value = value;
}

インラインで書くこともある

#ifndef C_HPP
#define C_HPP

class c {
private:
int m_value;

public:
int get();

void set(int const value);
};

inline int c::get(){
return m_value;
}

inline void c::set(int const value){
m_value = value;
}

#endif

bitcoinのソースコードで、基本hppとcppのファイル構造になっていたが、謎が解けた。

[C++].hppとは

### .hppとは
ヘッダーファイルで.hpp、.hというファイル形式で保存
.hppはc++が入っている。.hはc言語だがc++でも使用できる

sample.hpp

#ifndef Sample_hpp
#define Sample_hpp

#include <iostream>

using namespace std;

class Sample {
    public:
        string name;
};

#endif

[bitcoin] ASICとは？

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

複数文字のローカル変数

以下に対応できるようにする
foo = 1;
bar = 2 + 3;
return foo + bar;

typedef struct LVar Lvar;

// local variable
struct LVar {
    LVar *next; // next variable or null
    char *name; // variable name
    int len; // name length
    int offset; // RBP offset
};

LVar *locals;

### if, while, for
アセンブラではcmpを使って、jumpしてend or biginに行くか処理をするか判定している

program = stmt *
stmt = expr ";"
	| "if" "(" expr ")" stmt ("else" stmt)?
	| "while" "(" expr ")" stmt
	| "for" "(" expr? ";" expr? ";" expr? ")" stmt

if

  Aをコンパイルしたコード // スタックトップに結果が入っているはず
  pop rax
  cmp rax, 0
  je  .LendXXX
  Bをコンパイルしたコード
.LendXXX:

if else

  Aをコンパイルしたコード // スタックトップに結果が入っているはず
  pop rax
  cmp rax, 0
  je  .LelseXXX
  Bをコンパイルしたコード
  jmp .LendXXX
.LelseXXX
  Cをコンパイルしたコード
.LendXXX

while

.LbeginXXX:
  Aをコンパイルしたコード
  pop rax
  cmp rax, 0
  je  .LendXXX
  Bをコンパイルしたコード
  jmp .LbeginXXX
.LendXXX:

for

  Aをコンパイルしたコード
.LbeginXXX:
  Bをコンパイルしたコード
  pop rax
  cmp rax, 0
  je  .LendXXX
  Dをコンパイルしたコード
  Cをコンパイルしたコード
  jmp .LbeginXXX
.LendXXX:

関数・ローカル変数とcompiler

以下のような関数処理もコンパイルできるようにする

sum(m, n) {
	acc = 0;
	for (i = m; i <= n; i = i + 1)
		acc = acc + i;
	return acc;
}

main() {
	return sum(1, 10);
}

Cではローカル変数はスタックに置くことにしている、グローバル変数はメモリに置く
関数ごとに呼び出されるメモリ領域を「関数フレーム」「アクティベーションレコード」という
レジスタで関数フレームを常に指しているレジスタをベースレジスタ、値をベースポインタと呼ぶ
ベースレジスタはRBPレジスタを使用する

push rbp
mov rbp, rsp
sub rsp, 16

アルファベットの小文字ならばident

// token　type 構造体
typedef enum {
    TK_RESERVED, // op
    TK_INDENT,
    TK_NUM,
    TK_EOF, // end of input
} TokenKind;

program = stmt*
stmt = expr “;”
expr = assign
assign = equality (“=” assign)?
equality = relational (“==” relational | “!=” relational)*
relational = add(“<" add | "<=" add | ">” add | “>=” add)*
add = mul (“+” mul | “-” mul)*
mul = unary (“*” unary | “/” unary)*
unary = (“+” | “-“)? primary
primary = num | “(” expr “)”

Node *assign(){
    Node *node = equality();
    if (consume("="))
        node = new_node(ND_ASSIGN, node, assign());
    return node;
}

Node *expr() {
    return assign();
}

Node *stmt() {
    Node *node = expr();
    expect(";");
    return node;
}

void program() {
    int i = 0;
    while (!at_eof())
        code[i++] = stmt();
    code[i] = NULL;
}

分割コンパイルとリンク

ファイルを分割する
– 9cc.h
– main.c
– parse.c
– codegen.c

Makefile

CFLAGS=-std=c11 -g -static
SRCS=$(wildcard *.c)
OBJS=$(SRCS:.c=.o)

9cc: $(OBJS)
		$(CC) -o 9cc $(OBJS) $(LDFLAGS)

$(OBJS): 9cc.h

clean:
		rm -f 9cc *.o *~ tmp*

.PHONY: test clean