BitShares Forum

Other => Graveyard => Marketplace => Topic started by: bytemaster on December 31, 2013, 05:14:13 am

Title: 1000 PTS - Ripple-Style Consensus Implementation [CLOSED]
Post by: bytemaster on December 31, 2013, 05:14:13 am
I am looking for someone to develop a flexible, reusable, ripple-style consensus implementation.   This algorithm should be transaction content neutral.  The purpose of the algorithm is to allow a group of trusted nodes (Unique Node List) to reach consensus about the content of a merkel tree and timestamp for the next block and should add new blocks as quickly as possible.

For the purpose of this general purpose algorithm a transaction is just a blob of data and a transaction ID (hash of data) is valid if the node merely has a copy of this blob of data and the TRX ID does not already exist in the block chain.

The UNL is a database of IP addresses and Public Keys and all nodes connect to all other nodes.

Blobs of data are distributed among the nodes in the UNL using bitcoin style INV and GET_INVENTORY and GET_MESSAGE messages. 

This code should be built on top of the BitShares repository which already has primitives for the following:

1) Blob broadcast via the bitchat (email) system
2) Secure/encrypted sockets
3) JSON / Binary serialization
4) Elliptic Curve Utilities, etc....

This code should be built to follow coding conventions used in the bitshares code base.
This code should be built with the intention of being an API, a reusable component of a DAC toolkit.
This code must be developed in the open, on github
If a team of people work on it, then all participants must agree to the division of the bounty and github commits will track who did what.

For a video explanation of the algorithm:
http://www.youtube.com/watch?v=pj1QVb1vlC0

https://ripple.com/wiki/Unedited_Notes

The code must be complete with documentation and a working network of at least 20 nodes where new transactions are introduced to random nodes at random intervals at up to 1 MB of transaction data every 5 minutes with an average transaction size of 200 bytes.

Like all bounties, I am looking to purchase this as an off-the-shelf solution to the consensus problem with our code.  It must build as part of the bitshares code base.

I will provide feedback on the API as it develops and steer this in the direction I want, but suspect that the time / cost to implement should be far less than the bounty!   
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: alexkravets on December 31, 2013, 07:37:25 am
Nodes on the UNL are not really trusted, in fact they could be a collection of malevolent actors, the key thing about the UNL is that they are ONLY assumed not to be in collusion, therefore a UNL which consists of CIA, KGB & Chinese Intelligence is actually a valid and very good UNL. Non-collusion is therefore a much much weaker requirement than full trust.

See the following for precise definitions, rationale, etc

https://ripple.com/wiki/Consensus#Not_colluding
https://ripple.com/wiki/Unique_Node_List

Also, in the context of Ripple, because each transaction is self-validating using ECDSA AND
transaction ordering is deterministic (lexicographic by tx hash) the only possible mischief by a node is
to withhold a transaction from its consensus proposal.

Cheers ...
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: bytemaster on December 31, 2013, 07:40:26 am
Nodes on the UNL are not really trusted, in fact they could be a collection of malevolent actors, the key thing about the UNL is that they are ONLY assumed not to be in collusion, therefore a UNL which consists of CIA, KGB & Chinese Intelligence is actually a valid and very good UNL

See the following for precise definitions, rationale, etc

https://ripple.com/wiki/Consensus#Not_colluding
https://ripple.com/wiki/Unique_Node_List

Also, in the context of Ripple, because each transaction is self-validating using ECDSA AND
transaction ordering is deterministic (lexicographic by tx hash) the only possible mischief by a node is
to withhold a transaction from its consensus proposal.

Cheers ...

Alex, yes I recognize that the nodes need not be trusted aside from being on the UNL to prevent Sybil attacks.   I want to utilize the Ripple algorithm in as straightforward manner as possible.  I would even be happy to use the Ripple code if it can be pulled out and integrated with BitShares. 
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: alexkravets on December 31, 2013, 07:49:34 am
Sorry, I meant my post as a clarification for bounty takers.

C++ is not my forte, but my impression after looking at

https://github.com/ripple/rippled

Is that although the entire code base is pretty large, the core domain-independent consensus part is under a thousand lines and should be extractable, however thankless task that maybe :-)

Cheers ...
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: bytemaster on December 31, 2013, 07:53:07 am
Sorry, I meant my post as a clarification for bounty takers.

C++ is not my forte, but my impression after looking at

https://github.com/ripple/rippled

Is that although the entire code base is pretty large, the core domain-independent consensus part is under a thousand lines and should be extractable, however thankless task that maybe :-)

Cheers ...

Yep, that was my analysis of the code as well.  The goal for this bounty is to turn that code into something with a solid API and reusable in many different contexts.   

So I would like to clarify that this bounty should be heavily focused on making this reusable, well documented, and flexible.  We have at least two different code bases that we would like to use the code in:  BitShares and Bitcoin so a solid design is expected as part of adapting Ripple's code. 
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: toast on December 31, 2013, 07:59:04 am
Is this definitely the consensus protocol that will be used for bitshares? UNLs make me a bit nervous, but I'm still pretty new to ripple's approach.
It would be cool if a node's score could be improved by signing it with a keyhotee ID. If I remember correctly there was a way to improve your ID's rep by destroying money in its name, this way the solution looks more like PoS and relies less on guessing whether nodes are unique or not
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: bytemaster on December 31, 2013, 03:27:27 pm
Is this definitely the consensus protocol that will be used for bitshares? UNLs make me a bit nervous, but I'm still pretty new to ripple's approach.
It would be cool if a node's score could be improved by signing it with a keyhotee ID. If I remember correctly there was a way to improve your ID's rep by destroying money in its name, this way the solution looks more like PoS and relies less on guessing whether nodes are unique or not

Toast, I understand your concern about UNL and I have plans to address it.  This bounty just produces one piece of the puzzle, the selection of the UNL is a separate process. 

It all boils down to the following:
1) Mining is centralized one block at a time... very bad for blockchains that implement markets
2) Mining centralizes in control of specialized hardware that the little guy will never control... so is not an option
3) Long-term security based upon proof-of-stake where everyone ratifies the blockchain
4) Short-term security based upon a set of mostly connected (via trust) UNL nodes.
5) UNL nodes vote to add new nodes to the list.  Once a new node has received votes from at least 51% of existing nodes it is included.
6) Existing nodes have incentive to grow the UNL list because the larger trusted set of the UNL the more secure the network.

As long as the majority of the existing nodes vote in a growing number of diverse nodes people will have faith in the network not to collude. 

The critical thing is that even the nodes on the UNL list cannot collude to rewrite history because of the Proof of Stake, at most they could collude to block transactions but this is no difference than mining pool collusion.   The nodes that end up voting to exclude transactions would be public and people could just fork the main chain and select a new group to trust with the consensus process.

The way you keep the UNL list of nodes 'honest' is to make it incredibly easy for a competitor to take over if they gain popular support.



Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: hasher on January 01, 2014, 11:43:16 pm
there one guy who can help, he have 20 years of digital experience:
_________________________
http://www.linkedin.com/pub/david-schwartz/34/67b/8b7
David Schwartz's
        Chief Cryptographer at Ripple Labs
        Chief Technical Officer at WebMaster Incorporated
        Director of Software Development at WebMaster Incorporated
        Senior Network Engineer at Worldwide Internet Solutions

        Director of Network Services at Internet Gateway Connections
        Partner at Cardiophonics
        Software Developer at RE/MAX
        CEO at David Schwartz Enterprises
________________
he could be easy found and asked about anything  on stackexchange.com (he answered my two questions about Ripple economics without any arrogance before), maybe he could suggest something (or someone)to our community:
http://bitcoin.stackexchange.com/feeds/user/85
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: barwizi on January 16, 2014, 06:48:14 pm
Ledger system consensus. interesting lol 3k will get immediate attention
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: naturalog on January 20, 2014, 12:34:52 am
Beginning to take a deep look on this project
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: bytemaster on January 20, 2014, 12:39:05 am
Wonderful!  I will need this algorithm by March 1. 
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: naturalog on January 20, 2014, 12:43:09 am
I will tend to API-ize the ripperd code
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: toast on January 27, 2014, 10:25:04 pm
Can you post a repo? I want to see
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: bytemaster on January 29, 2014, 05:54:33 am
Unless someone can demonstrate meaningful progress on this bounty we are going to take it in-house.   You have 24 hours to commit to delivery and show you have code already underdevelopment.
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: barwizi on January 29, 2014, 06:58:22 am
this is a bit complicated and i tried finding info on ripple but it ain't out there. if anyone has coding time do the following create a system with defined security check points, say we have "security nodes" , a transaction can only be created when connected to at least two "security nodes".  Once a transaction is made it is transmitted through the network and only confirmed when all security nodes have consensus.

To avoid Ddos issues, security nodes are not permanent, they could be any machine in the network. this is how it will function:-

1) at any given time there are ten security nodes each is in possession of a token that verifies it's designation. After a certain number of blocks/transactions the tokens are passed to another machine on the network. If a machine with a token goes offline, one of the others will generate and pass on two tokens on the next round to cover for the lost one. further, timers are place on network activity of each node keeping record of how many transactions it has transmitted and how many times it has been in possession of a token This is then used for trust ratings in the event of a fork, such modification can be done in 24hrs to the BTC code.
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: alexkravets on January 29, 2014, 10:28:19 am
Good to see this going in house. This tells me things are getting serious at Invictus.

I only would like to caution against the temptation to de-APIify it and commingle it with BitShares domain.  If it's impossible to build a decentralized DropBox replacement DAC just as easily as it will would be to build BitShares on top of it then it's become an internal BitShares implementation artifact.
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [PENDING]
Post by: bytemaster on January 30, 2014, 05:51:33 am
This bounty is now closed.  I have implemented 50% of it already and will have the rest done this week.
Title: Re: 1000 PTS - Ripple-Style Consensus Implementation [CLOSED]
Post by: toast on January 30, 2014, 06:04:44 am
brb taking out loans to buy AGS
 +5% +5% +5% +5% +5%