# An Image Authentication Scheme Using Merkle Tree Mechanisms
## 3 Proposed Method
### Image Verification  
To verify the integrity is an important function of our proposed method. The proposed image verification procedure can not only detect whether the image was tampered with or not, but can also point out the tampered area on the image. Let the test image be denoted as \(I_{unv}\) (the image that needs to be verified), and the test result is a set and denoted as \(R=\{r_{i}\mid i=1,2,3,...,n\}\), where \(r_{i}\) is the test result corresponding to block \(B_{i}\) and \(r_{i}=\{0,1\}\), and \(n\) is the number of total blocks of \(I_{unv}\). First, generate Merkle tree \(M_{unv}\) for \(I_{unv}\) by using the Merkle tree generation method (refer to Section 3.1). Then, get Merkle tree \(M_{org}\) corresponding to the original image from the block in the blockchain. Finally, generate comparing results \(r_{i}\) which use \(M_{org}\) to compare with \(M_{unv}\). In case a leaf node is different, then set the value of \(r_{i}\) to 1, otherwise set it to 0. The process is shown in Figure 9. The key steps of the proposed image verification method are summarized as Procedure 2. ```
0: Unverified Image \(I_{unv}\)
0: Set of the tampered result \(R_{i}=(r_{1},r_{2},...,r_{n})\), \(r_{i} \begin{cases}0,&\text{right block}\\ 1,&\text{tampered block}\end{cases} \). 1: Generate Merkle tree \(M_{unv}\) of \(I_{unv}\) by using the Merkle tree generation method (refer to Section 3.1). 2: Retrieve \(M_{org}\) corresponding to original image form the blockchain. 3: Check the size of \(M_{org}\) and \(M_{unv}\) Merkle trees, if both of them have the same size then go to Step 4, else, set each \(r_{i}\) to 1 then stop procedure. 4: Compare \(M_{org}\) and \(M_{unv}\) recursively from root to the tree left. Check left side child hashes followed by right side child hashes. If the node matches, then set the value of \(r_{i}\) to 0. If the node does not match, and it is the bottom node of the Merkle tree, then set the value of \(r_{i}\) corresponding to the node to 1, else, compare the child nodes. 5: Go to Step 4, until all nodes have been checked. ### Image Recovery

In the case where image has been tampered with, the tampered area can be pointed out by using the Image Verification method in Section 3.2 (see Figure 10). After the tampered area has been detected, the transactions data is retrieved from the blockchain (see Figure 11). Then, the cipher image blocks are retrieved from the IPFS and the file is decrypted to patch back to the tamped area on the image. After downloading the data from IPFS, decrypt it to image blocks (refer Section 3.1). Finally, the decrypted image block is used to restore the decrypted area on the tampered area (refer Figure 12). The key steps of the proposed image recovery method are summarized as Procedure 3. Figure 11: Process of getting the transactions record. Figure 9: Process of image verification. ## 4 Simulation Results

In order to evaluate the performance of the proposed method, we implemented it in Ubuntu 18.04.02 OS on a quad-core 3.4 GHz CPU with 4 GB RAM. Six commonly used images were used in our simulation, namely, Lena, Baboon, Jet, Boat, Pepper, and Sailboat. All of the images were 8-bit grayscale images, and the size of each image was 512 \(\times\) 512 pixels, as shown in Figure 13.

Figure 12: Process of image recovery. The blockchain was implemented using python 3.6.8, the program refers to the article on the blockchain structure [5; 7; 11; 12]. As shown in Figure 14, the genesis block (also called the first block) was generated in the blockchain. The value of the previous hash has sixty-four '0'. The image block size is \(N\times N\) (e.g., \(N=16\)) pixels in the Merkle tree generation method (Refer to Section 3.1), and RSA encryption is applied to play the encryption mechanism in our method. In our simulation, the image can be divided into 2048 block images. The RSA key pair was generated by applying python Cryptographic module pcrypto 2.6.1. After that, encrypted files were uploaded to IPFS.