Understanding Blind Signatures by Ethan Heilman

Introduction

Blind Signatures are a signature scheme which allows one party to sign a message without learning the message they signed.

History – Invented by David Chaum in 1982 for an early centralized digital currency called anonymous ecash.

This was an anonymous ecash that enabled a trusted party (like a bank) to issue and redeem coins without learning to whom these coins were spent.

How Non-Anonymous Ecash Works

How non-anonymous ecash works

How Anonymous Ecash Works

  1. Alice chooses a random serial number SN
  2. Alice blinds SN with a random number r (*)
    bSN = Blind(r, SN)
  3. Signer signs bSN to generate a blind signaure
    bσ = sign(SK, bSN)
  4. Alice unblinds the blind signature to a signature on SN
    σ = unblind(r, bσ)
how blind signature work in ecash
anonymous ecash example with bank, ecash, etc.

Blind Signatures – Unlinkability

Unlinkability – Any bSN (blinded serial number) can be unblinded to any other SN (serial number). Thus a bSN can not be linked to any SN.

This is only a description of RSA blind signatures, however there are many more blind signature schemes.

RSA Signatures

PK = (e,N)
SK = (d,N)
RSA(PK, x) = x^e(mod N)
RSA-1(SK, y) = y^d(mod N)

RSA-1 and RSA are inverses of each other:

RSA-1(SK, RSA(PK, x)) = ((x^e)^d) (mod N) = x

Signing

RSA-1(SK, Hash(m)) = Hash(m)^d (mod N) = σ

Verification

RSA(PK, σ) = σ^e (mod N) = (Hash(m)^d)^e (mod N) = Hash(m) (mod N)

Hidden RSA Signature

I’m so tired of typing these equations. Here’s a screenshot.

RSA blind signatures

Understanding Cryptography for Bitcoin by John Newberry

The following is a lecture by John Newberry. Essentially, it’s a lecture that describes the proofs and mathematics underpinning the calculations for private keys and public keys. I’ve followed along and wrote down everything that has been said here, in order to get a better grasp on elliptic curves, finite fields, etc.

Transaction example from Bitcoin Whitepaper

A transaction consists of:

  • one or more txins, which contain:
    • a reference to the txout that is being spent
    • a digital signature proving that the owner of the private key authorized the transaction
  • one or more txouts, which contain:
    • the amount
    • the public key of the recipient

Verifying A Transaction

Bitcoin nodes do the following to verify each transaction:

  • Check that each txin, corresponds with an unspent txout.
  • Checks that the total amount in the txouts, does not exceed the total amount from the txins.
  • Check that each txin contains a valid signautre for the public key from the txout referenced.

Digital Signature

Digital Signatures are used to transfer ownership of coins.

A digital signature proves that the owner of the coin authorised the transfer:

  • only someone with the private key can sign the transaction (authentication)
  • no-one can change the transaction after it has been signed (integrity

What is a digital signature?

Digital signatures make use of asymmetric cryptography.

The user has a public key (which is published and known), and a corresponding private key.

Only someone with this private key can create a valid signature over a message. Anyone with the public key and the message, can confirm that the signature is valid.

Digital Signatures and Bitcoin

Bitcoin uses ECDSA over secp256k1, however a better signature algorithm is the Schnorr signature algorithm, as ECDSA is a bit of a hack to get around the patent reserving the Schorr signature.

ECDSA is an application of the discrete log problem, essentially meaning it is easy to multiply in this system, but much more difficult to divide.

Discrete logs are defined for cyclic groups with a generator G. The problem is defined as:

for a given H in the group, what is the scalar X, such that XG=H

Bitcoin uses the group of points on the elliptic curve secp256k1 defined over a finite field.

Finite Fields

Group

Defined as a set of objects along with a binary operator +.
The binary operator has the following settings.

  • Closure
    If you add two elements together, they are still an element within the group.
  • Identity
    Adding 0 to X, results in X
  • Inverse
    If you have a number X within a group, you also have the inverse, and when adding these two elements together, it returns 0.
  • Associativity
    (a + b) + c = a + (b + c)
  • Communicativity
    a + b = b + a

Cyclic Group

A group is considered cyclic, if there is a generator element:

a = g +g + g … (n times)

This I really didn’t understand, and the more I rewatched this part, the more I got confused. The following Youtube video explained the nature of cyclic groups and helped me understand a lot more about what we’re dealing with here.

Additionally, some of the notation in this video is explained, and it makes sense of the notation in the original lecture.

Field

A field is a commutative group with a secondary binary operator X.

The second binary operator is also closed, has an identity (1), has inverses (except for 0), is associative and commutative.

The binary operators are also distributive:

a x (b + c) = (a x b) + c

We can add, subtract, multiply, and divide over a field.

Example Fields

The real numbers are thought of as an infinite field.

The rational numbers, with addition and multiplication defined as normal, is an infinite field.

Integers from 0 to (n – 1), with addition and multiplication defined modulo n is a finite field.

Fp = {0,1,2,3,4,....,p-1}
F13 = {0,1,2,3,4,...,12}
4 + 5 = 9
8 + 9 = 4, (17 % 13 = 4)
4 - 8

Elliptic Curves

An elliptic curve is a curve of the form:

y2 = x3 + ax + b

In Bitcoin, we use the secp256k1 curve

y2 = x3 + 7

Instead of defining secp256k1 over all reals, we define it over a finite field of integers mod p.

Defining a Group Operation for the Elliptic Curve

To add two points:

  • Take the line meeting the two points
  • Find where the line intersects the curve again
  • Reflect through the x axis

To double a point:

  • Take the tangent at that point
  • Find where the tangent meets the curve again
  • Reflect through the X axis

A point’s inverse is the reflection in the X axis.

Adding a point to its inverse, yields our group identity: the point a infinity.

Adding the point at infinity to any point P, yields P.

Generating a Cyclic Group

  • Take any point G on the curve.
  • Repeatedly add it to itseflf until you reach G again.
  • The set of points generated is a cyclic group.
The generator point for secp256k1
The generator point for secp256k1

Discrete Log Problem For An Elliptic Curve

The private key, x, is scalar, 256 bit number in the range, [0, .., n-1], where n is the order of the group.

The public key is a point P on the curve where:

P = xG

It is easy to go from x to P.

It is computationally difficult to go from P to x.

This essentially means, it is easy to generate a public key from a private key, but much more difficult to generate a private key from a public key, because division in finite fields is difficult. This is how we know that our public and private keys are secure.

Schnorr Signatures

Schnorr Identification Protocol

A prover can prove to a verifier that she knows the private key x corresponding to a public key P without revealing x.

The verified learns nothing about x from the proof (except the fact that the prover knows x).

This is called a proof in zero knowledge.

Zero-Knowledge Proof

A zero-knowledge proof requires three properties:

  • Completeness – the proof convinces the verifier
  • Zero-knowledgeness – the proof doesn’t leak information
  • Soundness – a proof can only be produced by a prover who knows the private key

Schnorr Identification Protocol Steps

  1. Commitment – The prover picks a nonce scalar k and commits to it by sending K = kG to the verifier.
  2. Challenge – The verifier sends a challenge scalar e
  3. Response – The prover sends the response scalar:
    s = k + ex

The verified is convinced that the prover knows x if the identity holds:

sG = kG + exG
= K + eP

The transcript of the 3 step protocol is: (K, e, s)

If you can produce a proof, for any challenge e, then you must know x.

If verifier has:

s1 = k + e1x
and
s2 = k + e2x

They can now calculate:
x = s1 - s2 / e1 - e2

Non-Interactive Schorr Identification Protocol

The verifier’s only role was to provide a “random” challenge.

If we can replace the verifier with a random oracle that simply provides a random number after the commitment step, then we don’t need a verifier.

We treat a hash function as a random oracle.

“After” is key here. It means that the prover cannot know the output to a hash function before evaluating it.

This is called a Fiat-Shamir transform.

This has 3 steps:

  1. The prover picks a nonce scalar k
  2. The prover calculates e=H(kG)
  3. The prover computes the scalar s = k + ex

The proof is (s,e)

Anyone can verify by checking:

sG = kG + exG

Signature of A Message

Since H is a random oracle and returns different values for different inputs, the prover can add extra inputs to H.

The result is a signature of knowledge over a mesage.

The prover can set:

e = H(m||kg)

The prover calculates s in the normal way:

s = k + ex

The verifier then checks that:

sG = kG + exG
and
e = H(m||kg)

ECDSA

We use ECDSA with Bitcoin because Schnorr signatures were encumbered by a patent.

Few disadvantages compared to Schnorr:

  • Signatures are not linear (makes threshold and adaptor signatures much more difficult)
  • There is no security proof for ECDSA
  • ECDSA signatures are malleable.

ECDSA Signing

The prover signs a message m as follows:

  1. Set z as the leftmost bits of H(m)
  2. Pick a random nonce scalar k
  3. Set K = kG and r as the x coordinate of K
  4. Set s = k-1(z + rx)

The signature is the pair (r,s)

Verification of ECDSA

The signatures are verfiied as follows:

  1. Set z as the leftmost bits of H()m
  2. Set u = z/s and v = r/s
  3. If the x coordinate of uG + vP is equal to r, then the signature is valid.

More Reading

Borromean Ring Signatures

Confidential Transactions and Bulletproofs

Zero-knowledge proofs

Schorr Signatures

The Incentives of Bitcoin Miners

I came across this interesting question on Bitcoin Stack Exchange.

What happens to the bitcoin network when the miners all stop in the future?
What happens to the bitcoin network when the miners all stop, years in the future after all the bitcoins have been mined? How will the network continue to function? Won’t bitcoins then be useless? What would be the incentive for an individual to continue using computational power to service all the transactions? Isn’t this like a ticking time bomb or is there something I’m not getting?

Demioprax

If I were to rephrase this question, it would be something like this, “What incentives do Bitcoin miners have to keep mining?”

I thought this might be an interesting question to tackle, especially since we just had a halvening today! So let’s dive into it.

Why do Bitcoin Miners mine?

Bitcoin miners earn money, every time they guess a correct answer to a problem.

As more people participate in guessing, the problem gets harder and harder.

If you get a correct answer, you win money. Currently that reward is 6.25 bitcoin. This is why Bitcoin miners mine. To get Bitcoin.

What happens in the future?

As time goes on, the amount of Bitcoin will approach 21 million. When we hit 21 million, there will not be a reward for the miners. Now, if there is no reward for the miners, why would they mine? I don’t work for free. You probably don’t either! The miners probably would feel the same way.

The good news is that Satoshi already thought of this problem. We can pay for miners to accept our transactions, think of it as a tip. So if I send 1 BTC, I’ll add a tip (known as a fee) so it can get accepted by a miner.

A Bitcoin block contains on average around 1600 transactions. With 1600 tips, the miners can replace their previous reward, with tip rewards.

What are the incentives?

To make it very simple and to directly answer our question we asked earlier (remember? We asked, “What incentives do Bitcoin miners have to keep mining?”).

The incentives are simple: Bitcoin miners are motivated by Bitcoin. As the reward rate of Bitcoin goes down, the fees (tips we send on every transaction) go up, replacing the income lost.

Also, as long as Bitcoin maintains and raises in value, it could be considered very valuable to mine. Even if the reward is very little (6.25btc vs the original reward, 50 btc), the 6.25 btc earned now is worth much more than the 50 btc were worth at the time of earning.

Conclusion

Bitcoin miners are incentivized by money. They currently earn money through rewards, and a little bit through fees. In the future they can earn all their money through fees. Also, the price of Bitcoin is very important to the miners, because if the price was $0.00, they couldn’t make very much money from mining the bitcoin.

Bitcoin Project #1: Testnet Wallet

So, I will be the first to admit that in this journey of learning about Bitcoin, I have sorta been all over the place. Going from reading books, to reading documentation, to reading articles, to trying to hack something together, to failing, to reading, back to hacking, back to failing, on and on.

This time, I am setting an actual project for myself though. I am going to build a testnet wallet from scratch.

This will be a seriously difficult exercise for me. I am aware. I am giving myself until the end of January to build a BAD bitcoin testnet wallet.

The specifications are as follows:

  • Generate and store private key
  • Generate and store addresses
  • Delete addresses on user request
  • Delete private keys on user request
  • Send transactions to other addresses
  • Initial block download
  • Restore from Mneonmic
  • Labels and user management

For me, this is a massive undertaking. All I know right now, is how to generate addresses.

I figure, if I can hack this together in a month + 9 days, I can be considered a bad bitcoin developer. If I can be considered any sort of a Bitcoin developer, that is a WIN in my book.

I will try and report daily progress. I won’t make daily progress, but I definitely will make an effort.

This next week is critical for me since it is Christmas week, and I took the entire week off, so I can spend extra time to read, study, learn and build.

Let’s go!

Bitcoin Prep Work: Preventing Softforks


What I Am Reading:

Can soft-forks be prevented? and linked within – a discussion to the mailing list.

Notes

At first, I really didn’t get this at all. I read that it was impossible, but I didn’t understand how.

As I read the mailing list, I got progressively more confused. I really didn’t understand what was being talked about – isStandard, Anyone-can-spend scripts, etc.

But finally, I came across the quote below, and it illuminated it all for me very well.

Since a soft-fork is a restriction of the consensus rules, I think the only way to have an un-soft-forkable cryptocurrency is creating a cryptocurrency where no transaction is valid.

Imagine I build a very minimal cryptocurrency where in the transaction output you only indicate the public key to send your coins to and the amount. One can still soft-fork it by deciding that, from now on, only even amounts are valid or only public keys that are a multiple of 10 are valid.

After I read this I understood the context of all the other elements they were discussing on the mailing list.

Bitcoin Prep Work: Introduction to Bitcoin Blockchain

What I Watched:

SF Bitcoin Devs Seminar: A Special Presentation By Matt Corallo of Blockstream

Link to slides.

Notes

Bitcoin is mostly focused on preventing double-spends using proof-of-work.

Proof-of-work is based off of Hashcash.

Hashcash is a poisson process.

A Bitcoin without block reward would end up as a disincentive miners to act honestly.

Confirmations: 51% hashpower isn’t necessary for a short-term attack.

Writing consensus code is interestingly difficult.

The coding to consensus slide was probably the most interesting part of the talk, at least to me.

Conclusion

Great talk – I learned a lot about forking, and the Bad Ideas section was very enlightening.

The thing I really took away from this talk was: Bitcoin is a fragile system, but has a GREAT incentive structure, that takes weaknesses (eg. miners could try and double-spend) into strengths (if they double-spend, it destroys the use case).

Bitcoin Prep Work: Bitcoin’s Academic Pedigree

What I Read

I read Bitcoin’s Academic Pedigree.

Notes

Was very interesting to trace Bitcoin back to its original ideas. This paper was not very technical, but was rather a sort of technical recap. Any advanced topics were spelled out quite easily, even something seemingly complicated like Blockchain is described in very simple language.

This is definitely a paper that I will refer back on in the future. There is just so much history, I am sure I missed something.

The most interesting thing I learned was about hashcash. I didn’t realize that the solving of the puzzle itself, was the cash, in this protocol. It was cool seeing how Bitcoin was adopted to include proof-of-work, and the coinage/cash element was a complete separate part of this element.

Also, reading about Blockchains as a separate entity, with the paper evaluating the usage of a Blockchain among a consortium of banks, as the small number of parties would not need Nakamoto consensus.

Bitcoin Prep Work: If I’d Known What We Were Starting

What I Read

In this version of Bitcoin Prep Work, I read Ray Dillinger’s: If I’d Known What We Were Starting.

Notes

I’ve read this before, recently actually. It was great to re-read it. You can sense the admiration Ray has for Satoshi. He brings out, in great lengths, the characteristics of Satoshi and how it hasn’t been replicated since.

The un-scammy nature of Satoshi should have set a standard for the entire space, but many people ended up seeing Bitcoin & Blockchain as a get rich quick scheme, and still do.

It’s really exciting to read something through the lens of someone who has been in the Bitcoin space since the beginning. It gave me an interesting perspective on Satoshi, but it seems like Ray is a bit regretful of the whole experience, because of the abuse, but understands that it is a function of human nature.

Bitcoin Prep Work: Whitepaper

What I Read

I read the Bitcoin whitepaper. It has been a long time since I’ve read the Bitcoin whitepaper, and this time I actually understood it! I should have re-read it a while ago.

Notes

Definition of A Bitcoin

A bitcoin is defined as a chain of digital signatures. Specifically, you sign the previous hash and the public key of the next owner. When the next owner receives this coin, he can verify the signatures in order to know that the chain of ownership is valid.

Merkle Tree in Bitcoin

You can hash all the transactions, and come up with a root. This root is then used in the service string, which is used to generate the proof of work.

If we change any elements of the transactions, it will invalidate the root. This will further invalidate elements down the chain, specifically the previousBlockHash header that we generate for every block. So, you will have to recalculate the given block hash header, include it in the next block, and then recalculate the next header, since we use the previousBlockHash within every block.

You can see where this will be very time-consuming and not worthwhile to pursue, given the costs of proof of work.

Calculations

I didn’t understand the math behind the calculations, but I found this great article that broke down, in very simple terms, what this section meant.

Essentially, we are calculating the probability of an attacker to to alter the blockchain. The more hashpower he has, the easier it will be.

We can calculate, given an attacker chain and honest chain, how difficult it will be to overtake our chain. To quote the article,

“These numbers tell us the that the more CPU power an attacker has (q) the more confirmations we have to wait (5, 8, …) to know that the probability of the attacker catching up with the chain will be < 0.1%.”

Bitcoin white paper explained (PART 3/3)

This helped make it very clear to me what we were calculating in this section.

Conclusion

It was very beneficial to re-read the Bitcoin whitepaper. I felt like I learned a lot, and that I missed a lot by not reading it earlier.

I am a bit more technical now, so it definitely would have been more beneficial to tackle this sooner rather than later, but at any rate, I enjoyed how simple and straightforward this paper was.

Even the stuff I struggled with, I found simple explanations online about, that I could easily understand.

Building Bitcoin: Testnet Compatibility and Failing

Since the last post, I’ve done close to nothing. My main focus has been trying to make this half-done thing into a testnet ready environment.

My first focus is trying to get these addresses to be testnet compatible. That has NOT gone as well as I anticipated. I’m screwing something up, but I have no idea what.

The problem with this project is that once I get started on it, it’s hard to spend any other time on anything else throughout the day. This is difficult to do, especially with work deadlines.

At any rate – hopefully tomorrow brings us a much more optimistic update.