search

stacks-network / stacks-core

The Stacks blockchain implementation
https://docs.stacks.co
GNU General Public License v3.0
3k stars 660 forks source link

Schnorr Signature Support On-chain #3568

Open BowTiedDeployer opened 1 year ago

BowTiedDeployer commented 1 year ago

Is your feature request related to a problem? Please describe. We are building the Decentralized Mining Pool which will use FROST in the process of signing the transactions for funding the PoX address and committing the blocks. The mining pool stores the information such as the participants and their activity on-chain using Clarity on the Stacks side while sending the BTC on the Bitcoin blockchain. It would be very helpful to be able to verify the Schnorr signature on the Smart Contract on Clarity.

Describe the solution you'd like A Clarity built-in function that will support Schnorr signatures and facilitate the verification on-chain.

jcnelson commented 1 year ago

Hey folks, we probably won't get to this until the next hard fork (which adds sBTC).

igorsyl commented 1 year ago

I suggested to the Degens team over a call to implement the Schnorr verification algorithm using Clarity primitives before the next hard fork. @xoloki and @MarvinJanssen may be interested.

xoloki commented 1 year ago

I've been thinking about this for a while. Is there a link to the crypto primitives available in Clarity? I know there's an ecdsa sign/verify, but is there something that takes a private key and makes a public key from it?

igorsyl commented 1 year ago

Wait, is this a Schnorr verify function?

https://github.com/stacks-network/stacks-blockchain/blob/a71871a5b18daf04259a71512d6e18752c0b1e20/clarity/src/vm/functions/mod.rs#L116

jcnelson commented 1 year ago

I've been thinking about this for a while. Is there a link to the crypto primitives available in Clarity? I know there's an ecdsa sign/verify, but is there something that takes a private key and makes a public key from it?

No, unfortunately. The list of crypto primitives (including hash functions) are:

In all likelihood, such a function would need to implement the curve math directly using the existing Clarity keywords.

Insofar as runtime costs, such a function would certainly be expensive. However, it is possible via SIP-006 for the network to vote on what the total runtime cost of the function ought to be, without doing a hard fork. This feature enables the following development flow:

  1. write a necessary but potentially expensive Clarity function, such as this one
  2. release a modified Stacks node binary that intercepts contract-call?s to this function and runs the equivalent code in Rust
  3. use SIP-006 to vote on a new cost function for the Clarity function that more closely matches the runtime characteristics of the Rust implementation
xoloki commented 1 year ago

I've been thinking about this for a while. Is there a link to the crypto primitives available in Clarity? I know there's an ecdsa sign/verify, but is there something that takes a private key and makes a public key from it?

No, unfortunately. The list of crypto primitives (including hash functions) are:

  • hash160 (this is a Bitcoin-ism meaning "find the RIPEMD160 hash of the SHA256 hash of the input string")
  • sha256
  • sha512
  • sha512/256 (sha512 truncated to 256 bits)
  • keccak256
  • secp256k1-recover?
  • secp256k1-verify?
  • principal-of (gets the STX address of a compressed secp256k1 public key)

In all likelihood, such a function would need to implement the curve math directly using the existing Clarity keywords.

Insofar as runtime costs, such a function would certainly be expensive. However, it is possible via SIP-006 for the network to vote on what the total runtime cost of the function ought to be, without doing a hard fork. This feature enables the following development flow:

  1. write a necessary but potentially expensive Clarity function, such as this one
  2. release a modified Stacks node binary that intercepts contract-call?s to this function and runs the equivalent code in Rust
  3. use SIP-006 to vote on a new cost function for the Clarity function that more closely matches the runtime characteristics of the Rust implementation

This seems like a good option until the hard fork.

Could I take it one step further, and stub out the clarity impl, such that it refuses to run? Then it would only work for modified nodes which intercept the contract call

jcnelson commented 1 year ago

Could I take it one step further, and stub out the clarity impl, such that it refuses to run?

Unfortunately, this isn't an option. Each Stacks node with the same major and minor version numbers (2.0, 2.05, 2.1) must evaluate a given Clarity function call the exact same way. Failure to do this will lead to a chain split, whereby nodes with the modification to evaluate the schnorr signature verification logic process a transaction that calls it differently than nodes without the modification. This would in turn cause these two sets of nodes to evaluate the same block differently, leading to a divergence in their respective states.

fpbgg commented 1 year ago

Just to ensure the requirements are clear, this is what you're looking for, right?

New Clarity Function

secp256k1-schnorr-verify?

Inputs

Output

bool - Is the signature valid?

Algorithm details

This function would need to validate the Schnorr signature algorithm rather than ECDSA, over the secp256k1 group.

Acceptance Criteria

Given @jcnelson's comment above, I don't think a sign function would be appropriate here, as it would expose the secret key to all nodes.

igorsyl commented 1 year ago

Verify is all that's needed.

jcnelson commented 1 year ago

bool - Is the signature valid?

Output should be (response bool _), since the inputs can be invalid. The err type can be whatever you think is appropriate. Conventionally, we use int.

xoloki commented 1 year ago

@fpbgg exactly. Signing takes place in a distributed protocol, but we want the contract to be able to verify the signature before trying to write out a BTC TXO.

igorsyl commented 1 year ago

The proposed idea of Clarity-only function could go into a crypto Clarity lib instead of into stacks-blockchain. say, p256k1-cl? This issue should be reserved for the Rust impl and new issue in whichever repo for the Clarity impl.

jcnelson commented 1 year ago

Fine by me, but where should this issue live?

igorsyl commented 1 year ago

I propose here https://github.com/Trust-Machines/core-eng/issues/83 We can wrap up and spin out into a separate repo once stable. It would be great if clarinet provided "Clarity crates" then this could be the first crypto crate. cc @lgalabru