Bitcoin Forum
September 21, 2018, 03:22:07 AM *
News: ♦♦ New info! Bitcoin Core users absolutely must upgrade to previously-announced 0.16.3 [Torrent]. All Bitcoin users should temporarily trust confirmations slightly less. More info.
 
  Home Help Search Donate Login Register  
  Show Posts
Pages: [1] 2 3 »
1  Bitcoin / Development & Technical Discussion / Re: Threshold Multisignatures for Bitcoin on: September 11, 2018, 05:42:41 PM
Thanks.

1. The senders of the G*xi shares should sign the messages using xi private key.   Recipients can verify these and this should be sufficient to prevent a rogue key attacker from controlling x

2. The sender of the G*ki nonces should sign the messages using an "xi*ki" private key.  Recipients can verify these and this should be sufficient to prevent a rogue key attacker from controlling k

I updated this with the signing requirements:

https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-e7860ab34e7f
2  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.

3  Bitcoin / Pools / Re: [∞ YH] solo.ckpool.org 1% fee solo segwit mining USA/DE 232 blocks solved! on: July 18, 2017, 02:20:03 PM
Just to clarify, this and the shared pool are compatible with the upcoming segwit component of the New York Agreement AKA segwit2x soft fork and any blocks we find will be valid and accepted.

Can ck signal bit 1 and bit 4 both?
4  Bitcoin / Development & Technical Discussion / Re: Running on a port other than 8333 on: March 25, 2017, 01:48:35 AM
yeah, it's more like... if it's a nonstandard port, mark it as such, and connect much less frequently....ie: only one nonstandard port connection per day... with a doubling backoffs on failure, and random time to attempt.   this would allow nonstandard ports to exist.   any web server can handle an extra 10k requests evenly spread out through the day, so no risk of ddos.   if this seems to work, and it's useful, and it doesn't turn into a mosh pit on testnet, the levels can be slowly raised to 10 nonstandard peers per day, or whatever.
5  Bitcoin / Bitcoin Discussion / Re: Does SegWit even increase the block size? on: March 06, 2017, 06:11:12 PM
Yes, it does.   4MB, but 2.1 "effective" increase based on current traffic patterns.   

We need this block size increase today, because fees are going to become a big barrier preventing adoption as bitcoin price is bloated by institutional involvement in the coming year.

Also, since there's no way we can record every person's coffee and pizza purchases in the whole world in a single block chain, Bitcoin is going to need chained unconfirmed transactions ASAP as well.   

Segwit fixes both of these problems fairly quickly.   There's a cool compression algo coming out that can also triple the rate without bloating the chain at a loss of anonymity... but I wouldn't relay on that vaporware.  Segwit is real and is the only tested solution to date.   (( Bitcoin Classic was probably OK too.. (simple 2MB fork), but it never got off the ground. ))

6  Bitcoin / Bitcoin Discussion / Re: 95% lol. No chance. SegWit is now dead. on: January 16, 2017, 04:51:41 AM
Blocks are full

What does that even mean?   That's the crazy thing people keep saying.   Ant pool still mines empty blocks every day.   How are they "full"?   Some time in January 2015, zero and 1 satoshi fee transactions started backing up the mem pool.   


If you want to get to $0.01 fees and $5000 coins, you'd need fast and efficient 100MB blocks that can be easily and quickly transmitted to all nodes in the network.   100MB is crazy and can never work.   Networks just don't scale that way.   So let's please stop fooling ourselves and pretend off-chain scaling *isn't* the end game here.

I ran a survey over at reddit.   What percent of Bitcoin transactions are "off chain".   Predictably, big blockers say ZERO.  Because everything else is credit.   Which is true... but that doesn't mean that poor people need cheap ways of moving gold internationally for pennies.
7  Bitcoin / Bitcoin Discussion / Re: 95% lol. No chance. SegWit is now dead. on: January 16, 2017, 04:41:19 AM
So what actually happens now? Will the miners go for Bitcoin Classic or Unlimited, or does the bickering continue without being resolved for another year?

... it should have been a node consensus first, pool consensus second strategy.

There's like 4000 nodes running core, and 3000 of them are signaling segwit.   There are about 400 nodes signaling "other things" ... (XT, Classic, BU, etc.).   It's as clear as day on the node side.   Only miners hoping they can delay the fee drop and capacity increase a little longer.
8  Other / Bitcoin Wiki / Re: Request edit privileges here on: September 14, 2016, 12:49:23 PM
Username: Simul

Thx
9  Bitcoin / Development & Technical Discussion / Re: Scaling Bitcoin with Subchains on: July 08, 2016, 08:29:42 PM
In a way, this is like the dotted-quad notation of IPv4, where each "level" of subchains is another dotted quad.   It might be more convenient to use 16 (0-9A-F) as the number of subchains per level.   

I would add that the difficulty of subchains should be vetted in the main chain, so that someone can choose an address that targets a level of difficulty they are comfortable with.   

It seems that subchains can safely be weaker than the main chain, because of the vetting done by the main chain, which acts, effectively, as a series of checkpoints.

Also, some addresses should be reserved for future use.   For example, an alternate hashing scheme could be added to address position 11 in a future where this is seen as desirable.  Again, since this is synched with the main chain, it benefits a great deal from the security the main chain provides, with the possiblity of a long-fork mitigated.   


0 - 10 full block subchains
11 - 15 reserved for future use

10  Alternate cryptocurrencies / Altcoin Discussion / Re: Solution to Sia/Storj/etc DDOS issues and Sybil Vulnerability on: June 08, 2016, 03:31:20 PM
you need to know all of the hosts that have that file (not always public knowledge)

You merely need to download the file over and over... which causes the renter to run out of money.   Same as a DOS attack downloading a web page.

forcing attackers to spend significant monetary resources executing an attack.

Attackers always spend the same money that legitimate hosts spend.   The "attacker" here is running completely legitimate, full copies of the protocol.   The only difference is that they are running multiple docker containers on the same machine... rather than running on multiple machines.   There is simply no way to know that outside of IP.   Just like a DOS attacker runs a fully legitimate client, so too a Sybil attacker runs a legitimate server.

The really nice thing about both DDOS and Sybil attack prevention is that it's not a consensus layer problem.

I think that succinctly sums up what I meant in the original post.

Since DDOS and Sybil are inverted forms of similar attacks (multiple clients vs multiple hosts), these decentralized storage networks haven't introduced a "new" problem to the domain of hosting.  Indeed, any existing cloud hosting provider could, today, "claim redundancy" on your data... but physically locate it on the same machine.   The solution to this problem lies in the transport and social layers... not the consensus protocol.
11  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.
12  Alternate cryptocurrencies / Marketplace (Altcoins) / Re: Lisk Marketplace (Buy/Sell) and Speculation Thread on: April 01, 2016, 05:25:10 PM
Will sell 20k at .0003  I know it's a low price, but I need the cash now.  PM me.
13  Alternate cryptocurrencies / Altcoin Discussion / Re: Why Proof of Burn cannot work cleanly in practice on: March 07, 2016, 07:15:05 PM
You have to burn within the last 50 blocks, you cannot burn more recently than the last 10 blocks.   This effectively implements a "checkpoint".   Change the numbers of blocks as needed so that you're talking about days and hours.
14  Economy / Service Discussion / Re: [FUD] btc-e is also running fractional reserve on: June 05, 2014, 08:22:23 PM
Until a bitcoin exchange/business passes an audit by an outside/independent body (and continues to do so at regular intervals), why should

You don't need an audit.   This is Bitcoin, you can publish a signed ledger and tree of debits showing your holdings in BTC, LTC, etc.   

The fact that they are not doing so, despite being repeatedly asked, is very telling.

I pulled all my money out of btc-e, shortly after they refused to respond to the new protocols allowing the signed publishing of reserves and debts.

http://www.reddit.com/r/Bitcoin/comments/1yk4nv/please_ask_your_favorite_exchange_to_prove_that/
15  Alternate cryptocurrencies / Altcoin Discussion / Re: Hullcoin: The World’s First Local Government Cryptocurrency on: April 07, 2014, 02:17:34 PM
So all power to the elected representatives of Hull - they're trying to achieve something bitcoin hasn't managed yet.

+1 Spot on.
16  Alternate cryptocurrencies / Altcoin Discussion / Re: [ANN][WDC] Worldcoin Mining Pool www.multipool.in on: March 06, 2014, 04:00:29 PM
Does the pool keep mining fees, or are they distributed along with the block reward?   (I know it's not really important now, maybe .5%, but it will be over the next 6 months).

Do you plan to publish the blocks you mined, and the distribution transactions?
17  Bitcoin / Development & Technical Discussion / Re: Request for Comments on Audit Protocol on: February 28, 2014, 09:43:05 PM
good idea. much more should be done in this area. however there are several very hard problems though. proof of balance is not worth very much if an attacker can remove all coins in minutes. so if 500M$ evaporate without noticing, there is the question how to create accounts which are more secure by default. could one create an address which has different features? an address which is sealed so that only a certain percentage can be withdrawn? a multi-signature address? everything depends on the security mechanism.

I agree.  If someone's storing all their reserves on one machine, in one wallet, with one password... well, then you've got a problem.  And there's very little they can do to prove they aren't doing that.

But right now, a temporary measure is needed.   

We need to know that these large exchanges aren't running fractional reserves.   Mt. Gox insisted, repeatedly, that 90% of its assets were in cold storage.   But it never published keys and sigs.   And so we find out now that maybe they were making that all up.   People asked for keys and sigs to prove it... but they "demurred" on those requests...because "nobody else" was doing it.

If the Bitcoin Foundation came out with a "BIP" for this... even a simple thing like a standard JSON format and a requirement for SSL, that would be enough for the community to say... hey... there's a standard... why don't you adhere to it.

IMO, the first exchange to go transparent on reserves will see a flood of new business.
18  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.  

19  Bitcoin / Press / Re: [2014-01-12] OVERSTOCK CEO: Amazon Will Be Forced To Start Accepting Bitcoin on: February 15, 2014, 11:43:50 AM
You can buy stuff at Amazon with btc using https://bitk.in
20  Bitcoin / Bitcoin Discussion / Re: [FAKE] Amazon to start accepting bitcoin on: February 15, 2014, 11:41:52 AM
You can buy stuff on amazon through btczone. That service has been up a long time now.

Or you can go to bitk.in and shop amazon.  Best conversion rates.
Pages: [1] 2 3 »
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!