Đối số giới hạn dưới gần đúng
Approximate Lower Bound Arguments.
Giả sử một trình chứng minh sở hữu một khối lượng lớn bằng chứng có giá trị, muốn nhanh chóng thuyết phục trình xác minh bằng cách chỉ đưa ra một phần nhỏ bằng chứng. Các tác giả xác định Đối số giới hạn dưới gần đúng, hay ALBA, cho phép trình chứng minh thực hiện chính xác điều đó: chứng minh một cách ngắn gọn kiến thức về một số lượng lớn các phần tử thỏa mãn một vị từ (hoặc, nói chung hơn, các phần tử có tổng trọng số đủ khi một vị từ được khái quát hóa thành một hàm trọng số). Đối số này là gần đúng vì có một khoảng cách nhỏ giữa những gì trình chứng minh thực sự biết và những gì trình xác minh tin rằng trình chứng minh biết. Khoảng cách này cho phép các cơ chế rất hiệu quả. Các tác giả trình bày các cấu trúc không tương tác của ALBA trong các mô hình Oracle ngẫu nhiên và Chuỗi ngẫu nhiên thống nhất và cho thấy kích thước bằng chứng của họ gần như tối ưu. Các tác giả cũng cho thấy cách các cấu trúc của họ có thể được thực hiện đặc biệt hiệu quả về mặt giao tiếp khi bằng chứng được phân phối giữa nhiều trình chứng minh làm việc cùng nhau, điều này có tầm quan trọng thực tế khi ALBA được áp dụng cho một thiết lập phi tập trung. Các tác giả trình bày hai ứng dụng rất khác nhau của ALBA: cho chữ ký phi tập trung quy mô lớn và để đạt được khả năng kết hợp tổng quát trong các hệ thống bằng chứng ngắn gọn mục đích tổng quát (SNARK).