Cryptographic primitives

Cryptographic primitives used by BEAM are based on the secp256k1 library (the one that is used in bitcoin). Naturally it uses the same elliptic curve equation. The following primitives are used directly:

• secp256k1_gej - Basic curve point arithmetics: point addition, doubling, negation, import/export to a platform-ndependent format.
• secp256k1_scalar - Scalar arithmetics: addition, multiplication, inverse
• secp256k1_sha256_t - SHA-256 hash
• Cryptographic nonce generation (nonce_function_rfc6979).
• secp256k1_hmac_sha256_t - HMAC (message authentication)

The following cryptographic functions and schemes are built over them:

• Point multiplication (by a scalar).
  • There are different multiplication modes and scenarios:
    • Secure/Fast
    • Point may be either known in advance (a.k.a. Generator, prepared for multiplication) or "casual".
    • Aggregation: when many points are multiplied by scalars and summed - an appropriate effective algorithm is used.
  • The reason that this functionality is implemented in BEAM and not taken directly from secp256k1 is the following:
    • We'd like to have more low-level control of the primitives to implement advanced schemes
    • We need more generators: Standard secp256k1 supports just two (G,H), whereas we need many more (131)
    • No effective aggregation implementation
• Commitments (encoded amount with the blinding factor)
• Schnorr's signatures (including multi-sig)
• Bulletproofs (including multi-sig and batch verification)
• Secure communication channels
• Secure BBS messaging system

In addition there's a uintBig - a "big integer" (arbitrary width), supports basic arithmetics and shift operations (not including division). The number is represented as an array of bytes in a big-endian byte order. Platform-independent, serialized as-is. Implementation is very straight-forward, not for performance-critical tasks.

Hash

The Hash refers to the SHA-256 hash, unless otherwise specified. Used in various schemes. When hashing some data, it's fed in a way that is both platform-independent and unambiguous. This is achieved by the following specifications:

• 1-byte data is fed as-is
• Boolean values are encoded as a single byte with value either 0 or 1.
• Strings are fed as-is, including the 0-terminator (to prevent ambiguity for consequent strings).
• Numerical types (fixed-point) are stored as a variable-length byte sequence, with a special terminator mark. This ensures platform independence (integers may have varying width across different platforms).
• Non-primitive types are converted into the platform-independent binary format for hashing.

The following objects are derived from hash (built over them)

Oracle

Oracle is used in non-interactive cryptographic proofs, it's supposed to produce cryptographic challenges in a deterministic way, based on the visible transcript to the moment.

In BEAM Oracle uses the Hash in a straightforward way. All the visible transcript is hashed. Once the challenge is needed - the hash value is finalized, the result is the challenge, and it's immediately re-fed to the Hash. So that the new challenge construction (if needed) is generated from the visible transcript, including the previous challenge.

If there are restrictions for the challenge (such as it should be non-overflowing, non-zero scalar, or a valid x-coordinate of a curve point) - the Finalize-Re-feed is called in a loop, until the satisfying challenge is produced (i.e. accept/reject strategy is used).

Nonce Generator

Also used in cryptographic proofs, but, unlike Oracle, the nonce generation involves secret data, and should not be possible to reconstruct by others.

In BEAM Nonce generator is a combination of an Oracle, and the nonce function initialized by the secret data. That is, the Oracle accounts for all the visible transcript. When a nonce is needed - first it's received from the Oracle, and then passed as an input to the nonce function (implemented in (secp256k1), which also uses the secret data.

The final nonce generation function implemented in secp256k1 actually a modified HMAC-SHA-256 scheme.

KDF - Key derivation function

All the private keys are generated via KDF. In BEAM it's implemented via the Nonce generator, which is initialized once by the master secret data. The requested key parameters (key index, type/subtype, etc.) are hashed and then the output is generated by the standard Nonce generator initialized with the master secret.

Schnorr's signature

Implemented according to the standard, the "long" version, compatible with batch verification. Consists of a pair [P,k], whereas P is an arbitrary EC point, and k is the blinded private key. Supports multisignature of course.

Specifically the scheme is the following. Given a message hash M, private key sk, public key pk = G * sk:

• Prover
  • Generate a nonce nk = Nonce(sk, M), whereas Nonce() is the standard nonce generating function.
  • Calculate: P = nk*G
  • Expose to Oracle: P, M
  • Get the challenge e from Oracle.
  • Calculate k = - nk - e*sk
  • Signature: [P, k]
• Verifier
  • Expose to Oracle: P, M
  • Get the challenge e from Oracle.
  • Verify: k*G + e*Pk + P == 0

Binary platform-independent representation of the ECC primitives

The following are the primitives:

• ECC Scalar
  • 256-bits wide integer, representing the number in a big-endian format (via uintBig)
  • Deserialization ensures the number is indeed a valid scalar, i.e. strictly less than modulo-prime, to prevent ambiguity
• ECC Point
  • Represented as an X-coordinate, and a Y-parity flag (1 bit).
  • The X-coordinate is serialized via uintBig (similar to scalar).
  • To recover the Y-coordinate one must solve a quadratic equation, which, naturally has 2 solutions. This is where Y-parity flag is used.
  • When serialized individually the data is padded to a byte boundary (means the Y-parity bit takes the whole byte). However in some complex data types those flags are merged and stored separately (Ex: Bulletproofs).