Dr Gennaro Avitabile

Balancing immutability and compliance with regulations stands as a significant challenge in the realm of blockchain technology applications. Due to the increase of data-protection requirements (e.g., the GDPR in the EU), it is essential to address the problem of deleting data from a blockchain without compromising the security and transparency of the blockchain itself. Several works proposed techniques to address the data redaction problem. In their seminal work, Ateniese et al. [EuroS&P 2017] were the first to propose a redactable blockchain. Their approach focuses on permissioned blockchains and they showed how to change the content of a transaction without breaking the chaining among blocks by using special cryptographic hash functions (i.e., chameleon hash functions) and secure multi-party computation. We observe that the redaction technique of Ateniese et al. does not take into account the possibility that the blockchain supports smart contracts and that a redaction of a transaction might leave inconsistencies in the logic of the contracts, making some remaining non-redacted transactions invalid, and, more in general, the state of a smart contract inconsistent with the content of transactions. We find this choice rather limiting since decentralized and publicly verifiable computation guaranteed by smart-contract-enabled blockchains is necessary for modern (i.e., Web3) applications. To overcome the above limitations of the applicability of the redaction techniques of Ateniese et al., we propose a redaction technique with wider applicability that leverages succinct non-interactive arguments of knowledge (SNARKs) to realize what we call a proof-of-consistency.

At CRYPTO '94, Cramer, Damgard, and Schoenmakers introduced a general technique for constructing honest-verifier zero-knowledge proofs of partial knowledge (PPK), where a prover Alice wants to prove to a verifier Bob she knows tau witnesses for tau claims out of k claims without revealing the indices of those tau claims. Their solution starts from a base honest-verifier zero-knowledge proof of knowledge Sigma and requires to run in parallel k execution of the base protocol, giving a complexity of O(k gamma(Sigma)), where gamma(Sigma) is the communication complexity of the base protocol. However, modern practical scenarios require communication-efficient zero-knowledge proofs tailored to handle partial knowledge in specific application-dependent formats. In this paper, we propose a technique to compose a large class of Sigma-protocols for atomic statements into Sigma-protocols for PPK over formulae in conjunctive normal form (CNF) that overlap, in the sense that there is a common subset of literals among all clauses of the formula. In such formulae, the statement is expressed as a conjunction of m clauses, each of which consists of a disjunction of k literals (i.e., each literal is an atomic statement) and & ell; literals are shared among clauses. The prover, for a threshold parameter tau 1 providing improvements over state-of-the-art constructions.