Implementation of Our Bitcoin Sanitizer

[xuxi]

Here, we demonstrate the feasibility and practicality of our approach by providing a sanitizer tool that can be integrated in Bitcoin (or even other blockchains). Our implementation shows another application of ZK proofs that can be efficient enough to be used in practice.

The goal of our tool is to show that our solution allows to perform redactions in minutes rather than days as in previous solutions. We use STARKs combined with Isekai (see V-A) to convert C/C++ code into ZK proofs. Among the available options, we selected Aurora for the ZK proofs because Aurora provides: a) Post-quantum security: Aurora is plausibly post-quantum secure (there are no known efficient quantum attacks against this construction) guaranteeing security even against future advances in quantum technology. b) Fast verification: Aurora does not just provide short proofs but allows a verifier to run just in logarithmic time. c) Transparency: Aurora is transparent meaning that there is no trusted setup.8 d) General C/C++ code: a publicly available C/C++ library of Aurora that supports R1CS is available9 and this library is integrated into Isekai. Our implementation is deployed for the Linux OS.

We describe now the statement proved through a ZK proof by our implementation. Let X be the original transaction padded to a multiple of 64 bytes as described by SHA256 specifications [24]; let y1,…,ym be the bytes to delete in X ; let Y be the transaction obtained substituting y1,…,ym in X with bytes consisting of zeroes only, and padded as described by the SHA256 specifications [24]; let intervals be the set of intervals in which y1,…,ym are modified in X ; let SHARound be a circuit taking as input 1) a chunk of X, 2) the public values g0,…,g7 described by SHA256 specifications [24, Sec. 6],10 3) the output of the previous round. SHARound produces new values g′0,…,g′7 as described by the SHA256 specifications.

We assume that X=X1,…,Xn meaning that X is composed by n chunks of 64 bytes. The same holds for Y . Moreover, for simplicity, we define a function f that given Y , intervals , and y1,…,ym is able to reconstruct the original X . The statement ChunkPreImage that our implementation proves for each modified block is the following: ∃y1,…,ym s.t. SHARound(g0,…,g7,f(Yi,intervals,y1,…,ym))=g′0,…,g′7 , where Yi , for i∈{1,…,n} is the modified chunk, the elements y1,…,ym form the witness owned by the prover and g0,…,g7,Yi,intervals,g′0,…,g′7 are all public values. We remark that the verifier can compute the output of all SHA256 rounds on unmodified blocks and check that the final hash is equal to the value stored in the Merkle tree of the block of the Bitcoin blockchain.

We now explain the content of our implementation describing how it works for a modified chunk Xi of X . The main function is:

void outsource(struct Input *input, struct

NzikInput *nzik, struct Output

*output)

that specifies: the public input input of type struct Input *, corresponding to the variables Xi,g0,…,g7 ; the secret input nzik of type struct NzikInput *, corresponding to the variables y1,…,yn ; the output output of type struct Output *, corresponding to the variables g′0,…,g′7 . The routine outsource will use the public and private inputs to compute the intermediate hash of SHA256 on the current chunk and store it in output.11 The header file hash.h specifies the types of the structures struct Input, struct NzikInput and struct Output. The structure struct Input has the following format:

struct Input {

unsigned char trans [64];

unsigned int g0 [2];

unsigned int g1 [2];

unsigned int g2 [2];

unsigned int g3 [2];

unsigned int g4 [2];

unsigned int g5 [2];

unsigned int g6 [2];

unsigned int g7 [2];

unsigned int start [64];

unsigned int end [64]; };

while NzikInput has the following format:

struct NzikInput{

unsigned char

deleted_data[DEL_DATA_LENGTH]; }.

field trans contains the 64 bytes of Yi , deleted_data contains y1,…,ym , and g0,…, g7 contain the output of the previous round of SHA256.12 Isekai and Aurora work representing circuits so we have to fix an upper-bound to the maximum number of bytes that can be removed by a single 64 bytes chunk, that in our implementation is represented by the constant DEL_DATA_LENGTH in the file hash.h. The arrays start and end represent the starting points and the end points of each interval in which the data are removed.

From Yi , the routine outsource will first perform the string replacement using deleted_Data, start, and end obtaining back Xi . Xi together with g0,…, g7 will be passed to SHARound to obtain the new values g′0,…,g′7 that will be put in struct Output that is: