Browsed by
Tag: Bitcoin graphical environment

Scripts and stacks

Scripts and stacks

Personal note, Many things happened in past two months the required my full attention. I hope to resume a steady flow of posts in coming days.

Review

In the last post we’ve talked about one the biggest bitcoin misconception – The idea that transaction actually moves coins from one wallet to another. The truth is that transactions are nothing more that statements. These statements always points to a previous statement (that in turn point to an even older statement and so on), and usually these statement also specify an amount of coins that the current owner is wishing to transfer. The statement also contains a riddle, or an equation that needs to be proofed, and mostly, the key to proof this equation will require the use of the private_key that is associated with the recipient bitcoin address.

level3

Pay attention, even though Bob will be required to use his own private_key to proof that he indeed can solve this problem, the private_key still won’t be available to any one.

 

Now let’s look for a second at this transaction message. We’ve already learned how to create a bitcoin message (see this section about Version message and this one about headers). We just need to make sure that all of the fields are filled in accordance the protocol rules. Just like filling a form. You can find a complete list of the fields that needs to be filled in the bitcoin developers documentation.

 

 

Most of the fields are quite straight foreword. I might still create another post in the future with detail instructions on how to fill all the fields, but this isn’t really the topic of this post. This post deals with one of bitcoin more fascinating aspects – The riddle that Alice place in her statement. The riddle that only Bob can solve -The script.

 

(You just can’t wait to create your own transaction? you’re more than welcome to watch my videos on creating bitcoin transaction)

Scripts, what is it?

Scripts is a computer language. In more detail, it’s a set of predefined words that are agreed upon. Every node that follows the rules specified in the bitcoin protocol will know how to read, interpret and implement these words. Because bitcoin messages are basically nothing more then a string on bytes, these words are not written in plain English, rather are translated to OP_CODEs. That way, we can send our message as a string of bytes, and the receiving node will know that these bytes represent some instructions. (Important note, The receiving node will only treat this bytes as instructions only if they appear inside one of the script field.)

Here’re selected few:

Word Opcode Hex Input Output Description
OP_1ADD 139 0x8b in out  1 is added to the input.
OP_1SUB 140 0x8c in out 1 is subtracted from the input.
N/A 1-75 0x01-0x4b (special) data The next opcode bytes is data to be pushed onto the stack
OP_MIN 163 0xa3 a b out  Returns the smaller of a and b.
 OP_SHA256  168  0xa8  in  hash The input is hashed using SHA-256
OP_EQUAL 135 0x87 x1 x2 True / false Returns 1 if the inputs are exactly equal, 0 otherwise.

The original list included around 200 of these words, but currently most nodes will only support few dozes of these words. Using these few words we can create many “riddles” or state many conditions to claim the coins in our transaction message.

For example I can add the following string of bytes as my script.

0x01 0x8b 0x87 0x02 0x87

<1> <OP_1ADD> <2> <OP_EQUAL>
  1. It will take the number 1.
  2. Use the OP_CODE OP_1ADD to add 1 to it -> The output of this OP_CODE will be 2.
  3. Use the OP_CODE OP_EQUAL to make sure if the result is equal to 2. -> The output of this OP_CODE will be True.

A word of caution though, most nodes not only refuse to accept most of these OP_CODEs, they will even refuse to accept most non-standard  scripts, mainly because they want users to use standard transactions. Many nodes will not only refuse to accept a transaction with a non standard script, they’ll also refuse to transmit these transactions to other nodes.

 

Stacks

You might’ve already noticed that this script language can only be written as a list of operations. Unlike other high level languages (such as python for example) Scripts can only be used in a predefined order. This type of structure is called stack, because we’re stacking variables and data on top of each other. But not only we’re stacking them, using the stack structure also means that they’ll be processed in accordance to the order in which they were stacked.

In our previous example, the integer 1 was the first item in our stack. Then came the operation OP_1ADD which took that item as its input, processed this item by adding 1 to it, and than giving the output 2. Now the number 2 is stacked BELLOW the integer 2.

<1> <OP_1ADD> <2> <OP_EQUAL>

<2> <2> <OP_EQUAL>

The node recognize the OP_CODE <0x02> as the integer 2, so it moves on to the next item in our stack – the OP_CODE OP_EQUAL. This operation input is the two items that are directly bellow it and compere the two. If both are equal, it will return True.

<True>

 

This example code can’t be used with a standard bitcoin transaction, it’s only meant to give you a general feel on how scripts works.

You can find an example of a real transaction over here:

 

 

Give it a try with bitpy

One of bitpy newest feature is the ability to create stacks and see them in action in real time. Mind you, only few OP_CODES are currently implemented, but it might still give you a feel on how stacks works.

Example of stack using bitpy
Example of stack using bitpy

 

Simple stack architecture with python

Stack architecture can easily be implemented using arrays. After all, it’s nothing than an array of objects (variables, operations, results etc’).

In our bitpy project, under Utils/OpCodes/Codes.py I’ve created a stack class. In its most basic form, this class will only create and empty array upon initialization, followed by  2 methods only.

class Stack():

    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        elm = self.items.pop()
        return elm
  1. push(item) append new item to the array
  2. pop(item) remove the topmost item in my array.

This should be enough to create a very basic stack class. Still, I’ve added few more methods.

class Stack():

    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        elm = self.items.pop()
        return elm

    def size(self):
        return len(self.items)

    def printStack(self):
        display = ""
        for items in self.items:
            items = str(items)
            if len(items) > 5:
                display += " " + "<"+ items[:5] + "..." + ">"
            else:
                display += " " + "<" + items + ">"
        return display

    def clear(self):
        self.items.clear()

The isEmpty method will check if our stack array is empty.

The size method will give us the size of the array.

The printStack will provide us with a visual representation of our array. Pay attention that I’ve limited the size of each item to only 5 characters so that items such as hashed messages, bitcoin addresses, keys etc’ won’t take the all screen.

The clear method will remove all items from our array.

Using this methods we can easily start implementing more advanced OP_CODE to our stack array.

def OP_DUP(self):
    elm = self.pop()
    self.items.append(elm)
    self.items.append(elm)

def OP_HASH160(self): #saved as string!
    self.push(Utils.keyUtils.keys.generate_hashed_public_key_string(self.pop()))

def OP_EQUAL(self):
    elm1 = self.pop()
    elm2 = self.pop()

    if elm1 == elm2:
        self.push(1)
    else:
        self.push(0)

def OP_VERIFY(self):
    top = self.pop()
    if top == 1:
        self.push(1)
    else:
        self.push(0)

def OP_RETURN(self, input):
    self.push(input)

 

Keys, addresses and hashing

Keys, addresses and hashing

A key pair is one of the greatest tools that are used in Bitcoin, but it might be a little unintuitive at first. Don’t worry, you’ll get it!

There’s also a short video I made a few months ago that describes the basics of keys. It doesn’t completely corresponds to our current project, but it might provide you with another point of reference. You can watch it over here – Bitcoin python tutorial for beginners – keys and address.

 

One way function

The name “one way function” is quite self explanatory. These function are very easy to solve in one way but almost impossible to invert. Giving function f, and the input x, I can easily calculate the result y.

f(x) = y <- easy to solve

But given the result y, and the function f, It will be almost impossible to find x

f(?) = y <- almost impossible to guess.

The Bitcoin protocol define the use of some of these one way functions (SHA256, ripmed, ECDSA and murmurhash. More functions are being tested and might be used in the future).  Each one of these function has its own place in the protocol. Some functions will be used more then once and/or will be combined with another function to achieve even a grater level of security. For example, signing a message (usually a transaction message) will be done using the SHA256 function, SHA256("hello!"), finding the checksum of the message payload will be done using the SHA256 function twice SHA256(SHA256(message)).

  • Some people have hard time to accept the concept of “hard to guess”, they feel it’s too ambiguous. Well, technically an extremely powerful computer might be able to iterate through all possible results until it will find the right one (this is called brute force), but in practice, it will take a very – very long time. Trying to brute force the result of a SHA256 function on a 32 bytes message will take about 10^65 years. The age of the universe is only 1.4*10^9 year. I think it’s good enough security.
It’s easy to get the result y of function f for a giving x. But almost impossible to tell what the original input was.

 

Mathematical trapdoor and key pair

Mathematical trapdoor is a special type of one way function. The main difference is that in mathematical trapdoor we may also use few extra pieces of information called keys. Bitcoin uses the mathematical trapdoor function ECDSA or Elliptic Curve Digital Signature Algorithm, to produce two keys, or a key pair -A private key, and a public key – Both keys will always come in pairs! there cannot be a public key that matches two different private keys and vice versa!

The private key is used to solve (sign) the function f for message x. The result is the signed message y.

f(private_key, x) = y <- easy to solve

Now I have two messages. The original message x, and the signed message y. I want to prove that I’m the one who signed the original message x, that I’m the owner of the private key. But I don’t want to give my own private key. Anyone who have my private key will be able to sign in my name on other messages as well. So I’m using the public key. The public key can only be used to prove the solution of the function, but it cannot be used to sign messages

f(public_key, x) = y <- easy to prove

f(public_key, x) = null <- I can't sign message x with the public key. only with the private key

  • Pay attention that when we’re using the public key we’re just proving the equation, not solving it.

Here’s a simple numeric example I found on the wikipedia page on mathematical trapdoor:

An example of a simple mathematical trapdoor is “6895601 is the product of two prime numbers. What are those numbers?” A typical solution would be to try dividing 6895601 by several prime numbers until finding the answer. However, if one is told that 1931 is one of the numbers, one can find the answer by entering “6895601 ÷ 1931” into any calculator. This example is not a sturdy trapdoor function – modern computers can guess all of the possible answers within a second – but this sample problem could be improved by using the product of two much larger primes.

 

Let’s see an example:

Step one – create a key pair:

Create key pair using the ECDSA function and some random numbers
Create key pair using the ECDSA function and some random numbers

Step two – sign a message with the private key:

using the private key and the ECDSA algorithm
using the private key and the ECDSA algorithm

Step three – send the original message alongside the encrypted message and the public key

3 items are needed to validate the message. The public key, the original message and the encrypted message
3 items are needed to validate the message. The public key, the original message and the encrypted message

The code

In our project we’ve defined the Key class under Bitpay/Utils/KeyUtils/keys.py. This class contains all the necesery steps that are required in order to generate a private key, trnsform that private key to a public key and then create a Bitcoin address out of that public key.

step one – create (or receive) the private key

The first thing that we’re going to do is to create our private key. The private key is defined as  a random 32 bytes uint. Our class begins with a simple check. If the user initialize the Key class with an already existing private key, that private key will be saved into self.private_key. Otherwise, we’re using the urandom function in the os module to create a random 32 bytes long number.

def __init__(self, private_key=0):
    if private_key == 0:
        self.private_key = os.urandom(32)
        self.printable_pk = str(binascii.hexlify(self.private_key), "ascii")
    else:
        self.printable_pk = private_key
        self.private_key = binascii.unhexlify(private_key.encode('ascii'))

You might’ve noticed that we’ve also created a printable_pk variable. This variable will store the private key in hexadecimals. This way it is easier to store, copy and/or print the private key.

 

Step two – Use the private key to initialize the signing function

After we got our private key it’s time to use it initialize our ECDSA function. This step is similar to declaring our function f with the private key pr_k.

self.sk = f(pr_k, )

We’re defining the variable self.sk (for Signing Key) and use SigningKey.from_string from the ECDSA module with two arguments, the first one is our self.private key, and the second one is the curve (We haven’t talked about the curve yet, But it represent the mathematical part of our function. This is too advance mathematics so we won’t go into it in this project. But for now we just need to know that the Bitcoin protocol requires us to use the ECDSA function with the mathematical curve SECP256k1)

self.sk = ecdsa.SigningKey.from_string(self.private_key, curve = ecdsa.SECP256k1)

 

Step three – Use the initialized function (self.sk) to get the public key

Now that we got our signing key, we can use it in order to create our public key.

self.vk = self.sk.verifying_key

We’re defining a new variable called self.vk which will hold the verifying key, or the public key that can be sent alongside the signed message and the original message. This key will be used to verify that the message was indeed signed by the owner of that public key. And since every public key matches only one specific private key, it also proves that the one who signed the message also possess the corresponding private key.

 

Step four – Formatting the public key.

The variable self.vk holds the public key that will be used to verify our signed messages. But the Bitcoin protocol requires that we’ll represent this public key in couple of different formats.

The following chart from the Bitcoin wiki site shows the way the public key should be formatted:

Converting the public key to Bitcoin address
Converting the public key to Bitcoin address

 

The first line is the real public key, or in our case the verification key self.vk

this is the real public key - but we can't send it like this. We need to do dome formatting
this is the real public key – but we can’t send it like this. We need to do dome formatting

 

The second line tells us that we need to inser the byte 0x04 at the beginning of our public key

self.public_key =  b"04" + binascii.hexlify(self.vk.to_string())

We’re using the function to_string in order to display the variable self.vk  as a string. Then we convert it to hexadecimals so it will be easier to append the byte 0x04.

This is the public key in Bitcoin terminology. Usually, When looking for the public key in signed transactions, that's what it will look like
This is the public key in Bitcoin terminology. Usually, When looking for the public key in signed transactions, that’s what it will look like

 

The third line tells us to hash the public key twice. once using the SHA256 function, and then again using the ripemd160 function.

ripemd160 = hashlib.new('ripemd160') # <-initializing the ripemd160 function 
ripemd160.update(hashlib.sha256(binascii.unhexlify(self.public_key)).digest())
First hashing the public key using the SHA256 function. Then the result is hashed with the ripemd160 function
First hashing the public key using the SHA256 function. Then the result is hashed with the ripemd160 function

The forth line tells us to add another byte at the beginning of the hashed key.

We're working with the main network so we'll add the byte 0x00
We’re working with the main network so we’ll add the byte 0x00

This is the network ID byte which is used to prevent us from using keys and addresses that were generated in the test network, in the main network (and vice versa). In our example we’re using the main network, so the byte we’ll add will be 0x00.

self.hashed_public_key = b”00″ + binascii.hexlify(ripemd160.digest())

In Bitcoin terminology, the result is the hashed public key. This format is used mostly when creating a transactions.

 

The fifth (and sixth) line tells us to take our hashed public key and hash it again, twice, using the SHA256 function. The first 4 bytes of the result will be the checksum.

self.checksum = binascii.hexlify(hashlib.sha256(hashlib.sha256(binascii.unhexlify(self.hashed_public_key)).digest()).digest()[:4])
The checksum is the first 4 bytes
The checksum is the first 4 bytes

 

The seventh line creates the Bitcoin address in its binary form by appending the hashed public key with the checksum. This is a valid Bitcoin address, but it still need to go through one more process before it can be used with most Bitcoin wallets.

self.binary_addr = binascii.unhexlify(self.hashed_public_key + self.checksum)

 

The last line Finally we’ve reached the end point. There’s only one more thing we need to do before we can get the standard Bitcoin address and that is to convert the binary code of the address into a base58 string. The idea behind this conversion is quite simple. In order to reduce human errors, it was decided that some characters will be omitted from the standard Bitcoin address. characters like capital O, the number 0, lower case l and upper case I, as well as many more characters were omitted.

The final address represented in base 58.
The final address represented in base 58.
self.addr = base58.b58encode(self.binary_addr)
  • You might need to install the base58 module using the command pip install base58.

 

User interface

We’ve also added a tab to our graphical user interface which might help. You can use it to see the public key, hashed public key and Bitcoin address or any given private address.

The user interface for the keys can be found in the second tab
The user interface for the keys can be found in the second tab
Connection part three – Receiving messages

Connection part three – Receiving messages

In the previous posts, all that we’ve done was to construct and send messages to another node on the network. In this post, we’ll see what happens to incoming messages.

First stop – The ReceiverManager:

class ReceiverManager(Thread):
    def __init__(self, sock):
        Thread.__init__(self)
        self.sendingQueue = Utils.globals.sendingQueue
        self.sock = sock
        self.ping = ""

        self.outfile = open("data_received_from_node.txt", 'w')

    def run(self):
        while True:
            try:

                # get only the header's message
                header = self.sock.recv(24)

                if len(header) <= 0:
                    raise Exception("Node disconnected (received 0bit length message)")

                headerStream = BytesIO(header)
                parsedHeader = HeaderParser(headerStream)

                # get the payload
                payload = self.recvall(parsedHeader.payload_size)
                payloadStream = BytesIO(payload)

                self.manager(parsedHeader, payloadStream)

            except Exception as e:
                print(e)
                break

        print("Exit receiver Thread")

The receivermanager always runs in the background, checking our Thread for any incoming packets. Once it receives a packet, it will immediately cut its first 24 bytes.

header = self.sock.recv(24)

The first 24 bytes are the header. If you remember from this post, every Bitcoin message will starts with header, and the header is always exactly 24 bytes long.

 

The first 24 bytes are the header. The rest is the payload
The first 24 bytes are the header. The rest is the payload.

This header is now parsed as a string of bytes and passed to the HeaderParser class in Bitpy/Network/HeaderParser.py

headerStream = BytesIO(header)
parsedHeader = HeaderParser(headerStream)

 

Second stop – The HeaderParser class:

The HeaderParser class takes the first 24 bytes as a long string of bytes, and then it reads them in the same order that we’ve seen before.

Size (Bytes) Name Data type Description
4 Start string char[4]  The network identifier
12 Command name char[12]  The name of the command.
4 Payload size uint32 Len(payload)
4 Checksum char[4]  SHA256(SHA256(payload))[:4]

First 4 bytes for the Start string (or Magic number), another 12 bytes for Command name, the next 4 bytes are the Payload size and the last 4 bytes are the checksum.

4 bytes for starting string. 12 for command name. 4 for payload size and 4 for checksum
4 bytes for starting string. 12 for command name. 4 for payload size and 4 for checksum
class HeaderParser:
    def __init__(self, header):  # Packets is a stream

        self.magic = read_hexa(header.read(4))
        self.command = header.read(12)
        self.payload_size = read_uint32(header.read(4))
        self.checksum = read_hexa(header.read(4))

        self.header_size = 4 + 12 + 4 + 4

    def to_string(self):
        display = "\n-------------HEADER-------------"
        display += "\nMagic:\t %s" % self.magic
        display += "\nCommand name	:\t %s" % self.command
        display += "\nPayload size	:\t %s" % self.payload_size
        display += "\nChecksum	:\t\t %s" % self.checksum
        display += "\nheader Size:\t\t %s" % self.header_size
        display += "\n"
        return display

We’ve also defined the to_string function which basically makes it easier to print a human readable version of the message header.

You might’ve noticed that currently our code just accept the checksum field from the received message without checking it. This is of course a security flaw in our code. The checksum filed is there to help us verify the authenticity of the message. That is one of the ways we can make sure that no one tempered or changed the message on its way from the sender node to our node. But for the time being we’ll assume that the message is indeed authentic and we’ll accept the checksum as is.

 

Third stop – Back to the ReceiverManager:

Now that we have our header, it’s time to get the payload. The size of the payload was defined in the header of the message. We need to cut that amount of bytes from our incoming packets, just as we cut the first 24 bytes of the header. There’s however one extra step in our code. Instead of using the built in sock.recv function (as we did for the header) we’ve decided to implement our own recevall function. The rational was that since we have no way to predetermine the size of the payload, and since the built in sock.recv can’t handle large packets of unknown size, it would be wiser to break the payload into smaller parts and append them together. This has nothing to do with the Bitcoin protocol, it’s only our way to make sure that the code will properly handle large messages.

def recvall(self, length):
    parts = []

    while length > 0:
        part = self.sock.recv(length)
        if not part:
            raise EOFError('socket closed with %d bytes left in this part'.format(length))

        length -= len(part)
        parts.append(part)

    return b''.join(parts)

So now, after we’ve cut the required amount of bytes that represents the payload of our message, and we have both our header (which was already parsed) and our payload (yet to be parsed), we’ll pass them both to the receivermanager manager function.

 

Forth stop – Manager:

    
def manager(self, parsedHeader, payloadStream):

    command = parsedHeader.command.decode("utf-8")
    message = {"timestamp": time.time(), "command": command, "header": parsedHeader.to_string(), "payload": ""}


    if command.startswith('ping'):
        ping = Ping.DecodePing(payloadStream)

        pong = Pong.EncodePong(ping.nonce)
        packet = PacketCreator(pong)
        self.sendingQueue.put(packet.forge_packet())

        message["payload"] = str(ping.nonce)
        self.display(message)

    elif command.startswith('inv'):
        inv = Inv.DecodeInv(payloadStream)
        message["payload"] = inv.get_decoded_info()
        self.display(message)

    elif command.startswith('addr'):
        addr = Addr.DecodeAddr(payloadStream)
        message["payload"] = addr.get_decoded_info()
        self.display(message)

    elif command.startswith('pong'):
        pong = Pong.DecodePong(payloadStream)
        message["payload"] = pong.get_decoded_info()
        self.display(message)

    elif command.startswith('version'):
        version = Version.DecodeVersion(payloadStream)
        message["payload"] = version.get_decoded_info()
        self.display(message)

The manager function does a very simple thing. It checks the command of the message (the command is part of the header) and then it sends the message payload to be parsed by the corresponding functions. For example. If the manager sees that the command is «pong», it will use the decodepong method in Bitpay/Packets/control_messages/pong.py to extract the desire fields out of it. (You can read more about «pong», «ping» and «verack» messages in this post.).

 

Divergence

We have our pared message, both its header and payload. And now we need to decide what to do with them. For some messages this might be the end of the line. There’s nothing more we can do with them. Some might require us to act. «ping» message should be answered by a «pong» message, transactions should be checked and relayed (We’ll talk about transactions in later posts), «version» messages should be acknowledged by sending back a «verack» message.

A major part of learning the Bitcoin protocol is learning how each and every message should be dealt with. Which fields of information it contains and what is the meaning of this information. We’ve already talked about some of the messages in previous posts  (see here for «ping», «pong» and «verack» messages, and here for «version» message.) and as our project will have more features implemented, so we’ll discuss other type of messages and how to deal with them.

User interface

User interface

The best way to make our code really useful is to add user interface to it. There is a lot of this that can only be taught and understood by looking at the code itself, bu there are also many things that the average user can learn about the Bitcoin protocol that can be explained in a more “human friendly” way. An that is way Alexis and I have decided to add a Graphical User Interface (GUI) to our project in hope that in the future we can create a full Bitcoin graphical environment.

We’ve added a new folder to hold our GUI files, the UI folder. This folder contains 3 implementations. The first one uses the Tkinter module, the second uses the pyQt module and the third is a simple command line interface (And this is why we’re calling this folder UI and not GUI). We still haven’t decided on the final implementation bu we believe that we’ll eventually go with only the pyQt implementation, basically because this one looks the best!

 

This is what it looks like at the moment:

Bitcoin graphical environment
The user interface of bitpy.

This is our basic design, At the bottom there’s a list of all the messages you can send: «version», «verack» and «ping»   (More messages will be added soon). The left side keeps a record of all of the incoming messages, in the order in which they were received. Once we choose one of these messages, we can see at the right panel a display of the parsed message. The header and the payload.

Remember! this is just our first draft, but we’re quite proud of it. Little by little our project shows more and more potential.

 

installing dependencies

Because we’re using pyQt5, you might need to install the pyQt5 module on your machine. The easiest way to do so will be to use the commend:

pip install pyqt