Keys and Digital Signatures
Public-Private key pairs, combined with digital signatures, provide the mechanism required to hold coins securely and to independently prove ownership of them. Keys are held and controlled by a user’s wallet.
A private key is intended to be known only to the owner of the coins, whereas the corresponding public key can be shared without risk of compromising the coins and is used to receive funds which then become secured by the associated private key.
You can think of a public key as being your bank account number and the private key as your PIN number.
Generating Public-Private Key Pairs
An essential property of Public-Private key pairs is that the private key should not be deducible from the public key. Various cryptographic algorithms are available for generating a public key from a private key, for example RSA or Elliptic Curve Cryptography. These are one-way functions which, using complex mathematics, ensure that the private key cannot be deduced from the public key.
Digital Signature Schemes
Using a public-private key pair and a digital signature scheme, a user can digitally ‘sign’ some data e.g. a transaction, with their private key to create an unforgeable digital signature. Digital signatures are generated by applying the algorithm of the signature scheme to the private key and some data. Anyone can independently verify the validity of a signature knowing the user’s public key, the data, and the check algorithm of the digital signature scheme.
Minima uses the Winternitz One-Time Signature Scheme (WOTSS) as its digital signature scheme which applies one algorithm for generating public keys from a private seed and another to compute a digital signature, with a given piece of data to be signed. Winternitz is considered to be Quantum-resistant.
Not all Digital Signature Schemes are considered Quantum-resistant, for example RSA and Elliptic Curve Digital Signature Algorithm (ECDSA), used in Bitcoin and Ethereum. In the 90’s, Shor published a Quantum algorithm which could be used to break these schemes, rendering them vulnerable to attack from Quantum-based computers in the future.
Merkle Signature Scheme
The Merkle Signature Scheme (MSS), originally proposed by Ralph Merkle in the 70’s, combines a Quantum-resistant, hash-based, but one-time-use, digital signature scheme with hash trees.
A one-time-use signature scheme means that each public-private key pair can only be used once, securely, to sign some data. Reusing the same key pair for multiple signatures increases the chances of the private key being deduced. To mitigate this inconvenience, many single-use key pairs can be stored as leaf nodes in a hash tree, with the root hash of the tree used as a multiple-use root public key.
Minima uses a Merkle Signature Scheme by combining the Winternitz One Time Signature Scheme (WOTSS) with Merkle Mountain Range (MMR) hash trees. Winternitz is used to generate private/public key pairs and signatures which are stored as leaf nodes in an MMR, creating a Tree of Keys.
The cryptographic hash function used in Minima’s implementation of the Merkle Signature Scheme is SHA3-256, which is considered Quantum-resistant. It takes an input message and produces a 256-bit message digest, from which the input message cannot be determined.
Minima also uses MMR trees for storing a user’s coins. See MMR.
Trees of Keys
A Tree of Keys enables a user to have many secure but one-time-use private keys all associated with the same root public key. This is useful because it allows a user to share a single public key for receiving funds but to sign each transaction with a different private key, ensuring maximum security.
This root public key can be used securely, the same number of times as there are private keys associated with it, i.e. the number of leaf nodes in the tree. By signing with a different private key for each transaction, and presenting a proof path with the signature which indicates the path through the MMR tree from the private key to the tree root, any external party can validate that the signature was generated by the rightful owner of the funds.
Example of a single Tree of Keys
A TreeKeyNode is a single MMR Tree with (a default) 64 single-use Winternitz public-private key pairs and a Root public key
Each leaf node (Winternitz Key Pair & Signature) is generated using:
- a private seed - this is generated by concatenating a number from 0-63 with the private seed of this TreeKeyNode. i.e. Hash(i, PrivateSeed) for i = 0-63.
- a hash function with specified digest size - Minima uses the SHA3 hash function with a 256 bit digest.
- a chosen Winternitz parameter - Minima uses a Winternitz parameter of 8.
To find out more about Winternitz security, see https://eprint.iacr.org/2011/191.pdf
Therefore each leaf node corresponds to a Winternitz Key Pair and Signature:
| WOT Signature Scheme | Description |
|---|---|
| WOTS Private Key | Single use Winternitz private key |
| WOTS Public Key | Single use Winternitz public key |
| WOTS Signature | The one-time signature (of a given message/transaction) generated with the private key |
Example TreeKeyNode with just 4 leaf nodes:
Once all 64 keys are generated, the root hash can be calculated. Clearly a public key which can only be used securely 64 times would not be sufficient. To get more uses from a single root public key, there needs to be more keys (leaf nodes). However, the more Winternitz keys that exist, the longer it takes to generate them and the longer it takes to generate the root hash i.e. the root public key.
In order to efficiently scale the number of uses possible for a root public key, instead of simply generating a single large Tree of Keys with hundreds of thousands of leaf nodes, Minima constructs a Tree of Trees with multiple levels and a single top root.
A Tree of Trees consists of (a default) 3 levels where the root of all level 2 and 3 trees are signed by a Winternitz key pair in the level above (as shown below). The level 3 trees contain the Winternitz keys which are used to sign transactions.
Each individual Tree in Level 2 is connected to a leaf node key on Level 1 and will have its own private seed, generated by hashing the Level 1 key number (0-63) with its private key. Likewise, each Level 3 tree is connected to a key from a Level 2 tree.
The private keys from level 1 and 2 are used to sign the root hash of the level 2 and 3 trees respectively, creating a Tree of Key Trees, connected through signatures.
Diagram showing a full Tree of Trees (with default 3 levels & 64 keys/tree)
With each individual MMR tree containing 64 keys as leaf nodes; adding a second level of MMR trees provides 642 WOTS public-private key pairs.
The MMR tree grows logarithmically, with n levels providing a maximum of 64n one-time-use key pairs for the user to sign transactions with.
Minima uses a default 3 levels, providing a total of 643 = 262144 one-time-use keys.
The advantage of a ‘tree of trees’ over a single large tree is that:
- The user's root public key is calculated efficiently - only requiring the top (level 1) tree to be generated;
- Each level of trees is connected via digital signatures which can be independently verified
- Each level 3 tree can be added on demand as the user requires more private keys for signing transactions.
Single Tree (TreeKeyNode) properties
| TreeKeyNode Property | Description | Type |
|---|---|---|
| Size | The number of leaf nodes in this MMR Tree. Default is 64. | Integer |
| Tree | The MMR Tree structure of this TreeKeyNode | MMR |
| Children | An array of the child Trees belonging to this Tree (default 64 for each level 1 and 2 tree, 0 for level 3 trees) | TreeKeyNode array |
| Keys | An array of the Winternitz Keys added as leaf nodes to this Tree (default 64). | Winternitz Keys array |
| ChildSeed | The hash of the Private Seed that was used to generate this Tree i.e. Hash(PrivateSeed). This child seed will be used as the base to generate the private seeds for each child Tree (for level 1 & 2 trees only) | MiniData |
| PublicKey | The root hash of the tree. If this tree is Level 1, this will be the user’s root public key. | MiniData |
| ParentChildSig | The signature generated when the parent tree signed the root of this Tree (levels 2 and 3 only) | Signature Proof |
Tree of Trees (TreeKey) properties
| TreeKey Property | Description | Type |
|---|---|---|
| Root | The top tree of this tree of trees, generated from the user’s Base Private Seed. | TreeKeyNode |
| Levels | Number of levels of trees in this tree of trees (default 3) | Integer |
| KeysPerLevel | The number of keys per single tree (default 64) | Integer |
| Uses | The number of times the root public key has been used | Integer |
| Max Uses | The maximum number of uses = (Keys/level)number of levels. Default is 643. | Integer |
| PrivateSeed | The PrivateSeed used to generate all the trees in this TreeKey. | MiniData |
| Public Key | The root hash from the root tree. | MiniData |
Each TreeKey requires a private seed from which all the leaf node private keys are generated. This is covered in more detail next.
Constructing a Tree of Trees
On creation of a new Minima node, a 32 byte Base Private Seed is created using a Pseudo Random Number Generator (PRNG). From this base private seed, further private seeds are generated by combining it with a modifier (another 32 byte random number).
Each of these modified private seeds is used to create a Tree of Trees, the root of which becomes one of the user’s multiple-use root public keys.
Executing the keys command shows us the root keys that have been created:
keys
{
"command":"keys",
"status":true,
"response":[{
"size":64,
"depth":3,
"uses":0,
"maxuses":262144,
"modifier":"0x02984CB232D0C003F6681980689F45BA255522131882E1530D393518401A6CF8",
"publickey":"0x9F9FBFD83D999D952BE4A6538252043987F3937F3BBC361F00D5AE708EF1A105",
"privatekey":"0x28AF0DD826C1D49A74F6533920AFBCE5D2044AA822591B389E4A4518C483E672"
},
Public Keys, Scripts and Addresses in Minima
All 0x addresses in Minima, which can be shared publicly to receive funds, are Pay-to-Script-Hash (P2SH). This means that all funds are sent to the hash of a script. A Script is a series of instructions which are executed when a transaction is validated and added to a block. A transaction is only valid if the script returns a value of TRUE.
Every user has a set of default addresses, and hence scripts. For each of their root public keys, there is an associated default script - RETURN(SIGNEDBY(RootPublicKey)), the hash of which is an address of the user which can be used to receive funds.
Whenever a user receives funds to a specific address, a new coin is created containing that script, which must return a value of TRUE at the time of being spent in a transaction. This script will only return TRUE if the rightful owner of the coin has signed the transaction with one of the private keys for the given root public key - the one in the script - else it will return FALSE.
Example
When Alice sends funds to Bob’s address, she is actually locking those funds into a new coin with a script which says RETURN(SIGNEDBY(Bob’sPublicKey)). This coin can only be spent when a transaction, containing this coin as an input, is signed with a single-use private key of Bob’sPublicKey.
Assuming Bob is the only one holding his private keys, Bob is the only person who can spend this coin.
Signature Generation
When choosing to sign a transaction with the root public key, the user must not only provide the WOT signature of the transaction, but also the Parent-Child signatures that connect the multiple levels of the tree, and the proof path from leaf node to root for each level. This provides the full path from the transaction signature to the root public key, which can be then validated by any other user in the network.
A full signature, required for the transaction Witness therefore includes a list of MMR Proof paths and signatures from the bottom of the tree of trees, to the root public key at the top.
For example, a full signature proof in a transaction Witness would consist of:
MMR Proof path from the root public key to a Level 1 Winternitz key leaf node
with the ParentChildSignature connecting Level 1 to 2 (as a result of using a level 1 key to sign a Level 2 root)MMR Proof path from the root of the first Level 2 tree to a Level 2 Winternitz key leaf node
with the ParentChildSignature from Level 2 to 3 (as a result of using a level 2 key to sign a Level 3 root)MMR Proof path from the root of a Level 3 tree to a Level 3 Winternitz key leaf node
with the Signature of the transaction (as a result of using a level 3 key to sign the transaction)
Only the final signature is the signature generated from signing the transaction, the preceding signatures are the Parent-Child signatures that connect the multiple tree levels.
To learn more about MMR proofs, see the section on MMR Database.
The serialised data for each MMR Signature Proof consists of:
| Signature Proof Attribute | Description | Type |
|---|---|---|
| Public Key | The Winternitz public key of the leaf node | 64 byte hash (MiniData) |
| Proof | A list of Proof Chunks (nodes in the MMR tree) which provide the path from leaf node to the root of the tree. | MMR Proof |
| Winternitz Signature | A Winternitz Signature from signing either a child MMR key tree or some data e.g. a transaction | 64 byte hash (MiniData) |
In a transaction Witness, each Signature Proof also shows a root key which is the root hash of either the Level 1, 2 or 3 tree, where the Level 1 root hash is a multiple use root public key of the user.
Example of a full signature for a transaction:
"signatures":[{
"signatures":[
{"publickey":"0xE574DE48114CE0C8B73B40BBA9069EE354C227EC0965123B458D2CB24EFD6A83", "rootkey":"0xF9C0872B59932D11434CF3CCB23EDA1F7F189AC4438AD1D00AF94D7C28B6275B",
"proof":{
"blocktime":"0",
"proof":[{
"left":false,
"data":{
"data":"0x51761AF1E1BD225EAED96916AC1317B9F47315B5155156B681B5DAA4B65EB699",
"value":"0"}},
{"left":false,
"data":{ "data":"0x6F612A1F62206489CF6F00C3B6424C2D54E02B72C11763E21EC0E0C3D85161B8",
"value":"0"}},
{"left":false,
"data":{ "data":"0x2E999787BFA586571880580CD7B99C748F18900D1CD207C9AC9538A30207285B",
"value":"0"}},
{"left":false,
"data":{ "data":"0xD36DBD6C4E23A75B55AFB813EF067CA25A661C8AB82F5288BD0D0B2DCF0CA140",
"value":"0"}},
{"left":false,
"data":{ "data":"0x4DDC92942DBCCBBC1C026ADC92715F8A021F16E6FE35810AAD30D6E698980E3D",
"value":"0"}},
{"left":false,
"data":{ "data":"0x840F1A656596F02F1B787605E131AA1E3CF93DE618FFFC0EB03DDF301E861741",
"value":"0"}}],
"prooflength":6},
"signature":"0x…"},
{"publickey":"0xC14C2C8B35E55A2DF25EA0BA8A528BEEF8BD3FE688885B176BEBB8E8D95FAE67", "rootkey":"0x707BE4E4F280CC96F5972F66FCDFCFC78356ACD548EF74513E24257FFED8DE6C",
"proof":{
"blocktime":"0",
"proof":[{
"left":false,
"data":{ "data":"0x4F13DDDA0847150B2427C8E477908C790C5E001378816041CB550185303B9319",
"value":"0"}},
{"left":false,
"data":{ "data":"0xE3B4F5B1ADB6F71974C13AADDE8C26FAC61F6C0DAD76BA9C316740DA1B5480B2",
"value":"0"}},
{"left":false,
"data":{ "data":"0xE0B0051ED7B743EE466BF96D554B629B21A1588E09A18E6D2D02DBC77F26D473",
"value":"0"}},
{"left":false,
"data":{ "data":"0xD42055AFA35C85B98C92F1734956857816EB67BB4C16AEB12CFF3EDD0BC2488A",
"value":"0"}},
{"left":false,
"data":{ "data":"0xF1F986238938A8F82FD393E70F9226959FF115D3A4DC2AC7E13E40A58565B0E7",
"value":"0"}},
{"left":false,
"data":{ "data":"0x1029171D8035E7461C5367987A6096A832F56C7558E6E859088718FC321F8DFA", "value":"0"}
}],
"prooflength":6},
"signature":"0x…"},
{"publickey":"0xA54B6673D6A890444A90EFBE64FBD8576D59E144BB7166DA83109C9C32CF93B2", "rootkey":"0x15DF8CEA59E66D31762DB7F8D3A972CFF55F0E8DA25CA9C4222AAF93BBD7A31E",
"proof":{
"blocktime":"0",
"proof":[{
"left":false,
"data":{ "data":"0x6E2A8A0201D45E5B21003FA39FC32CF78755028F670687145DF365788AB83BEF",
"value":"0"}},
{"left":false,
"data":{ "data":"0xB9975A60B1187FFDF8C5F82DE910D47186DBB72A3CB478CB6BE168AD5FCD6AFD",
"value":"0"}},
{"left":false,
"data":{ "data":"0x07197775FA938D76A4252E2DD010E4C6145DCBE4EFD362E68DBDE79745563853",
"value":"0"}},
{"left":false,
"data":{ "data":"0x2C923B177B0417AF1E9A89858980D544CC065004F361B1BE395EC60DF674781F",
"value":"0"}},
{"left":false,
"data":{ "data":"0x235B875C4E2A48248DE06079613724D982A96069AE86ADD26F772AC192DDC5A2",
"value":"0"}},
{"left":false,
"data":{ "data":"0x9B90AD45CAEC23926163E65CC838207CDE1D48B990602E8F4AF060116BBEDA36",
"value":"0"}}],
"prooflength":6
},
"signature":"0x…." }
]
}],