126 changes: 126 additions & 0 deletions core/src/main/java/org/bitcoinj/utils/VersionTally.java
View file
@@ -0,0 +1,126 @@
/*
* Copyright 2015 Ross Nicoll.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/

package org.bitcoinj.utils;

import java.util.Stack;
import org.bitcoinj.core.NetworkParameters;
import org.bitcoinj.core.StoredBlock;
import org.bitcoinj.store.BlockStore;
import org.bitcoinj.store.BlockStoreException;

/**
* Caching counter for the block versions within a moving window. This class
* is NOT thread safe (as if two threads are trying to use it concurrently,
* there's risk of getting versions out of sequence).
*
* @see org.bitcoinj.core.NetworkParameters#getMajorityWindow()
* @see org.bitcoinj.core.NetworkParameters#getMajorityEnforceBlockUpgrade()
* @see org.bitcoinj.core.NetworkParameters#getMajorityRejectBlockOutdated()
*/
public class VersionTally {
/**
* Cache of version numbers.
*/
private final long[] versionWindow;

/**
* Offset within the version window at which the next version will be
* written.
*/
private int versionWriteHead = 0;

/**
* Number of versions written into the tally. Until this matches the length
* of the version window, we do not have sufficient data to return values.
*/
private int versionsStored = 0;

public VersionTally(final NetworkParameters params) {
versionWindow = new long[params.getMajorityWindow()];
}

/**
* Add a new block version to the tally, and return the count for that version
* within the window.
*
* @param version the block version to add.
*/
public void add(final long version) {
versionWindow[versionWriteHead++] = version;
if (versionWriteHead == versionWindow.length) {
versionWriteHead = 0;
}
versionsStored++;
}

/**
* Get the count for a block version within the window.
*
* @param version the block version to query.
* @return the count for the block version, or null if the window is not yet
* full.
*/
public Integer getCount(final long version) {
if (versionsStored < versionWindow.length) {
return null;
}
int count = 0;
for (int versionIdx = 0; versionIdx < versionWindow.length; versionIdx++) {
if (versionWindow[versionIdx] == version) {
count++;
}
}

return count;
}

/**
* Initialize the version tally from the block store. Note this does not
* search backwards past the start of the block store, so if starting from
* a checkpoint this may not fill the window.
*
* @param blockStore block store to load blocks from.
* @param chainHead current chain tip.
*/
public void initialize(final BlockStore blockStore, final StoredBlock chainHead)
throws BlockStoreException {
StoredBlock versionBlock = chainHead;
final Stack<Long> versions = new Stack<Long>();

// We don't know how many blocks back we can go, so load what we can first
versions.push(versionBlock.getHeader().getVersion());
for (int headOffset = 0; headOffset < versionWindow.length; headOffset++) {
versionBlock = versionBlock.getPrev(blockStore);
if (null == versionBlock) {
break;
}
versions.push(versionBlock.getHeader().getVersion());
}

// Replay the versions into the tally
while (!versions.isEmpty()) {
add(versions.pop());
}
}

/**
* Get the size of the version window.
*/
public int size() {
return versionWindow.length;
}
}
54 changes: 48 additions & 6 deletions core/src/test/java/org/bitcoinj/core/BlockChainTest.java
View file
Expand Up @@ -26,8 +26,10 @@
import org.bitcoinj.testing.FakeTxBuilder;
import org.bitcoinj.utils.BriefLogFormatter;
import com.google.common.util.concurrent.ListenableFuture;
import org.junit.rules.ExpectedException;
import org.junit.After;
import org.junit.Before;
import org.junit.Rule;
import org.junit.Test;

import java.math.BigInteger;
Expand All @@ -43,6 +45,9 @@
// Handling of chain splits/reorgs are in ChainSplitTests.

public class BlockChainTest {
@Rule
public ExpectedException thrown = ExpectedException.none();

private BlockChain testNetChain;

private Wallet wallet;
Expand Down Expand Up @@ -157,21 +162,21 @@ public void difficultyTransitions() throws Exception {
Block prev = unitTestParams.getGenesisBlock();
Utils.setMockClock(System.currentTimeMillis()/1000);
for (int i = 0; i < unitTestParams.getInterval() - 1; i++) {
Block newBlock = prev.createNextBlock(coinbaseTo, Utils.currentTimeSeconds());
Block newBlock = prev.createNextBlock(coinbaseTo, 1, Utils.currentTimeSeconds());
assertTrue(chain.add(newBlock));
prev = newBlock;
// The fake chain should seem to be "fast" for the purposes of difficulty calculations.
Utils.rollMockClock(2);
}
// Now add another block that has no difficulty adjustment, it should be rejected.
try {
chain.add(prev.createNextBlock(coinbaseTo, Utils.currentTimeSeconds()));
chain.add(prev.createNextBlock(coinbaseTo, 1, Utils.currentTimeSeconds()));
fail();
} catch (VerificationException e) {
}
// Create a new block with the right difficulty target given our blistering speed relative to the huge amount
// of time it's supposed to take (set in the unit test network parameters).
Block b = prev.createNextBlock(coinbaseTo, Utils.currentTimeSeconds());
Block b = prev.createNextBlock(coinbaseTo, 1, Utils.currentTimeSeconds());
b.setDifficultyTarget(0x201fFFFFL);
b.solve();
assertTrue(chain.add(b));
Expand All @@ -183,7 +188,7 @@ public void badDifficulty() throws Exception {
assertTrue(testNetChain.add(getBlock1()));
Block b2 = getBlock2();
assertTrue(testNetChain.add(b2));
Block bad = new Block(testNet);
Block bad = new Block(testNet, Block.BLOCK_VERSION_GENESIS);
// Merkle root can be anything here, doesn't matter.
bad.setMerkleRoot(Sha256Hash.wrap("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
// Nonce was just some number that made the hash < difficulty limit set below, it can be anything.
Expand Down Expand Up @@ -218,6 +223,43 @@ public void badDifficulty() throws Exception {
// TODO: Test difficulty change is not out of range when a transition period becomes valid.
}

/**
* Test that version 2 blocks are rejected once version 3 blocks are a super
* majority.
*/
@Test
public void badBip66Version() throws Exception {
final BlockStore versionBlockStore = new MemoryBlockStore(unitTestParams);
final BlockChain versionChain = new BlockChain(unitTestParams, versionBlockStore);

// Build a historical chain of version 3 blocks
long timeSeconds = 1231006505;
int blockCount = 0;
FakeTxBuilder.BlockPair chainHead = null;

// Put in just enough v2 blocks to be a minority
for (blockCount = 0; blockCount < (unitTestParams.getMajorityWindow() - unitTestParams.getMajorityRejectBlockOutdated()); blockCount++) {
chainHead = FakeTxBuilder.createFakeBlock(versionBlockStore, Block.BLOCK_VERSION_BIP34, timeSeconds);
versionChain.add(chainHead.block);
timeSeconds += 60;
}
// Fill the rest of the window with v3 blocks
for (; blockCount < unitTestParams.getMajorityWindow(); blockCount++) {
chainHead = FakeTxBuilder.createFakeBlock(versionBlockStore, Block.BLOCK_VERSION_BIP66, timeSeconds);
versionChain.add(chainHead.block);
timeSeconds += 60;
}

chainHead = FakeTxBuilder.createFakeBlock(versionBlockStore, Block.BLOCK_VERSION_BIP34, timeSeconds);
// Trying to add a new v2 block should result in rejection
thrown.expect(VerificationException.BlockVersionOutOfDate.class);
try {
versionChain.add(chainHead.block);
} catch(final VerificationException ex) {
throw (Exception) ex.getCause();
}
}

@Test
public void duplicates() throws Exception {
// Adding a block twice should not have any effect, in particular it should not send the block to the wallet.
Expand Down Expand Up @@ -343,7 +385,7 @@ public void coinbaseTransactionAvailability() throws Exception {

// Some blocks from the test net.
private static Block getBlock2() throws Exception {
Block b2 = new Block(testNet);
Block b2 = new Block(testNet, Block.BLOCK_VERSION_GENESIS);
b2.setMerkleRoot(Sha256Hash.wrap("addc858a17e21e68350f968ccd384d6439b64aafa6c193c8b9dd66320470838b"));
b2.setNonce(2642058077L);
b2.setTime(1296734343L);
Expand All @@ -354,7 +396,7 @@ private static Block getBlock2() throws Exception {
}

private static Block getBlock1() throws Exception {
Block b1 = new Block(testNet);
Block b1 = new Block(testNet, Block.BLOCK_VERSION_GENESIS);
b1.setMerkleRoot(Sha256Hash.wrap("0e8e58ecdacaa7b3c6304a35ae4ffff964816d2b80b62b58558866ce4e648c10"));
b1.setNonce(236038445);
b1.setTime(1296734340);
Expand Down
6 changes: 3 additions & 3 deletions core/src/test/java/org/bitcoinj/core/FullBlockTestGenerator.java
View file
Expand Up @@ -890,7 +890,7 @@ public boolean add(Rule element) {
TransactionOutPointWithValue out14 = spendableOutputs.poll();

// A valid block created exactly like b44 to make sure the creation itself works
Block b44 = new Block(params);
Block b44 = new Block(params, Block.BLOCK_VERSION_GENESIS);
byte[] outScriptBytes = ScriptBuilder.createOutputScript(ECKey.fromPublicOnly(coinbaseOutKeyPubKey)).getProgram();
{
b44.setDifficultyTarget(b43.block.getDifficultyTarget());
Expand All @@ -914,7 +914,7 @@ public boolean add(Rule element) {
TransactionOutPointWithValue out15 = spendableOutputs.poll();

// A block with a non-coinbase as the first tx
Block b45 = new Block(params);
Block b45 = new Block(params, Block.BLOCK_VERSION_GENESIS);
{
b45.setDifficultyTarget(b44.getDifficultyTarget());
//b45.addCoinbaseTransaction(pubKey, coinbaseValue);
Expand All @@ -940,7 +940,7 @@ public boolean add(Rule element) {
blocks.add(new BlockAndValidity(b45, false, true, b44.getHash(), chainHeadHeight + 15, "b45"));

// A block with no txn
Block b46 = new Block(params);
Block b46 = new Block(params, Block.BLOCK_VERSION_GENESIS);
{
b46.transactions = new ArrayList<Transaction>();
b46.setDifficultyTarget(b44.getDifficultyTarget());
Expand Down
107 changes: 107 additions & 0 deletions core/src/test/java/org/bitcoinj/utils/VersionTallyTest.java
View file
@@ -0,0 +1,107 @@
/*
* Copyright 2015 Ross Nicoll.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/

package org.bitcoinj.utils;

import org.bitcoinj.core.BlockChain;
import org.bitcoinj.core.Context;
import org.bitcoinj.core.NetworkParameters;
import org.bitcoinj.core.StoredBlock;
import org.bitcoinj.params.UnitTestParams;
import org.bitcoinj.store.BlockStore;
import org.bitcoinj.store.BlockStoreException;
import org.bitcoinj.store.MemoryBlockStore;
import org.bitcoinj.testing.FakeTxBuilder;
import org.junit.Test;
import static org.junit.Assert.*;
import org.junit.Before;

public class VersionTallyTest {
private NetworkParameters unitTestParams;

public VersionTallyTest() {
}

@Before
public void setUp() throws Exception {
BriefLogFormatter.initVerbose();

unitTestParams = UnitTestParams.get();
Context context = new Context(unitTestParams);
}

/**
* Verify that the version tally returns null until it collects enough data.
*/
@Test
public void testNullWhileEmpty() {
VersionTally instance = new VersionTally(unitTestParams);
for (int i = 0; i < unitTestParams.getMajorityWindow(); i++) {
assertNull(instance.getCount(1));
instance.add(1);
}
assertEquals(unitTestParams.getMajorityWindow(), instance.getCount(1).intValue());
}

/**
* Verify that the size of the version tally matches the network parameters.
*/
@Test
public void testSize() {
VersionTally instance = new VersionTally(unitTestParams);
assertEquals(unitTestParams.getMajorityWindow(), instance.size());
}

/**
* Verify that version count and substitution works correctly.
*/
@Test
public void testVersionCounts() {
VersionTally instance = new VersionTally(unitTestParams);

// Fill the tally with 1s
for (int i = 0; i < unitTestParams.getMajorityWindow(); i++) {
assertNull(instance.getCount(1));
instance.add(1);
}
assertEquals(unitTestParams.getMajorityWindow(), instance.getCount(1).intValue());

for (int i = 0; i < unitTestParams.getMajorityWindow(); i++) {
assertEquals(unitTestParams.getMajorityWindow() - i, instance.getCount(1).intValue());
assertEquals(i, instance.getCount(2).intValue());
instance.add(2);
}
}

@Test
public void testInitialize() throws BlockStoreException {
final BlockStore blockStore = new MemoryBlockStore(unitTestParams);
final BlockChain chain = new BlockChain(unitTestParams, blockStore);

// Build a historical chain of version 2 blocks
long timeSeconds = 1231006505;
StoredBlock chainHead = null;
for (int blockCount = 0; blockCount < unitTestParams.getMajorityWindow(); blockCount++) {
chainHead = FakeTxBuilder.createFakeBlock(blockStore, 2, timeSeconds).storedBlock;
assertEquals(2, chainHead.getHeader().getVersion());
timeSeconds += 60;
}

VersionTally instance = new VersionTally(unitTestParams);
instance.initialize(blockStore, chainHead);
assertEquals(unitTestParams.getMajorityWindow(), instance.getCount(2).intValue());
}
}