Nói cách khác, xác suất mà Bob đã nói dối về gốc Merkle sau N truy vấn là bao nhiêu?
Chà, đây là một cách mà Bob có thể gian lận; anh ấy có thể lấy danh sách $M$ giá trị $$V_1, V_2, ..., V_M$$ và thay vì tạo cây Merkle dựa trên đó, hãy chọn một giá trị $c$ chỉ số và một giá trị $V'_c \ne V_c$, và thay vào đó tạo thành danh sách $$V_1, V_2, ..., V_{c-1}, V'_c, V_{c+1}, ..., V_M$$ và hình thành cây Merkle dựa trên danh sách đó (và cung cấp cho Alice gốc được tính toán, có xác suất khá cao khác với gốc trong danh sách ban đầu).
Sau đó, khi Alice đưa cho anh ta $K$ chỉ số làm cơ sở $K$ bằng chứng trên, anh ấy tạo chúng dựa trên danh sách đã sửa đổi và cây mà anh ấy đã tính toán. Anh ta sẽ bị phát hiện là gian lận chỉ khi một trong những chỉ số mà cô ấy yêu cầu lại là chỉ số $c$; nếu không có chỉ số nào cô ấy yêu cầu tình cờ là chỉ số $c$, thì các bằng chứng mà cô ấy sẽ nhận được đều hợp lệ và nhất quán với nhau (vì chúng tương ứng với cây Merkle tự nhất quán, với các lá được tiết lộ là giá trị mà cô ấy mong đợi)
Xác suất Bob bị bắt gian lận, nghĩa là xác suất mà một trong các chỉ số mà Alice chọn là $c$, Là $K/M$. Do đó, xác suất phát hiện đối với bất kỳ chiến lược nào cũng không nhiều hơn thế (có thể ít hơn nếu có một chiến lược thậm chí còn tốt hơn mà Bob có thể sử dụng).
Vì vậy, để phát hiện Bob gian lận với xác suất 0,99, chúng ta có $K > 0,99 triệu$; tại thời điểm đó, Alice sẽ thực sự ít tính toán hơn nếu cô ấy chỉ tự mình tính toán lại cái cây.
Có vẻ thú vị đối với chúng tôi vì nó có thể là một dạng bằng chứng về không-thời gian nếu danh sách này tốn kém để xây dựng
Bây giờ, xem xét vấn đề dưới dạng bằng chứng công việc thú vị hơn một chút (bằng chứng không gian không hoạt động, vì cây và đường dẫn xác thực có thể được tính toán mà không làm tăng đáng kể số lượng tính toán cần thiết); rõ ràng, chiến lược gian lận mà tôi đưa ra ở trên không giải quyết được vấn đề đó, vì Bob đang làm hết công việc. Nếu tôi có nhiều thời gian hơn, tôi sẽ cố gắng điều tra thêm ...
