- Trong phần mềm local-first, Homomorphic Encryption và CRDTs được kết hợp để duy trì bảo mật cho tài liệu cộng tác
- Chỉ với mã hóa đầu cuối thì máy chủ không thể hợp nhất dữ liệu, nên phát sinh hạn chế về hiệu quả đồng bộ hóa và cập nhật
- Mã hóa đồng hình là công nghệ cho phép thực thi chương trình để máy chủ có thể hợp nhất các bản cập nhật CRDT mà không biết nội dung
- Tuy nhiên, do những giới hạn căn bản của mã hóa đồng hình (suy giảm hiệu năng, tăng dung lượng và khối lượng tính toán, yêu cầu mã phải hoạt động theo trường hợp xấu nhất), việc áp dụng thực tế gặp khó khăn nghiêm trọng
- Nhiều hướng tiếp cận khác nhau đang được nghiên cứu để CRDTs và tính toán an toàn có thể cùng tồn tại, và vẫn chưa có giải pháp hoàn chỉnh
Local-first và bài toán cộng tác an toàn
- Trong cộng tác từ xa, tài liệu được lưu theo mô hình CRDT theo kiểu local-first, sau đó cung cấp trải nghiệm cùng chỉnh sửa thông qua đồng bộ hóa
- Khi có yêu cầu bảo mật rằng nội dung tài liệu tuyệt đối không được lộ ra cho bên thứ ba như nhà phát triển ứng dụng, thì mã hóa đầu cuối là phương pháp thường được sử dụng
- Mã hóa đầu cuối có cách hoạt động đơn giản, nhưng vì máy chủ đồng bộ không thể hợp nhất dữ liệu nên nếu làm việc bất đồng bộ trong thời gian dài sẽ phát sinh giao tiếp dữ liệu kém hiệu quả
Mã hóa đồng hình là gì?
- Mã hóa đồng hình là một phương thức mã hóa đặc biệt cho phép thực thi thuật toán trực tiếp trên dữ liệu đã mã hóa
- Nhờ đó, máy chủ đồng bộ có thể thực hiện hợp nhất bản cập nhật CRDT mà không biết nội dung dữ liệu
- Tùy theo loại phép toán được hỗ trợ, mã hóa đồng hình được chia thành đồng hình một phần (chỉ hỗ trợ cộng hoặc nhân), đồng hình hạn chế/đồng hình phân tầng (hỗ trợ cả hai nhưng chỉ một số lần nhất định), và đồng hình hoàn toàn (không giới hạn)
- Càng có nhiều phép toán, nhiễu càng tích tụ trong bản mã và việc giải mã càng trở nên khó khăn, nên cần các kỹ thuật nâng cao như Bootstrapping
- Ở mức bit đã mã hóa (0/1), chỉ với việc kết hợp các cổng phép toán cơ bản như XOR, AND cũng có thể triển khai mạch Boolean tổng quát
Ví dụ triển khai CRDT mã hóa đồng hình trong thực tế
- Thư viện TFHE-rs dựa trên Rust được dùng để triển khai bằng mã hóa đồng hình một CRDT tiêu biểu là Last Write Wins Register
- Các trường và phương thức (mã hóa/giải mã) của struct bản rõ và struct mã hóa gần như giống nhau, nhưng có khác biệt quan trọng ở logic hợp nhất thực tế
- Vì việc phân nhánh đường thực thi như câu lệnh if/else, match có thể gợi ý cho việc giải bản mã, nên trong môi trường mã hóa bắt buộc phải đánh giá ngay mọi nhánh và vòng lặp
- So sánh điều kiện chính và các phép hợp nhất đều được xử lý bằng toán tử FheBool ở mức bit và phương thức
select, nhờ đó bên ngoài không thể phát hiện giá trị đã thay đổi ở điều kiện nào
Những giới hạn căn bản của mã hóa đồng hình
- Mất cân đối giữa khóa mã hóa và kích thước dữ liệu: trong ví dụ, dữ liệu 32 byte cần khóa máy chủ 123MB (ngay cả khi nén vẫn là 27MB), gây kém hiệu quả về dung lượng nghiêm trọng
- Suy giảm hiệu năng: thao tác merge CRDT đã mã hóa đồng hình được đo ở mức khoảng 1 giây, chậm hơn bản không mã hóa khoảng 2 tỷ lần
- Nếu vòng lặp hoặc phân nhánh thay đổi theo giá trị đầu vào thì sẽ gây rò rỉ thông tin, nên luôn phải tiêu tốn số phép tính và bộ nhớ theo trường hợp xấu nhất
- Ví dụ, ngay cả khi key-value thưa thớt như trong last-write-wins map, vẫn phải hợp nhất bằng cách lấp đầy mọi khóa theo kích thước cố định, làm suy giảm khả năng mở rộng thực tế
- Cần thiết kế để người quan sát bên ngoài không thể suy luận từ cấu trúc bản mã hoặc lịch sử thay đổi rằng giá trị có thay đổi hay phần nào đã được cập nhật
Kết luận và triển vọng
- CRDTs và mã hóa đồng hình về lý thuyết có thể kết hợp khá tự nhiên, nhưng trên thực tế tồn tại những ràng buộc nghiêm trọng về hiệu quả không gian/thời gian và cấu trúc chương trình
- Ở thời điểm hiện tại vẫn chưa có giải pháp thực dụng hoàn chỉnh, nhưng bản thân CRDTs cũng là công nghệ còn khá mới và vẫn đang được nghiên cứu liên tục
- Trong các ứng dụng cộng tác local-first, tiềm năng về các giải pháp đột phá nhằm cân bằng bảo mật và tính khả dụng vẫn còn nguyên
1 bình luận
Ý kiến trên Hacker News
Đúng là lĩnh vực mã hóa đồng hình hoàn toàn rất chậm và kém hiệu quả, nhưng cũng cần nói rằng đây là một lĩnh vực tương đối mới, chỉ xuất hiện từ năm 2009; tiến bộ trong 15 năm qua thực sự rất đáng kinh ngạc. Những lược đồ mã hóa đồng hình đầu tiên cần khóa có kích thước tới hàng TB/PB, còn bootstrapping (phép toán bắt buộc khi số phép nhân trong mã hóa đồng hình tăng lên) mất hàng nghìn giờ. Giờ đây khóa chỉ còn khoảng 30MB, và bootstrapping có thể thực hiện trong chưa tới 0,1 giây. Hy vọng lĩnh vực này sẽ tiếp tục phát triển để một ngày nào đó trở nên thực sự hữu dụng.
Các CRDT đời đầu (CRDT: Conflict-free Replicated Data Type) như WOOT cũng cực kỳ thiếu thực tế, nhưng các cơ sở dữ liệu CRDT hiện đại ngày nay có hiệu năng không thua kém quá nhiều so với LSM thông thường. Chẳng hạn, các RDX CRDT hoạt động bằng thuật toán tương tự merge sort nên đều là O(N). Trong phần lớn triển khai, chi phí overhead metadata cũng được kiểm soát tốt. Xem WOOT, librdx, go-rdx.
Do đặc tính kiến trúc của CRDT, nó gần như chắc chắn sẽ chậm, và ngay cả thuật toán tốt nhất cũng có chi phí cấu trúc cao. Khi thêm mã hóa đồng hình vào thì độ khó còn tăng lên rất nhiều. Quả thật rất ấn tượng, nhưng tôi vẫn tự hỏi liệu nó có dùng được trong thực tế hay không. Để làm căn cứ cho lập luận đó, người này trích dẫn lời giải thích: "để máy chủ tính ra map mới, nó phải merge từng khóa một, sau đó gửi toàn bộ map cho từng peer — vì từ góc nhìn của máy chủ, toàn bộ map đều khác nhau mỗi lần".
CRDT là viết tắt của Conflict-free Replicated Data Type, một kiểu dữ liệu đặc biệt cho phép đồng bộ phân tán mà không xảy ra xung đột. Xem liên kết Wikipedia về CRDT.
Bài viết có nhắc đến việc hiệu năng còn yếu, và thực tế trên M4 MacBook Pro, nếu chạy một last write wins register bình thường thì việc merge mất 0,52 nano giây, còn phiên bản mã hóa đồng hình mất 1,06 giây. Tức là tốc độ xử lý chênh nhau 2 tỷ lần, một con số thật sự gây sốc.
FHE (Full Homomorphic Encryption) thật sự rất chậm, nhưng từ sau năm 2009 đã có những bước tiến đáng kinh ngạc. Chỉ riêng tốc độ bootstrapping cũng đã nhanh hơn hàng chục triệu lần. Người ta thậm chí đã trình diễn AES-128 dựa trên mã hóa đồng hình bằng tfhe-rs. Tôi nghĩ khả năng áp dụng FHE thời gian thực cho suy luận/học AI đang ngày càng cao hơn. Xem liên kết GitHub tfhe-aes-128.
Tôi không đồng ý với ý rằng máy chủ không còn có thể hiểu được các thay đổi của client. Máy chủ chỉ cần gửi những thay đổi mà người dùng chưa thấy, rồi người dùng sẽ giải mã và merge chúng để tạo ra phiên bản mới nhất của tài liệu. Mã hóa đồng hình đúng là thú vị, nhưng trong những tình huống cần hiệu năng hay băng thông hợp lý thì nó hầu như không phù hợp. Trước đây tôi từng đọc một bài báo về điện toán bảo mật hoàn toàn dựa trên mã hóa đồng hình (mã hóa một CPU+RAM tùy biến thành ciphertext rồi xử lý một lệnh cho mỗi xung nhịp). Nó thực sự hoạt động, nhưng chỉ đạt mức 1 lệnh CPU ảo mỗi giây. Nếu tốc độ và chi phí như vậy vẫn chấp nhận được, thì tốt hơn là chạy cục bộ, hoặc nếu thật sự rất giàu thì mua phần cứng riêng để xử lý tại chỗ còn khôn ngoan hơn.
Các bài báo khoa học máy tính và mật mã thường khá xa rời tính thực tiễn, ví dụ như những nghiên cứu cực kỳ phi thực tế kiểu giảm độ phức tạp tấn công từ 2^250 xuống 2^230. Dù vậy, những nghiên cứu như thế vẫn có ý nghĩa trong R&D thực tế hoặc trong việc mở rộng biên giới những gì có thể làm được.
Nếu máy chủ không thể trực tiếp xử lý nội dung thì nó không thể hợp nhất tài liệu CRDT, và sẽ phải nhận rồi gửi đi toàn bộ trạng thái CRDT mỗi lần. Nếu bạn của bạn đang online cùng lúc thì có thể gửi operations để merge thời gian thực, còn nếu không thì sẽ rất kém hiệu quả.
Tôi tự hỏi liệu có thể tin tưởng việc sinh viên chạy mã chấm điểm WASM hoặc JS đã được mã hóa bằng FHE trực tiếp trên Chromebook của họ, với tổ hợp JupyterLite và ottergrader, hay không. Tôi cũng tò mò về mối liên hệ giữa code signing và screensaver của SETI@home.
Tốt hơn là không nên dùng THFE-rs, vì phía Zama yêu cầu giấy phép thương mại nếu dùng ngoài mục đích tạo prototype, nên điều khoản giấy phép khá bất tiện. Thay vào đó, tôi khuyến nghị các thư viện openFHE(C++), lattigo(golang), và cả hai đều có thể dùng tự do trong thương mại.
Tôi nghĩ FHE về bản chất là công cụ không phù hợp cho trường hợp này. FHE phù hợp khi xử lý dữ liệu do máy chủ trung tâm sở hữu hoặc biết rõ. Ở đây, nhiều người dùng phải cùng xử lý dữ liệu phân tán, nên MPC (tính toán đa bên: nhiều bên tham gia cùng tính toán trên dữ liệu bí mật riêng của mình, như cộng dồn các giá trị) sẽ hiệu quả hơn nhiều.
Tôi không thật sự hiểu các giả định mà bài viết đưa ra. Tôi hiểu khái niệm CRDT và mã hóa đồng hình, nhưng vẫn thắc mắc vì sao để đồng bộ thì hai bên lại phải cùng online một lúc. Nếu dùng kiểu trao đổi cập nhật bất đồng bộ theo mô hình
store-and-forward, thì dữ liệu đang truyền cũng có thể được gửi đi trong trạng thái đã mã hóa; vậy tại sao máy chủ lại phải giữ trạng thái (mà còn là trạng thái đã mã hóa), và phải chỉnh sửa theo cách như đề xuất?Sự kết hợp giữa tính chậm và kém hiệu quả của FHE với sự lãng phí không gian lưu trữ của CRDT trông khá thú vị.