อะไรคือฟังก์ชั่นฮาร์ดหน่วยความจำในอุดมคติ?

หลายสิ่งเหล่านี้กล่าวถึงในบทความในการตั้งค่านี้ "ฝ่ายตรงข้าม" คืออัลกอริทึมบางอย่างที่สามารถประเมินได้ $f_n$ ใช้ทรัพยากรน้อยกว่าที่เราคาดไว้

• $S$ = พื้นที่ / ความซับซ้อนของหน่วยความจำของฝ่ายตรงข้าม ในสายงานนี้ $f_n$ เป็นฟังก์ชั่นที่ทำการเรียกไปยังออราเคิลแบบสุ่ม $H : \{0,1\}^k \ถึง \{0,1\}^k$, และ $S$ คือการใช้พื้นที่ (กรณีที่แย่ที่สุด) ของฝ่ายตรงข้าม โดยวัดเป็น $k$-บิต "บล็อก"

• $T$ = ความซับซ้อนของเวลาของฝ่ายตรงข้าม โดยปกติจะวัดจากจำนวนการโทรเข้า $H$. ในบางรุ่น ฝ่ายตรงข้ามสามารถโทรแบบคู่ขนานได้ $H$ ฟรีดังนั้น $T$ คือจำนวน "รอบต่อเนื่อง" ของการโทรถึง $H$.

• $n$ = พารามิเตอร์ความแข็งที่ปรับได้ของฟังก์ชัน memory-hard ขนาดใหญ่ขึ้น $n$ เพิ่มความพยายามที่จำเป็นในการประเมินฟังก์ชัน $f_n$ (และตามหลักการแล้วความพยายามจะขยายเป็นกำลังสอง $n$). ฝ่ายที่ซื่อสัตย์ควรเลือกที่ใหญ่ที่สุด $n$ เพื่อให้พวกเขาเต็มใจที่จะใช้ความพยายามในการประเมิน $f_n$.

นิยามนี้ดีอย่างไร? ... ดังนั้นฉันเดาว่าคำจำกัดความนี้ไม่แน่นพอที่จะแสดงให้เราเห็นว่า KDF แบบฮาร์ดหน่วยความจำใดดีกว่า

มันเป็นเรื่องจริง $n^2/1000$ แตกต่างกันมากจาก $1000n^2$แต่คำจำกัดความนี้จะพอใจกับฟังก์ชันหน่วยความจำที่มีระดับความยากระดับใดระดับหนึ่งเหล่านี้ ในช่วงเวลาของบทความนี้ ฟังก์ชันเมมโมรี่ฮาร์ดของผู้สมัครส่วนใหญ่คือ โดยไม่แสดงอาการ แย่กว่านั้นมาก $\เธต้า(n^2)$. ดังนั้นคำจำกัดความนี้จึงค่อนข้างมีประสิทธิภาพในการแยกแยะผู้สมัครที่ไม่ดีออกไป เมื่อคุณมีผู้สมัครจำนวนมากที่ตรงใจสิ่งนี้ ไม่มีอาการ คำจำกัดความ จากนั้นคุณสามารถเริ่มกังวลเกี่ยวกับปัจจัยคงที่

คำจำกัดความความแข็งของหน่วยความจำที่ดีกว่านี้คืออะไร?

ใช่ คำจำกัดความนี้พิจารณาเฉพาะ แย่ที่สุด การใช้พื้นที่กรณี $S$. สมมติ $f_n$ เป็นฟังก์ชั่นที่ต้องใช้จริงๆ $n$ หน่วยของหน่วยความจำที่จะประเมิน -- ไม่มีทางที่จะประเมิน $f_n$ โดยไม่ต้องถือ $n$ หน่วยของหน่วยความจำ ในบางจุด. สิ่งนี้ไม่ได้ตัดความเป็นไปได้ที่ $n$ หน่วยหน่วยความจำจำเป็นสำหรับช่วงเวลาสั้นๆ เท่านั้น กล่าวอีกนัยหนึ่ง อาจมีอัลกอริทึมสำหรับ $f_n$ พล็อตของการใช้หน่วยความจำเมื่อเวลาผ่านไปมีลักษณะดังนี้:

(ภาพจาก สไลด์ของ Leo Reyzin บน scrypt)

หากมีอัลกอริทึมนี้ ขีดสุด การใช้พื้นที่ $n$ และยังใช้ $n$ เวลา ความซับซ้อน ST ของมันคือ $\โอเมก้า(n^2)$. ST-complexity เหมือนกับพื้นที่ของสี่เหลี่ยมขอบสีน้ำเงินในภาพนี้

แต่การวัดความแข็งของหน่วยความจำนี้ทำให้ปัญหาบางอย่างไม่ชัดเจน สมมติว่าฝ่ายตรงข้ามต้องการประเมิน $f_n$ ในอินพุตที่แตกต่างกันมากมาย และจัดตารางเวลาการประเมินเหล่านี้อย่างชาญฉลาดดังนี้:

กลยุทธ์นี้สามารถใช้เพื่อประเมินตัวอย่าง $f_n$ บน $n$ อินพุตที่แตกต่างกันโดยใช้เท่านั้น $O(n)$ เวลาและ $O(n)$ หน่วยความจำทั้งหมด! ดังนั้น "ต้นทุน ST" ทั้งหมดเพื่อประเมินฟังก์ชัน $n$ ครั้งคือ $O(n^2)$มีความหมายว่า ตัดจำหน่าย ราคาต่ออินสแตนซ์เท่านั้น $O(n)$.

วิธีที่ดีกว่าในการจำแนกความแข็งของหน่วยความจำของฟังก์ชันคือการวัดค่า พื้นที่ใต้เส้นโค้ง มากกว่าพื้นที่ของกรอบ นี่คือสิ่งที่เสนอใน ผลงานที่ตามมาซึ่งเมทริกซ์ความแข็งของหน่วยความจำเรียกว่า "ความซับซ้อนของหน่วยความจำสะสม"