As bitcoin adoption grows, so has the growth of light clients, i.e. nodes on the network incapable of independent transaction verification. To ensure that these clients can verify transactions related to them, the concept of bloom filters was proposed for usage in what is known as simple payment verification.

The introduction and usage of bloom filters made it possible for light clients to verify transactions in interested blocks in ways that, to a certain degree, preserved their privacy. However, this “privacy-preserving” method of payment verification is not without leaks, requiring trust in honest peers (full nodes) to forward Merkle blocks containing the desired transactions, for work they (full nodes) have no incentive to do.

For all the benefits they provide, the problems with bloom filters initiated the drive towards client-side transaction filtering based on trustless peer connections, and with no privacy leaks. In this article, I provide a basic overview of how light clients utilize bloom filters for payment verification, some of the challenges associated with their use, and why there was a need for a different way to conduct transaction verification.

Light Client Transaction Verification

Not all devices have the “luxury” of performing independent verification of transactions, which can only be done with access to the entire bitcoin ledger. This is primarily because of device-specific constraints on space, bandwidth, and processing power. These constrained devices are, in truth, only interested in the transactions related to the addresses in their wallets and should not be downloading multiple GBs of unrelated data. Also, with the growth of bitcoin, it has become increasingly more expensive to run a full node. Beyond just downloading the blockchain, nodes must remain connected to different peers on the network all the time. The memory, processing, and bandwidth requirements are quite “steep” and unreasonable for all nodes on the network to have.

For devices like mobile phones and tablets, it is possible to partake in the network by running lightweight clients — nodes that do not have access to the full blockchain but can conduct verification of payments by depending on full nodes, and their access to the complete ledger. To verify that a transaction of interest, i.e. paying bitcoins to address(es) on their wallet, is valid, the light clients create and send bloom filters to full nodes, who, in turn, forward just about enough block information (in a Merkle block) for the light clients to recalculate the Merkle root in the block header. The light clients check a transaction’s proof of inclusion if the Merkle roots match. This is the only way a light client can be sure that the transaction was included in this block.

The lack of access to the full blockchain translates to light clients delegating double-spend detection to full nodes and miners. Light clients are not exactly susceptible to double-spend attacks because they outsource the responsibility of detecting transactions spending the same UTXOs to miners. As long as honest miners have >51% of the hashing power, there will be no double-spends, as enforced by the miners.

Full nodes can hide transactions from them, thereby denying them service. With the hope of peering with an honest full node, light clients randomly connect to several nodes on the network to combat the aforementioned attack. This makes them vulnerable to Sybil attacks that encircle them with fake nodes that disconnect them from the real network, stalling the light clients. This attack cannot steal funds but will impact usability.

Light clients conduct transaction verification by using tune-able bloom filters so that they do not leak information about the addresses in their wallets.

Bloom Filters:

Light clients cannot share their addresses/script_pubkeys to full nodes. Well, they can, but should not because of the loss of privacy in doing so. What they can do is create a superset of transactions they might be interested in. This is done using bloom filters — a probabilistic search filter. These filters are n-sized bit field created by passing transactions through a set number of hash functions, noting the output number q (between 1 and n) of each hash function, and flicking the bit at position q on (0 to 1).

This is how light clients use bloom filters. They:

• create a list of script hashes, and transaction IDs from any UTXO its wallet can spend: For any transaction paying bitcoins to addresses in the light client’s wallet, the light client creates a list containing the transaction’s ID, the pub keys, and hashes in the transaction output’s script_pubkey, each input in the transaction input, and signatures in the witness scripts (or script_sig). See the figure below.

• add each list item to the bloom filter: Each item in the list is passed through the set number of hash functions to the bloom filter, as shown below.

• send bloom filter to peers: The bloom filter is then sent to peers on the network. Full nodes match each incoming transaction to the bloom filter, sending a Merkle block to the light client only when there is a match.
• verify transaction: With the Merkle block, the light client checks for matched transactions, and updates its view of the UTXO set, wallet balance, and the bloom filter to match future transactions that will reference the found UTXO.

The way bloom filters work seems pretty straightforward. Light clients get to, to some degree, protect their privacy, and keep bandwidth and space requirements at a minimum. These benefits are not without their costs though. The risk of Sybil attacks remain for the light client. Full nodes also bear the brunt of the work when they match each incoming transaction to the bloom filters they received. It is work done without reward that also exposes them to denial of service attacks if they get spammed with fake bloom filters. Having one bloom filter per connected client does not scale.

For all the benefits of bloom filters, it appears most light clients rely on data from wallet vendors for transaction verification (Song, 2019). The drawback to using bloom filters heralded a new way for light clients to perform client-side transaction filtering and verification. This way has to provide the following benefits:

1. Privacy: Bloom filters are tune-able and you can achieve varying degrees of privacy by how they are constructed. The larger the size of the bitfield, and the number of hash functions, the greater the accuracy and specificity of the filter, and the worse the privacy score. With a lower specificity, the better the privacy score. Light clients should be able to request for block headers without worrying about how much privacy is lost with the specificity of their bloom filters. The new way must ensure that light clients can request for block data without compromising on their privacy.
2. Trust: Light clients need to connect with at least one honest peer that would neither deny them service by hiding transactions nor send them double-spent transactions. The new way should encourage bitcoin’s philosophy of trustlessness. Light clients should request and get filter information for transactions they want to verify without having to trust any one honest peer.
3. Work: Full nodes are in a state of perpetual work, scanning and re-scanning bloom filters for every incoming transaction they receive. Apart from providing a service that keeps the bitcoin network active for growing light clients, there is no reward for server-side transaction filtering. The risks of DOS attacks also need consideration. If a new solution to the transaction verification problem for light clients reduces the work of scanning to one-time computation and eliminates the attack vector, then that should be explored.
4. Size: The size of the new filter should be lightweight. Small enough to compute and save to disk, and to relay along the network.

The proposal and implementation of compact block filters provided these benefits. In the follow-up article to this, I will explore compact block filters and how it is a better alternative to bloom filters.

Conclusion

As bitcoin adoption grows, so has the growth of light clients. These clients, without access to the full ledger, have particular requirements concerning transaction verification for addresses in their wallets. They rely on a payment verification method that creates and sends bloom filters to full node peers. These filters are tune-able, giving light clients privacy control, but makes them vulnerable to Sybil attacks. These filters also place a disproportionate amount of work on full nodes. To counter the disadvantages, a new kind of filtering system called compact block filters was proposed and will be the topic of discussion in my article.

Contact me

I would deeply appreciate any feedback you can provide. If you found this article helpful/useful or found factual misrepresentation, please do not hesitate to comment or contact me here or on Twitter @engb_os.

References

1. Antonopoulos, A. (2017). Mastering Bitcoin: Programming the open blockchain
2. Song, J. (2019). Programming bitcoin: Learn how to program bitcoin from scratch
3. Rosenbaum, K. (2019). Grokking Bitcoin
4. Mouton, E (2021): Compact Block Filters Deep Dive (BIP 158). https://bitcoin-dev.blog/blog/bip158-deep-dive/. Accessed 2 May 2022.

Architecture

This section covers some of the architectural modifications I made. It describes the state of the ldk-sample, the server, and the CLI binary.

Lightning Node: ldk-sample

This binary has remained largely unchanged from what I forked. A lightning node is a complex application with several parts coupled across the lightning protocol suite. The thought and decision-making that went into the network, messaging, p2p, routing, and payment layers were things that I didn’t want to change, given my scant but growing knowledge about the lightning network architecture. The fact that certain features are built across multiple layers meant that any changes I made, with the expectation that they would be constrained to one, would trickle across other layers.

The ldk-sample node has a coupled CLI as the only way to interact with the node. This CLI process commands that allow peer connection, channel opening, invoice generation, sending payment, signing messages, and a handful of other commands to glean information about the state of the node and to act in a channel with channel partner/peer.

My goal for this project was to decouple the CLI and run the node in ways akin to how LND runs, i.e. lnd node running separately with lncli sending commands and retrieving node state responses. Within the LDK node, I decided to build a server that would listen to requests from the CLI, as well as other clients capable of sending requests to the server. The diagram below shows a depiction of the architectural changes I decided to make.

Server

In the entry point to the ldk-sample project is a call that polls start_ldk() to start the node. Within this start function, the CLI for the node is started too. This interface polls for users’ input, matching them against defined lightning commands to, for example, get a node's information, or list connected peers, among others.

I decided to replace the CLI’s loop within the node’s start-up function with a running instance of an actix-web server as shown below.

To pass the node’s variables to the server’s application state, I defined a struct NodeVar<EventHandler>, generic for any field that implements EventHandle. This event handler takes in the node's handle_ldk_events function and polls in another tokio runtime, awaiting the various event outcomes (e.g. funding generated, payment received, etc) possible within a payment channel.

With this implementation, I could then create handlers for each command/path as shown below.

For demonstration purposes, the node variable struct node_var is passed to the list_peers request handler within which the peers connected to the LN-Node can be retrieved and sent back to the calling client (CLI or HTTP).

Beyond just the CLI making requests to this server, I wanted external HTTP clients to have the same capabilities, i.e. getting information about the node’s state, and acting to transact with other nodes in the network. I thought this would be a nice-to-have because of its “perceived” ease of use when compared with CLIs. Imagine having a dashboard with a great user interface to interact with your lightning node.

CLI binary

For the CLI to run separately, I created a different binary lnnode-cli within the project to take in command inputs, extract matching request body, send a request to the node's server with the reqwest crate, process server responses, and print to the caller's terminal.

To demonstrate the construction of a request body for the connectpeer command, the corresponding match arm parses the command’s arguments, i.e. public key, host, and port, to generate a hash map.

With the map constructed, the reqwest client can send the request to the server with the right body, i.e. json(&command). To further explain what right means here, a user would type out a command on the terminal to connect with a new peer.

The request body constructed from this terminal input is a hash map that is saved to the variable command .

With the returned response, the processing can be done and printed to the terminal within a match arm for the path visited.

Testing

If you do not have bitcoin core and either LND, eclair, or c-lightning installed, testing the application will be difficult because of all the setup required. However, with the installation of Lightning Polar , you can create a node network with as many as 3 lightning nodes and 1 block source (i.e. bitcoin core running in regtest). LN-Node can be connected to polar’s bitcoind and establish direct channels with any of the other nodes in the network. With the pre-requisites covered, clone the LN-Node repository and change to its root directory.

Within the root directory is a startup script lnnode.sh I wrote to make the process easier. With polar running and bitcoin node selected, copy the connection details from the Connect tab and populate the matching fields in the start-up script.

Having done that, open a terminal and run the script.

This starts up the node and the embedded server. Switch to another terminal to test the CLI and get a list of the command and arguments that can be passed.

With a HTTP client like Postman or Insomnia, the same requests to the node server can be made just like the CLI. Below is a screenshot of the request to open a channel with a peer with public key as shown, listening on host 127.0.0.1 and port 9736, with a channel funding amount of 100,000 sats.

This node information was gleaned from another node (carol) on polar. The repo also has a JSON file (insomnia_rest_api.json) importable into a client like Insomnia to test the endpoints.

Upgrades

As my knowledge of the lightning network and Rust grows, I expect to periodically revisit and upgrade this project primarily to achieve the following:

1. Remove reliance on the ldk-sample node by building a lightning node from scratch
2. Capture the channel events in server responses
3. Use a CLI-dedicated crate like clap to build a better client

Conclusion

The building experience was more challenging than I anticipated. I struggled with Rust more than I expected to, given that I had spent over a month learning the language. However, some positives to take from this experience is my increasing comfort reading and writing the language, as well as my growing knowledge of the lightning network.

I am always open to helpful feedback. Reach out here or on Twitter (@engb_os) if you have some or just want to chat.

References

1. LDK-sample: https://github.com/lightningdevkit/ldk-sample

The creation of payment channels is foundational to the lightning network, underpinning the ability of connected nodes to make off-chain payments. Establishing these channels involves six (6) message exchanges between prospective peers to set channel capabilities, create funding and refund transactions, and enter channel operations of forwarding payments. In this article, I will briefly explain each one of these messages with a particular focus on funding & refund transactions.

Part I: Setting channel capabilities

Prospective channel peers who would like to make millisat payments with each other start the process of creating a payment channel by sending two messages: open_channel where the initiator communicates their channel expectations, and accept_channel where the recipient accepts the proposed channel.

1. Requesting to open a channel

In the former, information regarding how much the channel will be funded with, the minimum channel balance, the time a peer needs to wait before claiming their funds in unilateral channel closing, the public key of the initiator, among others.

2. Accepting proposed channel

If the proposed channel expectations are found acceptable, the recipient responds with the latter message, providing their public keys also, alongside other information. The public keys of both the initiator and the recipient are needed to construct a 2-of-2 multisignature address for the funding transaction.

Part II: Creating funding and refund transactions

Having established a willingness to operate a channel between themselves, the initiating channel peer will do the following, in order:

• create a transaction payable to multisignature address constructed from both their public keys,
• create a funding transaction without broadcasting the said transaction,
• create a refund transaction chained with the funding transaction’s outpoint,
• send a funding_created message to the recipient channel peer with the funding transaction’s ID and output index.

The recipient channel partner will, upon receiving the message from the initiator:

• create and sign their version of the refund transaction
• send a funding_signed message to the initiator

With both signatures, the funding transaction can be broadcast and confirmed for channel operations to commence. This section will look a the creation of multisignature addresses, and the creation of funding and refund transactions.

1. Multisignature Address Generation

Consider the scenario where some entity created a *p2wpkh* transaction paying Alice 200,000 sats as depicted below. If Alice can provide a witness script structured in the same format as the witness script of Tx0P that redeems the UTXOs in Tx0Q:3, then Alice can spend the amount contained in Tx0P:0 by providing a valid signature and a public key whose hash produces the same 20-byte hash contained in the transaction output.

Note:

• The hash contained in the locking script is hash160, i.e. SHA256 + RIPEMD.

With the function below, the serialized locking script *s* is doubly hashed to produce a 32-byte hash.

Alice (iniitaiting channel partner) can create a p2wsh multisignature address by doing the following:

• Create a multisignature witness/redeem script with both hers and Bob’s public keys. Take note that the ordering of public keys presented here is just for depiction and not as is done in practice. Ideally, the ordering is done lexicographically.
• Hash the script to get a 32-byte hash

2. Funding transaction

With the multisignature hash address, Alice can construct a funding transaction that pays say 140,000 sats to Bob (recipient channel partner). A visualization of the transaction is shown. Here Alice spends from a single input and pays to two addresses. The first is the payment to the multisignature address, and the second is change back to her.

This transaction (Tx01) is not broadcast to the network by Alice but withheld. This withholding is done because Alice does not have the second quorum (Bob’s signature) to unlock the transaction if it is mined, without which she essentially has thrown money away if Bob withholds his signature. To get this signature, Alice has to send Bob a funding_created message, but not before creating a refund transaction that spends the UTXOs locked to the multisignature address, payable to herself.

3. Refund transaction

With the funding transaction created, Alice gets to create a p2wpkh refund transaction that pays the UTXOs locked in the 2-of-2 multisignature address to herself. As much as the funding transaction has not been broadcast, Alice can trust that the transaction’s ID will remain unchanged so that when it is eventually relayed to the network and mined, there is no malleability vector to worry about (thanks to segwit). When it is relayed and mined, Alice also needs Bob’s signature to spend the UTXO.

To get the needed signature, Alice sends a funding_created message to Bob letting him know about the funding outpoint. Bob creates and signs his version of the refund transaction and lets Alice know by sending a funding_signed message containing the signature corresponding to his public key used in creating the 2-of-2 multisignature address.

With both signatures, Alice has enough information to broadcast the funding transaction to the bitcoin network without fear of losing her money. She has the signatures needed in the witness script as shown in the rightmost transaction (see Figure 5) to recover all her money.

Having broadcast and confirmed the transaction, both channel partners share a funding_locked message that signals the readiness of the channel for operations (sending payments) between the peers.

Conclusion

In this article I looked at the messages prospective channel partners must share before a payment channel between them can be established using some diagrams that helped me visualize the processes better. Prospective peers must agree on the channel capabilities, the initiator must create funding and refund transaction and inform the other partner about this, sending enough information for the partner to create and sign their copy of the refund transaction, sharing the signature needed to refund the initiator if something goes wrong.

Contact me

I would deeply appreciate any feedback you can provide. If you found this article helpful/useful or found factual misrepresentation, please do not hesitate to comment or contact me here or on Twitter @engb_os.

References

1. Song, J. (2019). Programming bitcoin: Learn how to program bitcoin from scratch
2. Rosenbaum, K. (2019). Grokking Bitcoin
3. Antonopoulos Andreas, Osuntokun Olaoluwa, & Pickhardt René. (2021). Mastering the lightning network: A second layer blockchain protocol for instant bitcoin payments

These fields, except for the signature script, cannot be changed without invalidating the transaction. The field containing the unlocking script is emptied (a signature should not sign itself) before the transaction is hashed thus making it possible to change the unlocking script without rendering the transaction useless. Because of this reason, different unlocking scripts can represent the same transaction. How is this so? Initially, I thought that it had to do with how signatures are calculated, given that randomness is embedded in the signing algorithm used to sign transactions.

From my perspective, understanding the basic underlying mathematics of the signing process could provide some insights. Hence, in this article, I will explain my understanding of the basic math of signing, how different signatures, and in extension, unlocking scripts, can apply to the same transaction, and how segwit fixed transaction malleability.

Basic mathematics of signing

Signing is a way to prove the knowledge and possession of a secret number, i.e. private/signing key (e) without revealing this number. We know that in asymmetric cryptographic systems

where G is the generator point and P is the public key.

To sign a transaction hash, a random number k is selected such that

I assumed that because G lies on the elliptic curve, R lies on it too so that the summation of two points on the curve will give the position of R (addition is closed in a finite field). These points (u, v) can be selected by the signer as depicted in the image below.

Knowing that eG = P, and rearranging

Equation 4 can be considered as another way to represent the discrete log problem (DLP) because you either have knowledge of e, to select k such that (k — u)/v is equal to e (thus solving eG = P), or you try a brute force approach by selecting several combinations of (k, u, v).

In generating a valid signature S(r,s) for a transaction, we:

• hash the transaction to get z (the transaction hash) — taking note to empty the unlocking script and append appropriate signature hash flags,
• choose a random unique k,
• calculate kG = R(r,y) and select its x-coordinate (r),
• and calculate s such that the transaction hash (z), and signing key (e) are incorporated into the signature by selecting u and v as shown below:

Composing r and s gives a valid signature for the transaction.

Why different signature scripts can apply to the same transaction

As can be seen, any combination of k (must be unique for a signature), u, and v that satisfies the equation is valid for the given transaction hash z. From the signer’s perspective, this is fine. The signer of a transaction can sign the transaction many times, generating different signatures valid for the said transaction. This signature is then embedded in the signature script of the transaction, and then broadcast to the network.

However, some malicious users on the network can receive the broadcast transaction and modify it in different ways to generate a new valid but malleated transaction, which is essentially the same as the initially broadcasted transaction, albeit with a different transaction ID. These transactions spend the same inputs, transferring the same value to the same outputs, thus creating a conflict where only one of these transactions will be mined and added to the ledger. If the malleated transaction is mined, other transactions referencing outputs from the original transaction cannot spend from it.

How is this transaction malleability possible? The malicious user can modify the signature format of, add extra instructions to, or use cryptographic tricks on the signature script (Rosenbaum, 2019). Basically, by changing the signature script of the transaction, which changes the serialized transaction, and the transaction identifier.

Segwit and fixing transaction malleability

Segwit proposed to move the signature script data into another field — the witness field — that is not used for calculating the transaction ID, so that changes to the signature script field cannot impact the transaction identifier.

Conclusion

Randomness and the selection of a unique k value per signature allow signers to mutate transaction objects. They can generate different signatures for a transaction although one is selected and embedded into the unlocking script. In broadcasting their signed transaction, pre-segwit, users could experience a malleability attack that allowed malicious users to modify the signature script field of the broadcast transaction and change the transaction’s identifier. With segwit, moving the data from the signature script into a field that does not impact the calculation of the transaction ID, eliminated the malleability attack vector.

Note:

I would deeply appreciate any feedback you can provide. If you found this article helpful/useful or found factual misrepresentation, please do not hesitate to comment or contact me here or on Twitter @engb_os.

References

1. Antonopoulos, A. (2017). Mastering bitcoin: Programming the open blockchain
2. Song, J. (2019). Programming bitcoin: Learn how to program bitcoin from scratch
3. Rosenbaum, K. (2019). Grokking Bitcoin

Signatures can apply to all or parts of a transaction and the way we can tell is by inspecting the signature hash flags. These flags are 8-bit long characters appended to the end of a signature and are important because they make it possible for transactions to be constructed in different ways. The simplest type of transaction one can construct is a transaction that has just one input, referencing a UTXO, that pays to a single output address. However, transactions can have multiple inputs and outputs, with inputs referencing UTXOs from different owners who may sign their inputs. In this way, a partially constructed transaction can be created, where owners collaborate to collect all the needed signatures to make the otherwise invalid transaction valid. With signature hash (SIGHASH) flags, signatures can indicate what part of the transaction is included in the hash.

This article briefly explains the anatomy of signatures and how to identify SIGHASH flags, the types of SIGHASH flags, how SIGHASH types are applied, as well as scenarios where they can be used.

Anatomy of a DER signature

Digital signatures are serialized using the Distinguished Encoding Rules (DER) which encodes the standards for serializing digital signatures S(r,s). These signatures consist of the following parts, in order:

1. A starting byte of hex value [0x30]
2. Length of the signature sequence [0x44] or [0x45]
3. r-marker byte of hex value 0x02
4. Length of r [0x21]|| Big-endian representation of r
5. s-marker byte of hex value 0x02
6. Length of s [0x20]|| Big-endian representation of s
7. 1-byte SIGHASH suffix*

Types and application of signature hash flags

There are three types of signature hash flags: ALL, NONE, and SINGLE. Figure 3 shows the byte representation of each type.

For SIGHASH ALL, given a transaction Tx, the signature applies to all of Tx’s inputs and all its outputs (see green bounding boxes). SIGHASH ALL is applied by

1. Creating a copy of the transaction,
2. Empty script_sigs for each input and replace with the script_pubkey they reference. This is done because the “signature is part of the script_sig and … can’t sign itself” (Song, 2019, p. 132)
3. Make sure that no other fields are set to empty before the transaction is serialized (Tx_ser).
4. The flag 0x01 is added to the end of the serialized transaction and passed through a hashing function.
5. This message is then signed by the signing algorithm to generate the signature.

where e is the signer’s private key and S(r,s) the signature.

The transaction is rendered invalid if any of its details are changed because the signature will change too and be invalid.

For SIGHASH NONE, the signature applies to all of Tx’s inputs (see green bounding box) but to none of the outputs. The application process is as stated below:

1. Create a copy of the transaction
2. Empty each script_sig for all inputs and replace with the script_pubkey they reference
3. Empty out all output fields
4. Serialize the transaction
5. Append 0x02 to Tx_ser, hash, and then sign

For SIGHASH NONE, any output can be modified without invalidating the signature, but if any one of the inputs is modified, the signature is rendered invalid.

For SIGHASH SINGLE, all the inputs of the given transaction Tx are signed and one output that has the same index of one of the inputs being signed. This is essentially “authorizing all other inputs to go with a specific output” (Song, 2019, p. 133).

1. Create a copy of the transaction
2. Empty script_sigs for each input and replace with the script_pubkey they reference
3. Empty out all output fields bar the specific output
4. Serialize the transaction
5. Append 0x03 to Tx_ser, hash, and then sign

A change to the specified output or to any of the inputs invalidates the signature.

Modifier Flag

An ANYONECANPAY modifier flag exists that can be added to the aforementioned flags that apply to a single input in a transaction. Rosenbaum (2019) considers the ANYONECANPAY modifier flag as a way to commit to inputs only, by setting or not setting it, and the existing SIGHASH types (ALL, NONE, SINGLE) as a way to commit to outputs only.

With ANYONECANPAY set for ALL, changes can be made to all inputs except the select input (index 0) and the outputs (see image below).

ANYONECANPAY set for NONE means that changes can be made to all outputs, and inputs except the current input.

ANYONECANPAY set for SINGLE means that changes can be made to all outputs except the output with a matching index with the current input. All other inputs can be modified, added, and/or removed.

Scenarios

The table below shows a summary of use cases where these flags can be applied

Conclusion

In reviewing the bitcoin fundamentals necessary to explore the lightning network, I went down the rabbit hole of signature hash flags. These flags mark the parts of a transaction that are signed by a signature and provide flexible ways to construct transactions. I explained how to identify these flags from the anatomy of a DER signature, the 6 types of flags (including modifiers) that exist, and how some of these flags are applied to a transaction.

I would deeply appreciate any feedback you can provide. If you found this article helpful/useful or found factual misrepresentation, please do not hesitate to comment or contact me here or on Twitter @engb_os.

Note:

1. The || symbol is used to indicate concatenation
2. * SIGHASH flags should be a byte long although implementation serializes them to 4-bytes. Pieter Wuille provides a possible reason why this is the case here.

References

1. Antonopoulos, A. (2017). Mastering bitcoin: Programming the open blockchain
2. Song, J. (2019). Programming bitcoin: Learn how to program bitcoin from scratch
3. Rosenbaum, K. (2019). Grokking Bitcoin

They are “structures” we put in place to inform the compiler that objects borrowed remain, even after the borrowing object has been destroyed. We never really have to worry about lifetimes except when we create structs whose fields have borrowed data, or when we want to return borrowed data from a function.

I learned how to build a utility bitcoin library, in Python, in February, and set a goal to port the said library to Rust. In the course of doing so, I ran into a missing lifetime specifier error that questioned my knowledge of lifetimes.

This article is captures what I learned about lifetimes that helped me resolve my error. It presents a simple explanation of struct and function lifetimes.

Struct Lifetimes

Say, for example, that you have a structure that models a base dimension with two fields: length and breadth, as shown below

If another structure, a Tank, references an instance of BaseDimension, then we know that the instance of the BaseDimension struct must exist before the Tank struct is created and must remain after the tank is destroyed. We would need to reference the BaseDimension instance.

To define a lifetime for a structure, we use the following syntax:

For our tank example, we define a lifetime 'base for the BaseDimension as shown below, without which you would encounter a missing lifetime specifier error.

You can run a test of the code below on the rust playground. Here is a walk-through:

1. [Lines 2–5]: A BaseDimension struct is defined and has two fields: length and breadth
2. [Line 8]: A Colour enum with three (3) variances R, G, and B is defined.
3. [Lines 11–14]: A generic Tank structure with a lifetime of 'base is defined, having two fields: colour which is an enumeration of R, G, or B, and 'base which is a reference to a BaseDimension structure with a defined lifetime of 'base .
4. [Lines 16–21]: Within main, a base instance and a tank instance, with reference to the base, are created. The println! macro references the tank instance after it is called. The base and tank instances remain alive. Note that base20x40 will be alive for however long tank20x40 is, and can only be safe for destruction after the tank instance has been dropped.

Function Lifetimes

The second case to consider where lifetimes matter is with functions and returning borrowed values from them. The syntax is as shown below. Here we see the creation of two lifetimes 'lt_a and 'lt_b belonging to instances of TypeA and TypeB respectively. This function func returns a tuple of references to types TypeA and TypeB.

An illustrative example to show the use of lifetimes in a function is shown in Listing 2.

A walk-through of the example is listed below:

1. [Lines 2–6]: A City struct with three String fields: name , country , continent is defined.
2. [Lines 9–12]: A Hospital struct with a lifetime of 'city which will reference a borrowed instance of City
3. [Lines 14–16]: A function healthcare_centres with lifetime specifiers 'h and 'cityfor the parameters that are references to instances of &Hospital and City . Note how the struct lifetime is passed and the type of the return value: a tuple of borrowed objects.
4. [Lines 18–34]: Within main, instances of City and Hospital are created, with their references passed as arguments to healthcare_centre . The println! macros show how objects referenced by the function and tracked by their lifetimes outlive the function that called them.

The Rust compiler knows to save referenced instances in such a manner that it will outlive the function call. With the defined lifetimes, Rust can assess the relationship between the arguments passed to the function and the values returned in a safe way. We can tell that the reference(s) of the returned value from the function points to the arguments passed, and no where else.

Note:

• A special lifetime 'static is reserved by Rust for objects that must remain in memory until the program ends.
• Rust infers lifetimes. They (lifetimes) are only needed in defining functions or types.

Conclusion

Lifetimes are ways the compiler keeps track of what objects can/must remain alive as they are borrowed by other objects. This is how I like to think about them. If you liked this article and would like to see where I am applying some of the new Rust knowledge I have gained over the past two weeks, please check out bitlib — my attempt to port a bitcoin utility library to Rust.

Looking forward to any feedback I can get.

References

1. Blandy Jim, Orendorff, J., & Tindall, F, S, Leonora. (2021). Programming rust: Fast, safe systems development
   (2nd ed.) O’Reilly Media Inc.
2. Rust Programming: The Complete Developer’s Guide by Jason Lennon

Serialization is important because of the need to communicate different object data structures in efficient ways. In this article I will share some information about how public keys are serialized for transmission and use on the bitcoin network.

However, before serializing data into a binary representation, it is important to know what endianness is and how it affects the process.

Endianness

Endianness is byte-order and refers to the way computers order/organize bytes that make up the digital data in a computer’s memory (MDN, 2021) or the order in which bits are relayed over a channel. consider the hexadecimal representation of a 32-byte number 0x0A0B0C0D as shown below.

To access whatever data is encoded into this 32-byte word, the address of where this data is stored needs to be known. There are two ways a computer can access each byte in this word; the computer could access from the right end or the left end. These are known as big and little endianness. In the former, as shown in the figure below, the byte with the most significant byte (MSB) is saved to the highest address location while its least significant byte (LSB) can be accessed at the smallest address.

For little-endian representations, the reverse is the case. Here the LSB is accessed at the highest address while the MSB is accessed at the lowest address containing the 32-byte word. But why does this matter? Some bitcoin objects (the x- and y-coordinates of public keys) are serialized as big-endian and others (transaction version number, Merkle root, block timestamp) as little-endian. Because computers can be more efficient using the little-endian order as opposed to the big-endian, the byte-ordering for different objects must be taken into consideration when serializing and/or de-serializing them.

Public Keys

Public keys are points P(x,y) on the secp246k1 elliptic curve that bitcoin uses. They have x and y coordinates and are serialized using the Standards for Efficient Cryptography (SEC) — a known standard for Elliptic Curve Digital Signature Algorithm (ECDSA) public keys. For public keys, there are two SEC formats: uncompressed and compressed.

For the uncompressed format, a serialization of the point P(x,y) is created by doing the following:

1. Define a 1-byte prefix: 0x04
2. Add to the prefix the x-coordinate of P(x,y) encoded as 32-byte big-endian integer
3. Add to the prefix and x-coordinate the y-coordinate encoded as 32-byte big-endian integer

Given a simple integer representation of the coordinates of the public key, a function to serialize

Looking at Figure 3, we see that the uncompressed SEC format is 65 bytes long. The need arose to reduce the size of transactions and to conserve disk space on full nodes. Compressed public keys achieve this reduction by almost half the size of the uncompressed one (compressed public keys are 33 bytes long). This is done by some clever mathematics where just the prefix (encoding information about the evenness of the y-coordinate in 1 byte) and the x-coordinate (32 bytes) is stored.

The necessary background to understand the underlying mathematics about how compressed public keys are serialized can be found in [2]. The serialization process is:

1. Defining a prefix byte with a value of either 0x02, depicting an even y coordinate, or 0x03, depicting an odd y
2. Add to the prefix the x-coordinate of P(x,y) encoded as 32-byte big-endian integer

Base58 Format Addresses

Addresses are alphanumeric strings that users can share to receive bitcoin. An address, in the simplest case, is a string derived from a public key using two hashing algorithms: SHA256 and RACE Integrity Primitives Evaluation Message Digest (RIPEMD).

Given the byte and space savings of the compressed format of a public key, it is still considered too long and difficult to read. To address the length, readability, and security of public keys, the need arose to use an encoding format that could express more bits per character. Mixed alpha-numeric representations with a base greater than 10 can be used to make long characters more compact.

The hexadecimal (hex) encoding is one of such representations. For a 65-byte public key, the hex encoding has twice as many characters (see Figure 5) where 2 hex characters are needed to encode 1 byte. This makes for a 130-character long public key — bad for readability. As much as the hex representation is much shorter than a decimal representation, a Base 64 offers even more compactness.

A subset of Base 64, i.e. Base 58 encodes 6 bits/character and makes for a smaller (~87) characters set. Base 58 consists of all numbers (0…9), lowercase alphabets (a…z), and uppercase alphabets (A…Z). However, six (6) lookalike numbers/alphabets (0, O, l, I, -, _) and symbols were removed to form Base 58 and are used to encode addresses where bitcoins could be sent to.

Base 58 encoding is great because it offers the following benefits:

1. Compactness
2. Easy to read
3. Error detection

Listing 3 shows how to achieve compactness and better human readability for any bytes.

For error detection, Base58Check encoding format is used in bitcoin. This has built-in error-checking with a 4-byte checksum derived from the hashed SEC public key and added to the end of the SEC public key. The encoding process is as stated below:

1. A ‘version byte’ known prefix is prefixed to the SEC public key. This version prefix could be any one of the following — 0x00 (1) for bitcoin address, 0x6f (m or n) for bitcoin testnet address, 0x0488b21e (xpub) for extended public keys (not discussed in this article). The version byte helps with readability.
2. The checksum is computed by applying SHA256 hashing algorithm, twice, to the result above, extracting the first 4 bytes, and appending the result to the end (prefix + SEC public key + checksum). These bytes will help with error detection.
3. The result from 2 above is encoded with Base 58 function to address compactness.

A complete implementation with a simplified public key class is as shown below

Conclusion

This article explains endianness and how they affect serializing bitcoin objects, the SEC format for uncompressed and compressed public keys, and the base58check encoding of SEC addresses that improve readability, compactness, and security. I have been learning about bitcoin and found it helpful to conceive of serialization like I have outlined — with schematic representations of binary objects, and code. If you would like a more accurate implementation of a public key, you should get a copy of Programming Bitcoin by Jimmy Song or read it online.

If you found this article helpful or have recommendations to make it better, please do not hesitate to contact me. Happy reading.

References

1. MDN Contributors (2021, October 8): Endianness. https://developer.mozilla.org/en-US/docs/Glossary/Endianness. Accessed 28 February 2022
2. Song, J. (2019). Programming bitcoin: Learn how to program bitcoin from scratch O’Reilly Media.
3. Wikipedia (N.D.): Endianness. https://en.wikipedia.org/wiki/Endianness#Overview. Accessed 28 February 2022
4. Antonopoulos, A. (2017). Mastering bitcoin: Programming the open blockchain

But what are elliptic curves? What are finite fields? Why is ECC used in bitcoin?

To answer these questions, I need a better understanding of the foundational mathematics used in ECC. In this article I summarized what I learned about the following: elliptic curves, finite fields, groups, group law, and finite cyclic groups, the discrete logarithm problem (DLP) and elliptic curve discrete logarithm problem (ECDLP).

Elliptic Curves

One way to think about the equation that describes an elliptic curve is to consider a stack of oranges arranged in such a way that each level contains a square matrix of oranges forming a pyramid. For example, level 4 at the base of the stack will contain (4 x 4) = 16 oranges, level 3 will contain (3 x 3) = 9 oranges, level 2 will have (2 x 2) = 4 oranges, and level 1 (1 x 1) = 1 orange. Consider an interesting problem of rearranging an n-level stack of oranges into a single square matrix. Would it be possible to have a square matrix if there were 3 levels in the stack? To find out if this is possible we have to take the sum of the square of each level and then compute the square root. If the square root is an integer then we have a solution.

The equations above represents an elliptic curve. Given the knowledge of two points on the curve, the third can be found by the intersection of the elliptic curve and the straight line passing through the two known points.

Why is this equation and finding its solution important? To answer this we must understand what finite fields and groups are.

Finite Fields

A thing is said to be finite if it has definable/definite limits. Thus, finite fields are any fields (abstraction of numbers) with a finite set of elements. This means that there is a countable number of elements in the set representing the size/order of the set. Finite fields also have mathematically operations (addition and multiplication) that can be performed on the elements in the set such that the results of these operations are closed, i.e. are in the set. The following must hold true for finite fields:

1. These operators, addition (+) and multiplication (.), perform binary operations
2. The result of adding element c and d must be in the set, making addition closed.
3. There exists a neutral element 0 such that 0 + c = c
4. There exists the identity element 1 such that 1.c = c
5. There exist -c such that -c + c = 0
6. There exists the inverse of c such that

7. There exist prime fields where the order of the finite field is a prime number p where the elements in the set (mod p) of this field are {0, 1, 2, …, p — 1}

These conditions hold true because of modulo arithmetic that allow oversized results to wrapped around the divisor with the remainder falling within the boundary defined by the divisor. The snippet below shows how to implement a finite field element in Python.

Groups, Group Law, and Cyclic Groups

The combination of a finite field and an elliptic curve over this field gives rise to an interesting entity — a group. If you have a finite field and an elliptic curve defined over the field such that the rules for the addition of two points on the curve results in a third, on the same curve, then we have a group.

Groups typically have one law, which is point addition (+) that extends the necessary conditions of a finite field operation. These conditions are:

Additive Identity: Given a point P(x,y) on the elliptic curve, there exists an identity element 0(x,y) such that 0 + P = P. This identity element is known as the point at infinity.

Additive Inverse: Given a point P(x,y) on the curve, there exists another point P(x,-y) such that -P + P = 0 .

Point Addition: Given two points P₁(x₁, y₁) and P₂(x₂, y₂) on the elliptic curve, the third point P₃(x₃, y₃) is computed by calculating the slope (m) through P₁ and P₂, and substituting into the equation of the line that passes through either P₁ or P₂ and P₃. The equations are as shown below and hold true for cases where P₁ is not P₂.

Point Doubling: When P₁ = P₂, doubling is said to occur. Here P₁ + P₂ = P₁ + P₁ = 2P₁. The line formed is tangent to the point P₂ and passes through the third (technically second) point. The slope for this line is found by taken the derivative of the elliptic curve equation. The equation to compute y₃ remains unchanged however, the slope and x₃ equations change as shown below.

Scalar multiplication: What point doubling shows us is that we can perform a new kind of operation called scalar multiplication where P + P = 2P and 2 is a scalar multiple. This property is nonlinear and gives rise to two important considerations: finite cyclic groups and the discrete log problem.

Finite Cyclic Groups:

At some scalar multiple (n) of a select P, we compute the point at infinity nP = 0. For the select P, this means that there exists a finite set of multiples of P called a finite cyclic group. And plot of {P, 2P, 3P, 4P, …, nP} over a finite field is a scattershot of points showing the non-linearity of point addition in finite cyclic groups. This non-linearity is a great property in cryptographic systems because computing the scalar multiple of a select point is easy but predicting the value of the scalar given a point is quite difficult. This is the discrete logarithm problem (DLP).

A point on a simplified elliptic curve y² = x³ + ax + b can be implemented in Python as shown below.

Discrete Logarithm Problem

The generalized discrete logarithm problem in a finite field is one that defines the difficulty of finding an integer x within the range of 1 and p — 1 if there exists:

1. A finite cyclic group with an order of p — 1
2. A primitive element (α) which belongs to the finite cyclic group
3. A derivative element (β) such that αˣ = β

Computing the value of x is very hard if the parameters (p, α, β) are sufficiently large, even though computing the value of β is much easier.

Extending this, a DLP can be constructed with elliptic curves. Formally, the elliptic curve discrete logarithm problem (ECDLP) is the problem of finding an integer value e within the bounds of 1 and the number of points on the elliptic curve (which ~= the order of the finite cyclic group), such that the scalar multiplication of a primitive element G with e, i.e. eG, produces another point P on the elliptic curve.

In cryptographic systems e represents the uniformly selected random number that is the private key, G represents the generator point, P the derived public key.

Bringing it all together

Elliptic curves and the DLP are important because they form the primitives of ECC. With sufficiently large values for the order of the finite cyclic group (n), the generator point (G), and the order of a finite field (p), an elliptic curve discrete logarithm problem can be implemented for security- and privacy-conscious systems. The values bitcoin uses (see Programming Bitcoin, Chapter 3, Page 59) large enough to not have a successful attack against and known to provide long-term security with a time span of decades.

ECC, when compared with schemes in the same asymmetric algorithm family, provides the same security level with significantly smaller key lengths. For example, to achieve a security level of 128 bits, ECC requires 256-bit long keys, while 3072 bits is the minimum requirement for the same security level in others. Handling key lengths of 256 bits is much practical with better speeds than 3072 length keys.

Note:

1. If you are interested in the implementation of field and group operations in Python, here is a link to the code base for Programming Bitcoin. An implementation in C++ is contained in Chapter 9 of Pro Cryptography and Cryptanalysis.
2. If the resources above are too exhaustive, you can check out my repository. It has a much smaller footprint and contains code written alongside learning from Programming Bitcoin.

References

1. Song, J. (2019). Programming bitcoin: Learn how to program bitcoin from scratch O’Reilly Media.
2. Hankerson, D., Menezes, A., & Vanstone, S. (2004). Guide to elliptic curve cryptography Springer.
3. Paar, C., & Pelzl, J. (2010). Understanding cryptography (2. corr. printing ed.). Springer.
4. Mihailescu, M., Iulian, & Nita, S., Loredana. (2021). Pro cryptography and cryptanalysis with C++20: Creating and programming advanced algorithms Apress.

Good software, used by millions of people around the world, is almost always built by a team. Collaborating with other developers and designers to achieve the goals of the given tasks/projects is why I have decided to intern with Zuri. An organization whose long running partnership with HNG offers professionals with prior programming experience the opportunity to build software and connections.

My goal is simple. Finish the HNGi8 internship with another portfolio-worthy project whose backend is built mainly with Javascript. I believe that by completing each challenge for every stage of this program, I would apply the base knowledge I have gained learning programming, version control, deployment, and containerization. In achieving this, I expect to build good connections with fellow interns as we journey together.

In the event that you are looking to transition to software development like I have, these are recommendations of the best resources to level up:

1. Programming: Python is a popular language, with a clean, uncluttered style that makes it easy to read and learn. To gain intermediate proficiency, I highly recommend Jose Salvatierra’s “The Complete Python Course | Learn by Doing”. It is beginner-friendly and project-focused. You get the feeling of having a deep understanding of the language upon completion. For Javascript, Colt Steele and Stephen Grider’s “The Modern Javascript Bootcamp Course” comes highly rated on Udemy. It is split in two broad sections, where the first is focused on understanding the syntax of the language, and the second on building projects with it.
2. Versioning: Version control with git is a mandatory skill all software developers must have. The knowledge of which underpins collaboration in team projects. LinkedIn Learning’s “Git Essential Training: The Basics” is a good place to start. The course is taught by Kevin Skoglund, covers the basics, and introduces new learners to the Git Workflow — a recommended approach to using git effectively.
3. UI/UX Design: Design analyses user interface and experience for products. Figma is tool that has gained mainstream popularity in recent years, appearing to be the defacto standard for mobile and web products. A good place to start learning is Andrei and Daniel’s Udemy course titled “Complete Web & Mobile Designer in 2021: UI/UX, Figma, +more”
4. Scripting: Looking to add structure to your mobile and web products? HTML does just that. It is an easy to learn scripting language that is the foundation of all web applications. A good place to start is LinkedIn Learning’s “HTML Essential Training” by Jen Simmons.

Please do not hesitate to message me if you want more information about the recommendations I have made, other courses you can take, and or general updates about my progress with Zuri and HNG.