Check the state root to make sure it's equal to the previous state root after processing the block.

When the beacon chain is syncing or isn't connected to the network, it should tell the validator module not to propose any blocks and not accept any blocks until the chain is fully synced and the client is connected.

Reproduce:

1. Create a EpochInformationRequest.
2. Set EpochInformationRequest.EpochIndex to an invalid epoch.
3. Call a Beacon node's GetEpochInformation with the request.

The Beacon node will return success.
Expect: Beacon should report error on wrong epoch.

This will prevent many types of DoS attacks that would be possible using Protobuf.

State manager to hold state from shards including full vs. partial state.

• Specify P2P/RPC interface for accessing packages
• Specify how packages/transactions are generated and held
• Specify configuration options
• Build module
  • Core
    • State Storage
      • Optimize CSMT and implement for disk
    • Mempool
    • Package Generation
  • RPC
  • P2P
• Integration/unit tests

These data types are for shard storage.

Data Types

• Tree → keeps track of a full Merkle tree
• Witness → keeps track of information needed to update a state root
• PartialTree → keeps track of updates to the tree and can calculate a state root if provided correct witnesses

Tree

• Tree.set(key: uint256, value: uint256)
  • Sets a key within the tree
• Tree.setWithWitness(key: uint256, value: uint256) → Witness
  • Sets a key within the tree and returns the witness needed to set the key given only the state root. Should be able to construct a new state root given the witness and the old root.
• Tree.get(key: uint256) → value: uint256
  • Gets a key from the tree
• Tree.delete(key: uint256)
  • Deletes a key from the tree
• Tree.deleteWithWitness(key: uint256) → Witness
  • Deletes a key from the tree and returns the witness needed to delete the key given only the state root. Should be able to construct a new state root given the witness and the old root.
• Tree.proveKey(key: uint256) → Witness
  • Generates a witness that proves that a key equals the value provided.
• Tree.hash() → uint256
  • Finds the hash of the tree.

Partial Tree

PartialTrees are not really trees. They're simply the state root and witnesses. The witnesses allow certain parts of the tree to be updated or verified.

• PartialTree.new(stateRoot: uint256, witnesses: \[Witness\])
  • Initializes a partial tree given the state root and a list of witnesses
• PartialTree.set(key: uint256, value: uint256) → Error
  • Sets a key in the merkle tree or returns an error if the witnesses provided do not provide enough information to set the key.
• PartialTree.delete(key: uint256) → Error
  • Deletes a key from the merkle tree or returns an error if the witnesses provided do not provide enough information to delete the key.
• PartialTree.verify(key: uint256, value: uint256) → Error
  • Verify a key in the merkle tree or return an error if the witnesses provided doesn't provide enough information to verify the key.
• PartialTree.hash() → (uint256, Error)
  • Calculates new hash of the Merkle tree.
  • This applies all of the updates from set or verify and calculates a new state root using the witnesses provided.

Witness

Witnesses are trees that detail certain parts of the tree. Witnesses do not have to contain the whole tree, but just certain branches needed to update information about the tree or verify information about the tree. Partial trees only contain leaf nodes (values) if the verifier needs to verify a key, but not if they just need to update the key.

• Witness.compress(witnesses: \[Witnesses\]) → Witness
  • Because some information in witnesses are duplicated, we should be able to compress witnesses by combining them. For example, a single branch would just be a list of hash values, but if two branches share 5 of the same nodes, we can compress them by including the 5 common nodes only once.

Example Code

tree = Tree()

tree.set(1, 1)
tree.set(2, 2)
tree.set(3, 3)
tree.set(4, 4)

hashTree0 = tree.hash()

witnesses = []
witnesses.append(tree.setWithWitness(1, 2))
witnesses.append(tree.setWithWitness(2, 3))
witnesses.append(tree.deleteWithWitness(3))
witnesses.append(tree.proveKey(4))

hashTree1 = tree.hash()

partialTree = PartialTree(hashTree0, witnesses)
partialTree.set(1, 2)
partialTree.set(2, 3)
partialTree.delete(3)

assert partialTree.verify(4, 4)

assert partialTree.hash() == hashTree1

partialTree.set(3, 4) # error: no witness for setting key 3
partialTree.delete(4) # error: no witness for deleting key 4
partialTree.verify(4, 5) # error: no witness proving key 4 is set to 5

Diagram

This is a diagram to explain how updating/verifying keys should work.

Currently, the tree root can be calculated by calculating: (using x = 1)

l0 = hash(x || 2)
l1 = hash(l0 || l0_sibling)
root = hash(l1 || l2_sibling)

We can prove 1 is in the root by verifying that when 1 is plugged in for x, the state root is returned.

We can also update the tree by changing 1 to another value, yielding a new state root.

The PartialTree should also keep track of changed values which should take priority over proving in the tree. Because the state root will be different after modifying the tree at all, proving will have to use the original state root. Proving a value that was not modified will obviously verify. Proving a value that was modified will verify because the modified value is cached.

In the diagram above, the yellow node is the node to update/verify and the red nodes are the witnesses needed.

The witness tree should store witnesses on the opposite branch to where they actually are in the tree. In the example above, the witnesses are all on the right branch on the tree. The witness tree should actually store them on the left branches of the tree. (Hopefully this doesn't conflict with how a CSMT is defined).

https://goreportcard.com/report/github.com/phoreproject/synapse

Split up some state functions to decrease cyclomatic complexity.

Tests sometimes randomly fail with this.

The command "golangci-lint run --disable megacheck" exited with 4.

Ask peers for other peers.

https://godoc.org/github.com/libp2p/go-libp2p-discovery

The Synapse module should tie all current module together. It will multiple modules together and allow them to be run from a single process with a YAML config file.

First, all of the configs for apps should be YAML serializable/deserializable. Then, we need to implement a common app interface. Finally, we write the synapse module to tie all of the modules together.

The wallet should have the following commands:

• getbalance <addr> - gets the balance of an address
• sendtoaddress <fromaddr> <toaddr> <amount> - sends money to a certain address
• redeem <toaddr> - redeems premine

Sorry to be the bearer of bad news, but: I just stumbled across this project and I'm concerned that the name collides badly with https://github.com/matrix-org/synapse - the reference Matrix server implementation. Given Matrix is in a similar space (decentralised communication) and bears a lot of similarities with blockchains (we actually use replicated Merkle trees for decentralisation), I'm worried that users might get badly confused between the two. Matrix's Synapse even has sharding work for scalability, for instance - https://matrix.org/blog/2020/11/03/how-we-fixed-synapses-scalability.

So... given this project hasn't had that much visibility yet (e.g. only 9 github stars, relative to matrix-synapse's 6.8K) and is relatively new (matrix-synapse has been around and accelerating since 2014), I was wondering if you might consider renaming at this point to avoid future confusion? thank you! :)

Tracking issue for Phore Synapse main network

Currently, the max key is calculated on the fly in CSMT, but it really should be calculated when inserting.

On recursing back, on the way up all the hashes and max-key values along the minimum distance path are readjusted.

https://eprint.iacr.org/2018/955.pdf

Currently, to run a local testnet, you run with regtest.json with rootkey testnet even though there is already a testnet.json, but that's for a different purpose.

This all needs to be organized and documented.

Process block signature validation in parallel for the current epoch while syncing and then set a flag to skip signature validation on processing. Then, we can sync 8 blocks at a time and process them each as they become ready.

Validate signatures 1-8 in parallel (8/numcores)
Process blocks 1-8 skipping signature validation (8)
--------
Total Runtime = 8 + 8/numcores

vs.

Validate block 1 (1)
Process block 1 (1)
Validate block 2 (1)
Process block 2 (1)
Validate block 3 (1)
Process block 3 (1)
Validate block 4 (1)
Process block 4 (1)
Validate block 5 (1)
Process block 5 (1)
Validate block 6 (1)
Process block 6 (1)
Validate block 7 (1)
Process block 7 (1)
Validate block 8 (1)
Process block 8 (1)
--------
Total Runtime = 16

There should be a GetHash method for each of these takes the hash of all of the elements of each to validate state. We also possibly want this to be able to be updated without the entire tree, so possibly a sparse merkle tree would be the best route.

https://eprint.iacr.org/2018/955.pdf

This involves adding an interface for checking/sending broadcasts to the beacon chain and then updating the shard code to use those broadcasts.

For syncing/propogation, the peers will send the client a block hash and the client will download the full block/transaction from IPFS. This improves interoperability.

i.e. setting both finalized state and finalized block node

The shard module will execute transactions and generate a new state root based on witness/transaction packages received from relayers.

• Allow shard module to save/load from disk (#89)
• Allow shard module to communicate via P2P for syncing, and block/transaction propagation (#81)
• Allow shard module to execute transactions and update state root (#90)
• IPFS connection to handle transferring state, transactions and blocks (#91)

Synapse should close the database cleanly when CTRL-C is run.

If the beacon chain lags, re-request epoch data to make sure valid block can be created.

The log15 library doesn't allow global level setting. Testing is currently printing out a ton of logging which it shouldn't. We can't set the log level globally so we can't stop this behavior.

Reproduce:

1. Create a EpochInformationRequest.
2. Set EpochInformationRequest.EpochIndex to very large number (tested 10000000).
3. Call a Beacon node's GetEpochInformation with the request.

The Beacon node will eat up all RAM and freeze the OS.

Reproduce:

1. Create a AttestationData.
2. Fill AttestationData with wrong data. Especially, set the hashes with random data.
3. Call a Beacon node's SubmitAttestation with the request.

The Beacon node will return success.
Expect: Beacon should report error.

Reproduce:

1. Create a MempoolRequest.
2. Set MempoolRequest.LastBlockHash to random hash.
3. Call a Beacon node's GetValidatorInformation with the request.

The Beacon node will return success.
Expect: Beacon should report error because the request type is wrong (it should be GetValidatorRequest, but here is MempoolRequest).
This can be reproduced in Python since Python is dynamic type.

Branch: master

Code (in validatormanager.go):

// NewSlot is run when a new slot starts.
func (vm *Manager) NewSlot(slotNumber uint64) error {
	earliestSlot := vm.latestEpochInformation.earliestSlot
	logrus.WithField("slot", slotNumber).Debug("heard new slot")

	///////////////////////// here caused index out of range
	proposerSlotCommittees := vm.latestEpochInformation.slots[int64(slotNumber-1)-earliestSlot]

Stack trace:

panic: runtime error: index out of range

goroutine 1 [running]:
github.com/phoreproject/synapse/validator.(*Manager).NewSlot(0xc0000c82c0, 0x21749, 0xc000083ad8, 0x1)
	E:/projects/wqking/go/src/github.com/phoreproject/synapse/validator/validatormanager.go:267 +0xef8
github.com/phoreproject/synapse/validator.(*Manager).ListenForBlockAndCycle(0xc0000c82c0, 0xc000062e40, 0xada960)
	E:/projects/wqking/go/src/github.com/phoreproject/synapse/validator/validatormanager.go:422 +0x69a
github.com/phoreproject/synapse/validator.(*Manager).Start(...)
	E:/projects/wqking/go/src/github.com/phoreproject/synapse/validator/validatormanager.go:437
github.com/phoreproject/synapse/validator/module.(*ValidatorApp).Run(0xc00009ab40, 0x18, 0xc0000640e0)
	E:/projects/wqking/go/src/github.com/phoreproject/synapse/validator/module/app.go:105 +0x661
main.main()
	E:/projects/wqking/go/src/github.com/phoreproject/synapse/cmd/validator/synapsevalidator.go:28 +0x1d3

The BLS library was recently updated to allow public keys in G1. Update our wrapper to use this implementation.

Also, data types need to be updated to reflect that the public key now takes 48 bytes and the signature takes 96 bytes.

In a simple test (not many slots, maybe just one or two days), a lastSlotReceipts can hold more than 5M receipts, which is more than 100M RAM. And if there are more slots, I ever observed it uses too much RAM and crashes the OS.

I'm not sure if it can be eliminated, if not, we may need to use external database for it instead of residenting in memory. If we are going to use database, I can do it.
For the choice of database, current database for the chain uses very much disk. I think SQLite maybe better. The disadvantage of using SQLite is that we introduce a new kind of database to Synapse.

Currently the folder 'blockchain' and the package 'blockchain' are used by beacon chain, and 'database' is used by beacon chain too.
If the shard chain is under the same name, it will be confusing.
So we may consider to use 'beacon' for beacon chain related stuff, and 'shard' for shard chain?

test

This should be done similar to the beacon chain and we'll probably want to split the folders up so that we can run the shard and beacon chains more separately.

Add latest block to BlockMessage. When a client receives a block message where the last block isn't the latest block, request more blocks by sending a GetBlockMessage with the current chain locator.

This will include both a gRPC interface and a JSON RPC interface for easy interaction with the old Phore API.

On the shard chain, we include proofs in each block proving the position and public key of a validator with a beacon chain block. The following conditions have to be verified in order to enforce validity of shard blocks:

• Block hash and signature must validate with the included public key in the proof.
• Proposer index + shard must match algorithm for finding proposer index.
• Shard block proof must hash to finalized beacon chain block ValidatorProof .

If an attacker wants to fake a shard chain block, they would have to fake the validity of the public key included in the proof. To do that, they would have to have a finalized block in the beacon chain with a fake public key included. To do that, they would have to finalize a beacon chain. So, any attack that passes these 3 checks must have faked a finalized beacon block and we assume that is secure.

Shard proposer algorithm

To find the proposer of a shard block, we need an algorithm that ensures that we pick a proposer in the committee of the shard block and picks a different, randomized proposer for each block. The randomness is already taken care of because of the shuffling that happens with validators, so we'll just choose the n'th validator in the committee to propose the n + EPOCH_LENGTH * m where m is the EpochIndex block. So, the 0th validator proposes the block corresponding to EPOCH_LENGTH * m, 1th to EPOCH_LENGTH * m + 1, etc.

In the beacon validator proofs, we only need to keep track of EPOCH_LENGTH validators per shard. So, for the validator proofs, we'll set the key as hash(shard + slot) where shard is the committee the validator is assigned and slot is the slot the validator is assigned.

Currently the node addresses look like /ip4/0.0.0.0/tcp/11781/ipfs/12D3KooWSzvx4mxBSGhLzqS3gLp4wrGqivLuNghZadTgH1R1fbVR, which uses IPFS protocol. There are several evidence showing that IPFS is deprecated and it's replaced by P2P.

Evidence 1, in multiformats/go-multiaddr/protocols.go source code,

P_P2P     = 0x01A5
P_IPFS    = 0x01A5 // alias for backwards compatability

Evidence 2, Python version libp2p has nothing about IPFS, and all its example and test code use p2p.

Current problem is that if we continue using IPFS, I'm not sure if py-libp2p can parse the nodes' addresses.

Update github.com/btcsuite/btcutil to be Synapse compatible.

Specifically, do the following:

• Move the hdkeychain folder into synapse wallet folder.
• Remove references to chaincfg.Params and replace with constants that already exist in Synapse code
• Replace btcec.Pubkey/PrivateKey with secp256k1.PublicKey/PrivateKey

This way, we can do one single verify instead of three per-epoch.

First, we need a relayer module so that the shard module can get transactions to send. Dependent on #77