Sắp xếp mật mã trong Blockchains: tầm quan trọng của VRF

Khi tiền điện tử có thể là game thủ hệ thống

Khi tôi đọc và hiểu nhiều hơn về các công nghệ blockchain như một phần công việc nghiên cứu của tôi trong Witnet, tôi bắt đầu nhận ra tầm quan trọng của các giao thức và sơ đồ mật mã đối với các thiết kế của chúng. Thật đáng kinh ngạc khi một quyết định thiết kế nhỏ có thể ảnh hưởng đến cách người dùng tương tác với hệ thống và, có khả năng, tận dụng lợi thế của nó.

Trong bài đăng này, tôi muốn chia sẻ một số nghiên cứu nội bộ mà chúng tôi đã thực hiện tại Witnet và cách chúng tôi nhận ra rằng các giả định về mật mã của chúng tôi không đủ mạnh cho các mục đích ban đầu của chúng tôi.

PoE là một phần của Giao thức Blockchain

Proof of Eligabilities (PoEs) đang ngày càng trở nên phổ biến trong công nghệ Blockchain. Trong thực tế, PoE cho chúng ta cơ hội để quyết định ai chịu trách nhiệm thực hiện một hành động. Khi đủ điều kiện được phát hiện bởi từng cá nhân, chúng tôi thường gọi nó là sơ đồ phân loại mật mã, tức là khả năng khám phá xem bạn có phải là người chiến thắng xổ số của một người hay không.

Có một số thuộc tính mà một phân loại mật mã cần phải đầy đủ. Đầu tiên, các nút riêng lẻ sẽ có thể xác định xem chúng có đủ điều kiện để thực hiện một hành động nhất định hay không. Thứ hai, tính đủ điều kiện nên được kiểm chứng bằng mật mã bởi các đồng nghiệp khác. Thứ ba, một sự sắp xếp mật mã được liên kết với một danh tính duy nhất, tức là, các đồng nghiệp cần phải chắc chắn rằng bằng chứng được tạo ra bởi người ngang hàng tuyên bố nó. Ngoài ra, người ta cũng muốn rằng bằng chứng không thể phân biệt được với ngẫu nhiên.

Chúng tôi đã quan sát một số sơ đồ sắp xếp mật mã đang được đề xuất như một phần của thiết kế blockchain, từ Proof of Work nổi tiếng trong Bitcoin đến các đề xuất mới như, ví dụ: Algorand, Filecoin hoặc Witnet. Trong bài đăng này, tôi sẽ tập trung vào phân loại mật mã được mô tả trong Witnet và các cải tiến có thể có của nó. Tôi hy vọng thông tin được đăng ở đây là hữu ích cho các blockchain khác có cùng mục đích.

Sắp xếp mật mã dựa trên chữ ký số

Thông thường các sơ đồ phân loại mật mã dựa trên tính đủ điều kiện của họ dựa trên sự may mắn nhận được một số ngẫu nhiên nằm dưới một giá trị mục tiêu nhất định. Khó khăn rõ ràng phụ thuộc vào giá trị mục tiêu; giá trị càng cao, càng có nhiều cơ hội để trở thành đủ điều kiện. Giá trị mục tiêu, thực sự có thể khác nhau đối với các đồng nghiệp khác nhau, có lẽ tùy thuộc vào mức độ họ cư xử trong các nhiệm vụ trước. Đây chính xác là cách tiếp cận được mô tả bởi Witnet. Phân loại mật mã trong Witnet được định nghĩa là:

Sắp xếp mật mã trong Witnet

Trong đó <> biểu thị chữ ký trên khóa M và tôi đề cập đến ảnh hưởng của ngang hàng i tại thời điểm t. Ảnh hưởng đề cập đến danh tiếng của nút, tức là, nó hoạt động tốt như thế nào trong các nhiệm vụ trước. Về cơ bản, nếu hàm băm của chữ ký của nhiệm vụ mà một người ngang hàng muốn thực hiện giảm xuống dưới giá trị mục tiêu, thì cô ta trở thành đủ điều kiện để thực hiện nhiệm vụ. Chúng tôi quan sát làm thế nào mỗi đồng nghiệp có thể tìm ra cách sắp xếp riêng lẻ mà không tương tác với bất kỳ đồng nghiệp nào khác trong mạng. Giá trị ngẫu nhiên là chung cho tất cả các đồng nghiệp (cũng có thể là hàm băm của khối trước đó).

Để xác minh tính đủ điều kiện của một nút, phần còn lại của các nút trước tiên kiểm tra xem chữ ký đã được tạo với các tham số thích hợp (giá trị ngẫu nhiên được liên kết với kỷ nguyên hiện tại và tác vụ mà nút đó đang chọn). Sau đó, họ băm chữ ký để xem liệu nó có giảm xuống dưới giá trị đích hay không. Nếu vậy, tính đủ điều kiện của ngang hàng cho nhiệm vụ được xác minh.

Các loại sắp xếp mật mã dựa trên chữ ký điện tử (nghĩa là chữ ký của một tin nhắn đã cho) đầy đủ các câu lệnh được xác định ở trên: chúng được tạo bởi một đồng đẳng nhất định, chúng có thể kiểm chứng được thông qua khóa chung và đầu ra của chúng xuất hiện ngẫu nhiên mà không có khóa chung.

Nhưng các lược đồ sắp xếp mật mã dựa trên chữ ký số có xu hướng đầy đủ (như trong Witnet) một yêu cầu khác mà tôi không đề cập: mỗi đồng nghiệp nên có một lần chụp đủ điều kiện cho một thông điệp đầu vào. Mặt khác, các đồng nghiệp chỉ có thể chạy xổ số nhiều lần như họ muốn cho đến khi họ đủ điều kiện. Câu hỏi mà chúng tôi đã tự hỏi mình trong Witnet là: chữ ký số có đầy đủ tài sản này không?

Vấn đề: đầu ra không duy nhất cho ECDSA

Trước khi đưa ra câu trả lời cho câu hỏi trước đó, hãy để tôi giới thiệu ngắn gọn về cách hoạt động của Mật mã đường cong Elliptic.

Tóm lại, Mật mã đường cong Elliptic (ECC) là một hệ thống mật mã khóa công khai, trong đó mỗi đồng đẳng giữ một cặp khóa công khai-riêng. Khóa riêng chỉ được chủ sở hữu biết, trong khi khóa chung được mọi người biết đến. Các đồng nghiệp truyền thông trước tiên phải đồng ý về đường cong ECC rằng họ
sẽ sử dụng. Đường cong chỉ là tập hợp các điểm được xác định bởi một phương trình,
ví dụ: y ^ 2 = x ^ 3 + ax + b. Đường cong được xác định, trong số các tham số khác, bởi một điểm tạo nhờ chúng ta có thể đạt tới bất kỳ điểm nào khác trong đường cong. Để xây dựng một hệ thống như vậy, ECC xây dựng số học sau:

  • nếu P là một điểm trong đường cong thì -P là điểm phản xạ của nó trên trục x
  • nếu hai điểm P và Q khác nhau thì kết quả của việc thêm P và Q là
    được tính bằng cách vẽ một đường thẳng cắt P và Q, sẽ giao nhau trong một
    điểm thứ ba −R trong đường cong. R được tính bằng cách lấy phản xạ của −R
    đối với trục x.
  • P + P được tính bằng cách vẽ một đường tiếp tuyến với đường cong tại P,
    một lần nữa sẽ cắt nhau ở điểm thứ ba trong đường cong 2P. 2P chỉ là
    phản xạ trên trục x
Ví dụ bổ sung đường cong Elliptic

Lưu ý rằng với số học này, chúng tôi đã có thể thêm điểm và do đó, nhân số điểm với thang cuốn (5P chỉ là 2P + 2P + P). Cặp khóa riêng-công khai được xây dựng bằng cách chọn đầu tiên một số nguyên ngẫu nhiên sẽ cung cấp cho chúng tôi khóa riêng. Khóa công khai chỉ là phép nhân của số nguyên với điểm tạo. Tính bảo mật của lược đồ phụ thuộc vào độ khó hoặc truy xuất số nguyên có nguồn gốc điểm chung. Đây là, với khóa công khai Q, bài toán tìm số nguyên k nhân với bộ tạo để đạt Q tương đương với Bài toán logarit rời rạc.

Với một hệ thống như vậy, người ta có thể thực hiện một số cách tiếp cận mật mã. Một trong số đó là khả năng tạo chữ ký số. Có thể nhìn thấy bức tranh tổng thể về thế hệ siganture của ECDSA trong hình sau

Tạo chữ ký ECDSA

Về cơ bản, thông điệp đầu vào m được băm đầu tiên. Sau đó, một số ngẫu nhiên u được chọn sao cho khi nhân với điểm tạo G, ánh xạ tới một điểm trong đường cong có tọa độ x là 0. Nếu điều kiện này không được thỏa mãn, giá trị u được chọn lại. Nếu có, thì nghịch đảo của u được nhân với (e + dr) cho đến khi giá trị khác không. Chữ ký là tuple (r, s).

Trong thực tế, chúng ta không hoàn toàn cần phải hiểu thuật toán để nhận ra rằng chữ ký (r, s) phụ thuộc nhiều vào giá trị ngẫu nhiên u được chọn trong dòng 5. Đây là, giá trị chữ ký sẽ phụ thuộc vào một giá trị ngẫu nhiên, và do đó, một thông điệp nhất định có thể ánh xạ tới một số chữ ký khác nhau.

Điều này đã mâu thuẫn với những gì chúng tôi mô tả lý tưởng cho việc sắp xếp mật mã. Nếu tính hợp lệ của một đồng đẳng sẽ phụ thuộc vào hàm băm của chữ ký có thể nhận các giá trị khác nhau tùy thuộc vào giá trị ngẫu nhiên bạn đã chọn, chúng ta có thể hy vọng rằng các đồng nghiệp sẽ liên tục tính toán chữ ký cho đến khi họ tìm thấy một chữ ký có hàm băm đủ thấp, và do đó trở thành đủ điều kiện. Thật thú vị, sơ đồ tiền điện tử được sử dụng cung cấp cho các đồng nghiệp cơ hội để chơi trò chơi hệ thống.

Giải pháp: VRF là phân loại mật mã

Mặc dù vấn đề được đề cập, chúng tôi không muốn từ bỏ tất cả những lợi thế mà chữ ký số mang lại cho chương trình của chúng tôi. Do đó, chúng ta cần thêm thuộc tính duy nhất vào sắp xếp mật mã của mình, như thể đó là phiên bản khóa công khai của một chiếc máy tính bảng có khóa HMAC. Các hàm ngẫu nhiên có thể kiểm chứng (VRF) dường như thực hiện mánh khóe (và trên thực tế, chúng được sử dụng trong Algorand). VRF lần đầu tiên được giới thiệu bởi Silvio Micali trong [1]. Các VRF tạo ra hai kết quả đầu ra: một cái gọi là chữ ký duy nhất của β và một bằng chứng π. Ngoài việc là một hệ thống mật mã khóa công khai, chúng còn có các thuộc tính sau:

  • Kháng va chạm, tức là khó tìm thấy hai đầu vào ánh xạ tới cùng một đầu ra.
  • Pseudorandomness, tức là, đầu ra không thể phân biệt với ngẫu nhiên bởi bất kỳ ai không biết khóa bí mật.
  • Tính duy nhất đáng tin cậy, yêu cầu rằng, được cung cấp khóa công khai, đầu vào VRF tương ứng với đầu ra duy nhất.

Tuyên bố cuối cùng là khá quan trọng. Điều đó có nghĩa là β sẽ luôn là duy nhất cho một thông báo đầu vào nhất định và khóa chung, trong khi bằng chứng có thể được chọn ngẫu nhiên. Do đó, các đồng nghiệp không thể tạo ra một số chữ ký cho đến khi chúng đạt đến một giá trị đủ thấp, vì với cùng một đầu vào, chúng sẽ luôn nhận được cùng một giá trị. Đây là, họ chỉ chạy xổ số một lần cho mỗi tin nhắn đầu vào.

Ví dụ VRF

Câu hỏi tất nhiên là làm thế nào để xây dựng các chương trình đó. Chúng tôi thực hiện theo sơ đồ được đề xuất trong [2], mô tả các cấu trúc VRF cho cả RSA và ECC. Vì lợi ích của sự ngắn gọn, chúng tôi bỏ qua mô tả xây dựng RSA. Thật vậy, ECC cung cấp các lợi thế của chương trình tiền điện tử về kích thước khóa và chữ ký so với RSA để đạt được cùng mức bảo mật.

Thuật toán xác minh chữ ký ECC-VRF có thể được nhìn thấy bên dưới. ECVRF_hash_to_curve là một hàm băm một số nguyên cho một điểm trong đường cong. Ngược lại, ECVRF_hash_point là một hàm băm một số điểm trong đường cong thành một số nguyên. Với hai hàm phụ trợ này, chúng ta có thể xây dựng sơ đồ tạo chữ ký sau:

Tạo bằng chứng ECC-VRF

Đầu ra later sau đó được băm để kiểm tra xem thông báo có nằm dưới giá trị đích hay không, trong khi bằng chứng π được trình xác minh sử dụng để kiểm tra xem đầu ra có thực sự được tính với khóa chung được liên kết và cho thông báo đã cho theo cách sau:

Xác minh bằng chứng ECC-VRF

Nếu chúng ta xem xét thuật toán, nếu và chỉ khi cv bằng với c thì bằng chứng được xác minh. So sánh bước 15 từ xác minh và bước 4 từ thế hệ chữ ký, chúng ta có thể thấy rằng đẳng thức sẽ giữ chừng nào u = Gt và v = Ht. Người xác minh có thể xác nhận điều này mà không cần biết khóa bí mật k? Sau đây chúng tôi chứng minh tính đúng đắn của đẳng thức:

  • Giá trị u = Qc + Gs = Qc + G (t-kc) = Qc + Gt-Gkc = Qc + Gt -Qc = Gt
  • Giá trị v = c + Hs = βc + H (t-kc) = βc + Ht-Hkc = βc + Ht-c = Ht

Có thể xác minh rằng bình đẳng giữ mà không cần phải biết giá trị bí mật k.

Kết luận

Trong bài đăng này, tôi đã chia sẻ lý do tại sao các chương trình sắp xếp mật mã dựa trên chữ ký số có thể tạo ra động lực lớn cho các đồng nghiệp chơi trò chơi trên hệ thống, đặc biệt khi việc đủ điều kiện cho một nhiệm vụ phụ thuộc vào họ. Trong trường hợp của Witnet, cả nhiệm vụ khai thác và yêu cầu dữ liệu đều phụ thuộc vào đầu ra của sắp xếp, và do đó, chúng tôi không thể đặt ra một sự khích lệ như vậy cho các đồng nghiệp. Chúng ta có thể đạt đến một tình huống mà phần thưởng của yêu cầu dữ liệu đủ cao để khuyến khích các đồng nghiệp liên tục tạo chữ ký cho nó cho đến khi hàm băm đủ thấp, do đó thực hiện một loại Proof of Work không thể chấp nhận được đối với các yêu cầu dữ liệu. Trong thực tế, nếu các nút đặt tất cả các tài nguyên vào một yêu cầu dữ liệu hào phóng thì phần còn lại sẽ bị lãng quên và hiệu suất của hệ thống sẽ bị ảnh hưởng nghiêm trọng.

Các hàm ngẫu nhiên có thể kiểm chứng dường như giải quyết vấn đề được mô tả ở trên. Thật vậy, họ duy trì tất cả các lợi ích của chữ ký điện tử, với một thực tế bổ sung: chữ ký tên lửa là duy nhất cho một khóa công khai và thông điệp nhất định. Ngoài ra, VRF tạo ra bằng chứng nhờ đó người xác minh có thể kiểm tra tính hợp lệ của giao dịch. Do đó, VRF dường như là phương pháp phù hợp cho các hệ thống như Witnet.

Người giới thiệu

  • https://people.csail.mit.edu/nickolai/ con / gilad-algorand-eprint.pdf
  • https://people.csail.mit.edu/silvio/Selected%20Sellectific%20Papers/Pseudo%20Randomness/Verifiable_Random_Fiances.pdf
  • https://filecoin.io/filecoin.pdf
  • https://witnet.io/static/witnet-whitepaper.pdf
  • https://eprint.iacr.org/2017/099.pdf
  • https://tools.ietf.org/html/draft-irtf-cfrg-vrf-03