More Related Content
Similar to 高速な暗号実装のためにしてきたこと
Similar to 高速な暗号実装のためにしてきたこと (20)
More from MITSUNARI Shigeo
More from MITSUNARI Shigeo (20)
高速な暗号実装のためにしてきたこと
- 7. • 理論
• ペアリングベースによる効率のよい手法の提案
• 国際学会に採択（6月頃発表予定）
• 実装
• https://github.com/herumi/mcl
• C++/Xbyak/LLVMによるサーバ向け実装
• https://github.com/herumi/she-wasm
• JavaScript（WebAssembly）によるブラウザ向け実装
• https://herumi.github.io/she-wasm/she-demo.html （デモ）
理論と実装
7 / 40
- 9. • Zcash（暗号通貨）
• https://z.cash/
• 取り引きの追跡ができない匿名性の強い通貨
• ペアリングベースのゼロ知識証明（zkSNARKs）を用いて実現
• 入力を隠したまま正しい計算をしたかを検証可能
• DFINITY（ベンチャー）
• https://dfinity.org/
• Ethereumを拡張する仮想ブロックチェーンコンピュータ（?）
• ペアリングベースのBLS署名を用いて実現
• 秘密分散された公開鍵を用いて署名・集約が可能
応用例2
9 / 40
- 10. • 上位層はC++, 最下位層は独自アセンブリ言語 / LLVM
mclのモジュール構成
準同型暗号
ペアリング
楕円曲線
有限体
Xbyak
for x64
LLVM
for Aarch64
WebAssembly
BLS署名
10 / 40
- 12. • Cとアセンブラ（以下asm）との連係が面倒
• 構造体が配列を含む場合
• これぐらいならちょっとしたツールで対応もできるが
• template<size_t N>struct A{ int v[N];};とかだと結構辛い
• asmの擬似命令を覚えるのが面倒
• %macro, %if, %imacro, etc...
• アセンブラによって異なる
• 構文が後づけなものが多く分かりにくい
従来のアセンブラの不満なところ（1/2）
struct A {
int a;
int b[4];
int c;
};
%define offset_A_a 0
%define offset_A_b 4
%define offset_A_c 20
なんらかの方法で
asm側に伝える
12 / 40
- 13. • インラインアセンブラ
• 64-bit Visual Studioでは廃止された
• gccのインラインアセンブラは闇（注：個人の感想）
• 組み込み（intrinsic）関数
• 最近はかなりよい（が）
• VCはtemplateと組み合わせると辛い
• asm出力を見ながら理想の状態に向けて調節するのが辛い
（注：個人の感想）
従来のアセンブラの不満なところ（2/2）
13 / 40
- 14. • できるだけNASMに似た構文を目指す
• 演算子オーバーロードでごにょごにょ
• ヘッダオンリー
• #includeするだけで使える
• ライブラリにするとリンカの設定やコンパイラオプションに
気をつかわないといけない
Xbyakの設計
mov eax, dword [ecx + eax * 4 + 8]
vgatherdpd xmm1, [ebp+32+xmm2*4], xmm3
mov(eax, dword [ecx + eax * 4 + 8]);
vgatherdpd(xmm1, ptr [ebp+32+xmm2*4], xmm3);
NASM
Xbyak
14 / 40
- 15. • 関数と生成される命令が完全に1対1
• CPUに応じた専用命令を使いやすい
• 制御（if, else, for）はC++そのものなので書きやすい
• Cのoffsetofなどのマクロで構造体などを直接扱える
Xbyakの特長
// 構造体A<4>のメンバcの値の読み込み
mov (eax, ptr [ecx + offsetof(A<4>, c)]);
// add(eax, eax)を3回出力
for (int i = 0; i < 3; i++) {
add(eax, eax);
}
15 / 40
- 16. • 64 * n-bit加算（ビット長に応じたコード生成）
多倍長加算の例
GenAdd(int n) {
for (int i = 0; i < n; i++) {
mov(rax, ptr [x+i*8]);
if (i == 0) add(rax, ptr [y+i*8]);
else adc(rax, ptr [y+i*8]);
mov(ptr [z+i*8], rax);
}
ret(); }
add3:
mov rax, [rsi]
add rax, [rdx]
mov [rdi], rax
mov rax, [rsi + 8]
adc rax, [rdx + 8]
mov [rdi + 8], rax
mov rax, [rsi + 16]
adc rax, [rdx + 16]
mov [rdi + 16], rax
ret
add2:
mov rax, [rsi]
add rax, [rdx]
mov [rdi], rax
mov rax, [rsi + 8]
adc rax, [rdx + 8]
mov[rdi + 8], eax
ret
N=2 N=3
16 / 40
- 17. • AVX-512対応依頼（2016/4）
• 対応CPU存在してないのに?
• マニュアル1000ページ以上
• 7月対応
• Knights Mill用のも欲しい（2016/11）
• 対応したけど
確認方法が無い
• 2017/12/8ローンチ
>I've checked the
encoding using an internal version of XED assembler/...
AVX-512完全（Ice Lakeまで）対応
17 / 40
- 18. • Intel CPU向けに最適化されたdeep learningライブラリ
• https://github.com/intel/mkl-dnn
• エンジン部分がXbyakで書かれている
• MKL-DNNが利用しているツール（上記urlより引用）
• Caffe Optimized for Intel Architecture, DeepBench,
PaddlePaddle, Tensorflow, Microsoft Cognitive Toolkit
(CNTK), Apache MXNet, Intel Computer Vision SDK, etc.
Intel MKL-DNN
18 / 40
- 20. • （私がやってる暗号関係では）
• アルゴリズム
• わりと高度な数学
• 論文いっぱい
• 紙と鉛筆で考える
• データレイアウト
• いかにメモリアクセスを減らすか
• ex. 仮想関数を使わない（asmからアクセスしやすい）
• 基本命令のスループットとレイテンシ
• 一つのことをするのに沢山の方法がある
• 場合によっては選択するアルゴリズムが変わることも
開発中に考えていること
20 / 40
- 21. • 暗号アルゴリズムの速度は乗算（M）、加減算（A）
の回数で評価することが多かった
• 例. algo1はMが3回でAが5回. algo2はMが2回でAが7回
• もしMがAの10倍かかる（M=10A）なら
algo1=35A
algo2=27A
でalgo2が速い
• 2009年ごろ
• SIMDを使った手法が主流
• IntelのSIMDは64bitを超えるbitシフト（S）は苦手
• が、当時それを考慮した評価はあまり無かった
• Aが増えてもSが減ればトータルで高速なアルゴリズム
SIMD vs. add/sub/mul（1/2）
21 / 40
- 22. • 2009年～
• Core i7（Nehalem）で乗算のレイテンシーが3cycleと高速化
• SIMDより64×64→128bit乗算を使う方が速いかも
• SIMDを駆使した既存実装に対して2倍近い速度向上
• Haswellから利用可能なmulxなも使って世界最速
• https://github.com/herumi/ate-pairing
SIMD vs. add/sub/mul（2/2）
22 / 40
- 23. • 呼び出し既約
• Cの関数を呼び出すときのレジスタの値の設定ルール
• 例）Linuxなら第1～4引数がrdi, rsi, rdx, rcx
• 関数内でr12～r15, rbx, rbpを使いたければ値を退避・復元
• プロファイル上位のほとんどの関数をasm化
• それらの関数内での呼び出し規約は自分で決めてよい
• レジスタの退避・復元を最小化する呼び出し既約
• もちろんCから呼ぶとSEGV
• LLVMのコード生成より1.1～1.5倍速いことも
独自呼び出し既約（禁じ手）
23 / 40
func() // 擬似コード
store(rsp + 80, r12, r13, r14, r15,rbx, rbp);
計算本体
load(r12, r13, r14, r15, rbx, rbp, rsp + 80);
ret();
コンパイラから
呼ばれないなら
無くしてもよい
- 24. • 全てC++で完結しないことが多い
• 極めて速度が要求される部分だけC++ & asm
• DLL化してJava, C#, Go, Pythonなどから呼び出す
• C++クラスをC APIにする一般的な手順
• コンストラクタはcreateA();
• デストラクタはdestroyA(A* self);
• メソッドは第一引数がA*の関数
他言語と連係
class A {
void f(int x);
};
struct A;
A* createA();
void A_f(A* self, int x);
void destroyA(A* self);
C API
24 / 40
- 25. • JNI（Java Native interface）
• Javaからネイティブコードを呼び出すための仕組み
• SWIG
• C/C++をPython, PHP, Java, Goなどから呼ぶためのツール
• Javaと連係する場合
• C++のヘッダファイルからC APIへの変換コードを自動生成
• 自動生成されたC APIをJNIで呼び出し
Java側で同等のクラスを再構築
SWIGによるJavaとの連係
25 / 40
class A {
private long ptr;
A() {
ptr = createA();
}
};
- 28. • SWIGによるデストラクタの扱い
• Javaのラッパークラスのfinalize()でデストラクタを呼ぶ
原因の絞り込み
public class Fr {
private transient long swigCPtr;
protected transient boolean swigCMemOwn;
protected void finalize() { delete(); }
public synchronized void delete() {
if (swigCPtr == 0) return;
if (swigCMemOwn) {
swigCMemOwn = false;
Bn256JNI.delete_Fr(swigCPtr);
}
swigCPtr = 0;
}
28 / 40
- 31. • Go
• deferはインスタンスの寿命とスコープが異なるので使えない
• インスタンス生成毎にruntime.SetFinalizerにdestroyAを登録
• しかしやはりいつ呼ばれるかは不明
• JavaScript（WebAssembly）
• finalizerが無い
• （対処方法）classがUint32Arrayを持ちメソッドごとにcopy
• 細かい計算ではオーバーヘッドが大きいが、そもそも
呼び出しのオーバーヘッドが大きいので許せることもある
• Rust
• GCは無い
• std::ops::Dropで確実にdestroyAを呼べる
GCのある言語は辛い
31 / 40
- 32. • 必要サイズを取得するC APIを追加
• 一般解ではないがC/C++側でメモリ管理をしない戦略
• getSizeForA()が固定長のときのGoの例
メモリ管理を呼び出し側でしてもらう
size_t getSizeForA(); // createA()で必要だったメモリ量
bool InitA(A* a); // 領域aにAを構築する
void A_foo(A* a);
type A struct {
self *C.A
}
func NewA *A {
p := new(A)
p.self = C.createA()
runtime.SetFinalizer(p, destroyA)
return p
} 32 / 40
type A sturct {
v [4]C.unt64_t
}
func NewA *A {
return new(A)
}
- 35. • gccのバージョンを上げたらある処理が4倍遅くなった
• 関数のそれぞれのasm出力コードは問題なさそう
• 謎の挙動
• 右のbenchが遅い
• (B)と(C)の違いは?
おかしな因果関係?
void bench() {
(A)ベンチマーク
// (B)
}
int main() {
bench();
// (C)
unitTest1();
// (D)
unitTest2();
// (E)
unitTest3();
}
35 / 40
ここでexit()すると速い
ここでexitは少し遅い
ここだともう少し遅い
ここでexit()すると遅い
- 36. • gccのinlineを管理するオプション
• --param inline-unit-growth=<N>なども
• gccはinline対象関数の総量を管理している
• unitテスト内に大量のinline可能な関数がある
• 最適化レベルが上がりinline対象関数が増える
• bench内の関数がinline対象外となり遅くなる
• mainの途中でexitした後のコードは生成されない
• inline対象が減り、結果benchがinline化されて速くなる
• bench内でexitしてもmain内でのinline対象は減らない
• benchは速くならない
--param max-inline-insns-single=<N>
36 / 40
- 37. • AVX利用時に標準数学関数が5倍遅くなる現象
• 最小コードと原因追求に苦労
Visual Studioであったバグ
const struct A {
float a[8];
A() {
const float x = log(2.0);
for (int i = 0; i < 8; i++) a[i] = x;
}
} notUsed;
int main() {
...
}
37 / 40
一度も参照されない変数
7だと遅くならない
この中のsinやexpが遅くなる
