Mohammad Reza Hooshmandasl

In this work, we consider a combinatorial optimization problem with direct applications in blockchain mining, namely finding the most lucrative blocks for Bitcoin miners, and propose optimal algorithmic solutions. Our experiments show that our algorithms increase the miners’ revenues by more than a million dollars per month. Modern blockchains reward their miners in two ways: (i) a base reward for each block that is mined, and (ii) the transaction fees of those transactions that are included in the mined block. The base reward is fixed by the respective blockchain’s protocol and is not under the miner’s control. Hence, for a miner who wishes to maximize earnings, the fundamental problem is to form a valid block with maximal total transaction fees and then try to mine it. Moreover, in many protocols, including Bitcoin itself, the base reward halves at predetermined intervals, hence increasing the importance of maximizing transaction fees and mining an optimal block. This problem is further complicated by the fact that transactions can be prerequisites of each other or have conflicts (in case of double-spending). In this work, we consider the problem of forming an optimal block, i.e. a valid block with maximal total transaction fees, given a set of unmined transactions. On the theoretical side, we first formally model our problem as an extension of Knapsack and then show that, unlike classical Knapsack, our problem is strongly NP-hard. We also show a hardness-of-approximation result. As such, there is no hope in solving it efficiently for general instances. However, we observe that its real-world instances are quite sparse, i.e. the transactions have very few dependencies and conflicts. Using this fact, and exploiting three well-known graph sparsity parameters, namely treedepth, treewidth and pathwidth, we present exact linear-time parameterized algorithms that are applicable to the real-world instances and obtain optimal results. On the practical side, we provide an extensive experimental evaluation demonstrating that our approach vastly outperforms the current Bitcoin miners in practice, obtaining a significant per-block average increase of 11.34 percent in transaction fee revenues which amounts to almost one million dollars per month.

In this work, two-dimensional time-dependent quantum equation problems are studied. We introduce a numerical algorithm for solving the two-dimensional nonlinear complex quantum system with MLS and FDM methods. An efficient and accurate computational algorithm based on both, the moving least squares (MLS) and the finite difference (FDM) methods is proposed for solving it. The results demonstrate that the proposed algorithm is a robust algorithm with good accuracy. This is developed on MLS and FDM methods using numerical simulation for solving these kind of problems.

Given a positive integer k and a graph G = (V, E), a function f from V to the power set of I_k is called a k-rainbow function if for each vertex v ∈ V, f(v)=∅ implies ∪_{u ∈ N(v)}f(u)=I_k where N(v) is the set of all neighbors of vertex v and I_k = {1, …, k}. Finding a k-rainbow function of minimum weight of ∑_v ∈ V|f(v)|, which is called the k-rainbow domination problem, is known to be NP-complete for arbitrary graphs and values of k. In this paper, we propose a dynamic programming algorithm to solve the k-rainbow domination problem for graphs with bounded tree-width tw in 𝒪((2^k + 1+1)^twn) time, where G has n vertices. Moreover, we also show that the same approach is applicable to solve the weighted k-rainbow domination problem with the same complexity. Therefore, both problems of k-rainbow and weighted k-rainbow domination belong to the class FPT, or fixed parameter tractable, with respect to tree-width. In addition to formally showing the correctness of our algorithms, we also implemented these algorithms to illustrate some examples.

Following the Bitcoin model, many modern blockchains reward their miners in two ways: (i) a base reward for each block that is mined, and (ii) the transaction fees of those transactions that are included in the mined block. The base reward is fixed by the respective blockchain's protocol and is not under the miner's control. Hence, for a miner who wishes to maximize earnings, the fundamental problem is to form a valid block with maximal total transaction fees and then try to mine it. Moreover, in many protocols, including Bitcoin itself, the base reward halves at predetermined intervals, hence increasing the importance of maximizing transaction fees and mining an optimal block. This problem is further complicated by the fact that transactions can be prerequisites of each other or have conflicts (in case of double-spending). In this work, we consider the problem of forming an optimal block, i.e. a valid block with maximal total transaction fees, given a set of unmined transactions. On the theoretical side, we first formally model our problem as an extension of Knapsack and then show that, unlike classical Knapsack, our problem is strongly NP-hard. We also show a hardness-of-approximation result. As such, there is no hope in solving it efficiently for general instances. However, we observe that its real-world instances are quite sparse, i.e. the transactions have very few dependencies and conflicts. Using this fact, and exploiting two well-known graph sparsity parameters, namely treewidth and pathwidth, we present exact linear-time parameterized algorithms that are applicable to the real-world instances and obtain optimal results. We also provide an experimental evaluation demonstrating that our approach vastly outperforms the current Bitcoin miners in practice, obtaining a significant per-block average increase of 13.4% in transaction fee revenues.

Due to the availability of powerful image-editing software and the growing amount of multimedia data that is transmitted via the Internet, integrity verifications and confidentiality of the data are becoming critical issues. However, currently, the accuracy of detecting and the recovery capability of the tampered images by the existing methods through watermarking strategy is still not at the required level, especially at a higher tampered rate. This paper proposes a new blind and fragile watermarking method to detect tampering and better recovery of tampered images. To improve the quality of both the watermarked and the recovered images, a new feature extraction scheme is introduced which will produce a short but comprehensive recovery code using a new compression strategy. If a block in the image tampers, the proposed embedded feature allows the original data to be extracted for recovery. To overcome tamper coincidence, every block’s watermarked data contains not only the recovery code belonging to the block itself but also its neighbor’s data as a second layer of recovery. Various size blocks were investigated to see the performance and compare their efficiency for recovering an image after different tampering rates. The test showed the smaller block sizes may be more suitable for locating tampering, where the bigger ones are more suitable when the tampering rate is higher. The bigger block sizes in the proposed method can recover an image even after a 60% tampering rate with high quality (more than 31 dB). The experimental results prove that the proposed method can have better efficiency for detecting tampering, and recovery of the original image, compared to the relevant existing methods.

We study relations between evidence theory and S-approximation spaces. Both theories have their roots in the analysis of Dempster's multivalued mappings and lower and upper probabilities and have close relations to rough sets. We show that an S-approximation space, satisfying a monotonicity condition, can induce a natural belief structure which is a fundamental block in evidence theory. We also demonstrate that one can induce a natural belief structure on one set, given a belief structure on another set if those sets are related by a partial monotone S-approximation space.