Merkle Signature Performance, Multisignature Transactions

Merkle Signatures, an alternative to the popular ECDSA- and RSA-based signature schemes, are quantum-computer-resistant, as they rely only on the existence of a one-way hashing function (such as SHA256, SHA3/Keccak, Whirlpool, etc.). Both the cryptographic integrity and efficiency of hashing functions has been well-researched, which intrinsically makes Merkle Signatures a secure means of proving ownership and preventing forgeries of transaction information.

In the coming week, I will be publishing a much more fleshed-out graphical guide to Merkle Signatures and how addresses are derived from a tree, however as it stands the current code I have been developing for generating Curecoin addresses has proven sufficiently efficient for use in a cryptocurrency network. Addresses capable of signing 4k+ distinct transactions take a few seconds for a modern computer to generate (using only one core), and addresses capable of signing up to 2^16 transactions are available. For those familiar with the concept of a Merkle Tree, each bottom ‘leaf’ of the tree is one individual signature (a Lamport Signature). As such, proving a signature for a transaction involves publishing the hashes of the private keys of a Lamport Signature interlaced with half the private keys to represent the binary of the hash of the transaction message, as well as the authentication path up the tree to prove the top node–which is the main component of the Curecoin address.

The Curecoin address (example: C1NYDLCX7O2V5U3H566DPJVSR7MNGBKLZOXGG2MVVCC3UNPMQTO52FWBVQ) can be split into four distinct parts:
The starting ‘C’ denotes Curecoin
The ’1′ denotes the address ‘type’ (the number of signatures the address is capable of signing). 1=4096, 2=8192, 3=16384, etc.
The next four digits are a partial checksum. For example, if we changed the address to C1NYDLCX7O2V5U3H566DPJVSS7MNGBKLZOXGG2MVVCC3UNPMQTO52FWBVQ (where we changed an R to an S) Curecoin would be able to determine that this address is not valid, as the hash of the remaining address would not, when formatted and substringed, equal “NYDL.” Curecoin addresses will likely be shorter in the official release, I am using the full length 256-bit output of SHA256 for the addresses. It would be trivial to only use the first x number of bits determined to be secure (current estimates are pointing to 160 being far beyond secure).
The last (and by far the largest) portion of the address is the hash sitting at the top of the Merkle Signature Tree.

A visual example will make this a lot simpler to digest (haaa…).

Curecoin will also have a versatile Multisignature system. At will, people will be able to generate addresses which have multiple sets of private keys. Additionally, the network will support assigning rules to a multisignature address, such as how many private keys exist for the address, how many are required to spend money, and which ones have override capabilities. The rules for each multisignature address will be stored in the blockchain, and the creation of a multisignature address will cost a small amount of Curecoin to offset the data it adds to the blockchain. A few use case examples:

1.) A business holding a large number of Curecoin wants to protect their holdings. They transfer their Curecoin to a multisignature address which has 11 private keys, 7 of which are required to send funds. Each of the 11 private keys is generated at a geographically-diverse, secure location, and only the top hash (normally the address) of the private key Merkle Tree is sent to a central authority, who combines all these addresses to produce the multisignature address. They then create a special transaction which creates the multisignature address on the network, while defining the rules of behavior. In this case, they set 11 total private keys, and a minimum of 7 required to spend funds. Finally, the allow three of the addresses (those kept in the most secure places) to have ‘override’ capabilities–these three addresses, when all used together, can override the 7 requirement. As thus, a hacker would have to obtain the private keys for either three of these override addresses, or 7 distinct addresses (two of which could be the override addresses) to steal the coins. However, say the company were to experience a massive data loss. As long as either they still have 7 of their 11 original private keys, they can spend the Curecoins, and send them to other addresses. Additionally, if they lose more than 4 of their addresses, but still have the three override addresses, they can use only these three special addresses to spend their Curecoins on the network.

2.) A person wants to protect their Curecoins, so they create a multisig address with five signatures, two of which are required to send transactions, no override addresses. They put each private key on a different thumb drive, and put two in banks, one in an attic, one in a tin can in the backyard, and give one to a friend. In the event of a house fire or bank heist, they are still able to have access to their Curecoins.

3.) A business wants to create a voting trust for spending money. Each member on a 12-member board has their own private key, and these 12 private keys are used to create a multisig address with 12 private keys, requiring seven to spend money. No overrides. Thus, a majority of key holders must agree to spend money for a transaction to be possible.

 

Read More