Prova de intervalo (range proof)

Uma prova de intervalo (range proof) demonstra que um valor comprometido v está dentro de um intervalo, tipicamente [0, 2^n), sem revelá-lo. É um caso particular de prova de conhecimento zero que costuma ser aplicada sobre um compromisso (por exemplo, de Pedersen) do valor. O provador atesta que a representação binária do valor tem exatamente n bits, cada um zero ou um, o que limita v abaixo de 2^n, sem mostrar nenhum desses bits.

A construção de referência é Bulletproofs (Bünz, Bootle, Boneh, Poelstra, Wuille e Maxwell, IEEE Symposium on Security and Privacy 2018), que reformula o problema como um argumento de produto interno e comprime a prova a tamanho logarítmico em n. Não precisa de trusted setup, apoia-se apenas na hipótese do logaritmo discreto, é não interativa via Fiat-Shamir e permite agregar várias provas com custo adicional reduzido. Bulletproofs+ (Chung, Han, Ju, Kim e Seo) é uma melhoria posterior com provas ainda mais curtas.

Importa por dois motivos. Privacidade: em transações confidenciais é preciso provar que cada valor oculto é não negativo, evitando que se crie valor com quantias negativas por overflow modular. E solvência: um prestador de serviços pode provar que suas contas e reservas estão dentro de intervalos válidos sem publicar saldos individuais. Monero adotou Bulletproofs em outubro de 2018 para suas provas de intervalo, reduzindo de forma significativa o tamanho das transações, e a Liquid Network as emprega em suas Confidential Transactions.