purpleprotocol / purple_prototype Goto Github PK

In order to prevent things like #48 we should add a continuous integration pipeline for windows as well. The best thing for this is appveyor.

A packet for forwarding transactions. Related to #11.

Related to #53

The virtual machine provides indexed heap access via a two dimensional array of 256 elements each. Should we attempt to validate against accessing unallocated memory? Is this even possible with this model?

Otherwise we can just return an exception at runtime and stop execution on bad accesses but the other option would be much more desirable since it would provide total memory safety.

Related to #13

Any other packet besides Connect must be encrypted and then wrapped in a header which has the following fields. If you believe we need another field besides these, please suggest it in the comments.

• Version - The version of the network layer - u8
• CRC32 - CRC32 checksum - u32
• Network hash - Hash of the network name - u64

For example, when pushing a value to a stack which is popped from another stack.

The algorithm for the connection handshake is the following:

1. The Client establishes a TCP connection to the Server.
2. The Client constructs a shared key from the public key of the Server.
3. The Client attaches the shared key to a Connect packet which it sends to the Server.
4. When the Server receives the connect packet, it computes its shared key and attaches it to a Connect packet.
5. The Server sends the packet to the Client.
6. Peers are now connected and their communication channel is encrypted.

Even though the image builds just fine, when starting the docker image, we receive a dreaded segfault.

This article suggests changing allocators because jemalloc may be the culprit: https://jvns.ca/blog/2017/12/23/segfault-debugging/

An OpenShares transaction lists a shareholders controlled account in the ledger. The validation logic for an OpenShares transaction must do the following:

• Check that the creator address exists.
• Check that the creator address has the amount listed to be initially sent to the account's balance.
• Check that the creator address has the amount listed to be paid as the transaction's fee.
• If the transaction's fee is paid in the same currency as the one being initially transferred, check that the creator address has the summed amounts.
• Check that the representing stock hash is correctly computed.
• Check that the nonce listed in the transaction is correct.
• Check the validity of the shares object.
• Check the validity of the share map object in relation to the shares object.

An OpenContract transaction deploys a contract to the blockchain state. The validation logic for an OpenContract transaction must do the following:

• Check that the deployer address exists.
• Check that the code is valid.
• Check that the issuer address has the amount listed to be initially sent to the contract's balance.
• Check that the issuer address has the amount listed to be paid as the transaction's fee.
• If the transaction's fee is paid in the same currency as the one being initially transferred, check that the issuer address has the summed amounts.

Implementing the base consensus mechanism (without transaction validation, just event processing) requires:

• Creation of the causal graph based on a random set of events.
• Analysis of the causal graph i.e. counting votes, constructing candidate sets, figuring out - byzantine actions, etc.
• Event garbage collection i.e. discarding not included events.
• Conflict resolution via a deterministic hashing function i.e. jump consistent hashing.
• Easy Chain logic.
• Hard Chain logic.
• State Chain logic.
• Glue code between chains and validator pool logic.

Memory model

The memory of the virtual machine is a 256 long multi-dimensional array. Each element in the array is another array which has the length of 256. A memory address is then formed out of two bytes which are the coordinates of the element's location in the multi-dimensional array.

Limitations

Instead of using a growable model, where the memory can be increased indefinitely by being bought with gas, the virtual machine will use instead a fixed memory size and thus remove the gas costs for allocating to the heap.

If an entry in the memory can have at maximum 8 bytes (an i64 integer), and we have a total of 256^2 entries, then we say that the total heap size of the virtual machine is roughly 524kb. This is more than enough for financial software (they had way more complex software running on computers with no more than 5kb of memory back in the 70s).

Instructions

In the virtual machine spec, there are 14 load instructions:

i32Load               = 0x15,
i64Load               = 0x16,
f32Load               = 0x17,
f64Load               = 0x18,
i32Load8Signed        = 0x19,
i32Load8Unsigned      = 0x1a,
i32Load16Signed       = 0x1b,
i32Load16Unsigned     = 0x1c,
i64Load8Signed        = 0x1d,
i64Load8Unsigned      = 0x1e,
i64Load16Signed       = 0x1f,
i64Load16Unsigned     = 0x20,
i64Load32Signed       = 0x21,
i64Load32Unsigned     = 0x22

And 9 store instructions:

i32Store              = 0x23,
i64Store              = 0x24,
f32Store              = 0x25,
f64Store              = 0x26,
i32Store8             = 0x27,
i32Store16            = 0x28,
i64Store8             = 0x29,
i64Store16            = 0x2a,
i64Store32            = 0x2b

Load operations

Each load operation receives as arguments 2 coordinate bytes, as mentioned earlier. A load operation will take the item at the memory location and then it will push it to the operand stack.

Store operations

Store operations receive as arguments 2 coordinate bytes and pops an item from the operand stack and then places it at the memory location.

Related to #53

Related to #23

This can be easily done by adding a transaction api to PersistentDb over the rocksdb transaction api.

Also, this is where atomic writes should happen: https://github.com/purpleprotocol/purple/blob/master/src/chain/src/chain.rs#L331

This can be done in mainly two ways:

1. IGD/UPnP protocol - This is the easy but not preferred way since the protocol has been found to have vulnerabilities in the past and it is in general a bad security practice to enable UPnP on a router.

2. TCP Hole Punching - This is hard to do and introduces more complexity at the network layer. However this method is preferred since we do not need UPnP or open ports.

Implementing Hole Punching

In order to do this we need to have a special type of node which acts as a connection relay. The relay is required to have the 44034 port open. We also require SO_REUSEADDR set to true which fortunately is already handled by tokio by default on unix.

Also, I cannot seem to find any information on preventing port reuse in tokio on windows i.e. no way to set SO_EXCLUSIVEADDRUSE to true. We should investigate this.

Connection Protocol with Hole Punching

In order to perform hole punching, the connecting peers must first and foremost know their external ports. The protocol for two peers behind NATs connecting is the following:

1. Peer1 connects to a Relay.
2. Peer1 asks the Relay about its peer list by sending a RequestPeers packet.
3. The Relay sends a SendPeers packet to Peer1 which includes the information of Peer2.
4. Peer1 chooses to connect to Peer2 so it sends Peer2 a RequestConnection packet through the Relay which also forwards the internal port of Peer1 to Peer2.
5. Peer2 sends Peer1 an AcceptConnection through the relay.
6. The peers, now knowing their external ports, perform hole punching.
7. Peer1 and Peer2 now are connected through TCP.
8. Peer1 and Peer2 perform the connect handshake as usual.

We should implement an overlay mechanism to allow peers to talk to other peers which are not directly connected between each other.

This can be done by using a kademlia like protocol. However, in order to account for packet loss, we need a fallback mechanism.

Related to #57

Preventing packet loss and adversarial routing

This is done by routing packets in parallel using a k parameter like 20-25. We also add a sibling rule such that a node requires to know the siblings of its closest nodes if they fall within a sibling range and we forward packets to them as well.

Preventing eclipse attacks

The packet loss mechanism relies on the fact that honest nodes have siblings that have at least a sub-set that is honest. However, eclipse attacks prevents this.

The mechanism against this is simple: We do not allow arbitrary node ids in the overlay.

Disallowing arbitrary node ids

Normally a node id in the overlay is hash(PubKey).

We extend this rule to the following: hash(BlockHash + NodeId), where BlockHash is the latest hash of the block that has been mined on the HardChain starting with the genesis block.

Now, imagine the following scenario: An attacker does a timing attack by waiting for enough blocks to be mined that he has generated enough identities to launch a full-scale attack. The above solution only delays this.

The solution to this problem is to trigger a re-route every n blocks i.e. nodes will generate a new id and generate a new routing table. The lower the n, the more reliable the mechanism would be but we would need to re-route nodes more often.

Before we do #8 it would be nice if we had some benchmarks that we can compare it against.

There are 4 opcodes that are related to arrays. These are:

Fetch                 = 0x2c,
Grow                  = 0x2d,
ArrayPush             = 0x2e,
ArrayPop              = 0x2f

Fetch opcode - 0x2c

The Fetch opcode receives one byte as argument: the index of the fetched item in the array. Fetch will pop the array from the operand stack, fetch the element at the given index and then push it along with the array back to the operand stack.

Grow - 0x2d

The Grow opcode pops an array from the operand stack, it will grow it to the next greater sized array type and it will push it back to the operand stack. If the array is maximum sized, this operator makes the vm trap.

ArrayPush - 0x2e

The ArrayPush opcode pops an array and an item from the operand stack, it will push the item into the array and then it will push back the array to the operand stack.

ArrayPop - 0x2f

The ArrayPop opcode pops an item from an array on the operand stack and pushes it to the operand stack.

Related to #53

This packet is sent by a Relay node during NAT traversal and wraps either an RequestConnection or AcceptConnection packet. It also must contain the information of the port of the node which sent the wrapped packet.

Problem

Currently, the virtual machine parses bytecode during execution. This adds a lot of redundancy/overhead since for each subsequent jump, the parsing has to be done all over again.

Solution

The solution is to parse the bytecode exactly once, prior to execution. We can create an internal Intermediate Representation for the bytecode which contains all of the metadata required for jumps that is otherwise calculated at runtime.

The stored bytecode is in SSA form and this serves us well for validation but it is slow to execute. We can use non-SSA form when designing the internal IR since this yields much faster execution.

When interfacing with the outside world it is always nice to use human friendly strings such as in the case of dealing with JSON data. In order to do this we should implement custom serde serialize/deserialize traits on the Hash structures which convert it to hex.

This can be really handy for testing the network and consensus parts of the code.

Currently, multi-signature functionality in Purple requires different signatures per each signer, effectively making the state storage complexity per transaction O(n). In order to make this O(1), threshold signing must be implemented.

There are three approaches to this:

1. Implement a threshold signing crypto-system for the schnorr variant ed25519, which Purple currently uses.
2. Implement a new signing algorithm using an aggregate non-interactive zero-knowledge proofs protocol. This has the benefits of adding quantum security to the protocol and it keeps the multi-signature process non-interactive. However, this is impossible?
3. Use BLS only for shareholders accounts so that signatures can be aggregated non-interactively. Limiting it only to shareholder accounts doesn't put that much of a strain while performance loss on shareholder accounts will result in higher fees but is a fair price to pay for O(1) storage complexity. This can be further optimized via caching. Multi-sig accounts can then use the ed25519 threshold scheme. However this poses problems for stock transfers since the signers are required to have a BLS address but this can be addressed by requiring accounts to be tied to two addresses (one for authorizing stock transfers and one for other assets).

In order to minimise latency, nodes which are in the validator pool should have a direct TCP connection between themselves.

Pre-connection of validator sets

Since miners of the EasyChain know ahead of time who the current and the next most probable validators will be, we have time to establish a direct TCP connection between them.

These connections will have the highest priority on these nodes and may even require an increase in the max allowed peers i.e. the code currently has a default of 8 peers, however these connections could count separately.

Once the state change is applied to the pool and the nodes are joined, they will most probably already have a TCP connection established between them.

In order to do this effectively we will also need some kind of DHT based overlay in order to allow nodes which are not directly connected between themselves to reach each other in the case they do need to connect.

Protocol

The protocol for establishing a high-priority connection between two potential or existing validators is the following:

1. An easy chain miner successfully mines a block which will serve as proof for the need to establish a high-priority connection.
2. The miner sends a RequestConnection packet to all of the current validators which still have remaining allocated blocks after the current consensus step/epoch through the overlay. The miner also does this for previous successful miners on the EasyChain and to subsequent ones.
3. The nodes receiving the request verify if the sender NodeId matches the one which is the successful miner.
4. The nodes accept the connection by sending an AcceptConnection packet back through the overlay.
5. The nodes perform the connection handshake as usual.

Fallback Mechanism

Sometimes it is possible that validators will not connect to all of the other validators. In order to manage this case we will also require participants in the validator pool to forward created events to all of their (validator) peers.

This will ensure that all validators receive all created events and that they will only fall out of sync because of being shutdown or malicious.

The json rpc api should have a method for connecting to a specific peer. The arguments of the method can be the ip, port and node id.

Related to #21

We need to implement some kind of a reputation system in order to ban misbehaving nodes.

An OpenMultiSig lists a MultiSignature account in the ledger. The validation logic for a OpenMultiSig transaction must do the following:

• Check that the creator address exists.
• Check that the creator address has the amount listed to be initially sent to the account's balance.
• Check that the creator address has the amount listed to be paid as the transaction's fee.
• If the transaction's fee is paid in the same currency as the one being initially transferred, check that the sender address has the summed amounts.

This means implementing the following methods:

• NetworkInterface::send_to_peer.
• NetworkInterface::send_to_all.
• NetworkInterface::process_packet.

All of these functions should spawn futures on the tokio runtime in order to have asynchronous behavior.

In order to support more functional languages which heavily depend on recursion, the virtual machine should have tail-call optimization as a first class citizen.

Related to #23

A packet for forwarding blocks. Related to #11.

A Send Peers packet can only be sent after a received Request Peers packet and it simply sends a number of peers to the requesting node.

Related to #30

A Send transaction sends funds from a sender address to a receiving address. The validation logic for a Send transaction must do the following:

• Check that the sender address exists.
• Check that the sender address has the amount listed to be sent.
• Check that the sender address has the amount listed to be paid as the transaction's fee.
• If the transaction's fee is paid in the same currency as the one being transferred, check that the sender address has the summed amounts.
• In case the receiver address is either a shareholder, multi-signature or contract address, check if the account is listed in the ledger.

Note: Burn validation logic can serve as an example.

The nodes participating in the network must be able to request and send peers between each other.

Related to #11

A Pay transaction pays dividends to the shareholders of a shareholder controlled account. The validation logic for a Pay transaction must do the following:

• Check that the issuer address exists.
• Check that the issuer address is a shareholder controlled account.
• Check that the issuer address has the amount listed to be paid.
• Check that the issuer address has the amount listed to be paid as the transaction's fee.
• If the transaction's fee is paid in the same currency as the one being paid, check that the issuer address has the summed amounts.

Note: Burn validation logic can serve as an example.

Related to #23

Nodes can only send peer lists to other nodes when they are requested to do so, by receiving a Request Peers packet. A Request Peers packet must state the maximum number of peers that a node wishes to receive and if it receives more than this it will decrease the reputation of the sender and potentially ban it.

Maybe we should limit this to a maximum such as 256 peers and we can keep the encoding in one byte and to prevent unreasonably large requests.

Related to #30

So we can test locally anything we would otherwise test on a network.

Related to #23

When running multiple times the tests, the ones from chain randomly fails.

failures:

---- chain::tests::append_stress_test stdout ----
thread 'chain::tests::append_stress_test' panicked at 'called `Result::unwrap()` on an `Err` value: AlreadyInChain', src\libcore\result.rs:997:5
note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.
thread 'chain::tests::append_stress_test' panicked at '[quickcheck] TEST FAILED (runtime error). Arguments: ()
Error: "called `Result::unwrap()` on an `Err` value: AlreadyInChain"', C:\Users\itodo\.cargo\registry\src\github.com-1ecc6299db9ec823\quickcheck-0.7.2\src\tester.rs:176:28

---- chain::tests::it_rewinds_correctly2 stdout ----
thread 'chain::tests::it_rewinds_correctly2' panicked at 'called `Result::unwrap()` on an `Err` value: AlreadyInChain', src\libcore\result.rs:997:5
thread 'chain::tests::it_rewinds_correctly2' panicked at '[quickcheck] TEST FAILED (runtime error). Arguments: ()
Error: "called `Result::unwrap()` on an `Err` value: AlreadyInChain"', C:\Users\itodo\.cargo\registry\src\github.com-1ecc6299db9ec823\quickcheck-0.7.2\src\tester.rs:176:28

---- chain::tests::stages_append_test4 stdout ----
thread 'chain::tests::stages_append_test4' panicked at 'assertion failed: `(left == right)`
  left: `BelongsToDisconnected`,
 right: `DisconnectedTip`', src\chain\src\chain.rs:4496:9

---- chain::tests::stages_append_test3 stdout ----
thread 'chain::tests::stages_append_test3' panicked at 'assertion failed: `(left == right)`
  left: `BelongsToDisconnected`,
 right: `DisconnectedTip`', src\chain\src\chain.rs:1988:9


failures:
    chain::tests::append_stress_test
    chain::tests::it_rewinds_correctly2
    chain::tests::stages_append_test3
    chain::tests::stages_append_test4

test result: FAILED. 6 passed; 4 failed; 0 ignored; 0 measured; 0 filtered out

Currently the method of keeping track of balances in Purple is the Account Model. This model has the benefits of being easier to implement and to reason about, especially when support for smart contracts is also provided. But it has several downsides:

• No garbage collection of old addresses.
• Vulnerable to replay attacks unless other functionality is implemented.
• If replay attacks are fixed, it then becomes impossible to process transactions in parallel and each transaction must include a nonce and be approved sequentially, meaning that if a client sends more than one transaction and one of them fails, each of them will fail and the client must then recompute the committed transaction set.
• Incompatible with improvements proposed to Bitcoin Core such as the CoinJoin protocol.
• Very hard to implement scalable zero-knowledge transactions.

If we change to the UTXO model all of the problems disappear except for the fact that contract level transfers become harder to do and we have to completely re-write the state writing logic.

Different transaction types would be expressed via different meta fields on outputs.

Drawbacks

The only drawback we have of this is that the smart contract logic becomes a lot harder to implement and get right. We will have to tie ephemeral state changes to UTXO set changes somehow. This is hard but not impossible.

The mining algorithm that will be used for mining will be cuckoo by John Tromp. This algorithm is a memory-hard Proof of Work that has no currently known ASICS. This will help with the decentralization of the network quite a lot.

We have two options on implementing this in Purple:

1. We port the original C++ version of cuckoo by writing a sys-crate ourselves.
2. We use an already ported version.

The p2p layer of the Purple Protocol defines several packets type used for communication between nodes using tcp/ip. So far, these packets are:

• Connect - Used for connecting to a peer
• Request peers - Used for polling a node for its peer list
• Send peers - Used for sending the peer list
• Request transactions - Used for polling a node for it's mempool transactions
• Send transactions - Used for sending the list of pending transactions
• Forward event - Used for forwarding a consensus event
• Forward transaction - Used for forwarding a transaction
• Forward block - Used for forwarding a block

Related to #17