Git 支援其他 Hash 演算法的進展

GitSHA-1,而 SHA-1 又破的問題使得 Git 開始計畫其他 hash algorithm (「Google 與 CWI Amsterdam 合作,找到 SHA-1 第一個 collision」)。

在「"uchar [40]" to "struct object_id" conversion continues.」這邊可以看到一些動作,先把本來的 uchar[40] 換成一般性的 struct object_id

Hacker News 上的「The beginning of Git supporting other hash algorithms」也有一些討論可以看。

NIST 開始徵求 Post-Quantum Cryptography 演算法

現有常見的幾個加密基礎在量子電腦上都有相當快速的解 (像是整數質因數分解、離散對數),只是現在建不出對應夠大台的量子電腦... 但畢竟只是時間的問題了,所以 NIST 照著慣例對外尋求能夠抵抗量子電腦的演算法:「NIST Asks Public to Help Future-Proof Electronic Information」、「Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms」。

類似於 Google 先前在 Google Chrome 上實做的 CECPQ1,對 key exchange 的部份加上保護 (Google Chrome 引入 CECPQ1,開始測試 Post-Quantum Cryptography),這次 NIST 是針對 public key crytpsystem 的部份而發的...

投稿時間在 2017 的十一月底,大約一年後就可以看到有哪些演算法要參加競賽了... 不過因為 NSA 的惡名,不知道會不會有其他單位在同個時段啟動類似的活動...

透過演算法修照片的工具

看到「A simple interface for editing natural photos with generative neural networks.」這個工具,直接看這個兩分鐘的影片比較清楚知道他想要做的事情:

當你修正了某一個點後,這個工具就透過演算法改變其他的點,讓照片看起來變得自然... 作者所發表的論文可以在「Neural Photo Editing with Introspective Adversarial Networks」這邊下載到。

Dropbox 儲存密碼的方式

記得 Dropbox 前陣子才強迫所有使用者重設密碼:「The Dropbox hack is real」,官方的報告在這:「Resetting passwords to keep your files safe」,當時洩漏出來的資訊可以知道 2012 年的時候 Dropbox 用的是 SHA1:

What we've got here is two files with email address and bcrypt hashes then another two with email addresses and SHA1 hashes.

三個多禮拜候,Dropbox 說明了現在的密碼儲存策略:「How Dropbox securely stores your passwords」,現在是先 SHA512,再 bcrypt,然後存在資料庫裡時使用 AES256 保護:

比較特別一點的是先 SHA512 的部份,除了 72bytes 常見限制外,另外一個原因是為了避免 DoS,不過還是覺得有點怪就是了:

Other implementations don’t truncate the input and are therefore vulnerable to DoS attacks because they allow the input of arbitrarily long passwords.

而 AES256 的部份則是確保就算 SQL injection 或是其他方式將儲存的密碼撈出去後,也還有相當程度的保護能力。

Facebook 推出的 Zstandard 壓縮

Facebook 發了一篇出來,講 Zstandard:「Smaller and faster data compression with Zstandard」,可以看到:

如果與 Google 去年 open source 出來的 Brotli 相比,Zstandard 則是著重在速度,想要做出一個比 zlib 快很多但又比 zlib 壓的好的壓縮演算法。

Facebook 推薦好友機制的演算法讓更多的隱私問題浮現...

在「Facebook recommended that this psychiatrist’s patients friend each other」這邊報導了 Facebook 推薦好友機制的演算法意外的拉出了奇怪的東西:

[...], such as this story from Lisa*, a psychiatrist who is an infrequent Facebook user, mostly signing in to RSVP for events. Last summer, she noticed that the social network had started recommending her patients as friends—and she had no idea why.

“I haven’t shared my email or phone contacts with Facebook,” she told me over the phone.

精神科醫師被 Facebook 推薦他的病人... 而更慘的是病人也收到的推薦包括了其他的病人:

Another one of her female patients had a friend recommendation pop up for a fellow patient she recognized from the office’s elevator. Suddenly, she knew the other patient’s full name along with all their Facebook profile information.

“It’s a massive privacy fail,” said Lisa. “I have patients with HIV, people that have attempted suicide and women in coercive and violent relationships.”

而且因為職業的關係,他也對此很小心防範:

Lisa lives in a relatively small town and was alarmed that Facebook was inadvertently outing people with health and psychiatric issues to her network. She’s a tech-savvy person, familiar with VPNs, Tor and computer security practices recommended by the Electronic Frontier Foundation–but she had no idea what was causing it.

這聽起來不是什麼好演算法 :o

設計資料同步問題時一定會遇到的 Conflict 解決方案

在「A Conflict-Free Replicated JSON Datatype」這邊看到有趣的東西。(arXiv 說 2016/08/18 會有一個小時的 downtime,台灣時間剛好是 2016/08/18 的 20:20 開始:「Maintenance scheduled for Aug 18 8:20 a.m. EDT」)

作者們設計這個架構是想要在 JSON 結構上找出一個演算法,在 P2P 架構上 (而不需要靠 server) 可以同步並且產生一致的結果,另外要求當 conflict 時不要掉資料:

In this paper we present an algorithm and formal semantics for a JSON data structure that automatically resolves concurrent modifications such that no updates are lost, and such that all replicas converge towards the same state.

作者提出來的想法不是很複雜,而且 merge 保留姿的方法也頗... 特別,但總是給大家一個想法,各何況很多情況下都是有 server 架構,就簡單多了...

Cuckoo Filter:比 Bloom Filter 多了 Delete

在「Cuckoo Filter implementation in Go, better than Bloom Filters」這邊看到這個資料結構,有興趣的人也可以看「Cuckoo Filter:设计与实现」這篇介紹,下面是我抓重點整理。

Bloom Filter 支援的操作:

  • Add(element)
  • Query(element)

1970 年提出來的資料結構。優點是空間複雜度是 O(1),Query(element) 會有可接受的 false positive,缺點是不支援 Delete(element)、以及數量變多時誤判率的增加。

Cuckoo Filter 多了一組操作:

  • Delete(element)

2014 年提出來的資料結構。空間複雜度一樣是 O(1),但相同的空間用量下 false positive 變低,然後支援 Delete(element) 了。也因此論文直接寫「Cuckoo Filter: Practically Better Than Bloom」,表示可以直接替代。

看到 zmx 貼了之前的連結,更確信 Uber 的問題不是技術問題了...

Twitter 上看到 zmx 提了一個連結,講 Uber 年初時貼的「How We Built Uber Engineering’s Highest Query per Second Service Using Go」這篇文章的問題:

對照最近的事情還蠻有趣的,尤其是這篇文章後面提到的,酸~爆~了~XDDD:

It is clear to me that the team at Uber under-engineered this problem. Thoughtfully designing this service could trim down the number of nodes by an order of magnitude and save hundreds of thousands of dollars each year. That may sound like pittance to a company valued at more than the GDP of Delaware, but in my eyes that’s the salaries of a few engineers and a few good engineers can go a long way. Maybe even further than the few extra Mercedes-Benz S-Classes they could add to their fleet from the money they could be saving...

先不提政治問題,上面提到的 Quadtree 算是簡單易懂的結構,好久沒看到這個資料結構了:

Google 提出的 Jump Consistent Hash

堆了一陣子的文章...

當有 n 台 cache server 給你使用,最傳統的作法是 hash(key) % n 決定挑哪一台 cache server,但這個方法在增加或減少機器時就會讓 cache 大規模失效。Consistent Hashing 就是希望在這種情況下 (增加或是移除 cache server 時) 可以避免大規模 cache 失效的問題。

比較基本的 Consistent Hash 作法是將 hash(key) 的值對應到 ring 上 (假設是 hash value 的範圍是 32bits,也就是 0 到 0xFFFFFFFF,那麼 ring 繞一圈平均分佈),像是一開始只有三台,所以就是三個 bucket:

取自「Consistent hashing」這裡。

等加了機器後就分擔掉本來的 hash value 區段:

取自「Consistent hashing」這裡。

這樣的作法通常會需要 O(log N) 的時間複雜度 (query & add/remove server) 與 O(n) 的空間複雜度。

另外會有平均性的問題需要解決,通常的 workaround 是讓一個 server 有很多 virtual bucket 在 ring 上面解,像是這樣:

取自「The Simple Magic of Consistent Hashing」。

Google 在 2014 年發表出來的 Jump Consistent Hash 則給了更好的方案,O(1) 的空間使用率以及 O(logN) 的時間複雜度 (query only),而且非常平均的打散:「A Fast, Minimal Memory, Consistent Hash Algorithm」。

論文裡面給了 C++ 的實作:

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
  int64_t b = ­-1, j = 0;
  while (j < num_buckets) {
    b = j;
    key = key * 2862933555777941757ULL + 1;
    j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
  }
  return b;
}

神秘數字 (還出現 double) 與神秘的迴圈... 在 Performance Analysis 這段解釋了時間複雜度明顯跟迴圈有關,分析後可以得到 O(log N):

The time complexity of the algorithm is determined by the number of iterations of the while loop. [...] So the expected number of iterations is less than ln(n) + 1.

再來是 Consistent Hash 會討論「平均性」這個問題,可以看到跟以前的方法不是同一個級別:

執行的效率也非常好,要注意的是 X 軸是對數座標:

在 Note 的部份也說明了這個演算法 Google 沒有計畫要弄專利 (也公開出來了):

Google has not applied for patent protection for this algorithm, and, as of this writing, has no plans to. Rather, it wishes to contribute this algorithm to the community.