TinyRAM là một kiến trúc truy cập ngẫu nhiên được đề xuất bởi nhóm năm thành viên BCTGTV nổi tiếng (Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza) và Phòng thí nghiệm SCIPR, nhằm mục đích trở thành bằng chứng về công cụ tiện dụng điện toán không tất định. Cụ thể, TinyRAM là Máy tính Tập lệnh Giảm (RISC) với bộ nhớ truy cập ngẫu nhiên có thể định địa chỉ ở cấp độ byte. Nó tạo ra sự cân bằng giữa các mặt đối lập của "đủ biểu cảm" và "đủ đơn giản":
• Đủ biểu cảm để hỗ trợ mã hợp ngữ ngắn và hiệu quả khi được biên dịch từ ngôn ngữ lập trình cấp cao và
• Tập lệnh nhỏ, lệnh được xác minh dễ dàng bằng mạch vận hành và việc xác minh hiệu quả được thực hiện bằng cách sử dụng thuật toán và cơ chế mật khẩu của SCIPR.
ngành kiến trúc
TinyRAM được tham số hóa bằng hai số nguyên: độ dài từ W, phải là lũy thừa của 2 và chia hết cho 8 (điều này giống với các máy tính hiện đại, chẳng hạn như 32, 64) và số lượng thanh ghi K. Thường được đại diện bởi TinyRAM(W,K), trạng thái của máy bao gồm:
1. Bộ đếm chương trình pc (bộ đếm chương trình) bao gồm W bit.
2. K thanh ghi đa năng, được biểu diễn bằng r0, r1, ..., r(K-1), mỗi thanh ghi là W bit.
3. Cờ hiệu điều kiện bao gồm một bit.
4. Bộ nhớ, một mảng tuyến tính gồm 2^W byte, sử dụng quy ước little-endian để sắp xếp các byte.
5. 2 băng, mỗi băng chứa một chuỗi W bit từ. Mỗi băng là chỉ đọc theo một hướng. Trong số đó, một băng dành cho đầu vào công cộng x và băng còn lại dành cho đầu vào riêng w. Trên thực tế, nó là sóng mang đầu vào của TinyRAM.
Đầu vào của máy TinyRAM là 2 băng và bộ nhớ, đầu ra là lệnh trả lời, có tham số A, đại diện cho giá trị trả về và A = 0 có nghĩa là chấp nhận. Bạn cũng có thể sử dụng lệnh này để chấm dứt thực hiện chương trình.
TinyRAM có hai biến thể tùy thuộc vào nơi các lệnh được thực thi: một biến thể tuân theo kiến trúc Harvard và biến thể kia tuân theo kiến trúc von Neumann. Dữ liệu và chương trình của kiến trúc cũ được lưu trữ trong các không gian địa chỉ khác nhau và các chương trình ở chế độ chỉ đọc; dữ liệu và chương trình của kiến trúc sau được lưu trữ trong cùng một không gian địa chỉ có thể đọc và ghi được. Cụ thể, sự khác biệt giữa hai được thể hiện bằng sơ đồ:
Minh họa hai kiến trúc sau:
Trước khi bắt đầu các chi tiết thiết kế TinyRAM chi tiết hơn, chúng tôi sử dụng ví dụ về sách trắng chính thức để minh họa cách TinyRAM ngắn gọn và toàn diện, đồng thời có thể đáp ứng các vấn đề điện toán không xác định.
tầm quan trọng
Alice sở hữu x và Bob sở hữu w. Alice muốn biết tính đúng đắn của kết quả tính toán của thuật toán A(x, w), nhưng không muốn tự mình tính toán. Tình huống như vậy rất phổ biến trong các hệ thống chứng minh không kiến thức, có người chứng minh và người xác minh, người xác minh muốn biết tính đúng đắn của bằng chứng do người chứng minh cung cấp, nhưng không phải tự mình tính toán lại. Kiến trúc TinyRAM đáp ứng một kịch bản như vậy, trong đó hai băng có thể truyền vào một đầu vào riêng tư w và một đầu vào công khai x, trên đó các thủ tục xác minh và tính toán bằng chứng được thực thi. TinyRAM đã được triển khai trong thư viện libsnark do phòng thí nghiệm SCIPR triển khai. Để biết chi tiết, xem:https://github.com/scipr-lab/libsnark.
Lấy Trình tạo mạch làm ví dụ, sau khi chương trình C đi qua trình biên dịch, nó sẽ được biên dịch thành chương trình TinyRAM và sau khi đi qua Trình tạo mạch, một mạch được tạo và cuối cùng thu được mạch zkSNARK.
chỉ dẫn
TinyRAM hỗ trợ 29 lệnh, mỗi lệnh được chỉ định bởi 1 opcode và tối đa 3 toán hạng. Toán hạng có thể là tên thanh ghi (nghĩa là số nguyên từ 0 đến K-1) hoặc giá trị tức thời (tức là chuỗi W-bit). Trừ khi có quy định khác, mỗi lệnh sẽ không sửa đổi cờ và tăng máy tính lên i (mô-đun 2^W). Đối với kiến trúc Harvard, i=1 và đối với kiến trúc von Neumann, i=2W /8. Thông thường, toán hạng đầu tiên là thanh ghi đích cho phép tính mà lệnh thực hiện và các thao tác khác (nếu có) chỉ định các đối số cho lệnh. Cuối cùng, tất cả các hướng dẫn mất một chu kỳ của máy để thực hiện.
Có một số loại hướng dẫn và tên hướng dẫn tương tự như hướng dẫn lắp ráp intel x86, như tên của nó.
● hướng dẫn thao tác bit：
•and
•or
•xor
•not
● Hướng dẫn thao tác số nguyên:
•add
•sub
•mull
•umulh
•smulh
•udiv
•umod
● thay đổi hoạt động hướng dẫn:
•shl
•shr
● hướng dẫn hoạt động so sánh
•cmpe
•cmpa
•cmpae
•cmpg
•cmpge
●di chuyển hướng dẫn hoạt động
•mov
•cmov
● hướng dẫn thao tác nhảy
•jmp
•cjmp
•cnjmp
● hướng dẫn thao tác bộ nhớ
•store.b
•load.b
•store.w
•load.w
● Nhập lệnh thao tác:
•read
● Hướng dẫn hoạt động đầu ra:
•answer
Hợp ngữ
Các chương trình dành cho TinyRAM được viết bằng ngôn ngữ hợp ngữ TinyRAM, được lấy cảm hứng từ cú pháp ngôn ngữ hợp ngữ x86 của Intel. Các chương trình là các tệp văn bản chứa các dòng mã lắp ráp TinyRAM. Tùy thuộc vào việc chương trình dựa trên kiến trúc Harvard hay kiến trúc von Neumann, các chuỗi chứa trong dòng đầu tiên cũng khác nhau:
• Kiến trúc Harvard
“; TinyRAM V=2.000 M=hv W=W K=K”
• Kiến trúc Von Neumann
“; TinyRAM V=2.000 M=vn W=W K=K”
Trong số đó, W là độ dài từ được biểu thị bằng số thập phân và K là số lượng thanh ghi được biểu thị bằng số thập phân. Trong tệp chương trình, nội dung chứa trong từng dòng khác lần lượt cần thỏa mãn:
1. Không gian tùy chọn.
2. Một nhãn tùy chọn, được xác định để chỉ lệnh đầu tiên theo sau nó.
3. Hướng dẫn tùy chọn, theo hướng dẫn ghi nhớ, theo sau là toán hạng.
4. Không gian tùy chọn.
5. Comment tùy ý bắt đầu bằng dấu chấm phẩy, kết thúc ở cuối dòng.
Trong một chương trình, có thể có nhiều nhất 2^W lệnh. Nhãn chỉ có thể được xác định một lần, giống như một biến trong ngôn ngữ cấp cao.
mã mẫu (https://github.com/scipr-lab/libsnark/blob/master/tinyram_examples/answer0/answer0.s)
Nhằm đáp ứng nhu cầu tính toán và nâng cao hiệu quả đáp ứng mạch, TinyRAM bổ sung thêm phần mở đầu. Nếu một chương trình TinyRAM bắt đầu bằng phần mở đầu, điều đó có nghĩa là chương trình đó là một chương trình phù hợp.
Lời mở đầu ở trên:
• Đối với kiến trúc Harvard, I(i)= 1 * i, và inc = 1
• Đối với kiến trúc von Neumann, I(i) = 2W/8 * i, và inc = W/8
Mã mẫu trước đó cũng tuân theo lời mở đầu này.
So sánh hiệu năng của hai kiến trúc
Sự khác biệt về thiết kế của hai kiến trúc TinyRAM đã được giới thiệu trong phần "Kiến trúc" trước đó và hiệu suất của hai kiến trúc được so sánh ở đây.
Biểu đồ đầu tiên cho thấy số lượng cổng được tạo ra bởi hai kiến trúc.
l là số lệnh, n là kích thước đầu vào và T là số bước thực hiện.
Có thể thấy rằng số lượng cổng và số lượng hướng dẫn tăng tuyến tính đối với cái trước. Cái sau được cải thiện rất nhiều và càng có nhiều hướng dẫn, sự cải thiện càng lớn.
Biểu đồ thứ hai hiển thị thời gian và kích thước bằng chứng của hai kiến trúc để tạo Trình tạo khóa / người chứng minh / người xác minh dưới các đường cong có độ dài từ khác nhau.
Có thể thấy ở 80bit kiến trúc von Neumann có sự cải tiến vượt bậc so với kiến trúc Harvard và ở 128bit cũng có sự cải tiến nhẹ.
tóm tắt
tóm tắt
Chúng tôi đã nói về kiến trúc, thiết kế, hướng dẫn lắp ráp, v.v. của TinyRAM và giới thiệu những ưu điểm của nó: nó có thể được sử dụng để thực hiện các phép tính không xác định một cách thuận tiện. Đặc biệt là trong hệ thống bằng chứng không có kiến thức, có nhiều chỗ để phát triển hơn. Cuối cùng, phần so sánh hiệu suất của hai kiến trúc TinyRAM được giới thiệu.Kiến trúc von Neumann vượt trội hơn về số lượng và thời gian của các cổng được tạo cũng như kích thước của bằng chứng.
Tài khoản công khai WeChat: Sin7Y
http://www.scipr-lab.org/doc/TinyRAM-spec-2.000.pdf
https://www.cs.tau.ac.il/~tromer/slides/csnark-usenix13rump.pdf
http://eprint.iacr.org/2014/59
về chúng tôi
Sin7y được thành lập vào năm 2021 và bao gồm các nhà phát triển chuỗi khối hàng đầu. Chúng tôi vừa là vườn ươm dự án vừa là nhóm nghiên cứu công nghệ chuỗi khối, khám phá các công nghệ tiên tiến và quan trọng nhất như EVM, Layer2, chuỗi chéo, điện toán bảo mật và các giải pháp thanh toán tự động.
Tài khoản công khai WeChat: Sin7Y
GitHub | Twitter | Telegram | Medium| Mirror | HackMD | HackerNoon
IOS
Android