Homomorphically Encrypting CRDTs

ローカルファーストソフトウェアの問題:

遠く離れた場所に住む友人と共同で文書を編集したい場合、ローカルファーストの得意分野のように思える。文書をCRDTとして、保存し、何らかの同期サーバーを使い更新をマージし、あなたと友人の間で中継するのだ。しかし問題がある。文書の内容はごく気になっている

ただ問題がある

同期サーバーが変更をマージし、文書を開いた際に最新版を送信できた頃は問題なかった

トレードオフ:

あなたと友人はオンラインである必要がある

同期サーバーが変更をマージせずに単に通達する方式。非同期作業が可能になるが、サーバーが更新データを圧縮できなくなる

Last-Write-Wins Register (LWW-Register) の基本

役割:

1つの値を持ち

clock(更新回数を表すカウンタ)

peer ID

を一緒に管理する

merge alogorihm

もしother.clock < self.clock -> 何もしない

もしother.clock > self.clock -> otherの値で上書き

もしclockが同じ -> peer IDが大きい方を勝ちとする

code:register.rs

pub struct Register {

pub peer: u64,

pub clock: u64,

}

setで値を更新するとclockがインクリメントされる

mergeで上記アルゴリズムを実装

暗号化版EncryptedRegisterの実装

code:encrypt_register.rs

pub struct EncryptedRegister {

peer: FheUint64,

clock: FheUint64,

}

違いは型

u64 -> FheUint64(暗号化された64bit 整数)

u8 -> FheUint8 (暗号化された8bit 整数)

比較

code:plan_text.rs

if self.clock > other.clock {

// 自分の方が新しい → 何もしない

return;

}

if self.clock == other.clock && self.peer > other.peer {

// 時計が同じなら peer ID で勝敗 → 自分が勝ち → 何もしない

return;

}

// 上の条件に当てはまらなければ other に置き換える

self.peer = other.peer;

self.clock = other.clock;

self.value = other.value;

ただし、暗号化だとif文が使えない

条件を表す値を作成し、両方の値を暗号的に合成する

code:bool.rs

let higher_clock = self.clock.gt(&other.clock);

let equal_clock = self.clock.eq(&other.clock);

let higher_peer = self.peer.gt(&other.peer);

自分を残すべきか

code:keep_self.rs

let keep_self = higher_clock | (equal_clock & higher_peer);

平文のifを論理式に書き直した形

| と & はビット演算子なので「両方必ず評価される」＝条件分岐による情報漏洩がない。

結果として keep_self は 暗号化された「自分を残すかどうか」フラグ になる。

seletで暗号文を選択

code:select.rs

self.peer = keep_self.select(&self.peer, &other.peer);

self.clock = keep_self.select(&self.clock, &other.clock);

select(cond, a, b)はcondがtrueならa, falseならbを返すが、返り値も暗号文

つまりどっちを選んだかは外からはわからない

「どちらの text を残すか決めて上書きする」

というのも、ここは公開していても良くて、最終的なコンテンツが暗号化されていれば良いのでは？って思っている

もちろん匿名性を出すためにBlockchainのようにアドレスの概念やdidを取り入れることでどこまででも可能だと思うし