Máy tính lượng tử có thể đánh cắp Bitcoin của bạn trong “9 phút” như thế nào?

Phần 1 của loạt bài này đã giải thích máy tính lượng tử thực sự là gì. Chúng không chỉ là các phiên bản nhanh hơn của máy tính thông thường, mà là một loại máy hoàn toàn khác biệt, khai thác những quy luật vật lý kỳ lạ chỉ áp dụng ở quy mô nguyên tử và hạt.

Nhưng việc biết cách một máy tính lượng tử hoạt động không cho bạn biết cách nó có thể được kẻ xấu sử dụng để đánh cắp Bitcoin. Điều đó đòi hỏi sự hiểu biết về những gì nó thực sự đang tấn công, cách bảo mật của Bitcoin được xây dựng và chính xác thì điểm yếu nằm ở đâu.

Bài viết này bắt đầu với mã hóa của Bitcoin và đi sâu vào khung thời gian chín phút cần thiết để phá vỡ nó, như đã được xác định bởi bài báo về điện toán lượng tử gần đây của Google.

Bản đồ một chiều

Bitcoin sử dụng một hệ thống gọi là mã hóa đường cong Elliptic để chứng minh ai sở hữu cái gì. Mỗi ví có hai khóa. Khóa cá nhân là một con số bí mật, dài 256 chữ số ở dạng nhị phân, dài xấp xỉ câu văn này. Khóa công khai được tạo ra từ khóa cá nhân bằng cách thực hiện một phép toán trên đường cong cụ thể gọi là “secp256k1”.

Hãy coi nó như một bản đồ một chiều. Bắt đầu tại một vị trí đã biết trên đường cong mà mọi người đều đồng ý, gọi là điểm tạo G (như được hiển thị trong biểu đồ bên dưới). Thực hiện một số bước riêng tư theo một mô hình được xác định bởi toán học của đường cong. Số bước chính là khóa cá nhân của bạn. Nơi bạn kết thúc trên đường cong là khóa công khai của bạn (điểm K trong biểu đồ). Bất kỳ ai cũng có thể xác minh rằng bạn đã kết thúc tại vị trí cụ thể đó. Không ai có thể tìm ra bạn đã thực hiện bao nhiêu bước để đến đó.

Về mặt kỹ thuật, điều này được viết là K = k × G, trong đó k là khóa cá nhân và K là khóa công khai của bạn. Phép “nhân” này không phải là phép nhân thông thường mà là một phép toán hình học, nơi bạn lặp đi lặp lại việc cộng một điểm vào chính nó dọc theo đường cong. Kết quả dừng lại ở một điểm dường như ngẫu nhiên mà chỉ con số k cụ thể của bạn mới có thể tạo ra.

Đặc tính quan trọng là việc đi tới thì dễ dàng nhưng việc đi ngược lại, đối với các máy tính cổ điển, là điều thực tế không thể thực hiện được. Nếu bạn biết k và G, việc tính toán K chỉ mất vài mili giây. Nếu bạn biết K và G và muốn tìm ra k, bạn đang giải quyết bài toán mà các nhà toán học gọi là bài toán logarit rời rạc trên đường cong Elliptic.

Người ta ước tính rằng các thuật toán cổ điển tốt nhất hiện nay cho một đường cong 256-bit sẽ mất thời gian “lâu hơn cả tuổi của vũ trụ”.

Cửa sập một chiều này là toàn bộ mô hình bảo mật. Khóa cá nhân của bạn chứng minh bạn sở hữu đồng coin của mình. Khóa công khai của bạn an toàn để chia sẻ vì không máy tính cổ điển nào có thể đảo ngược toán học. Khi bạn gửi Bitcoin, ví của bạn sử dụng khóa cá nhân để tạo chữ ký số, một bằng chứng toán học rằng bạn biết con số bí mật mà không cần tiết lộ nó.

Thuật toán Shor mở cánh cửa theo cả hai chiều

Vào năm 1994, một nhà toán học tên là Peter Shor đã khám phá ra một thuật toán lượng tử có thể phá vỡ cửa sập này.

Thuật toán Shor giải quyết bài toán logarit rời rạc một cách hiệu quả. Chính phép toán mà một máy tính cổ điển sẽ mất thời gian lâu hơn cả tuổi thọ của vũ trụ, thuật toán Shor có thể xử lý trong cái mà các nhà toán học gọi là “thời gian đa thức”, nghĩa là độ khó tăng chậm khi các con số lớn hơn thay vì tăng bùng nổ.

Trực giác về cách nó hoạt động quay trở lại ba tính chất lượng tử từ Phần 1 của loạt bài này.

Thuật toán cần tìm khóa cá nhân k của bạn, cho trước khóa công khai K và điểm tạo G. Nó chuyển đổi điều này thành bài toán tìm chu kỳ của một hàm số. Hãy tưởng tượng một hàm số nhận một con số làm đầu vào và trả về một điểm trên đường cong Elliptic.

Khi bạn nạp cho nó các con số tuần tự 1, 2, 3, 4, các đầu ra cuối cùng sẽ lặp lại theo một chu kỳ. Độ dài của chu kỳ đó được gọi là chu kỳ, và một khi bạn biết hàm số lặp lại thường xuyên như thế nào, toán học của bài toán logarit rời rạc sẽ được giải quyết chỉ trong một bước. Khóa cá nhân sẽ lộ diện gần như ngay lập tức.

Việc tìm chu kỳ của một hàm số chính là điều mà máy tính lượng tử được chế tạo để thực hiện. Thuật toán đưa thanh ghi đầu vào của nó vào trạng thái chồng chập (hay trong cơ học lượng tử, một hạt tồn tại ở nhiều vị trí cùng một lúc), đại diện cho tất cả các giá trị khả thi một cách đồng thời. Nó áp dụng hàm số cho tất cả chúng cùng một lúc.

Sau đó, nó áp dụng một phép toán lượng tử gọi là biến đổi Fourier, khiến cho số lượng các câu trả lời sai bị triệt tiêu trong khi các câu trả lời đúng được củng cố.

Khi bạn đo kết quả, chu kỳ sẽ xuất hiện. Từ chu kỳ này, toán học thông thường sẽ khôi phục lại k. Đó chính là khóa cá nhân của bạn, và do đó là các đồng coin của bạn.

Cuộc tấn công sử dụng tất cả ba thủ thuật lượng tử từ bài viết đầu tiên. Chồng chập đánh giá hàm số trên mọi đầu vào khả thi cùng một lúc. Rối lượng tử liên kết đầu vào và đầu ra để các kết quả luôn tương quan với nhau. “Giao thoa” lọc bỏ tiếng nhiễu cho đến khi chỉ còn lại câu trả lời.

Tại sao Bitcoin vẫn hoạt động tốt đến ngày nay

Thuật toán Shor đã được biết đến hơn 30 năm. Lý do Bitcoin vẫn tồn tại là việc chạy nó đòi hỏi một máy tính lượng tử có số lượng qubit ổn định đủ lớn để duy trì tính liên kết trong suốt toàn bộ quá trình tính toán.

Việc chế tạo cỗ máy đó vẫn nằm ngoài tầm với, nhưng câu hỏi luôn là bao nhiêu là “đủ lớn”.

Các ước tính trước đây cho biết cần hàng triệu qubit vật lý. Bài báo của Google, được công bố vào đầu tháng 4 bởi bộ phận Quantum AI của họ với sự đóng góp từ nhà nghiên cứu Justin Drake của Ethereum Foundation và nhà mật mã học Dan Boneh của Stanford, đã giảm con số đó xuống còn ít hơn 500.000.

Hay nói cách khác là giảm khoảng 20 lần so với các ước tính trước đó.

Nhóm nghiên cứu đã thiết kế hai mạch lượng tử thực hiện thuật toán Shor chống lại đường cong Elliptic cụ thể của Bitcoin. Một mạch sử dụng khoảng 1.200 qubit logic và 90 triệu cổng Toffoli. Mạch còn lại sử dụng khoảng 1.450 qubit logic và 70 triệu cổng Toffoli.

Cổng Toffoli là một loại cổng tác động lên ba qubit: hai qubit điều khiển sẽ ảnh hưởng đến trạng thái của qubit thứ ba, gọi là qubit mục tiêu. Hãy tưởng tượng điều này giống như ba công tắc đèn (qubit) và một bóng đèn đặc biệt (mục tiêu) chỉ bật sáng nếu hai công tắc cụ thể được bật cùng một lúc.

Bởi vì các qubit liên tục mất trạng thái lượng tử, như Phần 1 đã giải thích, bạn cần hàng trăm qubit dư thừa kiểm tra công việc của nhau để duy trì một qubit logic đáng tin cậy duy nhất. Hầu hết một máy tính lượng tử tồn tại chỉ để bắt các lỗi của chính cỗ máy đó trước khi chúng làm hỏng quá trình tính toán. Tỷ lệ khoảng 400 trên 1 giữa qubit vật lý và qubit logic phản ánh lượng cơ sở hạ tầng tự giám sát khổng lồ của cỗ máy.

Khung thời gian chín phút

Bài báo của Google không chỉ làm giảm số lượng qubit. Nó còn giới thiệu một kịch bản tấn công thực tế làm thay đổi cách suy nghĩ về mối đe dọa này.