Nếu bạn đã từng gửi tin nhắn văn bản, phát đĩa CD hoặc lưu trữ tệp trên đám mây thì bạn đã được hưởng lợi từ việc sửa lỗi. Ý tưởng mang tính cách mạng này có từ những năm 1940, khi các nhà nghiên cứu lần đầu tiên nhận ra rằng có thể viết lại bất kỳ thông điệp nào dưới dạng cho phép dễ dàng khắc phục tình trạng tham nhũng sau này.

Trong nhiều năm, các nhà nghiên cứu đã phát triển nhiều phương án khéo léo, được gọi là mã sửa lỗi, mã hóa dữ liệu theo nhiều cách khác nhau và sử dụng các quy trình khác nhau để sửa lỗi. Nhưng đối với các nhà khoa học máy tính lý thuyết, rất ít mã có sức thuyết phục bằng cái gọi là mã có thể sửa được cục bộ. Các mã này có hai thuộc tính đồng thời nghe có vẻ gần như trái ngược nhau: Bất kỳ lỗi nào cũng có thể được sửa bằng cách đọc dữ liệu được mã hóa chỉ ở một vài nơi, tuy nhiên không kẻ tấn công nào có thể phá vỡ quy trình sửa lỗi này bằng cách giả mạo mã có chọn lọc. Nó giống như bạn có thể khôi phục lại bất kỳ trang nào bị xé ra khỏi một cuốn sách chỉ bằng cách liếc nhìn một vài trang khác.

“Đó là một hiện tượng kỳ diệu,” nói Tom Gur, một nhà khoa học máy tính tại Đại học Cambridge. “Tiên nghiệm, không rõ ràng là một đối tượng toán học như vậy có thể tồn tại hay không.”

Nhưng phép thuật này phải trả giá đắt. Các ví dụ duy nhất được biết đến về mã có thể sửa cục bộ là cực kỳ kém hiệu quả - việc mã hóa bất kỳ tin nhắn nào cũng khiến nó dài hơn theo cấp số nhân. Toàn bộ sách được mã hóa theo cách này sẽ quá khó sử dụng.

Các nhà khoa học máy tính từ lâu đã tự hỏi liệu có thể thực hiện được các mã có thể sửa được cục bộ tốt hơn hay không. Họ đặc biệt tập trung vào các mã chỉ sử dụng ba truy vấn để sửa bất kỳ lỗi nào, hy vọng rằng hạn chế nghiêm trọng này có thể giúp các mã này dễ hiểu hơn. Nhưng ngay cả trường hợp đơn giản này cũng đã khiến các nhà nghiên cứu bối rối trong hơn 20 năm.

Bây giờ nhà khoa học máy tính Pravesh Kothari của Đại học Carnegie Mellon và nghiên cứu sinh của ông Peter Manohar cuối cùng đã chứng minh rằng không thể xây dựng mã có thể sửa cục bộ gồm ba truy vấn để tránh chi phí theo cấp số nhân đó. Nó có thể là một kết quả tiêu cực, nhưng bất cứ điều gì làm rõ các giới hạn của việc sửa lỗi đều gây hứng thú cho các nhà nghiên cứu, đặc biệt là vì toán học về các mã có thể sửa được cục bộ xuất hiện ở những khu vực cách xa liên lạc.

“Kết quả này thật tuyệt vời,” nói Shubhangi Saraf, một nhà khoa học máy tính tại Đại học Toronto. “Đó là một bước đột phá lớn.”

Sức mạnh về con số

Để hiểu cách sửa lỗi, hãy tưởng tượng dữ liệu bạn muốn bảo vệ dưới dạng một chuỗi bit hoặc 0 và 1. Trong mô hình này, lỗi có thể là bất kỳ sự đảo ngược không mong muốn nào từ số 0 thành số 1 hoặc ngược lại, cho dù đó là do biến động ngẫu nhiên hay do cố ý giả mạo.

Giả sử bạn muốn gửi tin nhắn cho bạn bè nhưng bạn lo ngại rằng các lỗi có thể làm thay đổi ý nghĩa. Một chiến lược đơn giản là thay mỗi số 0 trong tin nhắn của bạn bằng 000 và mỗi số 1 bằng 111. Nếu bạn của bạn nhìn thấy một phần tin nhắn không chứa ba bit giống nhau liên tiếp, họ sẽ biết rằng đã xảy ra lỗi. Và nếu các lỗi là ngẫu nhiên và tương đối hiếm thì bất kỳ chuỗi 110 nào cũng có nhiều khả năng là chuỗi 111 bị hỏng hơn là chuỗi 000 bị hỏng. Một cuộc bỏ phiếu đa số đơn giản trong mỗi bộ ba sẽ đủ để sửa hầu hết các lỗi.

Sơ đồ này, được gọi là mã lặp lại, có ưu điểm là đơn giản nhưng lại không có gì khác đáng khuyến khích. Có một điều, nó đòi hỏi phải tăng gấp ba lần độ dài của mỗi tin nhắn chỉ để xử lý các lỗi tương đối hiếm gặp và nếu có khả năng xảy ra hai lỗi liền kề thì chúng ta sẽ cần nhiều dự phòng hơn nữa. Tệ hơn nữa, nó sẽ nhanh chóng trở nên vô dụng nếu lỗi không phải ngẫu nhiên, chẳng hạn như khi kẻ tấn công chủ động cố gắng phá hoại mã. Trong mã lặp lại, tất cả thông tin cần thiết để sửa một bit nhất định chỉ được lưu trữ trong một vài bit khác, khiến nó dễ bị tấn công có chủ đích.

May mắn thay, nhiều mã sửa lỗi hoạt động tốt hơn. Một ví dụ nổi tiếng, được gọi là Mã Reed-Solomon, hoạt động bằng cách chuyển đổi thông điệp thành đa thức - các biểu thức toán học như x² + 3x + 2 bao gồm các thuật ngữ khác nhau được cộng lại với nhau, mỗi thuật ngữ có một biến (chẳng hạn như x) được nâng lên một lũy thừa khác. Mã hóa tin nhắn bằng mã Reed-Solomon bao gồm việc xây dựng một đa thức với một thuật ngữ cho mỗi ký tự trong tin nhắn, sau đó vẽ đa thức dưới dạng đường cong trên đồ thị và lưu trữ tọa độ của các điểm nằm trên đường cong (lấy thêm ít nhất một điểm nữa). point hơn số lượng ký tự). Lỗi có thể đẩy một số điểm này ra khỏi đường cong, nhưng nếu không có quá nhiều lỗi thì chỉ có một đường cong đa thức đi qua hầu hết các điểm. Đường cong đó gần như chắc chắn tương ứng với thông điệp thực sự.

Mã Reed-Solomon cực kỳ hiệu quả — bạn chỉ cần lưu trữ thêm một vài điểm để sửa lỗi, do đó, mọi tin nhắn được mã hóa chỉ dài hơn một chút so với mã gốc. Họ cũng ít bị tổn thương hơn trước các loại gián đoạn có mục tiêu có thể gây ra thảm họa cho mã lặp lại, bởi vì thông tin được sử dụng để sửa lỗi ở bất kỳ đâu sẽ được phân phối trên toàn bộ thông báo được mã hóa.

Suy nghĩ toàn cầu, hành động cục bộ

Sức mạnh của mật mã Reed-Solomon bắt nguồn từ tính liên kết với nhau. Nhưng chính vì sự liên kết với nhau đó nên không có cách nào sửa được một lỗi nhỏ trong tin nhắn được mã hóa mà không đọc toàn bộ nội dung. Điều đó có vẻ không phải là một vấn đề trong bối cảnh giao tiếp: Nếu bạn đang gửi tin nhắn, bạn có thể muốn người nhận đọc toàn bộ tin nhắn. Nhưng nó có thể là một trở ngại trong việc lưu trữ dữ liệu - một ứng dụng chính khác của việc sửa lỗi.

Hãy xem xét một công ty lưu trữ email của người dùng trên đám mây - nghĩa là trên một loạt máy chủ. Bạn có thể coi toàn bộ bộ sưu tập email là một tin nhắn dài. Bây giờ giả sử một máy chủ gặp sự cố. Với mã Reed-Solomon, bạn cần thực hiện một phép tính lớn liên quan đến tất cả dữ liệu được mã hóa để khôi phục email của mình từ một máy chủ bị mất đó. “Bạn sẽ phải xem xét mọi thứ,” nói Zeev Dvir, một nhà khoa học máy tính tại Đại học Princeton. “Đó có thể là hàng tỷ tỷ email – có thể mất một thời gian rất dài.”

Các nhà nghiên cứu sử dụng thuật ngữ “cục bộ” để mô tả các mã chỉ sử dụng một phần thông điệp được mã hóa để phát hiện lỗi hoặc sửa chúng. Mã lặp lại đơn giản có đặc tính cục bộ nào đó, nhưng đó chính xác là lý do khiến nó rất dễ bị giả mạo. Ngược lại, một mã có thể sửa cục bộ sẽ tận dụng tối đa cả hai thế giới — nó có thể sửa lỗi ở bất kỳ bit nào chỉ bằng một vài truy vấn, tất cả đều không làm mất tính liên kết khiến mã Reed-Solomon trở nên linh hoạt.

“Đây là một khái niệm thực sự nghiêm ngặt,” Kothari nói.

Các ví dụ nổi tiếng nhất về mã có thể sửa được cục bộ là phiên bản của mã sửa lỗi đáng kính được các nhà toán học phát minh vào năm 1954. David Muller và Irving Reed (người cũng đã giúp phát triển mã Reed-Solomon). Giống như mã Reed-Solomon, mã Reed-Muller sử dụng đa thức với nhiều thuật ngữ được cộng lại với nhau để mã hóa các thông điệp dài.

Các đa thức được sử dụng trong mã Reed-Solomon bao gồm một biến duy nhất, x, vì vậy cách duy nhất để thêm nhiều số hạng hơn là sử dụng lũy ​​thừa cao hơn của x. Điều này dẫn đến một đường cong có nhiều điểm lắc lư mà chỉ có thể xác định được bằng cách nhìn vào nhiều điểm. Thay vào đó, mã Reed-Muller sử dụng đa thức trong đó mỗi số hạng có thể chứa nhiều biến nhân với nhau. Nhiều biến hơn có nghĩa là có nhiều cách hơn để kết hợp chúng, từ đó đưa ra một cách để tăng số lượng số hạng đa thức mà không nâng bất kỳ biến riêng lẻ nào lên lũy thừa cao như vậy.

Mã Reed-Muller rất linh hoạt. Bạn có thể mã hóa các tin nhắn dài hơn bằng cách tăng lũy ​​thừa cao nhất xuất hiện trong đa thức, tăng số lượng biến hoặc cả hai. Để làm cho mã Reed-Muller có thể sửa cục bộ, bạn chỉ cần giới hạn công suất tối đa của mỗi biến ở một giá trị không đổi nhỏ và xử lý các tin nhắn dài hơn bằng cách chỉ tăng số lượng biến.

Cụ thể, đối với mã có thể sửa cục bộ ba truy vấn, công suất tối đa đó được đặt ở mức 2. Sau đó, đối với từng biến riêng lẻ, mã hóa đa thức của thông báo sẽ vạch ra một hình parabol đơn giản. Để xác định hình dạng chính xác của parabol đó, bạn chỉ cần xét đường cong tại ba điểm. Hơn nữa, với nhiều biến số thì có nhiều parabol như vậy, bất kỳ biến nào trong số đó đều có thể được sử dụng để sửa lỗi. Đó là điều khiến mã Reed-Muller trở nên linh hoạt.

Thật không may, mã Reed-Muller có một nhược điểm nghiêm trọng: Số bit cần thiết để mã hóa một thông điệp tăng theo cấp số nhân với số lượng biến. Nếu bạn muốn một mã có tính cục bộ cao có thể sửa lỗi chỉ bằng một số truy vấn, bạn sẽ cần rất nhiều biến cho các tin nhắn dài và mã Reed-Muller sẽ nhanh chóng trở nên vô dụng trong thực tế.

“Số mũ trong trường hợp này là rất tệ,” Dvir nói. Nhưng nó có phải là không thể tránh khỏi?

Có thể sửa được hay có thể giải mã được?

Khi các nhà khoa học máy tính cố gắng tìm ra những mã có thể sửa cục bộ hiệu quả hơn nhưng không thành công, họ bắt đầu nghi ngờ rằng những mã như vậy hoàn toàn không thể tồn tại được. Năm 2003, hai nhà nghiên cứu chứng minh rằng không có cách nào đánh bại được mã Reed-Muller chỉ bằng hai truy vấn. Nhưng đó là tất cả những gì mà bất kỳ ai cũng có được.

Kothari nói: “Khi bạn đến bước thứ ba, kiến ​​thức của chúng tôi trở nên rất sơ sài.

Bước đột phá tiếp theo chỉ làm phức tạp thêm vấn đề. Trong hai bài báo đăng trên 2008 và 2009, các nhà khoa học máy tính Sergey Yekhanin và Klim Efremenko đã chỉ ra cách xây dựng các mã ba truy vấn hiệu quả hơn mã Reed-Muller, nhưng những mã này không thể sửa được cục bộ. Thay vào đó, chúng có một đặc tính khác biệt nhỏ gọi là khả năng giải mã cục bộ.

Để hiểu sự khác biệt, hãy tưởng tượng một lần nữa một nhà cung cấp dịch vụ lưu trữ đám mây kết hợp dữ liệu của người dùng thành một tin nhắn dài và bảo vệ dữ liệu đó bằng mã sửa lỗi. Cả mã có thể sửa cục bộ và mã có thể giải mã cục bộ đều có thể sửa lỗi ở bất kỳ bit nào của tin nhắn gốc chỉ bằng một vài truy vấn.

Tuy nhiên, mọi mã sửa lỗi cũng yêu cầu thêm các bit không có trong tin nhắn gốc — đó là lý do tại sao việc mã hóa tin nhắn lại khiến nó dài hơn. Hai loại mã này khác nhau ở cách chúng xử lý các bit bổ sung này. Các mã có thể giải mã cục bộ không hứa hẹn về số lượng truy vấn cần thiết để sửa lỗi trong các bit này. Nhưng trong một mã có thể sửa cục bộ, lỗi ở bất kỳ bit bổ sung nào cũng có thể được sửa theo cách giống hệt như lỗi ở bất kỳ bit nào của thông báo gốc.

“Mọi thứ bạn lưu trữ, cho dù đó là dữ liệu gốc của người dùng hay phần dư thừa và thông tin kiểm tra – tất cả những điều này đều có thể được sửa cục bộ,” cho biết Madhu Sudan, một nhà khoa học máy tính tại Đại học Harvard.

Mặc dù khác nhau về nguyên tắc, khả năng sửa lỗi cục bộ và khả năng giải mã cục bộ dường như luôn có thể thay thế cho nhau trong thực tế trước năm 2008 - mọi mã có thể giải mã cục bộ đã biết cũng có thể sửa được cục bộ. Khám phá của Yekhanin và Efremenko đã làm tăng khả năng có sự khác biệt cơ bản giữa hai tình trạng này. Hoặc có lẽ có thể sửa đổi mã của Yekhanin và Efremenko để chúng có thể sửa được cục bộ. Điều đó sẽ đặt hai điều kiện ngang nhau một lần nữa, nhưng điều đó cũng có nghĩa là các nhà nghiên cứu đã nhầm lẫn về mức độ hiệu quả mà các mã có thể sửa cục bộ ba truy vấn có thể đạt được. Dù thế nào đi nữa, sự hiểu biết thông thường sẽ phải thay đổi.

Logic vay mượn

Kothari và Manohar cuối cùng đã giải quyết được sự căng thẳng đó bằng cách áp dụng một kỹ thuật từ một lĩnh vực khác của khoa học máy tính: nghiên cứu về cái gọi là các vấn đề thỏa mãn ràng buộc. Cố gắng sắp xếp kế hoạch ăn tối với một nhóm bạn là một vấn đề thuộc loại hạn chế sự thỏa mãn. Mọi người đều có những lựa chọn mà họ sẽ chấp nhận và những lựa chọn mà họ sẽ phủ quyết. Công việc của bạn là tìm ra một kế hoạch làm hài lòng tất cả mọi người, hoặc nếu không có kế hoạch nào như vậy, hãy tìm ra kế hoạch đó càng sớm càng tốt.

Có sự bất cân xứng cố hữu giữa hai kết quả có thể xảy ra đó. Một giải pháp chấp nhận được có thể không dễ tìm, nhưng một khi bạn đã có nó, bạn sẽ dễ dàng thuyết phục người khác rằng nó sẽ hiệu quả. Nhưng ngay cả khi bạn biết rằng vấn đề thực sự là “không thỏa mãn” thì cũng có thể không có ví dụ nào cung cấp bằng chứng.

Vào năm 2021, Kothari và Manohar, cùng với Venkatesan Guruswami của Đại học California, Berkeley, đã thực hiện một nghiên cứu bước đột phá lớn trong việc nghiên cứu các vấn đề thỏa mãn ràng buộc bằng cách sử dụng một kỹ thuật lý thuyết mới để xác định những trường hợp phức tạp không thỏa mãn đó. Họ nghi ngờ rằng phương pháp mới cũng sẽ là một công cụ mạnh mẽ để giải quyết các vấn đề khác, và sinh viên tốt nghiệp của Guruswami, Omar Alrabiah đề nghị họ xem xét các mã có thể giải mã cục bộ ba truy vấn.

“Có thể nói đây là một chiếc đinh với một chiếc búa trong tay chúng tôi,” Kothari nói.

Kết quả đáng ngạc nhiên của Yekhanin và Efremenko đã chỉ ra rằng các mã có thể giải mã cục bộ ba truy vấn có thể hiệu quả hơn mã Reed-Muller. Nhưng liệu mã của họ có phải là mã tốt nhất có thể hay mã có thể giải mã cục bộ ba truy vấn thậm chí còn hiệu quả hơn? Kothari, Manohar, Guruswami và Alrabiah nghĩ rằng kỹ thuật mới của họ có thể chứng minh được những giới hạn về mức độ hiệu quả của những mã như vậy. Kế hoạch của họ là xây dựng một công thức logic bao gồm cấu trúc của tất cả các mã có thể giải mã cục bộ ba truy vấn có thể có kích thước nhất định và chứng minh nó không thỏa mãn, qua đó cho thấy rằng không có mã nào như vậy có thể tồn tại.

Bốn nhà nghiên cứu đã thực hiện bước đầu tiên theo hướng đó vào năm 2022, thiết lập mục tiêu giới hạn mới về hiệu quả tối đa của mã có thể giải mã cục bộ ba truy vấn. Kết quả vượt xa những gì các nhà nghiên cứu có thể đạt được bằng các kỹ thuật khác, nhưng nó không loại trừ tất cả các mã hiệu quả hơn của Yekhanin và Efremenko.

Kothari và Manohar nghi ngờ họ có thể tiến xa hơn. Nhưng tiến trình bị đình trệ cho đến khi Manohar ghi lại một phép tính nhanh chóng đằng sau phong bì chỉ ra rằng kỹ thuật này thậm chí có thể hoạt động tốt hơn đối với các mã có thể sửa cục bộ so với các mã có thể giải mã cục bộ.

Vài tháng sau, sau nhiều lần khởi đầu sai lầm khiến họ sợ rằng mình đã quá lạc quan, kỹ thuật này cuối cùng đã thực hiện được lời hứa của mình. Kothari và Manohar đã chứng minh rằng đúng như các nhà nghiên cứu đã nghi ngờ, không thể có bất kỳ mã có thể sửa cục bộ ba truy vấn nào hoạt động tốt hơn đáng kể so với mã Reed-Muller. Sự mở rộng theo cấp số nhân đó là một hạn chế cơ bản. Kết quả của họ cũng là một minh chứng ấn tượng rằng khả năng sửa lỗi cục bộ và khả năng giải mã cục bộ, mặc dù bề ngoài giống nhau nhưng thực sự khác nhau ở mức độ cơ bản: Cái sau rõ ràng là dễ nhận ra hơn cái trước.

Kothari và Manohar hiện hy vọng sẽ mở rộng kỹ thuật của họ để nghiên cứu các mã được phép thực hiện nhiều hơn ba truy vấn, vì hiện nay rất ít thông tin về chúng. Và sự tiến bộ trong lý thuyết sửa lỗi thường có ý nghĩa trong các lĩnh vực khác dường như không liên quan. Đặc biệt, các mã có thể sửa cục bộ xuất hiện bất ngờ ở mọi nơi từ vấn đề tìm kiếm cơ sở dữ liệu riêng tư trong mật mã để chứng minh các định lý trong tổ hợp. Còn quá sớm để nói kỹ thuật của Kothari và Manohar sẽ tác động như thế nào đến các lĩnh vực khác nhau này, nhưng các nhà nghiên cứu đang cảm thấy lạc quan.

“Có một ý tưởng mới thực sự hay ở đây,” Dvir nói. “Tôi nghĩ có rất nhiều tiềm năng.”