สมมติว่าอลิซมีรายการค่าต่างๆ และบ็อบส่งราก Merkle ของอลิซที่เขาอ้างว่ามีไว้สำหรับรายการค่านี้ แน่นอนว่าอัลกอริทึมการสร้าง Merkle tree นั้นเป็นที่ทราบกันดีอยู่แล้ว
จากนั้นอลิซสามารถเลือกค่าตามอำเภอใจจากรายการและขอหลักฐานจาก Merkle จาก Bob
สมมติว่าอลิซต้องการหลีกเลี่ยงการสร้างต้นไม้ทั้งต้นเพื่อยืนยันรากของ Merkle ของ Bob เธอจะแน่ใจได้อย่างไรว่ารูทของ Merkle ของ Bob นั้นถูกต้อง หลังจากที่ Bob ได้ส่งหลักฐาน N Merkle แล้ว กล่าวอีกนัยหนึ่งความน่าจะเป็นที่ Bob โกหกเกี่ยวกับรากของ Merkle หลังจากการสืบค้น N ครั้งคืออะไร
แก้ไข:
ฉันมีคำตอบอยู่ในใจแต่คิดว่าไม่ถูกสมมติว่าเรามีทรีที่มีโหนด M ทั้งหมด (นับรวมเลเยอร์ทั้งหมด) และการพิสูจน์แต่ละรายการในทรีนั้นมี N แฮชเป็นจุดข้อมูลในการพิสูจน์ หากอลิซขอการพิสูจน์ที่แยกจาก K เธอก็มั่นใจได้ว่ารากนั้นถูกต้องด้วยค่าความเชื่อมั่น (N*K)/M
ดูเหมือนไร้เดียงสาและแบบนี้จะเป็นเพียงขอบเขตที่ต่ำกว่า เนื่องจากมีอะไรมากกว่านั้น ต้นไม้ทำจากแฮชที่มีความต้านทานพรีอิมเมจ ดังนั้นจึงไม่ใช่แค่คำถามของการนับจุดข้อมูลที่รู้จักเทียบกับจุดข้อมูลทั้งหมด... ใช่หรือไม่
แก้ไข #2:
สูตรอื่น:
เมื่อกำหนดเวกเตอร์ที่ทราบค่าโดยพลการ V และ Merkle root R ที่สร้างขึ้นโดยการสร้าง Merkle tree สำหรับ V ถ้าฉันมีหลักฐาน N Merkle ฉันจะแน่ใจได้อย่างไรว่า R ถูกสร้างขึ้นอย่างตรงไปตรงมาและถูกต้องจาก V
เห็นได้ชัดว่าฉันสามารถสร้างต้นไม้ขึ้นใหม่ได้เนื่องจากฉันมี (หรือสามารถคำนวณ) V ทั้งหมดได้ แต่สมมติว่าฉันไม่ต้องการเพราะมันใช้เวลานาน เป็นต้น
กล่าวอีกนัยหนึ่งความน่าจะเป็นที่ Bob โกหกเกี่ยวกับรากของ Merkle หลังจากการสืบค้น N ครั้งคืออะไร
นี่เป็นวิธีหนึ่งที่ Bob สามารถโกงได้ เขาสามารถนำรายชื่อของ $M$ ค่า $$V_1, V_2, ..., V_M$$ และแทนที่จะสร้าง Merkle tree ตามนั้น ให้เลือกค่า $ค$ ดัชนีและค่า $V'_c \ne V_c$และสร้างรายการแทน $$V_1, V_2, ..., V_{c-1}, V'_c, V_{c+1}, ..., V_M$$ และสร้างต้นไม้ Merkle ตามรายการนั้น (และให้รากที่คำนวณได้แก่อลิซ ซึ่งมีความเป็นไปได้สูงที่แตกต่างจากรากจากรายการดั้งเดิม)
จากนั้นเมื่ออลิซให้เขา $K$ ดัชนีฐาน $K$ พิสูจน์บน เขาสร้างพวกเขาตามรายการที่แก้ไขและต้นไม้ที่เขาคำนวณ เขาจะถูกจับได้ว่าโกงก็ต่อเมื่อหนึ่งในดัชนีที่เธอขอเป็นดัชนีนั้น $ค$; หากไม่มีดัชนีใดที่เธอขอเกิดขึ้นเพื่อเป็นดัชนี $ค$จากนั้นหลักฐานที่เธอจะได้รับนั้นถูกต้องและสอดคล้องกันทั้งหมด (เนื่องจากสอดคล้องกับต้นไม้ Merkle ที่สอดคล้องกันในตัวเอง โดยใบไม้ที่เปิดเผยเป็นค่าที่เธอคาดหวัง)
ความน่าจะเป็นที่บ็อบถูกจับได้ว่าโกง นั่นคือ ความน่าจะเป็นที่หนึ่งในดัชนีที่อลิซเลือกคือ $ค$, เป็น $K/M$. ดังนั้น ความน่าจะเป็นในการตรวจจับกับกลยุทธ์ใดๆ นั้นไม่มากไปกว่านั้น (อาจน้อยกว่านี้หากมีกลยุทธ์ที่ดีกว่าที่ Bob สามารถใช้ได้)
ดังนั้นเพื่อตรวจจับการโกงของ Bob ด้วยความน่าจะเป็น 0.99 เรามี $K > 0.99M$; เมื่อถึงจุดนั้น การคำนวณของอลิซจะน้อยลง หากเธอเพียงแค่คำนวณต้นไม้ใหม่ด้วยตัวเอง
ดูน่าสนใจสำหรับเราเพราะมันสามารถเป็นรูปแบบของการพิสูจน์อวกาศได้หากรายการมีราคาแพงในการสร้าง
ตอนนี้ การมองปัญหาเป็นการพิสูจน์การทำงานนั้นน่าสนใจกว่าเล็กน้อย (การพิสูจน์พื้นที่ไม่ทำงาน เนื่องจากสามารถคำนวณต้นไม้และพาธการตรวจสอบสิทธิ์ได้โดยไม่ต้องเพิ่มจำนวนการคำนวณที่จำเป็นอย่างมาก) เห็นได้ชัดว่ากลยุทธ์การโกงที่ฉันให้ไว้ข้างต้นไม่ได้ทำลายปัญหานั้น เนื่องจาก Bob กำลังทำงานเต็มจำนวน ถ้าฉันมีเวลามากกว่านี้ ฉันจะพยายามตรวจสอบให้มากกว่านี้...
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
