TinyRAM เป็นสถาปัตยกรรมการเข้าถึงแบบสุ่มที่นำเสนอโดยกลุ่มสมาชิก 5 คนของ BCTGTV ที่มีชื่อเสียง (Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza) และ SCIPR Laboratory โดยมีจุดมุ่งหมายเพื่อพิสูจน์ว่าเป็นเครื่องมือที่มีประโยชน์สำหรับการคำนวณแบบ non-deterministic โดยเฉพาะอย่างยิ่ง TinyRAM เป็นคอมพิวเตอร์ชุดคำสั่งแบบย่อ (RISC) ที่มีหน่วยความจำเข้าถึงโดยสุ่มแอดเดรสระดับไบต์ มันสร้างความสมดุลระหว่างสิ่งที่ตรงกันข้ามของ "การแสดงออกเพียงพอ" และ "เรียบง่ายเพียงพอ":

• แสดงออกมากพอที่จะรองรับรหัสแอสเซมบลีที่สั้นและมีประสิทธิภาพเมื่อคอมไพล์จากภาษาโปรแกรมระดับสูง และ

•ชุดคำสั่งขนาดเล็ก คำสั่งสามารถตรวจสอบได้ง่ายโดยวงจรการทำงาน และการตรวจสอบที่มีประสิทธิภาพเกิดขึ้นได้โดยใช้กลไกอัลกอริทึมและรหัสผ่านของ SCIPR

สถาปัตยกรรม

TinyRAM กำหนดพารามิเตอร์ด้วยจำนวนเต็มสองตัว: ความยาวของคำ W ซึ่งต้องเป็นเลขยกกำลังของ 2 และหารด้วย 8 ลงตัว (เหมือนกับคอมพิวเตอร์สมัยใหม่ เช่น 32, 64) และจำนวนของการลงทะเบียน K โดยทั่วไปจะแสดงด้วย TinyRAM(W,K) สถานะของเครื่องประกอบด้วยสิ่งต่อไปนี้:

1. โปรแกรมเคาน์เตอร์พีซี (โปรแกรมเคาน์เตอร์) ประกอบด้วย W บิต

2. K รีจิสเตอร์อเนกประสงค์ แสดงด้วย r0, r1, ..., r(K-1) แต่ละรีจิสเตอร์คือ W บิต

3. ธงสถานะเงื่อนไขประกอบด้วยหนึ่งบิต

4. หน่วยความจำ อาร์เรย์เชิงเส้นขนาด 2^W ไบต์ โดยใช้หลักการ little-endian เพื่อจัดเรียงไบต์

5. เทป 2 เทป แต่ละเทปมีสตริง W bit word แต่ละเทปเป็นแบบอ่านอย่างเดียวในทิศทางเดียว ในหมู่พวกเขา เทปหนึ่งสำหรับอินพุตสาธารณะ x และอีกเทปหนึ่งสำหรับอินพุตส่วนตัว w ในความเป็นจริงมันเป็นผู้ให้บริการอินพุตของ TinyRAM

อินพุตของเครื่อง TinyRAM คือ 2 เทปและหน่วยความจำ และเอาต์พุตคือคำสั่งรับสาย ซึ่งมีพารามิเตอร์ A ซึ่งแทนค่าที่ส่งคืน และ A = 0 หมายถึงการยอมรับ คุณยังสามารถใช้คำสั่งนี้เพื่อยุติการทำงานของโปรแกรม

TinyRAM มีสองรูปแบบขึ้นอยู่กับตำแหน่งที่ดำเนินการคำสั่ง: ตัวแปรหนึ่งเป็นไปตามสถาปัตยกรรม Harvard และอีกรูปแบบหนึ่งเป็นไปตามสถาปัตยกรรม von Neumann ข้อมูลและโปรแกรมของสถาปัตยกรรมเดิมถูกจัดเก็บในพื้นที่ที่อยู่ที่แตกต่างกัน และโปรแกรมเป็นแบบอ่านอย่างเดียว ข้อมูลและโปรแกรมของสถาปัตยกรรมหลังจะถูกจัดเก็บไว้ในพื้นที่ที่อยู่แบบอ่านและเขียนได้เดียวกัน โดยเฉพาะอย่างยิ่ง ความแตกต่างระหว่างทั้งสองจะแสดงด้วยไดอะแกรม:

ภาพประกอบของสองสถาปัตยกรรมต่อไปนี้:

ก่อนที่จะเริ่มรายละเอียดการออกแบบ TinyRAM ที่มีรายละเอียดมากขึ้น เราใช้ตัวอย่างเอกสารไวท์เปเปอร์อย่างเป็นทางการเพื่อแสดงให้เห็นว่า TinyRAM มีความกระชับและครอบคลุมเพียงใด และสามารถตอบสนองปัญหาการคำนวณที่ไม่ได้กำหนดได้

ความสำคัญ

อลิซเป็นเจ้าของ x และบ็อบเป็นเจ้าของ w อลิซต้องการทราบความถูกต้องของผลการคำนวณของอัลกอริทึม A(x, w) แต่ไม่ต้องการคำนวณเอง สถานการณ์ดังกล่าวเป็นเรื่องปกติมากในระบบการพิสูจน์ที่ไม่มีความรู้ มีผู้พิสูจน์ และผู้ตรวจสอบ ผู้ตรวจสอบต้องการทราบความถูกต้องของหลักฐานที่ผู้พิสูจน์ให้ไว้ แต่ไม่จำเป็นต้องคำนวณใหม่ด้วยตนเอง สถาปัตยกรรม TinyRAM เป็นไปตามสถานการณ์ดังกล่าว โดยเทปสองรายการสามารถผ่านอินพุตส่วนตัว w และอินพุตสาธารณะ x ซึ่งใช้การคำนวณพิสูจน์และขั้นตอนการตรวจสอบ TinyRAM ถูกนำไปใช้ในไลบรารี libsnark ที่ดำเนินการโดยห้องปฏิบัติการ SCIPR สำหรับรายละเอียด โปรดดู:https://github.com/scipr-lab/libsnark.

ยกตัวอย่าง Circuit Generator หลังจากโปรแกรม C ผ่านคอมไพเลอร์ มันจะถูกคอมไพล์เป็นโปรแกรม TinyRAM และหลังจากผ่าน Circuit Generator วงจรจะถูกสร้างขึ้น และสุดท้ายจะได้วงจร zkSNARK

คำแนะนำ

TinyRAM รองรับ 29 คำสั่ง แต่ละคำสั่งระบุด้วย 1 opcode และสูงสุด 3 ตัวถูกดำเนินการ ตัวดำเนินการสามารถเป็นชื่อรีจิสเตอร์ (เช่น จำนวนเต็มตั้งแต่ 0 ถึง K-1) หรือค่าทันที (เช่น สตริง W-bit) แต่ละคำสั่งจะไม่แก้ไขค่าสถานะ และเพิ่ม pc โดย i (modulo 2^W) สำหรับสถาปัตยกรรม Harvard i=1 และสำหรับสถาปัตยกรรม von Neumann i=2W /8 โดยทั่วไป ตัวถูกดำเนินการตัวแรกคือรีจิสเตอร์ปลายทางสำหรับการคำนวณที่คำสั่งดำเนินการ และการดำเนินการอื่นๆ (ถ้ามี) จะระบุอาร์กิวเมนต์สำหรับคำสั่ง ในท้ายที่สุด คำสั่งทั้งหมดจะใช้เวลาหนึ่งรอบของเครื่องในการดำเนินการ

มีคำสั่งหลายประเภท และชื่อคำสั่งจะคล้ายกับคำสั่งการประกอบ Intel x86 ตามชื่อที่สื่อถึง

● คำแนะนำในการจัดการบิต：

•and

•or

•xor

•not

● คำแนะนำการจัดการจำนวนเต็ม:

•add

•sub

•mull

•umulh

•smulh

•udiv

•umod

● คำสั่งการทำงานกะ:

•shl

•shr

● คำแนะนำการดำเนินการเปรียบเทียบ

•cmpe

•cmpa

•cmpae

•cmpg

•cmpge

●ย้ายคำแนะนำการใช้งาน

•mov

•cmov

● คำแนะนำการดำเนินการกระโดด

•jmp

•cjmp

•cnjmp

● คำแนะนำการจัดการหน่วยความจำ

•store.b

•load.b

•store.w

•load.w

● ป้อนคำสั่งการทำงาน:

•read

● คำแนะนำการใช้งานเอาต์พุต:

•answer

ภาษาแอสเซมบลี

โปรแกรมสำหรับ TinyRAM เขียนด้วยภาษาแอสเซมบลีของ TinyRAM ซึ่งได้รับแรงบันดาลใจจากไวยากรณ์ภาษาแอสเซมบลีของ Intel x86 โปรแกรมคือไฟล์ข้อความที่มีบรรทัดของโค้ดแอสเซมบลี TinyRAM ขึ้นอยู่กับว่าโปรแกรมใช้สถาปัตยกรรม Harvard หรือสถาปัตยกรรม von Neumann สตริงที่อยู่ในบรรทัดแรกก็แตกต่างกันเช่นกัน:

• สถาปัตยกรรมฮาร์วาร์ด

“; TinyRAM V=2.000 M=hv W=W K=K”

• สถาปัตยกรรมฟอนนอยมันน์

“; TinyRAM V=2.000 M=vn W=W K=K”

ในหมู่พวกเขา W คือความยาวของคำที่แสดงเป็นทศนิยม และ K คือจำนวนของการลงทะเบียนที่แสดงเป็นทศนิยม ในไฟล์โปรแกรม เนื้อหาที่อยู่ในแต่ละบรรทัดจะต้องเป็นไปตาม:

1. ช่องว่างเพิ่มเติม

2. ฉลากทางเลือก กำหนดให้อ้างถึงคำสั่งแรกที่ตามมา

3. คำสั่งทางเลือก โดยคำสั่งช่วยจำ ตามด้วยตัวถูกดำเนินการ

4. ช่องว่างเพิ่มเติม

5. ความคิดเห็นที่เลือกที่จะเริ่มต้นด้วยเครื่องหมายอัฒภาคและสิ้นสุดที่ท้ายบรรทัด

ในโปรแกรมหนึ่งๆ สามารถมีคำสั่งได้สูงสุด 2^W ป้ายกำกับสามารถกำหนดได้เพียงครั้งเดียว คล้ายกับตัวแปรในภาษาระดับสูง

โค้ดตัวอย่าง (https://github.com/scipr-lab/libsnark/blob/master/tinyram_examples/answer0/answer0.s)

เพื่อตอบสนองความต้องการในการคำนวณและปรับปรุงประสิทธิภาพของวงจร TinyRAM เพิ่มคำนำ หากโปรแกรม TinyRAM เริ่มต้นด้วยคำนำหน้า แสดงว่าโปรแกรมนั้นเป็นโปรแกรมที่เหมาะสม

คำนำข้างต้น:

• สำหรับสถาปัตยกรรมฮาร์วาร์ด I(i)= 1 * i และ inc = 1

• สำหรับสถาปัตยกรรม von Neumann I(i) = 2W/8 * i และ inc = W/8

โค้ดตัวอย่างก่อนหน้านี้ยังเป็นไปตามคำนำนี้ด้วย

การเปรียบเทียบประสิทธิภาพของทั้งสองสถาปัตยกรรม

ความแตกต่างด้านการออกแบบของสถาปัตยกรรมทั้งสองของ TinyRAM ได้รับการแนะนำในส่วน "สถาปัตยกรรม" ก่อนหน้านี้ และเปรียบเทียบประสิทธิภาพของสถาปัตยกรรมทั้งสองที่นี่

กราฟแรกแสดงจำนวนประตูที่ผลิตโดยสถาปัตยกรรมทั้งสอง

l คือจำนวนคำสั่ง n คือขนาดอินพุต และ T คือจำนวนขั้นตอนการดำเนินการ

จะเห็นได้ว่าจำนวนประตูและจำนวนคำสั่งเพิ่มขึ้นแบบเชิงเส้นสำหรับอันแรก การปรับปรุงอย่างหลังดีขึ้นอย่างมาก และยิ่งมีคำแนะนำมากเท่าไร

แผนภูมิที่สองแสดงเวลาและขนาดการพิสูจน์ของทั้งสองสถาปัตยกรรมเพื่อสร้างตัวสร้างคีย์ / ผู้พิสูจน์ / ผู้ตรวจสอบภายใต้ส่วนโค้งของความยาวของคำที่แตกต่างกัน

จะเห็นได้ว่าที่ 80 บิต สถาปัตยกรรม von Neumann มีการปรับปรุงที่ดีกว่าเมื่อเทียบกับสถาปัตยกรรม Harvard และที่ 128 บิต ก็มีการปรับปรุงเล็กน้อยเช่นกัน

สรุป

สรุป

เราได้พูดคุยเกี่ยวกับสถาปัตยกรรม การออกแบบ คำแนะนำในการประกอบ และอื่นๆ ของ TinyRAM และแนะนำข้อดีของมัน: สามารถใช้ในการคำนวณแบบไม่มีกำหนด โดยเฉพาะอย่างยิ่งในระบบพิสูจน์ความรู้เป็นศูนย์ มีพื้นที่สำหรับการพัฒนามากขึ้น ในที่สุด การเปรียบเทียบประสิทธิภาพของสถาปัตยกรรม TinyRAM ทั้งสองจะแนะนำ สถาปัตยกรรม von Neumann นั้นเหนือกว่าในแง่ของจำนวนและเวลาของประตูที่สร้างขึ้นและขนาดของการพิสูจน์

บัญชี 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

เกี่ยวกับเรา

Sin7y ก่อตั้งขึ้นในปี 2564 และประกอบด้วยนักพัฒนาบล็อกเชนชั้นนำ เราเป็นทั้งผู้บ่มเพาะโครงการและทีมวิจัยเทคโนโลยีบล็อกเชน สำรวจเทคโนโลยีที่สำคัญและล้ำสมัยที่สุด เช่น EVM, Layer2, cross-chain, การประมวลผลเพื่อความเป็นส่วนตัว และโซลูชันการชำระเงินอัตโนมัติ

บัญชี WeChat สาธารณะ: Sin7Y

GitHub | Twitter | Telegram | Medium| Mirror | HackMD | HackerNoon