Optimized Delegated Byzantine Fault Tolerance (ODBFT)

vncoelho · 2018-10-24T20:54:30Z

Last update: 21th November

Part I: commit phase + regeneration strategy + minnor message p2p route optimizing
- Finish the original commit phase with partial signatures;
- Propose a new regeneration strategy able to recover lost/failled nodes;
- Use the maximum amount of benefits from the current Payloads, extracting all information (communication is the most expensive part of the descentralized system). Thus, let's process the maximum we can locally and extract good conclusions.

Part II, III and IV will be dealt in different Pull Requests.

Part II: Novel network routing strategies, a trade-off between payloads and communication (Q4 2018 - Q1 2019): https://github.com/igormcoelho/neo/tree/optimized-dbft-part-ii
- Implement novel efficient strategies for optimizing message routing.
Part III: Efficient prediction and optimization strategies for fine-tune the dBFT (Q2/Q3 2019)
- Fine-tune times and predict the cost of the next blocks in order to ensure accomplishment of desired block times.
Part IV: Metaheuristics an efficient selection of pending transactions (Q3 2019 - Q1/Q2 2020)
- Investigate the use of a Greedy Randomized Adaptive Search Procedure for FillingContext

Part I: Highlights of the proposal (which is a consolidation of previous knowledge discussed in other issues and PRs)

Complete signatures are only send after commit phase:
- At least, M partials signatures should be obtained before sending a complete signature of the context.makeHeader;
- Partials signatures are produced by signing the PrepareRequest Payload. One peculiarity is that the Speaker/Primary signs the PrepareRequest Payload_1 with an empty vector of his signature (as one could expected), while the Backups signs the complete PrepareRequest Payload_Complete that contains Speaker signature of the aforementioned PrepareRequest Payload_1;
- It should be noticed that, in essence, the Speaker/Primary partial signature could even be removed, but we are making use of this in order to speed up the P2P share of the PrepareRequest Payload since every PrepareResponse Payload is now containing the PrepareRequest Payload. Thus, any CN that receives the PrepareResponse Payload (even without receiving the PrepareRequest) can validate both of them together if his local PrepareRequest Payload is still null (for this purpose, the partial signature is important for ensuring that a third-entity does not modify primary payload content);
When a node Complete Signature is sent (flag CommitAgreement is activated) we can lock Change View. The reasoning is that M nodes already showed their agreement with the proposed Block.
- When M partial signatures are achieved, a given node signed the complete header and relay to the network.
- This node can not anymore increase its view level (Change View);
- An event called OnRegeneration is called every time that a node asks for ChangeView , it contains a Payload with all Partial Signatures (SignedPayloads) plus the original PrepareRequestPayload. It calls a MakeRegenaration event that will be spread throughout the network. That node (that asked for changeview) will be able to verify the OnRegeneration and even reduce its View number if it sees that Commit phase was already been achieved in a lower view.

Part I main contributors: @erikzhang, @shargon, @igormcoelho, @vncoelho, @belane, @wanglongfei88, @edwardz246003

Analogy of the proposal

An analogy of the proposal is the indefatigable miners problem (defined here):

The speaker is a Geological Engineering (my hometown is pioneer in it and one of the cities of more diversity of minerals in the world) and he is searching for a place to dig for Kryptonite;
He proposes a geographic location (coordinates to dig);
The majority (M guys) agrees with the coordinates (with their partial signatures);
Time for digging: they will now dig until they really find Kryptonite (no other place will be accepted to be dig until Kryptonite is found). Kryptonite is an infinite divisible crystal, thus, as soon as one finds he will share the kryptonite so that everyone will have a piece for finishing their contract 3.;
If one of them dies, when it resurrects it will see its previous signed agreement (3.) and it will automatically start to dig again. The other minority will suffer the same, they will be fulfilled with hidden messages saying that they should also dig.

vncoelho · 2018-12-17T16:50:48Z

Hi @erikzhang, I saw that you self-requested review.
Thanks for taking some time for checking it.
Do not hesitate to modify and change anything. You are the master Yoda here.

neo/Consensus/ConsensusService.cs

erikzhang · 2018-12-18T09:17:49Z

neo/Consensus/PrepareResponse.cs

+        /// <summary>
+        /// Speaker PrepareRequest Payload
+        /// </summary>
+        public ConsensusPayload PreparePayload;


Why not just use PrepareRequest?

public PrepareRequest Request;

You check everything!! eahuehauea
Could be, @erikzhang, I think that we do not use the Payload itself, you are right. It is worth changing and verifying this possibility for reducing the size of this Payload.

But I would need to double check the logic for the Regeneration (as well as when we indirectly receive this Payload OnPrepareResponse), because maybe we need some verification regarding view_number, etc...

If we decide to change this I personally would prefer to merge and then we perform this optimization until we are sure about all consequences.
Sorry for the bad design =/

You can get the view_number from the ConsensusPayload with PrepareResponse itself.

I need the code to be merged into the master branch to be well designed. If necessary, perhaps this pr will need to be split into multiple smaller prs to submit.

Yes, you are right, view_number can be obtained.
Furthermore, the other data there can also be modified, because the signature currently does not cover that variables.

The idea is, should we change it now or wait for a next PR?

I started a draft, @erikzhang.

It is already compiling without errors but with some problems on replicating the original payload for getting the hash: https://github.com/igormcoelho/neo/tree/erik-optimizing-consensuspayload-to-prepmessageonly

Commits:
igormcoelho@4d22638
igormcoelho@3d3c087

igormcoelho#4

Please considering that PreparePayload has more info than PrepareRequest, such as PrevHash, BlockIndex, TimeStamp. Question is that do we need to verify those info when we consider the requests are IDENTICAL?

Hi @wanglongfei88, in principle, values should be identical because they are obtained from the PrepareRequest Payload at OnPrepareRequest.

Thus, it should be easy to reproduce those values.
But I do not know what is happening in igormcoelho#4, should be some minor detail.

@erikzhang, I am still having problems with igormcoelho#4

It is a good idea and should work, but need some adjustments.
Do you think we should try to merge it now or it can be done after this one?

erikzhang · 2018-12-18T09:20:57Z

neo/Consensus/PrepareResponse.cs

+        /// <summary>
+        /// Prepare Request, PreparePayload, payload signature
+        /// </summary>
+        public byte[] ResponseSignature;


Since every ConsensusPayload has a signature, do we still need a ResponseSignature?

neo/neo/Network/P2P/Payloads/ConsensusPayload.cs

Lines 12 to 20 in 8310035

public class ConsensusPayload : IInventory

{

public uint Version;

public UInt256 PrevHash;

public uint BlockIndex;

public ushort ValidatorIndex;

public uint Timestamp;

public byte[] Data;

public Witness Witness;

You want to optimize everything, Erik! aheuaheuahueauheauea
You are right again, I think that we can use this and it is a nice way to save space! Nice catch.

But the logic would be a little different, because nowadays we use the ResponseSignature representing a simple way of signing the PrepareRequest. We would need to perform some minnor adjusts.
Again, I personally prefer to merge as it is (because it is quite of well tested) and then we perform this optimization.
But fell free to change anything you want, Erik. It is up to you. If you decide that it is better to do it now count with all of us for testing it.

In this new commits here https://github.com/igormcoelho/neo/tree/optimized-dbft-part-ii we updated it to All Known PrepRequest Signatures. I also prefer to keep the current template because of this possibility, we think that it is worth to send all known signatures, as we discussed in that recently opened issue.
If you also think that it is worth we can think about merging it now (the change has no big consequences and was already tested).

You don't need to save all the ResponseSignatures. You can relay the received PrepareResponse message again when needed.

In the current code we just relay one signature per time.

In the PART-II PR we are investigating this idea of sharing all ResponseSignatures, it is is not merged here yet. I has some advantages in some cases:

B receives PrepRequest from A and send Response

C receives Response_B (indirectly gets PrepRequest_A) and send Response

D only gets Response_C and it will contain all 3 signatures.

Since the PrepRequest message is shared in the Response payload we can easily check all Backup signatures.
But this is a case to be investigated.

The logic also applies to the FinalSignature of the header, once we receive OnCommitAgreement we can save all of them and share them when we relay our commit agreement.
It looks like a small speed up but I think it has potential benefits when the nodes becomes bigger with more nodes, it can help communication considerably.

ResponseSignatures and PreparePayload are essential for current logic of Regeneration which makes sure other nodes (disconnected or with low network) will be able to move on to commit phase if there are other nodes are already locked in commit phase.

Without regeneration, it will be difficult to reach consensus with some nodes are locked in commit phase, and other nodes are not in commit phase which will request change view without success.

I hope my comment makes sense and be helpful.

If a node enters the commit phase, it should lock its state and no longer change view. If only 2 nodes enter the locked state, then the other 5 nodes can change view and generate blocks. If there are 3 nodes entering the locked state, then the remaining 4 nodes cannot change view, they must reach a consensus in the current view.

A node can only enter commit phase with M valid signatures of the PrepareReq Message, even the Primary.

After receiving those M valid SignedPaylods, in the worst case M - f_{fault} = f_1 will be locked.

The rest f_{fault} + f_2 = 2f = M will ask for change_view and the Healthy/NoByzantine nodes f_2 will join the other f_1 by receiving their OnRegeneration Payload.

|f_{fault}| = |f_1| = |f_2| = 1/3 N
Safe limit = M = 2/3N
f_{fault} is the set of nodes that are Byzantine or Fault nodes (natural network fails).

@erikzhang, can/should I merge igormcoelho#5?

erikzhang · 2018-12-19T10:37:01Z

neo/Consensus/PrepareRequest.cs

+        /// <summary>
+        /// Final block signature
+        /// </summary>
+        public byte[] FinalSignature;


the primary should not send FinalSignature at the beginning. It should be sent in the Commit phase just like backups.

Hi @erikzhang,

In the first draft it was done as you suggested. Later we updated it in order to send the FinalSignature at the beginning, as a speed-up.
In the current NEO code (without this PR) it is done like this, Primary sends its complete signature since the beginning.

In term of logic, it makes sense because the primary is committed since the beginning (he is the one that proposed the block and it seams normal to have its signature).
With this we gain one signature that we already known.
As far as we analyzed there are no negative aspects.

A node that has sent a FinalSignature is not allowed to change view. This implementation violates the design I proposed earlier.

In fact, there is other way of looking...aehauheau
A node that sees the commitment of the majority (has M partial signatures`) is not allowed to change view. 💃 :D

I think it is better to send it earlier, Erik, we gain one signature (nodes can relay a block faster by knowing it in advance). The Speaker will not send it wrong because if he send it wrong everyone will know that he is Byzantine/Malicious/Fault.
But we also check it before creating the block:

neo/neo/Consensus/ConsensusContext.cs

Lines 104 to 111 in 451e2a7

if (PrimaryIndex == i && !Crypto.Default.VerifySignature(block.GetHashData(), FinalSignatures[i], Validators[i].EncodePoint(false)))

{

// CheckFinalSignatures...It looks like that Primary tried to cheat providing wrong final signature! His header signature will not be considered

if ((FinalSignatures.Count(p => p != null) - 1) >= M)

continue;

else

return null;

}

In addition, in the new design every Primary should propose it own set of transactions (we removed SignatureSent flag). Thus, it is almost impossible that someone cheat the system by storing this FinalSignature.

The core idea is that primary is not unconditionally accept its own proposal. The criteria for his approval are the same as the backups, that is, there are more than M consensus nodes to accept the proposal. PrepareRequest and PrepareResponse are the initial judgments of the node on the proposal, and FinalSignature is the ultimate judgment of the entire consensus team on the proposal.

I agree, @erikzhang, the description is precise.
The only point we modified was the FinalSignature_{primary}.

FinalSignature_{primary} being sent in the beginning does not mean that Primary accepted his own proposal.
Primary will just enter commit phase equally as other Backups, when M valid approvals are achieved.

In this sense, the FinalSignature_{primary} sent in advance is not used for any decision making, it is a just a speed up (in case of lack of agreement it will be reset:

neo/neo/Consensus/ConsensusContext.cs

Lines 78 to 92 in 451198a

public void ChangeView(byte view_number)

{

ViewNumber = view_number;

PrimaryIndex = GetPrimaryIndex(view_number);

PreparePayload = null;

TransactionHashes = null;

SignedPayloads = new byte[Validators.Length][];

FinalSignatures = new byte[Validators.Length][];

if (MyIndex >= 0)

{

ExpectedView[MyIndex] = view_number;

}

_header = null;

}

) and a new block will be produced with difference Nonce and possible different set of transactions.
Primary will still lock its change view only after M SignedPayloads are known (when it really enter commit phase).

send FinalSignature_{primary}, in advance, or not send, this is the question. ahueahueahueahueaea

Do we have a reached a decision about this? :D
Or should we really remove the FinalSignature_{primary} from being sent in advance?

erikzhang · 2019-01-02T11:45:10Z

There are several places that need to be modified. In order to save time, I will edit directly on this PR.

vncoelho · 2019-01-02T12:10:45Z

Please, do not destroy anything... aheuahueaaehuaheua

I am kidding, Erik. Fell free to edit. You are the master on this.

erikzhang · 2019-01-07T12:46:45Z

I tried to remove PrepReqSignature from PrepareRequest, but found it a bit difficult. I will try to split this pr into smaller ones.

erikzhang · 2019-01-07T14:38:30Z

#534

vncoelho · 2019-01-07T20:15:45Z

Ok, @erikzhang.

Let's do it this way.

vncoelho · 2019-02-16T14:23:23Z

Closing after the design of the Regeneration #579.
Some are features related to signatures sharing of Preparations and Commit are still missing on #547.

* Initial commit for contribution number 1. * Update api.md Filipino Translation for api.md * Update whitepaper.md - Cordeta From Line 1 to 61 A total of 1112 words. (Source codes and variables were not counted) * Update whitepaper.md changed all "alaala to memorya" few touches * Update Whitepaper.md Minor touches : Gayun din to Gayundin * Update whitepaper.md Review Changes modified review changes * * Updated commit for contribution 1. * Update api.md Updated review * Updated files for contribution no. 1 * Update for contribution #1. * Update api.md Fixed * Update api.md Fixed #2 * Update setup.md Filipino Translation for setup.md * Update exchange.md Filipino Transalation * Update api.md Updated changes * Fixes for contribution #1. * update exchange.md * Update setup.md * Update gui.md Filipino translation. Ready for review * whitepaper.md [FULL TAGALOG TRANSLATION][FOR REVIEW] From line 63 to 113 A total of 454 translated words * Update GUI.md I fixed the errors. * Update whitepaper.md Changes based from severinolorillajr * Initial TL translations for white-paper.md * Partial TL translations for white-paper.md - 1,176 words * NEO Filipino Localization #2 (part 1) * NEO Filipino Localization #2 (part 2) * Updated TL translations for white-paper.md based on review * NEO Filipino Localization #2 (Fix based on reviews)

shargon and others added 29 commits October 23, 2018 13:49

Commit phase

63847fc

Lock change view if commit was sent

064ebc9

Lock View change and resend the signature

5f3e99a

If someone sent view change and is locked, relay the signature again

f0c2ada

Move logs to avoid repetitions

14a31e6

Just relay again

6b23061

New commit phase

678d01a

sketch of new 3-phase consensus

201a28c

fixing change views

29c3dcb

small fixes

459dda9

more fixes

c585389

more includes

d01176b

serialization

bcacc70

more serialization

0fa260c

some variable initializations

db7d73a

some castings

672deed

more context

013e541

initialization

5e783bb

accessible vars

013d440

some more fixes

8c11d6d

more casting

c01a81e

trying deserialization

a55b26a

more deser

52b7b29

dummy Prep

b4c1f73

function deserial

ced18ea

more seri

ca0c500

more try

7dd700a

more include IO

3c7f343

declare iss

40a51c0

vncoelho mentioned this pull request Oct 24, 2018

fix consensus #425

Merged

vncoelho added 2 commits December 14, 2018 08:18

Merge branch 'master' into new_commit_phase

153f70a

Minor clean and removing checkings that were not necessary

73a6da7

vncoelho dismissed shargon’s stale review via 73a6da7 December 17, 2018 16:48

vncoelho commented Dec 17, 2018

View reviewed changes

neo/Consensus/ConsensusService.cs Outdated Show resolved Hide resolved

erikzhang reviewed Dec 18, 2018

View reviewed changes

Merge branch 'master' into new_commit_phase

d56ada6

erikzhang reviewed Dec 19, 2018

View reviewed changes

vncoelho added 4 commits December 19, 2018 09:34

Merge branch 'master' into new_commit_phase

da5793f

Merge branch 'master' into new_commit_phase

9405429

Merge branch 'master' into new_commit_phase

451198a

Merge branch 'master' into new_commit_phase

7930fd4

vncoelho force-pushed the new_commit_phase branch from d0889c2 to 7930fd4 Compare January 10, 2019 11:27

Merge branch 'master' into new_commit_phase

5d67766

This was referenced Jan 10, 2019

Add commit phase to consensus algorithm #534

Merged

dBFT 2.0 #547

Merged

edgedlt mentioned this pull request Jan 22, 2019

block sync stopped at 3260162 neo-project/neo-node#292

Closed

erikzhang added this to the NEO 3.0 milestone Jan 25, 2019

Merge branch 'master' into new_commit_phase

6cfcc8f

vncoelho mentioned this pull request Jan 25, 2019

Add PreparationHash field to PrepareResponse to prevent replay attacks from malicious primary #576

Merged

vncoelho mentioned this pull request Feb 6, 2019

Recover nodes requesting ChangeView when possible #579

Merged

vncoelho closed this Feb 16, 2019

lock9 mentioned this pull request Oct 25, 2019

Neo 3 Opmizations update list #1189

Closed

31 tasks

	public class ConsensusPayload : IInventory
	{
	public uint Version;
	public UInt256 PrevHash;
	public uint BlockIndex;
	public ushort ValidatorIndex;
	public uint Timestamp;
	public byte[] Data;
	public Witness Witness;

	if (PrimaryIndex == i && !Crypto.Default.VerifySignature(block.GetHashData(), FinalSignatures[i], Validators[i].EncodePoint(false)))
	{
	// CheckFinalSignatures...It looks like that Primary tried to cheat providing wrong final signature! His header signature will not be considered
	if ((FinalSignatures.Count(p => p != null) - 1) >= M)
	continue;
	else
	return null;
	}

	public void ChangeView(byte view_number)
	{
	ViewNumber = view_number;
	PrimaryIndex = GetPrimaryIndex(view_number);
	PreparePayload = null;
	TransactionHashes = null;
	SignedPayloads = new byte[Validators.Length][];
	FinalSignatures = new byte[Validators.Length][];
	if (MyIndex >= 0)
	{
	ExpectedView[MyIndex] = view_number;
	}

	_header = null;
	}

Conversation

vncoelho commented Oct 24, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Optimized Delegated Byzantine Fault Tolerance (ODBFT)

Part I: Highlights of the proposal (which is a consolidation of previous knowledge discussed in other issues and PRs)

Analogy of the proposal

Uh oh!

vncoelho commented Dec 17, 2018

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vncoelho Dec 18, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vncoelho Dec 19, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vncoelho Dec 18, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vncoelho Dec 19, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vncoelho Dec 20, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vncoelho Dec 19, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vncoelho Dec 19, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vncoelho Dec 19, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vncoelho Dec 20, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vncoelho commented Oct 24, 2018 •

edited

Loading

vncoelho Dec 18, 2018 •

edited

Loading

vncoelho Dec 19, 2018 •

edited

Loading

vncoelho Dec 18, 2018 •

edited

Loading

vncoelho Dec 19, 2018 •

edited

Loading

vncoelho Dec 20, 2018 •

edited

Loading

vncoelho Dec 19, 2018 •

edited

Loading

vncoelho Dec 19, 2018 •

edited

Loading

vncoelho Dec 19, 2018 •

edited

Loading

vncoelho Dec 20, 2018 •

edited

Loading

vncoelho Dec 20, 2018 •

edited

Loading

vncoelho commented Jan 7, 2019 •

edited

Loading