Bitcoin Forum
November 15, 2018, 05:32:09 AM *
News: Latest Bitcoin Core release: 0.17.0 [Torrent].
 
  Home Help Search Login Register More  
  Show Posts
Pages: [1]
1  Bitcoin / Development & Technical Discussion / Threshold Multisignatures for Bitcoin on: August 28, 2018, 10:25:36 PM
Hey, I've been working on a threshold scheme for multisignatures.  

I wrote this up, and am pasting it here in the hopes someone can help me find problems with it before I try to bug people on bitcoin-dev again with it and before I try to write up an iacr paper or some nonsense like that (I do think it's nonsense these days...).

https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-e7860ab34e7f

This basically re-uses proven cryptosystems like Schnorr and Shamir secret sharing, and takes advantage of the homomorphic properties of shared secrets in a fairly trivial way that I can't find a problem with.  It also uses the MuSig construction, to prevent participants from being able to birthday-attack parameters of the system.   I don't actually think it's necessary, and I will probably remove it unless someone thinks its needed.

An M of N Bitcoin Multisig Scheme

Currently, the leading proposal for a multisignature scheme is an M of M scheme. I would propose a modification of this protocol that provides both aa noninteractive M of M scheme and an interactive but verifiable M of N scheme.

I’m going to assume that G is a DLP-hard group of some kind, and that curve operations are done using elliptic-curve terminology. EI: Points can be added, and the generator is multiplied by a private key to get a public key.

Terminology:

G : the agreed upon group (secp256k1)
M : the number of participants required to sign.
N : the total number of participants. (N≥M)
H : a hash function of some kind. (SHA3)
P: the order of group G

The public parameters “G”, “M” and “N” must be agreed upon by all participants. If not, consensus verification will fail.
M of M Scheme

I’m going to begin with a description of the M of M scheme. Extending it to M of N requires an application of “secret redistribution”, which is well reviewed and proven not to leak information about the underlying secrets. I will provide an explanation of how to use it at the end.

To initiate a multisig scheme, each of the first “M” participants generates a secure random number “x”. Then, each participant “i” publishes their public key, G*xi.

Each party interprets the public keys as shares in a Shamir sharing scheme. Put simply, lagrange coefficients are calculated using Xi = H(G*xi). The coefficients are ordered, based on the sort order of X.

for i1 in sorted(Xis):
    coeff[i1]=1
    for i2 in Xis:
        diff = (i2-i1)%P
        inv = modinv(diff, P)
        val = i2 *inv%P
        coeff[i1]=coeff[i1]*val%P    


These coefficients are used to multiply each point by. The results are summed, and that is the “bitcoin public key” — the key that these participants are signing for.

for share in shares:
    point = coincurve.PublicKey(share.data)
    s = point.multiply(coeff[share.index])
    vals.append(s)

point_sum = coincurve.PublicKey.combine_keys(vals)

So, now we have an M of M public key. Nobody can possibly know the private key, and having M-1 devices gives you zero knowledge of the implied private key “x”. In addition there is no meaningful way share participants can influence the resulting implied key.

We can call this G*x, or “the public key”… in the signing scheme below.

Signing:

The participants in the scheme can now generate Schorr-style multisignatures.

When signing, each participant “i” rolls a random nonce “ki”. Each signing participant computes a “blinding parameter L”. These are akin to those used in the MuSig proposal.

L = H(X1, X2, X3…XM, 1)
X = SUM(H(L1,Xi))  ### i think this may be unnecessary.   M-1 attackers simply cannot influence either k or x in a meaningful way.
R  = G*k
e = H(R, M, X)
si = ki - xi * e

The signature share is (si, e).

It’s clear that a single particpant cannot choose a “weak public key”. In the proposed Shamir’s scheme, the value of M-1 shares has zero impact on the entropy contained in the final result. The same logic applies to the “implied k”. The value of e must be the same for all participants.

Verification:

The signatures must also be subjected to the lagrange coefficients algorithm above.

Each si is combined to a single “S” by multiplying the coeffs (calculated above) and the result is summed:

s = sum(coeff[index] * si)

Finally, you perform the same verification as in Schnorr.

rv = G*s + G*x*e
ev = H(r, M, X1)
assert(ev == e)

The math winds up about the same as well. The only variable the attacker controls at signature time is k. M-1 attackers don’t affect the randomness of k.

Derviation showing this still works.

rv = G*(k - x*e) + G(*x*e)
rv = G*(k) == R

One thing to understand is that after interpolation, the resulting “x” and Gx and “signatures” are combined correctly.

Shamir secrets shares are homomorphic in addition, subtraction, multiplication and addition, so this is something we get “for free”.

It is also why ECDSA can’t be used in a Shamir scheme. The modular inverse function will not work and shares could not be combined.
Addition of Share Participants:

Thus far, this scheme can be done without rounds of approvals. Share participants can generate keys offline and without participation from each other.

In order to create additional participants, they must be added to a larger implied polynomial using “secret redistribution”.

A quick summary of how this is done doesn’t do it justice, but there are lots of implementations and descriptions of secret share redistribution to choose from. For example: https://github.com/dfinity/vss

Summary: Each of M participants “shards” his share into N “sub shares” labeled 1..N, using Shamir’s secret sharing algorithm for an M of N scheme and using random coefficients. These subshares are, further, delivered to each of the corresponding share participants. They are then separately interpolated and combined to form new shares “xi” . Each participant must then publish the new G*xi. Each participant can now verify that the new combined and implied key G*x for all M subsets of N is the same as the original key G*x. ( Failure to verify this implies that one of the participants is functioning incorrectly and cannot sign — not that there is some sort of weakness. )

Redistribution can be used to *remove* participants, *add* them, or otherwise change the M of N scheme without compromising the scheme.

It’s notable that when using “secret redistribution” the addition of share participants does not change the verification algorithm, nor does it expose any information about the secret key or the implied secret key.

Caveats:

Also important to note that this entire article (and multisig schemes in general) assume that there are other mechanisms in place for verifying share participants. Any attacker that controls M of N keys using MITM techniques will be able to sign using any multisig scheme.

Public keys should be shared in-person using QR codes or, at least, using verbal or other verification techniques for keys shared online.

Currently, the leading proposal for a multisignature scheme is an M of M scheme. I would propose a modification of this protocol that provides both aa noninteractive M of M scheme and an interactive but verifiable M of N scheme.

I’m going to assume that G is a DLP-hard group of some kind, and that curve operations are done using elliptic-curve terminology. EI: Points can be added, and the generator is multiplied by a private key to get a public key.

2  Alternate cryptocurrencies / Altcoin Discussion / Solution to Sia/Storj/etc DDOS issues and Sybil Vulnerability on: June 06, 2016, 03:57:01 PM
All cloud storage networks, coin or otherwise, are vulnerable to DDOS attacks, where attackers cause renters or hosts to spend enormous sums of money by repeatedly downloading the same files.

  • The typical solution to these DDOS attacks remains "IP blocking".   For TCP/IP, this can be effective, and when coupled with some sort of tracing back to the source, results in DDOS attacks that wane and can be responded to fairly rapidly.
  • The practice of IP blocking has spawned an open and somewhat contentious network of public and private IP blocklists.   While it is likely that these blocklists will be relevant for storage coins, there will be undoubtedly be a need for blocklists to be maintained that are specific to cloud storage protocols.
  • Blocklists, even if fairly maintained, are centralized and many use DNS for distribution (see https://en.wikipedia.org/wiki/DNSBL).  A blockchain protocol for blacklisting may be ideal, with nominations, evidence, voting and expiration all occurring "on chain".   (It should be obvious why blocklists would greatly benefit from decentralization)

All storage coins are additionally vulnerable to a "not really redundant" Sybil attack. 

  • Any attacker can quite simply spin up many instances of the protocol on a single host - increasing his exposure and income - while completely defeating the purpose of redundant storage.
  • There is currently no way for a renter or user to know where its hosts physically reside, and whether they are on the same machine or not.
  • One way of mitigating this is to publish IP addresses of hosts as a part of file contracts or storage advertisements.   Renters should then prefer IP's that are somewhat distributed across the IP space.   This can, of course be defeated by routing diverse IP's to the same data center.   But this can be trivially detected and violators can then be published via the same IP blocklists above... using either DNSBL or blockchain tech.

In summary:

  • Any time you are "hosting" data, you need to deal with DDOS attacks.
  • However you solve it, I don't care: this solution will, de facto, provide an analogous solution for Sybil attacks on storage network redundancy

So don't worry about Sia/Storj sybil attacks.   They are just inverted DDOS attacks, and those have to be solved anyway.
3  Bitcoin / Development & Technical Discussion / Request for Comments on Audit Protocol on: February 28, 2014, 07:18:18 PM
Although this does not address liabilities, that is not a chief concern.   By implementing an interim standard for publishing reserve balances, we can quickly placate the investor community on the health of major exchanges:

http://www.reddit.com/r/Bitcoin/comments/1z72wz/btce_et_al_should_publish_their_reserve_balance/


LOCATION:
Code:
https://<site>/dcx/balance.json

CONTENT:
Code:
{
"time" : "<RFC 3339 time>",
"nonce" : "<unique nonce>",
"reserve" : [
        { "addr" : "1x.........",
          "sig"  : "<signature of nonce for address>"
        },
        { "addr" : "1b.........",
          "sig"  : "<signature of nonce for address>"
        },
        ....
    ]
}

Obviously this doesn't address:

  • Fiat balances
  • Liabilities

These issues can only be properly addressed with audits, since most exchanges don't use BTC protocol internally.  

However, following an audit, the ratio of average volume to liability can be expected to remain fairly stable, providing a public health metric that will give immediate relieve to the current climate of skepticism.  

4  Bitcoin / Project Development / Bitcoin spend site on: February 11, 2014, 08:36:43 AM
https://bitk.in - Spend bitcoins at Amazon.com.  Unlike other sites, you can put the actual amount of your order at Amazon, so you're not left with change at the end of the transaction.

Let me know what you think.   Also, if you're interested in being an affiliate, or have ideas for integration.   Specifically someone with greasemonkey experience that could write a program that swipes the checkout amount from amazon, pops an overlay, wiats for the gift code response, and stuffs it into the checkout form would be sweet.

5  Bitcoin / Development & Technical Discussion / Standard protocol for Bitcoin/SSL content verification on: January 28, 2014, 07:33:46 PM
As a merchant, I'd like to provide some assurance to my customers that the wallet address I'm signing with is one linked to my domain, in an irrevocable manner.

Currently, the merchant hosts an ssl connection, the customer typically sees a random, sometimes even recycled, address to send to.  

For assurance, the merchant may sign a message with order information : "Order# 4456 Address: 1N57686... Amount: 1.56 BTC", or something like that.  For that signature, the merchant will used a published address, typically one on his home page, or a donation page, and/or one associated with these forums.

This is great!  Because the customer can come along and prove that the merchant signed that message, and prove he sent the BTC to that address, etc.  

But suppose the merchant didn't post that public signing address anywhere? Do customers have to check archive.org first, to ensure the merchant's home page is in the cache with the donation address?   Or worse, bitcoinforums (yes, that's the standard these days).

Who's to say a particular address is associated with a particular site? 

And of course a customer can always create a wallet, stick a url in it, sign it and "swear it was on the merchant's site".

This is all silly, and we can have a standard, and SSL URI's are the right way to go:

a) publish a message at (https://) URL, can contain anything
b) client reads that, stores the results in his wallet
c) client sends a "verify transaction" consisting of a {SHA256(url+contents)} + bounty per verification + # of verifications requested
d) peers can accept the "verify transaction", verify that ssl url contents hash as stated, obtain the bounty, and publishing the signed {SHA256(url+contents)} message in the bitcoin block chain as a transaction from their address along with 50% of the bounty as a transaction fee.

At the end of the day, miners participating in verification get paid for verification services.  Customers can get assurance that verification is irrevocable.

Something like that...not terribly well thought out.  But something.

But here's the thing....I think it really should be built-in to bitcoin.   It could, of course, work as an "other coin".  

If even 10% of the miners upgraded, a customer could pay for URL content verification and get a response within a few minutes.  It won't be on the blockchain in a few minutes, sure.  But it will propagate fast, and block-chain confirmation would only be needed for a lawsuit later... not for a "confirmation now".

(Note: it could be used to "confirm content" of any kind, enabling interesting new uses)
6  Economy / Economics / What if a looser money supply is unquestionably needed in the future? on: December 29, 2013, 06:48:05 AM
I'd like a discussion of the future of monetary policy for Bitcoin.   Currently, bitcoin is capped, difficulties increase in relation to mining speed, and that older miners drop off as new efficient ones come on.  Yay.

For now, many miners are also big stakeholders, so the interest is in growth of stake and restriction of supply.   But the economy of this is changing very rapidly.   Very soon, perhaps only within a few months, miner capital investments will outstrip the perceived future value of their stakes.   

Bitcoin has survived two "changing of the guards" as it moves from cpu to gpu and then to asic.   Miners failing to adopt the new technologies slowly disappeared.   There's some evidence that the new "28nm" miners are already mining (cex.io's ghs price is dropping fast).

However, this raises some endgame concerns.   If mining ever becomes *too* unprofitable, because, say, transaction fees can't cover electricity costs even of those nice cool 28m chips, the pressure will build to add some inflation into bitcoin's protocol.   As technologies ramp up, there will be fewer and fewer entities profitably mining.  This is the consolidation people are concerned about.

Such a scenario is virtually guaranteed at 21mil coins.

If this starts to happen, and we don't add some monetary loosening at that point, the currency will either a) fail as mining fails or b) atrophy until 1 group owns 51%.  Of course, both scenarios are easily fixable by patching the protocol at some point in the future.

Miners control the current rules by which bitcoin is created.  So the set of future upgrades or changes to the core protocol that could happen can be reasonably be limited to "those that would benefit miners".

The phenomenon we have building is of "open source code and forum posts as a central bank", which is pretty cool.  Sure, it's not very central.  And yes, a majority of miners will have to agree to, download, and install a new protocol, so it's somewhat democratic. 

But still.

What are the currently known ways to address problems of long-term mining profitability.   Is the consensus that fees will eventually become profitable?  I've seen some discussion of the removal of upper limits.  Is Proof of Stake XX% Inflation ever discussed as a monetary loosening policy in connection with BitCoin.

I'd be curious to know what ideas people have been floating to address this issue.
7  Alternate cryptocurrencies / Altcoin Discussion / "Google altcoin" as real-world popularity commodity exchange on: December 22, 2013, 12:46:19 PM
There are a number of commodities that cannot be easily traded.   Like the popularity of "game of thrones".  I was thinking of a new kind of multiple-altcoin where the algorithms scarcity is, tied to a publicly available index, rather than to productivity.   

Essentially there would be any number of "X" sub-coins.

- The source of the "Y" would be akin to a /dev/random source of entropy, coded in watered-down Lua, with the code published in the blockchain as a transaction.   Miners would then be able to support "X" as a new sub-coin.

- Execution of the "Y" algorithm generates "entropy" transactions, and these are published as well, with consensus accepted as the new value for Y.  Miners can choose which "X" they mine, and the publishing of consensus "Y" results would be tied to mining.

I haven't really thought it out to the conclusion, but the concept of publishing scripting code in the blockchain - as a general concept - is interesting to me.   As is the concept of allowing people to speculate on things like "the popularity of a tv show".

I suppose you could ditch the Lua and just use Google's popularity search as the "Y" scarcity index.   But I like the idea of making it stupidly flexible.   

Some coins would be trivial to manipulate... like "doge".   Others would be well-designed, and inspire real investment, both by miners and by traders.   

I know there are metacoins out there... but none of them seem to work, and none of them contain script-embedded stuff.
Pages: [1]
Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!