purpleprotocol / purple_prototype Goto Github PK
View Code? Open in Web Editor NEWOld experiment, not related to the new Purplecoin architecture. Only kept for historical reasons. Please ignore.
License: GNU General Public License v3.0
Old experiment, not related to the new Purplecoin architecture. Only kept for historical reasons. Please ignore.
License: GNU General Public License v3.0
Implementing the base consensus mechanism (without transaction validation, just event processing) requires:
A packet for forwarding blocks. Related to #11.
Related to #23
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
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
Before we do #8 it would be nice if we had some benchmarks that we can compare it against.
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:
This can be really handy for testing the network and consensus parts of the code.
Related to #23
The algorithm for the connection handshake is the following:
Client
establishes a TCP connection to the Server
.Client
constructs a shared key from the public key of the Server
.Client
attaches the shared key to a Connect
packet which it sends to the Server
.Server
receives the connect packet, it computes its shared key and attaches it to a Connect
packet.Server
sends the packet to the Client
.So we can test locally anything we would otherwise test on a network.
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.
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 peerRequest peers
- Used for polling a node for its peer listSend peers
- Used for sending the peer listRequest transactions
- Used for polling a node for it's mempool transactionsSend transactions
- Used for sending the list of pending transactionsForward event
- Used for forwarding a consensus eventForward transaction
- Used for forwarding a transactionForward block
- Used for forwarding a blockThere are 4 opcodes that are related to arrays. These are:
Fetch = 0x2c,
Grow = 0x2d,
ArrayPush = 0x2e,
ArrayPop = 0x2f
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.
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.
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.
The ArrayPop
opcode pops an item from an array on the operand stack and pushes it to the operand stack.
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.
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.
An OpenShares
transaction lists a shareholders controlled account in the ledger. The validation logic for an OpenShares
transaction must do the following:
Related to #53
The nodes participating in the network must be able to request and send peers between each other.
Related to #11
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.
This can be done in mainly two ways:
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.
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.
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.
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:
Peer1
connects to a Relay
.Peer1
asks the Relay
about its peer list by sending a RequestPeers
packet.Relay
sends a SendPeers
packet to Peer1
which includes the information of Peer2
.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
.Peer2
sends Peer1
an AcceptConnection
through the relay.Peer1
and Peer2
now are connected through TCP.Peer1
and Peer2
perform the connect handshake as usual.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
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.
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).
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
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 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
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
An OpenMultiSig
lists a MultiSignature account in the ledger. The validation logic for a OpenMultiSig
transaction must do the following:
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
A Pay
transaction pays dividends to the shareholders of a shareholder controlled account. The validation logic for a Pay
transaction must do the following:
Note: Burn
validation logic can serve as an example.
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.
Related to #23
For example, when pushing a value to a stack which is popped from another stack.
In order to minimise latency, nodes which are in the validator pool should have a direct TCP connection between themselves.
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.
The protocol for establishing a high-priority connection between two potential or existing validators is the following:
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.NodeId
matches the one which is the successful miner.AcceptConnection
packet back through the overlay.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.
Related to #17
We need to implement some kind of a reputation system in order to ban misbehaving nodes.
An OpenContract
transaction deploys a contract to the blockchain state. The validation logic for an OpenContract
transaction must do the following:
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:
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.
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.
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:
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 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.
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
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
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.
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.
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.
A packet for forwarding transactions. Related to #11.
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/
A Send
transaction sends funds from a sender address to a receiving address. The validation logic for a Send
transaction must do the following:
Note: Burn
validation logic can serve as an example.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.