การคำนวณที่ตรวจสอบได้ (หรือการคำนวณที่ได้รับการตรวจสอบหรือการคำนวณที่ได้รับการตรวจสอบ ) ช่วยให้คอมพิวเตอร์สามารถถ่ายโอนการคำนวณ ของฟังก์ชันบางอย่างไปยัง ไคลเอนต์อื่น ๆ ที่อาจไม่น่าเชื่อถือในขณะที่ยังคงรักษาผลลัพธ์ที่ตรวจสอบได้ ไคลเอนต์อื่น ๆ จะประเมินฟังก์ชันและส่งคืนผลลัพธ์พร้อมหลักฐานว่าการคำนวณของฟังก์ชันนั้นดำเนินการอย่างถูกต้อง แนวคิดนี้เกิดขึ้นจากปรากฏการณ์ที่พบได้บ่อยขึ้นเรื่อย ๆ ของการ " เอาท์ซอร์ส " การคำนวณให้กับผู้ใช้ที่ไม่น่าเชื่อถือในโครงการต่าง ๆ เช่นSETI@homeและความต้องการที่เพิ่มขึ้นในการเปิดใช้งานอุปกรณ์ที่มีความสามารถในการคำนวณต่ำให้สามารถเอาท์ซอร์สงานคำนวณไปยังบริการคำนวณที่มีประสิทธิภาพมากกว่า เช่น ในคลาวด์คอมพิวติ้งแนวคิดนี้มีที่มาจากงานของ Babai et al. ^{[ 1 ]}และได้รับการศึกษาภายใต้เงื่อนไขต่าง ๆ รวมถึง "การตรวจสอบการคำนวณ" (Babai et al.) "การมอบหมายการคำนวณ" ^{[ 2 ]} "การคำนวณที่ได้รับการรับรอง" ^{[ 3 ]}และการคำนวณที่ตรวจสอบได้ คำว่าการคำนวณที่ตรวจสอบได้นั้นได้รับการกำหนดอย่างเป็นทางการโดย Rosario Gennaro, Craig Gentryและ Bryan Parno ^{[ 4 ]}และสะท้อนถึง "การคำนวณที่ได้รับการรับรอง" ของ Micali ^{[ 3 ]}

ความต้องการที่เพิ่มขึ้นในการมอบหมายงานคำนวณจากอุปกรณ์คำนวณที่ค่อนข้างอ่อนแอ (ไคลเอ็นต์) ไปยังบริการคำนวณที่มีประสิทธิภาพมากกว่า (เวิร์กเกอร์) และปัญหาของเวิร์กเกอร์ที่ไม่ซื่อสัตย์ซึ่งแก้ไขซอฟต์แวร์ของไคลเอ็นต์เพื่อให้ได้ผลลัพธ์ที่น่าเชื่อถือโดยไม่ต้องทำงานจริง^{[ 5 ]}เป็นแรงผลักดันให้เกิดการกำหนดแนวคิดของการคำนวณที่ตรวจสอบได้^{[ 4 ]}

การคำนวณที่ตรวจสอบได้นั้นไม่เพียงแต่เกี่ยวข้องกับการได้ผลลัพธ์จากฟังก์ชันที่จ้างภายนอกไปยังข้อมูลป้อนเข้าของลูกค้าและการพิสูจน์ความถูกต้องเท่านั้น แต่ยังรวมถึงการที่ลูกค้าสามารถตรวจสอบความถูกต้องของการพิสูจน์ได้ด้วยความพยายามในการคำนวณที่น้อยกว่าการคำนวณฟังก์ชันนั้นตั้งแต่เริ่มต้นอย่างมากอีกด้วย

มีการให้ความสนใจอย่างมากในการตรวจสอบการคำนวณฟังก์ชันที่ดำเนินการโดยผู้ปฏิบัติงานที่ไม่น่าเชื่อถือ รวมถึงการใช้^ตัว ประมวล ผลร่วมที่ปลอดภัย [ ^{6 ] [ 7 ]}โมดูลแพลตฟอร์มที่เชื่อถือได้ (TPMs) ^{[ 8 ]} การ พิสูจน์แบบโต้ตอบ^{[ 9 ] [ 10 ]}การพิสูจน์ที่ตรวจสอบได้ด้วยความน่าจะเป็น^{[ 11 ] [ 12 ]}ข้อโต้แย้งที่มีประสิทธิภาพ^{[ 13 ] [ 14 ]}และการพิสูจน์ CS ของ Micali ^{[ 15 ]}การตรวจสอบเหล่านี้เป็นแบบโต้ตอบซึ่งต้องการให้ไคลเอนต์โต้ตอบกับผู้ปฏิบัติงานเพื่อตรวจสอบความถูกต้องของการพิสูจน์^{[ 13 ] [ 14 ]}หรือเป็นโปรโตคอลที่ไม่ใช่แบบโต้ตอบซึ่งสามารถพิสูจน์ได้ในแบบจำลองออราเคิลแบบสุ่ม^{[ 15 ]}

การคำนวณที่ได้รับการตรวจสอบที่ใหญ่ที่สุด ( SETI@home ) ใช้การตรวจสอบโดยการจำลองแบบ

กระบวนการตรวจสอบ SETI @homeประกอบด้วยเครื่องไคลเอ็นต์หนึ่งเครื่องและเครื่องเวิร์กเกอร์หลายเครื่อง เครื่องไคลเอ็นต์จะส่งเวิร์กยูนิตที่เหมือนกันไปยังคอมพิวเตอร์หลายเครื่อง (อย่างน้อย 2 เครื่อง)

เมื่อผลลัพธ์ไม่เพียงพอภายในระยะเวลาที่เหมาะสม—เนื่องจากเครื่องปิดโดยไม่ได้ตั้งใจ การสื่อสารขัดข้อง ฯลฯ—หรือผลลัพธ์ไม่ตรงกัน—เนื่องจากข้อผิดพลาดในการคำนวณ การโกงโดยการส่งข้อมูลเท็จโดยไม่ได้ทำงานจริง ฯลฯ—เครื่องไคลเอ็นต์จะส่งหน่วยงานที่เหมือนกันเพิ่มเติมไปยังเครื่องทำงานอื่น ๆ เมื่อผลลัพธ์อย่างน้อยหนึ่งชุด (มักจะเป็น 2 ชุด) ตรงกันแล้ว ไคลเอ็นต์จะถือว่าผลลัพธ์เหล่านั้น (และผลลัพธ์ที่เหมือนกันอื่น ๆ สำหรับหน่วยงานนั้น) ถูกต้อง ไคลเอ็นต์จะให้เครดิตแก่เครื่องทั้งหมดที่ส่งผลลัพธ์ที่ถูกต้องกลับมา

Gennaro et al. ^{[ 4 ]}ได้นิยามแนวคิดของแผนการคำนวณที่ตรวจสอบได้ว่าเป็นโปรโตคอลระหว่างสองฝ่ายที่มีเวลาพหุนามเพื่อร่วมมือกันในการคำนวณฟังก์ชัน F: {0,1} ⁿ → {0,1} ^mแผนการนี้ประกอบด้วยสามขั้นตอนหลัก:

1. การประมวลผลเบื้องต้นขั้นตอนนี้จะดำเนินการเพียงครั้งเดียวโดยฝั่งไคลเอนต์ เพื่อคำนวณข้อมูลเสริมบางอย่างที่เกี่ยวข้องกับ F ข้อมูลส่วนหนึ่งเป็นข้อมูลสาธารณะที่จะแบ่งปันกับผู้ปฏิบัติงาน ในขณะที่ส่วนที่เหลือเป็นข้อมูลส่วนตัวและเก็บไว้กับฝั่งไคลเอนต์
2. การเตรียมข้อมูลป้อนเข้าในขั้นตอนนี้ ไคลเอนต์จะคำนวณข้อมูลเสริมบางอย่างเกี่ยวกับข้อมูลป้อนเข้าของฟังก์ชัน ข้อมูลส่วนหนึ่งเป็นข้อมูลสาธารณะ ในขณะที่ส่วนที่เหลือเป็นข้อมูลส่วนตัวและเก็บไว้กับไคลเอนต์ ข้อมูลสาธารณะจะถูกส่งไปยังเวิร์กเกอร์เพื่อคำนวณฟังก์ชัน F บนข้อมูลป้อนเข้า
3. การคำนวณและการตรวจสอบผลลัพธ์ในขั้นตอนนี้ ตัวประมวลผลจะใช้ข้อมูลสาธารณะที่เกี่ยวข้องกับฟังก์ชัน F และอินพุต ซึ่งคำนวณได้ในสองขั้นตอนก่อนหน้า เพื่อคำนวณผลลัพธ์ที่เข้ารหัส ของฟังก์ชัน F บนอินพุตที่ให้มา จากนั้นผลลัพธ์นี้จะถูกส่งกลับไปยังไคลเอนต์เพื่อตรวจสอบความถูกต้อง โดยการคำนวณค่าจริงของผลลัพธ์โดยการถอดรหัสผลลัพธ์ที่ส่งคืนโดยตัวประมวลผลโดยใช้ข้อมูลส่วนตัวที่คำนวณได้ในขั้นตอนก่อนหน้า

แนวคิดที่กำหนดไว้ของแผนการคำนวณที่ตรวจสอบได้จะลดปฏิสัมพันธ์ระหว่างไคลเอนต์และผู้ปฏิบัติงานให้เหลือเพียงสองข้อความ โดยแต่ละฝ่ายจะส่งข้อความเดียวไปยังอีกฝ่ายในระหว่างขั้นตอนต่างๆ ของโปรโตคอล^{[ 4 ]}

Gennaro และคณะ^{[ 4 ]}ได้กำหนดรูปแบบการคำนวณที่ตรวจสอบได้สำหรับฟังก์ชันF ใดๆ โดยใช้วงจรที่บิดเบือนของ Yao ^{[ 16 ] [ 17 ]}ร่วมกับระบบการเข้ารหัสแบบโฮโมมอร์ฟิกอย่างสมบูรณ์

แผนการคำนวณที่ตรวจสอบได้VC นี้ ถูกกำหนดไว้ดังนี้: ^{[ 4 ]}

VC = (KeyGen, ProbGen, Compute, Verify)ประกอบด้วยอัลกอริทึมสี่อย่างดังต่อไปนี้:

1. KeyGen(F, λ) → (PK, SK) : อัลกอริทึมการสร้างคีย์ แบบสุ่ม จะสร้างคีย์สองชุด คือ คีย์สาธารณะและคีย์ส่วนตัว โดยอิงตามพารามิเตอร์ความปลอดภัย λ คีย์สาธารณะจะเข้ารหัสฟังก์ชันเป้าหมาย F และถูกส่งไปยังตัวประมวลผลเพื่อคำนวณ F ในขณะที่คีย์ส่วนตัวจะถูกเก็บไว้เป็นส่วนตัวโดยไคลเอ็นต์
2. ProbGen(SK, x) → (σx, τx) : อัลกอริทึมการสร้างปัญหาจะเข้ารหัสอินพุตฟังก์ชัน x เป็นสองค่า คือค่าสาธารณะและค่าส่วนตัว โดยใช้กุญแจลับ SK ค่าสาธารณะ σx จะถูกส่งไปยังตัวประมวลผลเพื่อคำนวณ F(x) ในขณะที่ค่าลับ τx จะถูกเก็บไว้เป็นส่วนตัวโดยไคลเอนต์
3. Compute(PK, σx) → σy : ตัวประมวลผลจะคำนวณค่าที่เข้ารหัส σy ของผลลัพธ์ y = F(x) ของฟังก์ชัน โดยใช้คีย์สาธารณะ PK ของไคลเอ็นต์และอินพุตที่เข้ารหัส σx
4. ตรวจสอบ_SK (τx, σy) → y ∪ ⊥ : อัลกอริทึมการตรวจสอบจะแปลงเอาต์พุตที่เข้ารหัส σy ของผู้ปฏิบัติงานให้เป็นเอาต์พุตจริงของฟังก์ชัน F โดยใช้ทั้งกุญแจลับ SK และ "การถอดรหัส" ลับ τx โดยจะส่งออก y = F(x) หาก σy แสดงถึงเอาต์พุตที่ถูกต้องของ F บน x หรือส่งออก ⊥ ในกรณีอื่น ๆ

โปรโตคอลของแผนการคำนวณที่ตรวจสอบได้ซึ่งกำหนดโดย Gennaro et al. ^{[ 4 ]}ทำงานดังนี้:

ฟังก์ชัน F ควรถูกแทนด้วยวงจรบูลีนซึ่ง จะนำอัลกอริธึม การสร้างคีย์มาใช้ อัลกอริธึมการสร้างคีย์จะใช้กระบวนการเข้ารหัสแบบ Yao กับวงจรบูลีนนี้เพื่อคำนวณคีย์สาธารณะและคีย์ลับ คีย์สาธารณะ (PK) ประกอบด้วยข้อความเข้ารหัส ทั้งหมด ที่แสดงถึงวงจรที่เข้ารหัสแล้ว และคีย์ลับ (SK) ประกอบด้วยป้ายกำกับสายไฟแบบสุ่มทั้งหมด จากนั้นคีย์ลับที่สร้างขึ้นจะถูกนำไปใช้ในอัลกอริธึมการสร้างปัญหา อัลกอริธึมนี้จะสร้างคู่คีย์สาธารณะและคีย์ลับใหม่สำหรับรูปแบบการเข้ารหัสแบบโฮโมมอร์ฟิก ก่อน จากนั้นใช้คีย์เหล่านี้กับรูปแบบโฮโมมอร์ฟิกเพื่อเข้ารหัสสายไฟขาเข้าที่ถูกต้อง ซึ่งแสดงเป็นคีย์ลับของวงจรที่เข้ารหัสแล้ว ข้อความเข้ารหัสที่สร้างขึ้นแสดงถึงการเข้ารหัสสาธารณะของอินพุต (σx) ที่ส่งไปยังตัวทำงาน ในขณะที่คีย์ลับ (τx) จะถูกเก็บไว้เป็นส่วนตัวโดยลูกค้า หลังจากนั้น ตัวทำงานจะใช้ขั้นตอนการคำนวณของโปรโตคอล Yao กับข้อความเข้ารหัสที่สร้างขึ้นโดยอัลกอริธึมการสร้างปัญหา กระบวนการนี้ทำได้โดย การถอดรหัสข้อความเข้ารหัสของเกตแบบเรียก ซ้ำไปเรื่อยๆจนกว่าจะได้ค่าสายสัญญาณเอาต์พุตสุดท้าย (σy) คุณสมบัติโฮโมมอร์ฟิกของแผนการเข้ารหัสช่วยให้ตัวประมวลผลสามารถเข้ารหัสสายสัญญาณเอาต์พุตที่ถูกต้องได้ ในที่สุด ตัวประมวลผลจะส่งข้อความเข้ารหัสของเอาต์พุตกลับไปยังไคลเอนต์ ซึ่งจะถอดรหัสเพื่อคำนวณค่าเอาต์พุตจริง y = F(x) หรือ ⊥

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

แม้ว่าจะมีการแสดงให้เห็นแล้วว่าการคำนวณที่ตรวจสอบได้นั้นเป็นไปได้ในทางทฤษฎี (โดยใช้การเข้ารหัสแบบโฮโมมอร์ฟิก อย่างสมบูรณ์ หรือผ่านการพิสูจน์ที่ตรวจสอบได้เชิงความน่าจะเป็น ) แต่โครงสร้างที่รู้จักส่วนใหญ่มีค่าใช้จ่ายสูงมากในทางปฏิบัติ เมื่อไม่นานมานี้ นักวิจัยบางคนได้พิจารณาถึงการทำให้การคำนวณที่ตรวจสอบได้นั้นใช้งานได้จริง ความพยายามอย่างหนึ่งคืองานของนักวิจัยจาก UT Austin ^{[ 18 ]}ผู้เขียนเริ่มต้นด้วยระบบการโต้แย้งที่อิงตามการพิสูจน์ที่ตรวจสอบได้เชิงความน่าจะเป็นและลดต้นทุนลงได้ถึง 10 เท่า^{20 เท่า}พวกเขายังได้นำเทคนิคของพวกเขาไปใช้ใน ระบบ Pepperด้วย ผู้เขียนตั้งข้อสังเกตว่า "ข้อสรุปของเราจนถึงตอนนี้คือ ในฐานะเครื่องมือสำหรับการสร้างระบบที่ปลอดภัย PCP และระบบการโต้แย้งนั้นไม่ใช่สิ่งที่สูญเปล่า"

พื้นที่โดยรวมซึ่งปัจจุบันรวมถึงการดำเนินการต่างๆ ของกลุ่มต่างๆ ได้รับการสำรวจแล้ว^{[ 19 ]}

ในช่วงทศวรรษ 2010 เทคนิคการคำนวณที่ตรวจสอบได้มีการใช้งานจริงเพิ่มมากขึ้นในเทคโนโลยีบล็อกเชน^{[ 20 ]}