Fingerprints, Cryptographic Signatures and Proof of Work
Fingerprints are how objects refer to other. A fingerprint is a SHA256 hash of the object. Signatures are how objects are linked to their creators. A signature is an ECDSA signature with the user's private key, and can only be created by the user creating the object. Signatures are optional, it's OK to be anonymous and thus have no key and no signatures. Proof of Work provides protection against spam and DDoS by creation of objects computationally expensive enough to make bulk creation infeasible.
All entities except Address have the fields of Proof of Work, Signature, and Fingerprint. When creating objects, proof of work happens first, signature happens second, and fingerprint happens last. When verifying, fingerprint is verified first, signature is verified second, and PoW is verified last. Failure of any of these checks should cause the object to be thrown out with no further processing.
Fingerprint is only done on the immutable parts of an object. Signatures and PoWs are done for immutable and mutable parts of the objects. An initial PoW covers both mutable and immutable parts of the objects, and is immutable. If object gets updated after the fact, a mutable UpdatePoW is created, which is recreated after every new update.
This UpdatePoW field does not break fingerprint because it is a mutable field not included in the fingerprinting input. Without further restrictions, this could have caused a loophole where a malicious third party can create an update to a post that is not his / hers. To prevent this, updates can only be created for entities that are signed, and the update needs to be signed by the same key as the key that signed the initial object.
Nulling out fields
Creating proofs of work, signatures and fingerprints require emptying out certain fields in the object you are working on while you are generating them.
- The empty state for string fields is "".
- The empty state for number fields is 0.
- The empty state for array fields is [].
Emptying out does not mean actually changing the objects in any persistent manner. It means removing data from the in-memory objects which are provided to these three services, so that the calculations can be performed correctly.
Creation steps should never remove data, though it can add data to the object (inserting the resulting fingerprint, PoW or signature).
Verification steps should never add or remove data to the object in a persistent way.
Order of processing
The order in which you should generate these is this:
1) Signature
2) Proof of Work (In the last step of PoW, PoW signs itself with the user's key. See "Why?" below for the reason.)
3) Fingerprint
Why?
Signature provides identification. PoW provides a guaranteed cost to the sender to prevent spam. Fingerprint provides addressability. If you have PoW before signature (the order being, Signature, PoW, Fingerprint), then signature itself will not be covered under the guarantee of PoW. A spammer can generate many users and use the same proof of work without expending the effort PoW attempts to enforce.
If we do the reverse (the order being, PoW, Signature, Fingerprint), and have signature before proof of work, then the proof of work can be replaced by third parties. A third party can generate another proof of work for the signed post, generate a new fingerprint, and release it as a new post that was created by the owner of the signature. This post would have to be the same, however, it would still be a different post with a different fingerprint (because of the different proof of work).
This post could be used to split votes to a post by generating hundreds of copies of the same post. Assuming a post would generate 200 upvotes and be visible as such, copying the same post 20 times and distributing it would generate 10 upvotes for each of the posts, all of which would be visible as a post with 10 upvotes, not 200. This could be used to effectively 'kill' posts.
The solution to this is to have the PoW sign itself with the private key, as part of the PoW process. This authenticates the PoW as generated by the original owner, and renders any posts with unsigned or malsigned PoW invalid.
Signature
Signature is the thing that makes the object be associated with you. If you are an anonymous user, you will not have a key, so you will not have signatures on any objects. If you do have a key (i.e. if you decided to pick an username) this is how other nodes verify that the objects are actually coming from you (more specifically, signed by a key that is only in your possession).
It's perfectly okay for an object to have no signature, however, clients can elect to not show or communicate anonymous posts due to end user preferences. On the other hand, not transmitting or showing objects with low proof-of-work levels and no keys are great ways to make sure the quality of objects shown is high.
The signature algorithm is ECDSA. The specific curve is given at the 'type' field of the key object, but is usually secp521r1.
Mind that different libraries of cryptography aren't necessarily interoperable, they sometimes provide outputs in different formats. Make sure that the library you are using is able to operate within what's available in the protocol, and can provide results that can be processed by others.
Signature format
Signature length will vary based on the algorithm, but here is an example:
0164a8bf064f64f54de95d3ad5f23c764b8db74950ec4fecfb2d44004b8e5c32689a8450c0afc4b38c03f2d06ac0a26275e46d3c643deb29f8900765d658b3c767fe-013d60e7a1b0a43a032de3e60c4134739cc519b1209b29ceeae365d75afa214b4d0811412e781ebf716c5cd78b4adb0d8296c85028e321cf1c6ae07183b6fb17226e
r and s being bigints, the signature format is hex(byte(r))-hex(byte(s)), the - being dash. You seek the dash and use it to split r and s. The format is dependent on the curve type provided in the 'type' field.
In your objects, the update signatures are verified against the key of the original signature so that the update cannot be made by a different key.
If you end up with a signature failure, just throw out the object. You should not block the key owner, because the failures could be due to modification by someone else.
Creating signatures
1) Convert your object to JSON
2) Empty out the Fingerprint, Hashcash, and all mutable fields (these should already be empty as they are not created yet at this stage)
3) Run Signature algorithm over the stringified version of the JSON object
4) Save it to the appropriate field of the object you just created the signature for.
Verifying signatures
1) Convert your object to JSON
2) Empty out the Fingerprint, Hashcash, Signature, and all mutable fields
3) Stringify your JSON object
5) Run the algorithm to verify
Proof of Work
Every entity in Mim allows the local computer to prove that it has spent a certain amount of CPU power to create it. The amount of work to be proved is variable and can be set by the end user. The remote computer has the right to refuse or not take into consideration objects that it deems insufficiently proven of work, so try to keep this as high as you can tolerate. This is a measure that makes it too expensive for spammers to create posts in bulk and DDoS the network.
Proof of Work in Mim uses Hashcash method, and is optional.
The proof of work function in Mim is SHA256 x 3.
Mind that an empty proof of work field is a valid object, but a false proof-of-work field in an object is not. If your object has empty proof of work, you can continue processing it and show / not show, or communicate / not communicate (to other nodes) based on your preferences. But if you receive a PoW that does not successfully verify, you have a malformed object, and you should throw it out without any further consideration.
The nodes can have different proof of work requirements for different objects and states.
An example signed proof of work would be this:
[version]:[difficulty]:[date]:[input]:[extension]:[salt]:[counter]:[signature]
An example unsigned proof of work would be this:
[version]:[difficulty]:[date]:[input]:[extension]:[salt]:[counter]:
(The trailing ":" needs to be present.)
As you can see above, while Mim uses the Hashcash PoW. However, Mim Hashcash declares itself by declaring the version as MIM1. It also omits the fields of date, input, and extension. This is because Hashcash format includes redundant data fields that are already expressed in other fields of a Mim object.
Creating proof of work
1) convert your object to JSON. Important: Your json should be bit-by-bit equivalent of JSON output of Golang's json.Marshal. If you are building a third party client, be very careful in testing that, otherwise your proofs of work will be invalid.
2) Empty out the Fingerprint, ProofOfWork itself, and all fields of the updateable field set (LastUpdate, UpdateProofOfWOrk, UpdateSignature).
3) Run Hashcash over the stringified version of the JSON object. This Hashcash is customised to Mim. It works the same, but check the source code for minor differences.
4) After getting the hashcash result, get the private key, sign the result. Add the signature to the end of the hashcash result.
5) Save it to the appropriate field of the object you just created the PoW for.
Verifying proof of work
1) Convert your object to JSON
2) Empty out the Fingerprint, Proof of Work and updateable field set fields (LastUpdate, UpdateProofOfWOrk, UpdateSignature).
3) Stringify your JSON object
4) Verify the PoW itself by running it through the signature validation process.
4) Remove the latter portion of your PoW field starting with the ":", including the ":". This part was the signature.
5) Run Hashcash Verify.
Fingerprint
Fingerprints are SHA256 hashes of the entire JSON of the object except mutable fields, and it is how objects refer to each other. If you have a thread, it will have the fingerprint of the parent board in its board field. You should always check to make sure fingerprint matches the object first before doing anything else with the object. If the fingerprint does not match, the object is malformed either in transit or intentionally. You should throw out the object with no further processing.
Creating fingerprints
1) Convert your object to JSON
2) Empty out all mutable fields
3) Run SHA256 hash algorithm over the stringified version of the JSON object
4) Save it to the appropriate field of the object you just created the signature for.
Verifying fingerprints
1) Convert your object to JSON
2) Empty out the Fingerprint and all mutable fields
3) Stringify your JSON object
4) Run the algorithm to verify
UpdateSignatures and UpdateProofOfWork
These fields are only available on objects which have mutable fields. These fields provide PoW and Signatures for the mutable fields of the object, and computed using all fields of the objects. In other words, the normal variations of Signature and ProofOfWork fields provide coverage for only the immutable fields and first versions of the mutable fields, but UpdateSignature and UpdateProofOfWork provide coverage for both immutable and mutable fields as they are updated.
Every time you change any mutable fields, you should be generating a new timestamp for the LastUpdate field, and creating new UpdateProofOfWork and UpdateSignature fields. Other nodes will apply the latest timestamped update onto the object they have, provided that your new PoW satisfies their minimum PoW requirements and the signature verifies. The reason there is a PoW on updates is to prevent any key holder from spamming the network with updates.
In short: when you generate an object, the PoW will be created for all fields of the object, including the mutable fields. When you update a mutable field, you should be generating a UpdatePoW, and that will be the new canonical PoW that supersedes the original PoW. The original PoW is maintained in the object because removing it would cause the fingerprint to not match.
Page Signatures
Every page that is generated by a backend is signed by that backend's key. This allows for remotes to ensure the authenticity of the pages, as well as prevent attacks where an attacker can copy over a backend's Node ID, and behave like it has nothing to send, thus setting timestamps in other remotes for that Node ID. These nodes would only connect for entities after that set timestamp, therefore blackholing the entities that node might have for the duration of the attack.
The signing of each page prevents this, because Node ID is the fingerprint of the backend's public key, and every remote that received a node first makes sure that the signature matches the Node ID provided, and then that the signature provided is the signature for the whole of the page given by the public key within the page.