Tag Archives: algorithm

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

Git 用 SHA-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」也有一些討論可以看。

Posted in Computer, Murmuring, Programming, Security, Software | Tagged , , , , | Leave a comment

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 … Continue reading

Posted in Computer, Murmuring, Network, Security | Tagged , , , , , , , , , , , , , | Leave a comment

透過演算法修照片的工具

看到「A simple interface for editing natural photos with generative neural networks.」這個工具,直接看這個兩分鐘的影片比較清楚知道他想要做的事情: 當你修正了某一個點後,這個工具就透過演算法改變其他的點,讓照片看起來變得自然... 作者所發表的論文可以在「Neural Photo Editing with Introspective Adversarial Networks」這邊下載到。

Posted in Computer, Murmuring, Network, Photo, Programming, Recreation, Software | Tagged , , , , , , , | Leave a comment

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. … Continue reading

Posted in Cloud, Computer, Murmuring, Network, Programming, Security | Tagged , , , , , , , , , , , , | Leave a comment

Facebook 推出的 Zstandard 壓縮

Facebook 發了一篇出來,講 Zstandard:「Smaller and faster data compression with Zstandard」,可以看到: 如果與 Google 去年 open source 出來的 Brotli 相比,Zstandard 則是著重在速度,想要做出一個比 zlib 快很多但又比 zlib 壓的好的壓縮演算法。

Posted in Computer, Murmuring, Software | Tagged , , , , , , , , | Leave a comment

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 … Continue reading

Posted in Computer, Murmuring, Network, Security, Social, VPN, WWW | Tagged , , , , , , , , | Leave a comment

設計資料同步問題時一定會遇到的 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 … Continue reading

Posted in Computer, Murmuring, Network, P2P, Programming | Tagged , , , , , , , , | Leave a comment

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」,表示可以直接替代。

Posted in Computer, Murmuring, Programming | Tagged , , , , , , , | Leave a comment

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

在 Twitter 上看到 zmx 提了一個連結,講 Uber 年初時貼的「How We Built Uber Engineering’s Highest Query per Second Service Using Go」這篇文章的問題: TLDR; Uber:傳統方式太複雜了根據我們資料特性自創一套高效能的空間索引服務。前 Bing 員工:買了 Bing 怎麼不問專家啊?Quadtree 降兩個數量級啊,不然你們自創的做了這個小修改也是降兩個數量級啊!https://t.co/nHw1DgmYtU — Bill Zhong (@zmx) August 2, 2016 對照最近的事情還蠻有趣的,尤其是這篇文章後面提到的,酸~爆~了~XDDD: It is clear to me that the … Continue reading

Posted in Computer, Murmuring, Network, Programming, Search Engine, Software | Tagged , , , , , , , , , , | Leave a comment

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,那麼 … Continue reading

Posted in Computer, Murmuring, Network, Programming | Tagged , , , , , | Leave a comment