Score:0

อัลกอริทึมเพื่อตรวจสอบอินพุต 1 จาก N เป็นส่วนหนึ่งของแฮชเอาต์พุต

ธง us

มีอัลกอริทึมที่ช่วยให้พิสูจน์ว่าอินพุต x1 ถูกใช้เป็นอินพุต 1 จาก N เพื่อสร้างแฮชเอาต์พุต โดยไม่ทราบอินพุตอื่น ๆ ?

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

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

ข้อมูลเพิ่มเติมเกี่ยวกับกรณีการใช้งานที่เป็นรูปธรรม:

  1. ฉันต้องแสดงสถานะของระบบอย่างกระชับ (แฮช?)
  2. สถานะเปลี่ยนแปลง/พัฒนาอย่างต่อเนื่องตามอินพุตของผู้ใช้ใหม่
  3. ต้องมีวิธีตรวจสอบว่าอินพุตของผู้ใช้เฉพาะนั้นสะท้อนให้เห็นในสถานะปัจจุบันหรือไม่

วิธีทื่อคือการแสดงสถานะของระบบเป็นรายการอินพุต แต่ไม่ได้ผลเนื่องจากข้อจำกัดบางประการ
ดังนั้นฉันจึงหวังว่าจะมีฟังก์ชันการเข้ารหัสที่ช่วยให้รัฐสามารถแสดงได้อย่างกระชับ ฉันได้ตรวจสอบต้นไม้ Merkle, แบบแผนหลายลายเซ็น ฯลฯ แต่จนถึงตอนนี้ยังไม่พบสิ่งที่เหมาะสมกับการเรียกเก็บเงินจริงๆ

ph flag
ดูเหมือนว่าคุณจะสามารถแก้ปัญหาได้ด้วย Merkle Tree https://en.wikipedia.org/wiki/Merkle_tree
TommyF avatar
us flag
@ bmm6o น่าเสียดายที่ไม่ต้องมีความรู้เกี่ยวกับอินพุตอื่นหรือแฮชรวม แต่ขอขอบคุณสำหรับคำแนะนำ!
ph flag
ใช่ ต้นไม้จะต้องพร้อมใช้งานสำหรับทุกคนที่ต้องการตรวจสอบการคำนวณ
SEJPM avatar
us flag
ดังนั้น สิ่งที่คุณต้องการพิสูจน์ก็คือสำหรับค่าที่กำหนด $y$ มี $x_i$ อยู่บางส่วนจากชุดของขนาด $N$ ของค่า $S=\{x_1,x_2,\ldots,x_N\}$ เช่นนั้น $y=H(x_i)$ และที่คุณรู้ว่า $x_i$ (อาจไม่เปิดเผย?)? อนุญาตให้มีการโต้ตอบในการพิสูจน์ดังกล่าวหรือจำเป็นต้องเป็นคำสั่งที่เทียบได้กับค่าแฮช
TommyF avatar
us flag
@SEJPM ฉันได้เพิ่มข้อมูลเพิ่มเติมเกี่ยวกับกรณีการใช้งานที่เป็นรูปธรรมของฉันเพื่อให้ชัดเจนยิ่งขึ้น ขอบคุณที่พยายามช่วย!
Ben Voigt avatar
cn flag
@TommyF: คุณเคยทดสอบแนวคิดนี้โดยหลักการของ Pigeonhole หรือไม่ นั่นคือ ถ้าแต่ละอินพุต *N* มีความยาว *k* บิต และเอาต์พุตแฮชมีความยาว `x` บิต ดังนั้นหาก `x > N*k` เอาต์พุตเดียวกันสามารถสร้างได้ด้วยอินพุตที่แตกต่างกันจำนวนมาก (2* *(x - N*k)) ดังนั้น แม้ว่าคุณจะมีอินพุตที่สมบูรณ์และสร้างการคำนวณแฮชซ้ำโดยได้รับเอาต์พุตเดียวกัน คุณไม่มีทางรู้ได้เลยว่าคุณมีอินพุตดั้งเดิมหรือแค่เกิดการชนกัน

โพสต์คำตอบ

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