1. Introduction

The purpose of this note is to provide an introduction to the Generalized Linear Model and a matricial formulation of statistical learning derived from the class of exponential distributions with dispersion parameter. We assume that the reader is comfortable with linear algebra and multivariable calculus, has an understanding of basic probability theory and is familiar with supervised learning concepts.

A number of regression and classification models commonly used in supervised learning settings turn out to be specific cases derived from the family of exponential distributions. This note is organized as follows:

  1. Section 2 describes the family of exponential distributions and their associated Generalized Linear Model. The family described in [3] counts a significant number of distributions including e.g., the univariate Gaussian, Bernoulli, Poisson, Geometric, and Multinomial cases. Other distributions such as the multivariate Gaussian lend themselves to a natural generalization of this model. In order to do so, we extend the family of exponential distributions with dispersion parameter [3] to include symmetric positive definite dispersion matrices.
  2. Section 3 derives the Generalized Linear Model Cost Function and its corresponding Gradient and Hessian all expressed in component form. We derive the expressions associated with the general case that includes a dispersion matrix. We also derive simplified versions for the specific case when the dispersion matrix is a positive scalar multiple of the identity matrix.
  3. In Section 4, we limit ourselves to distributions whose dispersion matrix is a positive scalar multiple of the identity matrix. These are precisely the ones described in [3]. We express their associated Cost Function, Gradient and Hessian using concise matrix notation. We will separately analyze the case of the multivariate Gaussian distribution and derive its associated Cost Function and Gradient in matrix form in section 7.
  4. Section 5 provides a matricial formulation of three numerical algorithms that can be used to minimize the Cost Function. They include the Batch Gradient Descent (BGD), Stochastic Gradient Descent (SGD) and Newton Raphson (NR) methods.
  5. Section 6 applies the matricial formulation to a select set of exponential distributions whose dispersion matrix is a positive scalar multiple of the identity. In particular, we consider the following:
    • Univariate Gaussian distribution (which yields linear regression).
    • Bernoulli distribution (which yields logistic regression).
    • Poisson distribution.
    • Geometric distribution.
    • Multinomial distribution (which yields softmax regression).
  6. Section 7 treats the case of the multivariate Gaussian distribution. It is an example of an exponential distribution with dispersion matrix that is not necessarily a positive scalar multiple of the identity matrix. In this case, the dispersion matrix turns out to be the precision matrix which is the inverse of the covariance matrix. We derive the corresponding Cost Function in component form and also express it using matrix notation. We then derive the Cost function’s Gradient, express it in matrix notation and show how to to minimize the Cost Function using BGD. We finally consider the specific case of a non-weighted Cost Function without regularization and derive a closed-form solution for the optimal values of its minimizing parameters.
  7. Section 8 provides a python script that implements the Generalized Linear Model Supervised Learning class using the matrix notation. We limit ourselves to cases where the dispersion matrix is a positive scalar multiple of the identity matrix. The code provided is meant for educational purposes and we recommend relying on existing and tested packages (e.g., scikit-learn) to run specific predictive models.
Read the rest of this entry »

Tags: , , , ,

Download pdf here: Bitcoin ECDSA

1. Introduction

Simply stated, a bitcoin transaction is a transfer of spending control between different parties over a pre-specified amount of satoshis. A satoshi is the smallest fraction of a bitcoin and is equivalent to BTC 10^{-8}. In order to successfuly complete said transfer, the sender must demonstrate that she is the rightful owner of the satoshis she wishes to spend. Such a proof is imperative as it allows the different nodes on the network to reach an agreement regarding the validity of the transaction and as a result, facilitate its inclusion in the blockchain.

At the time of writing, bitcoin’s proof of ownership is encapsulated in a particular type of digital signature known as the Elliptic Curve Digital Signature Algorithm (ECDSA). It is a variant of the Digital Signature Algorithm (DSA) that relies on Elliptic Curve Cryptography (ECC).

In the first section, we introduce the DSA scheme, prove its correctness, and discuss some of its security properties. In particular, we point out that as of the time of writing, and despite its prevalence in various cryptographic settings, we do not know of any valid security proof of DSA in the random oracle (RO) model. However, we highlight that slight variations of it can be proven to be secure.

In the second section, we introduce the ECDSA scheme and prove its correctness. Later on, we present a python-based implementation to further elucidate its building blocks. We also describe how an ECDSA signature gets typically encoded within a bitcoin transaction. Finally, we highlight some of the scheme’s potential shortcomings including the absence to-date of a security proof in the RO model, its susceptibility to being malleable, and its non-linear design that hinders an efficient implementation of multisignature transactions.

Read the rest of this entry »

Tags: , , , ,

Download pdf here: Blockchain fork analysis

1. Introduction

In this post we analyze two sources of divergence on the blockchain caused respectively by a natural fork and a malicious fork. The revolution that has been brought about by Bitcoin’s blockchain is a direct result of its open nature. Indeed, anyone can be part of it, suggest changes to it, mine new blocks in it, or simply conduct routine validations on it. It is in many respects, the epitome of decentralization and censorship-resistance. Its appealing nature is in large part rooted in its rich interdisciplinary foundation that spans across philosophy, mathematics and economics.

But beyond the elegance of its theoretical underpinning, the blockchain’s seamless implementation rests on an inherent agreement between its different participants. Without agreement, this harmonious apparatus would likely decay into chaos. The rather flawless operation of the system is the result of a particular consensus protocol known as Proof of Work (or PoW for short).

The consensus is meant to be amongst all of the miners on the network. It stipulates that any miner always extend the chain of blocks with the highest amount of cumulative work. In this context, work is a measure of the expected computational effort that a miner exerts in order to solve a given cryptographic challenge. In essence, the challenge consists in finding a value that makes the computation emit an output with a mandatory minimum number l of leading 0’s. The work associated with mining a given block corresponds to the value 2^{l}, where l is dynamically adjusted to ensure that the network’s average block rate remains constant at \sim 0.00167 blocks / second (i.e., 1 block per 10 minutes). We discuss PoW as well as other consensus protocols in more details in another post.

In an ideal setting where all miners are honest (i.e., abide by the PoW consensus protocol) and where blocks are propagated instantaneously on the network, all the nodes will always have a unified view of the blockchain — barring the extremely unlikely scenario of two distinct miners generating two valid blocks at the exact same time). However, imperfections do exist:

  • Imperfection #1: The network incurs an information propagation delay. As a result, every new block takes a positive amount of time to reach all the other nodes on the network.
  • Imperfection #2: There exists a subset of dishonest miners that decide to disregard the PoW consensus protocol. As a result, such miners can fork the blokchain and start mining on top of a parallel chain different than the one with the highest amount of cumulative work.

Read the rest of this entry »

Tags: , , , , ,

Download pdf here: Bitcoin Key and Addresses

1. Introduction and Bitcoin’s elliptic curve review

The objective of this post is to introduce the reader to Bitcoin’s private and public keys, and to the Bitcoin addresses used in Pay to Public Key Hash transactions (P2PKH) and Pay to Script Hash transactions (P2SH).

As was previously introduced in the Elliptic Curve Groups post, the linkage between Bitcoin’s private and public keys is determined by a specific elliptic curve known as secp256k1. Recall that the curve’s parameters are as follows:

  • p = 2^{256} - 2^{32} - 2^{9} - 2^{8 }- 2^{7} - 2^{6} - 2^{4} - 1. This a very large prime number that serves as the order of the underlying field \mathbb{F}_p.
  • The secp256k1 curve is non-singular and is represented using its short Weierstrass form. We denoted the resulting group by (E(\mathbb{F}_p), \oplus_p), where

    E(\mathbb{F}_p) = \{{(x,y) \in \mathbb{F}_p^2\ |\ y^2 \equiv x^3 + 7 \pmod{p} \}}\ \cup\ \{{\mathcal{O}\}}

    \mathcal{O} denotes the point at infinity and is the identity element of the group. Here is a euclidean representation of this curve when p = 163 (it is not feasible to show it for p = 2^{256} - 2^{32} - 2^{9} - 2^{8 }- 2^{7} - 2^{6} - 2^{4} - 1).

    Bitcoin elliptic curve

  • The base point G has abscissa and ordinate given by

    x_G \equiv 55066263022277343669578718895168534326250603453777594175500187360389116729240
    \pmod{p}

    y_G \equiv 32670510020758816978083085130507043184471273380659243275938904335757337482424
    \pmod{p}

    which in hexadecimal notation are given by:

    x_G = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

    y_G = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

    Bitcoin’s public-key cryptography is hence conducted on the subgroup (\{{G\}}, \oplus_p).

  • The order of G is chosen to be a prime number equal to

    n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
    \pmod{p}

    which in hexadecimal notation is given by

    n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

  • Recall that n denotes the order of G, and must divide \#E(\mathbb{F}_p) i.e., the order of E(\mathbb{F}_p). The cofactor h is equal to \frac{\#E(\mathbb{F}_p)}{n}, which in this case is equal to 1. That means that the order of G is equal to that of E(\mathbb{F}_p), i.e., n = \#E(\mathbb{F}_p). Since n is prime, the order of E(\mathbb{F}_p) is also prime. As a result, (E(\mathbb{F}_p), \oplus_p) is a cyclic group and any of its elements could serve as a generator.

We also saw that Bitcoin’s private and public keys obey the following architecture:

  • A private key m is a 256-bit long scalar chosen from the set

    \mathbb{F}_n^* \equiv \mathbb{F}_n - \{{0\}}.

  • A public key M is an element of the subgroup \{{G\}}. M is derived from m by adding G to itself a total of m times. Addition refers to the elliptic curve group binary operation \oplus_p. More specifically,

    M = m \otimes_p G \equiv G \oplus_p G\ ...\ \oplus_p G (m times)

    It is a 512-bit long string denoting the elliptic curve point (x,y). It is an element of the set \{{G\}} which in this case is equivalent to E(\mathbb{F}_p). Both x and y are 256-bit long.

Read the rest of this entry »

Download pdf here: Elliptic Curve Groups

1. Introduction and motivation

The sempiternel question of how to gain and maintain power has haunted the minds of humanity’s brightest and darkest since the dawn of civilization. Be it physical (e.g., military) or economical (e.g., wealth), power’s very existence relied in part on access to information. Asymmetric information that is. Numerous are history’s examples that demonstrate how entities that knew what others didn’t and that were able to act on it, benefited from an unfair advantage. The quest for sustainable power motivates the protection of one’s proprietary information and the attempt at breaching that of the others.

Although significant in its own right, the pursuit of power is not the only motivator to conceal information. Privacy, in so far as the individual’s well-being is concerned, is another. In that respect, two areas stand out. The first is concerned with the unique nature of a human persona. As a matter of observation, and at the risk of irritating adherents of monism, the attributes of a human personality are so varied. Each attribute exists on a wide spectrum, making it unlikely that any two individuals have the same profile so to speak. The privacy spectrum is no exception, and while some live their lives as an open book, others might not even be comfortable sharing their half title page. The second area is concerned with the safety of a certain subset of individuals, e.g., whistle-blowers. They may hold sensitive information destined to be shared with a specific party. Should this information fall in the wrong hands, it could jeopardize the safety of the source.

It is therefore reasonable to assume that not every piece of information is meant to be common knowledge. One could certainly debate the merits of such a claim and in the process, revisit the very foundation of power, privacy and safety. The fact remains however, that information can be a source of influence, discomfort, and danger. One way of protecting specific content and limiting its access to intended parties only, is through the use of encryption and decryption algorithms.

Read the rest of this entry »

Tags: , , , , , , ,

Download pdf here: Groups and Finite Fields

1. Introduction

Group, field and elliptic curve theories make a regular appearance in the study of crypto-assets including but not limited to cryptocurrencies. For example, the security strength of a number of crypto-specific primitives relies on the math of elliptic curve groups over finite fields. These groups constitute a robust infrastructure to generate adequate public keys from private ones.

Groups and fields are foundational pillars of modern algebra. While in elementary algebra we rely on common arithmetic operations (e.g., addition and multiplication of real numbers), in modern algebra we raise further the level of abstraction. In particular, we introduce more general counterparts to real number addition and multiplication and define them over more general sets. An important objective is to study the common properties of all sets on which a fixed number of operations are defined. These operations tend to be interrelated in some definite way (e.g., distributivity of multiplication over addition).

In this post, we provide a concise (but by no means comprehensive) introduction to group and finite-field theory at the level needed to better appreciate the mathematical foundation of crypto assets. In a subequent post we build on this material to introduce elliptic curve groups defined over finite fields. The interested reader could consult e.g., [1] for a deeper dive on the theory of finite fields and its applications.

Read the rest of this entry »

Tags: ,

Download pdf here: The Stealth Address System

1. Introduction

The previous nine parts introduced Monero’s privacy and confidentiality attributes in so far as senders’ identities and transaction amounts were concerned. This part focuses on privacy with respect to the recipients of funds. To that end, we introduce the stealth address system [8] to ensure that any two transactions remain unlinkable, i.e., can not be proven to be destined to the same entity.

We divide this part into two sections. The first is an overview of some of the anonymity limitations of Bitcoin. The second introduces Cryptonote’s stealth address system which when coupled with ringCT, ensures a highly anonymous and confidential environment.

Anonymity over the blockchain

2. On Bitcoin’s anonymity … or lack thereof

In what follows, we describe two avenues that can be used separately or jointly to conduct a deanonymization attack on Bitcoin users. The first has to do with the propagation mechanisms of Bitcoin transactions over the network, and the second with the structure of a transaction. In addition, we describe some common practices that help an attacker link a Bitcoin address to a real-world identity.

Read the rest of this entry »

Tags: , , , , , , , ,

1. Introduction

In part 7 we introduced the MLSAG ring signature scheme. Among other things, it safeguarded the anonymity of the signer. In part 8 we discussed the notions of Pedersen Commitments and Confidential Transactions. They were used to mask transaction amounts without compromising the proper bookkeeping of balances on the network. In this part, we combine the two in a new structure known as ring Confidential Transaction or ringCT.

It turns out that combining both concepts in a single mathematical construct requires additional work. In the first section, we explain why outright combination of the aforementioned concepts fails to preserve the anonymity of the sender.

In the second section we remedy the situation by introducing the notion of a non-zero commitment. This will form the basis of Monero’s ringCT scheme.

The last section goes over the mechanics of how a Monero transaction is created and includes references to relevant parts of the code base. We introduce two variants of ringCT, namely ringCT Type Full and ringCT Type Simple. We finally conclude with a breakdown of the components of a real-life Monero transaction.

Read the rest of this entry »

Tags: , , , , , ,

Download pdf here: CT and Pedersen Commitment

1. Introduction

Pedersen Commitments are at the heart of how Monero conceals transaction amounts. The notion of a confidential transaction as enabled by Pedersen Commitments were outlined and defined by Gregory Maxwell in [1]. In what follows we first introduce the notion of a group homomorphism (of which the Pedersen Commitment map is a particular instance), we then define the Pedersen Commitment map, and finally present the mechanisms of a confidential transaction enabled by a such a map.

2. Group homomorphism

Let (M, \boxplus) and (N, \oplus) be 2 groups with respective group operations \boxplus and \oplus. A function f: M \rightarrow N is called a group homomorphism if and only if

f(u \boxplus v) = f(u) \oplus f(v),\ \forall u, v \in M

In other terms, operating on 2 elements in M and then applying f is equivalent to applying f on each element separately and then operating on the 2 outputs in N.

We now introduce a specific instance of a group homomorphism that we will invoke when concealing transaction amounts with Monero as part of the confidential transaction construct. In particular, we conduct arithmetic in the subgroup \{{G\}} of the elliptic curve group E. introduced in part 5 (refer to the post entitled Elliptic Curve Groups for an introduction to this topic)

Let (N, \oplus) \equiv (\{{G\}}, \oplus), and let (M, \boxplus) \equiv (\mathbb{F}_l \times \mathbb{F}_l, +) where + denotes element-wise addition in modulo l arithmetic over \mathbb{F}_l \times \mathbb{F}_l.

It is a known result in group theory that if a is a generator of a cyclic group \{{a\}} of order m, then there are \phi(m) elements of the group that have order m (\phi is the euler function introduced in part 1). In our case, the generator G of \{{G\}} has prime order l. Moreover \phi(l) = l-1 (since l is prime). Hence we can find l-1 other generators of \{{G\}}. Let H \neq G be another generator such that the DL (discrete logarithm) of H with respect to G is unknown. We define the Pedersen Commitment map (which we will later use to build a confidential transaction) as follows:

k: \mathbb{F}_l \times \mathbb{F}_l \rightarrow \{{G\}}

(x,a) \rightarrow k(x,a) \equiv (x \otimes G) \oplus (a \otimes H)

We claim that the map k is additively homomorphic. To see why, let (x_1,a_1),\ (x_2,a_2)\ \in \mathbb{F}_l \times \mathbb{F}_l. We then have:

k(x_1,a_1) \oplus k(x_2,a_2) = [(x_1 \otimes G) \oplus (a_1 \otimes H)] \oplus [(x_2 \otimes G) \oplus (a_2 \otimes H)]

= ((x_1 + x_2) \otimes G)) \oplus ((a_1 + a_2) \otimes H))
(where + denotes \pmod{l} over \mathbb{F}_l)

=k((x_1+x_2),(a_1+a_2))\ =\ k((x_1,a_1) + (x_2,a_2))

hence k is homomorphic.

Read the rest of this entry »

Tags: , , ,

Download pdf here: MLSAG Signature Scheme

1. Introduction

Monero stands out from other cryptocurrencies in its ability to hide the signer, conceal the transaction amount, and protect the identity of the recepient. Parts 1, 2, 3, 4, 5, and 6 helped us build the foundation to better understand and appreciate the security properties of ring signatures (albeit in the RO model). This part (introduction to MLSAG), as well as part 8 and part 9 will focus on Monero’s privacy in so far as the signer’s identity and the transaction amount are concerned. Part 10 will introduce stealth addresses as a mechanism to protect the identity of the fund’s recipient.

In order to describe how a Monero transaction hides both the signer’s identity and the amount of the transaction, we introduce 2 additional concepts:

  1. A generalization of the LSAG signature (introduced in part 6) to allow each member of the ring to have a key-pair vector [(pk_1,sk_1),.,(pk_n,sk_n)] instead of only one pair (pk,sk).
  2. A particular map known as the Pedersen Commitment that will be used to hide transaction amounts while allowing the network to check that input and output amounts always balance out.

Recall that by proving that a digital signature scheme was unforgeable, one gets the assurance that only the signing algorithm {\Sigma} associated with a given ring member can produce a valid signature (i.e., verified by \mathcal{V}). Any other procedure that bypasses {\Sigma} will result in a failed attempt of forgery with overwhelming probability. We note the following about the verification process of \mathcal{V}:

  • In a “non-ring” setting, the verification is done using a particular public key pk_{\pi}. The validation of a given signature proves that the signer of the message (in this case user \pi) knows the secret key sk_{\pi} associated with pk_{\pi}. Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair (pk_{\pi},sk_{\pi}) signed the message.
  • In a ring setting, the verification is conducted using a public key vector L \equiv [pk_1,...,pk_{\pi},...,pk_n] known as a ring. This vector is used to conceal the identity of the signer. The validation of a given signature proves that the the signer of the message (in this case user \pi) knows the secret key associated with one of the public keys in L. Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair (pk_{\pi},sk_{\pi}) signed the message, for some index 1 \leq \pi \leq n that no one other then the actual signer knows.
  • The ring setting can be generalized further by allowing each ring member i, 1 \leq i \leq n to have a key-pair vector of length m, given by [(pk_{i}^1, sk_{i}^1),...,(pk_{i}^m, sk_{i}^m)], as opposed to a unique key pair (pk_i, sk_i). In this setting, the verification is conducted using a public key matrix

        \[PK= \begin{bmatrix} pk_1^1 & ... & pk_{\pi}^1 & ... & pk_n^1 \\ ... & ... & ... & ... & ...\\ pk_1^m & ... & pk_{\pi}^m & ... & pk_n^m \\ \end{bmatrix} \]

    The validation of the signature proves that the signer knows the secret key associated with each one of its public keys. In other terms, there exists a column in PK (say column 1 \leq \pi \leq n) such that the signer knows the secret key associated with each public key appearing in that column. Assuming that secret keys are safe-guarded and non-compromised, this actually proves that the user with key-pair vector [(pk_{\pi}^1,sk_{\pi}^1),...,(pk_{\pi}^m,sk_{\pi}^m)] signed the message, for some index 1 \leq \pi \leq n (that no one other then the actual signer knows).

Read the rest of this entry »

Tags: , , , , ,

« Older entries