Tendermint: Why `Vote.SignBytes` is a JSON string?

[nnkken]

I'm trying to implement a custom blockchain using Tendermint, and I want to have a Relay contract on Ethereum so that my ERC-20 token can transfer between Ethereum and the Tendermint blockchain.

To do so, I need to write a smart contract on Ethereum verifying the block header from Tendermint. While other parts go well, the format of Precommits annoys me.

The signature are signed on the SHA-256 hash of the SignBytes, which are JSON strings, so to extract block header hash from the message, the smart contract needs to parse the JSON string, which is quite expensive.

I'm now finding work around on this problem, and my question is, why Tendermint is designed to sign a JSON string instead of a binary one, say a structure encoded by Amino, or the Merkle root of the information in the precommits (just like the block header hash)?

[jaekwon]

Amino would work... do you think that would save on EVM gas costs?
The Merkle root won't work because then we're left with the problem of information withholding... and besides, the Round field only exists in the vote.

[nnkken]

Amino will be muching better than JSON string in EVM.

Are the SignBytes directly passed to other validators?
I thought the content of the vote are serialized into another format, packed together with the signature, then other validators receiving this could check the signature by deserialize -> generate SignBytes -> check the signature with SignBytes.
In this way, the content of the vote can be different from the SignBytes

Besides, when I look at the format of current SignBytes:

{"@chain_id":"test-chain-dvwvaa","@type":"vote","block_id":{"hash":"044B1440465176F74042ACF3493A6BEFB6616E1F","parts":{"hash":"7C563049D57AB3D16817CB9E739303A02D085E9F","total":1}},"height":2,"round":0,"timestamp":"2018-05-24T03:52:21.310Z","type":2}

I think most of the parts (all except timestamp) are fixed for a successful commit, so if timestamp is not part of the SignBytes, then when validating votes for a block header, the parser will only have to parse the vote once and then reuse the same hash of SignBytes to validate all signatures.
Since timestamp is important, maybe the signature can sign sha256(sha256(chain_id, type, ...), timestamp), such that for each vote, only the timestamps have to be parsed instead of the whole vote.

[ebuchman]

In this way, the content of the vote can be different from the SignBytes

Yes, that's how it is now. The vote itself is amino encoded and the sign bytes are JSON. The JSON is leftover from when we did JSON transaction sign bytes so users could verify JSON befor signing, but validator nodes don't have that requirement.

We should change this to use Amino - tagging #1568

[ebuchman]

so if timestamp is not part of the SignBytes

Yeh, we're working on removing it, so the timestamp can come from the proposer instead: https://github.com/tendermint/tendermint/pull/1615

[nnkken]

Since timestamp is important, maybe the signature can sign sha256(sha256(chain_id, type, ...), timestamp), such that for each vote, only the timestamps have to be parsed instead of the whole vote.

From the comments in #1615 , it seems the timestamp field will be kept in the votes, so will this suggestion be considered?

[ebuchman]

Yes we should still do this!

[adrianbrink]

Yes, that's how it is now. The vote itself is amino encoded and the sign bytes are JSON. The JSON is leftover from when we did JSON transaction sign bytes so users could verify JSON befor signing, but validator nodes don't have that requirement.

Even though votes don't have to be human readable, small HSMs such as the Nano Ledger S or CodeSign (Thales HSM) should be able to decode the sign bytes and verify that the signature wouldn't cause a height/round regression.

JSON is easy to decode on the Nano Ledger S, since it we already implemented it for user transactions.

Having an HSM at launch that can provide double-sign protection on the HSM itself and hence protect against host compromise would be extremely valuable and I think something we should work towards.

[ebuchman]

We need to make a decision on this and document/finalize.

Paging @Liamsi @zmanian @tarcieri @jleni @jaekwon also for input.

Surely it would be quite convenient to stick with what we have (JSON) because then

• we don't need to change anything
• it remains human readable
• we can get double signing protection in hardware sooner by reusing existing code for parsing JSON on ledgers

That said, Amino is probably the better choice, because

• encodings are smaller (presumably faster, too, but we should benchmark)
• we don't actually need humans to read these
• its pure proto3 here since there are no interfaces in the vote so its a unanimous format
• it will be cheaper to process in ethereum (but how much cheaper?)
• we probably require double-signing protection in software anyways to set up high availability validators

@nnkken can you estimate gas cost for parsing JSON vs Amino (ie. proto3)? Are there useful example deserializers in the EVM/solidity that we could look at?

If we switch to Amino, it will probably be months before we have an HSM that can read the sign bytes. This just means that until then, any double-signing protection will have to be in software (which might be required anyways for high-availability validators...)

We could also stick with JSON for launch, with the expectation that we will upgrade to Amino (eg. when HSMs are ready), but that will likely delay integrations with Ethereum and the building of Ethereum bridges/sidechains, which are a critical component of our value proposition.

[liamsi]

I think the main reasons why we sticked with JSON are the ones you mentioned / listed. And from those, the main reason was that protobuf / amino did seem like overkill / infeasable on the ledger nano s (cc @jleni @cwgoes).

• its pure proto3 here since there are no interfaces in the vote so its a unanimous format

If we decide to switch to amino for vote, shouldn't we switch to amino for all the message a validator / the kms will sign?

• it will be cheaper to process in ethereum (but how much cheaper?)
• we probably require double-signing protection in software anyways to set up high availability validators

To make an informed decision, we need to know the answer to the first point above. Not sure, I understand the 2nd point yet. Although, if that means, having an HSM signing the votes (or the other messages) does not fulfil our security requirements in the case of highly available validators anyways, then I'm in favour of switching to amino. In conversations I had with @cwgoes and @jleni it sounded like this could mean that we can not sign messages on the ledger nano s though. Or at least we'd need a kind of amino (subset) implementation that does not need/use a heap.

but that will likely delay integrations with Ethereum and the building of Ethereum bridges/sidechains, which are a critical component of our value proposition.

And this delay would only be due to the gas price for parsing JSON?

[ebuchman]

was that protobuf / amino did seem like overkill / infeasable on the ledger nano s

Really infeasible?

If we decide to switch to amino for vote, shouldn't we switch to amino for all the message a validator / the kms will sign?

Yes, all the msgs are interface-free.

if that means, having an HSM signing the votes (or the other messages) does not fulfil our security requirements in the case of highly available validators anyways, then I'm in favour of switching to amino

The benefit of the ledger right now is we can implement the double signing prevention rules directly in hardware. But if we want a single validator to be supported by multiple HSMs with the same key for fault tolerance, then whatever is co-ordinating those HSMs (feeding them input, making decisions on their output) is a piece of software, and can get them to sign conflicting things (since each HSM won't know for certain what the other has signed), even though the individual HSMs would never double sign on their own.

That said, if we can do fault-tolerance without having to replicate the same key, for instance via multi-sig (implemented!) or via some other signature aggregation technique, then double-signing protection on the device would actually be effective.

Perhaps we should be considering multi-sig pubkeys for validators sooner than later to facilitate this?

And this delay would only be due to the gas price for parsing JSON?

Apparently. Though maybe @okwme or @mossid have a better idea.

[ValarDragon]

I'm confused as to why were concerned with the efficiency of the encoding scheme for what gets signed. (As afaict this isn't about how to store it) Signature verification takes orders of magnitudes longer than the encoding scheme for the message.

The message gets sha2 hashed before signing / verification, which has a block size of 64 bytes. So a couple bytes doesn't make a real difference to verification time.

I think we should stick with JSON until we have really good benchmarks indicating that this isn't the right solution. Given that we are currently using JSON, it doesn't seem like upgradability is an important part of this. So if we are switching encoding schemes for the sign bytes #postlaunch, cbor may make more sense here.

I definitely don't see value in delaying launch for this.

That said, if we can do fault-tolerance without having to replicate the same key, for instance via multi-sig (implemented!) or via some other signature aggregation technique, then double-signing protection on the device would actually be effective.

We could get DAVROS for validators :D

[nnkken]

Sorry that I forgot to provide testing results in the first place.

I have implemented a PoC in Solidity (the smart contract language of Ethereum) for parsing votes in both JSON and Amino. You may view the code here:
https://gist.github.com/nnkken/465df77ad28deffabf94b49b2298dc24

The code is based on a PoC of Ethereum-Tendermint relay contract a few months ago (when opening this issue), so some parts are already outdated (e.g. using RIPEMD160 in header simple tree hash instead of SHA256-truncated), but the parsing part should be more or less the same.

The requirement of the parsers is to confirm that the vote message has the right type (number 2, which means precommit), and then extract height and block hash from it.

For Amino, the parser tries to recognise each field number, typ3 and length by parsing varints, then extracts the corresponding values if the field number matches, skips the whole field otherwise.

For JSON, since parsing the whole JSON string is hard, I instead did it in a hacky way: the user provides the indices for the height, type and blockID fields in the JSON string, and the contracts verifies it by checking the prefix (JSON key and some symbols), then extracts the values. Not sure if there are any better ways.

The gas are logged by events injected in the code, before and after the concerned line. Since each event will cost about 2000 gas, the difference between 2 events is further deducted by 2000.

The gas consumptions are as follows:

Solidity v4.0.24, compiler optimization off:
Parsing Amino vote: 5133
Parsing JSON vote: 22275
Hashing JSON message: 1239
Recovering signature (secp256k1, using Solidity built-in function): 5217
Proving that the user-provided appHash is in the blockHash: 14340 (note that this is using RIPEMD160, which seems consuming more gas than SHA256-truncated in Ethereum)

Solidity v4.0.24, compiler optimization on:
Parsing Amino vote: 5752
Parsing JSON vote: 37983
Hashing JSON message: 1139
Recovering signature (secp256k1, using Solidity built-in function): 5187
Proving that the user-provided appHash is in the blockHash: 15424

Test input data are in the comments.

I have no idea why the optimized version consumes more gas. Maybe the optimizer optimizes the space consumption instead of the actual call? Anyway let's use the unoptimized version for comparison.

Suppose there are N validators, then for each commit to the relay contract, there will be N votes to hash, recover signer, parse and extract height and blockHash, while proving the appHash is in the blockHash is always run for once only, so below excludes the gas usage of the proving appHash part.

For Amino message, this will cost 5133 + 1239 + 5217 = 11589 gas per validator.
For JSON message, this will cost 22275 + 1239 + 5217 = 28731 gas per validator.

I personally think the difference is quite large.

[jleni]

JSON was preferred in the user app because one of the requirements indicated that it was necessary to parse generic messages, with no predefined schema. A layered dictionary structure had to be shown in the UI, etc. Parsing generic amino messages was not an option. In addition, there was already a amino to json implementation available. We could have gone with msgpack or similar but json seemed not a problem.

With respect to the validator app, I think the situation is different. While the json-based implementation is almost ready, moving to amino seems a good idea. The schema is well defined and only parsing two fields is necessary. Improving the proto layout could simplify this even further. I would suggest placing height/round at the beginning and ideally with some basic encoding (no zigzag, etc).

In addition to gas saving (@nnkken), I see a couple additional advantages:

• Avoid "canonical" json issues
• Smaller messages lead to faster APDU transfers
• Smaller messages allow keeping the whole vote in RAM (instead to having to swap to nvram). The problem with swapping to nvram is that this may result in unwanted wear.
• Simpler 2 field amino parsing will result in lower latency

I understand this is the current schema:

type Vote struct {
    ValidatorAddress Address   `json:"validator_address"`
    ValidatorIndex   int       `json:"validator_index"`
    Height           int64     `json:"height"`
    Round            int       `json:"round"`
    Timestamp        time.Time `json:"timestamp"`
    Type             byte      `json:"type"`
    BlockID          BlockID   `json:"block_id"` // zero if vote is nil.
    Signature        []byte    `json:"signature"`
}

is it too late for changing to something like this?:

type Vote struct {
    Height           int64     `json:"height"`
    Round            int       `json:"round"`
    ValidatorAddress Address   `json:"validator_address"`
    ValidatorIndex   int       `json:"validator_index"`
    Timestamp        time.Time `json:"timestamp"`
    Type             byte      `json:"type"`
    BlockID          BlockID   `json:"block_id"` // zero if vote is nil.
    Signature        []byte    `json:"signature"`
}

I understand that this would result in fixed offsets for Height and Round within the blob, allowing for almost no parsing at all.

[jleni]

By the way, another issue I see now, is that according to the specs, the whole blob was supposed to be signed. But now I see that the blob will contain the signature.
That means that some amount of parsing needs to happen, etc. This is something that would not be easy to support whether that is amino or json.

I think it would be important to separate the unsigned blob from the signed blob. Something like:

type UnsignedVote struct {
... height, round, etc. ...
}

type Vote struct{
    UnsignedVote unsignedVote
    Signature []byte
}

Otherwise validators are forced to have a much better understanding of amino, combine fields, etc.

[okwme]

For context, today's "SafeLow" gas price of 1.6 GWEI and a "Fastest" gas price of 30 GWEI at today's price of ~$290/Eth would result in the following costs:

$0.00536 @1.6 GWEI for Amino message (11589 gas per validator)
$0.10083 @30 GWEI for Amino message (11589 gas per validator)
$0.01334 @1.6 GWEI for JSON message (28731 gas per validator)
$0.24995 @30 GWEI for JSON message (28731 gas per validator)

link

[ebuchman]

Thanks for all the information everyone!

By the way, another issue I see now, is that according to the specs, the whole blob was supposed to be signed. But now I see that the blob will contain the signature.

@jleni the actual struct being signed is this one: https://github.com/tendermint/tendermint/blob/develop/types/canonical_json.go#L35

The whole thing is signed, and its in "canonical json" form. If we drop the JSON, we can probably re-order the struct.

As for JSON vs Amino in ETH, looks like the difference is about 2.5x. It's not insignificant, but also not an order of magnitude (phew!).

The problem with swapping to nvram is that this may result in unwanted wear.

This sounds like it could be a real concern. Can we say for certain that we need to do this with the JSON but not with the Amino ? What would the expected lifetime of the Ledger Nano S be if we have to do this ~3 times per second (ie. propose, prevote, precommit)?

[jleni]

The opposite, I think in this sense amino is better as it will result in smaller messages.

I would say.. as long as votes are below 2K is all fine and there is no need to use nvram. Between 2-2.5K it gets hard but maybe we can still keep it in RAM.

Above that swapping is necessary and I would say that 3/sec is not acceptable. At 3x/sec, even with some scheme to schedule the wear, it will be less that an month. Assume 30K of nvram with 500K cycles, and transactions of 3K. That results in 5M possible writes. At 3/sec, that is 10.8K/hr.. total 462hours.

Anyway, it amino can simplify the layout to the point where extracting height/round is easy/predictable. I would definitely go with amino. It will result in smaller messages, faster parsing, lower signature latency.

[ebuchman]

I would say.. as long as votes are below 2K is all fine and there is no need to use nvram. Between 2-2.5K it gets hard but maybe we can still keep it in RAM.

Oh I think the JSON will defntly be less than 2K. The struct is pretty small and itself contains only about 100 bytes of data, so maybe the JSON will double that at most. In any case we're talking at most a few hundred bytes.

Anyway, it amino can simplify the layout to the point where extracting height/round is easy/predictable. I would definitely go with amino. It will result in smaller messages, faster parsing, lower signature latency.

Ok. Sounds like an absolute all around win to move to Amino. I will get an ADR written up this week to address this. Given that this issue was actually included in the current iteration, I see no reason not to strive to get this included in the next release (v0.24.0).

Thanks!

[ValarDragon]

I feel like we haven't looked at all the options sufficiently yet. The reason that json blows up in size is that it includes the key names. If we're trying to remove this, this means the end application has to maintain a map from value to name. (For ui purposes)

In this same model, we can just encode as raw bytes with perhaps length prefixing. This will be as easy if not easier to write in hsm languages (no concept of field numbers or upgrade paths needed here). It will also be more efficient. All that's needed is the name to value map that were already saying the ledger / evm code needs to maintain.

Implementing amino isn't simple (iirc it took us awhile to make the golang implementation). There is an argument against a custom encoding scheme, due to mental complexity. That argument makes sense, but let's weigh all the options.

Another option is to remove the key prefix from the json, which will reduce its size as well. (Maintains ease of implementation)

[jleni]

No, definitely a complete amino implementation is out of scope. That would be a significant effort.
The point is that when the votes are encoded with amino, if the appropriate layout is used, the position of height and round is addressable with an offset in the amino blob. Basically, from an HSM perspective it would be a binary blob where these two values are at the beginning... From the HSM perspective, json or amino (hardcoded offsets) are feasible.

What you are describing about key values, applies to the user app. That is also out of scope and I would not change that at all. I think the discussion is limited to the validator case.

Now, with respect to EVM, both json and amino seem expensive. I guess it is possible to use some easier encoding that also facilitates things in the EVM?

[ValarDragon]

Oh your totally right, reading fixed offsets from the blob would be easy.

For the evm benchmarks, there should be no signature recovery, as were doing ed25519 signatures. If ed25519 isn't built into solidity, then that will far dominate verification time.

[tarcieri]

In this same model, we can just encode as raw bytes with perhaps length prefixing. This will be as easy if not easier to write in hsm languages (no concept of field numbers or upgrade paths needed here).

Absence of extensibility mechanisms has a recurring problem of coming back to haunt various protocols.

It seems like something in the way of an Amino message with pseudo-canonicalization applied accomplishes this while leaving the door open for future extensibility.

[nnkken]

The main workload for parsing the Amino vote is to lookup each field to find a specific field number (which is a varint with dynamic length, so again parsing needed), then extract the length and the "length of the length" (since the length itself is also a varint) of the value. So if positions and lengths are fixed, the "parsing" will become trivial.

For extensibility, Amino seems overkilling, since it is quite impossible to drop fields or change orders of the fields (which is bad for a canonical message for signing). If we are only going to append additional fields in the future, then maybe a fixed length version field at the beginning is enough?

The varint format is also undesirable, since for votes, the cost of a fixed 8-byte integers is negligible even for EVM or HSM, while the parsing cost matters more.

For comparison, I've added a test on EVM for parsing a simply packed vote bytes. The format is 8-byte big-endian height, 8-byte big-endian round, 1-byte vote type, 20-byte block hash, then the remaining (maybe variable length) fields.

During the test, I found that the gas cost of events is 1336 instead of 2000, so I updated the previously tested numbers below:

Solidity v4.0.24, compiler optimization off:
Parsing Amino vote: 5797
Parsing JSON vote: 22939
Parsing simply packed vote: 259
Hashing JSON message: 1903
Recovering signature (secp256k1, using Solidity built-in function): 5881
Proving that the user-provided appHash is in the blockHash: 15004

For Amino message, this will cost 5797 + 1903 + 5881 = 13581 gas per validator.
For JSON message, this will cost 22939 + 1903 + 5881 = 30723 gas per validator.
For simply packed message, this will cost 259 + 1903 + 5881 = 8043 gas per validator.

For the price of $290 USD/ETH, this means:

$0.006301584 @1.6 GWEI for Amino message (13581 gas per validator)
$0.1181547 @30 GWEI for Amino message (13581 gas per validator)
$0.014255472 @1.6 GWEI for JSON message (30723 gas per validator)
$0.2672901 @30 GWEI for JSON message (30723 gas per validator)
$0.003731952 @1.6 GWEI for simply packed message (8043 gas per validator)
$0.0699741 @30 GWEI for simply packed message (8043 gas per validator)

For the evm benchmarks, there should be no signature recovery, as were doing ed25519 signatures. If ed25519 isn't built into solidity, then that will far dominate verification time.

Native ed25519 support on EVM is planned, but not yet implemented. See: https://github.com/ethereum/EIPs/blob/master/EIPS/eip-665.md

For now I configurated Tendermint to use secp256k1 in the config file.

[ValarDragon]

Absence of extensibility mechanisms has a recurring problem of coming back to haunt various protocols.

You're right, this is an important thing to do. However I don't think is solved by just switching to amino. We would have to have a full protobuf implementation in the HSM langauge, or else were back to square one. (We want to make an update, but have to update the HSM code as well) So unless we plan on writing a full protobuf implementation, using amino for upgradability seems kind of moot to me.

I don't like the idea of optimizing our decision decisions for Solidity. I would much prefer working in the benchmarks of nanoseconds of processing time, RAM used, and bandwidth.

Overall I am unconvinced that parsing time really matters for anything except solidity, because all signature verification algorithms have to hash the message. (And Solidity subsidizes hashes iirc) Spatial efficiency of the encoded struct could reduce the hashing time, which would have a bigger overall impact than just parsing time. (Plus bandwidth time, if we consider this going over the internet to an HSM, though the difference the byte length causes is probably neglible) Could we get benchmarks for {amino / json} encoding / decoding time in nanoseconds in the golang implementation, so we can compare against hashing time?

However I am a fan of using a simply packed vote. This has us maintain the same assumptions that we are currently maintaining. (Upgrade is via hard upgrade to all code) Amino makes sense if we are willing to invest in HSM and Solidity protobuf implementations. This may be worth the trade-off, we are considering a couple changes to the vote structure in the future, i.e. Removing timestamp for BLS, including additional data for DKG's.

Also whats causing these large solidity parsing times for JSON's? How much would reducing key size improve parsing time?

[nnkken]

Also whats causing these large solidity parsing times for JSON's? How much would reducing key size improve parsing time?

I haven't done a detailed analysis on time consumptions of each parts, but I think the main difference is that the numbers / bytes are in ASCII form, so the parser needs to parse them back into an actual numbers / bytes. Especially for the 20-byte block hash, which needs to parse 40 hex digits, while in Amino / simply packed votes it is already in binary form and doesn't need any parsing.

Since I want to prevent parsing the whole JSON string, for the JSON vote message, I additionally required user to input the indices of the starting point of the key of the required fields, and use the key as prefix to validate that the indices actually correspond to the fields.

So I didn't parse any key fields (other than a simple byte-by-byte comparison). Reducing key size won't help and removing key fields would make it harder to use the same hack, further increasing the cost.

[jleni]

@ValarDragon I disagree with this:

You're right, this is an important thing to do. However I don't think is solved by just switching to amino. We would have to have a full protobuf implementation in the HSM langauge, or else were back to square one. (We want to make an update, but have to update the HSM code as well) So unless we plan on writing a full protobuf implementation, using amino for upgradability seems kind of moot to me.

When the blob layout leaves height/round at the beginning and there is no change in their offset, you can upgrade the vote without problems and without having to modify the HSM code. Remember that the HSM will never parse the amino blob. It will just extract two values at the beginning of it. I put emphasis in using the word blob, because to the HSM it is just a bunch of bytes with no meaning (except from height/round). This mean that an upgrade path is possible without having to make any changes to the HSM.

[jleni]

This is another disadvantage of json:

Overall I am unconvinced that parsing time really matters for anything except solidity, because all signature verification algorithms have to hash the message.

HSMs are not very powerful, while hashing takes time, it is typically hardware accelerated. However, parsing it is not and given that "canonical" JSON does not really exist. We need to add checks, etc. This means that JSON takes a bit of time to parse. Extracting uint64 from a known offset, would be definitely faster. One of the key non-functional requirements for the HSM is that latency (when signing) should be low. Removing complex parsing could help.

I personally would be more confortable with a hardcoded (@ValarDragon) or something a bit more standard such as MsgPack. However, from an architectural point of view, I am very much aligned with @tarcieri . Not providing an upgrade path will definitely bite us back in the worst moment.

[ebuchman]

Parsing Amino vote: 5797
Parsing JSON vote: 22939
Parsing simply packed vote: 259

This is telling ^^ ! That's 20x between simply packed bytes and Amino.

What if we used fixed lengths for everything but kept it in Amino (ie. proto3) ? This should be possible for everything except the ChainID and possibly the timestamp. But we could conceivably make the integers fixed length instead of varint. @Liamsi does amino support that feature of proto3 somehow?

[liamsi]

But we could conceivably make the integers fixed length instead of varint. @Liamsi does amino support that feature of proto3 somehow?

Yes, it does support fixed length integers. You can just add a tag (fixed64 or fixed32) and (u)int(32/64) will be fixed length encoded.
See for example: https://github.com/tendermint/go-amino/blob/faa6e731944e2b7b6a46ad202902851e8ce85bee/tests/proto3/proto3_compat_test.go#L21-L23
Amino then encodes exactly as [proto3]'s (s)fixed(32/64).

[ValarDragon]

When the blob layout leaves height/round at the beginning and there is no change in their offset, you can upgrade the vote without problems and without having to modify the HSM code. Remember that the HSM will never parse the amino blob. It will just extract two values at the beginning of it. I put emphasis in using the word blob, because to the HSM it is just a bunch of bytes with no meaning (except from height/round). This mean that an upgrade path is possible without having to make any changes to the HSM.

This is not an upgrade path. Everything in a vote is something an HSM should know about. (Otherwise why is it in the vote / being signed over in consensus) The Timestamp should be checked that it is monotonically increasing. Any additional DKG data should be checked for upgradability (or more likely generated from the HSM). So saying that just having the height and round at fixed offsets of the blob doesn't mean we have an upgrade path, but instead means we aren't checking the timestamp in the current implementation. If we _were_ checking Timestamps (as we would in an ideal world) this plan would fail when we want to remove them. See here for how protobuf removes fields: https://stackoverflow.com/questions/27610647/protocol-buffers-how-is-the-extensibility-and-backward-compatibility-achieved.

So "fixed offsets in an amino blob" does not mean we have upgradability at all. We have to be parsing the protobuf completely.

This is telling ^^ ! That's 20x between simply packed bytes and Amino.

I do agree with simply packed bytes (if we're fine with the upgradability concerns), however lets please use nanosecond benchmarks, not solidity gas costs. (Which are known to have differences / subsidize things differently)

What if we used fixed lengths for everything but kept it in Amino (ie. proto3) ? This should be possible for everything except the ChainID and possibly the timestamp. But we could conceivably make the integers fixed length instead of varint. @Liamsi does amino support that feature of proto3 somehow?

This combines the bad parts of both sides but maintain some simplicity. We have the extra space of amino relative to simply packed bytes, and we've lost the upgradability of amino since were not parsing it correctly. So we lose the entire upgrade path argument. I feel like using amino vs a plain struct isn't retaining us much simplicity

I think we should either accept lack of upgradability and use a fixed struct, or parse amino fully. (So that we can retain the upgradability argument)

If the argument is that "Lets be upgradable for everything but the height/round", then we can use the protobuf required flag for those fields.

[jleni]

@ValarDragon
mm, It was not specified that timestamp should be checked. @ebuchman @adrianbrink can we open another ticket or update the specs if this is the case?

The fixed offset "hack" was only for the first two fields used by the HSM. The upgrade path does not refer to the HSM.

Based on the specs we have, the HSM works as an oracle.

• It receives a blob from KMS/signatory
• retrieves height/round and applies some rules to confirm the sign request is valid
• hashes the complete blob and signs.

All other fields are obscure to the HSM. When discussing an upgrade path, I clearly meant that it would be possible to add additional fields to the blob. Obviously, if you remove any of the fields that are being used by the HSM.. you are directly affecting it and there is clearly no other solution than changing the code.

From my perspective, I am happy as long as the following considerations are taken into account:

• blobs should not go beyond 1.5 kilobytes
• the encoder must output a canonical message
• parsing should be as simple as possible, we need to reduce processing as much as possible to keep latency low.
• if extensibility ( and I have carefully chosen this word) is a requirement, it would be important to plan for backward compatibility.

I think we should either accept lack of upgradability and use a fixed struct, or parse amino fully. (So that we can retain the upgradability argument)

Parsing amino fully is definitely a no for an HSM. Two main reasons:
1) any changes in the proto file requires recompiling, that is the way protobuf works.
With the fixed offset we were avoiding this by just peeping two values.. but if everything should be parsed, every little change to the proto means recompiling the hsm app.
2) it is too complicated, we don't have dynamic memory, etc. Just dealing with a dictionary is a mess.

If the argument is that "Lets be upgradable for everything but the height/round", then we can use the protobuf required flag for those fields.

I understand that the required flag is some old thing from protobuf 2. This was removed from protobuf 3.

[jleni]

(I edited the list of requirements in the previous post. A canonical form is necessary.)

[ValarDragon]

I think we should do the simple encoding then with fixed offsets. We retain the append only backwards compatibility for checked fields.

Regarding the timestamps, didn't mean to suggest that that's a requirement for launch, but instead that that is a component of upgradability that the amino and parsing fixed byte offsets doesn't handle.

[jleni]

Sounds good to me. If you can propose some scheme, I am happy to follow.

[tarcieri]

I think we should do the simple encoding then with fixed offsets.

If you do that, I'd suggest a minimum viable extension mechanism: allow overlength messages.

If you want some rhyme/reason to it: add an extension length field (could even be just 1-byte) and ensure the overlength data matches it (i.e. always zero if no extensions are used).

[ebuchman]

Everything in a vote is something an HSM should know about. (Otherwise why is it in the vote / being signed over in consensus) The Timestamp should be checked that it is monotonically increasing. Any additional DKG data should be checked for upgradability (or more likely generated from the HSM)

No we don't really need to check this stuff. The only thing that matters for punishment currently is height/round. We're also planning to remove timestamp from votes eventually so we can use the proposer-based BFT mechanism and have a separate consensus message at lower frequency for syncing time.

This combines the bad parts of both sides but maintain some simplicity. We have the extra space of amino relative to simply packed bytes, and we've lost the upgradability of amino since were not parsing it correctly. So we lose the entire upgrade path argument. I feel like using amino vs a plain struct isn't retaining us much simplicity

I don't see this. I'm quite hesitant to add a new ad hoc serialization to Tendermint given we already have so much going on. Amino makes the most sense given existing design choices, and using the fixed size ints will make it much easier to parse fields out.

[ValarDragon]

If we don't need to check that stuff, then I agree with it not being in the vote.

I agree, another serialization scheme is a bad idea. Size of votes for signatures doesnt really matter that much, so it's not worth introducing another encoding scheme for. Using amino to avoid a new serialization scheme makes sense, as long we aren't making the argument that the amino switch is for upgradability(which it seems were not), since were not parsing in a manner where any relevant field is upgradable. I do think every field in a vote should ultimately either be checked by an hsm or not be in the vote, hence my prior objection to the upgradability argument for fixed byte parsing amino. (We only can do backwards compatible appends which other simpler / more efficient things provide as well)

I'm on board with switching to amino, and using fixed byte offsets.

[ValarDragon]

Actually, I'm not sure anymore for the ideal scenario. (I still agree with amino for prelaunch) #Postlaunch, I don't think adopting 3 encoding formats is unreasonable:

• JSON for human readable things
• Amino for upgradability
• Fixed Offset Struct Encoding when we want hardware support (This has the same upgradability as this thread is proposing, append-only)

Fixed Offset Struct Encoding is easier to implement in hardware, is more efficient encoding, and makes the exact upgradability offered much clearer. I think there is a standard here that can be adopted, and we could use another codec as well for this.

Prelaunch, I'm still in support of amino. Its probably not a good idea to derail this conversation with proposing to standardize a third encoding format though, so if anyones else wants to discuss this I can make another issue for it.

[tarcieri]

@ValarDragon with Protos (and Amino too I believe?) you can encode a message composed of fixed-width integers and fixed-width bytestrings in a specific order and get a message which always has fixed offsets for every value. If you ensure the message is encoded that way you can ignore the Proto/Amino framing and just treat it as fixed offsets.

[ValarDragon]

Yes, but then you have the field numbers and things. Its a slower encoding process. I guess your right, speed of encoding probably doesn't matter though, so we would never need a third encoding type standardized. I retract the previous proposal then, you're right.

[tarcieri]

@ValarDragon in a pinch you can do something like this, not that I'd recommend it but depending on circumstances it can get the job done: https://github.com/tendermint/signatory/blob/cb5fb0f12d85a798dbe8a1b53534e738ab060366/src/test_vector.rs#L38

[ebuchman]

If you do that, I'd suggest a minimum viable extension mechanism: allow overlength messages.

If you want some rhyme/reason to it: add an extension length field (could even be just 1-byte) and ensure the overlength data matches it (i.e. always zero if no extensions are used).

@tarcieri can you expand on what you mean here? You mean add a field that represents the "extra" length of the message beyond the expected size of the initial version? How does that compare to just including a version number ? I'm thinking of a message struct like:

message Vote {
    Version        fixed32
    Height         sfixed64
    Round         sfixed32
    VoteType    fixed32 // just need a `byte` but can protobuf do that?
    ChainID       string
    BlockID       BlockID
    Timestamp string
}

Note we include the ChainID so the same validator can sign on multiple chains - but if we want the same device to be able to be used on multiple chains, it needs to be parsing and remembering the height/round per chainID, which is probably out of scope for the short term.

[jleni]

A couple of comments on the proposed schema:

message Vote {
    Version        fixed32                      
    Height         sfixed64
    Round         sfixed32
    VoteType    fixed32 // just need a `byte` but can protobuf do that?
    ChainID       string
    BlockID       BlockID                      
    Timestamp string
}

BlockID if the type is complex, maybe is a good idea to leave it at the end?
Timestamp fixed64 can handle ~580years of unix time with nanosecond resolution or a LOT more if milliseconds are used. If necessary another fixed32 could be added.. just in case a few billion years is not enough :)
Height why signed here? is it possible to have negative heights?
Round why signed here? negative rounds?

Proposed:

message Vote {
    Version       fixed32                      
    Height        fixed64       
    Round         fixed32
    VoteType      fixed32
    Timestamp     fixed64
    BlockID       BlockID           
    ChainID       string             // at the end because length could vary a lot
}

[ebuchman]

BlockID looks like:

message BlockID {
  bytes hash = 1;
  PartSetHeader parts_header = 2 [(gogoproto.nullable)=false];
}

message PartSetHeader {
  int32 total = 1;
  bytes hash = 2;
}

It's just two hashes and an int. In theory we could also make it fixed size, at least for the sign bytes.

Timestamp should actually use google.protobuf.Timestamp which looks like:

message Timestamp {
  int64 seconds = 1;
  int32 nanos = 2;
}

Those also could be made fixed size for the sign bytes, but would diverge with what the rest of the codebase is using.

These BlockID and Timestamp fields don't need to be checked by the HSM yet, but could at some point in the future.

Height why signed here? is it possible to have negative heights?

Just for consistency with the rest of the codebase, which uses signed ints because they're used in arithmetic - we blogged about it. We could also change this for the sign bytes.

I wonder if its worth all these divergences from the rest of the codebase in the encoding of the sign bytes?

[jleni]

Timestamp: Yes actually I had that in mind.
Height/Round: Fair enough. Actually, it does not make sense to run < 0 with unsigned types. I would expect comparisons to be done before doing arithmetic operations but I see how this complicates things. Plus the lack of support in Java and the fact that the code is already there.. Let's definitely keep this as signed types.

This brings us to something like:

message Vote {
    Version       fixed32                      
    Height        sfixed64       
    Round         sfixed32
    VoteType      fixed32
    Timestamp     Timestamp         // << using protobuf definition
    BlockID       BlockID           // << as already defined 
    ChainID       string            // at the end because length could vary a lot
}

Last comment I have is VoteType. Do we want an enum there or fixed32 is fine?

[ebuchman]

Cool that's looking good.

VoteType in the code is just a byte and only takes on values of 0x1 or 0x2. We could save space using an enum (or just a non-fixed int) but not sure if its worth it, since this thing will always be easier to parse if we don't use varints (except for the ChainID string)

[liamsi]

I do not think it is absolutely necessary to save some bytes and try to optimize VoteType. On the other hand, even if this was varint encoded, we always know the length here, right? Wouldn't this still be easy to parse (0x1 or 0x2 will always be of length 1). Amino doesn't really support enums but is able to do the varint encoding, so it would work.

[jleni]

I guess what is missing is some feedback from @nnkken to be sure that any Solidity concerns are also addressed.

[nnkken]

The main overhead for JSON part are parsing and positioning, so any binary schema with fixed position fields will be OK.

For solidity, it will be more convenient if integers are in big endian. That said, conversion from little endian is quite simple and cheap, so taking care of other platforms like hardware wallets may have higher priority in this case.

[jleni]

@Liamsi I guess amino is the same as protobuf and store those as little endian right?

Solidity instructions have a cost and hardware wallets can handle anything without much trouble. It is easy to use bigendian in the HSMs. It is just that this might confuse people a bit.
Do the savings in Gas justify this?

[liamsi]

@Liamsi I guess amino is the same as protobuf and store those as little endian right?

Yes!

[nnkken]

A rough test shows that converting between big endian and little endian for a uint64 takes 241 gas, while for a uint32 it takes 119 gas (about half).

To convert the round and height numbers, it takes about 360 more gas, which is insignificant.

Also, most of the gas consumption is due to the fact that current EVM does not support bit-shifting natively, so the operation is simulated using multiplication / division with exponent. Bit-shifting will be native in the upcoming upgrade, so the gas usage will be further decreased (maybe about half?).

So my opinion is just use the native endianess for most of the target platforms.

Code sample:

        n = ((n >> 56) & 0x00000000000000FF) |
            ((n >> 40) & 0x000000000000FF00) |
            ((n >> 24) & 0x0000000000FF0000) |
            ((n >>  8) & 0x00000000FF000000) |
            ((n <<  8) & 0x000000FF00000000) |
            ((n << 24) & 0x0000FF0000000000) |
            ((n << 40) & 0x00FF000000000000) |
            ((n << 56) & 0xFF00000000000000);

[jleni]

Perfect! Sounds like we are almost ready to move forward :)
What do you think @ebuchman ?
I would leave this open a few more days waiting for comments @Liamsi @zmanian @tarcieri @jaekwon

message Vote {
    Version       fixed32                      
    Height        sfixed64       
    Round         sfixed32
    VoteType      fixed32
    Timestamp     Timestamp         // << using protobuf definition
    BlockID       BlockID           // << as already defined 
    ChainID       string            // at the end because length could vary a lot
}

Note: Little endian encoding as per default in amino

[ebuchman]

I think it's looking pretty great. Would love to get additional feedback but so far makes a lot of sense.

[liamsi]

Looks fine to me too!

[liamsi]

Im currently working on the kms side of this. The ChainID was previously not part of the Vote type. It was only added to the JSON while calling Vote.SignBytes(chainID string) []byte. I'm wondering if this field should be part of the actual type or if there will be a intermediate/"helper" type which will be amino encoded when calling SignBytes?

Just fledging out some implications: If we include ChainID in the original struct/type and not only in what will be encoded in SignBytes we need to change the Signable interface too.
Above, the Signature field is gone from the Vote. We might need two structs as @jleni suggested above: UnsignedVote and Vote (see https://github.com/tendermint/tendermint/issues/1622#issuecomment-414281264). Similarly, we'd need two such types for everything else that can be signed, implements the Signable interface (HeartBeat, Proposal, Vote).

[liamsi]

I think we should rename privval.SignVoteMsg to SignVoteRequest and (equivalent for HeartBeat, Proposal including ChainID excluding signature), encapsulate the proposed Vote as above and have a separate type for the signed reply; e.g. for Vote:

// this is an amino registered type; like currently privval.SignVoteMsg: 
// registered with "tendermint/socketpv/SignVoteMsg"
message SignVoteRequest {
   Vote vote;
};

and the reply thereof:

// also a registered type
SignedVoteReply { 
   Vote      vote
   Signature sig 
}

where Vote in both cases:

// vanilla protobuf / amino encoded
message Vote {
    Version       fixed32                      
    Height        sfixed64       
    Round         sfixed32
    VoteType      fixed32
    Timestamp     Timestamp         // << using protobuf definition
    BlockID       BlockID           // << as already defined 
    ChainID       string            // at the end because length could vary a lot
}

Any thoughts? cc @ebuchman @jaekwon @ValarDragon

[jleni]

I think that may make sense within tendermint, however, I would say we should not enforce protobut/amino replies in ledger firmware or signatory. In those case, the reply will be only the signature, that is..

reply = ed25519_sig(hash(vote_bytes))

I am not sure if there is already an agreement on which hash function will be actually used

[liamsi]

Makes sense. These messages would only be exchanged between tendermint <-> kms (or validators). The kms will send the vote bytes to the ledger, and include the reply (ed25519_sig(hash(vote_bytes))) in the SignedVoteReply.

[liamsi]

I am not sure if there is already an agreement on which hash function will be actually used

Do we actually need an additional hash? I mean ed25519 uses sha512 internally to hash the message (in this particular case vote bytes). We could as well do ed25519_sig(vote_bytes) directly. I think this was discussed somewhere else, too. Can't find it right now (maybe on slack).

[nnkken]

Is Tendermint going to support secp256k1 at launch?
Currently only secp256k1 is supported well in Ethereum, so I wish there will be at least a fallback option for using secp256k1, like what is implemented now.

[xla]

While we on the topic of changing the protocol between Tendermint and KMS can we expand the responses to carry proper ways of communicating errors? @Liamsi

[jleni]

@Liamsi cx_eddsa_sign API in the ledger operates over digests. This was the discussion around ed25519 and ed25519ph according to rfc8032. We need to leave the hash there for things to work. SHA512 is what we've been using.

@nnkken secp256k1 is used in the user app, not in the validators. If another signature type is used, then SignedVoteReply will need something to indicate that?

@xla I guess that is part of the "secret connection" right? not part of the SignedVoteReply that will be shared between nodes..

[tarcieri]

If another signature type is used, then SignedVoteReply will need something to indicate that?

In the past, we had discussed selecting which signing key for the KMS/HSM to use by including a public key (fingerprint) in the signing request. If we do this, then ideally Tendermint will know in advance the signature type being produced based off of the key type it used to request the signature.

[nnkken]

@jleni
But in current version, there is an option to use secp256k1 by writing secp256k1 private key in priv_validator.json. By doing so, the votes will be signed using secp256k1.
Will this be dropped at launch?

[jleni]

You mean in kms/signatory? Well, there are different providers. According
to the specs, ledger validator support is only for ed25519. Adding
secp256k1 would be easy but it is not supported right now.
If necessary I think it should be raised as soon as possible

On Tue, 18 Sep 2018, 16:19 Wu Chun Chung, [e-mail] wrote:

@jleni https://github.com/jleni
But in current version, there is an option to use secp256k1 by writing
secp256k1 private key in priv_validator.json. By doing so, the votes will
be signed using secp256k1.
Will this be dropped at launch?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/tendermint/tendermint/issues/1622#issuecomment-422411383,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ANEF2DShFO_dyYFtkdFysmy2oP7cj_JSks5ucQDrgaJpZM4ULmbK
.

[xla]

@xla I guess that is part of the "secret connection" right? not part of the SignedVoteReply that will be shared between nodes..

@jleni Not referring to the secret connection but the messages exchanged between tendermint and kms, residing in the privval package: https://github.com/tendermint/tendermint/blob/d419fffe18531317c28c29a292ad7d253f6cafdf/privval/socket.go#L504-L522

[tarcieri]

According to the specs, ledger validator support is only for ed25519. Adding secp256k1 would be easy but it is not supported right now.

The YubiHSM2 provider can also produce secp256k1 signatures (and now does so in full conformance with libsecp256k1's "low S" normalization for signatures and strict DER serialization rules).

However, I believe the plan for launch is Ed25519-only for validators?

[nnkken]

Oh I didn't notice that you are discussing about ledger kms. Please ignore me in this case. Really sorry for interrupting the discussing.

[liamsi]

@xla regarding the error handling: would an error message including an error type (an uint) and a brief description (string) be a proper way to communicate errors between tendermint <-> kms? Sth like this:

//  amino registered type
SignedVoteReply { 
   Vote      vote
   Signature sig 
   Error err
}

Error {
  uint type // error code
  string description // optional description
}

Or are there canonical ways already in practice in tendermint which I'm not aware of?

[xla]

@Liamsi Good direction I think, some enum (or emulation of it) and descriptive text should suffice. The bare minimum to implement control flow based on the returned error code.

[zramsay]

2422 is an issue for adding ## VoteSignBytes to the spec since it's currently missing

[tarcieri]

would an error message including an error type (an uint) and a brief description (string) be a proper way to communicate errors between tendermint <-> kms?

@Liamsi that sounds fine to me, and is pretty much what we already have on the KMS side. Specifically Signatory boils most errors down to a ProviderError with an accompanying string. That string can potentially include some pretty detailed information about what's going wrong with a signing operation.

[liamsi]

The discussion in here was centred all around the Vote message. It is clear that we will change SignBytes to return sth amino encoded for Proposal and Hearbeat, too. I'm wondering if we also need to restructure Proposal, and Hearbeat too, to make them easier to parse? I'm currently drafting an ADR to see if there are any open points and document what we are doing (and why).
@jleni @ebuchman

[liamsi]

I've summarized what we have until here and made some assumptions on the other types (proposal, heartbeat) in this (still very draftish) ADR: https://github.com/tendermint/tendermint/pull/2445

PTAL

[jleni]

@ebuchman Please consider that once this task is complete, we can move forward with the ledger's validator changes. It would be good to consider that too in the v1.0 plan.

[ValarDragon]

Launch is more immediate than 1.0 :), 1.0 will occur after launch

[jleni]

Even more then.. my point is that this is a block issue for the validator app and KMS integration. My suggesting is that those tasks should be scheduled somewhere in the plan too.

[xla]

@jleni Would the merge of #2455 unblock the ledger validator changes? Or is there more to the story here?

[jleni]

The issue #2455 seems links to PR https://github.com/tendermint/tendermint/pull/2459 that seems blocked at the moment.

About that specific PR, I have a comment here: https://github.com/tendermint/tendermint/pull/2459/files#diff-daae143e63f3624e1584b3ab20ad80ebR36

This seems to define a canonical vote as:

type CanonicalVote struct {
    ChainID   string           `json:"@chain_id"`
    Type      string           `json:"@type"`
    BlockID   CanonicalBlockID `json:"block_id"`
    Height    int64            `json:"height"`
    Round     int              `json:"round"`
    Timestamp time.Time        `json:"timestamp"`
    VoteType  byte             `json:"type"`
}

This is very different from the agreed (https://github.com/tendermint/tendermint/issues/1622#issuecomment-422363861)

// vanilla protobuf / amino encoded
message Vote {
    Version       fixed32                      
    Height        sfixed64       
    Round         sfixed32
    VoteType      fixed32
    Timestamp     Timestamp         // << using protobuf definition
    BlockID       BlockID           // << as already defined 
    ChainID       string            // at the end because length could vary a lot
}

Order and fixed size are important and a key element of what was being discussed here.
Am I missing something?

[xla]

@jleni Could you comment on the PR, so we can address it in the context of the changeset?

[xla]

@jleni Is there anything else besides #2459 that should be prioritised to have ledger testing moving?

[ebuchman]

The reason it's different I believe is so we can make the changes one PR at a time:

1. Use binary encoding instead of JSON
2. Fix the ordering and types of fields

[ebuchman]

Closing for #2545. Thanks all!