operation to commit to secp256k1 points?

[apoelstra]

Given a commit c, the operation c → P + H(P||c)G is a valid commitment operation, where P is an arbitrary given curvepoint and G is a standard generator for the curve. It does not depend on any properties of the curve except that G have large order (and this is a mathematical fact about crypto groups, not a security assumption), only on the security of the hash function H.

There are unfortunately a lot of variants here -- H can be any second-preimage-resistant hash function, the curve can be any elliptic curve or even a non-EC group, etc. But the parameters secp256k1, SHA256, would allow opentimestamps to support pay-to-contract and sign-to-contract on Bitcoin (and Ethereum, and grin).

This would require any OT library to support elliptic curve math, but they don't have to do a good job of it, only a correct job. Sidechannel resistance for example is unnecessary.

[petertodd]

What's the proposed use-case for pay-to-contract?

I'm pretty skeptical about adding extra dependencies without a compelling reason; just saving a few bytes isn't enough given how efficient OpenTimestamps is already.

[apoelstra]

In addition to the space savings and uncensorability (which I agree, OT already does a very good job on both),

• Letting OT work with Mimblewimble
• I'd like to write a wallet which uses sign-to-contract to commit to its state whenever it sends a transaction, and it would be nice to have a standard format for these commitments that would let me reuse them to timestamp other stuff.

[petertodd]

Keep in mind that OT is already uncensorable against anything less than full-on whitelists, as it doesn't need to use OP_RETURN.

Frankly, I don't care about Mimblewimble until it catches on. :)

That said, I think it would be reasonable to have an extended version of the OpenTimestamps standard with all the non-core features that only a subset of clients might want to use. For example, the standard limits the size of opcode results to 4KiB for the sake of stack-only embedded implementations without a heap; 99.99% of the time that limitation isn't an issue, but for the rare cases where it is, it'd be reasonable to process timestamps with that limit removed.

Remember that we've already got four different OpenTimestamps protocol (five if you include a unreleased Go version that I'm aware of) so I want to avoid creating unnecessary work for implementors of the core standard without solid reasons.

Speaking of, a closely related issue is that I'd like to define ways of making unknown opcodes backwards compatible with implementations that don't support them. For example, if your implementation is Bitcoin-only, and you're giving a BTC+ETH timestamp, it should be possible to ignore the Ethereum-specific Keccak opcodes and ETH attestation and still succesfully validate the BTC attestation.

I'm thinking it should be sufficient to set aside a block of opcodes that have an assumed serialization (e.g. 1byte) and in non-supporting clients are treated as "unknown" results that can't be verified, but can still be deserialized succesfully. This is similar to how attestations from unknown notaries are serialized in a backwards-compatible way. The main question there is simply do we ever need opcodes that are serialized with something other than 1 byte?

[apoelstra]

I'm not sure what you mean by 1 byte. Do you mean, do we ever need non-unary opcodes?

[petertodd]

First of all, append and prepend are both binary opcodes.

Secondly, attestations are effectively non-unary opcodes too! Note how the attestations could have been implemented is to build the arguments to the attestation on the stack, and then call a unary opcode that parsed those arguments. Instead, an attestation is parsed with one big argument, that in turn is parsed by the notary-specific validation code.

An example where this distinction matters is if you want to timestamp an attestation: suppose we have a trusted notary scheme, where timestamps are simply signed with a 32-byte ECC signature. Now suppose we want to be able to verify trusted timestamps created prior to a key compromise, known to have happened at time t.

If we can verify a timestamp on that signature from a second notary - like the Bitcoin blockchain - we can verify that the signature was created prior to the compromise, and we're good to go.

The trick is, how do we support this? In the current architecture there's no natural way to represent a timestamp on the body of an attestation; the attestation's arguments are effectively a leaf node in the tree and thus no opcodes can act on that data.

In the signature case, a natural representation might be for the attestation itself to have no arguments (or just the pubkey) and get the signature from the parent opcode's result. Then if you want to timestamp that signature, just add whatever extra opcodes are needed to timestamp that result.

Concretely, it'd look something like this:

<digest we want to timestamp>
append <foo>
sha256
{etc etc.}
append <signature>
  -> verify SignedAttestation(<trusted pubkey>)
  -> {various opcodes}
    verify BitcoinBlockHeaderAttestation(<block #>)

In the case of the block header attestation, because the attestation acts on the merkle root rather than the block hash if you wanted to have verification logic that required a second timestamp on the blockheader you'd have to specify a specific sequence of one append and one prepend to fill in the missing parts of the header. I'll have to think a bit more if that's too magical or not.

In both the SignedAttestation and BitcoinBlockHeaderAttestation we have attestation arguments that aren't hashed: both the SignedAttestation pubkey is and BitcoinBlockHeaderAttestation block # are just helpful hints to help the verifier; in either case the verify could still verify the attestation without them in theory by brute-force checking all the possible pubkeys or block #'s. You certainly would never care whether or not a block # had been timestamped; I'm more like 95% sure that true for pubkeys.

The thing is, imagine a case where we have a big certificate chain from the pubkey: we might have multiple binding signatures in the chain, with the timestamp only valid if timestamps existed for each of those binding signatures. Since those binding signatures timestamps would have all been created prior to the digest the timestamp itself is timestamping, I think it makes sense to store the binding signatures and timestamps within the SignedAttestation.

If we do that, then the SignedAttestation's so-called "pubkey" would actually be some complex certificate chain thing; fortunately, I think that's out of the scope of this discussion and from the point of view of the rest of the commitment operations tree it's just irrelevant metadata. Again, in theory you could bruteforce that certificate chain, provided you could find a computer made out of something other than matter, occupying something other than space... :)

Finally, one more example of a non-unary opcode is specialized tree-hashing modes. For example, in a log file I might want to hash the file as a big merkle tree (MMR list) with the leaves being each individual line to let me extract timestamps for specific lines or ranges of lines without revealing other lines. The git tree re-hashing support is a similar - already implemented - example.

However, in this case the special mode would only be used as the initial step in the timestamping process, so I'm not sure it's relevant to the commitment operation tree - in most cases you can turn what the special mode is doing into a series of standard commitment operations.

[petertodd]

So thinking about this more, I think we have a good argument for doing this: we'd be able to allow anyone to help timestamp the calendar merkle tips at zero marginal cost. Currently we're far from getting a timestamp in every block, and the above would get us there.

Lets talk more in Milan!

[apoelstra]

Per our in-person conversation earlier:

I misunderstood what you meant by "assumed 1 byte serialization" -- I thought you were suggesting that there be no binary opcodes, since these naturally have an argument that would take more than one byte to encode. And the subject of this issue -- EC-commitment operation -- would be binary!

What you said earlier, if I understand right, was that we could have a block of "future unary opcodes" and a separate block of "future binary opcodes", each identified by a 1-byte tag.

[mcelrath]

Hey guys, what's the status of this feature? It was my understanding that @petertodd was in agreement and this was going to be implemented. But I look on the opentimestamps-server and I see it's still using OP_RETURN and there don't appear to be any issues/PR's related to switching to using @apoelstra's commitment proposal.

Did this one die on the vine or just lacking an implementor?

[petertodd]

@mcelrath It's still on the todo list, it's just that I've had more pressing issues to deal with first.

Also, note that due to how segwit's commitment is designed, using this feature in conjunction with segwit greatly increases the size of timestamp proofs.

[mcelrath]

@petertodd Darn.

I'm lobbying to set up opentimestamps at my new employer. Can you elaborate on the segwit difficulty? I might be able to do the implementation myself...

[apoelstra]

The segwit difficulty is that sign-to-contract puts a commitment into witness data, which has its own Merkle tree which is committed to in the coinbase transaction of the transaction tree, so you wind up needing to traverse through both trees to get to the blockheader commitment.

[mcelrath]

Revisiting this... so the .ots file is larger because it has to traverse two trees in case of segwit. I don't see this as a fundamental problem, unless we're worried about nodes pruning witness data, or SPV verification of timestamps.

[apoelstra]

Right, it's purely an efficiency problem.

[petertodd]

No, it's not purely an efficiency problem, as there's a maximum message size limit of 4096 bytes. This would be hit by blocks containing >4096byte coinbase transactions, making a segwit-using signature impossible to make into a valid timestamp.

That said, most blocks have small coinbases, so this will usually not be a problem.

[petertodd]

Re: noes pruning witness data and SPV, none of that should be an issue as a BitcoinAttestation verifies the block header, and nothing else; OTS deliberately omits support for creating an attestation based on a transaction or similar thing precisely due to this issue.