AMS  Abstract Merkle Signature Scheme
Author: Herman Schoenfeld
Version: 1.1
Date: 20200720
Copyright: (c) Sphere 10 Software Pty Ltd. All Rights Reserved.
Abstract
An abstract postquantum digital signature scheme is presented that parameterizes a onetime signature scheme (OTS) for "manytime" use. This scheme permits a single keypair to efficiently sign and verify a (great) many messages without security degradation. It achieves this by following the original MerkleSignature Scheme but without a coupling to a specific OTS. Various improvements include a reduction in signature size, resistance to denialofservice attacks and smaller keys. This construction comprises a bitlevel specification for the Abstract Merkle Signature Scheme (AMS).
1. Introduction
Abstract Merkle Signatures (AMS) are a class of a quantumresistant digital signature schemes that utilize hashbased cryptography without any dependency on ellipticcurves or discrete logarithms. AMS is a formalization of the scheme originally proposed by Ralph Merkle [1] but in an OTSagnostic manner.
AMS is a "highlevel abstract" scheme that takes as a parameter a onetime signature scheme (OTS) and transforms it into a "manytime" equivalent. To this end, AMS serves as an "algorithm wrapper" of the parameterized OTS algorithm. AMS achieves this goal by encapsulating the cryptography of the OTS in an ephemeral manner* and by isolating the complexity of multiple OTS keys through the use of merkletrees.
AMS is similar in goal and scope to XMSS [2] but without a coupling to a specific OTS, with simplified tree structuring and with DoSvulnerability hardening. An AMS algorithm generally retains the performance, memory and security characteristics of the underlying OTS scheme but adds additional computational complexity in it's key generation. This arises from the fact that an AMS key is essentially a commitment to many pregenerated OTS keys.
In practice, an AMS implementation comprises of two layers, the OTS and AMS layers respectively. The AMSlayer of an AMSalgorithm requires the use of a cryptographic hash function (CHF) which is typically chosen to be the same as that employed by the OTSlayer of the algorithm (although this is not a strict requirement). The AMSlayer is itself quantumresistant as it relies solely on the proper use of a cryptographic hash function. Thus, if the OTSlayer is quantumresistant then the full AMSalgorithm is quantumresistant.
Whilst this document focuses on the AMSlayer and the integration points that an OTSlayer must comply with, it does not cover specific implementations of OTSlayers.
2. AMS Scheme
AMS is a generalpurpose, quantumresistant cryptographic scheme offering the following features:

Multiuse keys: a single private/public keypair can be used to securely sign and verify many messages.

Compact keys: keys are small and contain (compressed) hash commitments to OTS keys.

Efficient comparisons: testing if a public key derives from a private key is time efficient.

Parameterized: the underlying OTS and CHF can be changed without affecting the AMSlayer whatsoever.

Quantumresistant: AMS inherits all the PQC characteristics of the selected OTS algorithm.
Whilst AMS is strictly a "stateful" algorithm in that the signer must "remember information" about the most recent signature, it can used in a "practically stateless" manner in blockchain/DLT usecases. This is possible since changes to the keystore are not required in this scheme, only remembering the index of last used OTS key is necessary. Thus in blockchain/DLT applications, rather than maintaining this index in a local keystore, the blockchain maintains a public strictly increasing nonce that is associated with the signer. Every time a signature is generated by the signer, the public nonce field is correspondingly incremented on the public ledger as part of the consensus rules. So long as this nonce is atomically and strictly increased within the same transaction that contains the signature, no risk key reuse arises (which could if relying on local datastores susceptible to local corruption).
The AMSlayer of the scheme relies on a single cryptographic hash function (CHF) for all processing without any dependency on ellipticcurves or discrete logarithms. This CHF is also parameterized and, by convention, chosen to match that of the selected OTS scheme (although not strictly required).
The construction can be basically summarized as follows:

A
"Private Key"
is a user secret that deterministically generates batches of OTS keypairs.

A
"Public Key"
is a merkleroot of a batch of OTS keypairs.

A
"Signature"
comprises of an OTS signature, an OTS public key to validate that signature, and a merkleproof of that key within a "batch".

Signature verification entails both the underlying OTS verification algorithm and a merkleproof verification of the OTS key in the batch.
2.1 Notation & Definitions


is operator that denotes byte array concatenation. If the operand is aBYTE
,DWORD
,QWORD
it is implicitly converted to byte array usingToBytes
function. 
H(x)
is a oneway cryptographic hash function (CHF) ofU
bits. 
H^n
is cryptographic hash function that iterates theH
functionn
times such thatH^0(x) = x, H^1(x) = H(x), H^2 = H(H(x)), etc
. 
LastDWord(arr)
is a function that extracts the last 4 bytes of byte arrayarr
and reinterprets it as a littleendian 32bit unsigned integer. 
LastQWord(arr)
is a function that extracts the last 8 bytes of byte arrayarr
and reinterprets it as a littleendian 64bit unsigned integer. 
RandomBytes(N)
is a function that returns an array ofN
cryptographically random bytes. 
ToBytes(N)
is a function takes an unsigned 64bit (or 32bit) integer argumentN
returns it was an array of 8 (or 4) bytes in littleendian layout. 
Unless otherwise specified, all byte layouts are in littleendian format by default.
2.2 Private Key
A Private Key
P
is generated as follows:
P = v  OTS  h  RESERVED  Entropy
Field  Description  Bits  Value Range 
v

AMS version  8  1..256 
OTS

OTS algorithm  16  1..65536 
h

Height parameter  8  0..255 
RESERVED  30 bytes reserved for OTS parameters  224  0 
Entropy  Cryptographically random bytes used to seed OTS key generation  256  CRNG 
A private key is
64
bytes in length and can be used to sign up to
2^(64 + h)
messages. A Private Key can derive up to
2^64
unique Public Keys.
2.2.1 Field: Version
Version is an 8bit value mapping to integers
1..256
. As of this revision, the version is always
1
(mapping to all zeros). Values
2..256
are reserved for future revisions of the AMS scheme which can evolve independently from underlying OTS schemes.
2.2.2 Field: OTS
The OTS field is a 16bit field mapping to the integers
1..65536
which determines the AMS algorithm being used. These values are globally allocated by the author. Currently, they are:
AMS Algorithm  Description  OTS Algorithm  Value 
LAMS  Lamport Abstracted Merkle Signatures  Lamport  1 
WAMS  Winternitz Abstracted Merkle Signatures  WOTS  2 
WAMS+  Winternitz Abstracted Merkle Signatures Plus  WOTS+  3 
WAMS#  Winternitz Abstracted Merkle Signature Sharp  WOTS#  4 
2.2.3 Field: Height
The height parameter
h
is a 1byte value that determines how many OTS keys are coupled to a single public key. From the AMS perspective, the security of a public key degrades after being used more than
2^h
signature generations.
Specifically,
h
refers to the height of a merkletree whose leaves are a set of OTS public key hashes called the "batch". The merkleroot of the batch is called the "batchroot". A public key commits to a single batch. Signatures are signed using one of the OTS keys from the batch and never used again. The cardinality of a batch is
2^h
.
Whilst a public key can only be used for up to verify
2^h
distinct signature before security degradation, a private key can be used for
2^(64+h)
signature generations. This follows from the property that one private key can generate
2^64
unique public keys (and
2^h * 2^64 = 2^(64+h)
). Although a private key must be discarded beyond that number, it is for all practical purposes a reusable private key.
Choosing parameter
h
is left to the user as it's selection impacts the computational performance of the private key (but negligibly for the public key). Specifically, signing and verifying are negligibly impacted by
h
but generating keys and matching public keys to private keys has time complexity
O(h^2)
. If the user is able to replace their public key regularly, a low value of
0 <= h <= 8
is desirable. If a user plans to infrequently use their keys, a value
h=16
may be more appropriate in that expensive computations are done infrequently. The range
16 <= x <= 255
should be carefully considered, if at all.
h=0
will result in an private key that signs a single message thus rendering AMS into a redundant OTS. It is permitted for elegancy of the scheme.
2.3 Public Key
The public key
K
is a manytime public key and defined as follows:
K = v  h  C  B  Z  R
Term  Description  Bits  Value Range 
C

Key Code  64  UInt64 
B

Batch Number  64  UInt64 
Z

Spam Code  32  UInt32 
R

Batch Root  U  hash digest 
The public key is
(U/8 + 16)
bytes in length and can be used for
2^h
signature verifications before security begins to degrade. A single private key can derive up to
2^64
public keys by varying the
B
parameter.
2.3.1 Field: Key Code
The key code
C
is a 64bit unsigned integer derived as:
C = LastQWord( H^2( P ) )
The key code is used to efficiently test if a public key derives from a private key
P
. Since the key code is a cryptographically random checksum with
2^64
possible values, it is unlikely to collide with other (genuine) keys and thus can be used to efficiently filter matching keys.
2.3.2 Field: Batch Number
A private key can generate up to
2^64
public keys each of which commits to
2^h
OTS public keys. The batch number identifies which batch a public key commits to. All batches are derived from the private key using the batch number as a generating nonce.
2.3.3 Spam Code
The Spam Code
Z
is a 32bit unsigned integer checksum value derived as:
Z = LastDWord(H(K'_0)))
Term  Description 
K'_i

The
i'th
OTS public key in the batch
B
(
i=0
in above) 
The spam code works similarly to the key code except it is intended to thwart DoS attacks arising from deliberate key code collisions sent by a spammer. Without a spam code, a DoS attack could arise if a verifier is overwhelmed by a large list of public keys with key codes that (deliberately) collide with a known verifiers key code.
This can occur since calculating the batchroot is a computationally expensive process and a verifier can never determine if a public key is "cryptographically invalid". It can only determine if a public key derives from a private key (or not). This entails a batchroot calculation. The spam code is a mechanism to allow rapid filtering of such maliciously colliding invalid keys.
In the case where an attacker floods a verifier known good
B
and
Z
values, a verifier need only perform the expensive batchroot calculation once and cache the computed Public Key for
B
for future comparisons.
In the case where an attacker floods with varying
B
and
C
values, in an attempt to force the verifier to always evaluate the batchroot for
B
, precomputing/caching will not work since the range of values of
B
is too vast. In this scenario, the computation of the spam code is sufficient to discard this key, since the spammer cannot guess this code as it requires knowledge of the Private Key.
C
or
Z
does not provide an attacker any computational advantage in a bruteforce attack on
P
.
2.3.4 Field: Batch Root
The batch root is a merkleroot of the set of OTS public keys in the batch. It is defined as follows:
R = MerkleRoot( H(K'_0), ..., H(K'_n) )
Term  Description 
MerkleRoot

The root of the hashtree of the input leaf nodes 
K'_i

The
i'th
OTS public key in the batch
B

h

Tree Height parameter which determines batch size
2^m

n

Index of last item in batch (which is always
2^h  1 ) 
Here the batchroot commits to a set ephemeral OTS keys which will be used in signature generation and verification. Selection of the OTS keypair is performed by the signer during the signing process and care should be taken to never reuse an OTS key.
2.4 Signature Generation
For any message
M
, private key
P
and public key
K
a signature
S
is derived as follows:
1: algorithm AMS_Sign
2: Input:
3: M: a message to sign (arbitrarily long byte array)
4: P: an AMS private key to used to sign
5: B: the batch of OTS keys to use
6: i: the index of the OTS key in the batch
7: Output:
8: S: an AMS signature
9: PseudoCode:
10: let v = P.Version
11: let (P'_i, K'_i) = GenOTSKeys(P, B, i)
12: let S' = GenOTSSig( H(M), P'_i )
13: S = v  h  i  K'_i  S'  GenMerkleProof(H(K'_i), i, R)
14: end algorithm
Term  Description  Bits 
v

Version (from
P ) 
8

h

Height (from
P ) 
8

i

The index of the selected OTS key from the batch 
32

S'

The OTS signature for the message 
OTS_SigBits

P'_i

The OTS private key which derives
K'_i

OTS_PrivKeyBits

K'_i

The
i'th
OTS public key from the batch 
OTS_PubKeyBits

R

The batchroot of the batch which contains
K'_i

U

GenOTSKeys(x,y,z)

OTSlayer function that generates the
z'th
OTS keypair in batch
y
for private key
x


GenOTSSig(x,y)

OTSlayer function that generates an OTS signature of messagedigest
x
using OTS private key
y


GenMerkleProof(x,y,z)

A standard merkletree function that generates a merkleproof that
x
is
y'th
leaf of a merkletree with root
z


OTS_SigBits

Length of the OTS signature as returned by the OTS layer  
OTS_PrivKeyBits

Length of an OTS signature as returned by the OTS layer  
OTS_PubKeyBits

Length of an OTS signature as returned by the OTS layer. See Note below. 
Signatures are
(48 + OTS_PubKeyLenLength(S') + (h+1)*(U/8))
bytes in length, the bulk of which comprises of the OTS signature.
w
, the "WOTS public key" in the WAMS signature only consumes
U
bits (a significant optimization).
2.4.1 OTS Index
When signing. the selection of
i
is performed by the signer and care should be taken to not reuse a previously used onetime key. In blockchainbased applications, this is achieved by using the strictly increasing Nonce field from signing identity object stored in a public consensus database. Since this does not require local database updates, and the Nonce is always updated across a consensus database after a signed transaction is confirmed, there is no risk of accidental key reuse arising from local state corruption. Signature reuse could still exist but this would arise from a bug or attack to the client code (no different to traditional cryptographic schemes). When used in this manner, the AMS scheme can be considered "practically stateless", however it is not strictly so.
In nonblockchain/DLT applications, care should be taken to remember the index of the last OTS signature so as not to reuse. Note, if an attacker is able to trick the code into reusing an OTS key, it's security could be totally compromised after a few reuses.
2.5 Signature Verification
1: algorithm AMS_Verify:
2: Input:
3: M: the message being verified (arbitrary byte array)
4: S: the AMS signature of M
5: K: the AMS public key used to verify S
6: Output: Boolean
7: PseudoCode:
8: let size0 = U/8 ; byte size of a CHF digest
9: let size1 = OTS_SigLen/8 ; byte size of an OTS signature
10: let size2 = OTS_PubKeyLen/8 ; byte size of an OTS public key (hash)
11:
12: let reader = byte stream reader for S ; a littleendian byte reader
13: let v = reader.ReadByte ; AMS version
14: let h = reader.ReadWord ; height
15: let i = reader.ReadUInt ; OTS key index
16: let PKH = reader.ReadBytes(size2) ; OTS public key (hash)
17: let S' = reader.ReadBytes(size1) ; OTS signature
18: let MP = reader.ReadBytes(h * size0) ; merkleproof
19: let R = K.R ; batch root
20: Result = (v == K.Version) AND VerMerkleProof(MP, PKH, i, 2^h, R) AND VerOTSSig(S', H(M), PKH)
21: end algorithm
Term  Description 
VerOTSSig(x, y, z)

An OTSlayer function that returns true iff
x
is an OTS signature of messagedigest
y
which verifies with OTS public key (hash)
z , otherwise returns false. 
VerMerkleProof(u, v, w, x, y)

An OTSlayer function function that returns true iff
u
is the merkleproof that
v
is the
w'th
leaf in a merkletree whose leaves are a set of cardinality
x
and whose merkleroot is
y . 
The
VerMerkleProof
term ensures that the OTS key used by the signature was committed to by the public key and the
VerOTSSig
term verifies the OTS signature verifies to that OTS key. With these two steps, the verifier has determined the AMS signature contains a valid OTS signature and that the OTS public key in the signature was committed to by the AMS public key. Since only the bearer of the AMS private key can know the OTS private key, it follows the AMS signature was signed by the bearer of the AMS private key.
3. Reference Implementation
This section contains snippets for the full reference implementation [ 3 ]. The reference implementation is part of the PQC library within the Hydrogen Framework [4] .
3.1 OTS Interface
public interface IOTSAlgorithm {
OTSConfig Config { get; }
void SerializeParameters(Span buffer);
void ComputeKeyHash(byte[,] key, Span result);
byte[,] SignDigest(byte[,] privateKey, ReadOnlySpan digest);
bool VerifyDigest(byte[,] signature, byte[,] publicKey, ReadOnlySpan digest);
OTSKeyPair GenerateKeys(ReadOnlySpan seed);
}
public static class IOTSAlgorithmExtensions {
public static byte[] ComputeKeyHash(this IOTSAlgorithm algo, byte[,] key) {
var result = new byte[algo.Config.DigestSize];
algo.ComputeKeyHash(key, result);
return result;
}
}
3.2 AMS Implementation
public class AMS : DigitalSignatureSchemeBase {
public const int MaxHeight = 20;
public const byte Version = 1;
private readonly IOTSAlgorithm _ots;
public AMS(AMSOTS ots)
: this(InstantiateOTSAlgorithm(ots)) {
}
public AMS(AMSOTS ots, int h)
: this(InstantiateOTSAlgorithm(ots), h) {
}
public AMS(IOTSAlgorithm algorithm)
: this(algorithm, Configuration.DefaultHeight) {
}
public AMS(IOTSAlgorithm algorithm, int h)
: this (algorithm, new Configuration(algorithm.Config, h)) {
}
public AMS(IOTSAlgorithm algorithm, Configuration config)
: base(algorithm.Config.HashFunction) {
Config = config;
_ots = algorithm;
Traits = Traits & DigitalSignatureSchemeTraits.PQC;
}
public Configuration Config { get; }
public override IIESAlgorithm IES => throw new NotSupportedException("PQC algorithms have no known IES algorithms");
public override bool TryParsePublicKey(ReadOnlySpan bytes, out PublicKey publicKey)
=> PublicKey.TryParse(bytes, _ots.Config.HashFunction, out publicKey);
public override bool TryParsePrivateKey(ReadOnlySpan bytes, out PrivateKey privateKey)
=> PrivateKey.TryParse(bytes, _ots.Config.HashFunction, out privateKey);
public override PrivateKey GeneratePrivateKey(ReadOnlySpan secret) {
if (secret.Length != 32)
throw new ArgumentException("Must be 256bit value", nameof(secret));
var rawBytes = new byte[64];
Array.Fill(rawBytes, (byte)0);
rawBytes[0] = Version;
EndianBitConverter.Little.WriteTo((byte)_ots.Config.AMSID, rawBytes, 1);
rawBytes[3] = (byte)Config.H;
_ots.SerializeParameters(rawBytes.AsSpan(4, 28));
secret.CopyTo(rawBytes.AsSpan(^32));
return new PrivateKey(rawBytes, _ots.Config.HashFunction);
}
public override PublicKey DerivePublicKey(PrivateKey privateKey, ulong signerNonce) {
var batchLength = 1U << privateKey.Height;
var batchNo = signerNonce / batchLength;
return DerivePublicKeyForBatch(privateKey, batchNo, true);
}
public PublicKey DerivePublicKeyForBatch(PrivateKey privateKey, ulong batchNo, bool rememberBatch = false) {
var batch = CalculateBatch(privateKey, batchNo, out var spamCode);
var rawPubKey = Tools.Array.Concat(
EndianBitConverter.Little.GetBytes((uint)privateKey.KeyCode),
EndianBitConverter.Little.GetBytes((ulong)batchNo),
EndianBitConverter.Little.GetBytes((uint)spamCode),
batch.Root
);
if (rememberBatch) {
var publicKeyWithBatch = new PublicKeyWithBatch(rawPubKey, batch);
privateKey.RememberDerivedKey(publicKeyWithBatch);
}
return new PublicKey(rawPubKey);
}
public override bool IsPublicKey(PrivateKey privateKey, ReadOnlySpan publicKeyBytes) {
var batchNo = PublicKey.ExtractBatchNo(publicKeyBytes);
return
privateKey.KeyCode == PublicKey.ExtractKeyCode(publicKeyBytes) &&
CalculateSpamCode(privateKey, batchNo) == PublicKey.ExtractSpamCode(publicKeyBytes) &&
DerivePublicKeyForBatch(privateKey, batchNo).RawBytes.AsSpan().SequenceEqual(publicKeyBytes);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public byte[] Sign(PrivateKey privateKey, ReadOnlySpan message, ulong batchNo, int otsIndex) {
var messageDigest = CalculateMessageDigest(message);
return SignDigest(privateKey, messageDigest, batchNo, otsIndex);
}
public override byte[] SignDigest(PrivateKey privateKey, ReadOnlySpan messageDigest, ulong signerNonce) {
var (batchNo, otsIndex) = GetOTSIndex(privateKey.Height, signerNonce);
return SignDigest(privateKey, messageDigest, batchNo, otsIndex);
}
public byte[] SignDigest(PrivateKey privateKey, ReadOnlySpan messageDigest, ulong batchNo, int otsIndex) {
var builder = new ByteArrayBuilder();
// Append header
builder.Append(privateKey.Height);
builder.Append(EndianBitConverter.Little.GetBytes((ushort)otsIndex));
// Get/Calc the OTS batch
if (!privateKey.DerivedKeys.TryGetValue(batchNo, out var publicKeyWithBatch)) {
DerivePublicKeyForBatch(privateKey, batchNo, true);
publicKeyWithBatch = privateKey.DerivedKeys[batchNo];
}
var otsPubKey =
Config.OTS.UsePublicKeyHashOptimization ?
publicKeyWithBatch.Batch.GetValue(MerkleCoordinate.LeafAt(otsIndex)):
this.GetOTSKeys(privateKey, batchNo, otsIndex).PublicKey.AsFlatSpan();
Debug.Assert(otsPubKey.Length == Config.OTS.PublicKeySize.Length * Config.OTS.PublicKeySize.Width);
builder.Append(otsPubKey);
// Derive the individual private key again
// NOTE: possibility to optimize here if we want to cache ephemeral OTS private key, but large in memory
var otsKey = GetOTSKeys(privateKey, batchNo, otsIndex);
// Perform the OTS sig
var otsSig = _ots.SignDigest(otsKey.PrivateKey, messageDigest).ToFlatArray();
Debug.Assert(otsSig.Length == _ots.Config.SignatureSize.Length * _ots.Config.SignatureSize.Width);
builder.Append(otsSig);
// Append merkleexistence proof of pubKey in Batch (will always be 2^h hashes)
var authPath = publicKeyWithBatch.Batch.GenerateExistenceProof(otsIndex).ToArray();
foreach (var bytes in authPath) {
builder.Append(bytes);
}
var sig = builder.ToArray();
return sig;
}
public override bool VerifyDigest(ReadOnlySpan signature, ReadOnlySpan digest, ReadOnlySpan publicKey) {
Guard.Argument(IsWellFormedSignature(signature), nameof(signature), "Not a valid AMS signature");
Guard.Argument(digest.Length == _ots.Config.DigestSize, nameof(digest), $"Message digest must be { _ots.Config.DigestSize } bytes");
var reader = new ByteSpanReader(EndianBitConverter.Little);
var height = reader.ReadByte(signature);
var otsIndex = reader.ReadUInt16(signature);
var otsPubKey = reader.ReadBytes2D(signature, _ots.Config.PublicKeySize.Length , _ots.Config.PublicKeySize.Width);
var otsSig = reader.ReadBytes2D(signature, _ots.Config.SignatureSize.Length, _ots.Config.SignatureSize.Width);
var proof = new byte[height][];
for (var i = 0; i < proof.Length; i++)
proof[i] = reader.ReadBytes(signature, _ots.Config.DigestSize);
// OTS Key must exist in batch
var otsPubKeyHash = Config.OTS.UsePublicKeyHashOptimization ? otsPubKey.AsFlatSpan(): _ots.ComputeKeyHash(otsPubKey);
if (!MerkleMath.VerifyExistenceProof(_ots.Config.HashFunction, PublicKey.ExtractBatchRoot(publicKey).ToArray(), MerkleSize.FromLeafCount(1 << height), MerkleCoordinate.LeafAt(otsIndex), otsPubKeyHash, proof))
return false;
// OTS sig must be valid
return _ots.VerifyDigest(otsSig, otsPubKey, digest);
}
public bool IsWellFormedSignature(ReadOnlySpan signature) {
if (signature == null  signature.Length == 0)
return false;
var h = signature[0];
return signature.Length == (
3
+ (_ots.Config.PublicKeySize.Length * _ots.Config.PublicKeySize.Width)
+ (_ots.Config.SignatureSize.Length * _ots.Config.SignatureSize.Width)
+ h * _ots.Config.DigestSize);
}
private IMerkleTree CalculateBatch(PrivateKey privateKey, ulong batchNo, out uint spamCode) {
var batchSize = 1 << privateKey.Height;
var batchLeafs = new byte[batchSize][];
Parallel.For(0, batchSize, i => {
batchLeafs[i] = GetOTSKeys(privateKey, batchNo, i).PublicKeyHash.Value;
});
spamCode = CalculateSpamCode(batchLeafs[0]);
var merkleTree = new SimpleMerkleTree(_ots.Config.HashFunction);
merkleTree.Leafs.AddRange(batchLeafs);
return merkleTree;
}
private uint CalculateSpamCode(PrivateKey privateKey, ulong batchNo)
=> CalculateSpamCode(GetOTSKeys(privateKey, batchNo, 0).PublicKeyHash.Value);
private uint CalculateSpamCode(ReadOnlySpan wotsKey0)
=> EndianBitConverter.Little.ToUInt32(wotsKey0.Slice(^4));
private OTSKeyPair GetOTSKeys(PrivateKey privateKey, ulong batchNo, int index) =>
_ots.GenerateKeys(Tools.Array.Concat(EndianBitConverter.Little.GetBytes((uint)index), EndianBitConverter.Little.GetBytes((ulong)batchNo), privateKey.RawBytes));
private (ulong batchNo, int otsIndex) GetOTSIndex(int height, ulong signerNonce) {
var batchLength = 1U << height;
return (signerNonce / batchLength, (int)(signerNonce % batchLength));
}
private static IOTSAlgorithm InstantiateOTSAlgorithm(AMSOTS ots) {
switch (ots) {
case AMSOTS.WOTS:
return new WOTS(WOTS.Configuration.Default.W, true);
case AMSOTS.WOTS_Sharp:
return new WOTSSharp(WOTSSharp.Configuration.Default.W, true);
default:
throw new NotSupportedException(ots.ToString());
}
}
public abstract class Key : IKey {
protected Key(byte[] immutableRawBytes) {
RawBytes = immutableRawBytes;
}
public readonly byte[] RawBytes;
public override bool Equals(object obj) {
if (obj is Key key) {
return Equals(key);
}
return false;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected bool Equals(Key other) {
return Equals(RawBytes, other.RawBytes);
}
public override int GetHashCode() {
return (RawBytes != null ? RawBytes.GetHashCode(): 0);
}
#region IKey
byte[] IKey.RawBytes => RawBytes;
#endregion
}
public class PrivateKey : Key, IPrivateKey {
public readonly byte Version;
public readonly byte Height;
public readonly uint KeyCode;
public readonly Dictionary _derivedKeys;
internal PrivateKey(byte[] immutableRawBytes, CHF chf)
: base(immutableRawBytes) {
Version = immutableRawBytes[0];
Guard.Argument(Version == AMS.Version, nameof(immutableRawBytes), "Unrecognized version");
Height = immutableRawBytes[1];
Guard.Argument(0 <= Height && Height <= MaxHeight, nameof(immutableRawBytes), "Unsupported key height");
KeyCode = CalculateKeyCode(immutableRawBytes, chf);
_derivedKeys = new Dictionary();
}
internal void RememberDerivedKey(PublicKeyWithBatch publicKey) => _derivedKeys[publicKey.BatchNo] = publicKey;
public IReadOnlyDictionary DerivedKeys => _derivedKeys;
public static bool TryParse(ReadOnlySpan rawBytes, CHF chf, out PrivateKey privateKey) {
var version = rawBytes[0];
if (version != AMS.Version) {
privateKey = null;
return false;
}
var height = rawBytes[1];
if (height > MaxHeight) {
privateKey = null;
return false;
}
privateKey = new PrivateKey(rawBytes.ToArray(), chf);
return true;
}
private static uint CalculateKeyCode(ReadOnlySpan privateKeyRawBytes, CHF chf)
=> EndianBitConverter.Little.ToUInt32(Hashers.Iterate(chf, privateKeyRawBytes, 2).AsSpan(^4));
}
public class PublicKey : Key, IPublicKey {
public readonly ulong BatchNo;
public readonly uint KeyCode;
public readonly uint SpamCode;
public readonly byte[] BatchRoot;
internal PublicKey(byte[] immutableRawBytes)
: base(immutableRawBytes) {
KeyCode = ExtractKeyCode(immutableRawBytes);
BatchNo = ExtractBatchNo(immutableRawBytes);
SpamCode = ExtractSpamCode(immutableRawBytes);
BatchRoot = ExtractBatchRoot(immutableRawBytes).ToArray();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static uint ExtractKeyCode(ReadOnlySpan publicKeyRawBytes)
=> EndianBitConverter.Little.ToUInt32(publicKeyRawBytes, 0);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static ulong ExtractBatchNo(ReadOnlySpan publicKeyRawBytes)
=> EndianBitConverter.Little.ToUInt64(publicKeyRawBytes, 4);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static uint ExtractSpamCode(ReadOnlySpan publicKeyRawBytes)
=> EndianBitConverter.Little.ToUInt32(publicKeyRawBytes, 12);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static ReadOnlySpan ExtractBatchRoot(ReadOnlySpan publicKeyRawBytes)
=> publicKeyRawBytes.Slice(16);
public static bool TryParse(ReadOnlySpan rawBytes, CHF chf, out PublicKey publicKey) {
if (rawBytes.Length != Hashers.GetDigestSizeBytes(chf) + 16) {
publicKey = null;
return false;
}
publicKey = new PublicKey(rawBytes.ToArray());
return true;
}
}
public class PublicKeyWithBatch : PublicKey {
public readonly IMerkleTree Batch;
internal PublicKeyWithBatch(byte[] immutableRawBytes, IMerkleTree batch)
: base(immutableRawBytes) {
Batch = batch;
}
}
public sealed class Configuration : ICloneable {
public const int DefaultHeight = 8;
public readonly int H;
public readonly OTSConfig OTS;
public Configuration(OTSConfig otsConfig) : this(otsConfig, 8) {
}
public Configuration(OTSConfig otsConfig, int h) {
Guard.ArgumentInRange(h, 0, AMS.MaxHeight, nameof(h));
OTS = (OTSConfig)otsConfig.Clone();
H = h;
}
public Configuration Clone() => new Configuration(OTS, H);
object ICloneable.Clone() => Clone();
}
}
4. References
[1] Ralph Merkle. "Secrecy, authentication and public key systems / A certified digital signature". Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979. Url: http://www.merkle.com/papers/Certified1979.pdf
[2] IRTF. "XMSS: eXtended Merkle Signature Scheme". Accessed: 20200701, URL: https://tools.ietf.org/html/rfc8391
[3] Sphere 10 Software. PQC Library. Accessed 20230509, Url: https://github.com/Sphere10/Hydrogen/tree/master/src/Hydrogen/Crypto/PQC
[4] Sphere 10 Software. Hydrogen Framework. Accessed 20240509, url: https://github.com/Sphere10/Hydrogen