Let's implement a cryptocurrency

#bitcoin #go #p2p

Let’s implement bitcoin in Go. We’ll first take a look at the bitcoin whitepaper.

The whitepaper

It’s funny how blockchain is never mentioned. The paper only debate “Timestamp server with signed hash linking blocks”.Did the term was actually coined (got it ?) at the time ? Anyway,

Proof-of-work

To generate a Proof-of-work, we need to find a hash with n zeroes prefix. This is done by modifying the nonce field randomly and regenerating the hash.

Node responsabilities

  1. Listen to broadcasted blocks
  2. Listen to broadcasted transactions
  3. Try to sign a new block until done or new block is received
  4. Works on first received chain but keeps all other in case it becomes longer

Implementation

  1. Generate public/private key
  2. Connect to network, retrieve block chain and validate it.
  3. Listen to transactions and build block
  4. Try to sign new block with proof-of-work

Block

  • header
  • nonce
  • transactions root

Transactions are hashed in a Merkle tree with only the root included in the block’s hash.

Transactions

Transactions can have multiple input, and at most two outputs: one for the payment, and one returning the change if any back to sender.

Crypto money theorical validity

Attack on a crypto money is akin to a binomial random walk. So the attacker potential progress is a Poisson random variable.

The bigger the network, the longer the chain, the (exponentially) better it is. Cool.

Actual implementation

OK so, we’ve seen that bitcoin is an electronic cash system based on

  • a recursively signed chain of transaction blocks
  • an NP-hard problem
  • a P2P network

Let’s write a block

First, we need a Block. The block contains:

  • A Header with
    • the previous block’s hash
    • a nonce
    • the root hash of the transactions’s Merkle tree
  • The transaction’s hash Merkle tree

We can verify the validity of the chain only using block headers.

Let’s go with a simple implementation:

type Header struct {
	Prev  [sha256.Size]byte
	Nonce [sha256.Size]byte
	Root  [sha256.Size]byte
}

type Block struct {
	header Header
}

Now we need to hash this block:

func (b Block) Encode() ([]byte, error) {
	var buf bytes.Buffer

	err := binary.Write(&buf, binary.LittleEndian, b)
	if err != nil {
		return nil, err
	}

	return buf.Bytes(), nil
}

func (b Block) Hash() ([sha256.Size]byte, error) {

	bin, err := b.Encode()
	if err != nil {
		return sha256.Sum256(nil), err
	}

	return sha256.Sum256(bin), nil
}

Let’s write a Blockchain

Now that we have a Block that we can hash, we can have any chain and check its validity:

func TestValidate(t *testing.T) {

	bc := NewBlockchain()

	ok := Validate(bc)
	if !ok {
		t.Fatalf("expected empty blockchain to be valid")
	}

	b := &block.Block{
		Header: block.Header{
			Prev:  [sha256.Size]byte{},
			Nonce: [sha256.Size]byte{26, 40, 18, 41, 246, 84, 101, 88, 229, 243, 242, 66, 210, 31, 237, 17, 78, 78, 6, 29, 111, 30, 182, 10, 187, 101, 182, 53, 188, 21, 217, 201},
			Root:  [sha256.Size]byte{26, 40, 18, 41, 246, 84, 101, 88, 229, 243, 242, 66, 210, 31, 237, 17, 78, 78, 6, 29, 111, 30, 182, 10, 187, 101, 182, 53, 188, 21, 217, 201},
		},
	}
	bc.Append(b)

	ok = Validate(bc)
	if !ok {
		t.Fatalf("expected 1 block blockchain to be valid")
	}

	prev, err := b.Hash()
	if err != nil {
		t.Fatalf("cannot hash block: %s", err)
	}

	b = &block.Block{
		Header: block.Header{
			Prev:  prev,
			Nonce: [sha256.Size]byte{26, 40, 18, 41, 246, 84, 101, 88, 229, 243, 242, 66, 210, 31, 237, 17, 78, 78, 6, 29, 111, 30, 182, 10, 187, 101, 182, 53, 188, 21, 217, 201},
			Root:  [sha256.Size]byte{26, 40, 18, 41, 246, 84, 101, 88, 229, 243, 242, 66, 210, 31, 237, 17, 78, 78, 6, 29, 111, 30, 182, 10, 187, 101, 182, 53, 188, 21, 217, 201},
		},
	}
	bc.Append(b)
	ok = Validate(bc)
	if !ok {
		t.Fatalf("expected 2 block blockchain to be valid")
	}

	bc.Append(b)
	ok = Validate(bc)
	if ok {
		t.Fatalf("expected invalid previous block")
	}
}

First block is always valid, subsequent blocks are valid only if Header.Prev is equal to the previous block’s hash.

Let’s write an NP-hard problem

As we can see in the test output, we have a valid chain with:

dcd381637bd02a30da82c1264ffd7de62d3216a680419406c9299c35492bac10
222ef267bae092ad8e8056faf60d8152b234d2a00f3962e15344fd0390c7bf7e

It’s time to introduce the proof-of-work requirement, and use the Nonce field. We want the first n bits to be zeroes. The whitepaper specify that the proof-of-work to be a moving average of number of blocks per hour. Let’s ignore that for now and set a constant.

const (
	ProofOfWorkDifficulty int = 9
)

func Validate(b *Block) (bool, error) {
	h, err := b.Hash()
	if err != nil {
		return false, err
	}

	var c int
	for _, byt := range h {
		i := bits.LeadingZeros8(byt)
		c += i
		if i != 8 {
			break
		}
	}

	fmt.Printf("%x ---> c=%d\n", h, c)
	if c < ProofOfWorkDifficulty {
		return false, nil
	}

	return true, nil
}

func GenerateValideHash(b *Block) error {
	buf := make([]byte, 512)

	for {
		_, err := rand.Read(buf)
		if err != nil {
			return err
		}
		b.Header.Nonce = sha256.Sum256(buf)
		ok, err := Validate(b)
		if err != nil {
			return err
		}
		if ok {
			return nil
		}
	}
}

Now we can write a test for both:

func TestValidity(t *testing.T) {
	b := &Block{}
	b.Header.Prev = _testHash()
	b.Header.Nonce = _testHash()
	b.Header.Root = _testHash()

	ok, err := Validate(b)
	if err != nil {
		t.Fatalf("unexpected error validating block: %s", err)
	}
	if ok {
		t.Fatalf("expected invalid proof of work")
	}

	err = GenerateValideHash(b)
	if err != nil {
		t.Fatalf("unexpected error generating proof of work")
	}

	ok, err = Validate(b)
	if err != nil {
		t.Fatalf("unexpected error validating block: %s", err)
	}
	if !ok {
		t.Fatalf("expected valid proof of work")
	}

}

Looks like it works !

=== RUN   TestValidity
1a281229f6546558e5f3f242d21fed114e4e061d6f1eb60abb65b635bc15d9c9 ---> c=3
8579f5c8321f5c0a4360f4bfa61574a0c3082c97110eac176e440b11836da0bd ---> c=0
f0afaa2abf43b355a4347ed7754953d876b4b4295ab13271de7e828fae06c45d ---> c=0
b905314589ed4b2d3ed5c5be015871545638caaed7d1e79209e9355ecb5e3830 ---> c=0
67ee0dc837e0b0c17abb787ee4cf82b8edb4b79619376e8cfd73cd924421752a ---> c=1
4ef6b8dcbc9cee3fc16bbeeb9092c93f98a5cd3b2f5efddeb80f8dc9f69d5e38 ---> c=1
488bac0110d9b59b4bb04e137973ee9ddfbdc3c9a05c5d03741b68a4283116f1 ---> c=1
037c23e3a7ff3277dfb86bf1556bff17505e3b0a336dc9538f05a202616e4f40 ---> c=6
07bb80ab8f3ab965a76b8b03ad80b7fb4974ada2ede47565d507691235244aa7 ---> c=5
9c0f4d021ffa1f4e70fbcee8a9e9e8376982189e61fff943a6fd9bb389739d89 ---> c=0
474afea048e3a05cd2b14369b41c36bf9a2d829767fbe26d0c2f15219b3443eb ---> c=1
1a58866610c1890efef373a8f6cf1b0c1d995f71c938fa160bfdfff18bceb32f ---> c=3
65bf06d7c5cfda4c79dab576668be5fba2ca730f667fc646bc30e9c46119b49f ---> c=1
94337954c2fa8854397ae6f32e30d45c83c71721ce3db5cb853fde369bada532 ---> c=0
5a526c26d573df1613d272ff9584c0c8827601bdd3bd6c5be3ba145abb8a550c ---> c=1
b03a9ca341765cc67c356e578e4073deecf3b99fc4f08f7859060a068dcebbce ---> c=0
8dcfd22a19ce82a5e716708f42054f083118c194303c580ea45662eee223b7c3 ---> c=0
cce9b68027640dcd19477543dfc0a503066500ba80e008611405973183d9eb98 ---> c=0
40bcbbc083140375e0102ca1beb60d68aef7d068308e59cda12a77d3df376c67 ---> c=1
2c23ff0fbade52752dc716a9baff8ef4fe2e790ccfcd054d59ee17b64c1f2336 ---> c=2
717cb78bb041db8de292d704cf65c74fb038bc65fee45ac40b073fb00c435eeb ---> c=1
d00b2ba98043995c1e35cb89ea1e47a6b9171c56438debc0b1e9cf783f81e75b ---> c=0
a14baa86dbfba827cdbf25b24c702a1af54ca07ad9497380f65e2f9713f333c1 ---> c=0
d3c0c1103766d965b5e19c7f790fab62ddff6d88e119974f04f17b3c420abcb1 ---> c=0
898927e462f50c89f804c129b68a73c90e4a2490835dfd480cd52229875cbb9f ---> c=0
d9918bae3afc59bb84ab3d98ec529be96b3e0691b30c6542d684fa13fc85774e ---> c=0
7835b233def4e6cd74ed636698fe61c9e93fe874786c33dcc05a2ffd397c8260 ---> c=1
29eff18ad71940d6bb3ed324d834ce07d29e8c2d471c33ac6b3cb9dff09bbe67 ---> c=2
7f0e97a8af728e27974902703b1dfd8412255c14ac78afaf72cef5dc52340a7b ---> c=1
a7b5d830073a62c74a4c9a9ad143f0009f69e91b3f7a2b168e2a61492f8fdac7 ---> c=0
b1589944ee336ddd2e0e00de76917bcff65fd3260277365de181fa495fa0094d ---> c=0
dc4b69078d987c7abd101708c0c01a060f2a79561d76190c850ac5790081ef56 ---> c=0
e5ebb78ccb337da06f5d894eea5442db6080650518a9ec37e4fc4d8cf1274a25 ---> c=0
75ae82e3cc3e262f8679aa3806af94a58f804493f972447d8c1aa5d33da569fb ---> c=1
d1d135082a4ff829ab4e561be09af5ce05659e3902da941335860ec84b61bc27 ---> c=0
0ac0a7f83cb2c53a135d49693e4f5ed8e7157859c9dcd65896816355dc98a18e ---> c=4
cbe889823a5251920b561bfd19876d39ac1e9c360da5a414c761935663284ca0 ---> c=0
5d5a25403d333e65f456d0c3d15209a12d2773fee65f94f0c0e2895250e76b28 ---> c=1
dd9557e75e4a1120a538945b630e8325947459ef703d6d115f79902948e737de ---> c=0
fe2dff562eb0023fcee1d4a01c074f38531a3387048984bef6e36dbca64b656f ---> c=0
46439af8cb62780b004102ca3e5713ec899f943697971263280e4f5ebbff64e9 ---> c=1
b813378d14a50390b0726a29e61bdf54c5e2c276c63778118099bfeb88f6c4f5 ---> c=0
39e7dff6f950c321d2386ff1bb4374b71e5ed97b4b3d5a4fc44090f876d4952f ---> c=2
993643d263c1c0ea5d50eb04461fe4b7a66e84823b1d2067d65ed7c4a4ca35bf ---> c=0
93fca5636954c11475f4c3f933ffa54c681d8b8b1a54a679cd06b01b8be0bc6b ---> c=0
4b403b75a561ddcbec41454dcced8f1b703998df0b8d906136187d426dff092a ---> c=1
8962be3c068c58369bbda3d1ea6f1919a6622e7f7da8feb18fe989db894038e8 ---> c=0
6748dc6199f79374216bf96125157979bd5a2e977a016c6b15f2df889fcf45b8 ---> c=1
8c7f3faf089d9418ea53d4b8c11fa0bc873eb2a59f144e68c4beae2ba7132bcd ---> c=0
5e6e5d7179e1361e2058ce4638d4077c66b5ce47ab9589034bbc4b6da2889fc4 ---> c=1
7e37307075c527915d364a53e023a778aef1720d6e88e8cf467ae1129d8d44ba ---> c=1
217f7fb9be0620ecd9d214e3409c05f8a882374fabd0642553275ad4bfa500bc ---> c=2
20d48408235da691e2fae85161f24f5fde9750802c54beb133378afbee067131 ---> c=2
54cd91297c7f85151a56e04dc81ca75fa0df8e29b4267e9bb97013867cb41964 ---> c=1
a4249cee63c18ecdfb3f678aefeaad13249b1468e998f90b16b961535e184847 ---> c=0
0f9dc8faabf0f67a0482e9448b6158c0dbae3858eab70098acc1dceae9f72048 ---> c=4
205ebc8765cbe4e08350b03122b47198f4b06c1a6d6392e9cb9f3866389c7476 ---> c=2
6ec8b8a89ac7171b0f32d2152e47b79f5a1a678ceb351c01835bbc13a9e9f608 ---> c=1
ac803f22995d827fd84140d3fccba085e44ceac968b65d786ee84cdc325ed2f8 ---> c=0
79cda0e6697827652e912bdccc199e9dd5de42b30c8e7e0679b76c15d9281062 ---> c=1
4c0e2890af41b106689617393a0ea0fe3b196769daae3cf441c8323d7471ebfd ---> c=1
341483db0a9d43fe30f50001381f7b6ce4d1d220f16210eb798a4d6b13536a06 ---> c=2
3b0e72806f8271fbe66b2de9587b6816e33f1287cc1369b84aafefc9b45ec615 ---> c=2
e227a3c1e7744f23ffb8940ac160d48fcdfd2e33f6ac79e5ef3689da4211d6fc ---> c=0
b3cfb6d353fd34cbecc4f19cc9a3ed919c5774dc98872c73cd51373e47950820 ---> c=0
517d7336c512a61f1684f4bc4956593cac0563aa4c03136c0f7915fb09689e84 ---> c=1
e1b4de23fc7ebf1491bda18053b0cd1cf0a000da916294ac5704125c307552fb ---> c=0
09ab9873d18985d7386f6a8a093e6b1d9a684ed3ff6e16855e2bf43a54d97a42 ---> c=4
2de441fb8f9358f2a1209361808963075a0e704e3bf0396697a7ccfa6773e392 ---> c=2
61bed6ef78c4a7c77b9d5b41adb7aea91c77d865271a9f338df524810c90a19e ---> c=1
5f776787319ee1e368670f23cdf7a8b6fe277c0d55d8c1fe84a057979e6e62c9 ---> c=1
d23031f9d225c6e687e535f411d778afc35620800cf0a8ac5a954be6f6b1abf4 ---> c=0
1323580b48999e1dea85a1dfd8210486d80ddf9e45a45e70bd58e9dee892586d ---> c=3
a10703421f5cc52051049670bda209c1d4138667fc83710d5d5cbdc8c76e9a5f ---> c=0
50f948e107e284ba8bdc874542af2cf26f9abb0c0658ce691a966dcb2915434f ---> c=1
b9292bf63839e8d10ca33699ee206eb1ba7c1be63cbe89963844d82255643bc4 ---> c=0
eca44fb730a10830f61eb3d868e1404869f3db7c75cc1201345e06fb4613f0cc ---> c=0
b3b8d3186044f2dc176bc6256c86883450048bd2be107f4614fa1552d668131a ---> c=0
ed4e9ebd181fc3a753761e52997bc61ca620fa2bf084a13e9bd00921f7728de1 ---> c=0
31c81522a0c26d5975b467d6bf241d4ed924f3d98c52b99d11153cc16f0eddd1 ---> c=2
e8ae3cc241b7999bfbd04a02a5cee1ba07b26da07c2f9701692bfc35ce251e15 ---> c=0
88fdbb921f54e1510ab6d1b2f6c0c10f0383580908c90308400dd53cb7bbf914 ---> c=0
f0a003739bb27a8390ac7a9ee7520962b9315214eaa02671b7e0c2dad68f7f8a ---> c=0
71585212a79613a02e76918b6185fcf741f9064635ed2f22a16f6fe24b3dc837 ---> c=1
7fd9f9e7e2e6e2a9a798bd1a96205502e5f6761bfb2f5349fb15f27da757e3fd ---> c=1
b987d5234af47c5b2c615c9ddc65fa43e805ac1c68d390627a6c5766fd2dfba3 ---> c=0
02ec135fd9b25633310b6b0641d80afba991235a884c6a5024cd1f22e0c0fb4a ---> c=6
d6921cef7e8b32f67917b40564b2b3698c669047ca18df52b883aa75129a04a2 ---> c=0
ee27ea122d7ac4eb9d05ee8af8706ba036f8b4dc4778b0c36c384475b9533934 ---> c=0
6783da7822a4768b5fbcb49724825fa805878d930f4f7cb75d27e0ca27be9e43 ---> c=1
9f444df8c29d69aa71fc64b516f43a8e9e53ac94a956adece3984c7893ebc562 ---> c=0
4776cb716ab6d260c751f61150a7601608feee2c6924035b8fee90b258144932 ---> c=1
ce74d8df34844c6425aa63c39f997ee4f5c03198dad44865f79862346b1c80f2 ---> c=0
c963c55dc35eecb8ca6bd562a686b9e3fa44afa32166b803fa93c2a0160316ae ---> c=0
118ba6e159bb52eaaad89214f05ff38add7cabef8c436b04a2d3f7000d81bcdc ---> c=3
12a454cea68b11febfdad470576c87dce02a8b2d3d2b525ba5a7f2180a2f7bf0 ---> c=3
0afa0a9f5790f192c7e90e419163db02af680adf7e7332225a80a62cf7334b1f ---> c=4
bb1f3ead12be5ae759e3f4e05fad32dc05a39a6202cc4218203c0596c7777aea ---> c=0
b47e36856b3c4caf37b44f10efbc8a627e330fb7251c64b9d8f092d11ae9025f ---> c=0
28e6c7ca78bbbaf63226dddeafa9653c02a9b558458e4df6441a4828d1011980 ---> c=2
c12dd73eae744be0cf14b44075d3041a6c779fed1e5e8f9a6f01a49578b6148c ---> c=0
457b056bb7c1360c630c072611e9c49a1ce0da5208f916dff48a825bf04e665a ---> c=1
45089f5c7b818a530b0a19c499c93cf2818dde05b8eb7d995abf945a0866dbf9 ---> c=1
062a6346d020805767fe0a67f6dffbad6fa7630d57b41d33058a22c424104344 ---> c=5
6839224411a838ea5122556a1b085247baf49e6e5d7ce31f76838a1fc179c38b ---> c=1
123bbb3320e9774039e9243defa5cb7d6cd8dab2ea549e20284b45917197f78a ---> c=3
6f7b8349f3f509d8b16cc6a51fcc359953365b22999e616e0a1d8ec628daa798 ---> c=1
b2c68b197bd6544024d8838919ee65836474332246720411a3bec8ab43fc3074 ---> c=0
17eae552ee066e073af29477f2316f7a65008cf965327b99955c3ad795c77ca5 ---> c=3
1339aef785d2ff429c362bc9913f3be4962a7d6f703f03b87d0617ab044dcb70 ---> c=3
da6e8ce33da63107b82d6db71a0f7739811785e3d6606c5edbaac6eea685a97e ---> c=0
ca83aa6d4542c1f24f52f5e4fd108fbef74cbedea983738c13d39376a1a77aa2 ---> c=0
2b0088fc076743953b1efb8d1b73a89e439272ed1f10377da527f1ddeac481c7 ---> c=2
46f3728c022e3d091bac0233459d1c7614ec268c91b6a2035a00a60ba284de5c ---> c=1
389d025e40b0d587690e2418018aca333653cd0195c9cb17c8c1c5b59e0e06cc ---> c=2
7bbf6aa8534f5cb6a48e171cabefd36f2aeda61877ddfc4f2df8d3fe0c5ec196 ---> c=1
40fe7657008e0472d45667b6dfeaf64d7fa5695054c589d57fb2a75701ee3b40 ---> c=1
60732ec3e1e753f408d8fd075c46b1d79792668d9c5856873ce31b5b4b08dd96 ---> c=1
f6bec7ac292b90d530ea2140ede8a7213109962300ff79666721e39786b39ae5 ---> c=0
0e75b1070e6298826a980c21927d95604aeb18fcd2fbc9aea699ce60bb3fc936 ---> c=4
821184cfaa38702a47f3a3de9cc7537eb6d501baec5c616fefb868eafde6cb3a ---> c=0
58b301727b563760808ed12a1fd440af72d6c87f129bd75c5d0688a2cb294a97 ---> c=1
3e361e0cc0a5e93d854c34c244e547eaaa32369a1160bd2f7ee2139cbd8e75d6 ---> c=2
00275c3865542e66b1599f99bfc69f8afff3b086c9a4da3ac0315273f8493593 ---> c=10
--- PASS: TestValidity (0.01s)
PASS
ok      github.com/proullon/bitcoin/block       0.011s
=== RUN   TestValidate
--- PASS: TestValidate (0.00s)
PASS

The difficulty to find n increases exponentially, for testing purpose, let’s stay at 9: 1 byte + 1 bit.

Signature

The whitepaper specifies Each owner transfers the coin to the next by digitally signing a hash of the previous transation and the public key of the next owner and adding these to the end of the coin. A payee can verifiy the signatures to verify the chain of ownership.

The creator of the block signs the hash, to prove they’re the one doing the work and claiming the reward. We can use crypto/ecdsa for this. So, when creating a block, one need to

  • sign the hash of the previous transaction
  • include its own public key in the block
  • do the proof-of-work

Let’s adapt the code:

	sig, err := ecdsa.SignASN1(rand.Reader, privateKey, prev[:])
	if err != nil {
		t.Fatalf("cannot sign previous block's hash: %s", err)
	}
	t.Logf("Signature: %x", sig)
	b.Header.Prev = [sha256.Size]byte(sig)

	b.Owner, err = asn1.Marshal(privateKey.PublicKey)
	if err != nil {
		t.Fatalf("cannot DER encode public key: %s", err)
	}

block_test.go:75: 
    Signature: 30450220411cb91d166b180fbe4c3b8033ae451a67f0d3d86d7911b9dcd6d5df4de30824022100d62cfb761fc0f53b08ca39d72b598b05975798e51bbd7d3986e5856be11bb0f9
    block_test.go:80: cannot encode public key: asn1: structure error: unknown Go type: elliptic.Curve

Ah. There is no asn1 encoder for ecdsa.PublicKey type. I’m learning the crypto/elliptic.Curve type represents a short-form Weierstrass curve. I’ll have to check that.

Anyway, the ecdsa package exposes a function to convert to an ecdh.PublicKey, and those keys “can be parsed with crypto/x509.ParsePKIXPublicKey and encoded with crypto/x509.MarshalPKIXPublicKey. For NIST curves, they then need to be converted with crypto/ecdsa.PublibKey.ECDH after parsing.”

…Ok then, let’s do that. x509.MarshalPKIXPublicKey converts the public key to PKIX, ASN.1 DER form. Cool.

	sig, err := ecdsa.SignASN1(rand.Reader, privateKey, prev[:])
	if err != nil {
		t.Fatalf("cannot sign previous block's hash: %s", err)
	}
	t.Logf("Signature: %x", sig)
	b.Header.Prev = [sha256.Size]byte(sig)

	ecdshPublicKey, err := privateKey.PublicKey.ECDH()
	if err != nil {
		t.Fatalf("cannot convert public key to ECDH: %s", err)
	}

	pubkey, err := x509.MarshalPKIXPublicKey(ecdshPublicKey)
	if err != nil {
		t.Fatalf("cannot encode public key to ASN1 DER: %s", err)
	}

	t.Logf("Pubkey: %x  (len=%d)", pubkey, len(pubkey))
}

=== RUN   TestSignature
    block_test.go:75: Signature: 304502207155b0fbf29e14f3c0fce2a42c21196e712549a7b93e9318f6147fe73a701b2f022100b0e2a58a1d2aa2e86935b85e0b5f8a1d02e719c758b6b738e1fd175527490a3f
    block_test.go:88: Pubkey: 3059301306072a8648ce3d020106082a8648ce3d0301070342000478fc7058e8f908bf78491a99cf0f4a34ac81f1ceb41c1d9c8424e46e8feb5320a6bf7881d14374b00dc4a9ed817cb30a97f274764165ecde1f22941ce4647587  (len=91)
--- PASS: TestSignature (0.00s)
FAIL

Looks like we got what we need. So far the Go standard library has everything we could wish for.

Sources:

P2P network

Now, we need to build an application able to communicate peer-to-peer with other nodes to share the blockchain.

We need each node to:

  • load a private key
  • connect to peers
  • load a blockchain from disk
  • share the blockchain with peer
  • update blockchain on disk
  • listen to transaction request
  • listen to new blocks
  • build new block
  • share new block

We’ll also need a cli to:

  • generate private key
  • display information about the current blockchain
  • create a transaction

Let’s deal with all the cli boileplate with cobra:

$ bitcoin-cli
CLI utility to interact with bitcoin-node network

Usage:
  bitcoin-cli [command]

Available Commands:
  completion   Generate the autocompletion script for the specified shell
  generate-key Generate an ECDSA key to be used on bitcoin network
  help         Help about any command
  version      Software version number

Flags:
  -h, --help   help for bitcoin-cli

Use "bitcoin-cli [command] --help" for more information about a command.

$ bitcoin-cli version
This is a naive implementation, do not use it.

Let’s use libp2p|libp2p for the network setup. libp2p provides a lot of building blocks for peer-to-peer applications.Like discovery and rendez-vous in place of etcd, secret sharing in place of vault or pub/sub in place of kafka, Google pubsub or rabbitmq. It is a different paradigm, and the base of any true distributed application.

// Run initialise the node network with provided private key and disk working directory
func Run() error {

	host, err := libp2p.New()
	if err != nil {
		return err
	}
	defer host.Close()

	fmt.Println(host.Addrs())

	// Exit properly on SIGTERM and SIGINT
	sigCh := make(chan os.Signal, 1)
	signal.Notify(sigCh, syscall.SIGTERM, syscall.SIGINT)
	<-sigCh

	return nil
}

Let’s add peer discovery with mDNS (doc):

	// Peer discovery
	mdnsService := mdns.NewMdnsService(host, discoveryNamespace, &discoveryNotifee{})
	err = mdnsService.Start()
	if err != nil {
		return fmt.Errorf("cannot start mdnsService: %s", err)
	}

When I run 3 nodes in my local network I get:

# proullon @ desktop in ~/work/src/github.com/proullon/bitcoin [11:10:24] C:1
$ bitcoin-node run
[/ip4/127.0.0.1/tcp/35981 /ip4/127.0.0.1/udp/47685/quic-v1/webtransport/certhash/uEiCRyP7Zw31I5hJgeqNe3DpuT_R6SrJyW5GdVo6hFa3Rxw/certhash/uEiAg-olgLZwFB1BIeVAo3MSc0rAh1tOVuSbSJhEnap_zxQ /ip4/127.0.0.1/udp/55469/quic-v1 /ip4/192.168.1.39/tcp/35981 /ip4/192.168.1.39/udp/47685/quic-v1/webtransport/certhash/uEiCRyP7Zw31I5hJgeqNe3DpuT_R6SrJyW5GdVo6hFa3Rxw/certhash/uEiAg-olgLZwFB1BIeVAo3MSc0rAh1tOVuSbSJhEnap_zxQ /ip4/192.168.1.39/udp/55469/quic-v1 /ip6/::1/tcp/40381 /ip6/::1/udp/57576/quic-v1/webtransport/certhash/uEiCRyP7Zw31I5hJgeqNe3DpuT_R6SrJyW5GdVo6hFa3Rxw/certhash/uEiAg-olgLZwFB1BIeVAo3MSc0rAh1tOVuSbSJhEnap_zxQ /ip6/::1/udp/58728/quic-v1 /ip6/2a01:cb08:8c43:3700:ef07:63fd:ab1b:9637/tcp/40381 /ip6/2a01:cb08:8c43:3700:ef07:63fd:ab1b:9637/udp/57576/quic-v1/webtransport/certhash/uEiCRyP7Zw31I5hJgeqNe3DpuT_R6SrJyW5GdVo6hFa3Rxw/certhash/uEiAg-olgLZwFB1BIeVAo3MSc0rAh1tOVuSbSJhEnap_zxQ /ip6/2a01:cb08:8c43:3700:ef07:63fd:ab1b:9637/udp/58728/quic-v1]
found peer {12D3KooWGydHBHZKQW7Bozfra8R4QGGpi9kcB8D6tQge7nBwcPAQ: [/ip6/::1/tcp/41573 /ip6/2a01:cb08:8c43:3700:8f90:55c:d91d:459a/tcp/41573 /ip6/2a01:cb08:8c43:3700:60f1:d983:8a38:24ea/tcp/41573 /ip6/2a01:cb08:8c43:3700:7cae:1b8b:bf99:1f65/tcp/41573 /ip6/2a01:cb08:8c43:3700:c4f1:42a3:c7dc:346/tcp/41573 /ip6/2a01:cb08:8c43:3700:5ba0:4bfa:2dc6:c535/tcp/41573 /ip6/::1/udp/47629/quic-v1 /ip6/2a01:cb08:8c43:3700:8f90:55c:d91d:459a/udp/47629/quic-v1 /ip6/2a01:cb08:8c43:3700:60f1:d983:8a38:24ea/udp/47629/quic-v1 /ip6/2a01:cb08:8c43:3700:7cae:1b8b:bf99:1f65/udp/47629/quic-v1 /ip6/2a01:cb08:8c43:3700:c4f1:42a3:c7dc:346/udp/47629/quic-v1 /ip6/2a01:cb08:8c43:3700:5ba0:4bfa:2dc6:c535/udp/47629/quic-v1 /ip6/::1/udp/59863/quic-v1/webtransport/certhash/uEiD1jH39lBy1llJoSyf8qfTvaCrvXpKLkwbj5iHJmofE-g/certhash/uEiBWVcFlYKYMWA31_0CmKHa_wiiNivP0mmmbfV9PUKKuwQ /ip6/2a01:cb08:8c43:3700:8f90:55c:d91d:459a/udp/59863/quic-v1/webtransport/certhash/uEiD1jH39lBy1llJoSyf8qfTvaCrvXpKLkwbj5iHJmofE-g/certhash/uEiBWVcFlYKYMWA31_0CmKHa_wiiNivP0mmmbfV9PUKKuwQ /ip6/2a01:cb08:8c43:3700:60f1:d983:8a38:24ea/udp/59863/quic-v1/webtransport/certhash/uEiD1jH39lBy1llJoSyf8qfTvaCrvXpKLkwbj5iHJmofE-g/certhash/uEiBWVcFlYKYMWA31_0CmKHa_wiiNivP0mmmbfV9PUKKuwQ /ip6/2a01:cb08:8c43:3700:7cae:1b8b:bf99:1f65/udp/59863/quic-v1/webtransport/certhash/uEiD1jH39lBy1llJoSyf8qfTvaCrvXpKLkwbj5iHJmofE-g/certhash/uEiBWVcFlYKYMWA31_0CmKHa_wiiNivP0mmmbfV9PUKKuwQ /ip6/2a01:cb08:8c43:3700:c4f1:42a3:c7dc:346/udp/59863/quic-v1/webtransport/certhash/uEiD1jH39lBy1llJoSyf8qfTvaCrvXpKLkwbj5iHJmofE-g/certhash/uEiBWVcFlYKYMWA31_0CmKHa_wiiNivP0mmmbfV9PUKKuwQ /ip6/2a01:cb08:8c43:3700:5ba0:4bfa:2dc6:c535/udp/59863/quic-v1/webtransport/certhash/uEiD1jH39lBy1llJoSyf8qfTvaCrvXpKLkwbj5iHJmofE-g/certhash/uEiBWVcFlYKYMWA31_0CmKHa_wiiNivP0mmmbfV9PUKKuwQ /ip4/127.0.0.1/tcp/36593 /ip4/192.168.1.24/tcp/36593 /ip4/127.0.0.1/udp/56926/quic-v1 /ip4/192.168.1.24/udp/56926/quic-v1 /ip4/127.0.0.1/udp/36373/quic-v1/webtransport/certhash/uEiD1jH39lBy1llJoSyf8qfTvaCrvXpKLkwbj5iHJmofE-g/certhash/uEiBWVcFlYKYMWA31_0CmKHa_wiiNivP0mmmbfV9PUKKuwQ /ip4/192.168.1.24/udp/36373/quic-v1/webtransport/certhash/uEiD1jH39lBy1llJoSyf8qfTvaCrvXpKLkwbj5iHJmofE-g/certhash/uEiBWVcFlYKYMWA31_0CmKHa_wiiNivP0mmmbfV9PUKKuwQ]}
found peer {12D3KooWNG7wymXvy9RtcpSJ6EGKUHmDxW4SGvxFTFqk15mfUKUY: [/ip4/127.0.0.1/tcp/37665 /ip4/192.168.1.28/tcp/37665 /ip4/172.17.0.1/tcp/37665 /ip4/127.0.0.1/udp/34720/quic-v1 /ip4/192.168.1.28/udp/34720/quic-v1 /ip4/172.17.0.1/udp/34720/quic-v1 /ip4/127.0.0.1/udp/53323/quic-v1/webtransport/certhash/uEiAOaKv5VmO5mWhQL-HPYV2-qNWoZVGi8Fz8wH2pZZfOfA/certhash/uEiB8H8oAYnxELY7FNlnazwZgpGx2WbKeFUhGdVZzyPPvKQ /ip4/192.168.1.28/udp/53323/quic-v1/webtransport/certhash/uEiAOaKv5VmO5mWhQL-HPYV2-qNWoZVGi8Fz8wH2pZZfOfA/certhash/uEiB8H8oAYnxELY7FNlnazwZgpGx2WbKeFUhGdVZzyPPvKQ /ip4/172.17.0.1/udp/53323/quic-v1/webtransport/certhash/uEiAOaKv5VmO5mWhQL-HPYV2-qNWoZVGi8Fz8wH2pZZfOfA/certhash/uEiB8H8oAYnxELY7FNlnazwZgpGx2WbKeFUhGdVZzyPPvKQ /ip6/::1/tcp/37753 /ip6/2a01:cb08:8c43:3700:8a37:f1d2:b7d6:e864/tcp/37753 /ip6/2a01:cb08:8c43:3700:dfca:9ba9:7888:5780/tcp/37753 /ip6/2a01:cb08:8c43:3700:129b:387f:8fc1:5589/tcp/37753 /ip6/::1/udp/35773/quic-v1 /ip6/2a01:cb08:8c43:3700:8a37:f1d2:b7d6:e864/udp/35773/quic-v1 /ip6/2a01:cb08:8c43:3700:dfca:9ba9:7888:5780/udp/35773/quic-v1 /ip6/2a01:cb08:8c43:3700:129b:387f:8fc1:5589/udp/35773/quic-v1 /ip6/::1/udp/52021/quic-v1/webtransport/certhash/uEiAOaKv5VmO5mWhQL-HPYV2-qNWoZVGi8Fz8wH2pZZfOfA/certhash/uEiB8H8oAYnxELY7FNlnazwZgpGx2WbKeFUhGdVZzyPPvKQ /ip6/2a01:cb08:8c43:3700:8a37:f1d2:b7d6:e864/udp/52021/quic-v1/webtransport/certhash/uEiAOaKv5VmO5mWhQL-HPYV2-qNWoZVGi8Fz8wH2pZZfOfA/certhash/uEiB8H8oAYnxELY7FNlnazwZgpGx2WbKeFUhGdVZzyPPvKQ /ip6/2a01:cb08:8c43:3700:dfca:9ba9:7888:5780/udp/52021/quic-v1/webtransport/certhash/uEiAOaKv5VmO5mWhQL-HPYV2-qNWoZVGi8Fz8wH2pZZfOfA/certhash/uEiB8H8oAYnxELY7FNlnazwZgpGx2WbKeFUhGdVZzyPPvKQ /ip6/2a01:cb08:8c43:3700:129b:387f:8fc1:5589/udp/52021/quic-v1/webtransport/certhash/uEiAOaKv5VmO5mWhQL-HPYV2-qNWoZVGi8Fz8wH2pZZfOfA/certhash/uEiB8H8oAYnxELY7FNlnazwZgpGx2WbKeFUhGdVZzyPPvKQ]}

Not easily readable, but in less than 1 second, all nodes have found each other and a callback has be fired.

So, it’s able to find it’s own peers in a local network, that’s great. Now they should actually communicate with each other.

We also want a pub/sub for new transaction and new block (doc):

	// PubSub
	ps, err := pubsub.NewGossipSub(ctx, host)
	if err != nil {
		return fmt.Errorf("cannot start pubsub service: %s", err)
	}
	// join topics for transactions and blocks
	txTopic, err := ps.Join(TxTopic)
	if err != nil {
		return fmt.Errorf("cannot join transaction topic: %s", err)
	}
	txSub, err := txTopic.Subscribe()
	if err != nil {
		return fmt.Errorf("cannot subscribe to transaction topic: %s", err)
	}
	bTopic, err := ps.Join(BlockTopic)
	if err != nil {
		return fmt.Errorf("cannot join block topic: %s", err)
	}
	bSub, err := bTopic.Subscribe()
	if err != nil {
		return fmt.Errorf("cannot subscribe to block topic: %s", err)
	}

Now we need to piece everything together in an easily testable finite state machine. Something like:

type Node struct {
	privateKey     *ecdsa.PrivateKey
	bc             *blockchain.Blockchain
	tentativeBlock *blockchain.Block
}

func (n *Node) Start() {
}

func (n *Node) Stop() {
}

func (n *Node) run() {
}

func (n *Node) incomingTransaction(tx *blockchain.Transaction) {
}

func (n *Node) shareTransaction(tx *blockchain.Transaction) {
}

func (n *Node) incomingBlock(b *blockchain.Block) {
}

func (n *Node) startBuildingBlock() {
}

func (n *Node) stopBuildingBlock() {
}

func (n *Node) shareBlock() {
	data, err := n.tentativeBlock.Encode()
	if err != nil {
		return err
	}

	err = n.bTopic.Publish(context.Background(), data)
	if err != nil {
		return err
	}
}

Compatibility with official implementation

OK cool, but the whitepaper doesn’t specify the format of blocks, chain nor transactions. We’ll need to look at the official implementation to see what the protocols specs.

Let’s see what are the standards used in bitcoin:

  • SHA-256 for hash
  • ECDSA with DER encoding for signature
  • hash of ECDSA public key for addresses

source:

Building official implementation

Haha lib-boost. What a pain.

# proullon @ desktop in ~/work/src/github.com/bitcoin on git:master x [11:28:23] C:1
$ ./configure
...
checking whether miniUPnPc API version is supported... yes
checking for natpmp.h... yes
checking for initnatpmp in -lnatpmp... yes
checking for Boost headers >= 1.73.0 (107300)... configure: We could not detect the boost libraries (version 1.73.0 or higher). If you have a staged boost library (still not installed) please specify $BOOST_ROOT in your environment and do not give a PATH to --with-boost option.  If you are sure you have boost installed, then check your version number looking in <boost/version.hpp>. See http://randspringer.de/boost for more documentation.
configure: error: Boost is not available!

Ok…

# proullon @ desktop in ~/work/src/github.com/bitcoin on git:master x [11:31:34]
$ sudo pacman -S boost

Let’s buiiiiiiild now.

  • Insert 3 hours later meme *

Testing the official implementation

So there is a rust file checking the python implementation of the integration test of the C++ implementation. What a journey. I wanted to use them on my implementation but it’s in fact not trivial.

Running the official implementation

You need 500Gb and 10Gb per month…to run a full node.

OK then:

# fdisk /dev/sdc
# mount -t ext4 /dev/sdc3 /mnt/storage
# proullon @ desktop in ~/work/src/github.com/proullon/bitcoin [11:35:58] C:1
$ df -h
Filesystem      Size  Used Avail Use% Mounted on
/dev/sdc3       935G  2,1M  888G   1% /mnt/storage

Ready.

Next step ? Maybe look at Bitcoin book official protocol and adapt my implementation to be compatible with it.

The code is available on Github.

← prev