com.sap.cloud.sdk.services.blockchainbusinessservices.blockchainvisibility

Class AbstractMerkleTree

java.lang.Object

com.sap.cloud.sdk.services.blockchainbusinessservices.blockchainvisibility.AbstractMerkleTree

All Implemented Interfaces:

MerkleTree

Direct Known Subclasses:

V100MerkleTree, V110MerkleTree

@Beta
public abstract class AbstractMerkleTree
extends Object
implements MerkleTree

The purpose of this class is to create Merkle Tree.
Each node has either two child nodes or one leaf. Digest of each node is hash digest of its leaf or concatenation of left and right child node
To prevent collision among inner nodes and leaves hashes, 0x00 byte is prepended to leaf and 0x01 is prepended to inner node byte arrays. To have a better performance and serialized object, the whole tree is implemented as a LinkedHashMap
The key is binary traverse of tree from root to leaves as below ---------------0--------------
------------/-----\-----------
-----------00------01---------
----------/--\----/--\--------
--------000--001-010--011-----
If the log(number_of_leaves,2) != Integer , (e.g. 5) then NO extra leaf is added to make it full binary tree. All the values in nodes (hashes) are represented as HexStrings.

Author:

mehran.shakeri@sap.com

Field Summary

Fields

Modifier and Type	Field and Description
protected int	depth number of levels in the tree and can be calculated as (int) Math.ceil((Math.log(numberOfLeaves) / Math.log(2))) + 1
protected Map<Integer,String>	leaves leaves encoded in a mapping of the index to the value
protected MessageDigest	messageDigest messageDigest to perform hashing function
protected Map<String,String>	nodes Tree nodes as a LinkedHashMap
protected int	numberOfLeaves number of leaves in the tree
protected Map<Integer,String>	salts salts encoded in a mapping of the index to the salts with index i corresponds the the leaf with the same index i in the leaves map

Fields inherited from interface com.sap.cloud.sdk.services.blockchainbusinessservices.blockchainvisibility.MerkleTree

ROOT_HASH_KEY

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	AbstractMerkleTree(MessageDigest messageDigest, int numberOfLeaves) Creates an abstract MerkleTree
protected	AbstractMerkleTree(MessageDigest messageDigest, Map<Integer,String> leaves, Map<Integer,String> salts) Creates an abstract MerkleTree

Method Summary

Modifier and Type	Method and Description
static String	bytesToHexString(byte[] byteArray)
protected static int	calculateDepth(int numberOfLeaves) Could be seen as the number of rows in a binary tree with given number of leaves
protected abstract void	calculateHash(String rootHashKey) calculates the hash of given rootHashKey
protected abstract String	calculatLeafHash(String string) calculates the hash of the leaf
protected void	createEmptyTree() Calculates keys in the tree and set their value as null It also ignores redundant nodes. e.g.
protected static String	formatKey(int depth, String binaryString) formats the key with leading zeros "0" to reach the correct length of a key in the given depth
protected String	generateLeftChildKey(String parentKey) Left child key is always equal to parentKey + "0"
protected String	generateRightChildKey(String parentKey) Right child key is always equal to parentKey + "1"
String	getHashAlgorithm()
Map<Integer,String>	getLeaves() leaves encoded in a mapping of the index to the value
static List<String>	getMissingHashIndexes(Set<Integer> knownLeavesIndexes, int numberOfLeaves) Finds missing hash indexes to be able to rebuild the Merkle tree with given number of leaves and known leaf values. One can rebuild a Merkle tree with only a subset of leaves, if s/he has enough extra information about the tree. These extra information include the total number of leaves and hashes of missing leaves along with indexes of those hashes. e.g.
Map<String,String>	getNodes() Tree nodes as a LinkedHashMap
int	getNumberOfLeaves() number of leaves in the tree
String	getRootHash()
Map<Integer,String>	getSalts() salts encoded in a mapping of the index to the salts with index i corresponds the the leaf with the same index i in the leaves map
protected String	getValueByKey(String key) returns the value of the leaf
protected boolean	isALeafKey(String key) checks if a key corresponds to a leaf.
protected void	removeRedundantNodes(String key) removes nodes, when they have no child and replaces them with child when they have only one child.
protected void	setLeavesHashes() calculates and sets the hashes of the leaves

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.sap.cloud.sdk.services.blockchainbusinessservices.blockchainvisibility.MerkleTree

getProtocolVersion

Field Detail

messageDigest

protected final MessageDigest messageDigest

messageDigest to perform hashing function

leaves

protected Map<Integer,String> leaves

leaves encoded in a mapping of the index to the value

salts

protected Map<Integer,String> salts

salts encoded in a mapping of the index to the salts with index i corresponds the the leaf with the same index i in the leaves map

nodes

protected Map<String,String> nodes

Tree nodes as a LinkedHashMap

numberOfLeaves

protected final int numberOfLeaves

number of leaves in the tree

depth

protected final int depth

number of levels in the tree and can be calculated as (int) Math.ceil((Math.log(numberOfLeaves) / Math.log(2))) + 1

Constructor Detail

AbstractMerkleTree

protected AbstractMerkleTree(MessageDigest messageDigest,
                             Map<Integer,String> leaves,
                             Map<Integer,String> salts)

Creates an abstract MerkleTree

Parameters:

messageDigest - messageDigest

leaves - Map<Integer, String> leaves encoded in a mapping of the index to the value

salts - Map<Integer, String> salts encoded in a mapping of the index to the salts with index i corresponds the the leaf with the same index i in the leaves map

AbstractMerkleTree

protected AbstractMerkleTree(MessageDigest messageDigest,
                             int numberOfLeaves)

Creates an abstract MerkleTree

Parameters:

messageDigest - messageDigest

numberOfLeaves - number of leaves

Method Detail

calculateHash

protected abstract void calculateHash(String rootHashKey)

calculates the hash of given rootHashKey

Parameters:

rootHashKey - rootHashKey

calculatLeafHash

protected abstract String calculatLeafHash(String string)

calculates the hash of the leaf

Parameters:

string - key of the leaf

Returns:

hash

getValueByKey

protected String getValueByKey(String key)

returns the value of the leaf

Parameters:

key - key of the leaf

Returns:

value

setLeavesHashes

protected void setLeavesHashes()

calculates and sets the hashes of the leaves

createEmptyTree

protected void createEmptyTree()

Calculates keys in the tree and set their value as null
It also ignores redundant nodes.
e.g. a tree with three leaves before removing redundant nodes will look like this: ---------------0--------------
------------/-----\-----------
-----------00------01---------
----------/--\-----/----------
--------000--001--010---------
However we can remove the node with key '01' and use the 010 directly: ---------------0--------------
------------/---\-------------
-----------00----\------------
----------/--\----\-----------
--------000--001--010---------

removeRedundantNodes

protected void removeRedundantNodes(String key)

removes nodes, when they have no child and replaces them with child when they have only one child. It starts the reduction from the given key which is usually the root node.

Parameters:

key - key

isALeafKey

protected boolean isALeafKey(String key)

checks if a key corresponds to a leaf. Keys to the leaf are the longest and their length is equal to the depth.

Parameters:

key - key to check

Returns:

true if key is a leaf key

calculateDepth

protected static int calculateDepth(int numberOfLeaves)

Could be seen as the number of rows in a binary tree with given number of leaves

Parameters:

numberOfLeaves - total number of leaves in the tree

Returns:

int number of rows in the tree called as depth

generateLeftChildKey

protected String generateLeftChildKey(String parentKey)

Left child key is always equal to parentKey + "0"

Parameters:

parentKey - the key of the parent node

Returns:

key of the left child node

generateRightChildKey

protected String generateRightChildKey(String parentKey)

Right child key is always equal to parentKey + "1"

Parameters:

parentKey - key of the parent

Returns:

key of the right child node

getRootHash

@Nonnull
public String getRootHash()

Specified by:

getRootHash in interface MerkleTree

Returns:

the hash saved in the root of the tree

bytesToHexString

@Nonnull
public static String bytesToHexString(@Nonnull
                                               byte[] byteArray)

Parameters:

byteArray - arbitrary byteArray

Returns:

Hex string

getMissingHashIndexes

@Nonnull
public static List<String> getMissingHashIndexes(@Nonnull
                                                          Set<Integer> knownLeavesIndexes,
                                                          int numberOfLeaves)

Finds missing hash indexes to be able to rebuild the Merkle tree with given number of leaves and known leaf values.
One can rebuild a Merkle tree with only a subset of leaves, if s/he has enough extra information about the tree.
These extra information include the total number of leaves and hashes of missing leaves along with indexes of those hashes.
e.g. in the below Merkle tree
---------------0--------------
------------/-----\-----------
-----------00------01---------
----------/--\----/--\--------
--------000--001-010--011-----
having value of second leaf (indexed by 001), hash of leaf indexed by (000) and inner node (01),
also knowing there are 4 leaves in total, anyone can create the same unique Merkle tree.

Parameters:

knownLeavesIndexes - List<Integer> index of known leaves starting from zero (0)

numberOfLeaves - int total number of leaves

Returns:

List<String> minimum set of hash indexes to have a unique Merkle tree for given arguments.

formatKey

protected static String formatKey(int depth,
                                  String binaryString)

formats the key with leading zeros "0" to reach the correct length of a key in the given depth

Parameters:

depth - depth in the tree where the key belongs to

binaryString - position in the tree

Returns:

value

getHashAlgorithm

@Nonnull
public String getHashAlgorithm()

Specified by:

getHashAlgorithm in interface MerkleTree

Returns:

the hash algorithm used to build the hashes

getLeaves

public Map<Integer,String> getLeaves()

leaves encoded in a mapping of the index to the value

Specified by:

getLeaves in interface MerkleTree

Returns:

Map<Integer, String> the leaves mapping position to value

getSalts

public Map<Integer,String> getSalts()

salts encoded in a mapping of the index to the salts with index i corresponds the the leaf with the same index i in the leaves map

Specified by:

getSalts in interface MerkleTree

Returns:

the salts, which are used to build the hashes for the different leaves

getNodes

public Map<String,String> getNodes()

Tree nodes as a LinkedHashMap

Specified by:

getNodes in interface MerkleTree

Returns:

Map<Integer, String> the nodes of the tree

getNumberOfLeaves

public int getNumberOfLeaves()

number of leaves in the tree

Specified by:

getNumberOfLeaves in interface MerkleTree

Returns:

the number of leaves