Post by cadu28 on Mar 3, 2023 8:52:35 GMT
If the number of deletion intervals is less than DEL_DATA_LENGTH, the remaining elements of the arrays start and end can be set to 0. The program proofdel contains all the routines used to prepare the data for Isekai. The needed inputs for the prover are file original_tx, file transaction, and the intervals in which the user deleted the data. File original_tx is the file that contains the original transaction T before the deletion. File transaction contains the transaction T in which the bytes corresponding to the intervals taken in input by proofdel are set to the byte 0X00 . On the other side, the needed inputs to verify the proofs, are the file transaction, and the intervals in which the user deleted the data. proofdel will use these inputs to interact with Isekai to generate the circuit for the proofs, the proofs and to launch the verifier on each proof. proofdel interacts with Isekai to generate the proofs computing the following steps:
perform the padding of the binary string contained in transaction as prescribed by the SHA256 specifications [24] and divide the padded transaction in chunks C0,…,Cn of 64 bytes;
take the original values of the data to delete from original_tx and the hash of the transaction (before deletion);
infer the chunks {Cj}j∈{n} of the transaction T that contain modified data, using the intervals, and then for each of these Cj prepare the public input and the witness to send to Isekai;
receive back from Isekai a proof πj for each modified chunk Cj .
proofdel will prepare the data to send to Isekai to verify the proofs through the following steps:
take in input the modified transaction for Bitcoin blockchain;
recover the public inputs {ij}j∈{n} and the proofs {πj}j∈{n} , where values ij is the index to the j -th deleted chunk and πj is the proof for the j -th chunk;
send to Isekai the pairs (ij,πj) for each modified chunk (after collecting all inputs and proofs), to start the verification procedure;
end with success only if the verifier called by Isekai13 accepts all the proofs.
For simplicity, we are omitting the further step in the verification procedure. Indeed, proofdel will extract the intermediate output of SHA256 for each modified chunk from the public inputs and will use these intermediate outputs to compute the hash h of T . If h is equal to the value stored on the blockchain14 the verification procedure proofdel succeeds. Moreover, proofdel will also check that deleted data are not contained in harmful positions. Indeed, in Bitcoin it is possible to check if a transaction is a coinbase transaction. In the affirmative case, one can check if deletion occurs only in a scriptSig. If a deletion occurs after an OP_RETURN opcode, proofdel can check that the number of deleted bytes corresponds to the number of bytes contained in the OP_RETURN parameter. To check that redactions do not happen in harmful positions proofdel does not need to interact with Isekai.
SECTION VI.
Performance
The system used to test our implementation consists of a desktop computer running Ubuntu as operating system with an architecture ×86_64 , 32 GB of RAM and an Intel(R) Core i7−7820X CPU with clockspeed 3.60GHz. To execute our tests, we instantiate Isekai with Aurora. We remark that our experiments only focused on evaluating the practical feasibility of our implementation, and our goal is not to test the performance of Isekai/Aurora.
First, we analyzed the performance of our prover and verifier considering the number of modified chunks in a transaction. Our tests show that the computations of prover and verifier are nearly linear as expected. The verifier runs in about 3 seconds to verify the proof of a single chunk of SHA256 and for each additional chunk to verify the same amount of time is required. Notice that a node must run the verifier only at bootstrap time.
We remark that our tests have not been optimized and the code would be highly parallelizable. In particular, in a cluster with m > 1 processors the time of the prover and verifier could be reduced approximately by a factor m since the most expensive computation consists of running the prover and verifier on independent statements.
We tested our code on both real transactions taken from Bitcoin blockchain and on our own standard ad-hoc transactions.
Our own transactions have the purpose of evaluating our tool on different numbers of redacted chunks. Indeed for our tests we needed data to delete in many consecutive and non-consecutive chunks, instead of restricting ourselves to what is available on the Bitcoin blockchain.
We now describe the transactions that we have considered in the performance evaluation. The 1st transaction is a 64 bytes transaction that we call “Simple”. In Simple only 4 bytes contained in the first chunk were deleted. The 2nd transaction is the coinbase transaction of the genesis block. On this transaction we deleted the 69 bytes of the Chancellor sentence. We call this transaction “Chanc”. The 3rd transaction taken into account is Bitcoin transaction indexed “db27236623f19ceaf8535407e74b5dfad613aef7d5558631f4837fd0f6d83c83 ” in which we deleted 76 bytes distributed in 3 chunks. We call this transaction “db2723”. We define 4 ad-hoc OP_RETURN transactions. We call them “Ex1”, “Ex2”, “Ex3” and “Ex4” respectively. The sizes of these transactions are respectively 1280, 1280, 2560 and 3888 bytes. We deleted 640 bytes from Ex1 that were distributed in 10 SHA256 chunks, 920 bytes from Ex2 that were distributed in 15 SHA256 chunks, 1231 bytes from Ex3 that were distributed in 20 SHA256 chunks and 576 bytes Ex4, where bytes to delete were distributed in 16 different OP_RETURN output scripts contained in 23 SHA256 chunks.
The performance analysis reports the transaction length in bytes, the number of modified chunks, the number of bytes deleted by the entire transaction and the execution time in seconds of prover and verifier. Results are shown in Table III.
perform the padding of the binary string contained in transaction as prescribed by the SHA256 specifications [24] and divide the padded transaction in chunks C0,…,Cn of 64 bytes;
take the original values of the data to delete from original_tx and the hash of the transaction (before deletion);
infer the chunks {Cj}j∈{n} of the transaction T that contain modified data, using the intervals, and then for each of these Cj prepare the public input and the witness to send to Isekai;
receive back from Isekai a proof πj for each modified chunk Cj .
proofdel will prepare the data to send to Isekai to verify the proofs through the following steps:
take in input the modified transaction for Bitcoin blockchain;
recover the public inputs {ij}j∈{n} and the proofs {πj}j∈{n} , where values ij is the index to the j -th deleted chunk and πj is the proof for the j -th chunk;
send to Isekai the pairs (ij,πj) for each modified chunk (after collecting all inputs and proofs), to start the verification procedure;
end with success only if the verifier called by Isekai13 accepts all the proofs.
For simplicity, we are omitting the further step in the verification procedure. Indeed, proofdel will extract the intermediate output of SHA256 for each modified chunk from the public inputs and will use these intermediate outputs to compute the hash h of T . If h is equal to the value stored on the blockchain14 the verification procedure proofdel succeeds. Moreover, proofdel will also check that deleted data are not contained in harmful positions. Indeed, in Bitcoin it is possible to check if a transaction is a coinbase transaction. In the affirmative case, one can check if deletion occurs only in a scriptSig. If a deletion occurs after an OP_RETURN opcode, proofdel can check that the number of deleted bytes corresponds to the number of bytes contained in the OP_RETURN parameter. To check that redactions do not happen in harmful positions proofdel does not need to interact with Isekai.
SECTION VI.
Performance
The system used to test our implementation consists of a desktop computer running Ubuntu as operating system with an architecture ×86_64 , 32 GB of RAM and an Intel(R) Core i7−7820X CPU with clockspeed 3.60GHz. To execute our tests, we instantiate Isekai with Aurora. We remark that our experiments only focused on evaluating the practical feasibility of our implementation, and our goal is not to test the performance of Isekai/Aurora.
First, we analyzed the performance of our prover and verifier considering the number of modified chunks in a transaction. Our tests show that the computations of prover and verifier are nearly linear as expected. The verifier runs in about 3 seconds to verify the proof of a single chunk of SHA256 and for each additional chunk to verify the same amount of time is required. Notice that a node must run the verifier only at bootstrap time.
We remark that our tests have not been optimized and the code would be highly parallelizable. In particular, in a cluster with m > 1 processors the time of the prover and verifier could be reduced approximately by a factor m since the most expensive computation consists of running the prover and verifier on independent statements.
We tested our code on both real transactions taken from Bitcoin blockchain and on our own standard ad-hoc transactions.
Our own transactions have the purpose of evaluating our tool on different numbers of redacted chunks. Indeed for our tests we needed data to delete in many consecutive and non-consecutive chunks, instead of restricting ourselves to what is available on the Bitcoin blockchain.
We now describe the transactions that we have considered in the performance evaluation. The 1st transaction is a 64 bytes transaction that we call “Simple”. In Simple only 4 bytes contained in the first chunk were deleted. The 2nd transaction is the coinbase transaction of the genesis block. On this transaction we deleted the 69 bytes of the Chancellor sentence. We call this transaction “Chanc”. The 3rd transaction taken into account is Bitcoin transaction indexed “db27236623f19ceaf8535407e74b5dfad613aef7d5558631f4837fd0f6d83c83 ” in which we deleted 76 bytes distributed in 3 chunks. We call this transaction “db2723”. We define 4 ad-hoc OP_RETURN transactions. We call them “Ex1”, “Ex2”, “Ex3” and “Ex4” respectively. The sizes of these transactions are respectively 1280, 1280, 2560 and 3888 bytes. We deleted 640 bytes from Ex1 that were distributed in 10 SHA256 chunks, 920 bytes from Ex2 that were distributed in 15 SHA256 chunks, 1231 bytes from Ex3 that were distributed in 20 SHA256 chunks and 576 bytes Ex4, where bytes to delete were distributed in 16 different OP_RETURN output scripts contained in 23 SHA256 chunks.
The performance analysis reports the transaction length in bytes, the number of modified chunks, the number of bytes deleted by the entire transaction and the execution time in seconds of prover and verifier. Results are shown in Table III.